Steger Carsten 
  
SUBPIXEL-PRECISE EXTRACTION OF LINES AND EDGES 
Carsten Steger 
MV Tec Software GmbH 
Neherstrabe 1, 81675 München, Germany 
steger@mvtec.com 
Working Group 11/3 
KEY WORDS: Edge Detection, Line Detection, Subpixel Precision, Subpixel Accuracy, Bias 
ABSTRACT 
Novel approaches to extract curvilinear structures, i.e., lines and edges, from 2D images are proposed. For lines, explicit 
geometric models for line profiles are used to analyze their behavior in scale-space. From this analysis, algorithms to 
extract lines and their widths with subpixel resolution are derived, and it is shown that the line positions and widths are 
necessarily biased by the smoothing used in the extraction. Since the mapping that describes the bias is invertible, it can 
be removed, leading to unbiased and hence accurate results. To extract edges, they are regarded as bright lines in the 
gradient image. Furthermore, by a scale-space analysis it is shown why line and edge junctions often cannot be extracted. 
From this analysis, a new method to extract complete junction information is derived. Finally, the line and edge extraction 
algorithms are extended to multispectral images. 
1 INTRODUCTION 
Lines and edges are important objects for many applications. They arise quite naturally as the low-level primitives of 
choice to extract from images. For example, roads, railroads, and rivers can be regarded as lines in aerial or satellite 
images. The extraction of these kinds of objects is very important for the data capture or update of geographic information 
systems (GIS) (Baumgartner et al., 1999, Wiedemann et al., 1998). Obviously, for these applications the width of the line 
is essential since it characterizes the type of a road, for example. Edges are also important in numerous other applications, 
e.g., building extraction (Bignone et al., 1996, Fischer et al., 1997) or object recognition (Lanser et al., 1997). 
The approaches to line extraction can be classified into different categories (see (Steger, 1998b, Steger, 1998c) for a 
detailed review). In the first category, lines are regarded as ridges and ravines in the image (Eberly et al., 1994). Various 
differential geometric definitions can then be used to extract the ridges: as points on the contour line where the curvature is 
maximum (Maintz et al., 1996), as points where the principal curvature is a local maximum in the direction of maximum 
curvature (Armande and Montesinos, 1999), or as points where the gray values are restricted maxima or minima in the 
direction of the maximum eigenvalue of the Hessian (Busch, 1996). The first two definitions have the problem that ridges 
will often be extracted in the wrong position, even under very good conditions (Koenderink and van Doorn, 1994). Most 
notably, the first definition is unable to detect flat ridges, while the second definition will return a double response to a 
bar-shaped line if the image is not smoothed by a sufficient amount (Steger, 1998b). The third definition returns wrong 
line locations if the line has different lateral contrast, as we will see below. This definition can also be iterated through 
scale-space to obtain a coarse estimate of the line width (Lindeberg, 1998). The problem with this iterative scale-space 
approach is that at the optimal scale for width estimation the line position will in general be severely biased. None of the 
above approaches is able to extract lines that have a staircase profile. 
In the second category, lines are extracted by using special filters. In (Koller et al., 1995) lines are regarded as objects 
that have two parallel edges and filters tuned in direction and scale are constructed to extract them. A similar approach is 
used in (Heitger, 1995), where directionally tuned filters are used for feature detection. Since these filters also respond to 
non-features, another set of directionally tuned filters is used to suppress the unwanted responses. Another very similar 
approach is used in (Iverson and Zucker, 1995), where the suppression is done by a non-linear combination of the filters. 
The problem with all these approaches is that since special filters need to be constructed for several or even all possible 
line directions, the extractors are computationally very expensive. Furthermore, the last two approaches do not extract the 
line width. The first approach obtains a coarse estimate of the line width by an iteration through scale-space, which makes 
the approach even more expensive. The last two approaches can also be used to extract edges. 
A very interesting approach to the combined extraction of points, linear features (i.e., lines and edges), and blobs was 
proposed in (Fórstner, 1994, Fuchs, 1998). The average squared gradient, i.e., the matrix I'f = go, * (V(go, * JV(go,* 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 141