ific geomet-
search. For
y with many
oundary de-
tanari, 1971;
rands, 1988;
(e.g. Witkin
.u & Agger-
Jertas, 1992;
nmens et al.
for road de-
ty De Gunst
he approach
schemes, be-
joundary de-
road classes:
5. Monadic
esent or not,
ut further ex-
chemes carry
patial extent
classify each
sion rule. No
or contextual
be generally
entiation, (2)
4) Curvature
oposed, such
f. Lee et al.
mputing the
onstis Ja 1
s. The small-
mple interval
1. Hence the
rete function
)-s(0) (1)
ivative in y-
gy become:
,J+1).) The
ording Eq.(1)
crack) edges.
ith the masks
spose. These
To evade this
.ccordingly gy
now be done
d [-1 0 1]7,
s defined by:
! (magnitude)
edge strength
ing computa-
tion time, are the Manhattan distance: M2 = |g=| + gg.
and the chess-board distance: Ms — max(|g«|,|g,]). The
magnitude and edge direction show a directional bias; they
depend on the orientation of the edge with respect to the
grid. For example the magnitude error of the Sobel opera-
tor may reach 7.93 % and the angle error 2.90 degrees for
ideal step edges, while the magnitude error of the Prewitt
operator may even reach 12.87 % and the angle error 7.43
degrees (Lyvers & Mitchell, 1988). To replace Mi by M» or
Ma is disadvantageous since the orientation dependent bias
is more severe for the last two measures. Ma corresponds
to template matching with just two hypothesized directions
(section 4.3). The gradient components |gx| and |gy| will
occupy only a limited grey value range -typically in the range
of the grey values when properly normalized- which is usu-
ally in the range 0-255. Therefore, when using the Euclidean
distance M;, one may save computation time by precomput-
ing all edge strengths that may occur and to store them in a
look-up table. Although the Prewitt (1970) operator is de-
rived from a surface fitting approach (section 4.2), its 3 x 3
version can also be understood as combining discrete differ-
entiation with an unweighted smoothing perpendicular to the
direction over which the gradient is computed, i.e. horizontal
gradient component: [—1 0 1] +[1 h 1]”, and vertical compo-
nent: [1 0 1]7 « [1 h 1], with h = 1 and x the convolution
sign. For the Sobel-operator h = 2 and for the Isotropic
operator h = V5.
The Sobel operator has been shown to be superior to other
small support operators, like the 3 x 3 Prewitt operator. The
background of the Sobel operator is that the grey values that
lie closest to the central pixel become a higher weight than the
grey values which lie farther away, yielding good smoothing
properties.
Since also other features than edges show up as abrupt in-
tensity changes, e.g. noise and texture, differentiation ap-
proaches actually detect non-edges. When the response ex-
ceeds the prespecified threshold, it is assumed that the de-
tected grey value variability is due to the presence of an edge.
The early edge detection schemes, such as the Sobel opera-
tor, were developed on a more or less intuitive base, without
much mathematical foundation. When one wants to detect
a feature in a signal in a reliable way, two phenomena should
be at least employed: (1) a model of the appearance of the
feature in the signal, and (2) knowledge about corruption
of the signal with disturbances such as noise. Commonly,
edges are modeled as ideal step functions, i.e. two grey val-
ues are assumed to be present in the local neighbourhood.
The disturbances are usually modeled as additive zero-mean
Gaussian distribtued noise, uncorrelated with the signal. The
remaining part of this section treats methods based on such
image models.
4.2 Surface Fitting
In an attempt to make edge detectors more immune to non-
edge features, much research efforts has been devoted to
model explicitly how edges may look like in the local image
function. One of the results are surface fitting approaches.
The local image function is modeled as a set of basis func-
tions, that express the theoretical edge. The surface is fitted
to the local image function according some optimalization
norm, usually the I?-norm.
Prewitt (1970) -she was the first to suggest the surface fitting
idea- approximates the local image function by a second order
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
polynomial: g(z, y) — do + a12 + a2Y + a3 TY + A4 z? -- asy?
resulting, after a least squares fit, in a 3 x 3 neighbourhood
in the Prewitt masks discussed in the previous section.
The Hueckel (1973) method involves finding the parameters
of the best fitting ideal step edge, assuming two grey values
in a circular neighbourhood of 32 to 137 pixels. The fitting is
done by the L?-norm using a set of two-dimensional orthonor-
mal basis functions by a Fourier series in polar coordinates.
The expansion is truncated to eight terms for computational
and smoothing reasons.
O'Gorman (1976) modifies the approach of Hueckel, by using
Walsh functions, instead of sin/cos basis functions. The ra-
tionale governing this choice is that the discrete image space
bears a simple relationship to Walsh functions.
Ghosal & Mehrotra (1993) model an ideal step edge, assum-
ing the presence of two grey values, by a set of orthogonal
complex Zernike moments.
Haralick (1984) extents the polynomial approach of Prewitt
(1970), by suggested a zero-crossing edge detector based on
the facet model, introduced in Haralick (1980), using directed
second order derivatives.
4.3 Template Matching
Another approach to explicitly model the appearance of edges
is by using templates. Template matching for edge detection
purposes is the process of moving a two-dimensional tem-
plate, representing a prototype edge, over the entire image.
At every pixel the local image function over a patch, which
has the same extent as the template, is compared with the
template. The elements of the templates can be chosen freely,
as long as they reflect the underlying edge model. It is conve-
nient to introduce normalized templates, in particular: semi-
normalized, normalized, and fully-normalized templates. Let
h;,t = 1,...,n, be the elements of a template h.
A template is semi-normalized if the mean of the elements is
zero: 377^, h; — 0. An example is shown in Figure 1a.
A template is normalized if the mean of the elements is
zero and its variance is m/(n, — 1), where m is the num-
ber of non-zero elements within the template: 5$ 7^, h; —
0; 3575, h? — m. An example is shown in Figure 1b. This
definition yields two consequences: (1) the template elements
can only take the values —1,0 and 1, and (2) the number of
elements that have value —1 equals the number of elements
with value 1. So, the number of same-signed values is 2m.
A template is fully normalized if the mean of the elements is
. . . . TK HM S Tk 2
0 and its variance is 1/(n« — 1): S ns Pm 0; S Ut EL
An example is shown in Figure 1c. To examine the presence
5 5 5 —1 0 1 —1 0 1
—3 0 —3 —1 0 1 id —1 0 1
-3 —3 -—3 —1 0 1 6 —1 0 1
a b C
Figure 1: — Examples of normalized templates: (a) semi-
normalized, (b) normalized, (c) fully normalized.
of an edge at each pixel, multiple templates are needed. Each
template is associated with a hypothesized edge orientation.
Let there be K orientations and consequently K templates:
437
ete a
