考虑一个包含灰度值的二维数组，如下图所示：
我想找到红点之间的最佳路径。如果您将高亮度区域的亮区域视为“高”区域，将暗区域视为“低”区域，那么我希望一条线沿着从一个标记到另一个标记的暗“谷”延伸。
我知道的两类算法是：
基于图像处理的“自下而上”的操作（骨架化，分水岭，最终侵蚀等）
迭代最小化，“自上而下”操作（活动轮廓）。
我的问题是：
是否有任何典型且定义明确的操作或算法可以解决此问题，还是我应该使用上述一些通用技术来创建自己的游戏？
我会先尝试骨架化，但是我不知道如何在灰度图像上执行骨架化。而且，如果我要尝试一个主动轮廓，我想知道与所示图像相似的图像的内部和外部能量函数将是什么（我怀疑图像梯度可以充当矢量场）。
Original data (CSV) here。
编辑：这是实现接缝雕刻算法（如Wikipedia中所述）和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;
}
最佳答案
使用动态编程。边上的接缝雕刻使用此方法。您需要在原始数据上使用它，但要确保暗区的值较低，并且仅计算两个红点之间可能的路径。
根据您的目的调整了接缝雕刻：
每个像素都有一个代表能量的数字。您的情况是黑暗还是明亮。
在上方的红点下方开始一行。
向下扫描。对于每个像素，其能量加上其上方三个像素的最小能量总和（保存该值）。您还需要保存谁是他的父亲（具有比当前像素高的最小能量的像素）。
需要对算法进行的另一项更改是，您必须标记起源于上方第一个红色点的像素（也标记上方的点），并且始终对标记的像素赋予优先级。
如果执行所有这些步骤，则下部的红点像素将包含通往上部点的能量最少的路线。
备注：这可以提高性能。
关于image-processing - 在图像中寻找最小能量路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25613106/