Median Filter Needed

[HighInBC]

There is a real need for a simple variable radius Median Filter to act as a despeckler that does not introduce new colors or shades.

Here is a thread on the usage forum about this:
http://forum.doom9.org/showthread.php?s=&postid=556999

There are many uses for such a filter and clearly alot of people would want such a filter based on the thread.

The filter would simply take the radius given and set each pixel to the median of the values of the pixels within the radius.

There is a filter like this for PhotoShop and ImageMagick and virtually any graphics program worth it's salt.

[rfmmars]

Yes........ the filter should be able to apply any XY filter function to any or multiable areas of the screen.... Example I do telecine and many times the focus field is not flat from left to right or top to bottom. Should be able to shift a oval or rectangle very soft mask to any part of the screen.

I have not looked at Mask Tools yet so maybe this is aready possible.

richard
www.photorecall.net

[HighInBC]

The UnDot command does what I want:
http://mywebpages.comcast.net/trbarry/downloads.htm

However, it is locked to a 1 pixel radius, which is not enough to despeckle masks, I need variable radius.

[Dali Lama]

How about the STMedianFilter from trbarry?

-Dali

[HighInBC]

The T stands for temporal, I want just spacial, one frame at a time. I am not removing actual video noise, but speckles that the filter ignores.

Most despeckling filters only touch pixels that are close to each other(in color), but I have a pure black and pure white image. These filters don't touch the speckles because they are to different in intensity.

I want a dumb median filter, not one that makes decisions based on what it thinks will look best. I have tried everything one the warpenterprises page and the 3rd party filter page involving the word 'median' without getting the results I need.

[HighInBC]

of course I may be confused... however I did try that filter and it seemed to do nothing no matter what paramaters I entered, I assumed it was due the high contrast nature of my video. (My video is a mask with no shades of grey, just black or white)

Here is what I have:

http://adserton.crackerjack.net/~rambler/before.jpg

and using the Image Magick command 'Median Blur' with a radius of 2 I got this(Which is what I want):

http://adserton.crackerjack.net/~rambler/after.jpg

[Manao]

If its black and white, use Inpand and Expand, from the Masktools.

Something like : source.inpand(y=3,u=-128,v=-128).expand(y=3,u=-128,v=-128).\
expand(y=3,u=-128,v=-128).inpand(y=3,u=-128,v=-128)That should do the trick. It amounts to an opening followed by a closing ( or the contrary ).

To raise the radius, just do inpand.inpand.expand.expand.expand.expand.inpand.inpand and so on...

BUT

While it will work in blakc and white, results on a real video won't be pleasant.

[HighInBC]

Thanks for the idea, but that seems to make the image very blocky, and even magnifies the speckling.

[Manao]

Huh ?

I obtain that result on the screenshot you gave ( with inverting the inpand and expand, I mistakenly switched them in my previous post ) :

http://jourdan.madism.org/~manao/after.png

[HighInBC]

The example I gave was very simple, more complex masks show the blockyness more... Compare my after to your after and you see why I don't want to settle, and am still looking for a variable radius median filter.

Still the results are sofar much better than I have gotten with pure avisynth.

To get the best results now I have to export all the frames to bmp's and use Image Magick to do the median blur, then turn the new bmp's into an avi. This of course fragments my harddrive badly hehe.

There are atleast 4 avisynth filters out there that do this with a radius of 1 only... but as I said before I need radius of 2 or 3 or even greater.

[Si]

If you don't mind a slow filter - I'll write it.

What do you the filter to do in simple words (removing compicated terms like median :) )

regards

Simon

[Manao]

To compute the new value of a pixel, you order ( by value ) all the pixels inside the surrounding area defined by the radius, and the new value will be the median value ( the median of 1 5 7 20 23 is 7 ( the one in the middle once values are ordered ), for example )

[Dali Lama]

I just remember now: there is a filter for AviUtl that is a median filter. But it is in japanese. It would be nice to have one in AVISynth Simon.

-Dali

[HighInBC]

Originally posted by Si
If you don't mind a slow filter - I'll write it.

What do you the filter to do in simple words (removing compicated terms like median :) )

regards

Simon

Exactly what Manao said:

"To compute the new value of a pixel, you order ( by value ) all the pixels inside the surrounding area defined by the radius, and the new value will be the median value ( the median of 1 5 7 20 23 is 7 ( the one in the middle once values are ordered ), for example )"

Median is the center number in a list of values that has been sorted in order. I don't care if it is slow, thank you very much for your trouble.

-HighInBC

[tsp]

