Error in magnitude and direction

The principal problem with all types of edge detectors is that on a dis- crete grid a derivative operator can only be approximated. In general, two types of errors result from this approximation (Fig. 12.2). First, edge detection will become anisotropic, i. e., the computation of the magni- tude of the gradient operator depends on the direction of the edge. Sec- ond, the direction of the edge deviates from the correct direction. For both types of errors it is useful to introduce error measures. All error measures are computed from the transfer functions of the gradient fi lter operator.

12.3 Gradient-Based Edge Detection†                                                            321

 

Figure 12.2: Illustration of the magnitude and direction error of the gradient vector.

 

The magnitude of the gradient is then given by

1/2

. d ˆ ( k ). =.dˆ x( k )2 + dˆ y ( k )2Σ

 

 

,                      (12.16)

ˆ                 .  .

where d ( k ) is the vectorial transfer function of the gradient operator.

The anisotropy in the magnitude of the gradient can then be expressed by the deviation of the magnitude from the magnitude of the gradient in x direction, which is given by

ˆ              ˆ

.. ....   ..

e_m( k ) = d ( k ) −  d_x( k )  .                                     (12.17) This error measure can be used for signals of any dimension.

In a similar way, the error in the direction of the gradient can be

computed. From the components of the gradient, the computed angle

φ ' of the 2-Dgradient vector is

=

φ '  arctan dˆ y (k,  φ ).                                           (12.18)

dˆ x(k, φ )

The error in the angle is therefore given by

=                      −

e  (k, φ )    arctan dˆ y (k,  φ )         φ.                       (12.19)

φ                                             dˆ x(k, φ )

In higher dimensions, angle derivation can be in diff erent directions. Still we can fi nd a direction error by using the scalar product between a unit vector in the direction of the true gradient vector and the computed gradient vector d ˆ (k) (Fig. 12.2):

 

cos e_ϕ =

k ¯ T d ˆ ( k ) d ˆ ( k )

 

with

k ¯   =

 

  k

| k |

 

.                    (12.20)

. .

. .

322                                                                                                                    12 Edges

Figure 12.3: Application of the fi rst-order symmetric derivative fi lters D_x and

D_y to the test image shown in Fig. 11.4.

 

In contrast to the angle error measure (Eq. (12.19)) for two dimensions, this error measure has only positive values. It is a scalar and thus cannot give the direction of the deviation.

A wide variety of solutions for edge detectors exist. We will discuss some of them carefully in Sections 12.3.3–12.3.5.

 

12.3.3 First-Order Discrete Diff erences

First-order discrete diff erences are the simplest of all approaches to com- pute a gradient vector. For the fi rst partial derivative in the x direction, one of the following approximations for ∂ g(x₁, x₂)/∂ x₁ may be used:

Backward diff erence      g(x 1,  x 2) − g(x 1 − ∆ x 1, x 2)

∆ x₁

Forward diff erence          g(x₁ + ∆ x₁, x₂) − g(x₁, x₂)

∆ x₁

Symmetric diff erence     g(x₁ + ∆ x₁, x₂) − g(x₁ − ∆ x₁, x₂).

2∆ x₁

 

(12.21)

12.3 Gradient-Based Edge Detection†                                                            323

 

A                                                                    b

C                                                                    d

E                                                                    f

D · D + D  · D

L                                         D                                        D

Figure 12.4: Detection of edges by derivative fi lters: a Original image, b Lapla- cian operator, c horizontal derivative _2x, d vertical derivative _2y, e mag- nitude of the gradient ( _{2x 2x 2y 2y})1/2, and f sum of the magnitudes of c and d after Eq. (12.15).

 

These approximations correspond to the fi lter masks

Backward  − D _x = [1_• − 1] Forward   + D _x = [1 − 1_•] Symmetric D _2x = 1/2 [10 − 1].

 

(12.22)

324                                                                                                                    12 Edges

 

•

The subscript denotes the central pixel of the asymmetric masks with two elements. Only the last mask shows the symmetry properties re- quired in Section 12.2.3. We may also consider the two-element masks corresponding to the backward or forward diff erence as odd masks pro- vided that the result is not stored at the position of the right or left pixel but at a position halfway between the two pixels. This corresponds to a shift of the grid by half a pixel distance. The transfer function for the backward diff erence is then

− dˆ x = exp(iπ k˜ x/2) Σ 1 − exp(− iπ k˜ x)Σ  = 2i sin(π k˜ x/2),                               (12.23) where the fi rst term results from the shift by half a grid point.

Using Eq. (12.10), the transfer function of the symmetric diff erence

operator reduces to

dˆ 2x = i sin(π k˜ x) = i sin(π k˜ cos φ ).                                      (12.24) This operator can also be computed from

