EXTRACTING LINES USING DIFFERENTIAL GEOMETRY AND GAUSSIAN SMOOTHING
Carsten Steger
Forschungsgruppe Bildverstehen (FG BV)
Informatik IX, Technische Universität München
Orleansstr. 34, 81667 München, Germany
Ph.: +49-89-48095-122, Fax: +49-89-48095-203
E-mail: stegerc @informatik.tu-muenchen.de
Commission IIl, Working Group 2
KEY WORDS: Vision, Algorithms, Mathematics, Recognition, Feature Extraction, Aerial Imagery, Satellite Imagery
ABSTRACT
A new approach to the extraction of curvilinear structures from digital images is described. The approach is based on computing a
second order Taylor polynomial for each pixel in the image by convolution with derivatives of a Gaussian smoothing kernel. Line
points are found based on differential geometric properties of this polynomial: they are required to have a vanishing gradient and a
high curvature in the direction perpendicular to the line. The line direction is obtained from the eigenvectors of the Hessian matrix.
Because Gaussian masks are used to determine the polynomial the filter generates only a single response for each line. Furthermore,
the line position can be determined with sub-pixel precision and the algorithm scales to lines of arbitrary width. An analysis about the
scale-space behaviour of two typical line types (parabolic and bar-shaped) is given. From this analysis, requirements and useful values
for the parameters of the filter can be derived. Furthermore, an algorithm that links the individual line points into lines and junctions
is given. Its advantage is that it preserves the maximum number of line points while providing a topologically sound data structure of
lines and junctions. The versatility of the presented algorithm is illustrated through examples on a number of different aerial images.
1 INTRODUCTION
Extracting lines in digital images is an important low-level oper-
ation in computer vision that has many applications, especially in
photogrammetric and remote sensing tasks. There it can be used
to extract linear features, like roads, railroads, or rivers, from
satellite or low resolution aerial imagery.
The published schemes to line detection can be classified
into three categories. The first approach detects lines by only
considering the gray values of the image (Fischler et al., 1981,
Jedynak and Rozé, 1995). Line points are extracted by using
purely local criteria, e.g., local gray value differences. Since
this will generate a lot of false hypotheses for line points,
elaborate and computationally expensive perceptual grouping
schemes have to be used to select salient lines in the image
(Fischler, 1994, Jedynak and Rozé, 1995). Furthermore, lines
cannot be extracted with sub-pixel precision.
The second approach is to regard lines as objects having parallel
edges (Koller et al., 1995, Subirana-Vilanova and Sung, 1992).
In a first step, the local direction of a line is determined for each
pixel. Then two edge detection filters are applied in the direction
perpendicular to the line. Each edge detection filter is tuned to
detect either the left or right edge of the line. The responses of
each filter are combined in a non-linear way to yield the final
response of the operator (Koller et al., 1995). The advantage of
this approach is that since the edge detection filters are based on
the derivatives of Gaussian kernels, the procedure can be iter-
ated over the scale-space parameter o to detect lines of arbitrary
widths. However, because special directional edge detection fil-
ters have to be constructed that are not separable, the approach is
computationally expensive.
In the third approach, the image is regarded as a function z(z, y)
and lines are detected as ridges and ravines in this function by lo-
cally approximating the image function by its second or third
order Taylor polynomial. The coefficients of this polynomial
are usually determined by using the facet model, i.e., by a least
squares fit of the polynomial to the image data over a window of
a certain size (Glazer, 1994, Busch, 1994, Haralick et al., 1983).
The direction of the line is determined from the Hessian matrix
821
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
of the Taylor polynomial. Line points are then found by selecting
pixels that have.a high second directional derivative, i.e.. a high
curvature, perpendicular to the line direction. The advantage of
this approach is that lines can be detected with sub-pixel precision
without having to construct specialized directional filters. How-
ever, because the convolution masks that are used to determine the
coefficients of the Taylor polynomial are rather poor estimators
for the first and second partial derivatives this approach usually
leads to multiple responses to a single line, especially when masks
larger than 5 x 5 are used to suppress noise. Therefore, the ap-
proach does not scale well and cannot be used to detect lines that
are wider than about 5 pixels.
In this paper an approach to line detection that uses the differ-
ential geometric approach of the third category of operators will
be presented. In contrast to those, the coefficients of a second
order Taylor polynomial are determined by convolving the image
with the derivatives of a Gaussian smoothing kernel. Because
of this, the algorithm can be scaled to lines of arbitrary width.
Furthermore, the behaviour of the algorithm in scale space is in-
vestigated for various types of lines. Finally, an algorithm to link
the detected line points into a topologically sound data structure
of lines and junctions is presented.
2 DETECTION OF LINE POINTS
2.4 Models for Lines in 1D
Many approaches to line detection consider lines in 1D to be
bar-shaped, i.e., the ideal line of width 2w and height ^ is assumed
to have a profile given by
However, due to sampling effects of the sensor, lines usually do
not have this flat profile. Therefore, in this paper lines are assumed
to have an approximately parabolic profile. The ideal line of width
2w and height h is then given by
on [URL (wy,
mco zd 0,
h,
0.
jo] € w
Ie] uw! d
fo(x)
jz] < w
m (2)
rl n
