FAST MEDIAN FILTERING

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:

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.

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 :

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:

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

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 }:

Fast median filter implementations:

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