CSE/EE 585: Digital Image Processing II

Computer Project Report #1 :

Image Filtering

Group: Nils O Krahnstoever, Kaizhi Tang and Chunwei Yu

Date: March/5/1999

1. Objectives

Part One: Noise cleaning

There are many filtering methods to remove noise in images, such as Box Filtering, Median Filtering,Gauss Filtering, Contrast-DependentOutlier Removal, k-Nearest Neighbor Filtering, Midrange Filtering etc. None of the methods works well under all circumstances, each has its own specific area in which it works best. The first part of this project is to write code to implement various filtering strategies to remove different kinds of noise in an image, compare the performance for each method at different parameters and evalute the cost and result for each method.

Part Two: Image restoration

Using various methods to restore the blurred noise image caused by different mechanisms, compare the performance for each method as different parameters are varied, evaluate the cost and result for each method.
 
2. Summary of related work

Part One: Noise cleaning

A lot of work has been done in the image noise removal. Afrait(1954), Andrews and Kane(1970), Andrews and Caspari(1971), Haralick, Griswold and Kattiyakulwanich(1975) gave a statistic framework for noise removal. Davis and Rosenfeld(1978) suggested a k-nearest neighbor averaging technique for noise cleaning. Wang, Vagnucci and Li(1981) used a gradient inverse weighted noise-cleaning technique to reduce the sum-of-squares error within homogeneous regions while keeping the sums of squares between homogeneous regions relatively constant. Bovik,Huang, and Munson(1983) developed the general order statistics approach taking linear combinations of the sorted values of all the neighborhood pixel values. The most common one--Median Filtering-- was first introduced by Tukey(1971), and got its many variations by Gallagher and Wise(1981), Narendra(1981), Nodes and Gallagher(1983), Fitch, Coyle and Gallagher(1985) etc. Trimmed- Mean Filtering is another common order statistic operator that works well when the noise distribution has a fat tail(Bedner and Watt, 1984). Rider(1957), Arc and Fontata(1988) suggested the midrange esimator when the noise distribution has light and smooth tails. Enrich(1978) introduced a symmetric hysteresis and Lee(1983b) proposed the sigma filter averagingthe pixel values that are within a two-sigma interval. Selected-neighborhood averaging was introduced by Graham(1962), Newman and dirilten(1973), Tomita and Tsuji(1977), Nagao and Matsuyama(1979), Haralick and Watson(1981) and Lee(1980) used a minimum mean square noise-smoothing technique suitable for additive or multiplicative noise.

Part Two: Image Restoration

Image restoration is mostly based on the assumption of linear shift-invariant degradation so that the linear algebra can be applied. Schwarz and Friedland(1965) gave the definition of degradation model, and Deutsch(1965), Noble(1969), and Bellman(1970) presented the background for matrix operations. The discrete degradation model in terms of circulant and block-circulant matrices is developed by Hunt(1971, 1973). Much work has been done on inverse filtering approach by McGlamery(1967), Sondhi(1972), Cutrona and Hall(1968), and Slepian (1967). The progress in least square technique is made mostly by Helstrom(1967), Harris(1968), Rino(1969), Horner(1969), and Rosenfeld and Kak(1982).
 
3. Analytical Derivations

Part One: Noise Removal

Noise cleaning is based on the neighborhood spatial coherence and neighborhood pixel value homogeneity. It detects lack of coherence and either replaces the offending pixel or smooth the pixel values in the neighborhood. If the noise is well behaved, statistical approach can be used and  the box filter--weighted average of neighborhood of pixel value-- is the best both for the uncorrelated and correlated noise.The equally weighted average is based on the assumption that the noise is uncorrelated and the variance of the noise is uniform such that the equally weighted averaging is enough to remove the noise efficiently. If the noise is uncorrelated and the variance has a Gaussian distribution, then Gaussian filter should be implemented. When there is a peak noise(outliers), the pixel value was replaced by a random arbitrary number that has little to do with the original value, various other apporaches can be used. Order statistic neighbourhood operator sorted the neighborhood pixels in value and calculated the weighted average. The median operator takes the midpoint value as the average and the midrange operator takes average of the largest and smallest values which works better if the noise is light-tailed. K-nearest-neighbors approach sorts the values of the neighbors and takes the averages of k values that are nearest to the pixel in consideration. The Constrast-dependent outlier removal operator calculates the average and variance of the neighborhood, from the deviation of the pixel, determine whether to  replace with the average or not.

