8

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.

Gilad
  • 215
  • 2
  • 11
  • Median filter is non linear. You cannot combine multiple Median filter operations into a single operation. – sgarizvi Jan 31 '13 at 07:58
  • @sgar91 well you can, but it wouldn't be as simple as the median of a5x5 window. – Oliver Charlesworth Jan 31 '13 at 07: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 08:00
  • @OliCharlesworth can you tell me how this can be done? – Gilad Jan 31 '13 at 08:06
  • @OliCharlesworth I'm interested in that too, are you sure it can be done for the median filter ? In that case, can the root signal be found in a single step ? – mmgp Jan 31 '13 at 17:25
  • @mmgp: Sure. It won't be a pleasant operation, but fundamentally it's just a non-linear function of a 5x5 neighbourhood. – Oliver Charlesworth Jan 31 '13 at 17:36
  • @OliCharlesworth I would like to see it. – mmgp Jan 31 '13 at 17:39
  • @mmgp: The function is: compute the 9 medians of all possible 3x3 regions, and then compute the median of those results. – Oliver Charlesworth Jan 31 '13 at 18:52
  • @OliCharlesworth huh ? What is the point of doing that then instead of doing two 3x3 passes ? That is not combining the two passes into one. – mmgp Jan 31 '13 at 18:54
  • @mmgp: Expressed like that, there isn't one. I was merely pointing out that a 5x5 function very definitely exists. – Oliver Charlesworth Jan 31 '13 at 19:04
  • @OliCharlesworth while someone could call that as a 5x5 function, it is not one that produces the correct result for two 3x3 median filter passes. I could prepare a counter-example if that is needed at all. Or maybe I misunderstood your function. Did you mean the following: given a 2D discrete point (x, y), compute the median of the medians of the nine 3x3 windows around it, then assign the resulting median to (x, y). Was that it ? – mmgp Jan 31 '13 at 19:12
  • @mmgp: Something like that, yes. (I see now that I should have started my description with "given a 5x5 region...") ;) – Oliver Charlesworth Jan 31 '13 at 19:14
  • @OliCharlesworth http://i.imgur.com/Ns0bbKs.png, the central point there is assigned 0, but with two 3x3 passes it would have the value 1 (the notations I've used for showing the medians of the windows might be confusing, don't let distract you and check it yourself if needed). – mmgp Jan 31 '13 at 19:26
  • @mmgp: Huh? By definition, what I'm describing is identical to just performing two monolithic passes! – Oliver Charlesworth Jan 31 '13 at 19:27
  • @OliCharlesworth it certainly isn't, check the simple example. – mmgp Jan 31 '13 at 19:30
  • @mmgp: For a 5x5 example, my "function" is literally identical to running two passes! I don't understand what you'd be doing to obtain a value of 1 for the central pixel. – Oliver Charlesworth Jan 31 '13 at 19:32
  • @OliCharlesworth why are you fighting against the example ? First calculate a 3x3 median filter on it, pad with ones as needed. Now calculate a 3x3 median filter on the result obtained previously. The central point is 1 now. – mmgp Jan 31 '13 at 19:53
  • @OliCharlesworth I noticed I made a mistake in the example, I'm sorry for that, but at least we are in agreement that this function is doing nothing else than the two passes. Thus, nothing has been done to answer the question (I currently don't think it is answerable in a positive way). – mmgp Jan 31 '13 at 20:03
  • @mmgp i think there is no Mask that represents the median filter since it's non-linear as well you can do A*A(IM)=A^2(IM). – Gilad Jan 31 '13 at 22:35
  • @Androidy this isn't a rule for non-linear filters. I would try to explain how it works for certain non-flat morphological structuring elements, but from previous discussions about flat and non-flat morphology in SO I'm unsure if there is any point in doing so. – mmgp Jan 31 '13 at 22:42
  • 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 09:50

3 Answers3

2

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

2

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

Gilad
  • 215
  • 2
  • 11
1

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.