使用动态规划查找最优 seam,以竖直 seam 为例:
可以看成图论里的最短路径问题,把每个像素点看成一个节点,像素 (i, j) 连通的边只有上一行的左、中、右和下一行的左、中、右像素,那么我们要找的就是从图像第一行像素出发到图像最后一行像素的最短路。
可以用经典的最短路算法来求解,然而这里可以用动态规划进行更高效的求解:设图像宽、高分别为 W,H,记 M[i][j] 为到 (i, j) 像素点的最优 seam 的像素能量和,那么我们只要找到最后一行里能量最小的像素,即 min(M[H-1][j]),然后回溯即可以找到最优 seam。
放大:插入 k 条新 seam,那么先一次性找到 k 条最优 seam,然后按反向顺序逐一取左右 seam 平均插入到图像中即可。