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:

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

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

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

I've tried to edit your question to make it more readable and grammatical, but it was sometimes a bit hard for me to tell what you were trying to say. Please check that I didn't introduce any mistakes, and fix them if you find any. Thanks! — Ilmari Karonen

Ilmari Karonen Ilmari Karonen · Accepted Answer · 2014-11-11T17:25:51

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.

Two dimensional array median filtering

2 Answers