CSE/EE 585: Digital Image Processing II

Computer Project Report #1

Image Filtering

Group: Anirudh Modi, Shin Chin and Ming Ni

Date: March 21, 2000
A. Objectives

To compare the performance of different methods for noise removal and for image restoration, as different parameters are varied.

 
I. Noise removal
1. Images are corrupted by the following kinds of noise:
    a) Gaussian noise with standard deviations 1, 5, 9, 13, 17, 21 (note: standard deviation is the square root of variance)
    b) salt and pepper noise (5-25% in increments of 5)
2. The corrupted images are filtered using the following kinds of filters:
    a) Equally weighted average or Mean filtering
    b) Median filtering
    c) Gaussian filtering
    d) k-Nearest Neighbor filtering
3. To compare and contrast the effects of the above filtering techniques in terms of RMS error between
     the original image and the filtered image, and between the noisy image and the filtered image.
II. Image Restoration
1. To restore an image corrupted by
    a) a Gaussian filter
    b) a sinusoidal waveform running vertically in the image
    c) discrete camera motion
    d) White Additive Gaussian Noise
2. To restore the corrupted image using the following techniques
    a) Inverse Filtering
    b) Wiener Filtering
    c) Power Spectrum Filtering
    d) Constrained Least Squares with Second order derivative smoothing
3. The results from the different methods are that compared and contrasted.


B. Methods
 

I. Generating noisy Images
a. Adding Gaussian noise with standard deviations 1, 5, 9, 13, 17, 21
Gaussian noise was implemented in C++ using the Box-Muller method. which is fully described in Ross. The Box-Muller method uses the technique of inverse transformation to turn two uniformly distributed randoms into two unit normal randoms, X and Y. X and Y are unit normal random variables (mean = 0 and variance = 1), and can be easily modified for different values of mean and variance using the relation:
   X' = mean + sqrt(variance) * X
   Y' = mean + sqrt(variance) * Y
X and Y were added to 2 pixels at a time, X to the first pixel and Y to the second pixel.
 
b. Adding salt and pepper noise
We wrote a C++ program to implement this. For each pixel in the original image, we generated a random number between -1 and 1. For x% salt and pepper noise, we do the following: a random number in the range [-1.0:1.0] is generated. If the number is greater than 1.0-x/100, we replace the original image's pixel value with 255 (salt noise). If the random number generated is smaller than -1.0+x/100,  we replace the pixel value with 0 (pepper noise). Otherwise we leave the pixel value of the original image unchanged. Hence, if we want x% salt and pepper noise, we will have x/2% salt noise and x/2% pepper noise.
 
II. Image Filtering Methods
 All the filters mentioned below were implemented using a C++ program which can be found in the Appendix. An NxN square mask was used for each case of the filters, for three different values of N, i.e., 3, 5 and 7.
 
a. Equally Weighted Average  or "Mean" Filtering
The mask simply averages all the member values and replaces the center pixel with this average. If the pixels are at the edges of the image, we take the average of the pixels in the part of the mask that overlaps iwith the image and ignore the rest. For example, a pixel on the left edge of the image using a 3x3 mask has only 5 neighbors, hence we average only these 5 neighbors and the pixel itself, and replace the selected pixel with the result.

b. Median Filtering
We sort all the pixels in the mask according to their pixel values. We then take the value of the middle pixel from this sorted list (which is the median) and assign it to the selected pixel.
 

c. Gaussian Filtering
To create the masks, we approximate the two-dimensional Gaussian function given as


                       g(a,b) = exp( -(a²  + b²) / (2 * stddev² ) )
 

We created 3x3, 5x5 and 7x7 Gaussian Masks. The masks are as follows:

1 2 1 2 3 2 1 2 1 3x3

1 4 7 4 1 4 20 33 20 4 7 33 55 33 7 4 20 33 20 4 1 4 7 4 1 5x5

1 12 55 90 55 12 1 12 148 665 1097 665 148 12 55 665 2981 4915 2981 665 55 90 1097 4915 8103 4915 1097 90 55 665 2981 4915 2981 665 55 12 148 665 1097 665 148 12 1 12 55 90 55 12 1 7x7

 
where we used normalization factors of 1/15, 1/331, 1/50887 for the 3x3, 5x5 and 7x7 Gaussian masks respectively. To get the normalization factors, we summed all the values in the respective masks.


