3 ms·
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 seam
by thetrainfold 7y ago
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?
- Bjartr 7y agoThe algorithm is re-run, but is usually implemented using a dynamic programming approach to avoid completely recalculating every seam from scratch.
- akdas 7y agoI'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.
- akdas 7y agoGood 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.