least energy path

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 something I thought was worth sharing.

the idea is simple, find the weakest line that cuts a bitmap in two and preserve one of the halves. it’s also the idea behind an old disco number called seam carving described here and there, that kept many a flash developer busy in 2008.

to find the weak lines, we need a metric to compute the cost of a line and determine which would be the cheapest. I used the greyscale as the energy table to compute the cost of a path and an 8 pixels kernel as the neighbourhood (a very naive approach). in the case of the quilting, we always have a direction which to cut and this direction is axis aligned (up, down, left, right) a visual explanation of the algorithm would be as follow for the DOWN direction:

process1 pick the start pixel & evaluate its color (its greyscale value)
2 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 the right of the current pixel are necessary (TR, RI, BR) etc.
3 store the coordinates & move to the next location, goto 2
4,5,6 repeat 2 & 3 until you reach the bottom of the picture

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 + there are only 3 choices per direction (=2 bits) each time. this means that the 4 smallest costs could be encoded on 8 bits, stored and looked up which would probably speed up the path finding.

this is how I encode the costs in a compact format to perform quick lookups:

a visual explanation of the last line of the loop (that bit shifts values to pack them in an 8 bits integer)

encode

 

here’s the getIndex() method that determines the lowest cost between the 3 candidates (the “for each side” above):

once we have this look up table, finding the least energy path is quite trivial ; we need to look up the next pixel in the direction we’re searching, read this pixel’s value, shift and mask 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:

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 in the retrieval of the next pixel’s id. for instance masking 10010010 with 192 will leave the first 10 on the left, masking it with 48 will leave the following 01, with 12 you get the next 00 and with 3, the last 10. so for this pixel the least energy path up would be it’s TR, to it’s right, RI, at the bottom BL and on it’s left, BL.

here a gif of the results:

result

less noisy pictures give better results

blur

further filtering images ( contrast, sobel, threshold, etc. ) improves the path’s quality and is the (rough) basis for so called intelligent scissors aka livewire segmentation.

as mentioned above, quilting is a special, unsophisticated use case and I believe this approach should be enough.

here’s a live version on codepen: least energy path

enjoy :)

 

2 Comments

  1. tlecoz

    Interesting !
    I need to read the beginning maybe 5 times before I understood what you tryed to do (the results are not obvious when you just look at the demo without read the beginning again and again ) , but it’s interesting ! – and when you know what happen, it looks great ! (but I would like to see more example to be totally sure it works as great as expected, because it’s not so obvious :) )

    What is the final goal of that stuff ?

  2. tlecoz

    (Sorry I didn’t see the live version)

    To be honest, I ‘m not sure to understand your results.
    The results are interesting because something is working, and sometime it works even great, but sometimes the path should be simple and it’s not.

    I may be wrong but I think the issue you got in your “path finder” come from the fact you don’t store the previous angle between the “previous-previous-point” and the “previous point” . From that angle, you should define the starting value of “i” in your loop concerning the neightboors , then you ll be sure to move all the time using the less iteration possible (because the motion becomes logical, and because the motion is logical you will dodge some issues in the final result ). You also could try to optimise the path you got and rework from that optimised path.

    What is the final goal ? (bis)

    I may try, it’s definitly interesting !

Leave a Reply

Your email address will not be published. Required fields are marked *