Computation of Convolution

The discrete convolution operation is such an important operation that it is worth studying it in detail to see how it works. First, we might be confused by the negative signs of the indices m' and n' for either the

4.2 Linear Shift-Invariant Filters†                                                                        105

n

0 -1 -2 1 0 -1 2 1 0

m                                      *                      

m_ m

m+1

n_1 n

 

 

 

n+1

 

×

1  0 1 2       -1 0 1       -2 -1 0

Figure 4.1: Illustration of the discrete convolution operation with a 3 3 fi lter mask.

 

mask or the image in Eq. (4.5). This just means that we mirror either the mask or the image at its symmetry center before we put the mask over the image. We will learn the reason for this mirroring in Section 4.2.5. If we want to calculate the result of the convolution at the point [m, n]^T, we center the rotated mask at this point, perform the convolution, and write the result back to position [m, n]^T (Fig. 4.1). This operation is performed for all pixels of the image.

Close to the border of the image, when the fi lter mask ranges over the edge of the image, we run into diffi culties as we are missing some image points. The theoretically correct way to solve this problem according to the periodicity property discussed in Section 2.3.5, especially equation Eq. (2.44), is to take into account that fi nite image matrices must be thought of as being repeated periodically. Consequently, when we arrive at the left border of the image, we take the missing points from the right edge of the image. We speak of a cyclic convolution. Only this type of convolution will reduce to a multiplication in the Fourier space (Section 2.3).

In practice, this approach is seldom chosen because the periodic rep- etition is artifi cial, inherently related to the sampling of the image data in Fourier space. Instead we add a border area to the image with half the width of the fi lter mask. Into this border area we write zeros or we extrapolate in one way or another the gray values from the gray values at the edge of the image. The simplest type of extrapolation is to write the gray values of the edge pixels into the border area. Although this approach gives less visual distortion at the edge of the image than cyclic convolution, we do introduce errors at the edge of the image in a border area with a width of half the size of the fi lter mask. If we choose any type of extrapolation method, the edge pixels are overweighed. If we set the border area to zero, we introduce horizontal and vertical edges at the image border.

106                                                                              4 Neighborhood Operations

 

4

0

1

2

 

Figure 4.2: Image convolution by scanning the convolution mask line by line over the image. At the shaded pixels the gray value is already been replaced by the convolution sum. Thus the gray values at the shaded pixels falling within the fi lter mask need to be stored in an extra buff er.

 

In conclusion, no perfect method exists to handle pixels close to edges correctly with neighborhood operations. In one way or another, errors are introduced. The only safe way to avoid errors is to ensure that objects of interest keep a safe distance from the edge of at least half the size of the largest mask used to process the image.

Equation Eq. (4.5) indicates that none of the calculated gray values G_m'  n will fl ow into the computation at other neighboring pixels. Thus, if we want to perform the fi lter operation in-place, we run into a problem.

Let us assume that we perform the convolution line by line and from left to right. Then the gray values at all pixel positions above and to the left of the current pixel are already overwritten by the previously computed results (Fig. 4.2).

Consequently, we need to store the gray values at these positions in an appropriate buff er. Effi cient algorithms for performing this task are described in Jä hne [81] and Jä hne et al. [83, Vol. 2, Chap. 5].

The number of elements contained in the mask increases consider- ably with its size and dimension. A W -dimensional mask with a linear size of R contains RW elements. The higher the dimension, the faster the number of elements with the size of the mask increases. In higher dimensions, even small neighborhoods include hundreds or thousands of elements.

The challenge for effi cient computation schemes is to decrease the number of computations from O(RW ) to a lower order. This means that the number of computations is no longer proportional to RW but rather to a lower power of R. The ultimate goal is to achieve computation schemes that increase only linearly with the size of the mask (O(R1)) or that do not depend at all on the size of the mask (O(R0)).

4.2 Linear Shift-Invariant Filters†                                                                       107

 

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

Поделиться: