Detecting edge pixels with Marching Squares Algorithm

Last week a kind individual called "Rothrock" commented on an older blog entry of mine Extract shape outline points from BitmapData and pointed me to the Marching Squares Algorithm.

(Image ruthlessly stolen from wikipedia without remorse)

This does more or less what my "outline point extraction" algorithm was doing, except, with a grid of 4 pixels instead of 9. I nearly choked at the thought of how wasteful my previous approach was. So, I promptly implemented the algorithm in as3, and tested out the speed difference.

Indeed, Marching Squares pwns and humiliates my older implementation, it's 2-3 times faster. This due to the fact that the source bitmap data does not need to be doubled in size, and naturally less pixels require inspection.

However, there are two gaping problems with this 4 pixel grid approach.

1) 'Single pixel vertical and horizontal lines' result in duplicate points

Although the 4grid handles such "single pixel lines" like a champion, it "scans" those points twice (see the line at the bottom of the wikipedia image above). If the goal is to (let's say) extrude this shape, problems just might ensue. So my implementation allows for a parameter which returns only unique points.

2) There is a special case which causes an eternal march. Poor squares.

If you consider the grid variations on that wikipedia page image, the squares march right into our lonely pixel, and keep doing circles Ad infinitum.

The best solution I could come up with, and please don't hesitate to share a better one, was to set a MAX_POINTS value. If the number of discovered points exceeds this, then the algorithm stops, and hands the task over to... wait for it... my old approach :D I refactored this into a class called MarchingSquares9Grid.as . This one has no duplicate pixels by the way, thanks to the double sizing of the source bitmap.

Click the images below to see the algos in action:




On my machine the MarchingSquares runs around 50 fps, but dips whenever the above mentioned exception occurs. The point is that you'll always get the pixel outline, in most cases very fast, in fringe cases a bit slower.

I wrote a MarchingSquares class, which can be used as follows:

Actionscript:
  1. MarchingSquares.getBlobOutlinePointsClockwise(bmd);
  2. //or
  3. MarchingSquares.getBlobOutlinePointsCounterClockwise(bmd);

If speed isn't an issue, use :

Actionscript:
  1. MarchingSquares9Grid.getBlobOutlinePoints(bmd);

Just two considerations:

  • I couldn't be arsed to make the MarchingSquares9Grid run counter clockwise, so there's a method that reverses your Vector if that tickles your perversions.
  • Both of these will require at least a one pixel padding of transparent pixels in your source bitmap. This can be introduced with some bitmapdata magic.

download MarchingSquares.as and MarchingSquares9Grid.as here

Thanks again Rothrock!

Tags: , , , ,

