I held a workshop once where people implemented this (and other image algorithms). The end result can be seen here [0], and the tasks here [1] (but in Norwegian). Can click the "run seam carving" button to watch it unfold step by step.<p>[0]: <a href="https://matsemann.github.io/image-workshop/" rel="nofollow">https://matsemann.github.io/image-workshop/</a>
[1]: <a href="https://github.com/Matsemann/image-workshop" rel="nofollow">https://github.com/Matsemann/image-workshop</a>
This was a homework assignment in Robert Sedgewick's Algorithms course on Coursera!<p><a href="https://www.coursera.org/learn/algorithms-part1" rel="nofollow">https://www.coursera.org/learn/algorithms-part1</a><p>Great class and fun assignment!
It feels like those images of the energy could have been improved by plotting the log of the energy. It would allow us to see changes at the low end where the decisions are being made.
This brings to mind the Viterbi algorithm that calculates the most likely sequence of events in a hidden Markov model (Markov model itself is just a state machine on a graph with weighed edges, where each weight on a state transition is represented as a probability of that transition).<p>It's essentially bases to the same algorithm: you can eliminate sequences if they lead to the same event that is already part of a solution, but with lesser probability. The amount of paths would be exponential, but the ability to eliminate them keeps it polynomial. That really brings forth the beauty of dynamic programming.
There's also the approach that calculates the energy of the resulting image as opposed to the seam being removed, which allows the seams to pass through objects where doing so will minimize artifacts.<p>Paper: <a href="http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html" rel="nofollow">http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html</a><p>GitHub: <a href="https://github.com/axu2/improved-seam-carving" rel="nofollow">https://github.com/axu2/improved-seam-carving</a>
Cool to see this popping up again. It always impresses if you haven't seen it before and is a cool algorithm to work through.<p>The original paper was discussed on slashdot and back at that time I was inspired to build a little GUI around an open source algorithm implementation to play with my Qt skills.<p>It allows you to shrink, expand and "mask out" regions you don't want touch etc.<p>Still available on Google Code archive:<p><a href="https://code.google.com/archive/p/seam-carving-gui/" rel="nofollow">https://code.google.com/archive/p/seam-carving-gui/</a>
If you like DP imaging applications like this, this old Microsoft Research technical report is neat: it uses DP to merge frames from two webcams placed left and right to synthesize a view in the middle, like having a webcam in the middle of your monitor. The DP is interesting because it has penalities set up assuming planar content because faces are pretty flat and in front of the cameras. Link: <a href="https://www.microsoft.com/en-us/research/publication/efficient-dense-stereo-and-novel-view-synthesis-for-gaze-manipulation-in-one-to-one-teleconferencing/" rel="nofollow">https://www.microsoft.com/en-us/research/publication/efficie...</a>
I remember implementing this for a class years ago, and then the professor suggested doing the inverse to try to expand the image width. The idea was you would duplicate the lowest energy seam... but all that did was create a lot of repeats of the same seam.<p>I never did finish that weird idea, but I probably needed to try something like increasing the energy of the chosen seam (and its duplicate)... I may try that again, just because I'm curious what would happen.
This is also known as "liquid rescale" and there is (was?) a gimpl plugin for it. It last updated in 2013 or so. After that the developer was hired by Adobe to work on Photoshop.
Really interesting, thanks for sharing!<p>I believe there's a typo here: "the time complexity would still be 𝑂(𝑊)" should be "the space complexity would still be 𝑂(𝑊)".