Digital Signal Processing

By Steven W. Smith, Ph.D.

- 1: The Breadth and Depth of DSP
- 2: Statistics, Probability and Noise
- 3: ADC and DAC
- 4: DSP Software
- 5: Linear Systems
- 6: Convolution
- 7: Properties of Convolution
- 8: The Discrete Fourier Transform
- 9: Applications of the DFT
- 10: Fourier Transform Properties
- 11: Fourier Transform Pairs
- 12: The Fast Fourier Transform
- 13: Continuous Signal Processing
- 14: Introduction to Digital Filters
- 15: Moving Average Filters
- 16: Windowed-Sinc Filters
- 17: Custom Filters
- 18: FFT Convolution
- 19: Recursive Filters
- 20: Chebyshev Filters
- 21: Filter Comparison
- 22: Audio Processing
- 23: Image Formation & Display
- 24: Linear Image Processing
- 25: Special Imaging Techniques
- 26: Neural Networks (and more!)
- 27: Data Compression
- 28: Digital Signal Processors
- 29: Getting Started with DSPs
- 30: Complex Numbers
- 31: The Complex Fourier Transform
- 32: The Laplace Transform
- 33: The z-Transform
- 34: Explaining Benford's Law

Your laser printer will thank you!

Convolution by Separability

This is a technique for fast convolution, as long as the PSF is separable. A PSF
is said to be *separable* if it can be broken into two one-dimensional signals: a
vertical and a horizontal projection. Figure 24-5 shows an example of a
separable image, the square PSF. Specifically, the value of each pixel in the
image is equal to the corresponding point in the horizontal projection multiplied
by the corresponding point in the vertical projection. In mathematical form:

where *x*[*r*,*c*] is the two-dimensional image, and *vert*[*r*] & *horz*[*c*] are the one-dimensional projections. Obviously, most images do not satisfy this
requirement. For example, the pillbox is not separable. There are, however, an
*infinite* number of separable images. This can be understood by generating
arbitrary horizontal and vertical projections, and finding the image that
corresponds to them. For example, Fig. 24-6 illustrates this with profiles that
are double-sided exponentials. The image that corresponds to these profiles is
then found from Eq. 24-1. When displayed, the image appears as a diamond
shape that exponentially decays to zero as the distance from the origin
increases.

In most image processing tasks, the ideal PSF is *circularly symmetric*, such as
the pillbox. Even though digitized images are usually stored and processed in
the rectangular format of rows and columns, it is desired to modify the image
the same in all directions. This raises the question: is there a PSF that is
circularly symmetric *and* separable? The answer is, yes,

but there is only one, the *Gaussian*. As is shown in Fig. 24-7, a two-dimensional Gaussian image has projections that are also Gaussians. The image
and projection Gaussians have the *same* standard deviation.

To convolve an image with a separable filter kernel, convolve each *row* in the
image with the *horizontal projection*, resulting in an intermediate image. Next,
convolve each *column* of this intermediate image with the *vertical projection* of
the PSF. The resulting image is identical to the direct convolution of the
original image and the filter kernel. If you like, convolve the columns first and
then the rows; the result is the same.

The convolution of an *N*×*N* image with an *M*×*M* filter kernel requires a time
proportional to *N*^{2}*M*^{2}. In other words, each pixel in the output image depends
on *all* the pixels in the filter kernel. In comparison, convolution by separability
only requires a time proportional to *N*^{2}*M*. For filter kernels that are hundreds
of pixels wide, this technique will reduce the execution time by a factor of
*hundreds*.

Things can get even better. If you are willing to use a *rectangular* PSF (Fig. 24-5) or a *double-sided exponential* PSF (Fig. 24-6), the calculations are even more
efficient. This is because the one-dimensional convolutions are the *moving
average* filter (Chapter 15) and the *bidirectional single pole* filter (Chapter 19), respectively. Both of these one-dimensional filters can be rapidly
carried out by recursion. This results in an image convolution time proportional
to only *N*^{2}, completely independent of the size of the PSF. In other words, an
image can be convolved with as large a PSF as needed, with only a few integer
operations per pixel. For example, the convolution of a 512×512 image requires
only a few hundred milliseconds on a personal computer. That's fast! Don't
like the shape of these two filter kernels? Convolve the image with one of them
*several times* to approximate a Gaussian PSF (guaranteed by the Central Limit
Theorem, Chapter 7). These are great algorithms, capable of snatching success
from the jaws of failure. They are well worth remembering.