Get first non transparent pixel in a bitmap, 3 approaches and benchmarks

Tuesday, February 10th, 2009

I was (once again) very inspired by Mario Klingemanns presentation at the Max in Milan. He showed an example of finding the "perimeter of non transparent pixels" in a bitmap. Not long ago I did the same thing while trying to generate 3d text . He briefly mentioned "you just find the first non transparent pixel, then..." which left me wondering.

I had taken the "brute force approach" of just looping through the pixels, doing a if(bmd.getPixel32(ix,iy)>0x00000000) approach, which (unsurprisingly) isn't very fast. So, at the afterparty, I decided to harass Herr Klingemann. He gladly explained that you 'just create a one pixel high BitmapData, the width of your source BitmapData, iterate from top to bottom draw()ing this "scan line", using floodFill() and getColorBoundsRect() each time to compare if the bounds rect was the width of the source bitmap'.

This sounded incredibly slow. In preparation for my FITC presentation, i'm now returning to the 3d text code, and I just had to test this out. I had this "Brilliant" idea to use BitmapData.hitTest() instead... surely this was faster?! I would create a Rectangle, position it above the source BitmapData, then iterate all the way down, merrily hitTesting() all the way.

Here are my findFirstTransparentPixel() mutations:

PLAIN TEXT
Actionscript:
  1. public static function getFirstNonTransparentPixelLooping(bmd:flash.display.BitmapData):Point{
  2.     var ix:uint,iy:uint,bmd_height:uint=bmd.height,bmd_width:uint=bmd.width;
  3.     for (iy=0;iy<bmd_height;iy++){
  4.         for(ix=0;ix<bmd_width;ix++){
  5.             if(bmd.getPixel32(ix,iy)>0x00000000){
  6.                 return new Point(ix,iy);
  7.             }
  8.         }
  9.     }
  10.     return null;
  11. }
  12.  
  13. public static function getFirstNonTransparentPixelFloodFill(bmd:flash.display.BitmapData,test_fill_color:uint=0xFFFFFF00):Point{
  14.     //var hit_bmd:BitmapData=new BitmapData(bmd.width,1,true,0);
  15.     var hit_bmd:BitmapData;
  16.     var m:Matrix=new Matrix();
  17.     for(var i:int=0;i<bmd.height;i++){
  18.         m.ty=-i;
  19.         hit_bmd=new BitmapData(bmd.width,1,true,0);
  20.         hit_bmd.draw(bmd,m);
  21.         hit_bmd.floodFill(0,0,test_fill_color);//use yellow, assume that the image tested is monochrome... (black and transparent)
  22.         var bounds:Rectangle=hit_bmd.getColorBoundsRect(0xFFFFFFFF,test_fill_color);
  23.         if(bounds.width!=bmd.width){
  24.             return new Point(i,bounds.width);
  25.         }
  26.         //hit_bmd.floodFill(0,0,0);
  27.         hit_bmd.dispose();
  28.     }
  29.     return null;
  30. }
  31.  
  32. public static function getFirstNonTransparentPixelHitTest(bmd:flash.display.BitmapData,test_fill_color:uint=0xFFFFFF00):Point{
  33.     var hit_rect:Rectangle=new Rectangle(0,-bmd.height+1,bmd.width,bmd.height);   
  34.     for(var i:uint=1;i<bmd.height;i++){
  35.         if(bmd.hitTest(new Point(),0x01,hit_rect)){
  36.             var hit_bmd:BitmapData=new BitmapData(bmd.width,1,true,0);
  37.             var m:Matrix=new Matrix(1,0,0,1,0,-(i-1));
  38.             hit_bmd.draw(bmd,m);
  39.             hit_bmd.floodFill(0,0,test_fill_color);
  40.             var bounds:Rectangle=hit_bmd.getColorBoundsRect(0xFFFFFFFF,test_fill_color);
  41.             return new Point(bounds.width,i-1);
  42.         }
  43.         hit_rect.y++;
  44.     }
  45.     return null;
  46. }

Here's my test code:

PLAIN TEXT
Actionscript:
  1. protected function createTestBitmap(w:uint,h:uint):BitmapData{
  2.     var b:BitmapData=new BitmapData(w,h,true,0x00000000);
  3.     b.fillRect(new Rectangle(Math.round(w*.30),Math.round(h*.30),Math.round(w*.40),Math.round(w*.40)),0xFFFF0000);
  4.     return b;
  5. }
  6.  
  7. protected function testFirstBitmapFloodFill(w:uint,h:uint):void{
  8.     var start:uint=flash.utils.getTimer();
  9.     var b:BitmapData=createTestBitmap(w,h);
  10.     trace("testFirstBitmapFloodFill() first:"+BitmapDataUtil.getFirstNonTransparentPixelFloodFill(b));
  11.     trace("testFirstBitmapFloodFill() test took : "+(flash.utils.getTimer()-start)+" milliseconds");   
  12.     b.dispose();
  13.     b=null;
  14. }
  15.  
  16. protected function testFirstBitmapHitTest(w:uint,h:uint):void{
  17.     var start:uint=flash.utils.getTimer();
  18.     var b:BitmapData=createTestBitmap(w,h);
  19.     trace("testFirstBitmapHitTest() first:"+BitmapDataUtil.getFirstNonTransparentPixelHitTest(b));
  20.     trace("testFirstBitmapHitTest() test took : "+(flash.utils.getTimer()-start)+" milliseconds");
  21.     b.dispose();
  22.     b=null;
  23. }
  24.  
  25. protected function testFirstBitmapLooping(w:uint,h:uint):void{
  26.     var start:uint=flash.utils.getTimer();   
  27.     var b:BitmapData=createTestBitmap(w,h);
  28.     trace("testFirstBitmapLooping() first:"+BitmapDataUtil.getFirstNonTransparentPixelLooping(b));
  29.     trace("testFirstBitmapLooping() test took : "+(flash.utils.getTimer()-start)+" milliseconds"); 
  30.     b.dispose();
  31.     b=null;
  32. }

I tested all three functions with images ranging from 100x100 to 2000x2000 pixels:

Here be the results:

Test with image w:100,h:100
testFirstBitmapHitTest() first:(x=30, y=30)
testFirstBitmapHitTest() test took : 2 milliseconds
testFirstBitmapLooping() first:(x=30, y=30)
testFirstBitmapLooping() test took : 7 milliseconds
testFirstBitmapFloodFill() first:(x=30, y=30)
testFirstBitmapFloodFill() test took : 8 milliseconds

Test with image w:500,h:500
testFirstBitmapHitTest() first:(x=150, y=150)
testFirstBitmapHitTest() test took : 29 milliseconds
testFirstBitmapLooping() first:(x=150, y=150)
testFirstBitmapLooping() test took : 34 milliseconds
testFirstBitmapFloodFill() first:(x=150, y=150)
testFirstBitmapFloodFill() test took : 20 milliseconds

Test with image w:1000,h:1000
testFirstBitmapHitTest() first:(x=300, y=300)
testFirstBitmapHitTest() test took : 147 milliseconds
testFirstBitmapLooping() first:(x=300, y=300)
testFirstBitmapLooping() test took : 111 milliseconds
testFirstBitmapFloodFill() first:(x=300, y=300)
testFirstBitmapFloodFill() test took : 41 milliseconds

Test with image w:2000,h:2000
testFirstBitmapHitTest() first:(x=600, y=600)
testFirstBitmapHitTest() test took : 644 milliseconds
testFirstBitmapLooping() first:(x=600, y=600)
testFirstBitmapLooping() test took : 210 milliseconds
testFirstBitmapFloodFill() first:(x=600, y=600)
testFirstBitmapFloodFill() test took : 75 milliseconds

Started out good for me! With a small image my hitTest approach was over 3 times faster! Then, the bigger the sample image got, the more my method started sucking, and Mario started Rocking. Eventually the "looping" method became faster than the hitTest() :D

So, Conclusion : For small images, the amount of difference is so little it really doesn't matter, with bigger images go FloodFill... Hats off Quasimondo :)

If you have ideas for faster approaches, or improvements to the above three, don't hesitate to comment!

***EDIT :
CLICK HERE TO READ UPDATE

AND CLICK HERE TO READ UPDATE 2

***

Posted in Flash, experiment | 2 Comments »