Part Two: Image Restoration

Image restoration is based on the linear and shift-invariant property of degradation. The resulting image is usually obtained from a known mechanism such as camera motion which is linear and shift-invariant plus the noise which is uncorrelated with the blurring process. The resoration is to implement the inverse of degradation operator. Although it can be done using matrix inversion in sptatial domain, the restoration is much more efficient  with simple point by point algebraic operation in frequency domain. With the existence of noise, based on different criterion, different approaches are resulted.
Minimizing the RMS of noise results in the Wiener filter. Minimizing the Laplacian operator applied the image comes up with the constrained least square filter. To Cutt off certain frequency range of noise, Inverse filtering operator with cutt-off  may be used used. Based on some of the knowledge of original iamge and noise, power spectrum filtering can be used to restoring the image.
 
4. Algorithm

Part One: Noise Removal

The neighborhood is taken as 3x3 pixel matrix with the pixel in consideration as the center element of the matrix. Based on different approach, for each pixel in the image :
 
(i) Equally weighted average(box filtering)

Take the average of the nine pixels and assign it to the pixel in consideration.

(ii)  Median Filtering

Sort the neighborhood pixel in value, take the midpoint value in the list as the new value for the center pixel.

(iii) Gauss Filtering

Calculate the gaussian weight matrix, take the weighted average of the neighborhood pixel and assign it to the pixel in consideration.

(iv) Contrast-dependent outlier removal

Calculate the average and variation of the neighborhood pixel. If the value of the pixel has large deviation compared to its neighbor, replace it with the average, else remains unchanged.

(v)  k-Nearest Neighbour filtering

Sort the neighborhood pixel in value, take the average of the nearest k value in the list and assign it to the pixel.

(vi) Midrange Filtering

Sort the neighborhood pixel in value, take the average of the largest and smallest value in the list as the new value of the pixel.

Part Two: Image Restoration

     step 1  transform the blurred image and the impulse response function into frequency domain using forward FFT
                                                g(x,y)-->G(u,v)     h(x,y)-->H(u,v)

     step 2 based on different filtering
 

 (i) Inverse Filtering(Cuff-off)

Set a threshold for the elements in H(u,v) below which it is set to 1.0, then do pixel by pixel operation F(u,v)=G(u,v)/H(u,v)

(ii)  Inverse Filtering(Frequency Cuff-off)

Set a threshold for frequency above which the values related to these frequencies are set to 1.0, then do pixel by pixel operation F(u,v)=G(u,v)/H(u,v)

(iii) Wiener Filter

Add a constant and do pixel by pixel operation(H(u,v) is conjugate of H(u,v)) F(u,v)=H(u,v)*G(u,v)/(|H(u,v)|*|H(u,v)|+constant*Sn(u,v)/Sf(u,v))

(iv) Power Spectrum Filter

