May 31 2007

Effecient Sorting Algorithm For Applying Median Filter to a Image

Published by at 7:09 am under Algorithms,C Programming

Normally median filters are applied to remove speckle noises in an Image. There are many variations of Median Filters but all these variations are for choosing the kernel dimensions and shape. What i mean by kernel is that it could be a 3X3 kernel or 5X4 kernel or a radius 3 kernel.

A 3×3 kernal will have 9 elements to sort

A 5X5 kernal will have 25 elements to sort

A radius 3 kernel will have 29 elements to be sorted before you can pick the median.

Bottom line is you choose any variations of kernals, it boils down to effeciency of sorting. I have come up a one such algorithm that i think is very effecient for Median Filtering

Assumptions:

  1. RGB Planar data. The bit depth Per pixel is 8 bits.
  2. Median Filter Kernel size is Odd Number. Like 5, 9, 25 etc
  3. The following code is PseuodCode and good for one dimensional data.

A pseudo Code implementation of the Algorithm is shown below:

Global First_Element

Global Median_Value

Global PointOfInterest

Global Array [ 256 ] /* This assumes a bitDepth of 8. That is a Red Pixel is 8 bits in length.

Int FirstTimeSort ( char * sourceAddr, int NumberOfElementsToBeSorted )

{

int i , j;

// Reset all elements to 0

ZERO( Array)

for ( i = 0; i < NumberOfElementsToBeSorted; i++ )

{

/* The value in the sourceAddr must be between 0 and 255 */

/* We use values in SourceAddr to index into the Bucket. Then we increment to keep track of the repitations of the same number. If any value in sourceAddr is unique, then the Bucket count for that unique will be 1. */

Bucket[ sourceAddr[i] ] = Bucket[ sourceAddr[i] ] + 1 ;

/* At this point the values are sorted */

}

/* Now find the median*/

median = NumberOfElementsToBeSorted/2 +1

for ( i = 0, j=0; i < 256, j >= median, i++ )

{

j += Bucket[i];

Median_Value = i;

}

First_Element = sourceAddr[0];

PointOfInterest = sourceAddr[median -1 ]; /* C arrays are 0 indexed. Hence if you want to access the third element, you have to index array[2] */

return Median_Value;

}

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Int SubsequentSort ( char * sourceAddr, int NumberOfElementsToBeSorted )

{

int i , j;

Bucket[First_Element] -= 1;

Bucket[Median_Value] += 1;

Bucket[PointOfInterest ] -= 1;

Bucket[sourceAddr[NumberOfElementsToBeSorted-1]] += 1;

/* At this we have sorted all our values */

/* Now find the median*/

median = NumberOfElementsToBeSorted/2 +1

for ( i = 0, j=0; i < 256, j >= median, i++ )

{

j += Bucket[i];

Median_Value = i;

}

First_Element = sourceAddr[0];

PointOfInterest = sourceAddr[median -1 ];

return Median_Value;

}

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

The following code snippet shows how to use the above routines.

int main ()

{

char * source = 0;

char * PointOfInterest = 0;

int KernelSize;

source = SourceOfBuffer /* Point to the source of Buffer that holds the image to which we need to apply median filter */

PointOfInttest = source+2; /* Applying 1 dimensional Median filter. There is no difference for 2 dimensional kernel as well. */

KernelSize = 5; /* So the median will always be he third element of the sorted array */

/* Do a first tme sort */

*PointOfIntrest = FirstTimeSort ( source, KernelSize );

/* Now do subsequent sorts */

PointOfIntrest += 1;

source += 1;

Until ( END OF ( source ) )

{

*PointOfIntrest = SubsequentSort(source, KernelSize );

PointOfIntrest += 1;

source += 1;

}

Comments Off on Effecient Sorting Algorithm For Applying Median Filter to a Image

Comments are closed at this time.