Hacker News Reader

Comment by thetrainfold | Hacker News Reader

Question about the algorithm:

Is the algorithm run from scratch each time a seam is removed? I.e. energy function computed again on the resized image, all seams recomputed, then only the lowest energy seam is removed.. and repeat.

Or are all the seams from the first calculation used for resizing?

View on HN

Good question. I talked about it in my previous article, but the gist is I compute the energy (or costs in this case), then use dynamic programming to find the new lowest energy seam each time. This allows a subsequent seam to pass through an earlier seam, as seams are found based on the latest images, where pixels have been pushed together from previous removals.

However, you'll notice that the costs are only changed in a small area around the removed seam, so if I optimized the process, I could avoid recomputing costs for the majority of pixels.

The algorithm is re-run, but is usually implemented using a dynamic programming approach to avoid completely recalculating every seam from scratch.

I'm using dynamic programming, but I'm still computing seams from scratch on each "frame" (each time I resize the image). Dynamic programming is useful for solving the seam finding problem on each frame, but it's an orthogonal concern to what computation can be saved on the next frame.

For illustrative purposes, I didn't optimize storing the cost data across frames, but that's something I could do.

Reply on news.ycombinator.com