Estimate the noise power spectrum Sf(u,v) based on knowledge of the noise added to the image, obtain the power spectrum Sn(u,v) of the original(no blur, no noise) image(both are unrealistic since the original image is not known and the knowledge about noise is quite limited), do pixel by pixel operation F(u,v)=Sqrt(Sf(u,v)/(|H(u,v)|*|H(u,v)|*Sf(u,v)+constant*Sn(u,v))*G(u,v)
 

(v)  Constrained Least Squares with Second order derivative smoothing

Implement the Laplacian operator in frequency domain to get P(u,v), do pixel by pixel operation F(u,v)=H(u,v)*G(u,v)/(|H(u,v)|*|H(u,v)|+constant*|P(u,v)|*|P(u,v)|)


     step 3 use the inverse FFT to get the restored image F(u,v)-->f(x,y)
 
 

5. Results

 

Part One: Noise Removal

After many times of simulation, the following Excel table is obtained. Here is some conclusion when comparing different methods with different neccesary parameters applied on different noise images.

Generally, Median Filtering and k-Nearest Neighbor Filtering when k is 6 are the best two methods. We can compare the worse noisy images after filtering with those before filtering. Fig.1 (a) is the noise image. Fig. 1(b) and Fig. 1(c) are the filtered images using the Median Filtering and  k-Nearest Neighbor Filtering when k is 6 respectively. It seems that Midrange Filtering is not a good filter. Fig. 1(d) shows its effect. O/F RMS means the RMS errors between the original image and the filtered image. Fig. 2(a) to Fig. 2(d)  are another group of images. The noise image is taken from the salt pepper noise image with noise ratio equal to 0.2.


Figure 1   (a)Gaussian noise with deviation=21, (b) Median filter (O/F RMS = 12.5) 
(c) k-Nearest filter (O/F RMS=10.2), (d) Midrange filter (O/F RMS=18.3)

Figure 2  (a) Salt-pepper noise with noise ratio 0.2, (b) Median filter (O/F RMS = 29.1),
(c) k-Nearest filter (O/F RMS=34.1), (d) Midrange filter (O/F RMS=72.9)

For every kind of method, there is its favarite noise. Box filtering is an average method. Median filtering is very suitable to filter the salt-pepper noise. It is shown in the above examples. (compare Fig.2 (a) and Fig. 2(b)) Gaussian filtering is good at Gaussian noise. Fig.3 (a) shows the filtered image of Fig. 1(a), with the parameter alfa equal to 2 and beta equal to 20. Contrast-dependent outlier removal filtering is good at Gaussian noise when the threshold value is big. Fig.3 (b) shows its effect and the noise image is also Fig. 1(a). The k-Nearest Neighbor filtering is good method to almost every noise. But it shows best effect when deal with Fig.1 (a) when k is 3. Fig. 3(c) is the effect.

Figure 3  (a) Gaussian (2,20) Filtered (O/F RMS=9.7), (b) CDOR(0.9) Filtered (O/F RMS=10.0),
(c) k-Nearest (3) Filtered (O/F RMS=7.4)

Those method with some parameters are researched. We try to find out what is the best parameter. For all the situation, the noise is the multiplicative noise.For Gaussian filtering, as we keep alfa constant and let the ratio of beta to alfa is increasing, we can see that the effects become better and better. But as the ratio is large enough, the effects will not be apparent. Fig. 4(a) is the noise image. Fig. 4(b) to Fig.4 (d) are the gaussian filtered images with alfa =2 and ratio =5, 50 and 100 respectively. The data table is here.

beta/alfa          5.0          10.0          20.0       40.0        50.0         100.0
RMS error N/F      O/F   N/F    O/F   N/F     O/F  N/F    O/F  N/F   O/F  N/F     O/F   N/F
alfa=2             16.5 13.0    15.5  12.1    15.1 11.7   14.9 11.6  14.9 11.5    14.8  11.5

 

Figure 4  (a) Multiplicative noise, (b) Gaussian (2,10) Filtered (O/F RMS=13.0), 
(c) Gaussian (2,100) Filtered (O/F RMS=11.5), (d) Gaussian (2,200) Filtered (O/F RMS=11.5)
 
When we keep the ratio of beta to alfa and increase the value of alfa. We can get the following table.

alfa                  5.0        10.0        20.0         40.0        50.0       100.0
RMS error          N/F   O/F   N/F   O/F    N/F   O/F   N/F   O/F   N/F  O/F   N/F  O/F
beta/alfa=50       14.9  11.5  9.0   11.6   6.5   12.5  5.0   13.2  4.2  13.8  3.5  14.1

Fig. 5(a) to Fig.5 (c) are the Gaussian Filtered images with the constant ratio of beta to alfa (50) and alfa changes from 2 to 10 to 22 respectively.
 


Figure 5 (a) Gaussian (2,100) Filtered (O/F RMS=11.5), (b) Gaussian (10,500) Filtered (O/F RMS=11.6), 
(c) Gaussian (22,1100) Filtered (O/F RMS=14.1)

For Contrast-dependent outlier removal filtering, the effect will be better with the increment of the threshold value. But this is not the law. For some noise, especially the salt pepper noise, the best effect is shown when it is beside 0.6, in the middle. Fig.6 (a) to Fig.6 (c) show the effect when the threshold is 0.2, 0.6 and 0.9 respectively.



Figure 6 (a) CDOR(0.2) Filtered (O/F RMS=21.3), (b) CDOR(0.6) Filtered (O/F RMS=18.5), 
(c) CDOR(0.9) Filtered (O/F RMS=17.9)

For k-Nearest neighbor filtering, the effect when k=6 will be better than that k=3. Again,this is not the law. For some noise, the best effect is shown when k=3. Fig. 7(a) to Fig. 7(c) show the effect when k=3 and 6 respectively. The noise is salt pepper with noise ratio equal to 0.1.
 


Figure 7 (a) Salt-pepper noise with noise ratio 0.1, (b) k-Nearest filter (3) (O/F RMS = 28.2), 
(c) k-Nearest filter (6) (O/F RMS = 20.4)

Conclusion

(i)   The Median filter and k-nearest filter work well for different noises.
(ii)  Each kind of noise has its best filter.
(iii) For each filter, there seems to exist the optimal parameter value that produces the best noise removing.
 

Part Two: Image Restoration

In this the relative performance of various restoration algorithms was qualitatively and quantitatively assessed. The following methods where implemented and compared.
 
• Inverse Filtering (cutoff [i.e., ignoring small values])
• Inverse Filtering (frequency cut-off)
• Wiener Filter
• Power Spectrum Filter
• Constrained Least Square with Second order derivative smoothing

Description of the Experiment


Original Image:

The performance of the restoration algorithms was experimentally examined using the following image.
 




 


Figure 8: This is the original image "boat.dat"
found in the image database.
 






Degradation Models:

Two types of artificial analytical blurring were added:
 

• Linear horisontal motion of varying length.
• Gaussian blurring with varying sigma.


Furthermore, artificial gaussian white noise of zero mean and varying variance was added to more closelt approximate a real life situation.

Parameters:

The noise was varied by using sigma values from the set {2, 4, 8, 16}. For gaussian blurring, the amount of blurring was varied using sigma values from the set {1, 2, 4, 8}. For motion, blurring lengths from the set {8, 16, 32, 64} where used. The degraded noisy images where restored by applying the above methods varying the main restoration parameter for each method. The range in which the parameter of the different restoration algorithms was varied depended on the method:
 

• Inverse Filtering (cutoff)

Parameter varied: Threshold below which values in the system response function where ignored and set to 1.0.
Values: {0.001-0.01, 0.01-0.1, 0.1-1.0} (total of 30 values)
• Inverser Filtering (freq. cutoff)

Parameter varied: Freq. above which the system response was considered to be 1.0. The unit of the frequency is stated in pixel corresponding to the FFT of the images that has the same dimensions (256x256) as the original. The actual frequency is given by dividing the stated "frequencies" by 512.
Values: {10-80} (8 values)
• Wiener Filtering

Parameter varied: Gamma value as denoted in the lecture. The Wiener filter used in this experiment is thus the parametric version of the Wiener filter.
Values: {0.2-2.0} (10 values)
• Power Spectrum Filter

Parameter varied: Parameter before the noise power spectrum value. This allows a certain variation between the assumed noise power spectrum and the actual noise power spectrum.
Values: {0.2-2.0} (10 values)
• Constrained Least Square Filter

Parameter varied: Gamma value as denoted in the lecture.
Values: {0.001-0.01,0.01-0.1,0.1-1.0,1-5} (35 values)


The restoration experiment resultet in about 3200 images

It can be argued that the number of images would not have been neccessary but since disk space and CPU time was not a problem, there was no reason not to vary the parameters to this extend. The summary file, which can be found following this link, allows to efficiently get an overview of the results.

Results

 
Before a compact comprehensive summary of the results is presented, a representative case is shown in more detail. This allows to make specific comments about the restoration methods and the results commonly obtained.

Representative Example (noise with sigma=4 pixel):

In this example, noise with a sigma of 4 pixel was added to the degraded images. The two cases of Gaussian blurr and linear motion blurr are presented.

Gaussian blurr (sigma=2 pixel)

Degraded Images
 




_
Figure 9: (a) degraded image (Gaussian blurr of sigma=2)
(b) noise (sigma=4) added

Restored Images

Qualitative Analysis

1. Inverse Filtering (cut-off):
 




__
Figure 10: Ignoring values less than (a) 0.01 (b) 0.1 (c) 1.0

For low restoration parameters, image (a), only relatively small values in the response function are ignored. Therefore the noise term is amplified by a factor of 100 leading to the observed "grizzle". This "grizzle" decreases as the cut-off value increases (b). For even larger restoration parameters, image (c), so many points of the response function are masked out that the effective restoration is minimal. The restored image approaches the degraded image and the amount of restoration goes to zero.

2. Inverse Filtering (frequency cut-off):
 




__
Figure 11: Ignoring freq. greater than (a) 10 (b) 40 (c) 80
 




For low cut-off values only the lowest frequencies are affected and the effective restoration is low. For high cut-offs, image (c), most frequencies are affected and the restoration approaches the above inverse filtering.

3. Wiener Filter:
 




__
Figure 12: Factors of (a) 0.2 (b) 1.0 (c) 2.0
 




The Wiener filtering is roughly invariant to variations of the restoration parameter. This raises the question whether the restoration parameter should have been varied to a greater extend. Theoretically a restoration of 1.0 gives the optimal Wiener Filter. While maybe not capturing the full potential of the parametric Wiener filter the results show that the Wiener Filter gives consistent results around its optimal restoration parameter. In addition, the Wiener Filter was together with the Constraint Least Square filter, one of the two best performing methods.

4. Power Spectrum Filter:

__
Figure 13: Factors of (a) 0.2 (b) 1.0 (c) 2.0

As above for the Wiener filter, little variation in the result could be observed for varying restoration parameters. The noise level of the power spectrum filter was very high throughout all blurring parameters and noise levels.  This is probably due to the fact that a single noise sample (the actual noise sample that was added to the degraded image) was used. Estimating the noise power spectrum by averaging over several noise samples could potentially have given better results.

5. Constraint Least Square:

__
Figure 14: Factor of (a) 0.001 (b) 0.01 (c) 0.1

For the constraint least square algorithm, the restoration parameter can be considered as the weight given to the smoothness of the image. As it can be observed in the above images (a) through (c), the "smoothness" increases as the restoration parameter increases. The constrained least square method was one of the better performing methods for image restoration.

Motion (length=16 pixel)

The above experiments where repeated with linear motion degradation of length 16 pixel.

Degraded Image:

_
Figure 15: (a) degraded by linear motion (16 pixel)
(b) noise (sigma=4) added


Restored Images:

For inverse filtering the same comments as above apply:

1. Inverse Filtering (ignoring small values in response function):

__
Figure 16: Ignoring values less than (a) 0.01 (b) 0.1 (c) 1.0

2. Inverse Filtering (frequency cut-off):

__
Figure 17: Ignoring freq. greater than (a) 10 (b) 40 (c) 80

3. Wiener Filtering:

__
Figure 18: Factors of (a) 0.2 (b) 1.0 (c) 2.0

Again it can be seen that the Wiener Filter is robust towards variation of the restoration parameter. Qualitatively smaller values tend to give better results.

4. Power Spectrum Filter:

__
Figure 19: Factor of (a) 0.2 (b) 1.0 (c) 2.0

As above for Gaussian blurr, the noise level in the results obtained using the power spectrum filter is large compared with the best images obtained by the other methods.

5. Constraint Least Square:

__
Figure 20: Factor of (a) 0.001 (b) 0.01 (c) 0.1

It can be observed that the smoothness in the image increases as the restoration parameter increases as above for Gaussian blurr. Although the noise level seems to be higher for smaller restoration parameters, image (a), the obtained result seems to be slightly better than for larger values.

RMS Errors between original image and restored images:

In the following table the root mean square difference between the restored images and the original undegraded, noise-free image are summarized to obtain a quantitative measure for the performance of the various restoration algorithms. A complete summary of all images created can be found here.

 

 

Method	Defocus (sigma=4)			Motion (len=16)			Noise=4
Inverse Filter (cutoff)	0.01	0.1	1.0	0.01	0.1	1.0	parameters
	54.49	18.92	24.06	99.96	22.61	49.61	rms error
Inverse Filter (freq. cutoff)	10	40	80	10	40	80	parameters
	24.00	19.41	19.77	37.81	21.99	23.99	rms error
Wiener	0.2	1.0	2.0	0.2	1.0	2.0	parameters
	18.24	20.70	18.72	18.13	19.25	18.53	rms error
Power Spectrum	0.2	1.0	2.0	0.2	1.0	2.0	parameters
	35.38	41.61	31.19	65.83	65.44	63.22	rms error
Constr. Least Square	0.001	0.01	0.1	0.001	0.01	0.1	parameters
	19.13	18.00	20.17	20.29	17.92	21.18	rms error


It can be seen that the constrained least square method gives the best results in terms of the rms error. The power spectrum filter gives the worst results. It is worth noting that the best method in terms of rms error does not necessarily have to give the best qualitative results. A method might produce few outliers in the restored image that are perceived to be negligible compared to the overall quality of the image. However, the rms error "quality measure" is sensitive towards outliers and can lead to an "unfairly" low rating of the results. A good performance evaluation will involve both qualitative and quantitative performance measures. Therfore two additional sets of qualitative results (i.e., the actual images) are presented.

Representative Example: "Worst Case" (follow link for actual results)

The most difficult restoration task is the one with maximum degradation and highest noise level (noise with sigma=16 pixel, maximum blurring). This example gives an qualitative and quantitative impression of how the various methods perform in a very difficult restoration task. For compactness the images and rms errors are summarized in a table.

Gaussian Blurr:

It could be observed very clearly that all restoration methods struggle with this task. The high noise level makes a good restoration very difficult. An unbiased person that had no knowledge of the actual original image identfied the two trees in the image but did clearly not point out a sailboat. The Wiener filter, the inverse filter and the constrained least square filter all produced comparable results.

Motion:

The results for the motion degradation where clearly slightly better, although the degraded image did not appear to be less degraded than the images in the above case of gaussian blurr. Qualitatively the Wiener filter outperformed the other methods. With the constrained least square method a close second. This could also be observed in terms of the rms errors.

Representative Example "Best Case" (follow link for actual results)

The best case is considered to be the the one where the noise level is minimal. We choose to use maximum blurring in this example in order to show the performance of the various restoration algorithms under optimal conditions. The noise that was added to the degraded images has a variance corresponding to sigma=1.0 pixel.

Gaussian Blurr:

Compared to the "worst case", the results where better, but still far from the original image. All methods gave approximatelt comparable results with the exception of the power spectrum filter.

Motion:

Compared to the restoration of the gaussian blurring the restoration of the motion degraded images is far better. Especially the   Wiener filter and the constrained least square method gave good results (subjectively and in terms of rms error) and an unbiased person identified the trees, the forest in the background and "guessed" a lake in the foreground.
 
 

Detailed comparison of the various methods

Following is the curves of the root mean square error vs. their parameters for different filters. The inverse filtering with cuff-out decreases monotonically and finally reaches a constant as the parameter inceases. The inverse filter with frequency cut-off behaves the same way. For the constrained least square filter, there exists one optimal value at which the operator works best. The power spectrum operator and the wiener
filter change very slowly at large parameters.

Inverse Fliter(Cutt-off)

Inverse Filter(Freq. Cutt-off)

Constrained Least Square

Power Spectrum Filter

Wiener Filter


Following is the comparison of different filters apply to the same level of blurring and noise. For different type of Blurring and different noise, the constrained least square filter and the wiener filter always work best. The power spectrum filter is worst and with the inverse filter in between. It's no surprise that as the level of blurring and noise increases, the root mean square error increases too. But the presence of the noise plays much important role here. At low level of noise, the difference between various filters  tends to diminish. while at high level of noise, the difference is prominent.
 

Gauss Blurring(Noise Level=2)

Gauss Blurring(Noise Level=16)

Motion Blurring(Noise Level=2)

Motion Blurring(Noise Level=16)
 
 

Conclusion

(i)  For constrained least square filter, there exists an optimal parameter value under which it works best. For other filters, it seems that increase their parameters tend to improve their performance.
(ii) Under all types of blurring and all levels of the noise and blurring, the constrained least square filter and the wiener filter performance the best. The power spectrum filter seems to be the worst.

Source code (follow this link)