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.
Here is my Median example
sourcecode and zipped sources
Whilst working with some huge bitmaps for Aviary I had to face the undeniable fact that huge bitmaps are memory hogs and that the memory that is made available to the Flash Player by the browser is not unlimited. Actually it is quite limited - on my Vista machine that has 4GB of RAM I max out the memory at ca 1.5GB in FireFox 3.5.2. - that theoretically allows to keep 25 of the 64MB 4095*4095 bitmaps in memory which are the maximum sized bitmaps that Flash Player 10 allows for.
In practice it turns out though that this value is much smaller, the reason for it I learned from Joa: memory fragmentation does have a big impact on how big the chunks of memory can be that you can allocate at a certain time. So while you might be able to create 4 bitmaps of 10 MB each you might not be able to create a single one of 40MB.
But being limited to "just" 1.5GB is unfortunately not the end of the story. It shows that in most browsers (like FireFox 3.5.2) these ca. 1.5GB are not available to every SWF individually. No, all SWFs in all open tabs or windows of Firefox are sharing that one Pool of 1.5GB. That means the more one SWF requests the less is available for the others.
So in order that you can figure out what is happening yourself I've built MemoryHog, a tiny tool which will allocate and release memory. When you open multiple instances of it in your browser of choice you can see how memory is managed between all the open SWFs. A warning though: some browsers in some systems do crash when you press the "request maximum" button. Seems like Macs are more susceptible to this than PCs.
One thing you can see very good with MemoryHog is the influence of memory fragmentation. Sometimes whilst you cannot allocate a 100MB block anymore you are still able to get more than 10 10MB blocks.
My resume for Aviary: whilst it it nice to be able to finally use bigger bitmaps in Flash player 10 when it comes to using more than a few of them at the same time we will have to think about a implementing a tile based solution that makes better use of the fragmenting memory.
It's a tiny bit late maybe, but here are two image processing techniques that deal with automated thresholding and edge detection that I showed in my "2d or not 2d" talk in 2007 and in "The Pixel Whisperer" in 2008.
I've had a look at my presentation demos and repackaged their code into a single class called ThresholdBitmap. This is a BitmapData class with a few extras that help you if you plan to extract blobs or edges from a camera stream or some other bitmap.
The general problem when you do camera based experiments is that you have unnown lighting conditions. Using a simple fixed threshold might work at your development machine but might fail completely on a user's computer that has a different camera model or a different backdrop.
In image processing there are several automated thresholding methods, that are supposed to help with this problem, by looking at an image's histogram and adjusting the threshold to a level that separates the foreground from the background in an optimum way: Moment-Preservation, Maximum Entropy, Discriminant and Otsu. Those are quite capable in finding the optimum threshold level if you have relatively uniform lighting over the whole scene.
As an (better) alternative I included an adaptive threshold method which is implemented in PixelBender and which works very well also with uneven lighting, especially if you try to detect QR codes or other markers.
Furthermore the class includes a very fast edge detection (based on the thresholded image) which gives you nice 1 pixel wide edges in most cases.
Here is a demo that allows you to play around (you'll need a webcam)
Sourceview and code can be found here
Credits: the demo uses the super useful Minimal Components by Keith Peters and the Hi.RES! Stats by Mr. Doob.
Whilst playing around with some geometry that involved gradient fills I had to realize that the native implementation of Flash's createGradientBox() is unfortunately entirely useless as soon as you try to introduce rotation and scaling to a gradient. The reason seems to be that internally the order of matrix operations is unsuited for that task.
Maybe I've searched not thoroughly enough, but I didn't find any solution for this out there. So I've written a tiny class that fixes it. Here's a comparison of the difference between matrix.createGradientBox() and my new GradientMatrix.getGradientBox()
To use it you can use the same values that you would use in the native function, the only difference is that you don't have to create a new Matrix first. The syntax is var myGradientMatrix:Matrix = GradientMatrix.getGradientBox( width, height, rotation, tx, ty);
Download GradientMatrix.as here
I've started to have a bit of fun with the optimized Marilena face-tracking class and build a webcam based magic mirror. The specialty here is that it tries to displace your face only and leave the rest of the scenery untouched and additionaly adjusts the displacement scale based on how close you are to the camera:
Check out Manic Mirror at the Incubator
Yesterday Seb-Lee Delisle pointed us via Twitter to this great example of a Flash based real-time face detection. It turns out that already more than half a year ago Ohtsuka Masakazu had been porting the face detection part of OpenCV to AS3 and added the source code to the Spark project - which is like a Actionscript candy box full of surprises.
So I had a look at the source code and found one feature which I wanted to change: face detection is based on so-called Haar Cascades, simplified one could say that this is a very long list of zones that get checked for certain features in an image. In the orginal version this is an xml file of almost 1 MB size. Because this is so big the xml file gets compressed into a zip file where it fortunately becomes just 100K. So in the orginal version the zip file has first to be loaded and then unpacked and parsed. My consideration was that swfs get zipped anyway, so why not turn the whole xml file directly into a class?
So that's what I did. My adapted version does not need to load any external files anymore (which was my goal) and the whole swf becomes even about 50K smaller than the original version. I also did a few other optimizations like replacing Arrays with linked lists and reading a from ByteArray instead of using getPixel(). The downside is that since the Haar data is being hardcoded into the class now you will not be able to use this class to track anything else but faces (which in theory you could). But I expect that most people will not even know how to prepare a different Haar cascade recognition set - for example I'm one of those.
What's interesting is that this code will even run in Flash Player 9, since there is no PixelBender or Alchemy and neither the new Vector data type being used. Obviously by targeting Flash Player 10 one could even add a few more optimizations, but that's something for another weekend.
Example 1: Ohtsuka Masakazu's modified sample file
Example 2: Real-time webcam face tracking
Here's the modified sourcecode which includes two example files: Marilena_mod10.zip
Here are a few more of my entries for #tweetcoding:
"Moskitos":
g.clear();ls(1);o[i++]=[mouseX,mouseY,2*r(),2*r()]; for each(p in o){mt(p[0],p[1]); lt(p[0]+=2*s(p[1]*p[2]),p[1]+=2*s(p[0]*p[3])); };i%=2000
"Love in 3D":
if(i<250&&(x=y++)) with(addChild(new TextField)) text="<3",x=r()*500-250,y=r()*500-250,z=i*2-250, rotationX=rotationZ=r()*360;rotationY=i++
"Hyperdrive":
if (!o.b)addChild(o.c=new Bitmap(o.b=new BitmapData(500,500))),o.b.noise(2); z=s(i-=0.01)*15;o.c.z=-z;o.b.draw(this,o.o,o.o,"hardlight");
"Fibonacci Sequence":
if(!i)i=1,o.b=0,o.c=addChild(new TextField),o.c.autoSize="left",o.c.wordWrap=o.c.multiline=1; o.c.appendText(" "+i),o.a=o.b,o.b=i,i+=o.a
"All Invaders":
if(!i) g.beginFill(0),a=b=i=64,d=511; g.drawRect(a&=d,b&=d,i,i); g.drawRect(d-a+1-i,b,i,i); a+=r()<0.4?i:0;b+=r()<0.4?i:0;
"The Golden Days":
g.clear();g.beginFill(0); x=y=20;for(i=81;i--;g.drawCircle(40*a,40*b,d*2)) a=(i%9),b=int(i/9), d=m.sqrt((d=mouseX/40-a)*d+(d=mouseY/40-b)*d)
"Superstar":
g.beginFill(r()<0.4?0:1e8);q=r()*640;c=r()*480;a=2;u=r()*10; for(d=12;--d;(d<11?lt:mt)(q+u*a*s(i+=0.63), c+u*a*s(i+1.57)),a=7-a){}
Another two entries for #tweetcoding.
"1967":
i+=0.06;g.clear();g.beginFill(0);for(x=80;x--;){g.drawCircle(25+70*(x%9),25+70*(y=int(x/9)),70+(s(x%9*0.7+i+s(y*0.7+i)))*35)}
Grant Skinner has started a litte competition on Twitter called tweetcoding where the goal is to create something nice in 140 chars of Actionscript 3. And the fine folks at Adobe actually will give a free copy of Flash CS4 to the winner, who will be picked on March 1st.
As a starting point there is a small wrapper which predefines a few common functions and objects with short variable names. Above you see my first entry - which requires Flash Player 10 btw: which looks like this as a tweet
MORE...I just came across Sakri Rosenstrom's posts (1 2) about his methods of finding the first non-transparent pixel in a bitmap. Looks like he got inspired by my talk at MAX Europe - unfortunately he seems to have misunderstood my explanation back then. My bad - I should have posted my method a long time ago - so here we go. [Notice: it turns out that Sakri's method is faster than mine - please check the update at the bottom of this post]
First you might ask what the hell this method is needed for at all. There are three applications that come to my mind right away: blob tracking for multi-touch interfaces (using my flood fill method), QR-code recognition and bitmap vectorization. All of them have in common that after having detected a blob of uniform color in a bitmap you want to trace the outline of it. In order to do that you need to have a starting point of which you know that it lies on the edge. That's what the method I will show you here does.
If we were programming in C the approach would be to start at the top left corner of the bitmap and do a getPixel(x,y) from left to right and top to bottom until you find a pixel that is not 0x00000000. But since we are using Actionscript there are a few methods in the BitmapData class that will be quite faster than a loop.
The workhorse in this case is the getColorBoundsRect() method. In case you forgot what it does: this method will return you a Rectangle which encloses all pixels of a certain color inside a BitmapData object.
The starting situation: we have a transparent bitmap which contains non-transparent pixels somewhere. In step one we use getColorBoundsRect to narrow down on the minimum area that still contains any non transparent pixels:
var r1:Rectangle = bitmapData.getColorBoundsRect( 0xff000000, 0, false );
If the height of r1 equals 0 we know that the image is completely empty and can stop rightaway. If not we can continue. And here's the trick. We've got a rectangle now and we know for sure that somewhere in the topmost row of that rectangle there is a non-transparent pixel. What we cannot count on is that it is the one at the very left, aka r1.topLeft - it's absolutely possible that there is just a single pixel set in that row and it can be anywhere between r1.left and r1.right.
But here's the trick: we simply use getColorBoundsRect again - unfortunately we cannot do this using the same bitmapData. We need to extract that first row of pixels into a separate temporary bitmap:
var temp:BitmapData = new BitmapData( r1.width, 1, true, 0 );
temp.copyPixels( bitmapData, r1, new Point());
Now that we've got a 1 pixel high bitmapdata which contains at least one non-transparent pixel we can continue:
var r2:Rectangle = temp.getColorBoundsRect( 0xff000000, 0, false );
The last step is to add the offset we have found here to the previously found top left corner of first colorbounds:
var startPoint:Point = r1.topLeft.add( r2.topLeft );
All together it looks like this:
public static function getFirstNonTransparentPixel( bmd:BitmapData ):Point
{
var r1:Rectangle = bmd.getColorBoundsRect( 0xff000000, 0, false );
if ( r1.width > 0 )
{
var temp:BitmapData = new BitmapData( r1.width, 1, true, 0 );
temp.copyPixels( bmd, r1, new Point());
var r2:Rectangle = temp.getColorBoundsRect( 0xff000000, 0, false );
return r1.topLeft.add( r2.topLeft );
}
return null;
}
Or you can download the EdgeFinder.as class here
public static function getFirstNonTransparentPixel( bmd:BitmapData ):Point
{
var hit_rect:Rectangle=new Rectangle(0,0,bmd.width,1);
var p:Point = new Point();
for( hit_rect.y = 0; hit_rect.y < bmd.height; hit_rect.y++ )
{
if( bmd.hitTest( p, 0x01, hit_rect) )
{
var hit_bmd:BitmapData=new BitmapData( bmd.width, 1, true, 0 );
hit_bmd.copyPixels( bmd, hit_rect, p );
return hit_rect.topLeft.add( hit_bmd.getColorBoundsRect(0xFF000000, 0, false).topLeft );
}
}
return null;
}
