the local direc-
t are compatible
he current pixel
s in the interval
Desde).
riate neighbour
n the respective
the two points.
two points and
erence between
line is the one
lation, 6 z 1 is
1 the correct or-
follow without
ron. The algo-
nore line points
e best matching
to another line.
and the line that
ction point.
rting point has
a certain, user-
? current line as
er than another
to a hysteresis
s similar to that
st neighbour is
depend on the
iuthor does not
'enerated by the
) deal with mul-
nodel approach
d. No such case
13. Under this
Additionally, if
rection perpen-
nd (cz, Cy + |)
sed if they have
"mination crite-
ssed line points
r line.
points in Fig. 4
inal image. In
e., all lines, no
shold of 5 were
(a) New approach (o = 1.5)
(b) Facet model (7 X 7)
Figure 5: Linked lines detected using the new approach (a) and using the facet model (b). Lines are drawn in white while junctions are
displayed as black crosses.
used only the salient lines would be selected. It is apparent that
the lines obtained with the new approach are much smoother
than the lines obtained with the facet model. Furthermore, the
geometric precision in case of unequal contrast is better with the
new approach. Note, for example, the line that enters the image
at the bottom right corner. This line has quite a different contrast
on both sides. With the new approach the line is within half a
pixel of the true location of the line while with the facet model it
lies more than one pixel from the true line.
4 FURTHER EXAMPLES
In this section some more examples of the versatility of the pro-
posed approach will be given. Figure 6(a) shows the complete
aerial image from which the image in Fig. 4 was taken. In this
example, v — 1.5 and only bright lines that had a second deriva-
tive with an absolute value larger than 8 were selected. The lower
threshold for the hysteresis was set to 3. It can be seen from
Fig. 6(b) that the algorithm is able to extract most of the salient
lines from the image.
Figure 7 shows that the presented approach scales very well. In
Fig. 7(a) an aerial image with a ground resolution of = 50 cm is
displayed (the original test image suburb_1 has been reduced
by a factor of 2). The lines in this image are approximately bar-
shaped. If 35 pixel wide lines are to be detected, i.e., it w = 17.5,
according to (10), a ¢ > 10.1036 should be selected. In fact,
c — |l was used for this image. If lines with a contrast of
h > 100 are to be selected, (9) shows that these lines will have
a second derivative of zz —0.29594. Therefore, the threshold for
the absolute value of the second derivative was set to 0.29. The
lower threshold was set to 0.1. Figure 7(b) displays the lines that
were detected with these parameters. As can be seen, most of the
roads were detected. Most of the lines in this image have different
contrasts on both sides of the line. Therefore it is not surprising
that the detected lines deviate slightly from the true centers of the
lines. This is especially true for the horizontal line in the bottom
right part of the image. However, even this line is detected within
the boundaries of the actual line.
5 CONCLUSIONS
In this paper a low-level approach to the extraction of curvilin-
ear structures from images was presented. An analysis of the
scale-space behaviour of two distinct line types was carried out.
The results of this analysis help tremendously in the selection of
the appropriate parameters for the algorithm. The advantages of
this approach are that line extraction is done using only the first
825
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
and second directional derivatives of the image. No specialized
directional filters are needed. This makes the approach computa-
tionally efficient. For instance, the 520 x 560 image in Fig. 6 was
processed in 8 seconds on a HP 735 workstation. Furthermore,
since the derivatives are estimated by convolving the image with
the derivatives of a Gaussian smoothing kernel, only a single re-
sponse is generated for each line. The algorithm has no problems
extracting line points where three or more lines meet.
An algorithm has been presented that links the extracted line
points into a data structure containing lines and junctions. Al-
though the algorithm itself does not attempt any perceptual group-
ing, the data structure that is generated will facilitate this in a
higher-level step.
The presented approach shows two fundamental limitations.
Firstly, if a line has highly different contrasts on each side oft the
line, the position of the line will be estimated in a different position
than the actual center of the line. This is a fundamental limitation
of other approaches as well (Koller et al., 1995, Busch, 1994). In
this paper, an analysis was carried out that shows how the position
will vary with differing contrasts. Secondly, only a combined
estimate of the width and height of the line is returned. This
means, that narrow lines with high contrast will result in similar
responses as broad lines with low contrast. This contrasts with the
approach given in (Koller et al., 1995) that returns an estimate of
the width of the line as well as the height of the line at the expense
of computational complexity. However, if only lines of a certain
range of widths are present in an image, the combined estimate
presents no fundamental limitation since it will then depend only
on the contrast of the lines.
REFERENCES
Busch, A., 1994. Fast recognition of lines in digital images with-
out user-supplied parameters. In: International Archives of Pho-
togrammetry and Remote Sensing, Vol. XXX, Part 3/1, pp. 91-97.
Canny, J., 1986. A computational approach to edge detection.
IEEE Transactions on Pattern Analysis and Machine Intelligence
8(6), pp. 679—698.
Deriche, R., 1993. Recursively implementing the gaussian and its
derivatives. Rapport de Recherche 1893, INRIA, Sophia Antipo-
lis, France.
Fischler, M. A., 1994. The perception of linear structure: A
generic linker. In: Image Understanding Workshop, Morgan
Kaufmann Publishers, pp. 1565-1579.