You can get my version of medianblur here(30KB) (http://www.tsp.person.dk/MedianBlur.zip) .
It is very slow, not optimized at all and basicly untested. use it like this:
medianblur(clip,radius(default=2))

clip must be yv12

the source code is here (http://www.tsp.person.dk/mbsrc.zip)

[kassandro]

Originally posted by tsp
You can get my version of medianblur here(30KB) (http://www.tsp.person.dk/MedianBlur.zip) .
It is very slow, not optimized at all and basicly untested.
I think that such a filter can't be fast for a radius > 1. If radius=2 you have to sort 25 values for each pixels. If you have radius=3 then you have to sort over 49 values. It is impossible to use SSE for radius > 1. Thus even on the fasted PC you are well below 1 fps if radius=3 and that makes the filter unusable.
I recommend to iterate RemoveGrain(mode=4) and you will achieve a similar effect as with Image Magick above.

[Leak]

Originally posted by kassandro
I think that such a filter can't be fast for a radius > 1. If radius=2 you have to sort 25 values for each pixels. If you have radius=3 then you have to sort over 49 values. It is impossible to use SSE for radius > 1. Thus even on the fasted PC you are well below 1 fps if radius=3 and that makes the filter unusable.

It's not that bad - after all, you are moving a window over the image, so after you've sorted the first values when you move the window you can remove the values dropping out on the left side and insert the values coming in from the right side into the still sorted set.

Granted, it won't be very fast, but you don't have to re-sort all values for each pixel, since removing values will keep the set in sorted order.

np: Vladislav Delay - Kasvot Univat (Demo(n) Tracks)

[HighInBC]

1 fps is plenty fast. You see you would not use a radius >1 on video or the effect would look terrible. I am rendering special effects for a little film I am making with some friends. And waiting a few days for it to render is no problem at all.

Even with ImageMagick it was only at 1 frame per second and that was after turning the clip to bmp's and the back into video after, this helps me immensly!

[HighInBC]

Hmmm, at first attempt it seems to do little or nothing(Though a higher radius slows it down so I know it is trying), using this command:

LoadPlugin("C:/DVD Tools/AviSynth 2.5/plugins/MedianBlur.dll")
return StackVertical(b2a_mask.ConvertToYV12(),b2a_mask.ConvertToYV12().MedianBlur(radius=3))

I got this image:

http://adserton.crackerjack.net/~rambler/compare.jpg

You did say it was untested hehe. Thank -HighInBC

[kassandro]

Originally posted by Leak
It's not that bad - after all, you are moving a window over the image, so after you've sorted the first values when you move the window you can remove the values dropping out on the left side and insert the values coming in from the right side into the still sorted set.

Granted, it won't be very fast, but you don't have to re-sort all values for each pixel, since removing values will keep the set in sorted order.

np: Vladislav Delay - Kasvot Univat (Demo(n) Tracks)

I did have the same idea. It should improve matters if radius > 2. On the other hand you have to add additional structure to the sorting process such that you can take out the pixels on the left side and sort in the pixels from the right side. In the end, the algorithm will be a lot more complicated, but the larger the radius the larger the speed benefit.
In the same way you speed up Undot, but you need more than 8 SSE registers for that purpose (AMD's Hammer has 16 in 64 bit mode).

[tritical]

Little late now, but I had a go at a YV12 only median filter yesterday as well. It is similar to the filters in mask tools in that it takes 3 parameters (Y, U, V) so each plane can have its own radius, or depending on the settings planes can be copied, memset to specific values, or simply not processed at all. Also, this filter will handle the edges of the image (less then radius distance away). In a little speed test it appeared to be about twice as fast as medianblur for the same radius.

Also, it seems the reason tsp's filter does not do anything is that it literally doesn't... at the end it returns the original frame instead of the processed frame. I've been there before :p.

EDITED: removed link. tsp's is faster now and supports all the same things.. grab his.

[tsp]

embarrasing :o. Fixed that little bug, same link. Doesn't change the fact that it is slow. Working on another sort algorithm. Should speed the filter up.
Also I have added the feature to add seperate radius for each plane. if the radius is set to 0 the plane is unchange and if set to -1 the plane isn't processed at all.

the syntax is now:

medianblur(clip,radiusy,radiusu,radiusv)

[Mug Funky]

wow, tsp's medianblur does very funny (and cool looking) things to the picture. almost like a motion-blur. perhaps MVtools will give cleaner vectors if i feed it with this?

question: why is photoshop's median so much faster? adobe are definitely not known for optimizing anything (ever...).

[HighInBC]

Thanks tsp, this will work great! Problem solved. It is slow, but I can deal with that, would be nice if it gets faster tho hehe

-HighInBC

[tsp]

HighInBC If you only need a medianblur with a binary clip, I think it should be possible to make a very fast version.

[Manao]

Indeed : you make a convolution with a uniform matrix, followed by a binarize with a threshold at 128.

[Leak]

Originally posted by Manao
Indeed : you make a convolution with a uniform matrix, followed by a binarize with a threshold at 128.

How about just counting the number of white pixels and setting the current pixel to white if more than half of the surrounding pixels is white?

Isn't a full-fledged convolution a bit overkill for this case?

np: Phoenecia - Biorepo (Brownout)

[Manao]

A convolution by a kernel filled with ones amounts to count the white pixels. And some convolutions ( YV12Convolution at least ) are optimized in order not to recompute lines / columns already computed, so it will be almost as fast.

[tsp]

Updated medianblur. It is now minimum 3 times faster for radius 1 to about 10^6 times faster for radius 150 and up. You can get it here (http://www.tsp.person.dk/MedianBlur02.zip) and the sourcecode here (http://www.tsp.person.dk/mbsrc.zip).
The filter now creates a variable called DEBUG that containes the time in msec that the filter uses to calculate each frame.

Get the time like this:

scriptclip("subtitle(string(DEBUG),x=50,y=50)",after_frame=true)

[Mug Funky]

wow, that is a lot faster.

seems to mess up chroma on non-mod16 resolutions. that's not really a problem though.

[edit]

here's a very simple median-denoiser. i have a photoshop action that does the same thing (only much slower) for making jpegs more compressible.

clean = last.medianblur(4)
mask = yv12lutxy(last,clean,yexpr="x y - abs 256 6 / *")
maskedmerge(clean,last,mask)


it'd be cool to see a variable radius temporal filter too... might be a little faster with only 1 dimension to work in.

[tsp]

I finnished version 0.3 of medianblur. It is now even faster and can now process the borders too. Get it here (52 KB) (http://www.tsp.person.dk/medianblur03.zip). Sourcecode is included.

Next I will add a temporal filter or a binary median blur.

[Mug Funky]

whoa! bloody good work. it's faster than potatoshop now. i knew there was a good way to do this :)

[Didée]

Thanks tsp and tritical for implementing this. Please continue the race to make your filter faster than the other one's :D

BTW, anyone noticed yet that a median blur makes a wonderful base for removing edge halos ... ?

[tritical]

Well I think that race is over before it got started :D. tsp had to go and do it the smart way :), that spoils all the fun. I'll leave mine up just because it has this median resize algo that I remembered seeing in a book I read (though it is pretty crappy). It also has a center weighted median option though tsp's filter could have a center weighted option added fairly easily and be faster. tsp's is definitely faster if you want a plain median blur so I would recommended his filter...

[Didée]

Hmh. The results of MedianBlur() and TMedian() are very different.

Actually, TMedian() gives the result I expect from a median filter. MedianBlur() produces a strange "widening" of small features such as thin lines, which were rather supposed to disappear instead of getting widened:

http://img54.exs.cx/img54/680/median_comp.jpg

Am I missing something here?

[tsp]

nope it's caused by a couple of bugs. I'm fixing them right now. Expect version 0.31 to be released shortly

[tsp]

Done. Get it here (http://www.tsp.person.dk/medianblur031.zip). By the way how would you like the default value for the u and v plane radius? Half the value of the y plane. Same value as y or as now allways 2?

[tsp]

Made version 0.4 that adds a centerweighted medianblur

usage:

medianblurcw(clip,int radiusy,int radiusu,int radiusv,int weighty,int weightu,weightv, bool calcborder)

Get it here (http://www.tsp.person.dk/medianblur04.zip).

[Boulder]

Should this thread be moved to the usage forum? Many people don't peek in here often - including me.

Thanks for the filter, it might be useful with my TV caps:)

[tsp]

I will make a thread there when I have added the binary and temporal median blur. At the moment I'm implementing the integer SSE optimization of the binary median blur.

[kassandro]

I just made a look at MedianBlur.cpp. Nice work, tsp. For radius >= 3 your algorithm is clearly better than straightforward sorting of adjacent pixels. First you extend Leak's idea of counting black or white pixels of a binary clips to arbitrary clips and then you adapt also Leak's first idea of removing and inserting only one row of adjacent pixels to your algorithm. It probably can't be improved much further and performance, even with a ridiculous radius=10 should be well above 1 fps even on my slow machine.
Only function radixmedianInit (and also radixmedianInitXY) deserve some criticism, especially the line count[source[i%N+(i/N)*pitch]]++;. You can avoid all these slow divisions and also the multiplications (a dumb compiler may need even twodivisions here). On the other hand these functions are used only once for each pixel column. on the other hand, radixmedianRemove and radixmedianAdd are the critical routines and these cannot be improved substantially.

[tsp]

Version 0.5 ready. It includes a binary mask median blur and a spatial-temporal median blur(slow). You can get it here (http://www.tsp.person.dk/medianblur05.zip).

kassandro: thanks. This is my third c++ program/filter and second real filter(I don't think pop counts as a real filter). So I think it's a nice result considering that. I will try to improve performance even more now after I add the to last functions.