22 Responses to “Detecting edge pixels with Marching Squares Algorithm”

  1. Alan Shaw Says:

    Maybe the potras library would help!

    It’s a port of Potrace from our friends at the Spark project:

    <a href=”http://www.libspark.org/svn/as3/PotrAs/src/com/nitoyon/potras/” source
    samples

    potras wants black-and white rather than transparent-and-opaque, so I convert my input like this:

    public static function traceBitmap(bmd:BitmapData):ClosedPathList
    {
    // convert to form PotrAs needs (transparent to black and opaque to white)
    // and also move data down a pixel:
    var myBmd:BitmapData = new BitmapData(bmd.width, bmd.height, false, 0xff000000);
    myBmd.threshold(bmd, bmd.rect, new Point(0, 1), “==”, 0×00000000, 0xff000000, 0xff000000);
    myBmd.threshold(bmd, bmd.rect, new Point(0, 1), “==”, 0xff000000, 0xffffffff, 0xff000000);
    var closedPathList:ClosedPathList = PotrAs.traceBitmap(myBmd, true);
    myBmd.dispose();
    return closedPathList;
    }

  2. sakri Says:

    Hi Alan, thanks for commenting!

    Somebody pointed out potras to me in my “Extracting, Analyzing and Optimizing a Vector Shape from a BitmapData Shape” post. I downloaded it and tried it out… It’s very impressive, but I have to admit that portions of the code went way over my head.

    I couldn’t extract the code which extracts the blob outline pixels, like MarchingSquares does. It seems this is mingled (probably for performance sake) with the curves and lines generation (I’m probably wrong though, my peek under the hood was superficial). I wanted to grab that to compare performance (still do ;) ).

    I intend to study Potras, particularly the curves analysis/generation, it rocks! I did have some mixed feelings about the results though. Sometimes a character like “K” which has only diagonals and straight lines, would contain curves when extracted with Potras. A goal of mine has been to extrude 3D text, so I can’t use “vector curves” as such, but having this information would make it relatively easy to convert a curve into “best” line segments, which can be extruded.

    lots to explore :)

  3. nicoptere Says:

    hi,
    very neat. congrats !
    last year I had to do quite the same and my take ended up quite like your first version.
    to perform the second step of the Potras algorithm (simplifying), I found an intersting algorithm by Andreas Weber:
    http://www.motiondraw.com/blog/?p=50
    and the demo : http://www.motiondraw.com/md/as_samples/t/LineGeneralization/demo.html

    once you have thet key points, you can recreate smooth curves thanks to any cubic or quadratic curve algorithm ;)

    and btw, the algorithmist is working on how to create one curveTo() instead of hundreds of lineTo() : http://algorithmist.wordpress.com/2009/04/20/spline-to-bezier-preview/

    and thanks to Alan for the link :)

  4. Rothrock Says:

    Glad I could help. I think I know about one of the issues you found.

    For my purposes so far a one pixel line hasn’t happened and even if it did it would still be the contour of that shape. I’ve mostly been using this track fingers and stuff. And I don’t know about you, but under no amount of scaling do my fat little sausage fingers get to be one pixel!

    But issue two is the one about ambiguous patterns that I mentioned in my other post. At least I think it is. Somewhere else I found this idea. If you get one of the ambiguous cases (“0101″ or “1010″ or 5 and 10) you need to know what came before it.

    So in some pseudo code….

    if you’ve got a 5 and it was preceded by 8, 9, or 11 then x+1, else x-1;
    if you’ve got a 10 and it was preceded by 1, 3, or 7 then y+1, else y-1;

    Does that make any sense? It seemed to work for me in my naive AS2 version that I made awhile ago….

    – Rothrock

  5. sakri Says:

    Hi Nicopetre, cheers for the links! I’m really interested in the “smoothing” of the points the motiondraw demo. In my 3D extruded text demo the lines and diagonals are pretty much “clean”, only the curves need work, such smoothing of the positions looks ideal!

    Also, did you blog about that experiment you mentioned (from last year)? I’d be curious to see…

    Rothrock, that sounds good, I might give it a shot. Alan ported a Java implementation of MarchinSquares which I’ve been looking at this morning, seems to solve the problem (and is fast)… More about that once he wakes up :D

  6. Roland Zwaga Says:

    Does your demo have a memoryleak? If I continuously switch between the different algorythms the used memory seems to be constantly increasing.
    Perhaps you could check if it’s just your demo, or perhaps the leak is in the algorythm’s implementation, that way every app that uses the class will have the same problem…
    Other than that, this is pretty cool stuff, thank you for sharing!

  7. HIDIHO! » vectorization v0 Says:

    [...] a nice twitter story… sakri released a marching squares algorithm which is a fast and efficient way to outline rasterized [...]

  8. trop bien le blog » vectorisation v0 Says:

    [...] c’est cool… sakri nous a pondu un savoureux petit algorithme de marching squares qui est le petit frère des marching cubes et qui sert à détourer (vectoriser) des formes dans [...]

  9. lithander Says:

    I just implemented the same algorithm in C#. Have you considered to use a byte instead of string to store the cell type? It should be way faster to lookup a Point by a byte index then by a string key. It’s also faster to calculate. Or are there AS3 specific reasons for your approach?

    private static function getGridStringFromPoint(bmd:BitmapData,position:Point):byte{
    var type:byte = 0;
    if(bmd.getPixel32(position.x+_scan_point0.x,position.y+_scan_point0.y)>0×0)
    type +=1;
    if(bmd.getPixel32(position.x+_scan_point1.x,position.y+_scan_point1.y)>0×0)
    type += 2;
    if(bmd.getPixel32(position.x+_scan_point2.x,position.y+_scan_point2.y)>0×0)
    type += 4;
    if(bmd.getPixel32(position.x+_scan_point3.x,position.y+_scan_point3.y)>0×0)
    type += 8;

    return byte;
    }

  10. delfeld Says:

    I think that the garbage collection is affecting frame rate. If you hammer on one of the buttons, you will see your frame rate drop and the memory spike. Not sure if this matters to your results . . . .

  11. Josh Noble Says:

    Super Cool thanks for sharing.

  12. SF – Flash + Flex + Graphics » Blog Archive » Detecting Edge Pixels with Marching Squares Algorithm Says:

    [...] is a great experiment from Sakri.net.  I applications for this should be amazing.  It’s incredibly simple to use as well.  Say you [...]

  13. davet Says:

    I am in awe, just tried out your approach and it is awsome. Great work

  14. Carey Richardson Says:

    I’ve built a text warping tool for a printing company. I’m using Five3D’s vector text to begin with. I take a control shape that the user can then move around 8 points on, creating several text shape combinations. My techinque goes column by column and gets the original height of the column and compares it the height of the same column in the same. It resizes and positions the new column to match the shape. This works pretty well except that I would like a much cleaner final output, mainly for printing. Could I use your techinque to find the drawing points of my current final bitmap or do you think it would be best to use the technique above. If I use the above technique the points on the top and bottom of the boundry box would only need to be postioned on my top and bottom curves, correct? Is that possible? I really only need to change the shape in the vertical direction, horizontal would just be a bonus.

    Here is what I have:http://dev.mylocker.net/NewControlPanel/index2.html

    Any suggestions are welcome. We are also willing to pay for any help. You seem like the text expert on the web when it comes to creating vector text.

    Thanks for your time,

    Carey

  15. sakri Says:

    Hi Carey,

    That’s a cool tool you’re building! The problem with the approaches that I explored last year is that I never “solved” curve handling. My goal was extracting edges, then converting that to vector information so that I could eventually extrude the text (or shapes) into 3d objects. In these situations, the “curves” are nothing more than short lines following a curve. If you were to use that for print, it would look like crap I’m afraid.

    Given text with vector information, to do such transformation and end up with vector data that can be scaled for printing purposes, I fear, requires some math. I might be able to come up with a solution, but it would take time. You might want to try contacting Jim Armstrong at http://algorithmist.wordpress.com/ . I have no idea about his availability, but I’m sure it would be an easy pickle for him.

  16. Flash, show me your data! | Flash and random() thoughts Says:

    [...] I remember searching around a lot and found attempts by other flash fanatics to trace bitmap shapes into vector data (thinking I may give the workround through bitmap cloning of the drawn work a try),  see for instance just one example Sakri’s blog posting Detecting edge pixels with Marching Squares Algorithm. [...]

  17. RIA wolf » Custom dynamic hit-zones for flash objects Says:

    [...] shape.graphics.lineTo(x,y) to draw the outline you need and fill it. The library i used is located here and the code is here 1234567891011121314    public static function getOutline(b : [...]

  18. CopyQuery | Question & Answer Tool for your Technical Queries Says:

    [...] http://www.sakri.net/blog/2009/05/28/detecting-edge-pixels-with-marching-squares-algorithm/ [...]

  19. sakri Says:

    I’ve made an implementation of this with Javascript on codepen:

    Explanation :
    http://codepen.io/sakri/pen/aIirl

    Demos that use it:

    Ghost Text Effect : http://codepen.io/sakri/pen/zbqti
    Edge Flare Text Effect : http://codepen.io/sakri/pen/vIKJp
    Verlet “Jello” Text Effect : http://codepen.io/sakri/pen/mtlDu

    Source on Github:
    https://github.com/sakri/sakriNetCommonJS/blob/master/commonJS/CircularWander.js

    (this implementation is not bullet proof, there are cases where it fails, if there is interest I can continue work on it).

  20. Josh Grams Says:

    The following blog article suggests a way to resolve the loop: check which way you moved last time (to get to the corner case), and move the opposite direction in half the cases…

    http://devblog.phillipspiess.com/2010/02/23/better-know-an-algorithm-1-marching-squares/#attachment_78

  21. sakri Says:

    Thanks for the heads up Josh!

  22. sakri Says:

    Thanks Josh, I ported that script and it works perfect! http://www.sakri.net/blog/2014/03/31/marching-squares-javascript-canvas-implementation/

Leave a Reply