v YD o o. Wo — D WW — (VU VO 
DD ww Uu XV 
Steger Carsten 
  
large asymmetry, the uncorrected line positions and widths are severely biased. This bias is removed by the correction 
step, as is clear from Figure 12(c). The extracted line corresponds closely to the true position and width of the road. 
As noted above, the algorithm proposed in this section makes sure not to extract lines of equal polarity. This was explicitly 
done because the line position and width correction is completely different for the two different types of lines. In some 
cases it might be useful to extract lines of equal and different polarity at the same time. The easiest way to achieve this 
would be to regard lines of equal polarity as dark lines in the gradient image also. Note that the modeling of the bias is 
not affected by this, since it only depends on the width and asymmetry of the line. In this case, however, the line position 
would not be given by (7), and hence the position correction would be invalid. Instead, an explicit correction would have 
to be computed numerically in the same manner as for lines of different polarity. 
2.4 Edge Extraction 
As discussed in Section 2.2, in a gradient image edges appear as bright lines. Hence, with the line extraction and linking 
algorithm of Section 2.2 it is possible to design an algorithm that turns an arbitrary gradient-based edge detector, such 
as the Canny (Canny, 1986), (isotropic) Deriche (Deriche, 1987, Lanser and Eckstein, 1992), (isotropic) Shen (Shen and 
Castan, 1992, Lanser and Eckstein, 1992) or even the Sobel operator, into a subpixel edge detector. 
Before the edge detection algorithm will be described, a few words on the model of the underlying edge are necessary. 
Most approaches use the step edge model (Canny, 1986, Deriche, 1987, Lanser and Eckstein, 1992, Shen and Castan, 
1992), i.e., assume the edge of height h to be given by hfe(x), where fe(x) is given by (1). Other approaches assume 
the edge to be a Gaussian-blurred step edge, i.e., its profile to be given by h¢, (x) (Lindeberg, 1998). While both these 
assumptions are useful, since they simplify the analysis of the operator considerably, for our purposes they are not strictly 
necessary. The main point about these step edge profiles is that they are symmetric with respect to the inflection point 
at x = 0. Therefore, if the absolute value of the first derivative of these profiles are taken, symmetrical line profiles 
are obtained. It is obvious that under this condition, and the condition that the smoothing filter the edge operator uses 
is symmetrical with respect to the origin, isolated lines, and hence also edges, will be extracted in the correct subpixel 
position. Of course, if the edge profile is not symmetric to its inflection points, the edge locations will be biased (Ulupinar 
and Medioni, 1990). If the correct edge model can be derived analytically, it is possible to model this bias with the 
techniques introduced in Sections 2.2 and 2.3, and hence to remove the bias. 
As a result of the above discussion, the facet model edge detection scheme used in Section 2.2 to extract the line width 
and in Section 2.3 to extract the line positions (as dark lines in the gradient image) and widths can be used to detect single 
edge points, and that the linking algorithm can be used almost unaltered. Only two modifications need to be made to the 
linking algorithm. The first one is concerned with the thresholds used in the linking algorithm. To obtain the standard 
feature used for edge selection — the gradient magnitude — the responses of the line detector are substituted by the 
response of the edge operator at the corresponding point. The second, and most important, change is how to implement 
the algorithm efficiently. It is obvious that the facet model line detector does not need to be run on the entire image since 
the lower threshold of the linking algorithm determines the points which cannot be edge points. Hence, the line detector 
only needs to be applied to the region of the image in which the response of the edge detector is higher than the lower 
hysteresis threshold. With these modifications, the resulting subpixel edge detector is only about 15% slower than the 
typical edge detection cycle of running the edge operator, doing a combined non-maximum suppression and hysteresis 
threshold operation, thresholding the resulting image, calculating a skeleton from this region, and linking the edge points 
into contours. This is a very small price to pay for the added bonus of subpixel accurate results. Examples of the results 
obtainable with the proposed edge detector are given in the next section. 
3 MISSING JUNCTIONS IN LINE AND EDGE EXTRACTION 
Missing junctions in edge extraction are a well-known problem (Rothwell et al., 1994). Unfortunately, the also occur 
for the line and edge extraction algorithms proposed in this paper. In this section, we will use explicit models to get a 
qualitative impression of the behavior of the line and edge detectors proposed above in the vicinity of junctions and derive 
an algorithm that is able to extract the complete junction information from an image. 
We will start by modeling junctions of lines. Consider a T-junction where lines of different width and different contrast 
meet. A model for this type of junction is 
hi, x2z0^l|y| wi 
ha, z«0^ly| € w» 
hs, |r| € w3 ^y « —w1 
0, otherwise . 
fi(z,y) = (19) 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 149