2
–1
–1
0
Figure 4.3 Template for first order difference
edge(pic):=
newpic
←
zero(pic)
for x∈0..
cols(pic)–2
for y∈0..
rows(pic)–2
newpic
y,x
←
2
.
pic
y,x
–pic
y,x+1
–pic
y+1,x
newpic
Code 4.1 First order edge detection
Uniform thresholding (Section 3.3.4) is often used to select the brightest points, following
application of an edge detection operator. The threshold level controls the number of selected
points; too high a level can select too few points, whereas too low a level can select too
much noise. Often, the threshold level is chosen by experience or by experiment, but it can be
determined automatically by considering edge data (Venkatesh and Rosin, 1995), or empirically
(Haddon, 1988). For the moment, let us concentrate on the development of edge detection
operators, rather than on their application.
4.2.2 Analysis of the basic operators
Taylor series analysis reveals that differencing adjacent points provides an estimate of the first
order derivative at a point. If the difference is taken between points separated by x then by
Taylor expansion for fx +x we obtain:
fx +x = fx +x ×f
x +
x
2
2!
×f
x +Ox
3
(4.5)
By rearrangement, the first order derivative f
x is:
f
x =
fx +x −fx
x
−Ox (4.6)
This shows that the difference between adjacent points is an estimate of the first order derivative,
with error Ox. This error depends on the size of the interval x and on the complexity
of the curve. When x is large this error can be significant. The error is also large when
the high-order derivatives take large values. In practice, the short sampling of image pixels
and the reduced high-frequency content make this approximation adequate. However, the error
can be reduced by spacing the differenced points by one pixel. This is equivalent to computing
the first order difference delivered by Equation 4.1 at two adjacent points, as a new horizontal
difference Exx, where
Exx
xy
=Ex
x+1y
+Ex
xy
=P
x+1y
−P
xy
+P
xy
−P
x−1y
=P
x+1y
−P
x−1y
(4.7)
Low-level feature extraction (including edge detection) 119
This is equivalent to incorporating spacing to detect the edges Exx by:
Exx
xy
=
P
x+1y
−P
x−1y
∀x ∈ 2N −1y∈ 1N (4.8)
To analyse this, again by Taylor series, we expand fx −x as:
fx −x = fx −x ×f
x +
x
2
2!
×f
x −Ox
3
(4.9)
By differencing Equation 4.9 from Equation 4.5, we obtain the first order derivative as:
f
x =
fx +x −fx −x
2x
−Ox
2
(4.10)
Equation 4.10 suggests that the estimate of the first order difference is now the differ-
ence between points separated by one pixel, with error Ox
2
.Ifx < 1, this error is
clearly smaller than the error associated with differencing adjacent pixels, in Equation 4.6.
Again, averaging has reduced noise, or error. The template for a horizontal edge detection
operator is given in Figure 4.4(a). This template gives the vertical edges detected at its
centre pixel. A transposed version of the template gives a vertical edge detection operator
(Figure 4.4b).
1
1
–1
–1
0
(a) Mx (b) My
0
Figure 4.4 Templates for improved first order difference
The Roberts cross operator (Roberts, 1965) was one of the earliest edge detection operators. It
implements a version of basic first order edge detection and uses two templates which difference
pixel values in a diagonal manner, as opposed to along the axes’ directions. The two templates
are called M
+
and M
−
and are given in Figure 4.5.
+1 +1
–1
(a) M
–
(b) M
+
–100
0
0
Figure 4.5 Templates for Roberts cross operator
In implementation, the maximum value delivered by application of these templates is stored
as the value of the edge at that point. The edge point E
xy
is then the maximum of the two
values derived by convolving the two templates at an image point P
xy
:
E
xy
=max
M
+
∗P
xy
M
−
∗P
xy
∀x y ∈ 1N −1 (4.11)
120 Feature Extraction and Image Processing
Get Feature Extraction & Image Processing, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
