## C8 Fast Fourier Transform

Learn Photo Editing

Get Instant Access

AIP4Win implements one of the most powerful of all image processing tools: spatial filtering. The Fast Fourier Transform (FFT), the basic process behind most spatial processing, is covered in Chapter 17. Before running this tutorial, read this chapter to gain an understanding of spatial filtering.

The Fast Fourier Transform is a computationally accelerated technique for determining the frequency spectrum of a signal. In two dimensions, it can be applied to an image. The reason for transforming an image from the spatial domain to the frequency domain is that some operations, most notably filtering operations, become much simpler. In filtering an image, we are usually trying to enhance or suppress detail that occurs when pixels make a transition in intensity. Transitions that happen rapidly contain high frequencies, and transitions that happen more gradually contain low ones.

When we applied the Crispening Filter to the image of the Moon in Section C.7.3, we were enhancing the high frequencies to bring out detail. The Crispening Filter is a convolution filter, which is limited in what it can do, and tends to be rather coarse. The FFT filters we will demonstrate in this tutorial are extremely flexible, and allow you to exercise much more control over the filter characteristics.

The basic steps in filtering an image using FFT techniques are:

1. Convert the image to suitable dimensions.

2. Perform a forward FFT to transform it to the frequency domain.

3. Create a filter mask suitable to the filtering desired.

4. Multiply the image by the filter mask.

### 5. Perform an inverse FFT on the result.

This tutorial will demonstrate these steps using the manual FFT tools, and then demonstrate the use of the Auto FFT feature of AIP4Win. The images to be used can be found in the Fast Fourier Transform subdirectory of the Tutorials directory on the AIP4Win CD-ROM.

Step 1: Load an Image and Convert the Dimensions. The FFT technique has an inherent limitation. Any image you wish to apply it to needs to be square (i.e., have an equal number of pixels in each dimension), and the dimensions need to be integer powers of 2 (e.g., 2 x 2, 4 x 4, 8 x 8, 16x16, and so on) These are requirements of the FFT algorithm. It is also desirable that the pixels in the image be squared up prior to the processing.

Load the image "triangle.fts." It is a simple 128 x 128 image consisting of a white triangle on a black background. This image is of suitable dimensions already. Later on we will apply the technique to a more "real world" example.

Step 2: Perform a Forward FFT. Perform a forward FFT on this image by clicking the Enhance I Manual FFT\Forward FFT menu item. An image appears which is a bunch of diagonal lines. This image container holds the frequency-domain version of the triangle image. The picture it shows is a plot of the frequencies in the image versus their amplitude. The frequency plot has zero in the center with positive frequencies to the right and negative ones to the left. This is called the real axis. Running vertically through the center of the plot is the imaginary axis. Amplitude is plotted as intensity of the pixels in the picture. Low frequencies are clustered around the center of the plot and increase in frequency as you move outward.

Step 3: Create a Butterworth Filter Mask. Click the Enhance I Manual FFT\ Butterworth Filter Mask... menu item and the Butterworth Filter Generator window will pop up. This window is used to generate a filter mask to be applied to the image. The filter mask is multiplied by the FFT image to change the distribution of frequencies in the image. If the filter mask has very small values around its center, the masked FFT will have severely reduced low-frequency components. If the mask is dark around the edges, the masked FFT will have reduced high frequency components. One big advantage this approach gives us is that we can also generate "band pass" and "band stop" filters, which leave the low and high frequencies and remove those in between, or vice-versa.

The Butterworth Filter Generator window has a display showing a plot of the frequency characteristics of the filter it will generate, along with controls to change the shape of it. There is also a control to affect the size of the filter mask. This mask must be the same size as the image you are filtering.

Click the Low Pass, High Pass, Band Pass and Band Stop radio buttons to see what the various filter shapes look like. Move the Filter Order slider back and forth, and you will see the filter get steeper and shallower. When the low pass filter is selected, a Low Pass Radius control is visible which changes the cutoff point for the filter. Each of the other options enables a different control. The band pass and band stop filters have an additional control to adjust the width of the pass or stop band.

