A COMMON FRAMEWORK FOR THE EXTRACTION OF LINES AND EDGES
Andreas Busch
Institut für Angewandte Geodäsie
Frankfurt am Main
Germany
e-mail: busch@ifag.de
Commission Ill, Working Group 2
KEY WORDS: Statistics, Vision, Extraction, Mapping, Edge, Pattern Recognition, Robust Estimation, Line
ABSTRACT
In this paper models for extracting lines and edges, i.e. linear features, from digital images are presented. The models are
based on a common mathematical approach. In this connection importance is attached to the automation of the recognition
of lines and edges. A threshold that is required by the models is estimated by a robust method, i.e. a method that is not
sensitive to outliers and that requires no assumption about the statistical distribution of the data. Nodes, i.e. junctions or
crossings, and ends of the linear features are recognized and analysed to improve the results there and to find continuations
of objects. If we extract both, lines and edges, we are able to find pairs of edges that bound one line object. This yields a
complete description of a line and a segmentation of the lines in the image.
An example using satellite image data of SPOT shows that the spectral signatures are suitable for an object-related
classification, and that it is possible to distinguish different objects, e.g. rivers and autobahns, and to extract them by
knowledge-based techniques.
KURZFASSUNG
In diesem Beitrag werden Modelle fiir die Extraktion von Kanten und Linien, also linienhafter Merkmale, aus digitalen Bildern
vorgestellt, die auf einem gemeinsamen mathematischen Ansatz beruhen. Dabei steht die Automatisierung der Erkennung
von Kanten und Linien im Vordergrund. So wird ein Schwellwert, den die Modelle benötigen, mit Hilfe eines robusten,
d.h. gegenüber Ausreißern unempfindlichen Verfahrens, anhand der Bilddaten geschätzt, ohne daß irgendwelche Annahmen
über die statistische Verteilung der Daten erforderlich sind. Knoten, also Verzweigungen oder Kreuzungen, und Enden der
linienhaften Merkmale werden erkannt und analysiert, um an diesen Stellen die Ergebnisse zu verbessern und Fortsetzungen
von Objekten zu erkennen. Werden sowohl Kanten als auch Linien extrahiert, ist es möglich, Kantenpaare zuzuordnen, die ein
Linienobjekt begrenzen, was zur vollständigen Beschreibung einer Linie und zu einer Segmentierung der Linien im Bild führt.
Ein Beispiel mit Satellitenbilddaten von SPOT zeigt, daß spektrale Signaturen für eine objektbezogene Klassifizierung geeignet
sind und so Objektarten, z.B. Flüsse und Autobahnen, unterschieden und wissensbasiert extrahiert werden können.
1. INTRODUCTION
1.1 Background
Our approach for extracting linear features from digital im-
ages is based on the conceptual distinction of lines and edges.
These basic terms are best explained by an example. For
instance, we realize objects like roads and rivers in satellite
imagery as lines, which are bounded by two edges. Since lines
are formed by two edges, they are more complex objects than
edges. To both, lines and edges, we refer as linear features
or linear objects.
Owing to their different complexity line and edge detection
have developed separately. A large variety of edge detectors,
mostly based on linear filtering techniques, is known from
image processing. They range from classical methods like
Roberts, Sobel, or Prewitt gradient filters (see e.g. Haralick
and Shapiro 1992/93, vol.1, p.337) to sophisticated meth-
ods like Canny (1986) and Deriche (1990) edge detectors.
However, line detection is usually done by line following (e.g.
Grün 1994). The disadvantage of these techniques is that
they are often semi-automatic since a starting point for the
algorithm is given by an operator. On the other hand it is
favourable that interpretation of an object is directly done by
88
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
the operator when selecting a starting point. Other methods
for finding lines in digital images are related to digital filter-
ing because they scan the whole image deciding for each pixel
whether it is a line pixel or not (Busch 1994). A combination
of both approaches for line detection by using line following
for improving the results of the second method is promising.
The goal of this work is the derivation of a common frame-
work for line and edge extraction. A common model for both
linear features is advantageous since it leads to consistent re-
sults and allows linking of lines and edges that correspond to
one object. It is possible to process some tasks, e.g. threshold
estimation, for both features in the same way.
If we stick to the subdivision of computer vision in three levels,
namely image processing (low-level vision), pattern recogni-
tion (mid-level vision), and image understanding (high-level
vision), the main part of this paper belongs to the mid-level
of computer vision. The approach is suitable for delivering
salient objects, eliminating spurious details, and for comput-
ing useful attributes of the objects. For all features and at-
tributes statistical measures of quality or uncertainty can be
derived from the image data. They are important for a valu-
able and complete data flow to the next level of computer
vision, i.e.
per is the :
importanc
rithm are
i.e. they a
1.2 Und
We use ge
mon math
order poly
an image
al. 1983, I
levels as a
image win
g(z
The coeffi
polynomia
our line m
(Busch 19
g(x
The polyn
easily be i
grey levels
to differen
classical g
special cas
least squa
self-diagn:
The decis
is made f
polynomia
tracting e
which fall:
pixel of th
maximal :
is located
Line pixel
(2) which
is a line |
first deriv;
side the |
large. By
with sub-|
2. DIS
The mode
the signifi
or second
different f
effects th:
testing wt
a single tl
combinati
