a short post about the marching squares algorithm,\u00a0a technique mostly used to vectorize the outline of a binary image.<\/p>\n

it’s a very well known &\u00a0very well spread technique, I happened to have some spare time &\u00a0the urge to do something graphic.
\nfor a start let’s look at how things work.<\/p>\n

the idea is to draw a shape through the edges of cells which vertices are “weighted” ( each point of the cell has a value ).\u00a0in our case, we use an image to represent the cells’ grid ( an image is a grid of pixels\u00a0) &\u00a0if we use a binary image (black & white, no greyscale), the weights are the colors of the pixels ( 0 or 1 ) .\u00a0then we need a structuring element<\/em> or kernel<\/em> to scan our grid &\u00a0find the outline.<\/p>\n

the algorithm goes as follow:<\/p>\n

\n
1. apply a threshold to the image to obtain a binary image<\/li>\n
2. find the first non transparent pixel<\/li>\n
3. position the kernel at this location<\/li>\n
4. while the kernel has not reached the starting location\n
   \n
   • move the kernel around<\/em> the shape<\/li>\n
   • store the new location<\/li>\n
   • if the number of iteration is too high, break<\/li>\n
   • else continue<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

     the first step is fairly easy ; when you access the imageData of a given canvas, you can scan all the pixels’ components ( r,g,b or a ) &\u00a0match them against a given value.<\/p>\n

     a good idea though is to reduce the image’s colors\u00a0<\/em>before performing the marching square process\u00a0; this can be done quite simply either beforehand by using a restricted palette or on the fly by applying a simple reduction\u00a0algorithm like:<\/p>\n

     function segment( imageOrCanvas, steps )\r\n{\r\n\r\n    var w = imageOrCanvas.width;\r\n    var h = imageOrCanvas.height;\r\n    var canvas = document.createElement(\"canvas\");\r\n    document.body.appendChild( canvas );\r\n    canvas.width = w;\r\n    canvas.height = h;\r\n\r\n    var context = canvas.getContext(\"2d\");\r\n    context.fillStyle = \"rgba(255,255,255,255)\";\r\n    context.fillRect(0, 0, w, h);\r\n    context.drawImage(imageOrCanvas, 0, 0 );\r\n\r\n    var imgData = context.getImageData(0, 0, w, h);\r\n    var data = imgData.data;\r\n\r\n    for( var i = 0; i < data.length; i += 4 )\r\n    {\r\n        data[i]     = parseInt(parseInt( ( data[i] \/ 0xFF ) * steps + .5 ) * ( 0xFF \/ steps ) );\r\n        data[i + 1] = parseInt(parseInt( ( data[i + 1] \/ 0xFF ) * steps + .5 ) * ( 0xFF \/ steps ) );\r\n        data[i + 2] = parseInt(parseInt( ( data[i + 2] \/ 0xFF ) * steps + .5 ) * ( 0xFF \/ steps ) );\r\n    }\r\n\r\n    imgData.data = data;\r\n    context.putImageData( imgData, 0, 0 );\r\n\r\n}\r\nvar img = document.getElementById( \"me_gusta\" );\r\nsegment( img, 16 );\r\nsegment( img, 8 );\r\nsegment( img, 1 );<\/pre>\n
     which will give you something like<\/p>\n
     <\/a><\/p>\n
     the idea is\u00a0simple, for each component of the color,\u00a0first\u00a0normalize it ( data[ X ] \/ 0xFF ) then\u00a0interpolate between 0 &\u00a0the desired amount of steps ( * steps ) &\u00a0Math.ceil\u00a0it ( parseInt( X + .5 ) \u00a0) then multiply this by the value of a color step ( 0xFF \/ steps ).<\/p>\n
     the lower the number of steps, the easier it should\u00a0be to vectorize, adding a blur step before reduces the noise &\u00a0gives more usable regions.<\/p>\n
     to understand what comes next, you may\u00a0need to understand\u00a0the notion of kernel but there’s this example by Sakri that shows exactly what\u00a0the last step of the algorithm is about: \u00a0http:\/\/codepen.io\/sakri\/pen\/aIirl<\/a><\/p>\n
     as we’re using a simple 2 * 2 kernel, there are very few possibilities\u00a0(\u00a0only 16 actually )\u00a0to move the kernel when\u00a0looking for the direction. here’s a table with the integers 0-15 in binary form, the 4 rectangles below the figure represent the\u00a0bytes ( white=0, black = 1 ) &\u00a0the squares are the kernel itself ; what we’ll use to actually\u00a0determine the direction to move to (represented by\u00a0the arrow above the box).<\/p>\n
     <\/a><\/p>\n
     by sampling the right, bottom & bottom right pixels, this table allows us to quickly determine where we should go next but there are 2 flaws.<\/p>\n
     a minor flaw is that it contains both a 2 * 2 void square ( 0000 ) and a 2 * 2 full square ( 1111 ). this is not that bad ; as we select the first non-transparent pixel, it is usually located on the top left area of the picture so 0000<\/em> will head towards the bottom right & 1111<\/em> will head towards the top left.<\/p>\n
     the second flaw is more embarrassing though, it rises about the values\u00a06 ( 0110 ) & 9 ( 1001 ) and form a diagonal\u00a0pattern. in these cases, there is no way to tell where to send the kernel next, ending up in infinite loops. there are ways to\u00a0deal with this problem\u00a0but\u00a0that’s beyond the scope of this article.<\/p>\n
     to prevent the infinite loops,\u00a0I tried simply not to use those patterns.<\/p>\n
     which failed of course.<\/p>\n
     but it gave me an idea ; why not alter the binary shape so that this pattern doesn’t occur?<\/p>\n
     enter the Morphological operators<\/a>.
     \nthe morphological operators work on binary images & perform very simple\u00a0tests between a pixel & its neighborhood\u00a0to\u00a0determine whether or not to toggle\u00a0<\/em>a pixel.<\/p>\n
     this simple operators fill the smaller gaps that cause most of the infinite loops and applying this during the collection phase ( step 1 of the algorithm ) allows for not having to bother with ambiguous case anymore.<\/p>\n
     let’s take this burning head<\/em>\u00a0I did so it has\u00a0a fair amount of ambiguous cases (click to view full size) especially in the bottom right corner.<\/p>\n
     <\/a><\/p>\n
     trying a brute force marching square will fail, but applying the following kernel:<\/p>\n
     buffer[ id ] = 0;\r\nif (sum != 9 && sum > 1 )\r\n{\r\n    buffer[ id ] = 1;\r\n}\r\n\r\n\/\/then \r\nif( sum > dilation )\/\/dilation default: 5, lower = more greedy\r\n{\r\n    buffer[ i ] = 1;\r\n}<\/pre>\n
     where sum<\/em>\u00a0is the sum of the neighboring pixels’ values, allows to preserve only the outline of the shape and gives the red outline (click to view full size)<\/p>\n
     <\/a><\/p>\n
     if you look closely, you can follow the whole border without finding any ambiguous case + smaller elements (namely single pixels) are being discarded. now\u00a0instead of 16 possibilities, we end up managing only 12 the Lookup table now looks like this:<\/p>\n
     <\/a><\/p>\n
      <\/p>\n
     the burning head<\/em>\u00a0vectorized output looks like this<\/p>\n
     <\/a><\/p>\n
     the blue area is the vectorized outline\u00a0and the orange line & dots is the simplified version of the path. nice isn’t it?<\/p>\n
     here’s the code of\u00a0the marching squares method:<\/p>\n
     \/**\r\n * function that performs a marching squares vectorization\r\n * @param imageOrCanvas an image or a canvas to vectorize, preferably a binary image.\r\n * @param color the color you want to vectorize ( between 0 & 0xFFFFFF )\r\n * @param dilation value used in the dilation step ( 0 - 8 )\r\n * @param maxIterations this prevents infinte loops ( default 10e5 )\r\n * @returns {Array} a series of x, y coordinates\r\n * @constructor\r\n *\/\r\nfunction MarchingSquares( imageOrCanvas, color, dilation, maxIterations )\r\n{\r\n\r\n    dilation = dilation == null ? 5 : dilation;\r\n\r\n    maxIterations = maxIterations == null ? 10e5 : maxIterations;\r\n\r\n    var canvas = document.createElement( \"canvas\" );\r\n    var w = canvas.width = imageOrCanvas.width + 4;\r\n    var h = canvas.height = imageOrCanvas.height + 4;\r\n\r\n    var context = canvas.getContext(\"2d\");\r\n    context.fillStyle = \"rgba(255,255,255,255)\";\r\n    context.fillRect( 0,0, w, h );\r\n    context.drawImage( imageOrCanvas, 2, 2 );\r\n\r\n    var imgData= context.getImageData( 0,0,w,h );\r\n    var data = imgData.data;\r\n    var buffer = new Int8Array(w*h);\r\n    var path = [];\r\n    var first = NaN;\r\n\r\n    var i;\r\n    var r = color >> 16  & 0xFF;\r\n    var g = color >> 8  & 0xFF;\r\n    var b = color  & 0xFF;\r\n\r\n    for( i = 0; i < data.length; i+=4 )\r\n    {\r\n        \/\/ discard if the pixel has a different\r\n        \/\/ color than what we're looking for\r\n        if( data[ i ]       != r\r\n        &&  data[ i + 1 ]   != g\r\n        &&  data[ i + 2 ]   != b )\r\n        {\r\n            data[ i + 3 ] = 0;\r\n        }\r\n        else\r\n        {\r\n            data[ i + 3 ] = 1;\r\n        }\r\n    }\r\n\r\n    \/\/morphological operation extracting the border\r\n    for( i = 0; i < data.length; i+=4 )\r\n    {\r\n        id = i \/ 4;\r\n        var sum = neighborSum( data, i, 4, 3 );\r\n\r\n        buffer[ id ] = 0;\r\n        if (sum != 9 && sum > 1 )\r\n        {\r\n            buffer[ id ] = 1;\r\n        }\r\n    }\r\n\r\n    \/\/morphological dilation\r\n    \/\/this prevents infinite loops\r\n    for( i = 0; i < buffer.length; i++ )\r\n    {\r\n\r\n        sum = neighborSum( buffer, i, 1, 0 );\r\n        if( sum > dilation )\r\n        {\r\n            buffer[ i ] = 1;\r\n        }\r\n\r\n        \/\/ first non transparent pixel ( top left to current pixel )\r\n        if( isNaN( first ) && buffer[ i  ] == 1 )\r\n        {\r\n            first = i - w - 1;\r\n        }\r\n    }\r\n\r\n    if( isNaN( first ) )\r\n    {\r\n        console.log( \"warning: no empty pixels was found, exiting.\" );\r\n        return [];\r\n    }\r\n\r\n    \/\/morphological operators\r\n\r\n    function neighborIds( id, stride )\r\n    {\r\n        stride = stride || 1;\r\n\r\n        var to = id - w * stride;\/\/top\r\n        var tr = to + stride;\/\/top right\r\n        var tl = to - stride;\/\/top left\r\n\r\n        var ri = id + stride; \/\/ right\r\n        var le = id - stride;\/\/left\r\n\r\n        var bo = id + w * stride;\/\/bottom\r\n        var br = bo + stride;\/\/bottom right\r\n        var bl = bo - stride;\/\/bottom left\r\n\r\n        return [ tl, to, tr, le, id, ri, bl, bo, br ];\r\n    }\r\n\r\n    function neighborValues( data, id, stride, offset )\r\n    {\r\n        var values = [];\r\n        var ids = neighborIds( id, stride );\r\n        ids.forEach( function( id )\r\n        {\r\n            values.push( data[ id + offset ] );\r\n        });\r\n        return values;\r\n    }\r\n\r\n    function neighborSum( data, id, stride, offset )\r\n    {\r\n        var values = neighborValues( data, id, stride, offset );\r\n        var sum = 0;\r\n        values.forEach( function( value )\r\n        {\r\n            sum += ( value > 0 ) ? 1 : 0;\r\n        });\r\n        return sum;\r\n    }\r\n\r\n    \/\/marching square\r\n\r\n    var iteration = 0;\r\n    var id = getDirection( buffer, first );\r\n    while( iteration++ < maxIterations )\r\n    {\r\n        id = getDirection( buffer, id );\r\n\r\n        path.push( id % w - 1, parseInt( id \/ w ) - 1 );\r\n\r\n        if( id == first )    break;\/\/done\r\n    }\r\n\r\n    \/\/determine where to move next\r\n    function getDirection( data, id  )\r\n    {\r\n\r\n        var ri  = id + 1;\/\/ right pixel\r\n        var bo  = id + w;\/\/bottom pixel\r\n        var br = bo + 1;\/\/bottom right pixel\r\n\r\n        var x = 0;\r\n        var y = 0;\r\n        var key = data[ id ] << 3 | data[ ri ] << 2 | data[ bo ] << 1 | data[ br ];\r\n\r\n        if( key == 1 || key ==  3 || key == 11  ) x =  1;\/\/ rightt\r\n        if( key == 8 || key == 12 || key == 13  ) x = -1;\/\/ left\r\n        if( key == 4 || key ==  5 || key ==  7  ) y = -1;\/\/ up\r\n        if( key == 2 || key == 10 || key == 14  ) y =  1;\/\/ down\r\n\r\n        return id + x + y * w;\r\n\r\n    }\r\n    return path;\r\n}<\/pre>\n
     it’s intentionally unoptimized for legibility but one would probably merge &\u00a0inline the morphological operator, unfold & reorganize the way getDirection sets the x\/y\u00a0directions,\u00a0reuse the canvas & the buffer instead of recreating it\u00a0a.s.o.<\/p>\n
     and a standard call would go like :<\/p>\n
     function sample( img )\r\n{\r\n\r\n    var out = document.createElement( \"canvas\" );\r\n    out.width = img.width;\r\n    out.height = img.height;\r\n    document.body.appendChild( out );\r\n\r\n    var out_context = out.getContext(\"2d\");\r\n    out_context.drawImage( img,0,0,out.width, out.height );\r\n\r\n    var path = MarchingSquares( img, 0, 5, 10e5 );\r\n\r\n    out_context.fillStyle = \"rgba( 255,0,0,.35 )\";\r\n    out_context.strokeStyle = \"rgba( 255,0,0, .7 )\";\r\n    out_context.lineWidth = 3;\r\n    out_context.beginPath();\r\n\r\n    for( var i = 0; i < path.length; i+=2 )\r\n    {\r\n        out_context.lineTo( path[ i ], path[ i+1 ] );\r\n    }\r\n    out_context.closePath();\r\n    out_context.stroke();\r\n    out_context.fill();\r\n\r\n}\r\n\r\nwindow.onload = function()\r\n{\r\n    var img = document.getElementById( \"my_favorite_unicorn\" );\r\n    sample( segment( img,1 ) );\r\n};<\/pre>\n
     for instance calling this on a unicorn\u00a0picture would give this kind of output<\/p>\n
     <\/p>\n
     one of the greatest benefits of vectorization being to make\u00a0images scale-free,\u00a0<\/em>my favourite results come from smaller images\u00a0; here are 2 32 * 32 pictures vectorized & simplified:<\/p>\n
     <\/a><\/a><\/p>\n
     <\/p>\n
     that’s far from bulletproof and I wouldn’t recommend using it in production but that’s a fun little algorithm to play with. it allows on the fly vectorization of free shapes to use in\u00a0physics games for instance.<\/p>\n
     possible enhancements include, multiple shapes vectorization\u00a0&\u00a0triangulation, using better interpolation techniques than binary, using integral images (?!)\u00a0also, I’d recommend reading this lovely article: Metaballs and marching squares<\/a> by Jamie Wong.<\/p>\n
     that was it!
     \n
     \n<\/a>enjoy :)<\/p>\n","protected":false},"excerpt":{"rendered":"
     a short post about the marching squares algorithm,\u00a0a technique mostly used to vectorize the outline of a binary image. it’s a very well known &\u00a0very well spread technique, I happened to have some spare time &\u00a0the urge to do something graphic. for a start let’s look at how things work. the idea is to draw … [Read more…]<\/a><\/span><\/p>\n","protected":false},"author":1,"featured_media":414,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"sharing_disabled":false,"spay_email":"","jetpack_publicize_message":""},"categories":[3],"tags":[],"jetpack_featured_media_url":"http:\/\/barradeau.com\/blog\/wp-content\/uploads\/2014\/11\/burning_head_vector.png","jetpack_publicize_connections":[],"jetpack_shortlink":"https:\/\/wp.me\/p4oXhx-6j","_links":{"self":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/391"}],"collection":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=391"}],"version-history":[{"count":12,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/391\/revisions"}],"predecessor-version":[{"id":422,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/391\/revisions\/422"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/media\/414"}],"wp:attachment":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=391"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=391"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=391"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}