Monotonically Decreasing Transfer Function

⇐ ПредыдущаяСтр 53 из 85Следующая ⇒

Intuitively, we expect that any smoothing operator attenuates smaller scales more strongly than coarser scales. More speciﬁ cally, a smoothing operator should not completely annul a certain scale while smaller scales still remain in the image. Mathematically speaking, this means that the transfer function decreases monotonically with the wave number:

hˆ (k˜ 2) ≤ hˆ (k˜ 1) if

k˜ 2 > k˜ 1. (11.6)

We may impose the more stringent condition that for the highest wave numbers the transfer function is identical to zero:

1-D:

2-D:

hˆ (1) = 0

hˆ (k˜ 1, 1) = 0, hˆ (1, k˜ 2) = 0

(11.7)

3-D:

hˆ (k˜ 1, k˜ 2, 1) = 0,

hˆ (k˜ 1, 1, k˜ 3) = 0,

hˆ (1, k˜ 2, k˜ 3) = 0.

Together with the monotonicity condition and the preservation of the mean value, this means that the transfer function decreases monotoni- cally from one to zero for each averaging operator.

Isotropy

In most applications, the smoothing should be the same in all directions in order not to prefer any direction. Thus, both the ﬁ lter mask and the transfer function should be isotropic. Consequently, the ﬁ lter mask depends only on the magnitude of the distance from the center pixel and the transfer function on the magnitude of the wave number:

h( x ) = h(| x |) and hˆ ( k ˜ ) = hˆ (| k ˜ |). (11.8)

In discrete space, of course, this condition can only be met approxi- mately. Therefore, it is an important design goal to construct discrete masks with minimum deviation from isotropy.

286 11 Averaging

Box Filter

Basics

It is obvious that smoothing ﬁ lters will average pixels within a small neighborhood. The simplest method is to add all the pixels within the ﬁ lter mask and to divide the sum by the number of pixels. Such a simple ﬁ lter is called a box ﬁ lter. Box ﬁ lters are an illustrative example as to how to design a ﬁ lter properly. As an introduction, we consider a 1 3 box ﬁ lter

3 Σ Σ

3 R = 1 1 1 . (11.9)

The factor 1/3 scales the result of the convolution sum in order to pre-

serve the mean value (Section 11.2.2). Otherwise the gray value in a region with constant gray values is not preserved. We apply this mask to a vertical edge

.. ..

··· 0 0 1 1 ···

∗ 3 Σ 1 1 1 Σ =

··· 0 ₁/3 2/3 1 ···

.. .. .. ..

As expected for a smoothing operation, the sharp edge is transformed into a smoother ramp with a gradual transition from 0 to 1. Smoothing ﬁ lters attenuate structures with high wave numbers. Let us test this ﬁ rst with a vertical structure with a wavelength of 3 pixel distance:

. . .. . .

...

1 –2 1 1 –2 1 ···

∗ 3 Σ 1 1 1 Σ =

0 0 0 0 0 0 ···

. . .. . .

...

It turns out that the 1 3 box ﬁ lter completely removes a structure with the wavelength 3. As already discussed in Section 11.2.3, we expect that all structures with a wave number above a certain threshold are removed by a good smoothing ﬁ lter. This is not the case for the 1 3 box ﬁ lter. A structure with the wavelength 2 is only attenuated by a factor of 3:

. . . . . . . .

Σ Σ 3

··· 1 –1 1 –1 ··· 1 ··· − 1/3 1/3 − 1/3 1/3 ···

··· 1 –1 1 –1 ··· ∗ 1 1 1 =

··· 1 –1 1 –1 ···

··· − 1/3 1/3 − 1/3 1/3 ···

. . . . . . . .

11.3 Box Filter 287

0.8

0.6

0.4

0.2

-0.2

-0.4 0 0.2 0.4 0.6 0.8 ~

0.8

0.6

0.4

0.2

B =

Figure 11.1: Transfer functions of one-dimensional smoothing ﬁ lters: a box ﬁ l- ters with 3, 5, 7, and 9 coeﬃ cients; b binomial ﬁ lters p with p 2, 4, 8, 16, and

32.

D Box Filter

After this qualitative introduction, we discuss box ﬁ lters quantitatively by computing the transfer function. For sake of simplicity, we start with 1-Dﬁ lters. The mask of the box ﬁ lter

3 R _x = Σ 1/3 1/3 1/3 Σ (11.10)

× = =

is of even symmetry. According to the considerations in Section 4.2.6, we can apply Eq. (4.25) to compute the transfer function of the one- dimensional 1 3 box ﬁ lter. Only the coeﬃ cients h₀ h₁ 1/3 are unequal to zero and the transfer function reduces to

3rˆ 1 2 ˜

x = 3 + 3 cos(π k_x). (11.11)

The transfer function is shown in Fig. 11.1a. Our quick computation at the beginning of this section is veriﬁ ed. The transfer function shows a zero at k˜ 2/3. This corresponds to a wave number which is sampled 3 times per wavelength. The smallest possible wavelength (k˜ 1), which is sampled twice per wavelength, is only damped by a factor of three. The transfer function is negative for k˜ > 2/3. A negative transfer function means an interchange of minima and maxima, equal to a phase shift of 180 °. In conclusion, the 1 3 box ﬁ lter is not a good lowpass ﬁ lter. It is disturbing that the attenuation does not increase monotonically with the wave number but oscillates. Even worse, structures with the largest wave number are not attenuated strongly enough.

Larger box ﬁ lters do not show a signiﬁ cant improvement (Fig. 11.1a). On the contrary, the oscillatory behavior is more pronounced and the attenuation is only proportional to the wave number. For large ﬁ lter masks, the discrete mask with R coeﬃ cients comes close to a continuous box function of width R. Therefore the transfer function approximates

288 11 Averaging

A b

-1

-0.5

0.5 ~

k x

1 -1

-0.5

0.5

k y

-1

-0.5

0.5 ~

k x

1 -1

-0.5

0.5

k y

Figure 11.2: Transfer functions of two-dimensional box ﬁ lters shown in a pseudo 3-D plot: a 3 × 3 box ﬁ lter; b 7 × 7 box ﬁ lter.

the sinc function (± R5):

Rrˆ (k˜ ) = sin(π Rk˜ /2) ≈ sin(π Rk˜ /2) = sinc(Rk˜ /2). (11.12)

x R sin(π k˜ /2) π R˜ k/2

D Box Filter

Now we turn to two-dimensional box ﬁ lters. To simplify the arithmetic, we utilize the fact that the ﬁ lter is separable and decompose it into ver- tical and horizontal 1-Dcomponents, respectively:

3 3 3

1  1 1 1  Σ

Σ 1  1 

R = R _x ∗

R _y = 9   1 1 1   = 3

1 1 1

∗ 3  1  .

  1

The transfer function of the one-dimensional ﬁ lters is given by Eq. (11.11) (replacing k˜ x by k˜ y for the vertical ﬁ lter). As convolution in the space domain corresponds to multiplication in the wave number domain, the transfer function of R is

