Tip: Use AS3′s Histogram() method for color averaging

For several of my projects, I’ve been reusing the same simple method of finding the average color of a region, based on an often-used technique of looping over each pixel, grabbing the pixel’s color using BitmapData.getPixel(x,y), and bit-shifting the results to arrive at the individual color sums.

Great, I thought.  No need to ever revisit this.

Then, once I got started exploring computer vision and signal processing, I started needing color averages for live video, pumping in at 30 frames per second, on top of a screaming mountain of other intense math, and every millisecond started to matter.

So I followed up on a hunch I had about Actionscript’s BitmapData.Histogram() function.  There’s a lot of uses for this function, but even after looking around the AS3 forums, I haven’t found anyone who uses it for finding the average color values.  I gave it a shot and was very surprised at the result.  Check it out after the jump.

What the Histogram() method does is read over a BitmapData object and return a Vector.<Vector.<Number>> (a vector of vectors of numbers, if that makes sense) object with 4 rows–one each for red, green, blue, and alpha–and 256 columns storing the total number of pixels of each of the available brightness levels, 0-256, for that channel.  With this information at our fingertips, shouldn’t we be able to sum up the brightness levels and divide by the total number of pixels?  Let’s try it out.

The old way: Bitshifting color values

function averageColor(source:BitmapData):uint {
 source.lock();

 var pixel:uint;
 var red:Number = 0;
 var green:Number = 0;
 var blue:Number = 0;

 var w = source.width;
 var h = source.height;
 var countInverse:Number = 1 / (w*h);

 for (var i:int = 0; i < h; i++) {
  for (var j:int = 0; j < w; j++) {
   pixel=source.getPixel(j,i);

   red += pixel >> 16
   green += pixel >> 8 & 0xFF;
   blue += pixel & 0xFF;
  }
 }

 source.unlock();
 red *= countInverse;
 green *= countInverse;
 blue *= countInverse;

 return red << 16 | green << 8 | blue;
}

Take a look at what’s going on.  First I set up the variable holders for the red, green, and blue sums.  Then I set up holders for the width, the height, and the inverse of the total pixel count (Note:  I use the inverse so that I only have to perform 1 division operation at the beginning of the function instead of 3 at the end).

Then I loop through each and every pixel in the image, store the pixel’s color, decompose it using the standard bit-shifting method, and add it to each sum.  Assuming even a small image of 100 x 100 px, this result in 10,000 getPixel() calls.

The new way: Using the Histogram() function

private function histogramTest(source:BitmapData):uint {

 var histogram:Vector.<Vector.<Number>> = source.histogram();

 var red:Number = 0;
 var green:Number = 0;
 var blue:Number = 0;

 var w = source.width;
 var h = source.height;
 var countInverse:Number = 1 / (w*h);

 for (var i:int = 0; i < 256; ++i) {
  red += i * histogram[0][i];
  green += i * histogram[1][i];
  blue += i * histogram[2][i];
 }

 red *= countInverse;
 green *= countInverse;
 blue *= countInverse;

 return red << 16 | green << 8 | blue;
}

See what I did there?  Since I know each row in the Histogram() function’s result is a color channel, and each column is the count of how many pixels match each brightness level from 0 to 256, I can do some quick math to come up with the exact same color average results in a fraction of the time.

2x – 10x Performance increase

My test image was reasonably large, at 675 x 644 px (a total of 434,700 pixels), and the speed difference was staggering.  The Histogram method consistently booked a 2x speed increase in the browser (10ms vs 5ms) and a 10x speed increase in Flash player (50ms vs 5 ms – for some reason the .getPixel() method is consistently 5x faster in the browser).

Give it a shot on your own projects and let me know if you see the same results.

UPDATE: A new method was recommended to me, using the BitmapData.draw() method to resize the image down to 1px x 1px and then doing a single BitmapData.getPixel() call to read it.  While is is, like, crazy fast (100 trials averaged 0.6 ms), the result wasn’t accurate enough for what I need it for. Lord knows what perceptual color algorithms Actionscript uses, but it definitely wasn’t a pure average function.  For another project, maybe, but not when I need pixel-perfect accuracy.  I updated the test swf above to include its results too.