c++ - 在 C++ 中使用 Dijkstra 算法对图像进行 Seam Carving

Question

我正在尝试使用 Dijkstra 算法实现 Seam 雕刻。

到目前为止，我已经将图像转换为灰度并使用二维数组，我已经找到了图像的能量函数。现在，要实现 Dijkstra，我需要将此二维数组转换为图形，并为 Dijsktra 函数提供源和汇。

我想知道如何将这个二维数组变成一个图形，因为二维数组是 MxN 的矩阵，其中 M、N 都可以是非常大的数字，可以产生可能有大量图表，并为其确定接收器。

Answer 1

您不必将图像转换成图表。您所要做的就是使用动态规划来计算接缝，然后找到能量最小的接缝。更准确地说，计算 S[i,j](像素 (i,j) 的接缝):

1. 对于第一行，将能量值指定为像素 S[1,j] = E[1,j] 的接缝值

2. 对于下一行，从相邻像素向下传播最小接缝:S[i,j] = E[i,j] + min( S[i-1,j-1], S[i-1,j], S[i-1,j+1] )

3. 从 S 的最后一行中具有最小值的元素开始，通过选择具有最小接缝值的邻居向上爬。存储每个步骤。

4. 您存储的路径是能量最小的接缝。

我还找到了一篇很好的文章，用 MATLAB 源代码彻底解释了算法:

https://kirilllykov.github.io/blog/2013/06/06/seam-carving-algorithm/