Seam carving is fascinating, and especially the first version of the algorithm really really simple to implement. However, that algorithm introduces certain art

Seam carving is fascinating, and especially the first version of the algorithm really really simple to implement. However, that algorithm introduces certain artefacts - the boat in this picture[0] makes it pretty obvious. The cause of these artefacts are mainly that the original algorithm did not look at energy that was introduced by removing a seam: each time this happens, the pixels adjacent to this seam become neighbours, which creates a new energy gradient. So sometimes removing the least-energy seam would produce a net increase in energy. The original authors of the seam carving paper realised this[1], which lead to the obvious fix for it: instead of only looking at the current energy of a picture, and removing the least-energy seam, look how much of a net energy difference the removal of a seam would make, aka "forward energy". A few years later another paper came out that used "forward gradient difference maps" which supposedly work even better, but to be honest the formulas described in that paper are too complex for me to understand[2]. Conceptually though, I think they just extended the original energy function (a simple Sobel operator[3]) with a few other ones that include orientation and others: > The energy function measures the curvature inconsistency between the pixels that become adjacent after seam removal, and involves the difference of gradient orientation and magnitude of the pixels. Our objective is to minimize the differences induced by the removed seam, and the optimization is performed by dynamic programming based on multiple cumulative energy maps, each of which corresponds to the seam pattern associated with a pixel. The proposed technique preserves straight lines and regular shapes better than the original and improved seam carving, and can be easily combined with other types of energy functions within the seam carving framework With that in mind, it shouldn't be that complicated to come up with more improvements to seam-carving: just stack on different energy functions (either forward or current energy), and compute the ideal seam based on the (weighted) sum of them. [0] https://user-images.githubusercontent.com/883386/35498498-3c0f182c-04d7-11e8-9af8-695bc071e0f1.jpg https://user-images.githubusercontent.com/883386/35498498-3c... [1] http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf [2] http://cvlab.postech.ac.kr/~hyeonwoonoh/acmmm2012.pdf http://cvlab.postech.ac.kr/~hyeonwoonoh/acmmm2012.pdf [3] https://en.wikipedia.org/wiki/Sobel_operator https://en.wikipedia.org/wiki/Sobel_operator