Edge Detection by Zero Crossings

Principle

−

Edges constitute zero crossings in second-order derivatives (Fig. 12.1). Therefore, the second-order derivatives in all directions can simply be added up to form a linear isotropic edge detector with the transfer func- tion  (π k˜ )2 (Eq. (12.5)), known as the Laplacian operator. From Fig. 12.1 it is also obvious that not every zero crossing constitutes an edge.

Only peaks before and after a zero that are signifi cantly higher than the noise level indicate valid edges. From Fig. 12.1 we can also conclude that edge detection with the Laplace operator is obviously much more sensitive to noise in the signal than edge detection using a gradient-based approach.

12.4 Edge Detection by Zero Crossings                                        329

 

Laplace Filter

We can directly derive second-order derivative operators by a twofold application of fi rst-order operators

x

D2 = − D_x +D_x.                                              (12.42)

In the spatial domain, this means

 

[1_• − 1] ∗ [1 − 1_•] = [1 − 2 1].                                  (12.43)

The discrete Laplace operator L= D2 + D2 for 2-Dimages thus has the

fi lter mask

 

Σ

x

 

Σ  1 

y

 

 0   1 0 

L = 1 − 2 1

+    − 2    =    1  − 4  1                   (12.44)

 

 

and the transfer function

 1   0  1 0

ˆ l( k ˜ ) = − 4 sin²(π k˜ x/2) − 4 sin²(π k˜ y /2).                                  (12.45)

Like other discrete approximations of operators, the Laplace operator is only isotropic for small wave numbers (Fig. 12.9a):

48

48

ˆ l(k˜, φ ) = − (π k˜ )2 +  3 (π k˜ )4 +  1

cos 4φ (π k˜ )4 + O(k˜ 6).              (12.46)

 

There are many other ways to construct a discrete approximation for the Laplace operator. An interesting possibility is the use of binomial masks. With Eq. (11.23) we can approximate all binomial masks for suf- fi ciently small wave numbers by

4

B − I

bˆ 2R(k˜ ) ≈ 1 − R (k˜ π )2 + O(k˜ 4).                                       (12.47) From this equation we can conclude that any operator                                                                               p         consti-

tutes a Laplace operator for small wave numbers. For example,

 1  1 2 1 

 0 0 0  

L ' = 4( B

− I )  =    4    2  4  2    −    0  4  0     

1 2 1

1  1      2 1 

1      2 1

= 4    2  − 12  2   

0 0 0

(12.48)

 

with the transfer function

ˆ l'( k ˜ ) = 4 cos²(π k˜ x/2) cos²(π k˜ y /2) − 4                                  (12.49)

330                                                                                                                    12 Edges

 

a                                                                    b

0

-2

-4

-6

-8

-1

-0.5

0

 

 

c

0.5  ~

k x

 

1 -1

 

 

0

 

-0.5

 

 

1

 

0.5

~

k y

 

0.2

0.1

0

-0.1

-0.20

 

 

d

0.2

 

0.4

 

 

0.6

 

 

0.8 ~

k 1 0

 

 

0.5

 

1.5

q

1

 

0

-1

-2

-3                                                                                     ~

 

 

1

 

0.5

 

 

0.2

0.1

0

 

1.5

q

-4

-1

-0.5

0

 

0.5

 

~

k x 1 -1

k y

0

 

-0.5

-0.1

-0.20

 

0.2

 

 

0.4

 

0.6

 

 

0.8 ~

k 1 0

1

 

 

0.5

Figure  12.9:   Transfer functions of discrete Laplace operators and their anisotropy: a L Eq. (12.44), b ˆ l(k, θ ) − ˆ l(k, 0), c L' Eq. (12.48), d ˆ l'(k, θ ) − ˆ l'(k, 0).

 

is another example of a discrete Laplacian operator. For small wave numbers it can be approximated by

32

96

ˆ l'(k˜, φ ) ≈ − (π k˜ )2 +  3 (π k˜ )4 −  1

cos 4φ (π k˜ )4 + O(k˜ 6).              (12.50)

 

For large wave numbers, the transfer functions of both Laplace operators show considerable deviations from an ideal Laplacian, − (π k˜ )2.  L'  is signifi cantly less anisotropic than L (Fig. 12.9).

 

Regularized Edge Detection

Principle

The edge detectors discussed so far are still poor performers, especially in noisy images. Because of their small mask sizes, they are most sen- sitive to high wave numbers. At high wave numbers there is often more noise than signal in images. In other words, we have not yet consid- ered the importance of scales for image processing as discussed in Sec- tion 5.1.1. Thus, the way to optimum edge detectors lies in the tuning of edge detectors to the scale (wave number range) with the maximum

12.5 Regularized Edge Detection                                                  331

A                                                                    b

0.2

0.1

0

-0.1

-0.2

 

 

0.2

 

0.4

 

 

0.6

 

 

0.8 ~

k 1 0

 

0.5

 

1.5

q

1

 

10°

5°

0

-5°

-10°

 

 

0.2

 

0.4

 

 

0.6

 

 

0.8 ~

k 1 0

 

0.5

 

1.5

q

1

×

Figure 12.10: a Anisotropy of the magnitude and b error in the direction of the gradient based on the 2 2 cross-smoothing edge detector Eq. (12.51). The parameters are the magnitude of the wave number (0 to 1) and the angle to the x axis (0 to π /2).

 

