150 7
100 q
0.6 0.7 0.8
Figure 1: Typical distribution of the gradient/curvature of
single linear feature pixels. It has been obtained by dividing
the range of the parameter into 100 intervals of equal width
and by counting the number of occurences in each interval.
Additionally, the median and the thresholds corresponding to
the significance levels 90%, 95%, and 99% are shown.
0.1
Figure 1 shows an example of the discrete distribution of the
derivative of single pixels that are classified as linear features.
Typically, some thousand single pixels are found when apply-
ing the method to images of 1000 x 1000 pixels. So we have
a sample that is large enough to obtain a statistically well-
founded estimate for the threshold. Generally, the thresholds
(4) range between the second and sixth multiple of the me-
dian. The advantage of this estimation is that we do not need
any assumption about the underlying distributions, neither for
the distribution of the observation, i.e. the grey values, nor
for the distribution of the isolated feature pixels. Because the
thresholds (4) were developed from the median (3) they have
properties in common with the median. Especially, the esti-
mated thresholds are not sensitive to a certain percentage of
outliers, i.e. they are robust. This estimation technique has
proven to be very powerful with a variety of digital images of
any resolution (satellite, aerial, close range, and microscopic
images) which have been tested by the author.
2.3 Less sensitive hypothesis testing
The methods presented in Sections 2.1 and 2.2 have different
properties. While hypothesis testing is based on a local de-
cision that is made individually for every image window, the
robust estimation leads to one global threshold for all pixels.
Tests with lots of different images have shown that hypoth-
esis testing tends to give some more details than the robust
estimate, but also more noise. The robust estimate delivers
all details that rise above the estimated noise level.
It is possible to combine both methods by using a threshold
that excludes small values from hypothesis testing and that
rejects them anyway. This may be interpreted as a less sen-
sitive hypothesis test (Koch 1985, Koch 1990, p.88). The
threshold must be distinctly smaller than those given in (4).
We recommend to use values smaller than the median. Al-
though the threshold can be measured as a fraction of the
median, it is an additional control parameter of the algorithm
that complicates automatic processing.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
3. FROM PIXELS TO OBJECTS
The results of the methods presented in Section 2 are given
as an iconic representation, i.e. they are images again. Ad-
ditionally, we have line or edge positions with sub-pixel reso-
lution. To improve the results further steps of processing are
necessary. In detail these are a skeletonization process and
the detection of end and node pixels (Schickler 1992, Busch
1994).
Since the extracted lines and edges are sometimes wider than
one pixel we thin them by a skeletonization process that leads
to linear features of a width of one pixel. We use a skele-
tonization method designed specially for linear features. It
is based on the line and edge model, makes use of their di-
rection and works carefully to preserve the topology of the
line or edge network. Behind this is the concept of evading
decisions that are made better at a later stage of computer
vision.
All pixels belonging to linear features are classified as ends,
nodes, i.e. sites where linear features join or cross, or simple
members of a line or an edge. A grouping process links line or
edge pixels to objects which connect node and/or end pixels.
Closed chains of pixels without any end or node pixel are
recognized, too. By this we have a vector representation of
the linear features.
3.1 Analysis of nodes and ends
We want to take a closer look at nodes and ends now since
they are known to be the crucial point of linear feature extrac-
tion. So the models of Section 1.2 may fail at nodes because
the structure there does not correspond to the line or edge
model. This leads to gaps in the linear features that have to
be closed. Besides these spurious gaps and ends we have real
ends of the linear features visible in the image which typically
occur if objects overlap each other. Thus, we have to analyse
nodes and ends to enhance the extraction process there.
When examining nodes and ends we are looking for end pix-
els and other nodes nearby. The prospect is to find items for
closing gaps and to unite linear features. The number and
the length of the converging linear features are helpful crite-
ria for measuring the significance and importance of a node.
Nodes are classified as crossings, i.e. four linear features are
meeting, and branches or junctions, i.e. three linear features
converge. The topology of the node and the direction of the
meeting of linear features allow to find features which are each
other's continuation. If there is an even number of incoming
linear features, we have unique correspondence of opposite
features. Additional information comes from the direction
of the linear features. Sometimes there may be also pseudo-
nodes, i.e. nodes where two linear features meet. They occur
because the careful skeletonization algorithm avoids thinning
if the structure is ambiguous. We analyse the pseudonodes
to eliminate them by joining the incoming linear objects or
to classify them as corners which are recognized using the
direction of the linear features.
3.2 Combining lines and edges
If we extract both, lines and edges, we are able to find pairs
of edges that correspond to a line object, i.e. bound one
line. This is much easier than trying to find parallel edges
without knowing the line object. Besides the geometric ac-
curacy of the line position benefits from this, since — due
to the symmetric parabolic model (2) — the line position is
90
Figure 2:
with extrac
resolution -
affected by
the line. S
more exac
neighbour!
rection of
descriptior
the segme
based on «
Figure 2 a
The meth
computer
depicted !
used to fir
resolution.
We want