d. k-Nearest Neighbor Filtering
For each pixel in the mask, we subtract its value with the value of the center pixel. We then sort these subtracted values and take the first "k" values (which is (N² + 1)/2 in our case) in this sorted list, average them and add it to the value of the center pixel. We then replace the value of the pixel in the image with resulting value calculated above.


III. Compare RMS error
We selected three images: lenna, peppers and cleanwheel. Adding Gaussian noise with standard deviations 1, 5, 9, 13, 17, 21, and adding 5%, 10%, 15%, 20%, 25% salt and pepper noise for each one. For each of 33 noisy images,  we applied the above four noise removal filters. For each filter, we tried 3x3 mask, 5x5 mask and 7x7 mask (giving us 12x33=396 images in all!). The performance of different filtering methods as different parameters were compared in terms of RMS error between the original image and the filtered image, and between the noisy image and the filtered image. The RMS error was always expressed as percentage for generality (i.e. the actual value was divided by the number of colors: 255), since it then becomes a non-dimensional quantity and and is easier to compare.

IV. Image Blurring Methods
First we deteriorate the image in one of the following three ways:

 
a. Gaussian smoothing
The method used for Gaussian smoothing  is the same in principle as the Gaussian Filtering algorithm described above, except we are using the filter to corrupt the image rather than to enhance it.

b. Sinusoidal waveform
A vertical sinusoidal waveform was created using the vgsin function in Cantata. This waveform was then added to the original image.

c. Camera motion
The camera motion was simulated with Cantata. A sinusoidal waveform was generated using the vgsin function. This waveform was then multiplied with the Fourier Transform of the original image. The result was then converted to the spatial domain with the inverse Fourier transform. We then get the blurred image resulting from camera motion.
A sinusoidal waveform in the frequency domain is two impulses in the spatial domain. This means that by multiplying the Fourier transform of the original image with a sinusoid, we are actually convolving the original image with two impulses in the spatial domain, thus producing two overlapping images hence simulating the effect of image blurring due to camera motion. We can control the distance between the two images by changing the frequency of the sinusoidal waveform.


After the original image was deteriorated by one of the above three methods, we added White Additive Gaussian Noise to it using the vgauss function in the Khoros library. We used three different SNRs for each image obtained by giving standard deviations of 5, 13, 21 to the White Additive Gaussian noise.

                      V. Image Restoration Methods
                            The images were restored using the following four methods:

a. Inverse Filtering
This filtering was done using the inverse filtering algorithm in the Khoros library. The blurring function depending on the way the image was deteriorated was input into the "PSF function". The inner function "minimum PSF threshold" was used to control the cut-off. Three different cut-offs 0.1, 0.5, 0.8 were used for all the images. Since the noise was also known in our case, we used the formulation F(u,v) = G(u,v)/H(u,v) - N(u,v)/H(u,v) to clean the image in the frequency domain. Had the exact noise not been known (as is often the case in practise), we would only use the conventional inverse filtering formulation F(u,v) = G(u,v)/H(u,v).


b. Wiener Filtering
This filtering was done using the Wiener Filtering algorithm in the Khoros library. There are two parameters to be varied, the "Wiener parameter" and the "minimum PSF Threshold". We used the default for the "Wiener parameter" for all the images. For the "minimum PSF threshold" parameter, we used values of 0.1, 0.5, 0.8, 1.2 for all the images.


c. Power Spectrum Filtering
Power Spectrum filtering was done using a combination of the Khoros functions. Computation of the power spectrum of the noise function, original image and blurring function were done.


d. Constrained Least Squares with Second order derivative smoothing
The constrained least squares filtering was done using a combination of the Khoros functions. We computed the square of the Fourier transform of the Laplacian operator. We also computed the Fourier transform of the blurring function. The optimal gamma for the constrained least squares method was found by computing the residual vector r= g - (H)(f) where r is the residual vector, g is the degradated image, H is the blurring function and f is the output of the filter. r is a function of gamma. We compare the square magnitude of r with the square magnitude of the noise n, which we know, and adjust gamma until they are almost equal for optimal Filtering.

C. Results

 
Part 1: Noise Removal
From the tables and the graphs, we can summarize as follows:
- For Gaussian Noise, Gaussian filtering and k-Nearest Neighbor filtering are the best methods.
- For Salt and Pepper Noise, Median filtering and k-Nearest Neighbor filtering are the best methods.  The 5x5 mask can clean the noise better than  the 3x3 mask as the noise level goes up.