signal-to-noise ratio. Consequently, we must design fi lters that perform a derivation in one direction but also smooth the signal in all directions. Smoothing is particularly eff ective in higher dimensional signals be- cause smoothing in all directions perpendicular to the direction of the gradient does not blur the edge at all. Derivative fi lters that incorpo- rate smoothing are also known as regularized edge detectors because they result in robust solutions for the ill-posed problem of estimating

derivatives from discrete signals.

 

12.5.2 2 × 2 Cross-Smoothing Operator

×

The smallest cross-smoothing derivative operator has the following 2                       2 masks

D _x B _y = 1 Σ 1  − 1 Σ      and D _y B _x = 1 Σ      1   1 Σ     (12.51)

2  1  − 1                                      2  − 1 − 1

and the transfer functions

dˆ xbˆ y ( k ˜ )  =  2i sin(π k˜ x/2) cos(π k˜ y /2) dˆ y bˆ x( k ˜ )  =  2i sin(π k˜ y /2) cos(π k˜ x/2).

 

(12.52)

There is nothing that can be optimized with this small fi lter mask. The fi lters D _x = [1 − 1] and D _y = [1 − 1]^T are not suitable to form a gradient operator, because D _x and D _y shift the convolution result by half a grid constant in the x and y directions, respectively.

The errors in the magnitude and direction of the gradient for small wave numbers are

m                 ≈ −            +

e  (k˜, φ )         (π k˜ )3 sin² 2φ

24

O(k˜ 5).                    (12.53)

332                                                                                                                    12 Edges

 

A                                                                    b

0.2

0.1

0

-0.1

-0.2

 

0.2

 

 

0.4

 

0.6

 

 

0.8 ~

k 1 0

 

 

0.5

 

 

1.5

q

1

10°

5°

0

-5°

-10°

 

0.2

 

 

0.4

 

0.6

 

 

0.8 ~

k 1 0

 

 

0.5

 

 

1.5

q

1

Figure 12.11: a Anisotropy of the magnitude and b error in the direction of the gradient based on the Sobel edge detector Eq. (12.55). Parameters are the magnitude of the wave number (0 to 1) and the angle to the x axis (0 to π /2).

 

φ                  ≈ −           +

e  (k˜, φ )         (π k˜ )2 sin 4φ

48

O(k˜ 4).                      (12.54)

=           −

The errors are signifi cantly lower (a factor two for small wave numbers) as compared to the gradient computation based on the simple diff er- ence operator D ₂ 1/2 [10 1] (Figs. 12.5 and 12.10), although the anisotropic terms occur in terms of the same order in Eqs. (12.28) and (12.29).

 

Sobel Edge Detector

The Sobel operator is the smallest diff erence fi lter with odd number of coeffi cients that averages the image in the direction perpendicular to the diff erentiation:

2

1  1 0  –1                   1 

2

1  2  1 

1 0 –1

D _2x B _y = 8    2  0  –2    ,          D _2y B _x = 8  

0  0  0.  (12.55)

 

–1 –2 –1

 

×

The errors in the magnitude and direction of the gradient based on Eq. (12.55) are shown in Fig. 12.11. The improvement over the simple symmetric derivative operator (Fig. 12.5) is similar to the 2 2 cross- smoothing diff erence operator (Fig. 12.10). A Taylor expansion in the wave number yields the same approximations (compare Eqs. (12.53) and (12.54)):

e  (k˜, φ )         (π k˜ )3 sin² 2φ         O(˜ 5k  )                  (12.56)

m                 ≈ − 24                  +

for the error of the magnitude and

φ                  ≈ −           +

e  (k˜, φ )        (π k˜ )2 sin 4φ

48

 

O(k˜ 4)                      (12.57)

12.5 Regularized Edge Detection                                                  333

 

for the direction of the gradient. A comparison with the corresponding equations for the simple diff erence fi lter Eqs. (12.28) and (12.29) shows that both the anisotropy and the angle error of the Sobel operator are a factor of two smaller. However, the error still increases with the square of the wave number. The error in the direction of the Sobel gradient is still up to 5° at a wave number of 0.5. For many applications, such a large error cannot be tolerated.

 

Derivatives of Gaussian

A well-known general class of regularized derivative fi lters is the class of derivates of a Gaussian smoothing fi lter. Such a fi lter was, e. g., used by Canny [18] for optimal edge detection and is also known as the Canny edge detector. On a discrete lattice this class of operators is best ap- proximated by a derivative of a binomial operator (Section 11.4) as

(B, R)D_w = D_2wBR                                                                    (12.58)

+ ×    +

with nonsquare (2R 3) (2R 1)W − 1 W -dimensional masks and the transfer function

.

W

(B, R)dˆ w ( k ˜ ) = i sin(π k˜ w )                cos^2R(π k˜ w /2).                   (12.59)

w=1

Surprisingly, this fi lter turns out to be a bad choice, because its aniso- tropy is the same as for the simple symmetric diff erence fi lter. This can be seen immediately for the direction of the gradient. The smoothing term is the same for both directions and thus cancels out in Eq. (12.19). The remaining terms are the same as for the symmetric diff erence fi lter.

In the same way, Sobel-type RW -sized diff erence operators

 

w

RSw = Dw BR− 1

w.'≠ w

BR '                                                  (12.60)

w

with a (2R + 1)W W -dimensional mask and the transfer function

.

W

RSˆ d(k˜ ) = i tan(π k˜ d/2)               cos^2R(π k˜ d/2)                    (12.61)

w=1

×

show the same anisotropy at the same wave number as the 3 3 Sobel operator.

 

⇐ Предыдущая52535455565758596061Следующая ⇒

Поделиться: