Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

Operate on an image by performing Median Filtering in a 3x3 window. Operate on the resulting image by performing, again, Median Filtering in a 3x3 window. Can the resulting image be obtained from a single Median filtering?

my initial thought is that it can be done with the right mask. maybe a median next to a median. but i'm not sure.

share|improve this question

migrated from stackoverflow.com Feb 16 '13 at 20:36

This question came from our site for professional and enthusiast programmers.

    
Median filter is non linear. You cannot combine multiple Median filter operations into a single operation. –  sgarizvi Jan 31 '13 at 7:58
    
@sgar91 well you can, but it wouldn't be as simple as the median of a5x5 window. –  Oliver Charlesworth Jan 31 '13 at 7:59
    
@sgar91 it's not 3 operations. it's 2 . first you do the first Median and after that on the result . you do the next one. please explain why does it matter that it's not linear? –  Gilad Jan 31 '13 at 8:00
    
@OliCharlesworth can you tell me how this can be done? –  Gilad Jan 31 '13 at 8:06
1  
guys, there's a couple things to point out here. 1. this is a programming question and the moderator is an idiot. 2. there is a point in a single 5x5 operation even if it were just simply a cascade of two 3x3. this is because it is a single pass through the image and offers better cache localization than two separate passes. –  thang Feb 16 '13 at 9:50

3 Answers 3

The answer is no:

See the following rearrangements of numbers from 1 to 81. In the left case the 3x3 median of 3x3 medians will be

median([77, 72, 67, 62, 57, 52, 47, 37]) = 57,

in right case median

([5, 15, 23, 32, 41, 50, 59, 68, 77]) = 41

While the median of the whole 9x9 block is 41 for both cases. enter image description here

share|improve this answer
up vote 2 down vote accepted

ok so here is the answer of my Prof. Hagit Hal-or:

if there is such a mask then it must be 5x5.
A counter example shows that this can not be.
consider the 5x5 region of an image: we fill it with values 0...0,1,2...2 (12 0's and 12 2's)
the 5x5 median on this region gives 1, regardless where you place the numbers.
Now we build the 5x5 region so that if we apply the median on the median we do NOT get 1.
Set the following:

1 0 0 x x
0 0 0 x x
0 0 0 x x
x x x x x
x x x x x 

where x are the rest of the numbers.
The first pass with median will set the top left 3x3 to 0 and so the 1 is "lost" and any order
of placing the rest of the numbers will not bring the 1 back. So median on all other
regions will result in 0 or 2. So that the second pass of the median will look at numbers that are 0 and 2 only and so will NOT result in 1.

thanks all for helping

share|improve this answer

Yes, sorry I was wrong talking about averaging instead of median.

Lets see what happens in median filtering. Suppose that your filtering routine goes on image from TOP lines down, line after line. Suppose also that it goes in every line from left to the right. You can define it to go in any order, it will not change that point that I try to explain here.

In such walk it creates new picture, pixel by pixel that come from median 3 on 3.

1) When we do first median filtering, pixel that is located in first line from above, can travel to second line (in resulting image) and not to third (since meadian 3 on 3 can only "push" pixes for distance of one).

2) When we do second median filtering, this pixel can travel one more step down - to third line.

But what with travel distance for pixel that will want to move UP in lines? For example at the beginig this pixel is in fifth line. This distance for this pixel is only 1 and not more, since out routine goes from top to bottom in lines.

And this is just property of algorithm.

Now, you will want to use bigger median mask. Such mask will give you longer bottom to top traveling distance from bottom up, not 1! This will bring pixels to places, where they can not to be moved using 3 on 3 medians, as we did in first case! And this means that does not matter what size of median you take, such problem will present.

You can define any order of work for your median routine, problem will present but with different directions (up-down-left-right).

MAIN LINE: Its impossible to do same work with larger median mask, since it will give to pixels more fredom to move, then they have when two subsequent median filters of 3 on 3 are applied.

Well, I hope I was clear enough. Just a direction to think about it. Problem can be that my solution is not really connected to image processind and more to some procedural features of algorithm.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.