3rˆ = 3rˆ _x³rˆ _y =  1 + 2 cos(π k˜ x)  1 + 2 cos(π k˜ y ) . (11.13)

Evaluation

From Eq. (11.13) and Fig. 11.2a, we can conclude that 2-Dbox ﬁ lters are also poor lowpass ﬁ lters. A larger box ﬁ lter, for example one with a

7 7 mask (Fig. 11.2b), does not perform any better. Besides the disad- vantages already discussed for the one-dimensional case, we are faced with the problem that the transfer function is not isotropic, i. e., it de- pends, for a given wave number, on the direction of the wave number.

11.3 Box Filter 289

Figure 11.3: Test of the smoothing with a 5 5 (upper right quadrant) and a

9 9 box ﬁ lter (lower left quadrant) using a test image with concentric sinusoidal rings. The maximum wave number k˜ at the edge of the pattern is 0.6.

× ×

When we apply a box ﬁ lter to an arbitrary image, all these disadvan- tages aﬀ ect the image, but it is diﬃ cult to observe them quantitatively (Fig. 11.6). They are revealed immediately, however, if we use a carefully designed test image. This image contains concentric sinusoidal rings. The wavelength of the rings decreases with distance from the center. With this test image, we map the Fourier domain onto the space do- main. Thus, we can directly see the transfer function, i. e., the change in the amplitude and the phase shift, when a ﬁ lter is applied. When we convolve this image with a 5 5 or9 9 box ﬁ lter, the deviations from an isotropic transfer function become readily visible (Fig. 11.3). We can observe the wave numbers that vanish entirely and the change of gray value maxima into gray value minima and vice versa in some regions, indicating the 180° phase shift caused by negative values in the transfer function.

From this experience, we can learn an important lesson. We must not rate the properties of a ﬁ lter operation from its eﬀ ect on arbitrary images, even if we think that they seem to work correctly. Obviously, the eye perceives a rather qualitative impression, but for quantitative extraction of image features a quantitative analysis of the ﬁ lter proper- ties is required. This involves a careful analysis of the transfer function and the application of the ﬁ lters to carefully designed test images.

Now we turn back to the question of what went wrong with the box ﬁ l- ter. We might try to design a better smoothing ﬁ lter directly in the wave

290 11 Averaging

number space. An ideal smoothing ﬁ lter would cut oﬀ all wave num- bers above a certain threshold value. We could use this ideal transfer function and compute the ﬁ lter mask by an inverse Fourier transform. However, we run into two problems which can be understood without explicit calculations. The inverse Fourier transform of a box function is a sinc function. This means that the coeﬃ cients decrease only proportion- ally to the distance from the center pixel. We would be forced to work with large ﬁ lter masks. Furthermore, the ﬁ lter has the disadvantage that it overshoots at the edges.

Fast Computation

Despite all the disadvantages of box ﬁ lters, they show one signiﬁ cant advantage. According to the following equation, the convolution with a one-dimensional box ﬁ lter can be computed independently of its size with only three operations as a recursive ﬁ lter operation:

gm'

= gm' − 1

+ 2r + 1 (g_m_+r − g_m_{− r} _{− 1}). (11.14)