There are various kinds of techniques that we can use to clean the noise. However, the performance (in here, we use the RMS error to measure the performance) of each technique depends on how the noise behaves. For the well-behaved noise like Gaussian noise, the suitable filter is the linear types (Box and Gaussian filter). In contrast, the outlier or peak noise like the Salt & Pepper noise is suitable to be cleaned by non-linear filter (Median filter and K-Nearest Neighbor filter).

a) Performance for each method as different parameters are varied

i. Mean Filtering
For Gaussian noise, as the standard deviation  of the noise was increased, it was more difficult to remove the noise. This can be seen from the graph: Mean filter for lenna.gif corrupted with Gaussian noise. The RMS error between original and filtered image for higher standard deviations of Gaussian noise was larger. From the graph, one can see that as the mask size increases, the RMS error increases. Hence a 3x3 mask is better able to remove the noise than a 5x5 mask and a 5x5 mask better than a 7x7 mask.
For salt and pepper noise, as the percentage of salt and pepper noise added was incresed, it was more difficult for the mean filter to remove the noise. This can be seen from the graph: Mean filter for lenna.gif corrupted with Salt and Pepper Noise. One can also see from the graph that for 10%, 15%, 20%, 25% salt and pepper noise, the 5x5 mask size produced the smallest RMS error between original and filtered image. However for 5% salt and pepper noise, the 3x3 mask has the smallest RMS error.

ii. Median Filtering
For Gaussian noise, as the standard deviation  of the noise was increased, it was more difficult to remove the noise. This can be seen from the graph: Median filter for lenna.gif corrupted with Gaussian noise. The RMS error between original and filtered image for higher standard deviations of Gaussian noise was larger. From the graph, one can see that as the mask size increases, the RMS error increases.  Hence a 3x3 mask is better able to remove the noise than a 5x5 mask and a 5x5 mask is better than a 7x7 mask.
For salt and pepper noise, as the percent of salt and pepper noise added was incresed, it was more difficult for the mean filter to remove the noise. This can be seen from the graph: Median filter for lenna.gif corrupted with Salt and Pepper Noise. One can also see from the graph that for 20% and 25% salt and pepper noise, the 5x5 mask produced the smallest RMS error between the original and filtered image. However for 5%, 10% and 15% salt and pepper noise, the 3x3 mask produced the smallest RMS error.

iii. Gaussian Filtering
For Gaussian noise, as the standard deviation  of the noise was increased, it was more difficult to remove the noise. This can be seen from the graph: Gaussian filter for lenna.gif corrupted with Gaussian noise. The RMS error between original and filtered image for higher standard deviations of Gaussian noise was larger. From the graph, one can see that as the mask size increases, the RMS error increases.  Hence a 3x3 mask is better able to remove the noise than a 5x5 mask and a 5x5 mask is better than a 7x7 mask.
For salt and pepper noise, as the percent of salt and pepper noise added was incresed, it was more difficult for the Gaussian filter to remove the noise. This can be seen from the graph: Gaussian filter for lenna.gif corrupted with Salt and Pepper Noise One can also see from the graph that for 5%, 10%, 15%, 20%, 25% salt and pepper noise, the 5x5 mask size produced the smallest RMS error between original and filtered image.

iv. k-Nearset Neighbor filtering
For Gaussian noise, as the standard deviation  of the noise was increased, it was more difficult to remove the noise. This can be seen from the k-Nearest filter for lenna.gif corrupted with Gaussian noise graph. The RMS error between original and filtered image for higher standard deviations of Gaussian noise was larger. From the graph, one can see that for standard deviations of 1,5, 9 for the Gaussian noise as the mask size increases, the RMS error increases.  However for standard deviations of 17 and 21, the 5x5 mask size produces the smallest RMS error.
For salt and pepper noise, as the percent of salt and pepper noise added was incresed, it was more difficult for the Gaussian filter to remove the noise. This can be seen from the graph k-Nearest filter for lenna.gif corrupted with Salt and Pepper Noise, one can also see from the graph that for 5% and 10% salt and pepper noise, a 5x5 mask size produces the smallest RMS error followed by the 7x7 mask size then the 3x3 mask size. For 15%, 20% and 25% salt and pepper noise, a 7x7 mask size produces the smallest RMS error followed by the 5x5 mask size then the 3x3 mask size.
 

b) Comparison of the performance of the different methods

i. Salt and Pepper Noise
From the graph Comparison of various filters for 25% Salt and Pepper noise on lenna.gif (corresponding to the images here), we can see that the 5x5 median filter works the best in that it produces the smallest RMS error between original image and filtered image.  The 3x3 k-Nearest neighbor filter produced the worst results.

