If you follow me on Twitter you know that last days Mario, Nicoptere and me were trying to discover the fastest Median Filtering solution for Flash. Our first attempts were around 7 secs per 350×360 image size with small kernel 7×7! You may think that this is very slow, but Median Filtering is slow in all environments cause of its architecture. Anyway there is a constant time solution described here that will result in constant processing time for any radius. It is also mentioned that this is the fastest possible solution for now!
So no surprise all of us tried to implement it. 
After some unlucky results Nicoptere decided to leave the scene but this is all because of lack of time I think! Mario as he always do start trying to implement Linked Lists to make the process as fast as it possible. I’ve to say that Mario’s version is the fastest for now except one condition I describe later.
As for me I started with the simple Vector arrays and you will see this code inside my sources. This approach wasn’t very fast but stable for different kernel sizes. And the final version created using Linked Lists as Mario recommended. As it turns out that my version runs a little bit slower then Mario’s at small radius but performs faster when we extend filter radius size (starting radius 7).
Update:
I’ve merged my Histogram class with Mario’s filter applying structure (it is faster and more accurate) what results in faster and a lot more stable filter results. Now the speed doesn’t grow upon radius but it performs event faster with larger radius!
Added ByteArray based method using Joa’s TDSI tool. It performs faster at small radius but upon radius grow Linked List approach may become faster.
I’ve also added another ByteArray based method that works amazingly fast! Unfortunately this method will have unexpected results starting radius 16 in worst cases due to a tricky operation of packing integers in to single entry. I put it in MedianFilter Class under constantTimeBALimit name. But it is not included in demo application.
Test results:
Pure coded Linked Lists: 7×7 kernel: 0.8-1.17 sec; 101×101 kernel: 0.7-1.14 sec
ByteArray with TDSI: 7×7 kernel: 0.7-0.86 sec; 101×101 kernel: 1.0-1.17 sec
ByteArray with TDSI (Limited): 7×7 kernel: 0.43-0.51 sec; 101×101 kernel: 0.6-0.74 sec
(all tests done using standalone non-debug Flash Player version, Mac and PC)
Resources:
Test Application
Median Filter Class
I could never have achieved that on my own
thanks for sharing the source code ; after checking I can say that this is pure magic to me.
great, useful and clean … as always
this will give Mario a run for his money !
Been keeping an eye on the twitter conversations over the past few days. This is really fantastic work by all involved. Thank you for sharing the source…
Wouldnt it be cool if you extend the BitmapFilter, so we could use the class like this:
bmd.applyFilter( bmd, bmd.rect, new Point(), new MedianFilter( 5, BitmapFilterQuality.LOW ))
@Mark may be you right. have to look at this point
Okay, I have finally posted my bug fixed version and sources now (couldn’t do it any earlier since I was sitting in the plane from Canada back to Germany): http://www.quasimondo.com/archives/000692.php – as far as I can see both our results are visually identical now, so I think you can remove the “lot more stable” part
. But the speed difference is still there. Mine is faster for kernels up to 17×17, but beyond that yours becomes considerably faster (e.g. 101×101 – yours 1939ms, mine 2871ms).
Pretty cool, I loved the way you’ve all collaborated through Twitter. Would it be possible to make it asynchronous, or use some bucketing to process separate blocks? I am thinking of including it to HiSlope (coming really soon, I’ve finally done a lot of refactoring) but the exec time is still too high.
Very nice work! I wonder, did you consider using Pixel Bender to implement this?
Question; how does your image become that smooth? I have ported the most simple example from here (http://en.wikipedia.org/wiki/Median_filter) but it looks very pixelated.. (check: http://pastie.org/private/cfsxwtcng7r7bet7oecy1g). Any ideas how to get it smoother?
sorry correct link to code is http://pastie.org/private/cfsxwtcng7r7bet7oecy1g , without )
@Mark u should calculate median for every channel not for color value. I mean separate R, G and B channels and get median for each and only then to compile color value using median of each channel
wow very nice!
Wow its really fast dude! I figured out how to produce the median filter smoothly using the ‘regular way’, and yes; it takes about 6/7 seconds. I have no clue how the histograms + linked lists work and at what point they make the calculation that fast. But I figured out that if you use a cross instead of a block, you have to calculate less, so thats my only optimalisation.
Great work! Thanks for sharing the source code!