As you might have read in Eugene's blog, he, Nicoptere and me were having a little competition who could come up with the fastest implementation of a median filter. Median filters have the unpleasant property that they can not be as easily optimized as for example blur filters. The median filter is also one of those types of filters that are not very well suited for an implementation in Pixel Bender due to the way Pixel Bender processes images (except maybe for a trivial 3x3 median).
What a median filter does is to take all the pixels within a certain radius around a pixel, sort them numerically ( channel by channel) and then return the color that ends up in the middle of the sorted list. You can imagine that doing this for every pixel in an image is quite a processing effort. Fortunately people much smarter than me have found ways to speed this up considerably. The paper I had stumbled across sometimes in the past was this one by Simon Perreault and Patrick Hebert. And whilst the authors even provided the C source for this filter I did not bother to look at it since I thought that things that are fast in C are not necessarily fast in Flash and decided to roll my own version of the algorithm based on maintaining the histograms and the kernel in the form of sorted linked lists. I figured that this would speed up the process of joining and separating the histograms since I could use a kind of "zipper" technique to do that. To my astonishment the first tests were extremely slow - even though I tested the speed with a release version (testing this with the debug version is about 10 times slower).
The breakthrough came with a tip Ralph Hauwert gave me: whenever you create a linked list class in Actionscript make sure that you use the "final" keyword for it. Until then I had thought that this keyword acted more as a decorative element without real impact. Well, I'm happy that I was wrong since the speedup in this case was extraordinary.
When you compare my implementation with Eugene's note that a kernel size of 7x7 in his example is the equivalent of a radius of 3 in mine (3+3+1=7), 17x17 is a radius of 8 (8+8+1=17). As far as I can see my version is faster until a radius of 7 but after that his version surpasses mine. I have to study his code now to see how he has solved it.
Since the median filter still takes considerable rendering time I added a "asynchronous" switch which allows to render the effect in background without stalling the rest of the application. Of course this will slow down the whole rendering process.Posted at October 20, 2009 01:05 PM | Further reading