Now let's generate a mask. Set the filter mask for a Low Pass filter with a Filter Size of 128 x 128. Set the Filter Order to 1 and a Low Pass Radius of 16. Click Generate Filter, and a filter mask will be displayed as an image. As you can see, it is bright in the center, gradually fading to the edges. This tells us that the low frequencies will be relatively unaffected, but that high ones will be attenuated more and more as frequency increases.

Step 4: Mask the FFT. Now let's apply the mask to the FFT. Click the Enhance I Manual FFT I Mask Fourier Transform... menu item. The Mask FFT window will appear.

This window contains four controls:

• Fourier Image. Selects the Fourier Transform image that you want to mask.

• Masked With. Selects which image to use as a mask. Choose the Low-Pass Filter image.

• Base Value. When the base value is 0, frequencies blocked by the filter remain blocked; when the base value is 1, all frequencies present in the original image are passed through the filter. For now, leave this set to 0.

• Contrast. Multiplies the transmission of the filter by the contrast factor. This means that the filter does not merely attenuate unwanted frequencies, but can also amplify desired ones, increasing the effective contrast of the image. For now, leave this set to 1.

Now click Apply and a copy of the FFT image appears, but it is bright in the center and darker toward the edges, showing the effects of having been multiplied by the filter mask. Remember, this display is just a representation of the FFT of the image. The real FFT is a pair of complex, floating point arrays containing the real and imaginary frequency components of the triangle image. You cannot directly edit the FFT.

Step 5: Perform an Inverse FFT. Now click on the Butterworth Filter masked version of the FFT that was just produced to make sure it is active and then click the Enhance I Manual FFT\Inverse FFT menu item. A "fuzzy" version of the original triangle will appear. This "fuzziness" is caused by the high frequencies associated with the abrupt transition from pure white to pure black at the edges of the triangle.

Step 6: Experiment. You can use the FFT Mask Generator to create different filters that have a number of effects on the triangle image. Just repeat steps 3, 4 and 5 above, using different parameters for the Butterworth Filter.

Close all the images except for the original "triangle.fts" image when you are done.

Step 7: Auto FFT. Performing FFT filtering manually is a complicated process. AIP4Win provides an automated tool to do this for you. Click the EnhanceI FFT Filter... menu item. The Butterworth FFT Filter window will appear.

At first glance this looks just like the FFT Mask Generator window, but note that the Filter Size radio buttons are missing, and the controls from the Mask FFT window have been added. This tool will automatically take the selected image and float it on a larger one, if necessary, to bring it to the required square, power-of-2 dimensions needed by the FFT algorithm. It will then automatically run each of the steps listed above, and you will be able to see the individual windows appear as the steps are performed.

Select the "triangle.fts" image, and then set up the filter as follows:

Filter Shape: Low Pass

Filter Order: 4

Base Value: 0

Contrast: 1

Click Apply and watch what happens. The result should be a series of images flashing by, leaving a very fuzzy version of the original image.

Step 8: Try a Real Image. Open the "030119204.ccd" image from the Image Enhancement tutorial directory. Invoke the Auto FFT Tool and set it up as follows:

Filter Shape: High Pass Filter Order: 1 High-Pass Radius: 16 Base Value: 0 Contrast: 1

Click Apply. A new image will be generated which is a greatly sharpened version of the original. You may want to raise the Min. Pixel Value control on the Display Control window to improve the contrast. You can use the Brightness Scaling Tool to adjust the contrast as well.

Try out different settings on the Auto FFT Tool to see how they affect the appearance of the final image. Like all the other tools, it pays to experiment to get comfortable with how it will perform.

Close all open images when you are finished.

Utities Calibrate Measure Enhance Transform Color Mufci-Image Preferences Window Help jHi*l hihihi ami uiy ^iBaiBiafeiggi hibi msN

Current Active Image-

! Lurent Active Image -|||37)SlaveFíe1; NGC6992HijJ|

display I Défauts I Irnaoei I