Tell me more ×
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.
up vote 0 down vote favorite

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
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. – moller1111 Jan 30 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 at 0:30
1  
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 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. – Androidy Jan 31 at 7:37
So this is a Matlab question? If that is the case, it's offtopic here. – Raphael♦ Jan 31 at 14:51
show 3 more comments

2 Answers

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|improve this answer
up vote 1 down vote

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