EVEN, Philippe 
  
The automatic process limitations should not affect the application domain of the modelling system. Specially virtual or 
nearly virtual edges are sometimes required (fig. 3). Their specification should be left possible. In the case of multiple 
failures, the assistance should be possibly deactivated. 
The assistance performance should be equivalent for similar images. This is important to make it predictable so that the 
operator can decide as soon as possible if he uses it or not. 
5 AUTOMATIC EDGE SEGMENT ATTRACTION 
The simultaneous extraction of multiple edges which are linked together through geometric constraints - global energy 
minimisation (Fua and Leclerc, 1988), part of a solid primitive (Läbe and Gülch, 1998), collinear line grouping (Shufelt, 
1999a) - is a way to provide robustness. But in Pyramide, lines are processed separately. A gradient based approach 
is used in (Debevec et al., 1996) to attract a manually defined line segment to the nearest edge contour. Because of the 
uncertain quality of the provided images by the on-board camera, we rather selected a more robust technique. 
First of all the operator quickly draws a line segment on the image. A classical edge contour extraction is then performed 
in the line segment vicinity. The extraction area is a rectangle which sides are parallel to the image borders. If My (x1,%1) 
and M»(z», y») are the manual segment ends, the extraction area is bounded by the line x,pin = Max(0, min(x;, x») — €), 
Ymin = Max(0, min(y1 ; Y2) = €); Tmax = min (max(z; , 23) Te Xu 1, and Ymaz = Min(Max(y1, ya) +e); Vom — D, 
where X;m and Y;m are the image size, and € is a system parameter fixed to 5 pixels. This value was found to be a 
good compromise between the method efficiency and its flexibility. It bounds the accepted approximation of the manual 
specification. 
The provided edge points are then analyzed using a Hough transform. The Hough transform translates the edge segment 
detection problem from the Euclidean space to some parameters space. It is based on a vote technique where each extracted 
edge point votes for a set of possible lines. Polar coordinates are a suitable parameterization to solve this specific problem 
(Duda and Hart, 1972). They are given by the orientation 0 of the normal vector and the distance p to the image origin 
(see fig. 4a). The line (p, 0) is the locus of points (z, y) defined by equation (1) : 
p — x cos(0) -- ysin(0) (1) 
Let Vo be the neighbourhood of a given line segment (po, 09) in the Hough space. Defined by a sampling of the local area 
around the line, an accumulator array is associated to Vo (equation 2). 
o = [00 — no - 60,00 + no - 66] x [po — n,-6p, Po + n.p] (2) 
The accumulator array dimension is N — (2n + 1) x (2n, + 1). Each extracted edge point P votes for the lines of Vo it 
belongs to. The highest number found in the accumulator array provides the polar coordinates of the best edge segment. 
yl sor 
      
  
  
4 
/ L 
/ 
/ 
/ 
Oj/ 
^ 1 1 1 
0 20 40 60 80 
Figure 4: a) The line segment polar coordinates in the Euclidean space. b) The Hough space, with angle 0 in degrees in 
abscissae and p in mm in ordinate : each curve determines the possible lines passing through one edge point. 
  
100 120 140 160 180 
Properties of the Hough transform are discussed in (Illingworth and Kittler, 1988). Its major drawback deals with the 
large amount of storage and computation required when the dimension of the parameters space is high. But in our case, 
this dimension is only two. The computation time depends mostly on the definition factors 60 and 6 p, on the cell number 
N, and on the number of edge points that participate to the vote. The availability of an initial solution allows a reduction 
of the search space and then contributes to a shorter computation time. 
The Hough transform is very robust to possible occlusions; edge points on each part of the occluded edge vote for the 
same line. It also lowers the influence of spurious edge points due to detection noise, disturbing reflects or close objects. 
For two very close edge contours, the Hough transform provides the most influent one, but not some average line between 
both contours. The Hough transform is applied twice, the first time with a coarse definition to lower the vote dispersion, 
the second time with a finer definition to provide a good accuracy. 
  
226 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B5. Amsterdam 2000. 
  
The 
mag 
disp 
autc 
clic 
the 
und 
The 
aut 
the 
Be 
is \ 
sec 
im: 
siti