In signal processing

Signal processing

Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...

, it is often desirable to be able to perform some kind of noise reduction

Noise reduction

Noise reduction is the process of removing noise from a signal.All recording devices, both analogue or digital, have traits which make them susceptible to noise...

 on an image or signal. The median filter is a nonlinear digital filtering

Digital filter

In electronics, computer science and mathematics, a digital filter is a system that performs mathematical operations on a sampled, discrete-time signal to reduce or enhance certain aspects of that signal. This is in contrast to the other major type of electronic filter, the analog filter, which is...

 technique, often used to remove noise. Such noise reduction is a typical pre-processing step to improve the results of later processing (for example, edge detection

Edge detection

Edge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...

 on an image). Median filtering is very widely used in digital image processing

Image processing

In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...

 because, under certain conditions, it preserves edges while removing noise (but see discussion below).

Algorithm description

The main idea of the median filter is to run through the signal entry by entry, replacing each entry with the median

Median

In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...

 of neighboring entries. The pattern of neighbors is called the "window", which slides, entry by entry, over the entire signal. For 1D signals, the most obvious window is just the first few preceding and following entries, whereas for 2D (or higher-dimensional) signals such as images, more complex window patterns are possible (such as "box" or "cross" patterns). Note that if the window has an odd number of entries, then the median

Median

In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...

 is simple to define: it is just the middle value after all the entries in the window are sorted numerically. For an even number of entries, there is more than one possible median, see median

Median

In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...

 for more details.

Worked 1D example

To demonstrate, using a window size of three with one entry immediately preceding and following each entry, a median filter will be applied to the following simple 1D signal:

x = [2 80 6 3]


So, the median filtered output signal y will be:

y[1] = Median[2 2 80] = 2

y[2] = Median[2 80 6] = Median[2 6 80] = 6

y[3] = Median[80 6 3] = Median[3 6 80] = 6

y[4] = Median[6 3 3] = Median[3 3 6] = 3


i.e. y = [2 6 6 3].

Boundary issues

Note that, in the example above, because there is no entry preceding the first value, the first value is repeated, as with the last value, to obtain enough entries to fill the window. This is one way of handling missing window entries at the boundaries of the signal, but there are other schemes that have different properties that might be preferred in particular circumstances:

• Avoid processing the boundaries, with or without cropping the signal or image boundary afterwards,
• Fetching entries from other places in the signal. With images for example, entries from the far horizontal or vertical boundary might be selected,
• Shrinking the window near the boundaries, so that every window is full.

2D median filter pseudo code

Code for a simple 2D median filter algorithm might look like this:

allocate outputPixelValue[image width][image height]
edgex := (window width / 2) rounded down
edgey := (window height / 2) rounded down
for x from edgex to image width - edgex
for y from edgey to image height - edgey
allocate colorArray[window width][window height]
for fx from 0 to window width
for fy from 0 to window height
colorArray[fx][fy] := inputPixelValue[x + fx - edgex][y + fy - edgey]
sort all entries in colorArray[][]
outputPixelValue[x][y] := colorArray[window width / 2][window height / 2]

Note that this algorithm:

• Processes one color channel only,
• Takes the "not processing boundaries" approach (see above discussion about boundary issues).

Algorithm implementation issues

Typically, by far the majority of the computational effort and time is spent on calculating the median of each window. Because the filter must process every entry in the signal, for large signals such as images, the efficiency of this median calculation is a critical factor in determining how fast the algorithm can run. The "vanilla" implementation described above sorts every entry in the window to find the median, however since only the middle value in a list of numbers is required, selection algorithm

Selection algorithm

In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list . This includes the cases of finding the minimum, maximum, and median elements. There are O, worst-case linear time, selection algorithms...

s can be much more efficient. Furthermore, some types of signals (very often the case for images) use whole number representations: in these cases, histogram

Histogram

In statistics, a histogram is a graphical representation showing a visual impression of the distribution of data. It is an estimate of the probability distribution of a continuous variable and was first introduced by Karl Pearson...

 medians can be far more efficient because it is simple to update the histogram from window to window, and finding the median of a histogram is not particularly onerous.

Edge preservation properties

Median filtering is one kind of smoothing technique, as is linear Gaussian filtering

Gaussian blur

A Gaussian blur is the result of blurring an image by a Gaussian function. It is a widely used effect in graphics software, typically to reduce image noise and reduce detail...

. All smoothing techniques are effective at removing noise in smooth patches or smooth regions of a signal, but adversely affect edges. Often though, at the same time as reducing the noise in a signal, it is important to preserve the edges. Edges are of critical importance to the visual appearance of images, for example. For small to moderate levels of (Gaussian) noise, the median filter is demonstrably better than Gaussian blur at removing noise whilst preserving edges for a given, fixed window size. However, its performance is not that much better than Gaussian blur for high levels of noise, whereas, for speckle noise

Speckle noise

Speckle noise is a granular noise that inherently exists in and degrades the quality of the active radar and synthetic aperture radar images....

 and salt and pepper noise

Salt and pepper noise

Salt and pepper noise is a form of noise typically seen on images. It represents itself as randomly occurring white and black pixels. An effective noise reduction method for this type of noise involves the usage of a median filter, morphological filter or a contra harmonic mean filter.Salt and...

 (impulsive noise), it is particularly effective. Because of this, median filtering is very widely used in digital image processing

Image processing

In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...

.

See also

• Image noise
  Image noise
  Image noise is random variation of brightness or color information in images, and is usually an aspect of electronic noise. It can be produced by the sensor and circuitry of a scanner or digital camera...
  
  
• Median
  Median
  In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...
  
  
• Signal Processing
  Signal processing
  Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
  
  
• Digital Image Processing
  Digital image processing
  Digital image processing is the use of computer algorithms to perform image processing on digital images. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing...
  
  
• Gaussian blur
  Gaussian blur
  A Gaussian blur is the result of blurring an image by a Gaussian function. It is a widely used effect in graphics software, typically to reduce image noise and reduce detail...
  
  

External links

• Fast Matlab 1D median filter implementation
• Mathematica MedianFilter function
• Median filter
• Fast 2D median filter
• Fastest possible 2D implementation (GPL license)
• Implementation written in different programming languages (on Rosetta Code
  Rosetta Code
  Rosetta Code is a wiki-based programming chrestomathy website with solutions to various programming problems in many different programming languages. It was created in 2007 by Mike Mol. Rosetta Code includes 450 programming tasks, and covers 351 programming languages...
  
  )
• Dr Dobbs article