Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


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.