ii. Gaussian Noise
From the graph Comparision of various filters for Gaussian noise with std dev 21 on lenna.gif (corresponding to the images here), we can see that the 3x3 Gaussian filter works the best in that it produces the smallest RMS error between original image and filtered image. The 7x7 mean filter produced the worst results.
 
The complete results for all the cases are present here. The best filter (with regards to the minimum RMS error between the final filtered image and the original images) for each type of noise applied to the lenna.gif image are tabulated below (O-F stands for error between the original image and the final filtered image, N-F stands for the error between the noisy image and the final filtered image):

Image		Noise Type	Noise Level	Filter	RMS error (O-F)	RMS error (N-F)
lenna		Gaussian	SD=1	3x3-kNearest	1.61%	1.60%
lenna		Gaussian	SD=5	3x3-kNearest	2.05%	1.80%
lenna		Gaussian	SD=9	3x3-kNearest	2.82%	2.27%
lenna		Gaussian	SD=13	3x3-gaussian	3.47%	5.13%
lenna		Gaussian	SD=17	3x3-gaussian	3.81%	6.23%
lenna		Gaussian	SD=21	3x3-gaussian	4.20%	7.37%
lenna		S and P	5%	3x3-median	3.25%	12.56%
lenna		S and P	10%	3x3-median	3.62%	17.45%
lenna		S and P	15%	3x3-median	4.15%	21.34%
lenna		S and P	20%	5x5-median	4.80%	24.89%
lenna		S and P	25%	5x5-median	5.00%	27.83%





Part 2: Image restoration

a) Performance of each method

i. Inverse Filtering (Results)
For images corrupted by Gaussian filter and White Additive Gaussian Noise, we found that Inverse filtering using a PSF threshold of 0.5 works the best as it produces a sharp image with little noise. When using a PSF threshold of 0.1, the quality of the "restored image" was not very good due to the presence of a lot of "dots" (noise). For a PSF threshold of 0.1, the "restored image" was not very sharp.
For images corrupted by camera motion and White Additive Gaussian noise, we found that Inverse filtering using a PSF threshold of 0.1 worked the best in that it managed to remove much of the blurring caused by camera motion and much of the noise to produce a sharp and clean restored image, even as the standard deviation of the Gaussian noise was increased. For a PSF threshold of 0.5, the "restored image" was pretty "off-color" with some wavy texture. The same thing was true of the case using a PSF threshold of 0.8 but slightly worse.
For images corrupted by sinusoidal waveform and White Additive Gaussian noise, the inverse filter did not do a very good job of restoring the image. Even for the best case of PSF threshold of 0.1, there were still "bands" in the "restored" image although the sinusoidal waveform seemed to be removed. The quality of the "restored" image for PSF thresholds of 0.5 and 0.8 were pretty bad with the lenna image hardly well defined.

ii. Wiener Filtering (Results)
For images corrupted by Gaussian filter and White Additive Gaussian noise, the Wiener filter did not do as good a job of restoring the image as the inverse filtering. A PSF threshold of 1.2 seemed to work the best for most cases. However the "restored" images were not very sharp.
For images corrupted by camrea motion and White Additive Gaussian noise, the Wiener filter removed most of the blurring caused by camera motion, with PSF thrsholds of 0.8 and 1.2 performing the best. However as the standard deviation of the White Additive Gaussian noise was increased, the "restored" image was not as sharp and a little "off-color".
For images corrupted by sinusoidal waveform and White Additive Gaussian noise, the Wiener filter managed to remove the sinusoidal waveform. However, there were "bands" in the "restored" image. In this case, a PSF threshold of 0.1 gave better results.

iii. Power Spectrum Filtering (Results)
For images corrupted by Gaussian filter and White Additive Gaussian noise, the Power Spectrum filter did a good job of restoring the image producing a sharp and clean image. However as the standard deviation of the White Additive Gaussian noise was increased, the "restored" image was more blurry and less sharp.
For images corrupted by sinusoidal waveform and Additive White Gaussian noise, the power spectrum filter seemed to do a better job of restoring the image than the Inverse Filtering and Wiener Filtering in that the presence of "bands" was not as strong. The filter seemed to remove the sinusoidal waveform but some of it can still be slightly visible. However, as the standard deviation of the White Additive Gaussian noise was increased, the Power Spectrum filter did not produce a good job of restoring the image as the "restored" image was not very sharp and "off-color" as well as the presence of "texture".
For images corrupted by camera motion and White Additive Gaussian noise, the Power Spectrum filter does a good job of removing the blurr caused by camera motion producing a sharp and clean image. Even as the standard deviation of the White Additive Gaussian noise was increased, the Power Spectrum filter does a good job of restoring the image.

