Median Filter

Neighborhood averaging can suppress isolated out-of-range noise, but the side effect is that it also blurs sudden changes such as line featuress, sharp edges, and other image details all corresponding to high spatial frequencies.

The median filter is an effective method that can, to some extent, distinguish out-of-range isolated noise from legitmate image features such as edges and lines. Specifically, the median filter replaces a pixel by the median, instead of the average, of all pixels in a neighborhood $w$

$$y[m,n]=median\{ x[i,j], (i,j) \in w \}$$ (16)

where $w$ represents a neighborhood defined by the user, centered around location $[m,n]$ in the image.

1D median filter:

Consider a 1x5 window sliding over a 1D array (either horizontal or vertical) of pixels. Assume the five pixels currently inside the windows are:

where the middle pixel with value 200 is an isolated out-of-range and is therefore likely to be noisy. The median of these five values can be found by sorting the values (in either ascending or descending order). The median is 110, the value in the middle:

The original pixel value 200 is replaced by the median 110.

Question: How do you get rid of noise in the form of horizontal line across the image using 1D median filter?

2D median filter:

The window of a 2D median filter can be of any central symmetric shape, a round disc, a square, a rectangle, or a cross. The pixel at the center will be replaced by the median of all pixel values inside the window.

Programming issues:

Sorting is necessary for finding the median of a set of values. There exit various sorting algorithm with complexity of $O(n\; log_2 n)$. However, in this case, as the number of pixels is quite limited, a simple sorting method with complexity $O(n^2)$ can be used. The code segment below sorts a 1-D array of $n$ elements into descending order:

  for (i=0; i<n-1; i++)
      for (j=i+1; j<n; j++)
          if ( bin[i] < \;bin[j] ) {
              w=bin[i]; bin[i]=bin[j]; bin[j]=w; 
          }

Example:

This figure shows the comparison of the smoothing results of a 1D signal (blue, 1st column) by an average filter (red, 2nd column) and by a median filter (red, 3rd column) both of size five. It is clear that the average filter always blurs edges without completely suppressing noise, while the median filter can preserve sharp edges while completely suppressing isolated out-of-range noise, based on the size of the feature. If its size is less than half of the filter size, indicating the pixel is likely to be an out-of-range noise, it is replace by the median. However, if the size is greater than half of the window, large enough to represent some legitimate feature in the image, it is preserved.