Simple Temporal Median Filter

[kevina]

I have an idea for an extremly simple yet very effective filter which eliminates noise by simple clipping each pixel in current frame to the minimum and maximum of the surrounding frames. It is extremely effective at removing single frame temporal noise such as black streaks due to dirty VCR heads. It removes noise in a way no other temporal noise filter, that I have seen, does.

Here is a before and after image of a dirty frame: Before (http://kevin.atkinson.dhs.org/temporal_median/in.png) After (http://kevin.atkinson.dhs.org/temporal_median/out.png)

And here is a short video clip (mjpeg format) Before (http://kevin.atkinson.dhs.org/temporal_median/in.avi) After (http://kevin.atkinson.dhs.org/temporal_median/out.avi)

The filter works as follows:
Let a = pixel from previous frame
Let b = pixel from current frame
Let c = pixel from next frame

IF b < min(a,c)
THEN b = min(a,c)
IF b > max(a,c)
THEN b = max(a,c)
Or put another way:
b = max(min(a,c), b)
b = min(max(a,c), b)
Or put yet another way:
b = median(a,b,c)
Which is why it is called a temporal median filter.

More information as well can be found at http://kevin.atkinson.dhs.org/temporal_median/.

I do not have the ability or know how to create an AVISynth filter (no VC++). Thus, I would really appreiate it if someone could do so for me. It should be extremly easy to do. The above link included some sample code which takes yuv4mpeg as input and output. It also included some hints on how to port it.

Thanks in advance.

Edit to fix medium -> median

[Acaila]

What you are describing is in fact called a temporal median filter, and as far as I know Tom's STMedianFilter (www.trbarry.com/STMedianFilter.zip) does both spatial and temporal median filtering.

Tom also made UnDot (www.trbarry.com/UnDot.zip) which is just a spatial median filter.

[Nic]

Anybody else want to help me start a petition to get Tom to have an index to his filters on his main page of www.trbarry.com ? ;) :D

[Acaila]

You've got my vote :D

[bilu]

@Nic

Better do it in another thread because you'll get lots of votes and this thread will go completely offtopic :D

Bilu

[Nic]

Erm....I was joking (?) I dont want lots of people actually voting. But I can see what you mean. Ill bring it back on topic.

@kevina20723:
Please let us know if Tom's filter will be enough to fill your needs. If not adding your SSE code and using Tom's filter as a base means creating the filter should be no more than a few minutes work.

Cheers,
-Nic

[kevina]

Thanks everybody. I overlooked STMedianFilter. I will have a look.

PS: I fixed my embarrassing spelling mistake.

[Acaila]

Sorry to have actually voted Nic, but I think people have bugged Tom for over a year now to do something like that ;).



Although a temporal median filter could probably be written very fast, doing it right is something else entirely. Frames in a video change because of motion, so a pixel in one frame doesn't correspond anymore to the same pixel in an adjacent frame.

That's why to do it right requires either:
1) some sort of motion compensation algorithm to find the true adjacent pixels, or
2) setting a threshold for the maximum amount the filter is allowed to change a pixel to minimize any potential damage.

I believe Tom's approach was the second one. On the other hand I believe the first should result in the best (=highest quality, most noise reduction), albeit slowest, algorithm.

[kevina]

Acaila, your right that my simpile filter will cause ghosting in motion areas. I tried Tom's filter, but it not nearly as effective. Most of the back dots will still there.

May I suggest a third method:

Identify the motion areas and only apply the filter to the non motion areas. This should be faster, and easier, than actually trying to track the motion.

My main goal is to eleminate temperal "salt-and-pepper" noise. By limiting the amount that a pixel can change you also remove the main benefit of a median filter.

If someone can create (or find) a filter which will clean up my sample clip to the same level my filter can and do it without ghosting I would greatly appreciate it.

[trbarry]

That's why to do it right requires either:
1) some sort of motion compensation algorithm to find the true adjacent pixels, or
2) setting a threshold for the maximum amount the filter is allowed to change a pixel to minimize any potential damage.

