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