February 17, 2009
Getting the First Non-transparent Pixel in an Image

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]

Here's a little demo.

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

[Important Notice] I should have made some speed test before recommending this method. It turns out that getColorBoundsRect() is not as fast as I thought it was. Sakri Rosenstrom's HitTest method is twice as fast as mine. So I've taken another look at his implementation and optimized it a bit more, making a kind of hybrid between both of our methods. My test tell me that this optimzed version is about twice as fast - I have updated the code in EdgeFinder.as already


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;
}

Posted at February 17, 2009 05:24 PM | Further reading
Comments

Hey Mario,

There's a small typo in the link:
edgeFinder.as should be EdgeFinder.as (capital E)

Posted by: Gepatto on February 17, 2009 09:09 PM

Thanks for the notice Gepatto - I've updated that link now.

Posted by: Mario Klingemann on February 17, 2009 09:35 PM

Hi Mario!

First of all, thanks for taking the time out at Max to explain this to me! I apologize for "smudging your name" with code that wasn't actually yours ;) Should have probably emailed you before posting that blog entry.

I added your correct method to my test run, and it turns out that the testing wasn't a complete waste of time:

http://www.sakri.net/blog/2009/02/18/get-first-non-transparent-pixel-in-a-bitmap-part-iii/

The HitTest method seems to run marginally faster?!

Anyway, I think I've polluted my blog with enough entries about this topic now! See you at FITC!

Sakri


Posted by: sakri on February 18, 2009 11:20 AM

Hey Sakri,

it turns out that your method is at least twice as fast as mine. Gosh - I'm impressed!

Posted by: Mario Klingemann on February 18, 2009 12:36 PM

Interesting discussion, but what would you use this for?

Posted by: Ian on February 19, 2009 06:49 PM

Hey guys,
Was playing around with this method a little and managed to make it about 30% faster on average. Varies quite a bit depending on the data and settings, though. Change the n property for different results and inputs.

public static function getFirstNonTransparentPixel2( bmd:BitmapData ):Point
{
var n:int = 4;
var h:int = bmd.height;
var p:Point = new Point();
var hit_rect:Rectangle = new Rectangle(0,0,bmd.width,n);
var hit_bmd:BitmapData = new BitmapData( bmd.width, n, true, 0 );
for( hit_rect.y = 0; hit_rect.y < h; hit_rect.y+=n)
{
if( bmd.hitTest( p, 0x01, hit_rect) )
{
hit_bmd.copyPixels( bmd, hit_rect, p );
return hit_rect.topLeft.add( hit_bmd.getColorBoundsRect(0xFF000000, 0, false).topLeft );
}
}
return null;
}

Posted by: Stuart on February 22, 2009 03:24 PM

Stuipd question:

how to find the first Transparent pixel? :D
i mean with alpha = 0?

Posted by: Gino on May 7, 2009 04:04 AM

And another "stupid" question....

Can this be tweaked to find the largest contiguous rectangle of all transparent pixels?

I have a series of for loops to do this now, but it seems horribly inefficient.

Posted by: Ross R on November 30, 2009 08:14 PM
Post a comment
Name:


Email Address:


URL:


Comments:


Remember info?



Thank you!

Most Visited Entries
Sketches, Works & Source Code
Lectures
Contact
Backlog
In Love with
Powered by
Movable Type 2.661

© Copyright Mario Klingemann

Syndicate this site:
RSS 1.0 - RSS 2.0

Quasimondo @ flickr
Quasimondo @ LinkedIn
Quasimondo @ Twitter
Quasimondo @ Facebook
Quasimondo @ MySpace
Quasimondo is a Bright
Citizen of the TRansnational Republic
My other blog in german
Impressum


My family name is written Klingemann,
not Klingelmann, Klingeman, Klingaman, Kingemann,
Kindermann, Killingaman, Klingman, Klingmann, Klingonman
Klingemman, Cleangerman, Klingerman or Kleangerman

profile for Quasimondo at Stack Overflow, Q&A for professional and enthusiast programmers