//
// Implementation of 'Median Filter'
//
// The following code does Median Filtering by passing 
// small arrays (squares) to the quick sort algorithm.
// The pixel is replaced by the median of the array.
//


public class MedianFilter extends Object
{
  public MedianFilter() {};
  public int[] filterPixels(int inPixels[], int windowSize,
                            int width, int height)
  {
    int outPixels[] = new int[inPixels.length];
    int offset = (windowSize-1)/2;

    int pixel;
    
    // array[] is the square that is passed to the quicksort function
    
    int array[] = new int[windowSize*windowSize];
    for (int x = offset; x < width - offset; x++)
    {
      for (int y = offset; y < height - offset; y++)
      {
        pixel = 0;
        for (int i = x - offset; i <= x + offset; i++)
        {
          for (int j = y - offset; j <= y + offset; j++)
          {
            array[pixel] = inPixels[j*width+i];
            pixel++;
          }
        }
        sort(array, 0, array.length - 1);
        outPixels[y*width+x] = array[windowSize*windowSize/2];
      }
    }

    return outPixels;
  }

void sort(int array[], int lo, int up)
{
	int i, j;
    	int tempr;

	while ( up>lo )
	{
		i = lo;
        	j = up;
        	tempr = array[lo];
        	/*** Split file in two ***/
        	while ( i<j ) 
		{
			for ( ; array[j] > tempr; j-- );
			for ( array[i]=array[j]; i<j && array[i]<=tempr; i++ );
			array[j] = array[i];
		}
        	array[i] = tempr;
        
		/*** Sort recursively, the smallest first ***/
        	if ( i-lo < up-i )
		{
			sort(array,lo,i-1);  
			lo = i+1; 
        	}
		else    
		{
			sort(array,i+1,up);
			up = i-1;
		}
	}
   }
}