I believe Tom's approach was the second one.
Acaila -

Actually STMedianFilter uses both motion comp and thresholds. But it catchs only slow 1 pixel motion in any of 9 adjacent directions, including 0 motion. I just used the TomsMoComp code for that.

Acaila, your right that my simpile filter will cause ghosting in motion areas. I tried Tom's filter, but it not nearly as effective. Most of the back dots will still there.

kevina20723 -

STMedianFilter will probably approximate yours (with extreme ghosting) if you use

STMedianFilter(0,0,255,255)

for temporal filtering only, with no thresholds. But you probably won't like it. See www.trbarry.com/Readme_STMedianFilter.txt .

OT: I absolutely promise everybody (again) to start making a real web page. ;)

- Tom

[Acaila]

Originally posted by trbarry
Actually STMedianFilter uses both motion comp and thresholds. But it catchs only slow 1 pixel motion in any of 9 adjacent directions, including 0 motion. I just used the TomsMoComp code for that.Thanks for clearing that up, I wasn't entirely sure how you implemented it.

Originally posted by kevina20723
If someone can create (or find) a filter which will clean up my sample clip to the same level my filter can and do it without ghosting I would greatly appreciate it.For pure salt-and-pepper noise (which is mostly a single abberant pixel) spatial median filtering is what is used the most as far as I've read. Although your artifacts are a little bigger than a single pixel, I do believe it would still benefit from this. Maybe extending to other pixels instead of just the neighbouring pixels for the median calculation could be beneficial. Something like this perhaps:

X X X
X X X
XXXXX X
X X X
X X X

So if you had a filter that could work with multiple patterns you could try which one works best for your case.

Another idea, since the artifacts in your video are mostly black, the filter could use a luma threshold so it only filters (near)black pixels. That way you could filter more aggressively without worrying for over-filtering the entire video (plus it'd be a lot faster too).

But all of this is just thinking out loud :).

[kevina]

Acaila wrote:
For pure salt-and-pepper noise (which is mostly a single abberant pixel) spatial median filtering is what is used the most as far as I've read. Although your artifacts are a little bigger than a single pixel, I do believe it would still benefit from this.

I believe that a temporal median filter will be far more effective than a spatial one for the type of noise in my clip. A spatial one will only be able to remove small dots. A temporal one will be able to remove far more than small dots such as large dots and streaks

Dirty VCR heads tend to produce horizontal streaks. The streeks in this clip look more like dots since they are not that bad but I have some clips with very long ones. Perhapes a horizontal only median filter will work. I have tried one with a radius of 1, but it wasn't that effective. If I have the time I will try one with a longer radius.

So if you had a filter that could work with multiple patterns you could try which one works best for your case.

Yes a median filter in which you can specify the pattern to use as a bit matrix would be useful....

Edit to fix typos

[Acaila]

I belive that a temporal median filter will be far more effective than a spatial one for the type of noise in the clip. A spatial one will obly be able to remove small dots. A temporal one will be able to remove far more than small dots such as large dots and streaksSince creating an effective temporal median filter that doesn't create ghosting is quite difficult, I meant that a spatial one could be a simple alternative worth testing.
But you're correct, a temporal version would be best.

[Didée]

For one-frame streaks and dots, did you have a look at this thread (http://forum.doom9.org/showthread.php?s=&threadid=52310)?

[kevina]

Didée, I just had a look at the thread. Unfortually it does not contain a link to the source or an explanation of how it works. It might be the answer I am looking for.

ALL, I think I can make my simple median filter work and avoid ghosting by first creating motion map of the frame and then only apply the median filter for a particular pixel when that pixel is not in motion in the prev, cur, and next frame. The motion map needs to be good enough so that it is not effected my noise or else it may think the noisy pixels I am trying to remove is motion thus making the motion map useless.

It seams that Donald Graft smart deinterlacer (with motion map denoising) fits the bill.

Anyone willing to do the work to combine the smart deinterlacer motion map and my median filter? I think the results will defiantly be worth it.