iv. Constrained Least Squares with Second order derivative smoothing (Results)
For images corrupted by Gaussian filter and White Additive Gaussian noise, the CLS method does not produce as good results as the inverse filtering and power spectrum filtering. The color of the "restored" image was not as strong and not as sharp especially as the standard deviation of the White Additive Gaussian noise was increased.
For images corrupted by sinusoidal waveform and White Additive Gaussian noise, the CLS method managed to remove much of the sinusoidal waveform. However, there were still "bands" in the "restored" image similar to that of the Inverse filtering and Wiener filtering. The "restored" image was not as clear as the standard deviation of the White Additive Gaussian noise was increased.
For images corrupted by camera motion and White Additive Gaussian noise, the CLS method managed to remove the blurring caused by camera motion. When the standard deviation of the White Additive Gaussian Noise was 5, the "restored" image was pretty sharp. However, as the standard deviation of the White Additive Gaussian Noise was increased, the "restored" image was less sharp.

b) Comparison of different methods

i. Gaussian filter
For images corrupted by Gaussian filter, the inverse filtering method with a PSF threshold of 0.5 and Power Spectrum filtering produced the best results. The Constrained Least Squares approach and Wiener filtering approach did not produce as good results.

ii. Sinusoidal waveform
For images corrupted by sinusoidal waveform, the inverse filtering, Wiener filtering and Constrained least squares approach produced "restored" images which had "bands". Power Spectrum filter produced better results than the other filters in that "bands" were not present in the restored image.

iii. Camera motion
For images corrupted by camera motion, all the filtering methods managed to produce good results in removing the blur caused by camera motion.
 
 

1. For part 1, we implemented the various filters to remove Gaussian noise and Salt and Pepper noise. We then compared the performance of the various filters. We found that the performance of the various filters depends on the mask sizes of the filter as well as the type of noise corrupting the image. We also found that the 5x5 median filter is best able to remove Salt and Pepper noise as expected. k-Nearest neighbor filter comes close second after the median filter. Mean filter is the worst filter for Salt and Pepper noise as it has an effect of blurring the image beyond recognition. These were supported by the magnitude of RMS error between original image and filtered image. This confirms the fact that median filter is an outlier filter. For Gaussian noise, a 3x3 Gaussian filter works the best in terms of RMS error. However, one might question the use of RMS errors to evaluate the filters for all purposes. Once the RMS errors get large (say more than 15-20%), they do not make much sense (due to the fact that two totally different images may have an RMS error as low as 30-40%, hence once we near that range, the numbers make little sense). In such cases, visual indication/comparison may be the best classifier.

2. For part 2, we compared the performance of various image restoration filters (in the frequency domain). Many factors influence the effectiveness of the restoration process. We found that the performance of each filter depends on the image, the type of corruption and the various parameters that can be varied for each respective filter. All the filters are very sensitive to cut-offs/thresholds, hence care should be taken to choose the optimum values for every case.
    
   E. Links to all the graphs/results:
   • Filtering of lenna.gif with Gaussian Noise (std_dev=21)
   • Filtering of lenna.gif with 25% Salt and Pepper Noise (10% noise)
   • Filtering of peppers.gif with Gaussian Noise (std_dev=21)
   • Filtering of peppers.gif with 25% Salt and Pepper Noise
   • RMS error data for all the runs
   • Individual study of each filter for removal of Gaussian noise
   • Individual study of each filter for removal of Salt and Pepper noise
   • Comparison of RMS of various filters for Gaussian noise case with std_dev=21 (on lenna.gif)
   • Comparison of RMS of various filters for 25% Salt and Pepper noise case (on lenna.gif)
   • Inverse filtering
   • Wiener filtering
   • Power Spectrum filtering
   • Constrained Least Square filtering
   • All the 429 filtered images generated for Part 1!
   • All the CANTATA workspaces
    
   F. Links to the Source Code:
   • main.cc: The main driving routine
   • noise.cc: The code for the various noise generating routines
   • filters.cc: The code for the various filters
   • error.cc: The code for calculating RMS error
   • image.cc: Basic code for reading/writing/manipulating PGM images
   • image.h: Header for the GrayImage class
   • Miscellaneaous files: Makefile, matrix.cc, matrix.h
   • Entire C++ source code in tar-gzipped format

   ---