There is no such thing as a universal filter, but we can get close by building one that adapts to the local noise. Dwayne Phillips walks us through the math to make a filter look a little bit smart.
Introduction
Most images contain some type of noise. This occurs today more than ever since people are using home scanners and digital cameras. These inexpensive input devices work only as well as their users (amateurs like me) handle them. We tend to over-expose images and allow dust to accumulate on lenses and scanner glass. How do you remove the noise from such images? How do those software packages that come with the cameras and scanners do it? This article discusses one method: adaptive filtering. Adaptive filters combine simple filter concepts with decision making logic to change or adapt their behavior based on the image and noise content.
Simple Filters and Noise
Two commonly used image filters are the mean and median filters. (An earlier paper in this series discussed median filtering of spatial frequencies. See [1].) The mean filter calculates the mean or average pixel value in a region. The median filter finds the median pixel value in a region. (Line up the pixels, sort them by value, and select the one in the middle.) Each of these filters work well in specific situations. As I will show, they are not right for every noisy image.
The mean filter works well on noise where the pixel value (the color, or intensity for grayscale images) of the noise is similar to the image's pixel values. The averaging effect of the mean filter tends to smooth away this noise. The mean filter, however, tends to blur edges in an image. If the noise is in the form of impulses or spots, these impulses act like edges, and the mean filter smudges them.
Image 1 is (left to right) an image of a boy, that image corrupted with noise, and the result of the mean filter applied to the noisy image. This noise contains bright and dark impulses. Notice how the mean filter only smudged or blurred the noise. It did not remove it.
The median filter works well on impulse or spot noise. It throws away those outlying pixels without averaging their values. The median filter, however, does not work well on noise that is close to the image's pixel values. Image 2 shows the boy image corrupted with the same type of impulse noise as in Image 1. The result of the median filter is much better than that of the mean filter. The median filter threw out all the impulse noise pixels.
There are several types of noise commonly encountered in image processing. This paper looks at three types: 1) equal distribution noise, 2) Gaussian or normal distribution noise, and 3) salt and pepper noise (illustrated in Images 1 and 2). In equal distribution noise, all the pixels are spread evenly between two pixel values. Equation (1) shows this mathematically. It shows the probability of a pixel value in the image's histogram. In this equation, any pixel between gray levels a and b will occur the same number of times as any other pixel in that range. The image will not contain any pixels outside that range. Equal distribution noise occurs when using a digital camera with light concentrated in one visual band.
The histogram for Guassian noise is described by Equation (2). This is the common normal distribution or bell curve. The gray levels of the pixels tend to cluster around a mean "m." The spread of gray levels about the mean is given by the standard deviation (s) "sigma." Gaussian noise is common in digital cameras and scanners. In scanners, the scanning light source is not perfect; it does not illuminate evenly. The illumination near the source is brighter than away from it. The pattern of brightness has a normal or Gaussian distribution.
Finally, salt and pepper noise contains two values: one bright (salt) and one dark (pepper). Specks of dust and dirt on a camera lens or a scanner bed are simple examples.
Image 3 shows the boy image corrupted by the three types of noise. Though not as severe as the salt and pepper noise, the equal and Gaussian distribution noise corrupt the image.
The different types of noise also differ in the manner in which they combine with an image. The Gaussian and equal distribution noise are additive. Their values add to the pixel values in an image. Notice how the image corrupted with Gaussian and equal distribution noise (right side of Image 3) is brighter than the original image. Adding the noise raises the pixel values. The salt and pepper noise is multiplicative. The values in salt and pepper (very bright and very dark) are multiplied by the values in the image. The very bright value saturates the input image, so its product is trimmed to the brightest value possible (white). The very dark value is a zero. Multiplying it by the original image produces a zero (black).
I wrote a utility program to generate the different types of noise shown in the images. I don't discuss that program here, but you can download the source code for it, along with the source code for the filters described, and .bat files for generating the images shown, from the CUJ website at www.cuj.com/code.
For an explanation of the I/O routines; the median, high-pass, and low-pass filters; and the topic of spatial frequency filtering, see [3].
The simple mean and median filters work well when you know a lot about the noise corrupting an image. They do not, however, work well when employed blindly. What we need are filters that adapt or change themselves based on the noise they encounter.
Adaptive Filters
Adaptive filters examine a noisy image and adapt their way of processing that image accordingly. This paper discusses three adaptive filters: 1) MMSE (Minimum Mean-Square Error), (2) DW-MTM (Double Window-Modified Trimmed Mean filter), and 3) SAM (Signal Adaptive Median) filter. These filters are described in [2] — long, complicated names, but simple when you think about them.
Adaptive filters perform their job based on image statistics. Equations (3), (4), and (5) show the information these filters need to gather from the images. Equation (3) calculates the first moment (mean) of an image region; simply add up the pixel values and divide by the area. Equation (4) shows how to calculate the second moment of an image region. It is meaningful here only because we need it for Equation (5). Equation (5) calculates the variance (s2) of the pixels in a region. The variance and its square root, the standard deviation, indicate the spread of pixel values in a region; these figures describe how much the values vary from the mean. A large variance usually indicates that an edge is within the region. Another explanation for a large variance is the presence of salt and pepper noise.
Listing 1 shows the moments subroutine that calculates the first and second moments, the variance, and the standard deviation (s). The "else not out of bounds" section follows directly from Equations (3), (4), and (5).
The moments subroutine calculates statistics from any size area in an image. This includes the statistics for an entire image. It can be used to find the noise variance in a background area of an image as well as the noise variance in an image that contains nothing but noise. I used moments in this last mode to find the noise variance for the examples shown.
The first adaptive filter to discuss is the MMSE filter. This filter produces an output equal to the input when the local variance is much greater than the noise variance. (The noise variance is the variance of a plain background area containing nothing but noise.) When this happens, the input probably contains an edge, so leave it alone. If the local variance is about the same as the noise variance, the output becomes the mean of the local area. Therefore, the question for the MMSE filter is, do we apply a mean filter or do nothing?
Equation (6) shows how the MMSE filter makes this decision. When the local and noise variances are about the same, the first term goes away, leaving only the local mean. When the local variance is much greater than the noise variance, the second term goes away, leaving only the input. Cases between the extremes produce mixtures of the two.
Listing 2 shows the code that implements the MMSE filter. It allows the user to choose the size of the area being filtered (3x3, 5x5, etc.) with the size parameter. That parameter is sent to the moments subroutine to calculate the local variance and mean. The noise variance is known ahead of time and input by the user. The "else moments not out of bounds" section of code implements Equation (6).
Image 4 shows the result of the MMSE filter applied to an image corrupted by Gaussian noise. The result of the filter, far right, is not as clean as the input image (far left). Nevertheless, it is cleaner than the corrupted image (center).
The MMSE filter does not work well with impulse noise such as salt and pepper noise. Image 5 shows this failing. The "cleaned image" (far right) does not look much better than the corrupted one (center). The MMSE filter either passes the input to the output or outputs the mean of the input. Image 1 showed how poorly the mean works on such a noisy image.
The DW-MTM filter works much better on salt and pepper noise, and performs well on the Gaussian noise as well. The name, Double Window-Modified Trimmed Mean, comes from the DW-MTM filter's use of two windows, and its behavior of trimming away impulses when it calculates the mean of an area.
The DW-MTM filter algorithm starts with a pixel having coordinates x,y. First, the filter finds the median of a little region surrounding x,y (a 3x3, 5x5, etc.). Next, it uses a bigger region (the second or "double" window such as 5x5, 7x7, etc.) to find a mean. When finding the mean, the filter throws away or "trims off" any pixel if its gray level varies from the median by a certain factor. That factor is a constant K times the standard deviation of the noise. The constant K ranges from 1.5 to 2.5. This is because in a Gaussian distribution 95% of the values are within two standard deviations of the mean.
This process sounds more complicated than it is. Listing 3 shows the dwmtm subroutine. The user passes in the parameters that set the sizes of the two windows (big_size and little_size). Also passed in are the standard deviation of the noise and the constant K (noise_sd and k). The loops over i and j go through the entire image. The first section inside these loops finds the median in a little region. The next section finds the lower and upper range using this median and K times the standard deviation of the noise. Finally, the code calculates a mean using only the pixels with values inside the upper and lower range. This mean is put into the output image.
Image 6 shows the result of applying the DW-MTM filter on the same noise used in Image 5 — with drastic improvement. The result is not as crisp as the input, but it is much improved over the corrupted image. The DW-MTM filter also works well on Gaussian noise (left as an exercise for the reader).
The final adaptive filter described here (there are many more) is the signal adaptive median or SAM filter. The SAM filter uses the low-pass and high-pass filters described in [1] and [3]. Areas of an image containing high spatial frequencies typically contain edges. A high-pass filter passes these edges through. Areas of an image with low spatial frequencies are plain background; the low-pass filter passes these areas through and blurs edges. The strategy employed by the SAM filter is: if an area contains background or blurs, use a low-pass filter. Otherwise, use a high-pass filter.
Equation (7) shows the SAM filter output. The factor K is adjusted by the presence or absence of edges. Equation (8) shows this adjustment — the adaptive part of this filter. If the noise variance multiplied by a constant c is greater than the local variance, set K=0. The SAM filter becomes a low-pass filter. Otherwise, the SAM filter output also contains information passed by the high-pass filter. The values for c range from 0.0 on up. I had good results with c in the range 2.0 and 3.0.
Listing 4 shows the SAM subroutine. First notice how this subroutine uses four image arrays instead of the usual two. The user passes in the types of low-pass and high-pass filters to use (see [1] and [3]). The outputs of these two filters go into the main loop over i and j. A call to the moments subroutine returns the local variance. The konstant (c) and the local and noise variance (passed in by the user) determine the factor K. This multiplies the high-pass filter result, and the product is summed with the low-pass filter result.
Image 7 shows the result of the SAM filter applied to an image corrupted by Gaussian noise. The clean image, although not as crisp as the input image, is much better than the corrupted one.
Putting It All Together
The three adaptive filters become more useful when placed into a program. Listing 5 shows a main program that calls these filters. It uses a command-line interface that permits using batch of script files like the ones that created the images in this paper (also available in the online source archive accompanying this article).
Conclusion
This paper has introduced the topic of adaptive filters that remove noise from images. Images commonly contain many types of noise. Simple filters work well in simple cases. Adaptive filters perform much better because they adapt their algorithms to the type of image and type of noise present. There are many more types of adaptive filters available. You can create your own adaptive filter by using several available filters and switching among them based on information you find in the image. The filters shown here have many parameters, and the examples given only scratched the surface. There are plenty of experiments to perform. As usual, have fun trying them.
References
[1] Dwayne Phillips. "Image Processing Part 7: Spatial Frequency Filtering," The C Users Journal, October 1992.
[2] Harley R. Myler and Arthur R. Weeks. Computer Imaging Recipes in C (Prentice Hall, 1993).
[3] Dwayne Phillips. Image Processing in C, Second Edition 2000. Available at fatbrain.com on http://www1.mightywords.com/asp/bookinfo/bookinfo.asp?theisbn=EB00014987.
Dwayne Phillips has worked as a software and systems engineer with the U.S. government since 1980. He has written Image Processing in C, Second Edition 2000 (see fatbrain.com), and The Software Project Manager's Handbook, Principles that Work at Work (IEEE Computer Society, 1998). He has a Ph.D. in Electrical and Computer Engineering from Louisiana State University. He can be reached at d.phillips@computer.org.