the idea is simple, find the weakest line that cuts\u00a0a bitmap in two and\u00a0preserve one of the halves. it’s also the idea behind an old disco number called seam carving<\/a>\u00a0described here<\/a>\u00a0and there<\/a>,\u00a0that kept many a flash developer\u00a0busy in 2008<\/a>.<\/p>\n to find the weak<\/em> lines, we need a metric to compute the cost of a line and determine which would be the cheapest.\u00a0I used\u00a0the greyscale as the energy table to compute the cost of a path and an 8 pixels kernel as the neighbourhood\u00a0(a very naive\u00a0approach). in the\u00a0case of the quilting,\u00a0we always have a direction\u00a0which to cut and this direction is axis aligned (up, down, left, right)\u00a0a visual explanation of the algorithm would be as follow for the DOWN direction:<\/p>\n this was all good but I realized that the relationships between pixels (the cost to go from one to the next) do not change from one path to the other\u00a0+ there are only 3 choices per direction (=2 bits) each time.\u00a0this means that\u00a0the 4 smallest costs could be encoded on 8 bits,\u00a0stored and looked up which would probably speed up the path finding.<\/p>\n this is how I encode the costs in a compact format to perform quick lookups:<\/p>\n a visual explanation of the last line of the loop (that bit shifts values to pack them in an 8 bits integer)<\/p>\n <\/p>\n here’s the getIndex() method that determines\u00a0the lowest cost between the 3 candidates (the “for each side” above):<\/p>\n once we have this look up table, finding the least energy path is quite trivial ; we\u00a0need to look up the next pixel in the direction we’re searching, read this pixel’s value, shift and\u00a0mask this value to get the portion of the 8 bits that described the next best candidate, move there. which in code and with a sx, sy as the starting coordinates for the path goes like:<\/p>\n depending on the direction, the sx or sy values are linearly incremented or decremented while the other component is incremented using the precomputed values. the mask prevents other bits to interfere\u00a0in the retrieval of the next pixel’s id. for instance masking 10010010<\/strong> with 192 will leave the first 10<\/strong>\u00a0on the left, masking it with 48 will leave the following 01<\/strong>, with 12 you get the next 00<\/strong> and with 3, the last 10<\/strong>. so for this pixel the least energy\u00a0path up would be it’s TR, to it’s right, RI, at the bottom BL and on it’s left, BL.<\/p>\n here a gif of\u00a0the\u00a0results:<\/p>\n less noisy pictures give better results<\/p>\n further filtering\u00a0images ( contrast, sobel, threshold, etc. ) improves the path’s quality and\u00a0is the\u00a0(rough)\u00a0basis for so called\u00a0i<\/a>ntelligent scissors<\/a> <\/em>aka\u00a0livewire segmentation<\/a>.<\/em><\/p>\n as mentioned above, quilting<\/em>\u00a0is a special, unsophisticated use case and I believe this approach should be enough.<\/p>\n here’s a live version on codepen:\u00a0least energy path<\/a><\/p>\n enjoy :)<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" I’m trying to get a proper quilting algorithm to work, one of the important steps is to cleverly “cut” a portion of the image that is going to be drawn on top of another. so I was thinking of how I’d work around this and came up with\u00a0something I thought was worth sharing. the idea … [Read more…]<\/a><\/span><\/p>\n","protected":false},"author":1,"featured_media":527,"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\/2015\/07\/process.png","jetpack_publicize_connections":[],"jetpack_shortlink":"https:\/\/wp.me\/p4oXhx-8s","_links":{"self":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/524"}],"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=524"}],"version-history":[{"count":10,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/524\/revisions"}],"predecessor-version":[{"id":572,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/524\/revisions\/572"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=\/wp\/v2\/media\/527"}],"wp:attachment":[{"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=524"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=524"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/barradeau.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=524"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"process\"](\"http:\/\/barradeau.com\/blog\/wp-content\/uploads\/2015\/07\/process.png\")
1 pick the start pixel & evaluate its color (its greyscale value)
\n2 evaluate the neighbouring pixels’ values & choose the one with the smallest cost (the closest grey value to the current pixel), in the case of a DOWN direction, only the 3 pixels below the current pixel are necessary (BL, BO, BR), if we go to the right, only the 3 pixels to\u00a0the right of the current pixel are necessary (TR, RI, BR) etc.
\n3 store the coordinates & move to the next location, goto 2
\n<\/span>4,5,6 repeat 2 & 3 until you reach the bottom of the picture<\/p>\n\/\/for each pixel, find the shortest energy direction to its 8 neighbours\r\nvar tl, to, tr, le, ri, bl, bo, br;\r\n\r\n\/\/pixel-neighbour distance values\r\nvar vle, vto, vri, vbo;\r\n\r\nfor( y = 0; y < h; y++ ) {\r\n\r\n for (x = 0; x < w; x++) {\r\n\r\n \/\/gets the pixel greyscale value\r\n id = ( ( y * w ) + x ) * 4;\r\n v = data[id];\r\n\r\n \/\/greyscale values of the kernel ( top left, top, top right, left, right, bottom left, bottom, bottom right )\r\n tl = data[ id - w4 - 4 ];\r\n to = data[ id - w4 ];\r\n tr = data[ id - w4 + 4 ];\r\n le = data[ id - 4 ];\r\n ri = data[ id + 4 ];\r\n bl = data[ id + w4 - 4 ];\r\n bo = data[ id + w4 ];\r\n br = data[ id + w4 + 4 ];\r\n\r\n \/\/find best candidate for each direction\r\n vle = getIndex( v, tl, le, bl );\r\n vto = getIndex( v, tl, to, tr );\r\n vri = getIndex( v, tr, ri, br );\r\n vbo = getIndex( v, bl, bo, br );\r\n\r\n \/\/4 best candidates encoded in the green channel (CW from top to left)\r\n data[ id + 1 ] = vto << exports.TOP | vri << exports.RIGHT | vbo << exports.BOTTOM | vle << exports.LEFT;\r\n\r\n }\r\n}<\/pre>\n![\"encode\"](\"http:\/\/barradeau.com\/blog\/wp-content\/uploads\/2015\/07\/encode.png\")
<\/p>\n\/\/return the least energy neghbour\r\nfunction getIndex( value, a,b,c )\r\n{\r\n\r\n var i0 = Math.abs( value - a );\r\n var i1 = Math.abs( value - b );\r\n var i2 = Math.abs( value - c );\r\n\r\n \/\/all 3 pixels have the same value, return random index\r\n if( i0 == i1 && i1 == i2 )return parseInt( Math.random() * 3 );\r\n\r\n \/\/2 pixels have the same value\r\n \/\/randomly return one of the 2 if they are lower than the third value\r\n if( i0 == i1 && i1 != i2 )return i1 < i2 ? ( ( Math.random() < .5 ) ? 0 : 1 ) : 2 ;\r\n if( i1 == i2 && i2 != i0 )return i2 < i0 ? ( ( Math.random() < .5 ) ? 1 : 2 ) : 0 ;\r\n if( i2 == i0 && i0 != i1 )return i0 < i1 ? ( ( Math.random() < .5 ) ? 2 : 0 ) : 1 ;\r\n\r\n \/\/regular case, choose smallest difference\r\n var min = Math.min( i0, Math.min( i1, i2 ) );\r\n if( min == i0 ) return 0;\r\n if( min == i1 ) return 1;\r\n if( min == i2 ) return 2;\r\n\r\n}<\/pre>\nvar path = [];\r\npath.push( sx, sy );\r\n\r\nvar count = direction == exports.LEFT || direction == exports.RIGHT ? w : h;\r\nvar mask = exports[ \"MASK_\" + direction ];\r\n\r\nvar id = ( ( sy * w ) + sx ) * 4;\r\nwhile( count-- )\r\n{\r\n\r\n \/\/get current pixel direction value ( val = 0, 1 or 2 )\r\n var val = ( data[ id + 1 ] & mask ) >> direction ;\r\n\r\n if( direction == exports.TOP ){\r\n\r\n sx += ( val == 0 ? -1 : ( val == 1 ) ? 0 : 1 );\/\/choose least energy path\r\n sy--;\/\/go up\r\n\r\n }\r\n if( direction == exports.RIGHT ){\r\n\r\n sx++;\/\/go right\r\n sy += ( val == 0 ? -1 : ( val == 1 ) ? 0 : 1 );\/\/choose least energy path\r\n\r\n }\r\n if( direction == exports.BOTTOM ){\r\n\r\n sx += ( val == 0 ? -1 : ( val == 1 ) ? 0 : 1 );\/\/choose least energy path\r\n sy++;\/\/go down\r\n\r\n }\r\n if( direction == exports.LEFT ){\r\n\r\n sx--;\/\/go left\r\n sy += ( val == 0 ? -1 : ( val == 1 ) ? 0 : 1 );\/\/choose least energy path\r\n\r\n }\r\n id = ( ( sy * w ) + sx ) * 4;\r\n path.push( sx, sy );\r\n}<\/pre>\n![\"result\"](\"http:\/\/barradeau.com\/blog\/wp-content\/uploads\/2015\/07\/result.gif\")
<\/p>\n![\"blur\"](\"http:\/\/barradeau.com\/blog\/wp-content\/uploads\/2015\/07\/blur.gif\")
<\/p>\n