This recursion can be understood by comparing the computations for the convolution at neighboring pixels. When the box mask is moved one position to the right, it contains the same weighting factor for all pixels except for the last and the ﬁ rst pixel. Thus, we can simply take the result of the previous convolution, (g_m' − 1), subtract the ﬁ rst pixel that just moved out of the mask, (g_m_{− r} _{− 1}), and add the gray value at the pixel that just came into the mask, (g_m_+r ). In this way, the computation of a box ﬁ lter does not depend on its size and the number of computations is O(r 0). Only one addition, one subtraction, and one multiplication are required to compute the ﬁ lter result.

Binomial Filter

Basics

From our experience with box ﬁ lters, we conclude that the design of ﬁ lters is a diﬃ cult optimization problem. If we choose a small rectan- gular ﬁ lter mask, we get a poor transfer function. If we start with an ideal transfer function, we get large ﬁ lter masks and overshooting ﬁ l- ter responses. The reason for this behavior is the fundamental relation between smoothness and compactness of the Fourier transform pairs (Section 2.3.5). An edge constitutes a discontinuity. A discontinuity leads to an impulse in the ﬁ rst derivative. The Fourier transform of an

11.4 Binomial Filter 291

impulse is evenly spread over the whole Fourier domain. Using the inte- gral property of the Fourier transform (Section 2.3), an integration of the derivative in the space domain means a division by k in the Fourier do- main ( R5). Then we know without any detailed calculation that in the one-dimensional case the envelope of the Fourier transform of a func- tion which shows discontinuities in the space domain will decline with k− 1 in the wave number domain. This was exactly what we found for the box function. Its Fourier transform is the sinc function ( R5).

Considering this basic fact, we can design better smoothing ﬁ lters. One condition is that the ﬁ lter masks should gradually approach zero.

D Binomial Filter

Here we will introduce a class of smoothing ﬁ lters that meets this crite- rion and can be calculated very eﬃ ciently. Furthermore, these ﬁ lters are an excellent example of how more complex ﬁ lters can be built from sim- ple components. The simplest and most elementary smoothing mask we can think of is

B 1 [1 1]. (11.15)

It averages the gray values of two neighboring pixels. We can use this mask p times in a row on the same image. This corresponds to the ﬁ lter mask

2p [1 1] ∗ [1 1] ∗ ... ∗ [1 1], (11.16)

p t˛ im¸ es r

or, written as an operator equation,

Bp = BB. .. B. (11.17)

p t˛ im¸ es r

Some examples of the resulting ﬁ lter masks are:

B 2 = 1/4 [12 1]

B 3 = 1/8 [133 1]

B 4 = 1/16 [1464 1]

B 8 = 1/256 [18 28 56 70 56 288 1].

(11.18)

Because of symmetry, only the odd-sized ﬁ lter masks are of interest. In order to perform a convolution with the asymmetric mask 1/2 [1 1] correctly, we store the result in the right and left pixel alternately.

The masks contain the values of the discrete binomial distribution. Actually, the iterative composition of the mask by consecutive convolu- tion with the 1/2 [1 1] mask is equivalent to the computation scheme of

B B

292 11 Averaging

Figure 11.4: Test of the smoothing with a 4 and 16 binomial ﬁ lter using a test image with concentric sinusoidal rings.

Pascal’s triangle:

p f σ 2

0 1 1 0

1 1/2 1 1 1/4

2 1/4 1 2 1 1/2

3 1/8 1331 3/4

4 1/16 14641 1

5 1/32 1 5 10 10 5 1 5/4

6 1/64 1 6 15 20 15 6 1 3/2

7 1/128 1 7 21 35 35 21 7 1 7/4

8 1/256 1 8 28 56 70 56 28 8 1 2

(11.19)

where p denotes the order of the binomial, f the scaling factor 2− p, and

σ 2 the variance, i. e., eﬀ ective width, of the mask.

. Σ

The computation of the transfer function of a binomial mask is also very simple since we only need to know the transfer function of B. The transfer function of Bp is then given as the pth power:

bˆ p

= cos^p(π k˜ /2) = 1

p (π k˜ )2

−

3p2 − 2p (π k˜ )4

384

+ O(k˜ 6). (11.20)

The graphical representation of the transfer function in Fig. 11.1b reveals that binomial ﬁ lters are much better smoothing ﬁ lters than box

11.4 Binomial Filter 293

a b

-1

-0.5

0.5 ~

k x

1 -1

-0.5

0.5

k y

0.06

0.04

0.02

0.2

0.4

0.6

0.8 ~

k 1 0

0.5

1.5

0.5

0.03

0.02

0.01

1.5

-1

-0.5

0.5 ~

k x

1 -1

k y

-0.5

0.2

0.4

0.6

0.8 ~

k 1 0

0.5

− B B

Figure 11.5: Transfer function of two-dimensional binomial ﬁ lters: a 2; b anisotropy Bˆ 2(k˜, θ ) Bˆ 2(k˜, 0) in a (k, θ ) diagram; c 4; d anisotropy for 4 as in b.

ﬁ lters. The transfer function decreases monotonically and approaches zero at the largest wave number. The smallest mask, 2, has a halfwidth of k˜ /2. This is a periodic structure which is sampled four times per wavelength. For larger masks, both the transfer function and the ﬁ lter masks approach the Gaussian distribution with an equivalent variance. Larger masks result in smaller half-width wave numbers in agreement with the uncertainty relation.

D Binomial Filter

Two-dimensional binomial ﬁ lters can be composed from a horizontal and a vertical 1-Dﬁ lter:

Bp = BpBp . (11.21)

The smallest mask of this kind is a 3 × 3-binomial ﬁ lter (p = 2):

2 Σ Σ

1  1 

1  1 2 1 

 1 

 1 2 1

B = 4 1 2 1 ∗ 4  2  = 16  2 4 2   . (11.22)

B + × +

The transfer function of the 2-Dbinomial ﬁ lter p with (p 1) (p 1) coeﬃ cients is easily derived from the transfer functions of the 1-Dﬁ lters

294 11 Averaging

A b

C d

E f

Figure 11.6: Application of smoothing ﬁ lters: a original image; b 5 × 5 box ﬁ l- ter; c 9 × 9 box ﬁ lter; d 17 × 17 binomial ﬁ lter (B16); a set of recursive ﬁ lters Eq. (11.36) running in horizontal and vertical directions; e p = 2; f p = 16.

Eq. (11.20) as

bˆ p = bˆ p bˆ p = cos^p(π k˜

/2) cos^p(π k˜

/2), (11.23)

and correspondingly for a 3-Dﬁ lter as

bˆ p = bˆ pbˆ p bˆ p = cos^p(π k˜ /2) cos^p(π k˜

/2) cos^p(π k˜

/2). (11.24)

11.4 Binomial Filter 295

A b

C d

× B ×

Figure 11.7: Suppression of noise with smoothing ﬁ lters: a image from Fig. 11.6a with Gaussian noise; b image with binary noise; c image a and d image b ﬁ ltered with a 9 9 binomial ﬁ lter ( 8); e image a and f image b ﬁ ltered with a 3 3

median ﬁ lter (Section 11.7.1).

B B

The transfer functions of 2 and 4 are shown in Fig. 11.5. Already the small 3 3 ﬁ lter is remarkably isotropic. Larger deviations from the circular contour lines can only be recognized for larger wave numbers, when the transfer function has dropped to 0.3 (Fig. 11.5a). This property can be shown by expanding Eq. (11.23) in a Taylor series using cylindrical

296 11 Averaging

coordinates k ˜ = [k˜, θ ]T :

bˆ p

p ˜ 2

2p2 − p ˜ 4 p cos 4θ ˜ 4

≈ 1 − 8 (π k) +

256 (π k) −

768 (π k). (11.25)

Only the second-order term is isotropic. In contrast, the fourth-order term contains an anisotropic part which increases the transfer function in the direction of the diagonals (Fig. 11.5a). A larger ﬁ lter (larger p) is less anisotropic as the isotropic term with k˜ 4 increases quadratically with p while the anisotropic term with k˜ 4 cos 4θ increases only linearly with p. Already the 5 5 ﬁ lter (Fig. 11.5b) is remarkably isotropic. The insigniﬁ cant anisotropy of the binomial ﬁ lters also becomes apparent when applied to the test image in Fig. 11.4.

Evaluation

Figure 11.6b, c show smoothing with two diﬀ erent binomial ﬁ lters. We observe that the edges get blurred. Fine structures as in the branches of the tree are lost. Smoothing suppresses noise. Binomial ﬁ lters can reduce the noise level of zero-mean Gaussian noise (Section 3.4.2) con- siderably but only at the price of blurred details (Fig. 11.7a, c). Binary noise (also called impulse noise), which causes wrong gray values for a few randomly distributed pixels (Fig. 11.7b) (for instance due to trans- mission errors), is suppressed only poorly by linear ﬁ lters. The images are blurred, but the error caused by the binary noise is not eliminated but only distributed.

Fast Computation

+ + −

+ × +

We close our consideration of binomial ﬁ lters with some remarks on fast algorithms. A direct computation of a (2p 1) (2p 1) ﬁ lter mask requires (2p 1)2 multiplications and (2p 1)2 1 additions. If we de- compose the binomial mask into elementary smoothing masks 1/2 [1 1] and apply this mask in horizontal and vertical directions 2p times each, we only need 4p additions. All multiplications can be handled much more eﬃ ciently as shift operations. For example, the computation of a

17 17 binomial ﬁ lter requires only 32 additions and some shift opera- tions compared to 289 multiplications and 288 additions needed for the direct approach.

11.5 Filters as Networks‡

The binomial ﬁ lters we have discussed in this section are built from the sim- plest elementary operations we can think of: scaling of pixels and the addition of neighboring pixels. For both of these operations we can construct a circuit element that performs the corresponding operation. Figure 11.8 shows a scaler,

11.5 Filters as Networks‡ 297

g g g

Scaler

h Multiplier

Adder

h Subtractor

Figure 11.8: Elementary circuits for performing discrete ﬁ lter operations.

an adder, a subtractor, a multiplier, and a shift-register stage. The circuit ele- ments can perform the operations either analogously or digitally. With these circuit elements, we built FIR ﬁ lters with electronic networks in an instructive way. This results also in a new perspective for ﬁ lter operations.

As a ﬁ rst example, we consider the 1-D binomial mask B 4 1/16 [1464 1]. Figure 11.9 shows diﬀ erent implementations for computing the ﬁ lter output for one pixel. While direct implementations result in irregular-shaped circuit nets, the composition of the ﬁ lter with the B 1/2 [1 1] mask gives a regular mesh of operations. For the calculation of a single output pixel, we need 10 additions, more than for the direct implementation. To calculate the ﬁ lter out- put of the next pixel, we only need four additions if we store the intermediate results on each level of the ﬁ lter net from the computations of the previous pixel (Fig. 11.9d).

Actually, we could build a net of these circuits, spanning the whole vector, to compute the binomial smoothing in parallel (Fig. 11.10). Such a net has a num- ber of interesting properties. Each level of the net corresponds to a ﬁ ltering of the image with the elementary smoothing mask 1/2 [1 1]. Thus we obtain not only the ﬁ nal result but all intermediate smoothing results. The grid points of the individual layers change from regular grid points to intermediate grid points in a natural way.

The network model for ﬁ lter operations is also suitable for illustrating the diﬀ er- ent approaches in handling the boundary problems of ﬁ ltering. We could close the net into a ring. This corresponds to a cyclic convolution. Or we could extend the net beyond the edges of the vector, so that we get all the nodes needed to calculate the ﬁ rst and last point. Then we can either ﬁ ll the grid points in the lowest levels lying outside the vector with zeroes or we can extrapolate them in an appropriate manner from the points within the vector.

The extension of ﬁ lter nets to two dimensions is straightforward for separable ﬁ lters. The nets are then composed of nets alternately connecting the pixels in the horizontal or vertical direction. The ﬁ lter nets are valuable tools for algorithm design. As we have seen, they are especially useful in making eﬃ cient use of intermediate results and in getting a clear idea of the boundary problems at the edges of images.

298 11 Averaging

A b

C d

Figure 11.9: Diﬀ erent circuit nets for performing the binomial smoothing ﬁ lter operation B 4 1/16 [1464 1]: a direct implementation; b saving multiplica-

tions; c composition with the elementary ﬁ lter B 1/2 [1 1]; d computation for the next pixel.

11.6 Eﬃ cient Large-Scale Averaging‡

Despite the eﬃ cient implementation of binomial smoothing ﬁ lters r by cas- caded convolution with, the number of computations increases dramatically for smoothing masks with low cutoﬀ wave numbers, because the standard devi- ation of the ﬁ lters is proportional to the square root of p according to Eq. (3.42):

σ =  p/4. (11.26)

Let us consider a smoothing operation over a circle with a radius of about only

1.73 pixels, corresponding to a variance σ 2 3. According to Eq. (11.26) we need to apply 12 which — even in an eﬃ cient separable implementation — requires 24 (36) additions and 2 (3) shift operations for each pixel in a 2-D(3-D) image. If we want to smooth over the double distance (σ 2 = 12, radius ≈ 3.5, B48) the number of additions quadruples to 96 (144) per pixel in 2-D(3-D) space.

11.6 Eﬃ cient Large-Scale Averaging‡ 299

Figure 11.10: Circuit net for computing the 1-D binomial smoothing ﬁ lter B4.

11.6.1 Multistep Averaging‡

The problem of slow large-scale averaging originates from the small distance between the pixels averaged in the elementary B 1/2 [1 1] mask. In order to overcome this problem, we may use the same elementary averaging process but with more distant pixels and increase the standard deviation for smooth-

ing correspondingly. √ In two dimensions, the following masks could be applied

along diagonals (σ · 2):

1  1 0 0  1  0 0 1 

0 0 1

1 0 0

B _x₊_y = 4   0 2 0   , B _x₋_y = 4   0 2 0   , (11.27)

or, with double step width along axes (σ · 2) and in three dimensions,

 1   1 

1 1 1

B _2x = [1020 1], B _2y =  2  , B _2z =  2 

. (11.28)

 

4 4

 1 

 1  z

The subscripts in these masks denote the stepping width and coordinate direc- tion. B _x₊_y averages the gray values at two neighboring pixels in the direction of the main diagonal. B _2x computes the mean of two pixels at a distance of 2 in the x direction. The standard deviation of these ﬁ lters is proportional to the distance between the pixels. The most eﬃ cient implementations are multistep masks along the axes. They have the additional advantage that because of sep- arability, the algorithms can be applied to image data of arbitrary dimensions.

The problem with these ﬁ lters is that they perform a subsampling. Conse- quently, they are no longer ﬁ lters for larger wave numbers. If we take, for

example, the symmetric 2-D B2 2 ﬁ lter, we eﬀ ectively work on a grid with a

doubled grid constant in the spatial domain. Hence, the reciprocal grid in the wave number space has half the grid width and the transfer function is period- ically replicated once in both directions (Fig. 11.11). Generally, the zero lines

300 11 Averaging

A b

1 1

0.5

-1

-0.5

0.5 ~

k x

1 -1

k y

-0.5

-1

-0.5

0.5 ~

k x

1 -1

k y

-0.5

Figure 11.11: Transfer function of the binomial mask applied a in the diagonal

x+y

direction (B2

x− y

) and b with double step width in axis directions (B2 2

of the transfer function of masks with larger step width reﬂ ect this reciprocal grid. For convolution with two neighboring pixels in the direction of the two di- agonals, the rec√ iprocal grid is turned by 45°. The grid constant of the reciprocal

grid is a factor 2 smaller than that of the original grid.

Used individually, these ﬁ lters are not of much help. But we can use them in cascade, starting with directly neighboring pixels. Then the zero lines of the transfer functions, which lie diﬀ erently for each pixel distance, eﬃ ciently force the transfer function close to zero for large wave number ranges.

Cascaded multistep binomial ﬁ ltering leads to a signiﬁ cant performance in- crease for large-scale smoothing. For normal separable binomial ﬁ ltering, the number of computations is proportional to σ 2(O(σ 2)). For multistep binomial ﬁ ltering it depends only logarithmically on σ (O(ldσ 2)) if a cascade of ﬁ lter operations with recursive step width doubling is performed:

p p p p

BP ··· B B B B . (11.29)

2s− 1x

8x 4x s ti˛ m¸ es

2x x

Such a mask has the standard deviation

σ 2 = p/4 + p + 4p +... + 4^s⁻¹p = p (4^s − 1) (11.30)

and the transfer function

s ti˛ m¸ es r

s− 1

cos^p(2^s'− 1π k˜ ). (11.31)

s'=0

Thus, for s steps only ps additions are required while the standard deviation grows exponentially with ≈ p/12 · 2s.

With the parameter p, we can adjust the degree of isotropy and the degree of residual inhomogeneities in the transfer function. A very eﬃ cient implemen- tation is given by using p = 2 ( B 2 = 1/4[1 2 1] in each direction). However the

11.6 Eﬃ cient Large-Scale Averaging‡ 301

a b

0.5

0.1

0.05

1.5

-1

-0.5

0.5 ~

k x

1 -1

k y

-0.5

-0.05

-0.1

0.2

0.4

0.6

0.8 ~

k 1 0

0.5

0.02

1.5

-1

-0.5

0.5 ~

k x

1 -1

k y

-0.5

-0.02

0.2

0.4

0.6

0.8 ~

k 1 0

0.5

Figure 11.12: Transfer function of cascaded multistep binomial ﬁ lters and their anisotropy: a B2B2, b Bˆ 2Bˆ 2(k˜, θ )− Bˆ 2Bˆ 2(k˜, 0), c B4B4, d Bˆ 4Bˆ 4(k˜, θ ) − Bˆ 4Bˆ 2(k˜, 0).

The anisotropy is shown in polar coordinates (k˜, θ ) as the deviation from the transfer function in the x direction.

residual side peaks at high wave numbers with maximal amplitudes up to 0.08 are still signiﬁ cant disturbances (Fig. 11.12a, b, Fig. 11.13a, b).

With the next larger odd-sized masks (p = 4, B 4 = 1/16[1 4 6 4 1] in each di- rection) these residual side peaks at high wave numbers are suppressed well below 0.005 (Fig. 11.12c, d, Fig. 11.13c, d). This is about the relative resolution of 8-bit images and should therefore be suﬃ cient for most applications. With still larger masks, they could be suppressed even further. Figure 11.14 shows the ﬁ rst four steps of multistep averaging with the B 4 mask, illustrating how quickly the smoothing reaches large scales.

11.6.2 Multigrid Averaging‡

Multistep cascaded averaging can be further enhanced by converting it into a multiresolution technique. The idea of multigrid smoothing is very simple. When a larger-step mask is involved, this operation can be applied on a corre- spondingly coarser grid. This means that the last operation before using the larger-step mask needs to compute the convolution only at the grid points used by the following coarser grid operator. This sampling procedure is denoted by a special syntax in the operator index. _x_|₂ means: Apply the operator in the x direction and advance the mask two pixels in the x direction. Thus, the output of the ﬁ lter operator has only half as many pixels in the x direction as the input.

302 11 Averaging

A b

C d

Figure 11.13: Cascaded multistep averaging with step width doubling according to Eq. (11.29), applied to the ring test pattern: a B2B2, b B2B2B2, c B4B4, and

d B4B4B4.

2 1 4 2 1 2 1

Multigrid smoothing makes the number of computations essentially indepen- dent of the standard deviation of the smoothing mask. We again consider a sequence of 1-Dbinomial ﬁ lters:

p p p

Bx↓ 2 ··· Bx↓ 2Bx↓ 2.

s ti˛ m¸ es r

x|2

Since Bp

takes p operations, the operator sequence takes

p. 1 = 2p.1 − 1 Σ < 2p.

s'=1 2s'− 1

2s− 1

11.6 Eﬃ cient Large-Scale Averaging‡ 303

A b

C d

Figure 11.14: Cascaded multistep averaging with step width doubling according to Eq. (11.29), applied to image Fig. 11.6a with a one, b two, c three, and d four steps using the B 4 ﬁ lter.

As for the multistep approach, Eq. (11.30), the standard deviation of the oper- ator sequence is

= −

σ 2 p (4^s 1). (11.32)

= ∀ ≥

Thus, smoothing to any degree takes not more than twice as many operations as smoothing at the ﬁ rst step! As for multistep binomial ﬁ lters, the standard deviation grows by a factor of two. Also — as long as B ˆ p(k˜ ) 0 k˜ 1/2 — the transfer functions of the ﬁ lters are the same as for the multistep ﬁ lters.

11.6.3 Recursive Averaging‡

A totally diﬀ erent approach to large-scale averaging is given by recursive ﬁ lter- ing introduced in Section 4.3. The recursion essentially gives a convolution ﬁ lter an inﬁ nite point spread function. The basic advantage of recursive ﬁ lters is that they can easily be “tuned”, as we have demonstrated with the simple lowpass ﬁ lter in Section 4.3.5. In this section, the focus is on the design of averaging ﬁ lters that meet the criteria we discussed earlier in Section 11.2, especially the zero-shift property (Section 11.2.1) that is not met by causal recursive ﬁ lters.

304 11 Averaging

Basically, recursive ﬁ lters work the same as non-recursive ﬁ lters. In principle, we can replace any recursive ﬁ lter with a non-recursive ﬁ lter whose ﬁ lter mask is identical to the point spread function of the recursive ﬁ lter. The real problem is the design of the recursive ﬁ lter, i. e., the determination of the ﬁ lter coeﬃ cients for a desired transfer function.

While the theory of one-dimensional recursive ﬁ lters is standard knowledge in digital signal processing (see, for example, Oppenheim and Schafer [133]), the design of two-dimensional ﬁ lters is still not adequately understood. The main reason is the fundamental diﬀ erence between the mathematics of one- and higher-dimensional z-transforms and polynomials [112].

Despite these theoretical problems, recursive ﬁ lters can be applied successfully in digital image processing. In order to avoid the ﬁ lter design problems, we will use only very simple recursive ﬁ lters which are easily understood and compose them to more complex ﬁ lters, similar to the way we constructed the class of binomial ﬁ lters from the elementary smoothing mask 1/2 [1 1]. In this way we will obtain a class of recursive ﬁ lters that may not be optimal from the point of view of ﬁ lter design but are useful in practical applications.

In the ﬁ rst composition step, we combine causal recursive ﬁ lters to symmetric ﬁ lters. We start with a general one-dimensional recursive ﬁ lter with the transfer function

+ A ˆ = a(k˜ ) + ib(k˜ ). (11.33)

The index denotes the run direction of the ﬁ lter in the positive coordinate direction. The transfer function of the same ﬁ lter but running in the opposite direction is

− A ˆ = a(k˜ ) − ib(k˜ ). (11.34)

Only the sign of the imaginary part of the transfer function changes, as it cor- responds to the odd part of the point spread function, while the real part cor- responds to the even part.

We now have two possible ways to combine the forward and backward running ﬁ lters into symmetric ﬁ lters useful for averaging:

addition

A ˆ = 2 Σ + A ˆ + − A ˆ Σ = a(k˜ )

(11.35)

multiplication

A ˆ = + A ˆ − A ˆ

= a2(k˜ ) + b2(k˜ ).

Both techniques yield real transfer functions and thus even ﬁ lters with zero shift that are suitable for averaging.

As the elementary recursive smoothing ﬁ lter, we use the two-element lowpass ﬁ lter we have already studied in Section 4.3.5:

±A_x: G_m' n = G_m' , n∓ 1 + α (G_mn − G_m' , n∓ 1) with 0 ≤ α ≤ 1 (11.36) with the impulse response

(±A

x)m, n

α (1 − α )n n> 0, m = 0

0 otherwise.

(11.37)

11.6 Eﬃ cient Large-Scale Averaging‡ 305

0.8

0.6

0.4

0.2

Figure 11.15: Transfer function of the recursive lowpass ﬁ lter Eq. (11.39) for diﬀ erent values of α = 1/2, 1/4, 1/8, and 1/16.

The transfer function of this ﬁ lter can easily be calculated by taking into account that the Fourier transform of Eq. (11.37) forms a geometric series:

±Aˆ x(k˜ ) = α ˜ . (11.38)

1 − (1 − α ) exp(∓ iπ k)

This relation is valid only approximately, since we broke oﬀ the inﬁ nite sum in Eq. (11.37) at n = N − 1 because of the limited size of the image.

Consecutive ﬁ ltering with a left and right running ﬁ lter corresponds to a multi- plication of the transfer functions

Aˆ (k˜ )

+ ˆ ˜ − ˆ ˜ α 2

x = A_x(k)

Ax(k) ≈ α 2 + 2(1 − α )(1 − cos(π k˜ )). (11.39)

= =

The transfer function shows the characteristics expected for a lowpass ﬁ lter (Fig. 11.15). At k˜ 0, Aˆ x(k˜ ) 1; for small k˜, the transfer function falls oﬀ in proportion to k˜ 2,

α 2

Aˆ x ≈ 1 − 1 − α (π k˜ )2 k˜ , 1, (11.40)

and has a half-value wave number k˜ c (Aˆ x(k˜ c ) = 1/2) of

˜ 1 α α

k_c ≈ π arcsin 2(1 − α ) ≈ √ 2π , (11.41)

where the last approximation is only valid for α < < 1. At the highest wave number, k˜ = 1, the transfer function has dropped oﬀ to

Aˆ x(1)

α 2

≈ 4(1 − α ) + α 2

. (11.42)

In contrast to binomial ﬁ lters, it is not exactly zero, but suﬃ ciently small even for small values of α (Fig. 11.15).

Two-dimensional ﬁ lters can be composed from one-dimensional ﬁ lters running in the horizontal and vertical directions:

A= A_xA_y = +A_x− A_x+A_y − A_y. (11.43)

306 11 Averaging

A b

-1

-0.5

0.5 ~

k x

1 -1

-0.5

0.5

k y

0.2

0.15

0.1

0.05

0.2

0.4

0.6

0.8 ~

k 1 0

0.5

1.5

-0.4

-0.2

0.2

k x 0.4

0.4

0.2

0 k y

-0.2

-0.4

0.03

0.02

0.01

0.2

0.4

0.6

0.8 ~

k 1 0

0.5

1.5

Figure 11.16: Transfer functions of two-dimensional recursive lowpass ﬁ lters: a A with α = 1/2, b anisotropy of a: Aˆ (k, θ ) − Aˆ (k, π /4), c A' with α = 1/2, and d anisotropy of c: Aˆ '(k, θ ) − Aˆ '(k, 0).

This ﬁ lter (Fig. 11.16) is less isotropic than binomial ﬁ lters (Fig. 11.5). Averaging in coordinate directions is considerably less than in the other directions. How- ever, recursive ﬁ lters have the big advantage that the computational eﬀ ort does not depend on the degree of averaging. With the simple ﬁ rst-order recursive ﬁ lter, we can select the degree of averaging with an appropriate choice of the ﬁ lter parameter α (Eq. (11.41)). The isotropy of recursive ﬁ lters can be further improved by running additional ﬁ lters along the diagonals:

A' = A_xA_yA_x₋_yA_x₊_y. (11.44)

− +

The subscripts x y and x y denote the main and second diagonal, respec- tively. The transfer function of such a ﬁ lter is shown in Fig. 11.16b.

In contrast to non-recursive ﬁ lters, the computational eﬀ ort does not depend on the cut-oﬀ wave number. If α 2− l in Eq. (11.36), the ﬁ lter can be computed without any multiplication:

G_m' n = Σ G_m' , n±1 · 2^l − G_m' , n±1 + G_mnΣ · 2⁻^l, l > 1. (11.45)

The two-dimensional ﬁ lter needs only 8 additions and shift operations per pixel, while the ' ﬁ lter, running in 4 directions, needs twice as many oper- ations. This is not more eﬃ cient than the multigrid approach with binomial masks (Section 11.6.2) that makes a much better isotropic ﬁ lter.

11.7 Nonlinear Averaging 307

Nonlinear Averaging

The linear averaging ﬁ lters discussed so far blur edges. Even worse, if the mask of the smoothing operator crosses an object edge it contains pixels from both the object and the background, giving a meaningless result from the ﬁ lter. The same is true if averages are performed when a certain number of pixels in an image show erroneous values, e. g., because of a transmission error. The question, therefore, is whether it is possible to perform an averaging that does not cross object boundaries or that ignores certain pixels. Such a procedure can only be applied, of course, if we have already detected the edges or any distorted pixel.

In this section, we discuss three types of nonlinear averaging ﬁ l- ter: the classical median ﬁ lter (Section 11.7.1); weighted averaging, also known as normalized convolution (Section 11.7.2); and steerable aver- aging (Section 11.7.3), where we control the direction and/or degree of averaging with the local content of the neighborhood.

Median Filter

Linear ﬁ lters eﬀ ectively suppress Gaussian noise but perform very poorly in case of binary noise (Fig. 11.7). Using linear ﬁ lters that weigh and sum up, we assume that each pixel carries some useful information. Pixels distorted by transmission errors have lost their original gray value. Lin- ear smoothing does not eliminate this information but carries it on to neighboring pixels. Thus the appropriate operation to process such dis- tortions is to detect these pixels and to eliminate them.

This is exactly what a rank-value ﬁ lter does (Section 4.4). The pix- els within the mask are sorted and one pixel is selected. In particular, the median ﬁ lter selects the medium value. As binary noise completely changes the gray value, it is very unlikely that it will show the medium gray value in the neighborhood. In this way, the medium gray value of the neighborhood is used to restore the gray value of the distorted pixel. The following examples illustrate the eﬀ ect of a 1 × 3 median ﬁ lter

M: M[··· 123789 ··· ] = [··· 123789 ··· ] M[··· 12 102456 ··· ] = [··· 124556 ··· ] M[··· 000999 ··· ] = [··· 000999 ··· ]

As expected, the median ﬁ lter eliminates runaways. The two other gray value structures — a monotonically increasing ramp and an edge be- tween two plateaus of constant gray value — are preserved. In this way a median ﬁ lter eﬀ ectively eliminates binary noise without signiﬁ cantly blurring the image (Fig. 11.7e). Gaussian noise is less eﬀ ectively elimi- nated (Fig. 11.7f).

308 11 Averaging

The most important deterministic properties of a one-dimensional 2N + 1 median ﬁ lter can be formulated using the following deﬁ nitions.

• A constant neighborhood is an area with N + 1 equal gray values.

•

An edge is a monotonically increasing or decreasing area between two constant neighborhoods.

•

An impulse is an area of at most N points surrounded by constant neighborhoods with the same gray value.

•

A root or ﬁ x point is a signal that is preserved under the median ﬁ lter operation.

With these deﬁ nitions, the deterministic properties of a median ﬁ lter can be described very compactly:

• Constant neighborhoods and edges are ﬁ x points.

• Impulses are eliminated.

Iterative ﬁ ltering of an image with a median ﬁ lter results in an image containing only constant neighborhoods and edges. If only single pixels are distorted, a 3 3 median ﬁ lter is suﬃ cient to eliminate them. If clusters of distorted pixels occur, larger median ﬁ lters must be used.

The statistical properties of the median ﬁ lter can be illustrated with an image containing only constant neighborhoods, edges, and impulses. The power spectrum of impulses is ﬂ at (white noise). As the median ﬁ l- ter eliminates impulses, the power spectrum decreases homogeneously. The contribution of the edges to a certain wave number is not removed. This example also underlines the nonlinear nature of the median ﬁ lter.

Weighted Averaging

In Section 3.1, we saw that gray values at pixels, just like any other ex- perimental data, may be characterized by individual errors that have to be considered in any further processing. As an introduction, we ﬁ rst discuss the averaging of a set of N data g_n with standard deviations σ _n. From elementary statistics, it is known that appropriate averaging requires the weighting of each data point g_n with the inverse of the vari- ance w_n = 1/σ 2. Then, an estimate of the mean value is given by

N N

g =. g_n/σ 2  . 1/σ 2

(11.46)

n n

n=1 n=1

while the standard deviation of the mean is

g n

σ 2 = 1  . 1/σ 2. (11.47)

n=1

The weight of an individual data point in Eq. (11.46) for computation of the mean is the higher, the lower its statistical error.

11.7 Nonlinear Averaging 309

A b

C d

Figure 11.17: Weighted averaging using the edge strength to hinder smoothing at edges: a image from Fig. 11.6a with added Gaussian noise; b weighting image after 5 convolutions; image after c two and d ﬁ ve normalized convolutions using a B2 binomial smoothing mask (compare with Fig. 11.7).

The application of weighted averaging to image processing is known as normalized convolution [57]. The averaging is now extended to a local neighborhood. Each pixel enters the convolution sum with a weighting factor associated with it. Thus, normalized convolution requires two images. One is the image to be processed, the other an image with the weighting factors.

By analogy to Eqs. (11.46) and (11.47), normalized convolution is de- ﬁ ned by

G ' H ∗ ( W · G ), (11.48)

H ∗ W

= ∗

where H is any convolution mask, G the image to be processed, and W the image with the weighting factors. A normalized convolution with the mask H essentially transforms the set of the image G and the weighting image W into a new image G ' and a new weighting image W ' H W which can undergo further processing.

In this sense, normalized convolution is nothing complicated or spe- cial. It is just adequate consideration of pixels with spatially variable

310 11 Averaging

statistical errors. “Standard” convolution can be regarded as a special case of normalized convolution. Then all pixels are assigned the same weighting factor and it is not required to use a weighting image, since the factor remains a constant.

The ﬂ exibility of normalized convolution is given by the choice of the weighting image. The weighting image does not necessarily get as- sociated with an error. It can be used to select and/or amplify pixels with certain features. In this way, normalized convolution becomes a versatile nonlinear operator.

As an example, Fig. 11.17 shows an noisy image that is ﬁ ltered by nor- malized convolution using an weighting image that hinders smoothing at edges.

Steerable Averaging

The idea of steerable ﬁ lters is to make the convolution mask dependent on the local image structure. This is a general concept which is not restricted to averaging but can be applied to any type of convolution process. The basic idea of steerable ﬁ lters is as follows. A steerable ﬁ lter has some freely adjustable parameters that control the ﬁ ltering. These could be various properties such as the degree of smoothing, the direction of smoothing, or both. It is easy to write down a ﬁ lter mask with adjustable parameters. We have done this already for recursive ﬁ lters in Eq. (11.36) where the parameter α determines the degree of smoothing. However, it is not computationally eﬃ cient to convolve an image with masks that are diﬀ erent at every pixel. Then, advantage can no longer be taken of the fact that masks are separable.

An alternative approach is to seek a base of a few ﬁ lters, and to use these ﬁ lters to compute a set of ﬁ ltered images. Then, these images are interpolated using adjustable parameters. In operator notation this

reads

H (α ) = f_p(α )H_p, (11.49)

p=1

where _p is the pth ﬁ lter and f_p(α ) a scalar interpolation function of the steering parameter α. Two problems must be solved when using steerable ﬁ lters. First, and most basically, it is not clear that such a ﬁ lter base H_p exists at all. Second, the relation between the steering parameter(s) α and the interpolation coeﬃ cients f_p must be found. If the ﬁ rst problem is solved, we mostly get the solution to the second for free.

As an example, a directional smoothing ﬁ lter is to be constructed with the following transfer function:

hˆ θ 0 (k, θ ) = 1 − f (k) cos²(θ − θ ₀). (11.50)

11.7 Nonlinear Averaging 311

Figure 11.18: Transfer functions for the three base ﬁ lters for directional smooth- ing according to Eq. (11.54).

In this equation, cylindrical coordinates (k, θ ) are used in the Fourier domain. The ﬁ lter in Eq. (11.50) is a polar separable ﬁ lter with an arbi- trary radial function f (k). This radial component provides an arbitrary isotropic smoothing ﬁ ltering.

−

The steerable angular term is given by cos2(θ θ ₀). Structures ori-

ented in the direction θ ₀ remain in the image, while those perpendicular to θ ₀ are completely ﬁ ltered out. The angular width of the directional smoothing ﬁ lter is 45°.

We separate the cosine function in Eq. (11.50) into trigonometric func- tions that depend only on either θ or the steering angle θ ₀ and obtain

hˆ θ (k, θ ) = 1 − 1 f (k) [1 + cos(2θ ₀) cos(2θ ) + sin(2θ ₀) sin(2θ )]

0 2

(11.51)

with the base ﬁ lters

hˆ 1 = 1 − 1 f (k),

hˆ 2

= − 2 f (k) cos(2θ ),

hˆ 3

= − 2 f (k) sin(2θ )

(11.52)

and the interpolation functions

f₁(θ ₀) = 1, f₂(θ ₀) = cos(2θ ₀), f₃(θ ₀) = sin(2θ ₀). (11.53)

Thus three base ﬁ lters are required. The ﬁ lter hˆ 1 is an isotropic smooth- ing ﬁ lter, the other two are directional ﬁ lters. Although the equations

312 11 Averaging

0.8

0.6

0.4

0.2

0.5

0.8

0.6

0.4

0.2

0.5

0.8

0.6

0.4

0.2

0.5

Figure 11.19: Transfer functions for the steerable smoothing ﬁ lter according to Eq. (11.51) using the base ﬁ lters Eq. (11.54): smoothing in 0°, 22.5°, and 45°to the x axis.

for this family of steerable directional smoothing ﬁ lter are simple, it is not easy to implement polar separable base ﬁ lters because they are not Cartesian separable and, thus, require careful optimization.

Nevertheless, it is even possible to implement this steerable smooth- ing ﬁ lter with 3 3 base ﬁ lters (Fig. 11.18). Because of symmetry prop- erties of the transfer functions, we have not much choice to chose the ﬁ lter coeﬃ cients and end up with the following three base ﬁ lters:

1  1 2 1  1  0 − 4 0  1  − 2 0 2 

1 2 1

0 − 4 0

2 0 − 2

H ₁ = 32   2 20 2   , H ₂ = 32   4 0 4   , H ₃ = 32   0 0 0  

hˆ 1 1 2 ˜ 2 ˜

π 2k˜ 2

1 = 2 + 2 cos (π k₁/2) cos (π k₂/2) ≈ 1 − 8,

hˆ 2 =

hˆ 3 =

4 .cos(π k˜ 1) − cos(π k˜ 2)Σ ≈

8 .cos(π (k˜ 1 + k˜ 2)) − cos(π (k˜ 1 − k˜ 2))Σ ≈

π 2k˜ 2 cos(2θ ), 8

π 2k˜ 2 sin(2θ ). 8

(11.54)

From Fig. 11.19 it is obvious that this simple implementation works well up to moderate wave numbers. At high wave number (k˜ > 0.5), the directional ﬁ lter does no longer work very well.

11.8 Averaging in Multichannel Images‡ 313

11.8 Averaging in Multichannel Images‡





At ﬁ rst glance, it appears that there is not much special about averaging of multichannel images: just apply the smoothing mask to each of the P channels individually:

G '1





G '2

 H ∗ G ₁ 

 H ∗ G ₂ 

   

= .  = H ∗ G =  .

. (11.55)



  .  

H ∗ G _p

This simple concept can also be extended to normalized convolution (Section 11.7.2). If the same smoothing kernel is applied to all components, it is suﬃ cient to use one common weighting image that can be appended as the (P 1)th component

of the multicomponent image.







G '1 G '2 

 

( H ∗ ( W · G ₁))/( H ∗ W )







( H ∗ ( W · G ₂))/( H ∗ W )

 

(11.56)

  =  

 G 'P 

 ( H ∗ ( W · G _P ))/( H ∗ W ) 

 W '  

H ∗ W 

A special case of multicomponent images is given when they represent features that can be mapped to angular coordinates. Typically, such features include the direction of an edge or the phase of a periodic signal. Features of this kind are cyclic and cannot be represented well as Cartesian coordinates.

Also, they cannot be averaged in this representation. Imagine an angle of +175° and –179°. The mean angle is 178°, since –179° = 360° – 179° = 181° is close to

175° and not (175° – 179°)/2= –2°.

Circular features such as angles are, therefore, better represented as unit vec- tors in the form n ¯ _θ = [cos θ, sin θ ]^T.

In this representation, they can be averaged correctly as illustrated in Fig. 11.20. The average vector points to the correct direction but its magnitude is generally smaller than 1:

( n ¯ _θ + n ¯ _θ )/2 = Σ cos[(θ 1 + θ 2)/2] Σ cos[(θ − θ )/2]. (11.57)

1 2 sin[(θ ₁ + θ ₂)/2] ² ¹

For an angle diﬀ erence of 180°, the average vector has zero magnitude. The decrease of the magnitude of the average vector has an intuitive interpretation. The larger the scatter of the angle is, the less is the certainty of the average value. Indeed, if all directions are equally probable, the sum vector vanishes, while it grows in length when the scatter is low.

These considerations can be extended to the averaging of circular features. To this end we set the magnitude of the vector equal to the certainty of the quantity that is represented by the angle of the vector. In this way, short vectors add little and long vectors add more to the averaging procedure.

This is a very attractive form of weighted convolution since in contrast to nor- malized convolution (Section 11.7.2) it requires no time-consuming division. Of course, it works only with features that can be mapped adequately to an angle.

314 11 Averaging

y y

average vector

q2 q₂

q₁ q₁

x x

Figure 11.20: Averaging of a cyclic quantity represented as a normal vector

n ¯ _θ = [cos θ, sin θ ]^T on the unit vector. The average vector ( n ¯ _θ + n ¯ _θ )/2 points

in the correct direction (θ ₁ θ ₂)/2 but its magnitude decreases with the diﬀ erence angle.

Finally, we consider a measure to characterize the scatter in the direction of vectors. Figure 11.20 illustrates that for low scatter the sum vector is only slightly lower than the sum of the magnitudes of the vector. Thus, we can deﬁ ne an angular coherence measure as

c | H ∗ G | , (11.58)

| G |

where H is an arbitrary smoothing convolution operator. This measure is one if all vectors in the neighborhood covered by the convolution operator point in the same direction and zero if they are equally distributed. This deﬁ nition of a coherence measure works not only in two-dimensional but also in higher- dimensional vector spaces. In one-dimensional vector spaces (scalar images), the coherency measure is, of course, always one.

11.9 Further Readings‡

The articles of Simonds [171] and Wells [197] discuss fast algorithms for large Gaussian kernels. Readers with an interest in the general principles of eﬃ cient algorithms are referred to the textbooks of Aho et al. [3] or Sedgewick [167]. Blahut [10] deals with fast algorithms for digital signal processing. Classical ﬁ lter design techniques, especially for IIR-ﬁ lter are discussed in the standard textbooks for signal processing, e. g., Proakis and Manolakis [144] or Oppenheim and Schafer [133]. Lim [112] speciﬁ cally deals with the design of 2-DIIR ﬁ lters. A detailed description of the deterministic and statistical properties of median ﬁ lters can be found in Huang [75] or Arce et al. [5]. They are also discussed in detail in the monograph on nonlinear digital ﬁ lters by Pitas and Venetsanopou- los [140]. The monograph of Granlund and Knutsson [57] on signal processing for computer vision deals also with weighted averaging (normalized convolu- tion, Section 11.7.2). Steerable ﬁ lters (Section 11.7.3) were introduced by the articles of Freeman and Adelson [48] and Simoncelli et al. [170].

Edges

Introduction

The task of edge detection requires neighborhood operators that are sen- sitive to changes and suppress areas of constant gray values. In this way, a feature image is formed in which those parts of the image appear bright where changes occur while all other parts remain dark.

Mathematically speaking, an ideal edge is a discontinuity of the spa- tial gray value function g( x ) of the image plane. It is obvious that this is only an abstraction, which often does not match the reality. Thus, the ﬁ rst task of edge detection is to ﬁ nd out the properties of the edges con- tained in the image to be analyzed. Only if we can formulate a model of the edges, can we determine how accurately and under what conditions it will be possible to detect an edge and to optimize edge detection.

Edge detection is always based on diﬀ erentiation in one or the other form. In discrete images, diﬀ erentiation is replaced by discrete diﬀ er- ences, which only approximate to diﬀ erentiation. The errors associated with these approximations require careful consideration. They cause ef- fects that are not expected in the ﬁ rst place. The two most serious errors are: anisotropic edge detection, i. e., edges are not detected equally well in all directions, and erroneous estimation of the direction of the edges. While the deﬁ nition of edges is obvious in scalar images, diﬀ erent def-

initions are possible in multicomponent or vectorial images (Section 12.6). An edge might be a feature that shows up in only one component or in all. Edge detection also becomes more complex in higher-dimensional images. In three dimensions, for example, volumetric regions are sepa- rated by surfaces, and edges become discontinuities in the orientation of surfaces.

Another important question is the reliability of the edge estimates. We do not only want to ﬁ nd an edge but also to know how signiﬁ cant it is. Thus, we need a measure for edge strength. Closely related to this issue is the question of optimum edge detection. Once edge detectors deliver not only edges but also an objective conﬁ dence measure, diﬀ er- ent edge detectors can be compared to each other and optimization of edge detection becomes possible.

315

ISBN 3–540–67754–2 All rights of reproduction in any form reserved.

316 12 Edges