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.
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.
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
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.