Line
ed. The models are
on of the recognition
method that is not
les, i.e. junctions or
0 find continuations
object. This yields a
or an object-related
to extract them by
aus digitalen Bildern
rung der Erkennung
Hilfe eines robusten,
ndwelche Annahmen
gen, und Enden der
1 und Fortsetzungen
2 zuzuordnen, die ein
_inien im Bild führt.
issifizierung geeignet
n kónnen.
oint. Other methods
ated to digital filter-
eciding for each pixel
994). A combination
' using line following
nethod is promising.
of a common frame-
mon model for both
ads to consistent re-
s that correspond to
tasks, e.g. threshold
e way.
vision in three levels,
)n), pattern recogni-
rstanding (high-level
ings to the mid-level
jitable for delivering
ails, and for comput-
all features and at-
r uncertainty can be
important for a valu-
xt level of computer
vision, i.e. image understanding. A major aspect of this pa-
per is the automation of linear feature extraction. We attach
importance to the fact that control parameters of the algo-
rithm are to a great extent independent of the image data,
i.e. they are standardized like, e.g. a significance level.
1.2 Underlying models
We use generic models for lines and edges which have a com-
mon mathematical background. The edge model is a third
order polynomial function that is fitted to the grey levels in
an image window. lt is known as facet model (Haralick et
al. 1983, Haralick 1984). The polynomial represents the grey
levels as a function of the row and column coordinates in an
image window and takes the form
g(z,y) = ko
+ kizckoy
+ kan? + kazy + ksy?
+ kez? 4 kız"y + kgxy” + koy® . (1)
The coefficients k; are determined by a least squares fit of the
polynomial in the image window. From this we have derived
our line model which is a second order polynomial function
(Busch 1993, 1994)
g(z, y) = ko
+ Kız + Kay
+ ksz® + kazy + ksy® (2)
The polynomial model offers great flexibility because it can
easily be used with arbitrary window sizes, and because the
grey levels in the image window can be weighted according
to different models, e.g. as in Box or Gaussian filters. Simple
classical gradient filters, like Sobel or Prewitt, are included as
special cases. Additionally, the redundancy of the polynomials
least squares fitting in an image window allows control and
self-diagnosis of the algorithm by means of statistical testing.
The decision whether a pixel is an edge pixel or a line pixel
is made from the first and second order derivatives of the
polynomial functions and their principal directions. For ex-
tracting edges we calculate the intersecting polynomial of (1)
which falls in the direction of the gradient vector. The centre
pixel of the image window is classified as an edge pixel if the
maximal absolute value of the polynomial's first derivative
is located inside the pixel and differs significantly from zero.
Line pixels are recognized using the intersecting parabola of
(2) which falls in the direction of maximal curvature. A pixel
is a line pixel if there is a zero crossing of the parabola's
first derivative, i.e. if the extremum of the parabola falls in-
side the pixel and if the parabola's curvature is sufficiently
large. By this procedure we obtain line and edge positions
with sub-pixel resolution.
2. DISCRIMINATING NOISE AND REAL DETAILS
The models introduced in Section 1.2 require a decision about
the significance of the absolute value of the polynomial's first
or second derivative since we want to know whether it is
different from zero in order to discriminate real details from
effects that are due to noise. We can do this by hypothesis
testing which is done individually for every image window, by
a single threshold that is applied to the whole image, or by a
combination of both methods.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
2.1 Hypothesis testing
A classical method for checking significance is hypothesis
testing. Since it is based on the assumption of normally
distributed observations it may lead to unsatisfactory results
when applied to image data where this condition is often vi-
olated (Busch 1994). Whenever hypothesis testing is applied
to images it must be checked whether it is sufficient to as-
sume that the data are normally — or whatever else might
be prerequisite — distributed.
2.2 Robust estimation
We want to estimate a threshold that allows to separate arte-
facts and spurious details in the image from salient lines and
edges. Thus, what we need is related to a noise estimate,
but it is different from thresholding techniques for binarizing
images (Sahoo et al. 1988).
The basic idea of the method is to produce an image with
a lot of noisy linear features and to estimate the threshold
from the noise then. In the first step we apply the method
of Section 1.2 using zero as threshold. Hence, the decision
about the line or edge attribute is made using only the loca-
tion of the extremum of the polynomial's derivative ignoring
the derivative's amount. To estimate a threshold from the
mass of pseudo features produced by this, we start with the
consideration that linear features in digital images are formed
by long chains of pixels. Thus, single, i.e. isolated pixels
classified as lines or edges are due to noise mostly and are
suitable items for deriving a noise estimate. So we collect
the derivatives of all single edge or line pixels and take their
median as a robust estimate for the typical derivative of a
noisy linear feature. As we are using isolated feature pixels
our approach is different to the one of Venkatesh and Rosin
(1995) who consider edge continuity and edge curves to de-
termine a threshold. To eliminate most of the single pixels we
must use a threshold which is larger than the median, since
the median eliminates half of the noise. We see this from its
definition:
M
Median M : J ples) des = 05 (3)
Here cs denotes the parameter which is the basis of the deci-
sion. This is the maximal absolute value of the polynomial's
first derivative in case of edge pixels and the curvature of the
parabola in case of line pixels. The index s reminds of the
fact that the probability density function p represents single
linear feature pixels.
By generalizing (3) we find thresholds corresponding to con-
venient significance levels
Poo
Tw. = Pos: y p(cs) des = 0.90
Ts
Pos : / p(c;) des = 0.95
Jt oi Poo; / p(cs). de, z 0.99 .. (4)
