image-processing - 在图像中寻找能量最少的路径

Question

考虑一个包含灰度值的二维数组，如下图所示:

我想找到红点之间的最佳路径。如果您认为亮区在海拔意义上是“高”而暗区是“低”，那么我想要一条线沿着黑暗的“山谷”从一个标记延伸到另一个标记。

我知道的两类算法是:

1. 基于图像处理的“自下而上”操作(骨架化、分水岭、最终侵 eclipse 等)
2. 迭代最小化，“自上而下”操作(事件轮廓)。

我的问题是:

Is there any typical and well-defined operation or algorithm to solve this problem, or should I create one myself from some of the generic techniques mentioned above?

我会先尝试骨架化，但我不知道如何在灰度图像上执行它。而且，如果我要尝试一个事件轮廓，我想知道对于与所示图像相似的图像，什么是好的内部和外部能量函数(我怀疑图像梯度可以充当矢量场)。

Original data (CSV) here .

编辑:这是我在实现接缝雕刻算法(如维基百科中所述)和 Shoham 建议强制路径通过标记后的工作代码:

private double[] MinimumEnergyBetweenMarkers(double[,] array, Point upper, Point lower)
{
    int rows = array.GetLength(0);
    int cols = array.GetLength(1);

    // Points might come in another format, whatever
    int iupper = upper.Y;
    int jupper = upper.X;

    int ilower = lower.Y;
    int jlower = lower.X;            


    // First, scan down from upper marker,
    // storing temp results in a second array
     double[,] new_array = new double[rows, cols];
    FillArrayWithNans(ref new_array, double.NaN);
    new_array[iupper, jupper] = array[iupper, jupper];
    int i = iupper;

    while (i++ < ilower + 1)
    {
        for (int j = 1; j < cols - 1; j++)
        {
            var valid_neighbors = new List<double>()
            {
                new_array[i-1, j-1],
                new_array[i-1, j],
                new_array[i-1, j+1]
            }.Where(v => !Double.IsNaN(v));
            if (valid_neighbors.Count() > 0)
                new_array[i,j] = array[i,j] + valid_neighbors.Min();
        }
    }

    double[] shortest_path = new double[rows];
    FillArrayWithNans(ref shortest_path, double.Nan)

    shortest_path[ilower] = jlower;
    i = ilower;
    int jj = jlower;

    // offsets might be wider to allow for "steeper" paths
    var offsets = new int[]{-1,0,1};

    while (i-- > iupper)
    {
        double minimum = double.MaxValue;
        int jtemp = jj;
        foreach (int offset in offsets)
        {
            if (jj > 0 && jj < cols - 1)
            {
                double candidate = array[i-1, jj+offset];
                if (candidate < minimum)
                {
                    minimum = candidate;
                    jtemp = jj+offset;
                }
            }
        }
        jj = jtemp;
        shortest_path[i] = jj;
    }

    return shortest_path;
}

Answer 1

使用动态规划。 Seam Carving 在边缘上使用此方法。您需要在原始数据上使用它，但要确保暗区的值较低，并且您只计算两个红点之间可能的路径。

根据您的目的调整的 Seam Carving:

1. 每个像素都有一个数字来表示能量。在您的情况下，黑暗或明亮。

2. 从上方红点下方的一行开始。

3. 向下扫描。对于每个像素，将他的能量加上他上方三个像素的最小能量总和(保存此值)。您还需要保存谁是他的父亲(当前像素上方能量最小的像素)。

4. 需要对算法进行的另一项更改是，您必须标记源自上方第一个红点的像素(也标记上方的点)，并始终优先考虑标记的像素。

如果您遵循所有这些步骤，下方的红点像素将包含通往上方点的最少能量路径。

备注:这可以提高性能。