CASCADED DECISION-BASED MEDIAN AND UN-SYMMETRIC TRIMMED MEAN FILTER FOR REMOVAL OF HIGH-DENSITY IMPULSE NOISE IN AN IMAGE

K.S. SRINIVASAN and D.EBENEZER 
Department of Electronics and Communication Engineering
College of Engineering, Guindy, Anna University,
Chennai-600 025.
INDIA

Abstract: - A new two-stage cascaded filtering algorithm is proposed for removal of high-density impulse noise. The first stage is the Decision-based Median Filter (DMF) which is used to identify pixels likely to be contaminated by impulsive noise and replaces them by the median value. The second stage is the Un-symmetric Trimmed Mean Filter (UTMF), which uses a small, fixed window, to trim the impulse values lying at the extreme ends, in an unsymmetric manner. The proposed algorithm is tested on different images and is found to produce better results, both in terms of visual appearance and quantitative measures. In terms of edge preservation and noise suppression, the proposed algorithm shows a significant improvement in comparison with other non-linear filters even if the noise density is as high as 90%.

Key-Words: - Impulse noise, Non-linear filters, Standard Median Filter, Decision-based filter, Alpha-trimmed mean filter, Un-symmetric filter, Cascaded Filters.

1 Introduction
In the transmission of images over channels, images are corrupted by impulse noise, due to faulty communications[1,2]. The objective of filtering is to remove the impulses so that the noise free image is fully recovered with minimum signal distortion[3]. Noise removal can be achieved, by using a number of existing linear filtering techniques which are popular because of their mathematical simplicity and the existence of the unifying linear system theory. A major class of linear filters minimizes the mean squared error(MSE) criterion and it provides optimum performance among all classes of filters if the noise is additive and Gaussian. However, these linear filtering techniques are not effective in removing non-gaussian noise such as impulse noise and it gives rise to non-linear signal processing techniques. 
The best-known and most widely used non-linear digital filters, based on order statistics[4], are median filters. Median filters are known for their capability to remove impulse noise without damaging the edges. The main drawback of Standard Median filter(SMF) is that it is effective only for low noise densities. At high noise densities, standard median filters often exhibit blurring for large window sizes and insufficient noise suppression for small window sizes[5,6].

 The Alpha-Trimmed Mean Filter(ATMF)[7] is another type of non-linear filter, which, is also used to remove the impulse noise in which the parameter “”, called the trimming factor, controls the number of values that are trimmed. It can be seen that as the value of the trimming factor “” increases, the ability of the filter to remove impulse noise is further increased. However, when the noise density is as high as 50% and above, there is insufficient noise removal and loss of image edge details. The reason for this loss in image edge details is due to the fact that the ATMF trims the extreme values even if they are not impulse values[4].
The decision based-median filter is a class of impulse rejecting filter it replaces only the corrupted pixels by some nonlinear filter and the uncorrupted pixels leave it unaltered[4]. The decision whether a pixel is corrupted or not is determined by the local image structure. Once uncorrupted pixels classified from the corrupted pixels and are used to train and predict the relationship between the centre pixel and its neighbor pixel which can be used to replace the  corrupted pixels. The draw back of this method is that it blurs the edges because it smoothes the variation between the centre pixel and its neighboring pixels.
In order to overcome the above mentioned difficulties, a new two-stage cascaded filter is proposed in this paper which removes the noise as 
high as possible, without blurring and retains the fine edge details. The proposed algorithm contains a new kind of decision-based median filter and un-symmetric trimmed mean filter which are connected in cascade. This decision based-median filter directly replaces the corrupted pixels only with a median value of its neighborhood pixels while the uncorrupted pixels are left unchanged. The Un-symmetric Trimmed Mean Filter(UTMF), as the name indicates, performs un-symmetric trimming of the impulse values and averages the remaining pixels. The purpose of using an un-symmetric trimmed mean filter is to remove only the impulse noise lying at the extreme ends, while the original pixel values are retained. 

2 Algorithm

2.1 Decision-based Median Filtering (DMF)
The first stage of the proposed algorithm is the decision-based median filter. In standard median filtering(SMF), each and every pixel value is replaced by the median of its neighborhood values. The decision-based median filter however makes a rough approximation of whether a pixel is corrupted or not. Then, the uncorrupted pixel values are retained and the corrupted pixels are replaced by the median value of their neighbors. Hence the output of DMF is superior to the SMF. The algorithm for DMF works as follows:

Step 1:  A 2-D window ‘S xy’ of size 3 x 3 is selected. 
the pixel to be processed is Z xy.
Step 2:  The pixel values in the window are sorted in 
ascending order and Z min , Z max, Z med  are calculated 
       	Z min - the minimum gray level value in S xy
       	Z max -the maximum gray level value in S xy
       	Z med – the median of gray levels in S xy
Step 3:  Calculate the differences b1 and b2 as given 
by
b1= Z xy  - Z min, 
b2= Z xy  - Z max
Step 4:  If   b1>0 and b2<0, 
the pixel being processed is un-corrupted and it is left unchanged.
Else,
the pixel is corrupted and it is replaced with the median value Z med.

Move the window horizontally / vertically and repeat from step1 to step4. The above steps are repeated , until the processing is completed for the entire image. The output obtained is subjected to further processing.

2.2 Un-symmetric Trimmed-Mean filtering (UTMF)
The idea behind a trimmed mean is to reject the most probable outliers. In the existing Alpha-Trimmed Mean Filtering(ATMF), the trimming is symmetric at either end. The number of values being trimmed depends upon the trimming factor “”. If the value of =4, then “/2” values are trimmed on both the ends and the remaining pixels are averaged. It is observed that higher the value of “”, greater is the noise suppression. In ATMF, sometimes even un-corrupted pixel values are also trimmed. This eventually leads to loss of image detail and blurring of the image. In to overcome the above problem, an un-symmetric trimmed mean filtering method is proposed. 
In UTMF, the trimming is un-symmetric i.e. the numbers of pixels trimmed at the two ends are not always equal. The UTMF checks whether the extreme values of the sorted array, obtained from the 3 x 3 window, are impulse values and trim only those impulse values. For example, if a 3 x 3 window does not have any impulse, the UTMF would not trim any values. On the contrary, the ATMF would trim values, irrespective of whether the 3 x 3 window has an impulse or not. This property of UTMF makes it more efficient in noise suppression than the existing ATMF. The algorithm of UTMF is given below

Step 1:  A 2-D window ‘S xy’ of size 3 x 3 is selected.
Step 2:  The pixel values in the window are sorted in 
       	ascending order and stored in a 1-D array.
Step 3:  If any pixel value in the array is either ‘0’ or 
‘255’ (which is nothing but impulse noise), the corresponding pixel values are eliminated from the array. If there are no impulse values in the array, all the 9-elements are retained.                                
Step 4:  The pixel being processed is replaced by the   
       	mean of the values in the 1-D array.

Move the window by one step and repeat from step 1 to step 4. The above steps are repeated, until the processing is completed for the entire image 

2.3 Cascaded connection of DMF and UTMF
The DMF is superior to the SMF because it removes only corrupted pixels. The disadvantage of DMF is that, the median pixel also be a noisy pixel value results in DMF fails to remove noise effectively at 
high density. The UTMF has better noise removing ability than the existing ATMF, owing to the fact that it uses an unsymmetric trimming method to discard only the impulse values. The UTMF is used to remove the noise completely. At very high noise densities, around 80% there is blurring of the image. The proposed cascaded algorithm uses a combination of both DMF and UTMF, to further improve the output obtained from the UTMF. The noisy image is first processed using the Decision-based median filter. The output of DMF is given as the input to the UTMF. The cascaded connection is hence used to remove impulse noise with a noise density as high as 90%. The cascaded connection yields the highest value of Peak Signal to Noise Ratio(PSNR) and Image Enhancement Factor(IEF) value as shown in Tables 1 and Table 2.

3 Simulation Results 
The performance of the cascaded filter is studied at different levels of noise densities ranging from 10% to 90% The outputs are shown in Fig.1.

The value of PSNR is calculated, using the formula                          
PSNR= 	 (1)

The IEF is calculated, using the formula
                                IEF =           (2)    

where 
s – original image
r – corrupted image
x – restored image
MxN – size of image
In  Fig.1 the outputs of various filters like SMF(column 3), DMF(column 4), ATMF(column 5), UTMF(column 6), and proposed algorithm(column 7) are shown. Column 1 represents the original image and column 2 represents image corrupted by impulse (salt & pepper) noise. From column 3 SMF can give a reasonable output only up to 50 %, the same thing holds good for DMF and ATMF. An acceptable quality of the image is obtained for 70% of noised image during the recovery using UTMF. However in case of proposed algorithm there is an absolute recovery of 90% noised image which can be observed from the last row under proposed algorithm.
Fig 2 is obtained from the values given in Table 1 for a given 10% noised image the maximum PSNR obtained is 36.52 when DMF is used. For 20% noised image the maximum PSNR is 32.35% under UTMF, the trend slowly changes towards proposed algorithm in terms of increased PSNR as the noise densities increased up to 90% ie.,it can be observed the maximum PSNR is obtained using the proposed algorithm when compared to other mentioned algorithm with noise density increased from 30% onwards.
	Fig.3 shows a plot of Image Enhancement Factor for various filtering algorithms. Similar to the trends of db obtained in Table 1 here also the IEF is more for the proposed algorithm when the image is compared with SMF, DMF, ATMF and UTMF. However the general trend is that images are corrupted to the worst case and hence the proposed algorithm will be very much apt in removing high density noised image. 
	Fig 4 represents the outputs of various filters for different images ( camera man, blood cell and eight . tif) are analyzed. It shows that the proposed algorithm completely removes the noise even if the noise density is as high as possible. 
The Table 3 shows the IEF and PSNR values for the proposed algorithm for the above images. The PSNR value is well with in the minimum permissible range (25 db)for all the above images till the noise density is 70%. Above 70% noise density the PSNR value is starts decreasing slowly thus the edges are blurred even if the noises are removed effectively

Original Image    Noisy Image             SMF                   DMF                 ATMF                 UTMF                  PA

           a)               b) 30% Noise	         c)		        	d)	                      e)	                      f)	                     g)

           a)               b) 40% Noise	         c)		        	d)	                      e)	                      f)	                     g)

           a)               b) 50% Noise	         c)		        	d)	                      e)	                      f)	                     g)

           a)               b) 60% Noise	         c)		        	d)	                      e)	                      f)	                     g)

           a)               b) 70% Noise	         c)		        	d)	                      e)	                      f)	                     g)

           a)               b) 80% Noise	         c)		        	d)	                      e)	                      f)	                     g)

           a)               b) 90% Noise	         c)		       		d)	                      e)	                      f)	                     g)
Figure 1a) – Original Image
Figure 1b) – Corrupted Image 
Figure 1c) – Output of Standard Median Filter (SMF) 
Figure 1d) – Output of Decision-based Median Filter (DMF) 
Figure 1e) – Output of Alpha-Trimmed Mean Filter (ATMF) (with trimming factor =4) 
Figure 1f) – Output of Un-symmetric Trimmed Mean Filter (UTMF)
Figure 1g) – Output of Proposed Algorithm (PA)
Fig. 1 – Image Filtering Results

Table 1 – Comparison of PSNR values for various filtering methods
ND
 	PSNR (in decibels)	
	SMF	DMF	ATMF	UTMF	PA	
			=2	=4	=6			
10 %	33.06	36.52	29.03	31.32	32.44	32.65	32.41	
20 %	28.78	31.45	24.94	28.91	30.65	32.35	32.18	
30 %	23.60	25.30	21.80	25.86	28.44	31.90	31.88	
40 %	18.81	20.52	19.38	22.70	25.91	31.36	31.45	
50 %	15.27	16.69	17.23	19.54	22.88	30.64	31.05	
60 %	12.30	13.47	15.55	17.15	19.73	29.58	30.51	
70 %	10	10.86	14.24	14.72	16.63	28.50	29.74	
80 %	8.08	8.74	13.02	12.71	13.48	26.39	28.54	
90 %	6.64	6.95	11.97	11.14	10.73	23.3	26.03	

Table 2 – Comparison of IEF values for various filtering methods
ND
 	IEF	
	SMF	DMF	ATMF	UTMF	PA	
			=2	=4	=6			
10 %	57.92	128.77	22.75	39.97	50.04	52.13	50.54	
20 %	43.09	79.06	17.94	44.67	66.65	98.24	94.24	
30 %	19.74	29.23	13.06	33.16	59.92	132.84	131.82	
40 %	8.80	12.80	9.89	21.38	44.85	156.10	160.30	
50 %	4.79	6.65	7.53	12.99	27.62	166.07	181.93	
60 %	2.92	3.81	6.16	8.90	16.12	155.75	192.80	
70 %	2.00	2.44	5.30	5.97	9.21	141.68	198.51	
80 %	1.47	1.71	4.57	4.29	5.10	99.23	163.98	
90 %	1.18	1.27	4.04	3.34	3.05	59.11	100.05	

Table 3 – Comparison of PSNR and IEF values for Proposed algorithm 
														
Noise Density (ND)	Camera man	Blood cell.tif	Eight.tif	
	IEF	PSNR (in db)	IEF	PSNR( in dB)	 IEF	PSNR(in dB)	
10 %	15.42	26.97	33.79	30.66	36.67	30.00	
20 %	39.38	26.65	63.71	30.35	67.81	29.74	
30 %	41.38	26.50	82.77	29.72	101.13	29.54	
40 %	53.52	26.36	97.90	29.25	124.30	29.27	
50 %	61.30	25.94	98.91	28.31	143.01	28.86	
60 %	66.66	25.54	97.91	27.47	156.75	28.48	
70 %	65.70	25.09	82.04	26.06	164.05	28.03	
80 %	59.05	23.74	53.69	23.59	142.27	26.78	
90 %	40.06	21.55	25.57	19.90	87.51	24.17	

SMF - Standard Median Filter; 	          ATMF - Alpha-Trimmed Mean Filter; 	PA - Proposed Algorithm
DMF - Decision-based Median Filter; UTMF - Un-symmetric Trimmed Mean Filter; 

 Noise      Original Image     		Noisy Image           	SMF                    DMF				PA   
density
50%                      
90%                      		   30%                      
  70%     	               
   30%                   
   70%                    
					
Figure 4 Filtered output of Camera man , Blood cell and Eight . tif images

4	Conclusion
In this work, it can be observed that the performance of the proposed filter is superior to the existing filters. Even at very high noise densities (around 90%), the texture, details and edges are preserved effectively. The filtering method suggested can be further improved by using neural networks for further enhancing the outputs and also to remove other types of noise, such as random-valued impulse noise, mixed noise etc.
References:
 [1] E.Srinivasan and D.Ebenezer, “A New Class of Midpoint Type Non-linear Filters for Eliminating Short and Long Tailed Noise in Images, Third International Symposium on Wireless Personal Multimedia Communication, November 2000, Bangkok, Thailand.
[2] W.K.Pratt, Digital Image Processing (New York: Wiley 1978).
[3] I. Pitas and A.N.Venetsanopoulous, Non-linear Digital Filter Principles and Applications, (Boston: Kluwer Academic publishers, 1990).
[4] J.Astola and P.Kuosmanen, Fundamentals of Non-Linear Digital Filtering, BocRaton, CRC, 1997.
 [5] S.Manikandan, O.Uma Maheswari, D.Ebenazer, “An Adaptive Recursive Weighted Median Filter with Improved Performance in Impulsive Noisy Environment”, WSEAS Transactions on Electronics, Issue 3, Vol.1, July 2004.
[6] Ho-Ming Lin, “Median Filters with Adaptive Length”, IEEE Transactions on Circuits and Systems, Vol.35, No.6, June 1988.
[7] T.S. Huang, G.J.Yang, and G.Y.Tang, “Fast two dimensional Median Filtering algorithm“, IEEE Transactions on Acoustics, Speech and Signal Processing,1(1995), pp. 499-502.
[8] Pok,G.Jyh-Charn Liu “Decision based median filter improved by predictions”ICIP 99 (1999) proceedings vol 2 pp 410-413.