Digital image processing in the frequency domain
INTRODUCTION
We have seen in various chapters that a digital image is a rectangular array of numbers representing the luminance and colour at discrete positions in a scene. The image can be thought of as a matrix of pixels, each pixel carrying three numerical values (i.e. one per colour channel). The pixel position identifies a spatial coordinate and each pixel value represents the intensity of the colour channel at that position. The three values of a pixel depend on the colour model employed. For example, they may represent primary colour components of red, green and blue (e.g. RGB), or they may represent luminance and two normalized chromaticity values (e.g. YCC) – see Chapter 23.
Other chapters have clearly demonstrated that the power of digital image processing and manipulation lies in the simple fact that with modern computers it is very easy to process numbers. The majority of techniques described previously have concentrated on processing image data presented in the above form. The processing may be applied as an operation to individual pixels, known as a point process, where each output pixel value is the result of an operator being applied to an input pixel in the same position, e.g. the application of a greyscale transformation function to alter tonal values and contrast. Alternatively, it may rely on the relationship of the position of two or more pixels and their values, known as neighbourhood processing, e.g. the difference in or averaging of neighbouring pixel values. Applying digital image-processing techniques in this manner to the image data as above is termed ‘working in the spatial domain’ or ‘spatial image processing’.
Chapter 7 introduced the concept of spatial frequency and the Fourier transform. Rather than consider signals in terms of the value represented at each point, we may alternatively imagine the signal as composed of differing amounts of various frequencies (Figure 28.1). The idea presented by the mathematician Fourier is conceptually simple, but has far-reaching consequences in many areas of science and technology. Fourier demonstrated that all functions (signals) may be represented by the addition of a number of sine and cosine waves of various frequencies and phase. The number of sine and cosine waves in some instances may approach infinity. He further proved that for each unique signal there is a unique set of waves to represent that signal.
Analysing imaging systems by examining their frequency content (i.e. looking at the amount of each sine and cosine wave) we may arrive at the modulation transfer function (MTF) and the Fourier theory of image formation among many others (see Chapters 7 and 24). It is possible to transform between spatial frequencies and the original signal represented in the spatial domain via the application of the Fourier transform (see later).
The principles of the majority of frequency processing operations may be understood by concentrating on monochrome images. It should be noted that, because of the difference between the performance of the human eye to chrominance and luminance signals, in particular the poor resolution of the chrominance response (see Chapters 4 and 5), it is common for different processing to be applied to each image channel. Unless specified, for the remainder of this chapter we will work on greyscale (or single-channel) images.
Figure 28.1 The construction of a signal by the addition of sine waves.
It has been seen in Chapter 27 that one of the major tools in image processing is digital filtering. There are two basic classes of spatial digital filter: linear and non-linear. In general terms only linear spatial filters have a direct equivalent Fourier (or frequency-domain) implementation. This is because linear filters are applied in a manner consistent with linear systems theory (a linear spatial filter is applied by convolution of a mask with the image) – see Chapter 7. They may also be combined and their effects largely reversed within the limitations of the integer representations used for digital images. As we will see later, whilst non-linear filters may be combined, their effects, once applied to an image, cannot be undone. This is an important consideration when designing workflows to process images and contemplating appropriate points to record or back up images.
As an important tool for transforming between the spatial and frequency domains, the Fourier transform will be briefly reviewed before developing its discrete implementation. Convolution will be reintroduced and its implementation in frequency space discussed. Later in the chapter, image restoration and further image space transformations, the discrete cosine and wavelet transforms, will be introduced.
FOURIER SERIES AND TRANSFORM REVISITED
Briefly, summarized from Chapter 7, it has been shown that the addition of enough sine and cosine waves will enable the reproduction of any signal desired. The addition of three sine waves may be represented by:
where u is spatial frequency and a is the coefficient for each sine wave. This notation is inefficient, however, for large numbers of sine waves and a more compact form is given by:
To add a phase change and a constant offset we may rewrite the above as:
This is the Fourier series. Euler’s formula is a classical result in trigonometry and states that:
Using Euler’s formula, Eqn 28.3 may be rewritten as:
where cn is a coefficient related to an and bn via: an = cn + c – n and bn = i(cn − c − n). For a non-periodic function f(x), the Fourier transform F(u) is defined as:
The complex function F(u) represents the amount of frequency u present in the non-periodic f(x). The total amplitude of the signal at frequency u is given by the modulus of F(u). The inverse Fourier transform may be derived using a similar approach and converts signals represented in the frequency domain into the spatial domain:
Using the Fourier transform and its inverse it is possible to move into and out of frequency space efficiently. Some common results for the Fourier transform are given in Chapter 7.
Signals that have been digitized are a finite number of discrete samples, i.e. they are not continuous or infinitely long. This means that it is not possible to use the continuous formulation of the Fourier transform to process our discretely sampled images. The one dimensional discrete Fourier transform (DFT) may be written as:
where M is the number of discrete samples (number of data points).
The inverse transform is given by:
For most practical purposes the DFT closely approximates the Fourier transform, save for the introduction of aliasing and a bandwidth limitation. If n samples are spaced at δx, frequency samples will be spaced at δu = 2WMaxn, which is equivalent to 1/δx.n, where the maximum spatial frequency contained in the output, WMax = 1/2δx. Frequencies above this are not rejected but aliased about the Nyquist frequency and contaminate the spatial frequencies in the output.
The Fourier transform and the DFT may be extended to two dimensions, where:
is the two-dimensional Fourier transform and
the two-dimensional DFT where M and N are the number of data points in each dimension.
The inverse transforms are given by:
and
for the two-dimensional continuous and discrete cases respectively.
Equation 28.11 is separable and thus it may be rewritten:
This is an important result as it shows that the two-dimensional DFT may be implemented by computing the one-dimensional DFT of each column and then the one-dimensional DFT of each row of that result. The importance of this will become apparent as we discuss the fast Fourier transform.
FAST FOURIER TRANSFORM (FFT)
The FFT is a method to efficiently compute a one-dimensional DFT, generally reducing the approximate number of operations required from N2 to Nlog N, where N is the number of data points and the logarithm is to base 2. The most common FFT is the Cooley–Tukey algorithm, which iteratively splits the N data points into two transforms of length N/2. One transform is of the odd data points and the other of the even data points. The algorithm may be applied recursively until N transforms of data length 1 are required. Once the transforms are performed the completed DFT may be reconstructed. As mentioned later in this chapter, it is for the reason of recursive splitting that data lengths of 2n are preferred.
IMAGING EQUATION REVISITED
As discussed in Chapter 7, provided that a system is linear and stationary, an image may be considered to be formed from the addition of overlapping, scaled point spread functions (PSFs) in the x and y directions. The input scene may be denoted as Q(xp, yp), the output image as Q′(xp, yp) and the PSF as I(x, y). Mathematically, the relationship between them is given by the imaging equation:
This is a two-dimensional convolution integral. It represents the previously described process of adding up the scaled PSFs over the surface of the image. The integrals represent the summation process when the individual PSFs are infinitesimally close together.
It is often written as:
or even just:
where 
denotes convolution as previously.
LINEAR SPATIAL FILTERING (CONVOLUTION)
It was seen in Chapter 27 that a convolution kernel may be created to generate a particular effect in an image. The desired result is controlled by the size of and the values given to the kernel. The convolution process was described in Chapter 7 when dealing with image formation. Here we review a discrete digital implementation. The formula for digital convolution is:
i.e.
In these two equations, f represents the original image and h is the filter array of size M × M where M is an odd number (typically 3 or 5). The output of the convolution, g, is the required processed image.
Figure 28.2 illustrates the process of convolution (this was also previously illustrated in Figure 27.16). The array of numbers is a portion of a digital image, f, under convolution with a 3 × 3 filter array, h. The convolution kernel is positioned above f, in position (i, j) and multiplied with the image values. The nine products are summed and the result placed in the position (i, j). This is then repeated for all values of (i, j). As previously discussed in Chapter 27, care must be taken to account for values at the boundaries of the image. It should be noted that the results from convolution are identical to the results from the equivalent frequency-domain implementation when the image is considered to be periodic in real space. It should also be noted that as with all calculations based on integer output, there will be some rounding errors associated with the application of each kernel. Further, clipping will occur if the output value cannot be represented using the specified bit depth of the image because it is either too large or too small. These effects can be minimized by combining convolution kernels that perform several processes into a single operation.
Figure 28.2 Digital convolution.
FREQUENCY-DOMAIN FILTERING
The convolution theorem, introduced in Chapter 7, implies that linear spatial filtering can be implemented by multiplication in the frequency domain. Specifically, the convolution of Eqn 28.19 can be implemented by the relationship:
where F is the Fourier transform of the original image f, H is the Fourier transform of the filter h and G is the Fourier transform of the processed image g. A digital image represented in the spatial domain is processed by taking its Fourier transform, multiplying that transform by a frequency space filter, and then taking the inverse Fourier transform to revert the resulting image back to the spatial domain. For the reasons mentioned previously, FFT algorithms require that the image is square, with the number of pixels on a dimension being a power of 2 (128, 256, 512, 1024, etc.).
The number of operations for the FFT is approximately Nlog N. Therefore, to perform a convolution in frequency space on an image of size N × N requires:
• Nlog N (base 2) operations to FFT each row = N2 log N operations to FFT the image in a single direction.
• An additional N2 log N to FFT the result to create the two-dimensional (2D) DFT for the image, totalling 2N2 log N.
• An additional 2N2 log N operations to perform the 2D DFT on the kernel. Note that the kernel has to be the same size as in the image in frequency space to be able to multiply each point in the 2D DFTs.
• N2 multiplications to multiply the 2D DFTs.
• An additional 2N2 log N operations to convert the image back into the spatial domain.
The total number of operations to perform convolution in the frequency domain is therefore of the approximate order 6N2 log N + N2. To perform convolution in the spatial domain on the same N × N pixel image with an M × M kernel assuming the image is treated as periodic, we require approximately:
• M2 operations to multiply the kernel with the image at a single location.
• M2 − 1 additions to sum the results at that location.
• One divide to scale the result, totalling 2M2 operations at each pixel location.
• Repeat the above at each image location, or N2 times.
The total number of operations to perform convolution in the spatial domain is therefore approximately 2M2N2. Figure 28.3 illustrates that for small kernel sizes on a 1024 × 1024 pixel image there is little advantage in performing the calculation in frequency space. As the kernel size increases, however, the advantages of performing the calculation in frequency space are readily apparent. Further advantage may be gained when applying the filter to a series of images, or a movie sequence. The 2D FFT of the kernel only needs to be computed once and thus the number of calculations for each additional frame is reduced to 4N2 log N + N2. It should be noted that the above is a generalized approximation and there are many techniques to reduce the number of calculations further in both cases, such as storage of results for reuse, etc.
Figure 28.3 Number of operations required to perform convolution in the spatial and frequency domains on a 1024 × 1024 pixel image versus kernel size.
Frequency space filters are often developed from a consideration of the frequency content of the image and the required modification to that frequency content, rather than an alternative route to a real space convolution operation. A simple analogy is that of a sound system. If a set of speakers has particularly poor treble or bass response, it is possible to overcome this limitation by boosting those frequencies using a graphic equalizer. Conversely, if the music has too much treble or bass the graphic equalizer is used to reduce those frequencies.
Figure 28.4) illustrates such a filter approach. The Fourier transform in Figure 28.4b shows strong vertical and horizontal components. By attenuating the horizontal high frequencies (Figure 28.4c), it is possible to suppress the (Figure 28.4d). The same effect could be achieved by operating directly on the appropriate pixel values in the original image, but this would require considerable care to produce a seamless result.
As seen in Chapter 27, linear filters have two important properties:
1. Two or more filters can be applied sequentially in any order to an image. The total effect is the same.
Figure 28.4 (a) Original image. (b) The Fourier transform of (a). (c) The Fourier transform of (b) with frequencies attenuated as indicated by the pale areas. (d) The resultant processed image.
2. Two or more filters can be combined by convolution to yield a single filter. Applying this filter to an image will give the same result as the separate filters applied sequentially.
The properties above are readily apparent when considering convolution in the frequency domain. Since convolution in the spatial domain is represented by multiplication in the frequency domain, the application of many filters can occur in any order without affecting the result. Further, the filter frequencies can be multiplied together before application to the image.
Low-pass filtering
A filter that removes all frequencies above a selected limit is known as a low-pass filter (Figure 28.5a). It may be defined as:
where u and v are spatial frequencies measured in two orthogonal directions (usually the horizontal and vertical). W0 is the selected limit. Figure 28.6 illustrates the effect of such a top-hat filter, also sometimes termed an ideal filter. As well as ‘blurring’ the image and smoothing the noise, this simple filter tends to produce ‘ringing’ artefacts at boundaries. This can be understood by considering the equivalent operation in real space. The Fourier transform (or inverse Fourier transform) of the top-hat function is a Bessel function (similar to a two-dimensional sinc function – see Chapters 2 and 7). When this is convoluted with an edge, the edge profile is made less abrupt (blurred) and the oscillating wings of the Bessel function create the ripples in the image alongside the edge. To avoid these unwanted ripple artefacts, the filter is usually modified by windowing the abrupt transition at W0 with a gradual transition from 1 to 0 over a small range of frequencies centred at W0. Gaussian, Hamming and triangular are examples of windows of this type (see Figure 28.7).
High-pass filtering
If a low-pass filter is reversed, we obtain a high-pass filter (Figure 28.5b):
Figure 28.5 The transfer functions for low-pass (a), high-pass (b), high-boost (c) and band-stop (d) filters.
Figure 28.6 (a) Original image. (b) The Fourier transform of (a). (c) The Fourier transform from (b) with frequencies attenuated by a low-pass filter as in Eqn 28.21. (d) The resultant processed image.
This filter removes all low spatial frequencies below W0 and passes all spatial frequencies above W0. Ringing is again a problem with this filter and windowing is required. Figure 28.8 illustrates the result of a Gaussian-type high-pass filter.
High-boost filter
Selectively increasing high spatial frequencies it is possible to create a high-boost filter (Figure 28.5c):
In regions where the filter is greater than unity a windowing function may be used. As edges are predominantly associated with high spatial frequencies, it is possible to create the illusion that the image is sharpened. This can, however, cause ‘tell-tale’ over- and undershoot when edge profiles are plotted. Further, due to the shape of typical MTF curves (see Chapter 24), high spatial frequencies are usually associated with low signal-to-noise ratio and thus over-amplifying the frequencies in this region can increase the effect of noise. Figure 28.9 illustrates the result of a high-boost filter.
BAND-PASS AND BAND-STOP FILTERS
Bass-pass and band-stop filters are similar to high-pass and low-pass filters except a specific range of frequencies is either attenuated or transmitted by the filter (Figure 28.5d). A band-pass filter may be defined as:
Figure 28.7 Examples of Gaussian (a), Hamming (b) and triangular (c) windowing functions.
Figure 28.8 The result of applying a high-pass filter to the image of Figure 28.4a.
Figure 28.9 Result of applying a high-boost filter to the image of Figure 28.4a.
Figure 28.10 (a) Original image. (b) The result of applying a band-pass filter to (a). (c) The result of applying a band-stop filter to (a).
where W0 to W1 represents the range of frequencies to pass. A band-stop filter is defined as:
These types of filters can be particularly useful for removing or enhancing periodic patterns. Figure 28.10a–c illustrates the effects of applying band-pass and band-stop filters to an image.
IMAGE RESTORATION
In very general terms, two degradation processes always affect an image when it is captured, or subsequently reproduced: the image is blurred and noise is added. The process of recovering an image that has been degraded, using some knowledge of the degradation phenomenon, is known as image restoration. The degradation function may be measured directly if the image system used to record the images is available, a priori information, or in certain cases such as astrophotography, it may be estimated from the image itself, a posteriori information.
Those image-processing techniques chosen to manipulate an image to improve it for some subsequent visual or machine-based decision are usually termed enhancement procedures. Image restoration requires that we have a model of the degradation, which can be reversed and applied as a filter. The procedure is illustrated in Figure 28.11.
We assume linearity so that the degradation function can be regarded as a convolution with a PSF together with the addition of noise, i.e.
where f(x, y) is the recorded image, g(x, y) is the original (‘ideal’) image, h(x, y) is the system PSF and n(x, y) is the noise.
Figure 28.11 A simple model for image recovery from degradation.
We need to find a correction process C{} to apply to f(x, y) with the intention of recovering g(x, y), i.e. C{f(x, y)} → g(x, y) (or at least something close). Ideally the correction process should be a simple operation, such as a convolution.
Inverse filtering
This is the simplest form of image restoration. It attempts to remove the effect of the PSF by creating and applying an inverse filter. Writing the Fourier space equivalent of Eqn 28.26 we obtain:
where F, G, H, and N represent the Fourier transforms of f, g, h and n respectively; u and v are the spatial frequency variables in the x and y directions.
An estimate for the recovered image, Gest(u, v) can be obtained using:
Figure 28.12 The original image (a) has been subject to a complicated convolution process at the capture stage involving movement (b). A Wiener filter correction yields (c). Simple inverse filtering yields the noisy result in (d).
If there is no noise, N(u, v) = 0 and if H(u, v) contains no zero values we get a perfect reconstruction. Generally noise is present and N(u, v) ≠ 0. Often it has a constant value for all significant frequencies. Since, for most degradations, H(u, v) tends to be zero for large values of u and v, the term
will become very large at high spatial frequencies. The reconstructed image will therefore often be unusable because of the high noise level introduced.
This problem can be illustrated very easily using a simple sharpening filter. Although a specific degradation process is not involved in the derivation of the filter, some typical form for h(x, y) is implied. The effect of such a filter is broadly equivalent to the application of Eqn 28.28 followed by an inverse Fourier transform. Figure 28.12 shows an example.
Despite the problems described above, it is often very much easier to work in the frequency domain when attempting to deconvolve an image. The PSF of an imaging system is typically small with respect to the size of an image. Because of this, small changes in the estimated PSF cause large changes in the deconvolved image. The relationship can be understood further by considering the Fourier transform of a Gaussian function, as given in Chapter 7, Eqn 7.21. The Fourier transform of a Gaussian is another Gaussian of changed width. As it becomes narrower in real space it grows wider in frequency space. Therefore, if we imagine the line spread function (LSF) of a system as a Gaussian function we can clearly see that a small LSF will yield an extensive MTF. As the MTF extends over a large range of frequencies, it will be less sensitive to small changes if used to deconvolve the image.
Optimal or Wiener filtering
A better approach to image restoration is to modify the inverse filtering process to take into account information about the noise level. The Wiener filter is derived for this purpose. It attempts to reconstruct the image by finding not the ‘ideal’ or the ‘true’ image version, but an optimal image that is statistically the best reconstruction that can be formed. The optimal image is defined as that image which has the minimum least-squared error from the ‘ideal’ image. In practice we do not know what the ‘ideal’ image is, the problem is expressed like this to simply allow the mathematical derivation to continue.
Consider a reconstruction gest(x, y) of the ‘ideal’ image g(x, y). We wish to minimize the least square difference, i.e. we require
to be a minimum. The < > brackets denote an average over all values of x and y. It would also be useful to do this by convolution. In other words we want to find a filter y(x, y), say, such that:
and the above minimum condition applies.
In Fourier space, Eqn 28.31 can be written as:
where Y(u, v) is the Fourier transform of y(x, y). Using Eqn 28.27, this result becomes:
The minimization condition may be rewritten in the frequency domain:
This minimization takes place with respect to the filter Y(u, v) and is written as:
where the subscripts u and v are omitted for clarity. Equation 28.35 becomes:
If we assume the noise n(x, y) has a zero mean and is independent of the signal, it follows that all terms of the form <N(u, v)> will be zero and can be ignored. If the squared term in Eqn 28.36 is expanded and simplified, the minimization condition can be solved to yield:
where H*(u, v) is the complex conjugate of H(u, v). This is because of notation from complex mathematics and arises because the general function (u, v) has separate real and imaginary terms to allow for an asymmetric spread function h(x, y). The result above is the classical Wiener filter. If we assume the degrading spread function is symmetrical, Eqn 28.37 reduces to:
Note that in the noise-free case, where N(u, v) = 0, Eqn 28.38 reduces to:
which is just the ideal inverse filter. The term
in Eqn 28.38 can be approximated by the reciprocal of the squared signal-to-noise ratio as defined in Eqn 24.12 of Chapter 24. Therefore, Eqn 28.38 above can be approximated by:
Equation 28.41 offers a useful means of devising a frequency space filter to combat a known degradation (e.g. uniform motion blur) when the image is noisy.
Maximum entropy reconstruction
In common with other reconstruction techniques, this aims to find the smoothest reconstruction of an image, given a noisy degraded version. It does so by considering the pixel values of an image to be probabilities, from which the entropy of an image can be defined. The entropy of the reconstructed image, formed in the absence of any constraints, will be a maximum when all the probabilities are equal. In other words it will comprise white noise. When constraints are applied by using the information in the original degraded image, an optimum reconstruction for that image is formed. The process involves iteration (repeated approximations) and will include the deconvolution of a known or estimated PSF. The technique is computationally expensive and care is required to avoid divergent or oscillatory effects. It is used widely for the reconstruction of noisy astronomical images where information as to the limits of resolution and detectability is sought.
Interactive restoration
In many applications of digital image processing the operator will have the opportunity to react to the outcome of a particular process. It then becomes advantageous to utilize the intuition of an experienced observer for the interactive restoration of images. Given the uncertain nature of noise measures and degradation processes, most restoration procedures will benefit from this flexibility. For example, the noise-to-signal power term of Eqn 28.41 may be replaced by an operator-determined constant, chosen by trial and error to yield the most appropriate correction.
Extended depth of field (EDOF)
Image restoration is employed in some modern cameras to attempt to increase the apparent depth of field. By modifying the PSF of the lens to be consistent (though not necessarily as good over a larger depth of field), it is possible to subsequently recover the lost sharpness using image restoration. The resultant effect is that the lens has an apparently larger depth of field. The technique can eliminate the need for autofocus, thereby reducing the number of mechanical parts and increasing the reliability of a system. The cost of the procedure, however, is increased image-processing complexity and possible noise. As noise is prone to change depending on exposure conditions, a noise model of the sensor needs to be included internally to the imaging system to optimize the reconstruction. Further, variation of the PSF across the field of view needs to be accounted for. A modern mobile phone sensor, for which EDOF is particularly desirable, can deconvolve an image in real time.
WAVELET TRANSFORM
Despite the importance of the Fourier transform in imaging, there are many other transformations which prove useful for various applications. Of great utility in modern image compression is the wavelet transform. A transform is simply a method for converting a signal from one form to another. The form to which it is converted depends upon its basis function. In the case of the Fourier transform the basis for the conversion is a sine wave and, as we have seen, the phase at each frequency is changed by adding a proportion of a cosine wave of the same frequency. These waves are thought of as extending infinitely in space.
A limitation of the Fourier transform is that whilst it reveals which spatial frequencies are contained in the image as a total, it does not tell us where those frequencies occur in the image. It is not localized spatially. A wavelet is limited in space and may be thought of as a pulse of energy. Figure 28.13 shows a typical wavelet, though it should be noted that there are many different types, of various shapes. The wavelet is used as the basis function for the wavelet transform.
The continuous wavelet transform (CWT) may be written as:
where Ψ(x) is the wavelet, f(x) the function to be transformed, τ a translation variable and s a scaling variable. The wavelet may be thought of as being convoluted with the input signal. It is shifted through the signal as τ is changed. The wavelet is effectively scaled using s, which changes the scale of details with which it is concerned, i.e. the set of spatial frequencies it is analysing.
Interpreting this in a less mathematical manner, we may imagine the convolution form of the equation to be similar to matched filtering or correlation (see Chapter 27), and the wavelet as being resized. For a given ‘size’ (scale) of the wavelet, the wavelet transform is finding out how much of the wavelet there is at each point in the image. The transform then repeats this for many ‘sizes’ (scales) of the wavelet. When the wavelet is scaled to be small it analyses small or high-resolution information and conversely, when it is large, low-resolution or large structure.
Figure 28.13 A typical wavelet used in the continuous wavelet transform, the Mexican hat wavelet.
Discrete wavelet transform
The discrete wavelet transform (DWT) is not simply a discrete version of the above CWT as is the case for the Fourier transform. The DWT operates via a method known as sub-band coding and iteratively decomposes the signal into ever-decreasing bands of spatial frequencies. At the heart of its operation, a pair of quadrature mirror filters (QMFs) are created. The QMFs consist of a high-pass and low-pass filter whose impulse response is closely related by:
where hH is the high-frequency impulse response and hL the low-frequency response. Application of both filters to the signal results in two outputs, one of which contains higher spatial frequencies and one of lower spatial frequencies, hence the name sub-band coding. We denote the higher spatial frequencies detail information, the lower spatial frequencies approximation information. The filters are applied in a convolution-type operation as previously:
and
and where f is the original discrete signal, F is the filtered signal and h the filter. The subscripts L and H indicate low- and high-frequency respectively. Because the signal has been filtered to contain half the number of spatial frequencies, it follows from the Nyquist theorem (see Chapter 7) that half of the samples may be removed without changing the information contained in each result. One of the goals of efficient QMF filter pair design is to generate filter pairs that can reconstruct the original signal after the removal of the redundant samples effectively.
The DWT proceeds by iteratively applying the low- and high-pass filters, also known as the scaling and wavelet filters, successively to the signal, then subsampling to remove redundant information (Figure 28.14). This creates a filter bank or decomposition tree. The information from the wavelet filter yields the DWT coefficients at each decomposition level and that from the scaling filter is processed again to yield coefficients for the subsequent level.
Figure 28.14 A discrete wavelet transform decomposition tree.
Figure 28.15 The application of the Haar wavelet transform to an image.
Reconstruction of the signal is performed by up-sampling the result at each decomposition level and passing it through a reconstruction filter. The reconstruction filter is exactly the same as the analysis filter except it is reversed spatially. The benefit of the DWT to imaging is in the area of image compression, as explained in Chapter 29. By quantization or removal of the coefficients that represent the highest spatial frequencies in the image, information can be removed with a minimum of visual impact (Figure 28.15).
BIBLIOGRAPHY
Bracewell, R.N., 1999. The Fourier Transform and its Applications, third ed. McGraw-Hill, New York, USA.
Brigham, E.O., 1988. The Fast Fourier Transform and its Applications. Prentice-Hall, New York, USA.
Castleman, K.R., 1996. Digital Image Processing. Prentice-Hall, Englewood Cliffs, NJ, USA.
Gleason, A. (translator), et al., 1995. Who Is Fourier? A Mathematical Adventure. Transnational College of LEX/Blackwell Science, Oxford, UK.
Gonzalez, R.C., Woods, R.E., Eddins, S.L., 2004. Digital Image Processing Using MATLAB. Pearson Prentice-Hall, Englewood Cliffs, NJ, USA.
Goodman, J.W., 1996. Introduction to Fourier Optics (Electrical and Computer Engineering), second ed. McGraw-Hill, New York, USA.
Jacobson, R.E., Ray, S.F., Attridge, G.G., Axford, N.R., 2000. The Manual of Photography, ninth ed. Focal Press, Oxford, UK.
‘Scion Image’, www.scioncorp.com. A free image-processing package capable of performing fast Fourier transforms and processing on images.