Extract shape outline points from BitmapData
On my quest to generate 3D text from non-embedded fonts, after extracting positive and negative shapes from characters, the next step is to analyze and extract the points which define the pixel boundary surrounding the extracted shapes.
There is a "brute" way to do this, simply by looping through every pixel in a BitmapData, and checking weather any surrounding pixels are transparent. This works, but the discovered pixels are not in a meaningful order.
The goal is to create an algorithm which circumnavigates the extremities of shapes, storing the traversed points in sequence, eventually doing this:
My original approach was to grab the first transparent pixel, then loop around its 8 surrounding pixels, run through some rules, then determine the next pixel to move to, until the "3x3 grid" would arrive at its starting point. The "3x3" grid would move along the shape clockwise.
As a side note, it was a relief to see Marios presentation in Milan, where he had pretty much the same approach, except his was moving counter clockwise. One very important "innovation" that I learned from Mario was to double the size of the analyzed bitmap. This prevents "single pixel" lines, which, if you think about it, are very tricky for the "3x3 grid" to analyze.
My implementation was sluggish, and had a few bugs... So I came up with another approach. I guessed that the rules of moving clockwise never change, so I figured a lookup table approach might just work. The idea is to represent the "3x3 grid" surrounding a pixel as a String using zeros for transparent pixels, ones for non-transparent ones. The lookup table would then map the "next position" to the various "3x3 grids". Here's a short snippet of my lookup table:
-
protected var _variations:Object={
-
"000110110":new Point(0,1),
-
"111110000":new Point(-1,0),
-
"111011011":new Point(0,-1),
-
"111111110":new Point(0,1),
-
"100111111":new Point(1,0)}
It's still not the Usain Bolt of algorithms, but a big improvement on my previous attempt. So where did this magical lookup table come from? If you look at the animated gif above, it's actually a screenshot of a "outline pixels generator" tool which I wrote just for this purpose. This allowed me to move along the edge of a shape, as the eye would follow it, and store the "moves" as "rules". You can find the entire lookup table in the zip below.
To test and demo the algorithm, I wrote a quick flex app, click to try it out:
Choose any font, pick a character, then extract the outlines. There is one thorny topic of annoyance. Flash player adds a weird anti-alias to all text above a certain font size. Small non-embedded text appears as one would expect, but in bigger sizes (which is needed for better curve information), there is a "quasi-anti-alias". In the above image,
- The left-most image is a non-embedded text field, with the "anti-alias".
- The second image is a "mono-chrome" representation of it.
- The third is the generated outline (of the mono-chrome)
- The last one is the original (first image), with the generated outline superimposed.
The outline is not "ideal", all pixels with an alpha greater than 0 are represented as black, making the image "blockier" than necessary. In the "superimposed" image, particularly with curves, there is a clear difference between the original character and the curve. meh. There is a way to get the "aliased" text with embedded fonts, more here. But since I'm interested in non-embedded fonts...
The second "demo" within is an animated "blob", which extracts the outline on every frame. I made this mostly just to "test" the algorithm... So far it's not throwing any errors for me. The frame rate is dependent on the number of "separate shapes and negative shapes". If you have a slow machine I don't recommend this one 
The next step is to analyze these outline paths and optimize them into "vector information", which I'll blog about shortly.
Click here to try out the demo, then click
here to download the zipped flex source folder. The relevant code is in plain as3 classes, in case flex isn't your thing.
Tags: AS3, bitmapdata, Flash, flex
April 13th, 2009 at 9:46 am
Awesome stuff, liking the lookup table approach! Reminds me of how I work my way through a maze
Looking forward to the continuation!
April 14th, 2009 at 8:45 am
Looking good, as you know I’m looking for something similar atm and I have a simple outliner in pixel bender, might be useful >>> http://www.frankula.com/lab/swf/outliner.zip
April 17th, 2009 at 2:23 pm
Nice work! But can the variations in the posted example class possibly be all combinations? There’s only about 40 of them.
April 17th, 2009 at 2:40 pm
Hi Nick,
The number of combinations is reduced by the fact that the source BitmapData is doubled in size (no ‘single’ pixels). I can’t say with 100% certainty that the list covers every possible combination, but so far the algo hasn’t thrown any errors for me (which it should do in the event a combination is missing).
April 17th, 2009 at 2:54 pm
Sakri – ofcourse, my bad. Works like a charm with the bitmap doubled in size. Awesome!
May 18th, 2009 at 11:54 pm
Have you looked at the Marching Squares algorithm? It uses a 2×2 grid so you don’t need to double the size of the bitmap. That was the first thing I was looking into using with blob detection. Of course it doesn’t give you diagonals…
I also found another algorithm that I don’t yet understand that is described in this paper:
http://www.iis.sinica.edu.tw/~fchang/paper/component_labeling_cviu.pdf
May 19th, 2009 at 10:11 pm
Yeah I think Marching Squares is a good choice. I used your algorithm (not the whole example) on a 264 x 290 bitmap with 5 shapes in it. (Just doodles with the paint brush.)
Using the double sized extraction and your 9-grid search it took 137 milliseconds.
Using the double sized extraction and a 4-grid search it took 124 milliseconds
Using the single sized extraction and a 4-grid search it took 44 milliseconds
I couldn’t use the 9-grid search with the single sized extraction because my shape throws an error.
But the combination of not having to double the bitmap and having to only test 4 pixel values is a lot faster than your current implementation.
Here is the scan points:
new Point(0,-1),
new Point(-1,-1),
new Point(-1,0),
new Point(0,0)
With a 4-grid there are only 16 possible combinations compared to the 512 for a nine grid. I’m not sure how you are getting away with 40 combinations, but I’m guessing it has to do with the center always being an on pixel and the doubling must rule out some others. Maybe? With 4 grid there are two combinations that don’t occur, all on and all off so the 14 variations are:
“0001″ :new Point(1,0),
“0010″ :new Point(0,1),
“0011″ :new Point(1,0),
“0100″ :new Point(-1,0),
“0101″ :new Point(1,0),
“0110″ :new Point(0,1),
“0111″ :new Point(1,0),
“1000″ :new Point(0,-1),
“1001″ :new Point(0,-1),
“1010″ :new Point(0,1),
“1011″ :new Point(0,-1),
“1100″ :new Point(-1,0),
“1101″ :new Point(-1,0),
“1110″ :new Point(0,1)
There are two ambiguous variations 0101 and 1010. Those whould be where a shape approaches itself at an angle but doesn’t touch. I haven’t tried it yet to see if that can cause an “infinite” loop.
May 20th, 2009 at 6:14 am
Hi Rothrock,
Thanks for taking the time to post
I had a quick look at Marching Squares on wikipedia, looks great! In retrospect, I’m wondering why I went for 9 squares 
Do you have an AS3 implementation of Marching Squares? I’d love to give it a spin myself…
Thanks again
Sakri
May 20th, 2009 at 7:05 am
I haven’t actually made an AS3 version other than modifying what you posted here. Your example is the same idea, just not having a 4-grid. So in your class where you have BitmapEdgeScanner class you replace (or make a second version) of the _scan_points and _variations properties. Also change the loop in updateScanGrid to i<4.
I think your shape extractor is a lot faster than trying to use the marching square to march over all the empty space and the interiors.
And don’t forget to not double size extract the shapes! That is where the biggest time saving seems to be. I was also looking at BitmapData.lock/unlock in some places, but I couldn’t find anywhere where it seemed to make a really large difference.
July 2nd, 2009 at 12:39 am
I took a minute to adapt your code to the 4-pixel marching squares algorithm…
package com.MorganMoonjob.edgeDetection{
import __AS3__.vec.Vector;
import flash.display.BitmapData;
import flash.geom.Point;
public class EdgeScanner{
protected var _scanPts:Vector.=Vector.([
new Point(0,0),
new Point(1,0),
new Point(0,1),
new Point(1,1)
]);
protected var _variations:Object={
“0000″:new Point(1,0),
“0001″:new Point(0,1),
“0010″:new Point(-1,0),
“0011″:new Point(-1,0),
“0100″:new Point(1,0),
“0101″:new Point(0,1),
“0110″:new Point(-1,0),
“0111″:new Point(-1,0),
“1000″:new Point(0,-1),
“1001″:new Point(0,-1),
“1010″:new Point(0,-1),
“1011″:new Point(0,-1),
“1100″:new Point(1,0),
“1101″:new Point(0,1),
“1110″:new Point(0,-1),
“1111″:new Point(1,0)
}
protected var _target:BitmapData;
protected var _grid:String;
public function getCurrentGrid():String{
return _grid+”";
}
protected var _position:Point;
public function get position():Point{
return _position;
}
public function EdgeScanner(target:BitmapData){
reset(target);
}
public function reset(target:BitmapData):void{
_grid=”";
_target=target;
}
public function moveTo(p:Point):void{
_position=p;
updateScanGrid();
}
protected function updateScanGrid():void{
_grid=”";
var p:Point;
for(var i:uint=0;i0x0 ? “1″ : “0″);
}
}
public function getNextEdgePoint():Point{
var p:Point=_variations[_grid];
if(p==null)throw new Error(“BitmapEdgeScanner Error : _grid:”+_grid+” , not found in _variations”);
return new Point(_position.x+p.x,_position.y+p.y);
}
}
}
July 2nd, 2009 at 6:06 am
Hi Morgan,
Thanks for posting!
Did you see this post http://www.sakri.net/blog/2009/05/28/detecting-edge-pixels-with-marching-squares-algorithm/
I’ve also got the four pixel version running there, however, it’s not bullet proof, there are a few conditions in which a “straight forward” 4 pixel version fails.
September 1st, 2009 at 6:08 pm
I noticed in FlexSimpleTraceBox you are looking to find class names dynamically. Here are some suggestions:
import flash.utils.getQualifiedClassName;
getQualifiedClassName() returns the name of a class as a String.
Creating a class dynamically:
// SomeClass could be an Object class, too, so can be pretty generic
import some.class.definition.SomeClass;
import flash.utils.getDefinitionByName;
var className:String = “SomeClassName”;
classRef = getDefinitionByName(className) as Class;
imgMC = (new classRef() as SomeClass);
September 17th, 2009 at 4:18 pm
You could also use GlowFilter and then threshold method (for speed) but of course it wouldn’t give you pixel coords, just the transparent outline BitmapData
January 20th, 2010 at 5:18 pm
[...] worden deze tiles omgezet naar 1 bitmap. – Van deze bitmap wordt de rand bepaalt met behulp van deze class van Sakri Rosenstrom. – Omdat de class van iedere pixel een punt maak rond ik de punten af naar de [...]
July 15th, 2010 at 7:20 pm
[...] sakri.net for he’s shape outline algorithm [...]
September 12th, 2011 at 10:55 am
[...] pixels de l’image, et je met tout ça dans un tableau. Puis j’utilise un algo tiré du blog de sakri. Il propose également un autre algo sur la base d’une grille 2×2, mais je n’ai [...]