FAST MEDIAN FILTERING WITH IMPLEMENTATIONS IN C/C++/C#/VB.NET/Delphi

The simplest way to know what is median filter and how it acts - is to undertsand how median of a sequence of numbers is calculated. Suppose whe have the sequence of 9 numbers: A = { 3, -1, 9, -1, 0, 5, 4, 3, 28 }. To calculate median of sequence A we need to:
1) Order all numbers of sequence in ascending (or descending) order:
here we get A* = { -1, -1, 0, 3, 3, 4, 5, 9, 28 }

2) Find the element in the middle of sequence A*. In this case it is 3. So, the result is: median of sequence A is 3.

Please note that number of elements in A is odd, so we had no problems to get element strictly in the middle of ordered sequence. if number of elements is even we will take two elements from the middle and get their mean value.

Now, more formally:To get median of numeric sequence A which contains N elements we have to: 1) Order sequence A. Lets note ordered sequence as A* . 2) IF N is odd then median(A) = A*N/2 else median(A) = (A*(N/2)-1+A*(N/2)+1))/2

More examples:

Sequence
Median
{0, -33, 8, 7, -1}
0
{0, -33, 8, 7, -1, 4}
2
{3, -3, 5, 2 }
-0.5

Now let introduce median filtering . Filtering, basically, is an operation that transforms one set to another. Here we deal with 1D arrays, so

Now, lets Generally, filtering is operation that transforms one sequence of numbers to another, preserving number of elements but eliminating (filtering out) some "bad" elements - eliminating here means that "bad" values are replaced with "good" ones. Lets start as usual from example:
We have numerical sequence:
A={
0, 0,-1, 0, 1, 0, 0, -1, 0, 0, 6, 5, 4, 5, 5, 6, 3, 5, 4, 5, 5 }.
For each element ai of this sequence take elements from its neighbourhood (elements that surround current), and calculate its median using above considerations. Add this number to output sequence.
Here we meet the word "neighbourhood". Before applying median filter to sequence we need to define the size of neighbourhood. Usually sizes of neighbourhood are odd and start from 3 (current element and two its neighbours - left and right). For the first and last elements we we are unable to get the first and the last neighbours accordingly. To overcome this situation we will take twice element what neighbourhood we are talking about. For the first element we have: {0, 0, -1, ..... - so we get neighbourhood: { 0, 0, 0 } - first element taken twice. For the last: ....., 4, 5, 5} - so we take { 5, 5, 5 }. The way in which we define the neighbourhoods for boundary elements depends generally on the nature of sequence that is filtered.

Now, assuming the size of neighbourhood is 3 we perform median filtering of input sequence A.

Original
Neighbourhood
Result
median of neighbourhood

0
{0, 0, 0}

0
0
{0, 0, -1}
0
-1
{ 0, -1, 0}
0
0
{-1, 0, 1}
0
1
{0, 1, 0}
0
0
{1, 0, 0}
0
0
{0, 0,-1}
0
-1
{0, -1, 0}
0
0
{-1, 0, 0)
0
0
{0, 0, 6}
0
6
{0, 6, 5}
5
5
{6, 5, 4}
5
4
{5, 4, 5}
5
5
{4, 5, 5}
5
5
{5, 5, 6}
5
6
{5, 6, 3}
5
3
{6, 3, 5}
5
5
{3, 5, 4}
4
4
{5, 4, 5}
5
5
{4, 5, 5}
5
5
{5, 5, 5}
5

As a result we have output sequence: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5 }. The difference between two sequences is seen better from common table. The first row :

Original sequence
0 0 -1 0 1 0 0 -1 0 0 6 5 4 5 5 6 3 5 4 5 5
Filtered sequence 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 4 5 5 5

We see that filtered sequence doesn' contain outliers, but preserves sharp transition from 0 to 5. That is the most attractive feature of median filter - elimination of isolated outliers and preserving of "common shape".


The next table contains one more row - result of median filter with larger neighbourhood - 5 elements:

Original sequence
0 0 -1 0 1 0 0 -1 0 0 6 5 4 5 5 6 3 5 4 5 5
Filtered sequence* 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 4 5 5 5
Filtered sequence** 0 0 0 0 0 0 0 0 0 0 4 5 5 5 5 5 5 5 5 5 5

Here you may download 1D median filtering illustrating AVI video clip.

In 1981 T.Huang proposed fast 2D median filtering algorithm for gray scale images. The main idea of algorithm is to use histogram instead using sort. For example, we have array of N elements taking values from 0 to 255. We put all elements of array to histogram. Now, sum all histogram elements beginning from 0 till sum reaches the middle N/2. This value will give us median of array. I'm not going to discuss here all details of Huang algorithm. You can find them in Web. Just google: "Huang median filter" or something like that.
Illustration how median filter effectively removes "salt" like noise from images
:

 
Original noised image
The same image after applying median filter
  Original image Processed image
     

Since original Huang algorithm deals with 256 gray level images we can use arrays to keep histograms. What should we do in case of integer-, real-valued or some custom type-valued images? Obviously we can't use arrays in such cases. To overcome this problem we can use binary tree based histograms. Each node of tree-based histogram contains input value as key and integer counter.
For example, have a look at histogram for input array: { 1, -1, 0, 1, 5, 3, 8 }:

 

tree-based histogram

Fast median filter implementations:

Algorithm
Compiler
Source code

Fast 1D median filter implemented with binary tree based histogram

Borland C++ Compiler 5.5 (updated - performance comparison between simple and fast filters)
Download

Fast 1D median filter implemented with binary tree based histogram

Visual C++ 2008 Download
Fast 1D median filter implemented with binary tree based histogram
aCC (HP-UX) Download
Fast 1D median filter implemented with binary tree based histogram
cxx (OpenVMS)

Download

Fast 2D median filter for 256 gray-level images. Array based histogram. Borland C++ Compiler 5.5 Contains fast median filter implementation and 'direct' median filter implementations. Download
Fast 2D median filter implemented with binary tree based histogram Borland C++ Compiler 5.5 Contains fast median filter implementation and 'direct' median filter implementations. Download
Fast 2D median filter implementation for 256 gray-level images based on T.Huang algorithm VB.NET Console application that compares filtered images processed by fast median filter and simple median filter (based on median definition) Download VB.NET project
Fast 2D median filter implementation for 256 gray-level images based on T.Huang algorithm VB.NET GUI application that illustrates image median filtering.
Screenshot of original image with added noise
Screenshot of image processed by fast median filter
Download VB.NET project
Fast 2D median filter implementation for 256 gray-level images based on T.Huang algorithm C#.NET Console application that compares filtered images processed by fast median filter and simple median filter (based on median definition) Download C#.NET project
Fast 2D median filter implementation for 256 gray-level images based on T.Huang algorithm C#.NET GUI application that illustrates image median filtering.
Download C#.NET project
Fast 2D median filter implementation for color images. Uses fast median filter for each color (rgb) component. C#.NET GUI application that illustrates color image median filtering.
Download C#.NET project
Fast 2D median filter implementation for 256 grayscale images. Borland Delphi GUI application that illustrates color image median filtering.
Download source file

Download median filter implementations and start using one of the most powerful noise removing tools!