次の図のように、グレースケール値を含む 2 次元配列を考えてみましょう。
赤い点の間の最適なパスを見つけたいです。高度の意味で、明るい領域を「高く」、暗い領域を「低い」と見なす場合、あるマーカーから別のマーカーまでの暗い「谷」に沿って線を引く必要があります。
私が知っているアルゴリズムの 2 つのカテゴリは次のとおりです。
- 画像処理ベースの「ボトムアップ」操作 (骨格化、流域、究極の浸食など)
- 反復最小化、「トップダウン」操作 (アクティブな輪郭)。
私の質問は：
この問題を解決するための典型的で明確に定義された操作またはアルゴリズムはありますか、または上記の一般的な手法のいくつかから自分で作成する必要がありますか?
最初にスケルトン化を試みますが、グレースケール イメージに対して実行する方法がわかりません。そして、アクティブな輪郭を試すとしたら、示されている画像に似た画像の内部エネルギー関数と外部エネルギー関数は何が良いのだろうかと思います (画像の勾配がベクトル場として機能する可能性があると思います)。
編集: これは、シーム カービング アルゴリズム (ウィキペディアで説明されている) を実装した後の私の作業コードであり、マーカーを通るパスを強制するためのショーハムの提案です。
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;
}