Steger Carsten 
  
True wo — 
          
         
     
       
      
        
  
  
X 
5050 
AN 
MAN 
5 
   
e. 
2 
X 
ES 
RES 
AG 
OK) 
KN) 
KD 
OO VA 
X VS 
DON 
20 % 
X 
X 
Q0 
X 
A 
% 
^ 
X 
% 
$ 
(X) 
"n 
ÿ 
X 
% 
(A 
% 
8 
^ 
Y 
5 
5 
2%) 
XX 
X 
X 
A 
X 
" 
hn 
A 
X 
  
(a) True wo (b) True a 
Figure 3: True values of the line width w, (a) and the asymmetry a (b). 
| algorithm (Press et al., 1992). To make the bias inversion efficient, f^! must be computed once offline and tabulated. 
Because of the scale-invariance property, the resulting table is an array of only two dimensions (v, and r), which makes 
the table manageable in size. 
In 2D, we can model lines as curves s(t) that exhibit a characteristic 1D profile in the direction perpendicular to the 
line, i.e., perpendicular to n(£) — s'(t). Hence, we can extract lines points in 2D by requiring that the first directional 
derivative in the direction n(¢) should vanish and the second directional derivative should be of large absolute value. The 
direction n(t) can be obtained for each pixel from the eigenvector corresponding to the eigenvalue of largest magnitude of 
the Hessian matrix of the smoothed image. The Hessian and the gradient result in a second-degree Taylor polynomial in 
each pixel, from which we can extract the line position with subpixel accuracy (Steger, 1998b). To extract the line width, 
the edges on the right and left side of the line are extracted by extracting edge points on a search line of length 2.50 in 
the direction +n(t). The length of the search line is motivated by the restriction o > w/ V/3. As mentioned above, edges 
are regarded as bright lines in the gradient image. Therefore, to extract edge points we need the first and second partial 
derivatives of the gradient image. The gradient image is given by 
  
  
  
e(z,y) = \ Lo(@ 9) fum y? = JR +R (8) 
where f (z, y) is the image smoothed with g, (x, y). The partial derivatives are given by: 
e = fotze + Foley (9) 
e 
oy = feft Jude (10) 
zjzzz t JyJaay + 2t 2 nel 
soon delen 4 hf + Fès + Fa - À d 
€ 
€ Safzıy + IT + Jez fey + "TRITT. — €g€y 5 
Exy = = (12) 
zjJzyy * JuJyyy + 2 + 2 —e? 
£99 = f f yy IPRETT. fi Toy y (13) 
  
e 
As can be seen, we need the third partial derivatives of the smoothed image, i.e., 8 convolutions in total. For efficiency 
reasons, the coefficients €, . . . , e,,, are computed by convolving the image with 3 x 3 facet model masks (Steger, 1998b). 
With this second-degree Taylor polynomial, the edge point extraction is exactly the same as the line point extraction above. 
Note that in contrast to standard edge detection approaches, the direction perpendicular to the edge is obtained from the 
Hessian of the gradient image, not from the gradient direction. We will see below what implications this definition has. 
The individual line points are linked into lines by an extension of Canny’s hysteresis thresholding algorithm (Canny, 1986) 
which takes the direction of the lines into account and correctly handles junctions (Steger, 1998b). 
Figures 4(a) and (c) display the result of extracting lines and their width with bias removal from an aerial image with a 
reduced resolution of 1 m. To assess the accuracy of the results, they are shown superimposed onto the original image of 
resolution 0.25 m. For comparison purposes, Figures 4(b) and (d) display the results without bias removal. Evidently, the 
algorithm was able to correct the line positions and widths successfully with high accuracy. 
2.3 Extraction of Lines with Different Polarity 
We would now like to use the same scale-space analysis techniques as for lines with equal polarity to design an algorithm 
that is able to extract lines with different polarity, which returns unbiased line positions and widths. This type of lines 
  
144 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.