Dwayne Phillips works as a computer and electronics engineer with the U.S. Department of Defense. He has a Ph.D. in Electrical and Computer Engineering from Louisiana State University.
Introduction
This is the seventh in a series of articles on images and image processing. The first six articles discussed reading and writing images (TIFF format), displaying them, printing them, histograms and histogram equalization, and basic and advanced edge detection. This article will discuss spatial frequency filtering. (All source code is available through the C Users Group.)
Spatial Frequencies
All images and pictures contain spatial frequencies. Most of us are familiar with some type of frequency such as the 60-cycle, 110-volt electricity in our homes. The voltage varies in time as a sinusoid and the sinusoid completes a full cycle 60 times a second — a frequency of 60 Hertz.Images have spatial frequencies. The gray level in the image varies in space (not time), i.e. it goes up and down. Figure 1 shows the side view of an image with low spatial frequencies. The gray level is low at the left edge of the figure, stays constant for a while, then shifts to a higher gray level. The gray level is fairly constant throughout (only one change in space) and so has low spatial frequencies.
Figure 2 shows the side view of an image with high spatial frequencies. The gray level changes many times in the space of the image. The rate or frequency of change in the space of the image is high, so the image has high spatial frequencies.
Filtering
Filtering is also a common concept. When we adjust the bass and treble on our stereos we are filtering out certain audio frequencies and amplifying others. High-pass filters pass high frequencies and stop low frequencies. Low-pass filters stop high frequencies and pass low frequencies. In the same manner, we can filter the spatial frequencies in images. A high-pass filter will amplify or "pass" frequent changes in gray levels and a low-pass filter will reduce frequent changes in gray levels.Consider the nature of a frequent or sharp change in gray level. Figure 1 showed an image with only one change in gray level. That change, however, was very sharp — it was an edge (Phillips, November 1991). A high-pass filter will pass, amplify, or enhance the edge. A low-pass filter will try to remove the edge. Instead of an instant move from one gray level to another, the low-pass filter will produce a gradual slope between the two levels. The two gray levels will still exist, but the transition will be slower.
Application of Spatial Image Filtering
Spatial image filtering has several basic applications in image processing. Among these are noise removal, smoothing, and edge enhancement. Noise in an image usually appears as snow (white or black) randomly sprinkled over an image. Spikes or very sharp, narrow edges in the image cause snow. A low-pass filter smooths and often removes these sharp edges.Edge enhancement improves the appearance of an image by sharpening the outlines of objects. I used an edge detector in "Image Processing, Part 6: Advanced Edge Detection" (Phillips, January 1992) to enhance edges. In that article, I detected the edges in an image and then overlaid the edges on top of the original image to emphasize them. A high-pass filter produces the same result in one operation.
Frequency vs. Spatial Filtering
Consider sound as noise varying in the time domain, i.e. the pitch of the noise varies with time. A pure sinusoid completing a cycle 1000 times a second is a 1KHz tone. In the frequency domain, this is a single value at 1000. To filter it out, we multiply it by a low-pass filter that only passes frequencies below 900 cycles per second. Picture the low-pass filter as an array with the value of 1 in all places from 0 through 900 and the value 0 in all places above 900.Multiplication in the frequency domain is a simple idea, however, there is just one problem. You hear sound in the time domain, but you must transform it to the frequency domain before you can multiply it. You do this with the Fourier transform (Karl 1989) which requires substantial computations, and in some cases is not worth the effort.
Multiplication in the frequency domain corresponds to convolution (Phillips, Nov. 1991, Jan. 1992) in the time and the spatial domain. If we use a small convolution mask, such as 3x3, then convolving this mask over an image is much easier and faster than performing Fourier transforms and multiplication.
Low-Pass Filtering
Low-pass filtering smooths out sharp transitions in gray levels and removes noise. Figure 3 shows four low-pass filter convolution masks. Convolving these filters with a constant gray level area of an image will not change the image. Notice how the second convolution mask replaces the center pixel of the input image with the average gray level of the area. The other three masks have the same general form — a "peak" in the center with small values at the corners.The next four figures show numerical examples of how a low-pass filter affects an image. Figure 4 shows an image segment with low spatial frequencies. The image segment changes gray level once, but with a sharp transition. Figure 5 shows an image segment with higher spatial frequencies. It changes gray level every row of pixels, with every change a sharp transition.
Figure 6 shows the result of convolving the first 3x3 low-pass filter mask of Figure 3 with the image segment given in Figure 4. The high and low gray-level rows remain, but the transition differs. The low-pass filter smoothed the transition from one row to three rows of pixels. In a photograph this would make the edge look fuzzy or blurred.
Figure 7 shows the result of convolving the first 3x3 low-pass filter mask of Figure 3 with the image segment given in Figure 5. The image in Figure 7 still has transitions or edges from row to row. The low-pass filter, however, reduced the magnitude of these transitions. In a photograph they would appear dimmer or washed out when compared with the original in Figure 5.
Median Filters
A special type of low-pass filter is the median filter (Levine 1985). The median filter takes an area of an image (3x3, 5x5, 7x7, etc.), looks at all the pixel values in that area, and replaces the center pixel with the median value. The median filter does not require convolution. It does, however, require sorting the values in the image area to find the median value.There are two noteworthy features of the median filter. First, you can easily change the size of the median filter. (The photographs later will show the effect of using a different size.) Implementing the different size is a simple matter of for loops in the code.
Second, median filters remove noise in images, but change noise-free parts of images minimally. Consider the influence of a 3x3 median filter on the image segments in Figure 4 and Figure 5. The image in Figure 4 would not change. Centering the 3x3 filter on the last row of 150's yields a median value of 150. Centering it the first row of 1's yields a median value of 1. The image in Figure 5 would change, but the change would not be obvious. The filter would replace the rows of 150's with rows of 1's and would replace the rows of 1's with rows of 150's.
Effects of Low-Pass Filtering
Photograph 1 is an aerial image spotted with noise. There are two streets running vertically with rows of houses on either sides of the streets. The white dots all over the trees are noise. The noise came from a poor photograph compounded by less than perfect scanning. Photograph 2, Photograph 3, Photograph 4, and Photograph 5 show the result of applying the low-pass filters to the image in Photograph 1. The four results are all similar. The filters removed the snow from Photograph 1 and retained the appearance of the houses and streets. My personal favorite is Photograph 5 but you should apply all four masks to your image and decide for yourself. The masks are different and produce different results — sometimes noticeable sometimes not.Photograph 6 shows the result of applying a 3x3 median filter to Photograph 1. The filter removed the snow but left the areas of houses and streets unchanged.
Photograph 8, Photograph 9, and Photograph 10 show the result of applying three different median filters (3x3, 5x5, and 7x7) to the house image in Photograph 7. In the result of the 3x3 filter (Photograph 8) , the trees start to appear fuzzy and the lines between the bricks disappear. In the result of the 5x5 filter (Photograph 9) , the trees are blotches, the bricks only textures, and the other details are disappearing. Finally, the 7x7 filter (Photograph 10) eliminates all detail. The "best" filter for this image is probably the 3x3 filter. Images with different-size details and noise would require different-size filters.
(Note how in Photograph 10 you can only recognize the large objects such as windows, roof, window frames, door frames, and door. This is an excellent starting point for a part of image processing called segmentation. In segmentation you want a computer to find the major objects in the image and separate or segment them from the other objects. Segmentation would be difficult with Photograph 7 because it contains too many small and insignificant objects, such as bricks and leaves. Photograph 10 is fuzzy enough where you can only recognize the large objects. Segmentation will have to wait for another article.)
Although you can change the size and results of median filters easily, they can be slow. The 3x3 median filter and the 3x3 convolution filters work equally fast. However, when you move to 5x5, and beyond, the median filter slows down noticeably because of the continuous sorting and picking of the median value.
Implementing Low-Pass Filtering
Listing 1 shows the source code for the low-pass and median filters. The first section of code declares the four low-pass filter masks (then three high-pass filter masks which we'll discuss later).The major filtering function is filter_image. This implements the low-pass (and high-pass) convolution filters. filter_image resembles the convolution-based, edge-detection functions in parts 5 and 6 of this series (Phillips, Nov. 1991, Jan. 1992). The first section of filter_image checks to see if the output image file exists. If not, it creates the file to be the same size as the input file.
The d=type statements set up the denominator for later use. The low-pass filter masks should have fractions in front of them (1/6, 1/9, 1/10, and 1/16). Using the fractions in convolution masks would require floating-point arrays and operations. It is much simpler and quicker to use shorts and then divide the final result.
filter_image reads an array from the input image and then goes into the for loops to perform the convolution. These loops move through the image array and do the 3x3 multiplication and summing. The sum is divided by the denominator mentioned above and set to the max or min value in case of overrun. filter_image finishes by calling fix_edges (Phillips, November 1991) to fill the edges of the output and writes the array to the output file.
The next function in Listing 1, median_filter, implements the variable-size median filter. The key to this filter is finding the median pixel value in the nxn area you are filtering. I did this by creating an array to hold the pixel values, sorting the array, and taking the middle number in the sorted array. First I allocated the elements array to hold the pixel values by calling malloc. median_filter then checks for the existence of the output image file and creates it, if necessary.
After reading the image, median_filter goes into a series of loops which cover the entire image array. As it moves through the image, it copies an nxn area of pixel values surrounding each point to the elements array. The output image array is set to the median_of the elements array. median_filter calls fix_edges to fill out the edges of the output and then writes it to the output image file.
The next function in Listing 1 is median_of. This calls sort_elements to sort the elements array and returns the middle element of the sorted array. The sort_elements function (next in Listing 1) is a bubble sort. It calls the swap function (also in Listing 1) to swap elements.
High-Pass Filtering
High-pass filters amplify or enhance a sharp transition (an edge) in an image. Figure 8 shows three 3x3 high-pass filter convolution masks. Each will leave a homogenous area of an image unchanged. They all have the same form — a peak in the center, negative values above, below, and to the sides of the center, and corner values near zero. The three masks, however, produce different amplifications to different high spatial frequencies.
Effects of High-Pass Filtering
Figure 9 and Figure 10 show the results of applying the first high-pass filter mask to Figure 4 and Figure 5. In Figure 9 (the result of filtering Figure 4) the high-pass filter amplified the edge. The transition from 150 to 1 is now from 255 to 0. In a photograph this would appear as adjacent black and white lines. In Figure 10 (the result of filtering Figure 5) the high-pass filter amplified the many edges, making the transitions all from 255 to 0. This would appear as alternating black and white lines in a photograph. Notice the differences between Figure 9 and Figure 10 and Figure 5 and Figure 6. The low-pass filter (Figure 5 and Figure 6) smoothed the edges. In contrast, the high-pass filter enhanced them.Photograph 11, Photograph 12, and Photograph 13 show what the high-pass filters will do to the house image of Photograph 7. Photograph 11 shows the result of the first high-pass filter convolution mask. Look closely at the differences between Photograph 7 and Photograph 11. In Photograph 11 you can see leaves, shingles on the roof, the texture of the screen door, and far greater contrast in the bricks and mortar. This high-pass filter has enhanced the details of the image.
Photograph 12 shows the result of the second high-pass filter convolution mask. This image is almost black and white (few gray levels between). The details (edges) were enhanced, but probably too much. Photograph 13 shows the result of the third high-pass filter convolution mask. This image contains many tiny highlights in the leaves of the trees and noise or snow in the remaining parts.
These photographs show the differences in the filtering properties of the three masks. The third filter mask has little affect on low spatial frequencies and a great affect on areas with relatively high spatial frequencies. So it does not enhance the bricks but does enhance the tiny leaves in the trees. The second filter has a high gain on most high frequencies (edges). So it produced an almost black and white image all the edges were amplified greatly. The first filter amplifies all edges, but not with a high gain. The filter enhanced, but did not saturate, the edges. Each filter has its own unique properties and you should use them to their advantage. Try all three on an image and choose the enhancement you prefer.
Implementing High-Pass Filtering
The high-pass filters use the same function, filter_image, as the low-pass filters, but when calling filter_image you send it a different filter mask. In Listing 1, you will find the function setup_filters. This copies a filter mask declared at the top of Listing 1 into a 3x3 filter array. You must call this function to load the desired filter mask before calling filter_image.It's time now to integrate the filtering capabilities into the C Image Processing System (Phillips 1991, 1992). Listing 2 shows the additions to the main program. I added a tenth case to handle image filtering. The code calls the usual routines to obtain image names and parameters. The get_filter_options function is at the end of Listing 1. It queries the user about low-pass, median, or high-pass filtering and which filter mask to use. The second part of Listing 2 shows the addition to the main menu.
Listing 3 shows the mainfilt application program which will filter an entire image file. mainfilt communicates with the user via a command line. Typing mainfilt produces a reminder of the command and parameters. mainfilt interprets the command, reads the header of the input image file, and sets up the looping structure. If needed, it calls setup_filters to load the desired filter mask. The loops over i and j call the chosen filter and cover the entire image. The filter functions read the input image array, filter it, and write the result to the output image. I used mainfilt to create the output images shown in the photographs.
Conclusion
This article has discussed spatial frequencies in images and how to filter these frequencies. It demonstrated several types of low-pass and high-pass filters on various images. These are not the only filter masks available. Those familiar with Fourier transforms could derive other masks and also experiment with band-pass and band-stop filters.
References
Karl, John H. 1989. An Introduction to Digital Signal Processing. Academic Press.Levine, Martin D. 1985. Vision in Man and Machine. McGraw-Hill.
Phillips, Dwayne. March 1991. "Image Processing, Part 1: Reading the Tag Image File Format." The C Users Journal.
Phillips, Dwayne. May 1991. "Image Processing, Part 2: Displaying Images and Printing Numbers." The C Users Journal.
Phillips, Dwayne. June 1991. "Image Processing, Part 3: Displaying and Printing Images Using Halftoning." The C Users Journal.
Phillips, Dwayne. August 1991. "Image Processing, Part 4: Histograms and Histogram Equalization." The C Users Journal.
Phillips, Dwayne. November 1991. "Image Processing, Part 5: Writing Images to Files and Basic Edge Detection." The C Users Journal.
Phillips, Dwayne. January, 1992. "Image Processing, Part 6: Advanced Edge Detection." The C Users Journal.