Two dimensional array median filtering

Question

I'm trying to write code that implements median filtering on a two-dimensional array. Here's an image to illustrate:

The program starts at the beginning of the array. The maximum array size is 100. I know that I can use an array like:

int a[100][100];

to store the input, and that I can iterate over a part of this array using two for loops like this:

for(i=0;i<size_filter;i++)
for(j=0;j<size_filter;j++)
      temp[i][j]=a[i][j]     // not so sure

But how can I make this code loop over the neighbors of every element in the array, calculate their median, and replace the center element with the median?

---

For some examples of what I'm trying to do, let's say that the input is a 5x5 matrix, so the input size is 5. And I want to run a 3x3 median filter on it, i.e. each element should be replaced by the median of the 3x3 elements surrounding it.

The program starts at the corner index (0,0). For this index, it scans the 3x3 region surrounding it (of which only four indexes actually lie within the input array), which contains the values 0, 0, 1, and 0. The median of these values is 0, so that's what the code should output for this array index.

In the picture below, the number in bold italics is the center cell, and the plain bold numbers are its neighbors within the 3x3 region surrounding it:

0 0 0 0 0
1 0 0 1 0
1 1 0 0 0
0 1 1 0 0
0 0 0 0 0 

Here's another example, this time with the center index (0,1):

0 0 0 0 0
1 0 0 1 0
1 1 0 0 0
0 1 1 0 0
0 0 0 0 0 

This time, the elements in the 3x3 region (excluding those outside the input array) have the values 0, 0, 0, 1, 0, and 0, and again, their median is therefore 0.

Here's yet another example, this time from the middle of the input, at center index (3,2):

0 0 0 0 0
1 0 0 1 0
1 1 0 0 0
0 1 1 0 0
0 0 0 0 0 

This time, the elements within the 3x3 region have the values 1, 0, 0, 1, 1, 0, 0, 1, and 1, and their median in therefore 1.

Final example:

<size of array><size filter> <data>
8
3
0 0 0 0 0 0 0 0
0 5 0 0 6 0 0 0
0 0 0 0 0 7 0 0
0 0 0 0 5 0 0 0
0 0 0 5 6 0 0 0
0 0 8 5 5 0 0 0
0 0 0 7 0 0 9 0
0 0 0 0 0 0 0 0

Output:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 5 5 0 0 0
0 0 0 5 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Answer 1

It looks like you're trying to implement a two-dimensional median filter. The straightforward way to implement such a filter is to have four nested loops: two outer loops over the x and y coordinates of the whole image, and two inner loops over the neighborhood of the center pixel.

It's perhaps easier to describe this in code than in text, so here's some Python-esque pseudocode to illustrate:

# assumptions:
#  * image is a height x width array containing source pixel values
#  * filtered is a height x width array to store result pixel values in
#  * size is an odd number giving the diameter of the filter region

radius = (size - 1) / 2   # size = 3 -> radius = 1

for y from 0 to height-1:
    top = max(y - radius, 0)
    bottom = min(y + radius, height-1)

    for x from 0 to width-1:
        left = max(x - radius, 0)
        right = min(x + radius, width-1) 
        values = new list

        for v from top to bottom:
            for u from left to right:
                add image[v][u] to values

        filtered[y][x] = median(values)

Translating this code into C is left as an exercise.

It's also possible to optimize this code by noting that the neighborhoods of adjacent array cells overlap significantly, so that the values of those neighboring cells can be reused across successive iterations of the outer loops. Since the performance of this algorithm on modern CPUs is essentially limited by RAM access latency, such reuse can provide a significant speedup, especially for large filter sizes.

Answer 2

this:

for(i=0;i<size_filter;i++)
for(j=0;j<size_filter;j++)
      temp[i][j]=a[i][j];

is a good starting point. You just iterating over every pixel of your input array, determine the median of the neighborhood and write it to an output array. So instead of temp[i][j]=a[i][j]; you need some WhatEverType calcMedianAt(const WhatEverType a[100][100], int r, int c, int size); function.

So you can call temp[i][j]=calcMedianAt(a, i,j, 3);

the function itself has to extract the value to a list (do proper border handling) and find the median in that list (for example by calling some median function WhatEverType calcMedian(const WhatEverType* data, int len); and return it.