# median filter one after the other

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.

-
Correct me if i'm wrong. Whether you iterate the image once or twice, in both cases you have O(n^4). More detailed first one is O(n^4) and the second one is O(n^4)+O(n^4) which results again in O(n^4). (Programmatically: 2 nested loops for the x and y iteration of the image and 2 nested loops for the x and y iteration of the filter -> total 4 nested loops. Therefore O(n^4) ) I assumed in this analysis that the median filter gets the twiced size when used for just one iteration. – Hasan Tahsin Jan 30 '13 at 22:58
@moler111 cannot follow you. Applying a constant-width median filter is $O(n)$, where $n$ is the number of pixels, or $O(hw)$, where $h,w$ are the dimensions. (You might have meant $O((hw)^2)$.) – Yuval Filmus Jan 31 '13 at 0:30
What is a median filter? Where did you get stuck with your idea? How large a window should you go for? – Yuval Filmus Jan 31 '13 at 0:31
@YuvalFilmus it doesn't matter what size the given Image is. what you usually do let's say in MATLAB, is take the 3X3 median filter pad it with zeros to the size of the image (100x100 for example) do a convolution of them. we know that median filter does an average for each pixel in the image for it's 3x3 neighbors. so this means that applying this function twice will do 2 averages for the 3x3 pixels into each pixel of the image. – Gilad Jan 31 '13 at 7:37
So this is a Matlab question? If that is the case, it's offtopic here. – Raphael Jan 31 '13 at 14:51

The value a pixel gets after applying the median filter only depends on points in the $3\times 3$ window centered at it. So applying the media filter twice, any pixel depends only on points in the $5\times 5$ window centered at it. So you could in principle do it in one go, using a larger window and a more complicated function. How complicated - I'll let you to find out.

-

The median is a value of a sample which states that half of the other values of the sample have higher values and the other ones are smaller ones. In a 3⨉3 filter you are selecting the median out of a sample of 8 elements. Let's assume we have the following values in our sample (an image of size 3⨉3):

1  2   4
8  16  32
64 128 255

If we apply the median filter for the upper left value [sample: {2, 8, 16}], the median is 8 (not processing out of boundary values). After the first application of the median filter we get a new sample:

8  8  16
16 20 16
16 32 32

If we apply the median filter again, we get:

16 16 16
16 16 20
20 16 20

So my point here is that after each application of the median filter, you will get a new sample [0]. But the evaluation of one new pixel depends on all the other sample values and modifies the sample itself. Because of this dependence I cannot see any way to be able to apply the filter twice in one step. I also did not find any literature about this [1].

[0] Unless the image contains only the same value at each pixel which we cannot assume.
[1] which I don't want to use as a pro or contra argument.

-