Page 124 -

3.2 Linear filtering 103

convolution kernels for computer vision applications is often influenced by their separability.
How can we tell if a given kernel K is indeed separable? This can often be done by
inspection or by looking at the analytic form of the kernel (Freeman and Adelson 1991). A
more direct method is to treat the 2D kernel as a 2D matrix K and to take its singular value
decomposition (SVD),

K = σ i u i v T i (3.21)
i
(see Appendix A.1.1 for the definition of the SVD). If only the first singular value σ 0 is
√ √
T
non-zero, the kernel is separable and σ 0 u 0 and σ 0 v provide the vertical and horizontal
0
kernels (Perona 1995). For example, the Laplacian of Gaussian kernel (3.26 and 4.23) can be
implemented as the sum of two separable filters (4.24)(Wiejak, Buxton, and Buxton 1985).
What if your kernel is not separable and yet you still want a faster way to implement
it? Perona (1995), who first made the link between kernel separability and SVD, suggests
using more terms in the (3.21) series, i.e., summing up a number of separable convolutions.
Whether this is worth doing or not depends on the relative sizes of K and the number of sig-
nificant singular values, as well as other considerations, such as cache coherency and memory
locality.

3.2.2 Examples of linear filtering

Now that we have described the process for performing linear filtering, let us examine a
number of frequently used filters.
The simplest filter to implement is the moving average or box filter, which simply averages
the pixel values in a K ×K window. This is equivalent to convolving the image with a kernel
of all ones and then scaling (Figure 3.14a). For large kernels, a more efficient implementation
is to slide a moving window across each scanline (in a separable filter) while adding the
newest pixel and subtracting the oldest pixel from the running sum. This is related to the
concept of summed area tables, which we describe shortly.
A smoother image can be obtained by separably convolving the image with a piecewise
linear “tent” function (also known as a Bartlett filter). Figure 3.14b shows a 3 × 3 version
of this filter, which is called the bilinear kernel, since it is the outer product of two linear
(first-order) splines (see Section 3.5.2).
Convolving the linear tent function with itself yields the cubic approximating spline,
which is called the “Gaussian” kernel (Figure 3.14c) in Burt and Adelson’s (1983a) Lapla-
cian pyramid representation (Section 3.5). Note that approximate Gaussian kernels can also
be obtained by iterated convolution with box filters (Wells 1986). In applications where the
filters really need to be rotationally symmetric, carefully tuned versions of sampled Gaussians
should be used (Freeman and Adelson 1991) (Exercise 3.10).
The kernels we just discussed are all examples of blurring (smoothing) or low-pass ker-
nels (since they pass through the lower frequencies while attenuating higher frequencies).
How good are they at doing this? In Section 3.4, we use frequency-space Fourier analysis to
examine the exact frequency response of these filters. We also introduce the sinc ((sin x)/x)
filter, which performs ideal low-pass filtering.
In practice, smoothing kernels are often used to reduce high-frequency noise. We have
much more to say about using variants on smoothing to remove noise later (see Sections 3.3.1,
3.4, and 3.7).