D _2x = − D _x 1 B _x = [1_• − 1] ∗ 1/2 [1 1_•] = 1/2 [10 − 1].

The fi rst-order diff erence fi lters in other directions are given by sim- ilar equations. The transfer function of the symmetric diff erence fi lter in y direction is, e. g., given by

dˆ 2y = i sin(π k˜ y ) = i sin(π k˜ sin φ ).                                       (12.25)

D

D      D

The application of _2x to the ring test pattern in Fig. 12.3 illustrates the directional properties and the 90° phase shift of these fi lters. Fig- ure 12.4 shows the detection of edges with these fi lters, the magnitude of the gradient, and the sum of the magnitudes of _2x and _2y.

Unfortunately, these simple diff erence fi lters are only poor approx- imations for an edge detector. From Eqs. (12.24) and (12.25), we infer that the magnitude and direction of the gradient are given by

1/2

 

 

and

| d ˆ |=.sin²(π k˜ cos φ ) + sin²(π k˜ sin φ )Σ

(12.26)

sin²(π k˜ sin φ )

φ ' = arctan sin(π k˜ cos φ ) ,                                        (12.27)

+

where the wave number is written in polar coordinates (k, φ ). The re- sulting errors are shown in a pseudo 3-D plot in Fig. 12.5 as a function of the magnitude of the wave number and the angle to the x axis. The magnitude of the gradient decreases quickly from the correct value. A Taylor expansion of Eq. (12.26) in k˜  yields for the relative error in the magnitude

e_m(k˜, φ ) ≈

(π k˜ )3 sin² 2φ 12

O(k˜ 5).                      (12.28)

12.3 Gradient-Based Edge Detection†                                                           325

A                                                                    b

10°

5°

0

-5°

-10°

 

 

0.2

 

0.4

 

0.6

 

 

0.8 ~

k 1 0

 

0.5

 

 

1.5

q

1

Figure 12.5: a Anisotropy of the magnitude and b error in the direction of the

T

gradient based on the symmetrical gradient operator Σ D_2x, D_2yΣ . The para-

meters are the magnitude of the wave number (0 to 1) and the angle to the x

axis (0 to π /2).

 

±           =

The decrease is also anisotropic; it is slower in the diagonal direction. The errors in the direction of the gradient are also large (Fig. 12.5b). While in the direction of the axes and diagonals the error is zero, in the directions in between it reaches values of about  10° at k˜  0.5.  A Taylor expansion of Eq. (12.27) in k˜  yields the angle error according to Eq. (12.19) in the approximation for small k˜:

e_φ (k˜, φ ) ≈

 

(π k˜ )2 sin 4φ 24

 

+

O(k˜ 4).                       (12.29)

As observed in Fig. 12.5b, the angle error is zero for φ = nπ /4 with

n ∈ Z, i. e., for φ = 0°, 45° 90°, …

12.3.4 Spline-Based Edge Detection‡

The cubic B-spline transform discussed in Section 10.6.5 for interpolation yields a continuous representation of a discrete image that is also continuous in its fi rst and second derivative:

g₃(x) =.c_nβ ₃(x − n),                                             (12.30)

where β ₃(x) is the cubic B-spline function defi ned in Eq. (10.60). From this continuous representation, it is easy to compute the spatial derivative of g₃(x):

.=∂ x

∂ g₃(x)

c_n

n

∂ β 3 (x − n).                                    (12.31)

∂ x

For a discrete derivative fi lter, we only need the derivatives at the grid points. From Fig. 10.20a it can be seen that the cubic B-spline function covers at most 5 grid points. The maximum of the spline function occurs at the central grid point. Therefore, the derivative at this point is zero. It is also zero at the two

326                                                                                                                    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

1°

0.5°

0

-0.5°

-1°

 

0.2

 

 

0.4

 

0.6

 

0.8 ~

k 1 0

 

 

0.5

 

 

1.5

q

1

Figure 12.6: a Anisotropy of the magnitude and b error in the direction of the gradient based on the cubic B-spline derivative operator according to Eq. (12.33). Parameters are the magnitude of the wave number (0 to 1) and the angle to the x axis (0 to π /2).

 

outer grid points. Thus, the derivative is only unequal to zero at the direct left and right neighbors of the central point. Therefore, the derivative at the grid point x_m reduces to

∂ g₃(x)

.

= (c_m+1 − c_{m− 1})/2.                                     (12.32)

∂ x.xm

π k

Thus the computation of the fi rst-order derivative based on the cubic B-spline transformation is indeed an effi cient solution. We apply fi rst the cubic B-spline transform in the direction of the derivative to be computed (Section 10.6.5) and then the D_2x operator. Therefore, the transfer function is given by

D ˆ x = i

sin(π k˜ x)

˜

= iπ k˜ x − i

5 ˜ 5

x + O(k˜ 7 ).                  (12.33)

2/3 + 1/3 cos(π k_x)

180          x

The errors in the magnitude and direction of a gradient vector based on the B-spline derivative fi lter are shown in Fig. 12.6. They are considerably less than for the simple diff erence fi lters (Fig. 12.5). This can be seen more quantitatively from Taylor expansions for the relative errors in the magnitude of the gradient

 

 

and the angle error

 

e_m(k˜, φ )

(π k˜ )5          2

≈ − 240 sin 2φ

+ O(k˜ 7)                          (12.34)

e_φ (k˜, φ ) ≈

(π k˜ )4 sin 4φ 720

+ O(k˜ 6).                            (12.35)

The error terms are now contained only in terms with k˜ 4 (and higher powers of

k˜ ). Compare also Eqs. (12.34) and (12.35) with Eqs. (12.28) and (12.29).

 

12.3.5 Least-Squares Optimized Gradient‡

In this section fi rst-order derivative fi lters are discussed that have been opti- mized using the least squares technique already used in Section 10.6.6 to op- timize interpolation fi lters. The basic idea is to use a one-dimensional 2R + 1

12.3 Gradient-Based Edge Detection†                                                           327

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

 

1°

0.5°

0

-0.5°

-1°

 

 

0.2

 

0.4

 

 

0.6

 

 

0.8 ~

k 1 0

 

0.5

 

1.5

q

1

=        = −                       =                       = −

Figure 12.7: a Anisotropy of the magnitude and b error in the direction of the gradient based on the least squares optimized derivative fi lter according to Eq. (12.39) for R 3 (d₁ 0.597949, d₂ 0.189835, d₃ 0.0357216). Pa-

rameters are the magnitude of the wave number (0 to 1) and the angle to the x

axis (0 to π /2).

 

fi lter mask with odd symmetry in the corresponding direction w and to vary the coeffi cients so that the transfer function approximates the ideal transfer function of a derivative fi lter, iπ k˜ w , with a minimum deviation. Thus the target function is

tˆ (k˜ w ) = iπ k˜ w                                                                            (12.36)

+

and the transfer function of a one-dimensional 2R                  1 fi lter with R unknown coeffi cients is

.

R

Rdˆ (k˜ w ) = − i        2d_v sin(vπ k˜ w ).                                 (12.37)

v=1

As for the interpolation fi lters in Section 10.6.6, the coeffi cients are determined in such a way that Rdˆ ( k ˜ ) shows a minimum deviation from tˆ ( k ˜ ) in the least- squares sense:

∫

1

w(k˜ w

0

). d(k_w

) − tˆ (k˜ w

 

2

˜

). dk_w

 

.                         (12.38)

R ˆ ˜

The wave number-dependent weighting function w(k˜ w ) determines the weight- ing of the individual wave numbers.

−

One useful additional constraint is to force the transfer function to be equal to iπ k˜  for small wave numbers. This constraint reduces the degree of freedom by one for a fi lter with R coeffi cients, so only R 1 can be varied. The resulting equations are

 

and

 

R

.   .                                          Σ

Rdˆ  = − i sin(π k˜ w ) − i             2d_v  sin(vπ k˜ w ) − v sin(π k˜ w )                          (12.39)

v=2

.

R

d₁ = 1 −       vd_v.                                          (12.40)

v=2

As a comparison of Figs. 12.6 and 12.7 shows, this fi lter exhibits a signifi cantly lower error than a fi lter designed with the cubic B-spline interpolation.

328                                                                                                                    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

1°

0.5°

0

-0.5°

-1°

 

0.2

 

 

0.4

 

0.6

 

 

0.8

 

~

k 1 0

 

 

0.5

 

 

1.5

q

1

=      = −                        = −                        = −

Figure 12.8: a Anisotropy of the magnitude and b error in the direction of the gradient based on the least squares recursive derivative fi lter according to Eq. (12.41) for R 2 (β 0.439496, d₁ 0.440850, d₂ 0.0305482. Pa-

rameters are the magnitude of the wave number (0 to 1) and the angle to the x

axis (0 to π /2).

 

Derivative fi lters can be further improved by compensating the decrease in the transfer function by a forward and backward running recursive relaxation fi lter (Section 4.3.5, Fig. 4.4b). Then the resulting transfer function is

 

(R, β )dˆ  =

 

R

.   .                                          Σ

− i sin(π k˜ ) − i        2d_v  sin(vπ k˜ w ) − v sin(π k˜ w )

v=2

1 + β − β cos(π k˜ w )

 

 

(12.41)

with the additional parameter β. Figure 12.8 shows the errors in the magnitude and direction of the gradient for R = 2.

A more detailed discussion on the design of optimal derivative fi lters including tables with fi lter coeffi cients can be found in Jä hne [81].

 

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

Поделиться: