A Fast and Improved Switching Median Filter with Adaptive Window for Impulse Noise Removal

A Fast and Improved Switching Median Filter with Adaptive Window for Impulse Noise Removal

T. Sandhya Kumari1, Ch. Anitha Bhavani2, K. Sreedhar3

1 Assoc. Professor, E.C.E. Dept., Vignans Institute of Engineering for Women, Visakhapatnam.

2 M.Tech, Chaitanya Engineering College, Visakhapatnam.

3 Asst. Professor, E.C.E. Dept., Chaitanya Engineering College, Visakhapatnam.

Abstract

A fast and improved switching median filter using an adaptive window is proposed for the removal of impulse noise. The proposed method uses an adaptive window for both noise detection and filtering. The probability of noise within an imposed window is calculated and depending on the noise density the window size is changed. Once the window size is determined, the pixels are classified and these detected pixels are filtered by using an adaptive window which further depends on the noise density calculated during noise detection. By making the window adaptive for both noise detection and filtering this method showed superior performance in terms of computational time without deteriorating the filtering performance in terms of subjective quality (visual quality) and objective quality (PSNR). The performance of the proposed method is demonstrated by the results obtained from simulations on various images.

Keywords: Adaptive window, Impulse Noise, Switching Median Filter.

1. Introduction

   Digital images are usually corrupted by noise during image acquisition, transmission and processing. The impulse noise is the one which severely degrades the image quality and causes a great loss of information details. Hence, it is required to eliminate such noise before subsequent processing such as edge detection, image segmentation and object recognition. Various filtering techniques have been proposed for the removal of this impulse noise. Initially, linear filters are implemented which are easier to design and implement. But, they produce serious image blurring. As a result, nonlinear filters have been proposed. The widely used filter under non-linear class is the median filter [1].Because of its simplicity in implementation, several modifications are made to the median filter which led to the development of various filters such as centre- weighted filter[2], weighted median filter[3].

   Conventional median filters when applied uniformly over the entire image degrade the image quality. This led to the development of switching median filters which incorporates noise detection mechanism prior to filtering. The switching median filter incorporating Boundary Discriminative Noise Detection (BDND) [4] is found to show superior performance especially for images corrupted with high noise densities. This method employs a 21×21 window for noise detection and classifies the pixel into a corrupted pixel or uncorrupted pixel based on the boundaries calculated during the detection process. However, the second iteration will be invoked to further examine whether the detected pixel is corrupted or uncorrupted based on a more confined local statistics using a 3×3 window. An adaptive window is used for filtering based on the number of uncorrupted pixels within the prescribed window. This method showed superior performance for images corrupted with high noise densities (up to 80%) when compared to other methods [5-8] in terms of peak signal-to-noise ratio (PSNR).

   Two modifications to the filtering step in BDND are implemented [9] which results in the improvement in PSNR compared to BDND. In this method, the filtering window is expanded based on the percentage of uncorrupted pixels that is expected to be found in the filtering window. Secondly, the new pixel value incorporates the spatial relation between the noisy pixel and the uncorrupted pixels in the window and also the relation between the values in a set of uncorrupted pixels and the new pixel value.

   However, the BDND and the modifications in BDND method described above uses two fixed window sizes (i.e.21×21 and 3×3) for noise detection. Selection of such a large window size increases the computational complexity and computation time. Thus, to reduce the computational complexity an adaptive window is proposed in this paper for noise detection without deteriorating the performance of filtering in terms of subjective (visual) and objective (PSNR) quality.

2. Noise Model

Pixels are randomly corrupted by two fixed extreme values, 0 and 255 (for 8-bit monochrome image), generated with the same probability. That is, for each image pixel at location (i, j) with intensity value si,j, the corresponding pixel of the noisy image will be xi,j , in which the Probability Density Function of xi,j is,

p

detection. However, the noise density is calculated for each time the window size is changed and compared. Thus, depending on the noise density, the window size is made adaptive.

The maximum detection window size (Wd Wd ) is limited to 21×21 and the minimum size is limited to 5×5.Once the window size is determined, all the pixels within the determined window centered on the considered pixel will

f (x)

,

2

1 p ,

f or x 0

f or x s

(1)

be grouped into three clusters; hence two boundaries b1 and b2 are determined. For each

i, j

p

pixel xi,j being considered if

0 xi, j

b1 , the

, f or x

2

255

pixel will be assigned to lower intensity level; otherwise to the medium intensity level for

where p is the noise density.

b1 x

i, j

b2 or to the higher intensity level for

Equation 1 shows that each pixel in an image has probability p/2 to be corrupted into either

b2 x

i, j

255 .Obviously, if the center pixel

a white dot (salt) or a black dot (pepper) and has a probability 1-p to be noise-free pixels or clean pixels. The binomial distribution is the discrete probability distribution of the number of successes in a sequence of n independent yes/no experiments, each of which yields success with probability p. Thus, in a window, if n represents the number of trials i.e. total number of pixels and r represents the number of success i.e. pixels corrupted with noise having a probability p and probability 1-p for noise free pixels, then the Probability Density Function f(x) of an image corrupted with impulse noise can also be expressed as,

being considered falls onto the middle cluster it

is treated as uncorrupted, since its intensity value is neither relatively low nor relatively high. Otherwise, it is very likely that the pixel has been corrupted by impulse noise.

This algorithm is applied to each pixel of the noisy image in order to identify whether it is uncorrupted or corrupted. After such an application to the entire image, a two- dimensional binary decision map is formed at the end of the adaptive noise detection stage, with 0s indicating the positions of uncorrupted pixels, and 1s for those corrupted ones.

f (x)

n pr (1

r

p)n r

(2)

In summary the steps of the proposed method are:

1. Impose a window Wd Wd of size

   In this proposed method, the noise density within the placed window size is calculated by using the equation for probability expressed as the ratio of number of impulses (NA) to the total number of pixels (N), mathematically expressed as

   f (x) = NA/N (3)

   11×11, which is centered on the current pixel.

2. Calculate the noise density within this window using the Probability Density Function equation given in (3).

3. If the noise density is greater than the threshold, window Wd Wd size is

   1. Adaptive Noise Detection

      In order to determine whether the pixel is corrupted or not, an 11×11 window is imposed centered around the current pixel to be detected. The noise density within the imposed window is calculated using the equation (3). If the calculated noise density is in between 30% and 50% then the window size is increased by one pixel outwards on all the four sides and if the noise density is greater than 50% then the window size is decreased by one pixel inwards on all the four sides. If the noise density is less than 30% then the same window size is used for

      reduced by one pixel inward in all the four sides of the window, Else if the density is lesser than the threshold; the window Wd Wd size is extended by one pixel outward in all the four sides of the window. Thus, the window size is made adaptive based on the noise density within the window.

   2. Sort the pixels in the determined window according to the ascending order and find the median, med, of the sorted vector Vo.

   3. Compute the intensity difference between each pair of adjacent pixels across the sorted vector Vo and obtain the difference vector Vd.

   4. For the pixel intensities between 0 and med in the Vo, find the maximum intensity difference in the Vd of the same range and mark its corresponding pixel in the Vo as the boundary b1 .

   5. Likewise, the boundary is identified for pixel intensities between med and 255; three clusters are, thus, formed.

   6. If the pixel belongs to the middle cluster, it is classified as uncorrupted pixel, and the classification process stops; else, the second iteration will be invoked.

   7. Impose a 3×3 window, being centered on the concerned pixel and repeat Steps 4)7).

   8. If the pixel under consideration belongs to the middle cluster, it is classified as uncorrupted pixel; otherwise, corrupted.

4. Adaptive Noise Filtering

   The major contributions of making the entire switching median filter being noise- adaptive come from the impulse-noise detection as described in the previous section. In order to determine the window size of the filtering window, the limit of the maximum window size requires being determined first. Based on the binary decision map, no filtering is applied to those uncorrupted pixels, while the SM filter with an adaptively determined window size is applied to each corrupted one.

   The maximum window size is limited to 7×7 (instead of 11×11 as suggested in [4]) in order to avoid severe blurring of image details at high noise density cases (i.e., (p>50%)). In BDND, starting with WF =3, the filtering window iteratively extends outward by one

   improved BDND algorithm by comparing the number of uncorrupted pixels Nc is less than

   ½(1-P) N, The term (1-P) basically is the percentage of uncorrupted pixels that is expected to be found in the filtering window. Incorporating this term in the condition makes it adaptive to the noise density. In other words, when the noise density increases, the condition is loosened since the expected number of uncorrupted pixels decreases.

   The second modification made in modified BDND is to consider the spatial relation between the noisy pixel and the uncorrupted pixels in the window and the relation between the values in Vu and the Yij. Thus the value of pixel to be replaced is modified as:

   (4)

   Where d(k) is a function of the spatial distance between the pixel of the kth value in Vu and the noisy pixel at location (i,j)

   (5)

   with S(k) and T(k) are the row and column indices of that pixel, and

   (6)

   The distance is computed using the City- block distance definition to reduce computations. Since these modifications increased the objective quality in terms of signal-to noise ratio in the filtered image the same modifications were considered for this proposed method.

5. Simulation Results

The performance evaluation of the filtering operation is quantified by the PSNR calculated using the following standard formula:

pixel in all the four sides of the window, provided that the number of uncorrupted pixels (denoted by NC) is less than half of the total number of pixels (denoted by (Sin 1 2[WF WF ]) ) within the filtering

PSNR

MSE

10log10

1 M

2552

db

MSE

N 2

( yi, j si, j )

(7)

(8)

window. But, it is hard to obtain this condition with small windows in cases of high noise densities. The direct impact on increasing the window size is the possible loss of correlation between the pixel values inside the filtering window. This directly affects the value that replaces the noisy pixel, which may lead to blurring. Thus this condition is modified in

MN i 1 j 1

Where M and N are the total number of pixels in the horizontal and the vertical dimensions of the image; si,j and yi,j denote the original and the filtered image pixels, respectively.

Fig.1 First row shows three original test images; (first) Lena, (second) Cameraman and

(third) Baboon and Second row presents their corresponding noisy images with 80% impulse noise corruption.

Fig.2 First row presents filtered images using proposed method. Second row presents the filtered image using modified BDND.

Simulations were carried out using several monochrome images, from which. Lena, Cameraman and Baboon is chosen for demonstration in Fig.1.The first row shows the original image and their corrupted versions with 80% noise density are shown in the second row. The filtering performance of the modified BDND method and the proposed switching median filter for the test images are shown in Fig.2 for comparison. The visual quality of the filtered images using the proposed method is observed to be free from impulse noise and does not deteriorate the visual quality of modified BDND. The PSNR performance comparison is graphically illustrated in Fig. 3. It is observed from the graphs that the PSNR value for modified BDND is superior to that of BDND.

This value is taken as reference for comparing the PSNR values of the proposed method and is observed that its performance is also improved compared to BDND and is almost same as that to modified BDND.Fig.4 shows the comparison of the computational time of the proposed method. It is observed that the proposed method shows excellent performance in terms of computational complexity. The computational time required for the proposed method is less (i.e. approximately half) than that required for BDND and modified BDND method. Thus this method, decreases the computational time by making the window size adaptive and increase the speed of performance without deteriorating the PSNR and visual quality of the existing BDND and modified BDND methods.

Fig. 3 PSNR performance comparison using the proposed method and the Modified BDND method on (a) Lena (b) Cameraman and (c) Baboon corrupted by various noise densities (10%-80%)

Fig. 4 Computational time comparison using the proposed method and the Modified BDND method on (a) Lena (b) Cameraman and (c) Baboon corrupted by various noise densities (10%-80%)

Conclusions

Restoration of images corrupted with impulse noise is an interesting problem. Several methods exist for the removal of impulse noise. Out of the several existing methods the BDND method is found to perform well in terms of subjective quality and objective quality. However, two modifications in the filtering techniques is found to further increase the signal-to noise ratio in the modified BDND method. In this thesis, a new scheme of impulse detection and filtering is proposed. The proposed method uses an adaptive window for both noise detection and filtering. This method can not only get better image quality, but also have shorter computation time. The computation time reduces to almost half the timerequired by Modified BDND method. The proposed structure shows stable performance across a wide range of noise densities varying from 10% – 80%. Another tremendous advantage of this algorithm is fairly simple to implement for real-time image applications

REFERENCES

1. I.Pitas and A. N. Venetsanopoulos, Order Statistics In Digital Image Processing, Proc. IEEE, vol. 80,no 12,pp. 1893-1921, Dec. 1992.

2. S.J.Ko and Y.H.Lee, Center-Weighted Median Filters and Their Applications to Image Enhancement, IEEE Tran. Circuits and syst., vol.38, pp.984-993, Sept.1991.

3. D.R.K. Brownrigg, The Weighted Median Filter, Comm. ACM, vol. 27, pp. 807-818, August 1984.

4. Pei-Eng Ng and Kai-Kuang Ma, A Switching Median Filter With Boundary Discriminative Noise Detection For Extremely Corrupted Images IEEE Trans.Image Processing, vol.15,no.6, pp. 1506-1516, June 2006.

5. H.L.Eng and K.K.Ma, Noise Adaptive Soft- Switching Median Filter, IEEE Trans. Image Process., vol.10, no.2, pp.242-251, Feb.2001.

6. S.Zhang and M.A.Karim, A New Impulse Detector For Switching Median Filters, IEEE Signal Proces.Lett., vol.9, no. 4, pp. 360-363, Nov. 2002.

7. Z.Wang and D.Zhang, Progressive Switching Median Filter for the Removal of Impulse Noise from Highly Corrupted Images, IEEE Trans. Circuits Syt.II, vol. 46, no.1, pp.78-80, Jan.1999.

8. H.Hwang and R.A. Haddad, Adaptive Median Filters: New Algorithms and Results, IEEE Trans. Image Process., vol.4, no.4, pp.499- 502,Ap.1995.

9. Iyad F. Jafar and Rami Al Namneh Improving the filtering performance of the

   BDND algorithm in impulse noise removal, 2012-9thInternational Multi-conference on Signals, Systems and Devices.

10. I.Pitas and A. N. Venetsanopoulos, Nonlinear Digital Filters: Principles and Applications, Boston, Kluwer, 1990.

11. W.K.Pratt, Digital Image Processing, 3rd Ed. New York: Wiley, 2001.

12. S.G.Tyan, Median Filtering: Deterministic Properties, in Two-Dimensional Signal Processing- II, T.S.Huang, Ed. NewYork: Springer Verlag, 1981.

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Vol. 1 Issue 10, December- 2012