Median Filter – Edge Preserving Filter


The Median filter is a nonlinear noise reduction filter that is widely used in image processing. It is very effective in cases of salt and paper noise (impulsive noise) and speckle noise, but in cases of high noise levels it’s performance become comparable with Gaussian blur filtering. The main advantage of this filter is that it can blur and reduce the noise levels while retains edges. This feature of median filter makes it suitable as a preprocessing step for further image processing tasks such as edge detection/extraction. An important note is that median filter has the effect to round existing corners and is not suitable for corner detection.


How Median Filter works?

The Median filter is working using a sliding window iterating through each signal entry one by one. At each point numerically sort the list of adjacent neighbors and then replace central value with the middle one from the list. The classical algorithm uses sorting, which is not much efficient and may lead to bigger execution delay. Thus in attempts for optimization there are several different techniques for finding the middle value.

How to find the median value?

  • Array sorting – this is a classical algorithm where we sort the values below the median kernel and as a result we use the value in the middle
  • Selection algorithm – it is acceptable to use partial sorting or other selection method, since the goal is simply to find the middle value.
  • Histogram medians – at window movement we can update histogram with pixel changes and use it further to resolve the median value

The following picture displays an example of 3×3 sliding window and how the algorithm process current pixel.

median filter 3x3 windowReplacing current pixel from 3×3 filter window

 

The image above show how the sliding mask represents the matrix as 1D array of pixel values. To extract the middle value the algorithm sorts the neighbors array . Then the middle value replaces the central pixel.

 


Median Filter source code


/*
	Created by FIVEKO.com 2017
	
	The source code is designed and developed for educational purposes only. 
	It is designed for no other purpose and neither the authors nor their institutions 
	accept any liability concerning its use.
*/

"use strict"; 

function median(pixels, size, colors) {
	var d = pixels.data;
	var buff = new pixels.data.constructor(new ArrayBuffer(pixels.data.length));
	var w = pixels.width;
	var h = pixels.height;
	const bpr = w*4; // Bytes per row
	
	if (size < 3) return;
	
	const ms = Math.floor(size / 2);
	const mc = Math.floor((size*size) / 2);
	
	// Find the middle value by histogram traversal
	function getMiddle(h, n){
		for (var count = h[0], i = 1; i < 255; i++, count += h[i]){ if (count >= n){
				return i;
			}
		}
		return 255;
	}
	colors = colors || 3;
	for (var i, j, c = 0; c < colors; c++){
		var srcIt, dstIt, l;
		for (i = ms; i < h - ms; i++) {
			var hist = new Uint16Array(256);
			
			for (var ii = (i - ms)*bpr; ii <= (i + ms)*bpr; ii+=bpr){
				for (var jj = c; jj < (ms*2)*4 + c; jj+=4){
					hist[d[ii + jj]]++;
				}
			}

			for (j = ms, dstIt = i*bpr + j*4 + c; j < w - ms; j++, dstIt+=4){
				const offset = (i - ms)*bpr + c;
				// Add rigtmost values to the histogram
				for (srcIt = offset + (j + ms)*4, 
					l = srcIt + bpr*size; srcIt < l; srcIt+=bpr){
					hist[d[srcIt]]++;
				}
				
				buff[dstIt] = getMiddle(hist, mc);
				// Remove leftmost values to the histogram
				for (srcIt = offset + (j - ms)*4, 
					l = srcIt + bpr*size; srcIt < l; srcIt+=bpr){ hist[d[srcIt]]--; } } } } if (colors > 1){
		for (var i = 3; i < l; i+=4){
			buff[i] = 255;
		}
	} else {
		for (var i = 3; i < l; i+=4){
			buff[i] = 255;
			buff[i - 2] = buff[i - 1] = buff[i - 3];
		}
	}
	
	pixels.data.set(buff);

	return pixels;
}

Visit FivekoGFX on GitHub for more image processing examples


Median Filter Demo

Kernel size: 3

Releted Articles


References