I’ve been busy working on 3D lately, didn’t have much spare time for private stuff.
the mean shift filter is a little bogger used in many image processings where you need to blur something and keep sharp edges.
It is used in image restoration to remove crackles, dust & scratches… but it is also known as the infamous ‘watercolour’ photoshop filter. the only filter that can kill ANY good picture within seconds.
- I found clear and detailed infos in french here
- and I ported the algorithm from this abysmal library
It all started yesterday when I was looking for a way to z-sort the elements (components ) of an image.
it is impossible if you have only one image, but possible if you have a pair of stereoscopic images.
I found an excellent article here: 3d vision with stereo disparity that describes a way to achieve this rather easily.
it could be nice to approxiamte a 3D space after what the camera sees.
anyway, in the explainations, Shawn mentions another technique that uses a mean shift filter to separate the componentns of the image and obtain a nice smooth result.
the image created with the mean shift filter are somewhat strange, like ghosts. this is why I wanted to port it to AS :)
now here is a little interactive something:
BEWARE: the complexity of the process is given by the radius value keep it low for a start.
you can click on the picture to swap between the original and the filtered picture.
here’s a series of outputs:
original picture
note how the algorithm preserves the image features.
the last one shows the result of a high radius (=25) it took around half an hour to process ^^
you can create the filter as follow:
//instanciation //default radius:3 | distance:12 var meanshift:MeanShift = new MeanShift( radius, distance ); //assigns the bitmapData to process meanshift.bitmapData = bd; //setters for the params meanshift.radius = radius.value; meanshift.distance = distance.value; //runs the filter meanshift.process(); //listens to progression meanshift.addEventListener( ProgressEvent.PROGRESS, progress ); meanshift.addEventListener( Event.COMPLETE, completeHandler );
below is the source code:
it uses Keith Peters minimal components first time I use them, pretty satisfied :)
the pics have been taken by myself. if ever you use them, please link back or contact me if you want bigger resolution. by the way the carabus auratus (the beetle) is not dead I found it asleep under a rock and as soon as it woke up it was impossible to take a neat picture of it :)
the algorithm is (once again) given AS SUCH, no warranty it will work for you blahblahblah.
it can be made much faster if only I could steal Quasimondo’s brain for a minute… stealing is bad.
it’s really an interesting filter to play with, if applying a displacementMapFilter, you get paint daubs. you can also process a much smaller version of your bitmapData and then stretch the smart-blurred thumbnail and redraw it with a Blendmode. I was also thinking about street fighter 4 design and found that there was something quite similar in the way characters are rendered.
+it narrows down the number of colors used in the picture and assigns them cleverly (as compared to the Pixelbender filter I did lately #1) maybe on smaller versions with a biiiig radius it’s ok or as a preprocess…
well… that was it!
Andy Li
on Sep 10th, 2009
@ 9:46 pm:
WOW! This post is interesting! I’ve implemented bilateral filter in Pixel Bender ( http://blog.onthewings.net/2009/04/14/bilateral-blur-by-pixel-bender/ ) and the result is very similar to the mean shift filter as seen in your post. You should try do the filter in PB too and have a comparison :)
BTW, I’m also doing some 3D thing related to stereoscopic images! But I think I will do it in openFrameworks since Flash is too slow for that…
Hope to read more about your project :)
Mario Klingemann
on Sep 10th, 2009
@ 9:49 pm:
That’s a great effect – thanks for finding and porting it! And I wish I had some time for trying to optimize it a bit right now, but I still have a talk to prepare…
But after a quick look I saw already a few potential areas to gain a few milliseconds.
Tweets that mention HIDIHO! » Blog Archive » the mean shift filter -- Topsy.com
on Sep 10th, 2009
@ 10:17 pm:
[...] This post was mentioned on Twitter by tekool. tekool said: RT @nicoptere the mean shift filter http://bit.ly/ZSndG #actionscript – great effect. I spy with my optimizer eye: deeply nested loops ;-) [...]
Mario Klingemann
on Sep 11th, 2009
@ 12:28 am:
Okay I coudn’t leave it untouched and tried to optimize it a bit. It turns out though that there is not that much to optimize in that inner loop since the sliding window around the pixel is moving.
So I did the usual stuff: replace the Array with a Vector and store the pixel infos in a typed object. I took the freedom to move the colorspace from YIQ to YUV which is closer to human perception even though that whole color space change doesn’t seem to make any big difference in the final result – one could leave the pixels simply in RGB and save oneself those back and forth color conversions.
The speedup of using a Vector shows best with bigger radii – at the maximum setting it’s ~2x speed on my machine.
The biggest speedup for small radii was to allow the processing of more than one line per timeout. That will give you ~4x the speed for small radii (the bigger the radius is the smaller the effect of this improvement).
There might be a possibility to replace that inner loop which calculates the distance with a tiny pixel bender filter, not sure how much that will bring.
Here’s the optimized version so far (I have added two more parameters, just to see if the result is any different: minShift controls the size of the pixel shift that has to happen before the iteration is stopped, maxIterations is the maximum amount of iterations per pixel before the loop exits):
http://www.quasimondo.com/scrapyard/MeanShift_opt.zip
Frank Reitberger
on Sep 11th, 2009
@ 9:06 am:
superb Nicolas. Could be nice to build a PB-Shader on this too… ;)
rackdoll
on Sep 11th, 2009
@ 10:20 am:
Great effect! Nice found! Good job :)
nicoptere
on Sep 11th, 2009
@ 11:03 am:
thanks all for the nice words :)
Pixel Bender does excellent job to process a pixel or its close neighbours but it does not handle loops.
as for Andi’s filter, you can see PB limitations pretty soon ; the effect would be more intense if we could increase the radius more.
as mentioned by @Quasimondo, alll it could be used for is this inner loop work. would it be worth?
I read somewhere that the ShaderJobs are much faster for calculations.
@andi: I netvibed your RSS & added it to blogroll, cool stuff there :)
@quasimondo
I’m glad you would’nt leave it alone!
the filter runs so much faster now that one could almost use it for real. thanks lot.
@frank PB of course but within the limitations mentioned above ^^
@rackdoll thanks :)
Median Cut « GrgrDvrt
on Nov 18th, 2009
@ 6:55 pm:
[...] Bien sûr tout celà n’est pas à confondre avec avec l’autrement plus compliqué mean shift filter. Bon, trop bien! Cette fois c’est le [...]
Mr Ming
on Jul 22nd, 2010
@ 1:44 am:
Great blog!!! wow…Can this be used in flash cs5? Can someone share a working CS5 .fla with separate class so I can learn from it. Basically all I want to do is import an external image at runtime and add this filter on it. I’m a intermediate flash cs5 AS3 user that knows nothing about flex at the time.
With a basic working .Fla that uploads a image and filters it at runtime will be all I need. That will be great if one of you masters can help me..Please reply here or email me at stealburg@hotmail.com Thx and again great blog guys!!!