|
|
|
|
|
|
by cgearhart
2138 days ago
|
|
|
No, it’s a greedy algorithm. I don’t think it would be in P to solve it globally. Naively you could perform any graph search to find minimum total cost to depth N where the cost between nodes is the energy removed. In that case it’s exponential. Because the seam is defined such that each pixel in the next row is within 1 column of the pixel in the preceding row, you can reuse all the calculations except for a pyramid shaped area around the last removed seam (in the worst case). However, that area is on the order of half the total number of pixels, so it doesn’t save _too_ much to reuse the other half. |
|
|
> in the worst case
I wonder if typical data is more forgiving. If, for example, we cut an optimal seam down the column n=x, and the DP algorithm tells us that the best seams starting at (0,x-1) and at (0,x+1) are also column seams, the next iteration can happen in linear time in the number of rows. (Plus number of columns -- pessimistically -- if the next-optimal seam isn't "nearby".)
Basically, you're checking the things that crossed the old seam, and I'd guess that'd happen often enough, but I don't know how far the effects would typically spread. Maybe it would work worse in "sparse" images like blue sky, and better in "noisier" images like forests and crowds and dogs' fur.
I'm not sure how much cost that data-dependence would incur though. Might not be worthwhile.