Median filter

Median filter
Example of 3 median filters of varying radii applied to the same noisy photograph. Implemented in Adobe Photoshop.

In signal processing, it is often desirable to be able to perform some kind of noise reduction on an image or signal. The median filter is a nonlinear digital filtering 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 on an image). Median filtering is very widely used in digital image processing because, under certain conditions, it preserves edges while removing noise (but see discussion below).

Contents

Algorithm description

The main idea of the median filter is to run through the signal entry by entry, replacing each entry with the median 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 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 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).
Use of a median filter to improve an image severely corrupted by defective pixels

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 algorithms can be much more efficient. Furthermore, some types of signals (very often the case for images) use whole number representations: in these cases, histogram 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. 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[1]. However, its performance is not that much better than Gaussian blur for high levels of noise, whereas, for speckle noise and salt and pepper noise (impulsive noise), it is particularly effective[2]. Because of this, median filtering is very widely used in digital image processing.

See also

References

  1. ^ E. Arias-Castro and D.L. Donoho, "Does median filtering truly preserve edges better than linear filtering?", Annals of Statistics, vol. 37, no. 3, pp. 1172–2009.
  2. ^ G.R. Arce, "Nonlinear Signal Processing: A Statistical Approach", Wiley:New Jersey, USA, 2005.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Median (disambiguation) — Median has different meanings in different contexts: Median, in statistics, a number that separates the lowest value half and the highest value half Median (geometry), in geometry, a line joining a vertex of a triangle to the midpoint of the… …   Wikipedia

  • Median — This article is about the statistical concept. For other uses, see Median (disambiguation). 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… …   Wikipedia

  • Filter (Bildverarbeitung) — Die (digitale) Bildverarbeitung nutzt die Mittel der Signalverarbeitung zur Aufbereitung dies sind Bildvorverarbeitungsroutinen wie Kalibrierung, Restauration, Rekonstruktion zur Speicherung und zur Darstellung von visuellen 2D bzw. 3D… …   Deutsch Wikipedia

  • Rank filter — is an image processing term. Typically, in digital filtering, pixels within a window are ranked by intensity values, and the center pixel is replaced with a new value. The new value is calculated as a function of the ranked pixels. Only the… …   Wikipedia

  • Nonlinear filter — A nonlinear filter is a signal processing device whose output is not a linear function of its input. Terminology concerning the filtering problem may refer to the time domain (state space) showing of the signal or to the frequency domain… …   Wikipedia

  • Moving average — For other uses, see Moving average (disambiguation). In statistics, a moving average, also called rolling average, rolling mean or running average, is a type of finite impulse response filter used to analyze a set of data points by creating a… …   Wikipedia

  • Noise reduction — For sound proofing, see soundproofing. For scientific aspects of noise reduction of machinery and products, see noise control. Noise reduction is the process of removing noise from a signal. All recording devices, both analogue or digital, have… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Diamond Cut Audio Restoration Tools — Diamond Cut Audio Resotration Tools Developer(s) Craig Maier and Rick Carlson of Diamond Cut Productions …   Wikipedia

  • Seismic Unix — is an open source seismic utilities package supported by the Center for Wave Phenomena (CWP) at the Colorado School of Mines (CSM).Infobox Software name = Seismic Unix caption = Velocity Analysis with SU developer = [http://www.cwp.mines.edu/… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”