Skip To Content

距離累積アルゴリズム

Image Server で利用可

距離累積 (Distance Accumulation) ツールおよび距離アロケーション (Distance Allocation) ツールは、従来のコスト距離ツールを置き換えます。 これらの新しいツールは、セルの中心のネットワークを通るパスを検出する代わりに、連続的累積サーフェスを再構築することによって、すべての方向でコスト距離を計測します。 入力コスト摩擦サーフェスおよびその他のパラメーターから出力累積コスト サーフェスを作成できます。 他のサーフェスと同様に、コンター ライン (等しい累積コストのライン) を追加し、それらを 3D で視覚化し、アロケーション集水域と組み合わせて視覚化することによって、結果をより正確に理解することができます。 通常、このサーフェスを構築する目的は、最急降下のパスである最小コスト パスをプロットすることです。

累積コスト サーフェス

これらのツールによって使用されるアルゴリズムは、傾斜角からサーフェスを再構築します。

サーフェスの再構築のアプローチ

[距離累積 (Distance Accumulation)] ツールおよび [距離アロケーション (Distance Allocation)] ツールを使用して最小累積コストを検出することは、もはやネットワーク問題ではありません。 出力累積コスト ラスターは、未知の形状を含むサーフェスです。 分析範囲内の各セルでの傾斜角のみを前提として、形状を検出する必要があります。 このアプローチは、微分幾何学の概念を使用し、すべての方向での真の距離およびコストを計算します。

累積コスト サーフェスは、次の 3 つの重要な質問に答えます。

  • 距離の関数として、どの位置でコストが急速に増加するか?
  • どのソース セルが、特定のソース以外のセルに最も近いか?
  • ソース以外のセルから最も近いソース セルまでのどのパスをたどるべきか?

出力サーフェスと共に 3D ビューおよびコンター ラインを使用して、これらの質問に対する答えを見つけることができます。 [距離アロケーション (Distance Allocation)] ツールおよび 最適パス (ライン) ツールを使用して、より正確な答えを得ることができます。

下のサブセクションでは、簡単な入力コスト摩擦サーフェスと出力累積コスト サーフェスの関係について説明します。

簡単な入力コスト摩擦サーフェス

コスト = 3 の中心部分、コスト = 2 の中間部分、コスト = 1 の外側部分を含む簡単なコスト摩擦ラスターについて考えます。

同心円としてのコスト摩擦ラスター
中心を示すポイントを含む同心円として、コスト摩擦ラスター入力が示されています。

3D 解釈を使用して、コスト摩擦ラスターと出力累積コスト サーフェスの関係を理解することができます。 セル c でのサーフェスの高さは、入力コスト ラスターからの傾斜角に、それらの傾斜角が有効である距離を掛けた値の合計 (h = 3 * d1 + 2 * d2 + 1 * d3) になります。

コスト摩擦ラスターおよび出力累積コスト サーフェスの関係の 3D 表現
コスト摩擦ラスターと出力累積コスト サーフェスの関係が、3D 表現で示されています。

同じ出力サーフェスの平面図は、コンター ラインが累積コストの変化をどのように描くかを示します。 セルの位置には、傾斜角および傾斜方向の値も表示されます。 傾斜方向 (最急降下の方向) は、コンター ラインに対して常に直角になります。

コンター ラインは、累積コストがどのように変化するかを示す
コンター ラインは、ラスター サーフェスの平面図で累積コストがどのように変化するかを示します。

最小累積コストの組み込み

もう少し複雑な例を以下に示します。 ソース以外のセルでの累積コスト (標高) は、最小コストでそのセルに到着するソースから発生します。

コスト ラスターは、ライト グレーとしての 1 およびダーク グレーとしての 3 という 2 つの値を含みます。 ソース ポイントは、S1 および S2 です。 ソース以外のセル D は、累積コストに関して S1 により近いです。

ソース ポイント S1 および S2 とソース セル D を含むコスト ラスター
入力コスト ラスターに、入力ソース ポイントおよびソース セルが重ね合わされています。

コンター ラインを累積コスト サーフェスに追加すると、ソースから離れて移動するにつれてコストがどのように速く変化するかを視覚化するのに役立ちます。 ソース以外の位置から開始して、コンター ラインに対して直角に移動すると、最も近いソース セルに戻ります。 このパスは、幾何学的に最も近いソースの周囲のコストが高いため、そのソースに行きません。

2 つのソースに関する累積コスト サーフェスの平面図
ソース以外の位置からの、2 つのソース (S1 および S2) に関する最小累積コスト サーフェスの平面図が示されています。

以下の 3D ビューは、同じ最小累積コスト サーフェスを示しています。 このサーフェスは、コストが高いソースの周囲で傾斜が非常に急になっています (コストがより急速に累積する)。 このソースは、このソースに非常に近い最小コスト サーフェスのみを保有しています。 分析範囲内の他のすべてのセルでは、左側にあるソースによってサーフェスが保有されています。

最小累積コスト サーフェスの 3D 表現
2 つのソースに関する最小累積コスト サーフェスの 3 次元表示が示されています。

集水域としてのアロケーション領域

入力コスト摩擦サーフェスおよび出力累積コスト サーフェスがさらに複雑になっても、コンター ライン、傾斜角、および傾斜方向を使用して累積コスト サーフェスの動作を理解することができます。 加えて、ソースの周囲のアロケーション領域は、累積コスト出力サーフェス上の集水域として機能します。 アロケーション領域内のすべての最小コスト パスは、同じソースに流れます。 下の例では、アロケーション集水域を、コンター ラインおよび 3D ビューと組み合わせています。

コンター ライン (この例では、等時線) を使用して、この移動時間サーフェスなどのより複雑な累積コスト サーフェスを、2D および 3D で正確に視覚化することができます。

2D でコンター ラインを含む累積コスト サーフェス
2D 平面図でコンター ラインを含む累積コスト サーフェスが示されています。

以下の図では、同じサーフェスの 3D ビューが示されています。 背景に含まれている崖は、河川の存在によって生じるバリアです。

3 次元表示での累積コスト サーフェス
累積コスト サーフェスの 3 次元表示が示されています。

以下の図に示されているように、最小コスト パスは、アロケーション ゾーン (集水域) を定義するソースに向かって累積コスト サーフェスを下に流れています。

最小コスト パスの流れの 3 次元表示
累積コスト サーフェスの下方への最小コスト パスの流れの 3 次元表示が示されています。

サーフェス再構築アルゴリズムは、ネットワーク アルゴリズムの拡張です。

各セルでの最も急な傾斜角の値の知識のみを使用して累積コスト サーフェスを検出するために、サーフェス再構築アルゴリズムを使用することもできます。 このアルゴリズムは、従来のコスト距離ツールによって使用される最短パス アルゴリズムに類似していますが、ネットワークの 8 つの方向のいずれにも従わない累積コストの近似値を提供するための追加ステップを含んでいます。 この追加ステップは、アイコナール ステップと呼ばれます。 以下では、簡単に説明します。詳細については、Sethian (1999 年) をご参照ください。

文脈においてこのステップを理解するために、下の中心セルの累積コストが z5 になっています。 隣接セルの累積コスト zi がすべてわかっていると仮定します。 入力コスト ラスターから、中心セルでの傾斜角の値 S もわかっています。

中心セルの高さを含む 3 x 3 グリッド
図 4。 サーフェス再構築アルゴリズムは、中心セルでの入力コスト摩擦ラスターからの傾斜角を、隣接セルの仮定された既知の高さ zi と共に使用して、高さに関する複数の近似を行うことによって、中心セルの高さ z5 を計算します。

たとえば、z5 の 1 つの近似は、z3 と z5 の間の対角線に沿ったものであることができ、下の図に示されているように、z5 = z3 + 1.4 * セルサイズ * S となります。 この場合、S (入力コスト ラスターからの値) は、三角形 abc の傾斜角と解釈されます。 そのようなすべてのネットワーク型近似の場合、z5 での傾斜角は、z5 での累積コストを近似するためのみに使用されます。 これは、セルのペアからのコストの平均を使用する従来のネットワーク アルゴリズムとは異なっています。

1 つのセルに関する対角線の傾斜角の計算
図 5。 対角線の計算ステップが示されています。 入力コスト摩擦サーフェスからの傾斜角は、三角形 abc の斜辺の傾斜角と解釈されます。

下の一連の 3 つの図に示されているように、既存の高さのペアを使用する 4 つを含む、8 つのネットワークの近似を行うことができます。 この例では、セル z5 の位置での入力コスト ラスターの値が、2 つの既知のポイントおよび未知の標高 z5 を通過する平面の勾配の大きさ S として解釈されます。 この関係から、z5 について解くことができます。 これがアイコナール ステップです。

アイコナール ステップの入力
図 6。 アイコナール ステップの入力が示されており、2 つの高さ z6 および z8 がわかっています。

平面の勾配の大きさが計算されます。

計測値 S は平面の勾配の大きさです
図 7。 コスト ラスターからの計測値 S は、2 つの既知の標高 z8 および z6 と未知の標高 z5 を通過する平面の勾配の大きさです。

勾配の方向が計算されます。

勾配の方向は傾斜方向 (バック方向) の値です
図 8。 勾配の方向は、セル z5 の傾斜方向 (バック方向) の値です。

アイコナール ステップは、バック方向と呼ばれる z5 での傾斜方向情報も復元します。

これで、中心セルでの標高に関して、12 個の近似値が存在しています。 これらの近似値のうちの最小値が、中心セルの累積コスト値 z5 として選択されて、記録されます。 バック方向ラスターを要求した場合、(前の段落で説明した) 勾配の傾斜方向が、出力バック方向ラスター内の対応する位置に記録されます。

このプロセスは、近接セルのうちの 1 つの新しい標高値が取得されるたびに、セルに対して繰り返されます。 最終的に、標高値の変化が止まり、アルゴリズムが終了します。 初期の標高は、ソースから提供され、ゼロであるか、ソースごとの初期累積値になります。 その他の初期標高値は、無限大に設定されます。 このアルゴリズムの詳細は、Sethian (1999 年) において説明されています。 このアルゴリズムの Esri の実装は、Sethian (1999 年) および Zhao (2004 年) において説明されている手法の組み合わせです。

要約すると、これらのステップは、各セルの傾斜角から開始し、累積コスト サーフェスの標高と最急降下の方向の両方を再構築します。

最小コスト パス

最小コスト パスは、累積コスト サーフェス上の最も急な下り坂の方向をたどります。 1 つのセルのその方向が、上の図 8 に示されています。 出力バック方向ラスターは、セルごとにその方向を格納します。 バック方向ラスターを入力として [最適パス (ライン) (Optimal Path As Line)] ツールを使用し、任意のソース以外のセルから開始して、それらのパスをプロットすることができます。

下の図では、右上にある青色のソース以外のセル d から開始して、下のソース セル s に移動する曲線の最小コスト パスが示されています。 d は上部のソースに幾何学的に近いですが、そのソースの周囲の高いコストのため、曲線のパスをたどって s に移動するほうが、コストが低くなります。

目的地 d は、青色の四角形です。 このパスは、最も低いコストで到達することができるように、高コストのソースの周りで曲がりながら、より低いコストのエリアを通ってソースに移動します。

円は、最小コスト パスの構築を示しています
図 9。 図 3 の入力コスト摩擦サーフェスから構築された累積コスト サーフェスを使用する最小コスト パスの構築が示されています。

直観に反した名前に見えるかもしれませんが、最小コスト パス構築の入力位置は、目的地と呼ばれます。 ソースは、サーフェスを構築するために使用されており、最小コスト パスが終了する位置です。

サーフェスの周囲のアロケーション ゾーンは、目的地からの最小コスト パスが、上部のソースではなく下部のソースに移動することを、さらに明確にします。 次に、選択されたエリアが拡大され、出力バック方向ラスター内のセル値がどのように解釈されるかを示します。

四角形で強調された分析範囲の位置
分析範囲の位置がボックスで示されています。

バック方向セルの中心を接続する格子がダーク グレーで示されています。 セルの境界がライト グレーで示され、セル値が方位角の矢印で示されています。 最小コスト パスは、格子のラインと交差するときに、移動方向での最も近いバック方向セルの方位角を使用して、方向を更新します。 セル a の隣にある上部のパスの頂点で、その頂点から離れるラインを方向づけるために、a に格納されているバック方向の値が使用されます。 次に交差する格子のラインは、セル b に最も近いため、2 番目の頂点から出るために方位角が使用される、などとなります。

バック方向ラスターのセル値の格子
バック方向ラスター内のセル値の解釈方法についての格子の表示が示されています。

要約すると、最小コスト パスは、セルの中心から開始してセルの中心で終了します。 その他のパスの頂点は、セルの中心を通る水平ラインおよび垂直ラインの格子上のどこかに存在することができます。

有効傾斜角の計算

前のセクションで説明した傾斜角の値は、厳密には入力コスト摩擦ラスターから発生しません。 複数のその他の入力があり、それらが組み合わさって、サーフェス再構築アルゴリズムによって使用される有効傾斜角を決定します。 セルを通る運動方向、およびソースから、またはソースへの移動方向を考慮することの重要性などの、これらの入力の詳細な説明は、他のトピックに記載されています。 ここでは、サーフェス再構築アルゴリズムによる入力の使用方法に重点を置きます。 入力は次のとおりです。

  • コスト摩擦入力 C
  • サーフェス入力 S
  • ソース コスト乗数 M
  • 水平方向ファクター関数 HF
  • 垂直方向ファクター関数 VF

再構築アルゴリズムによって使用される有効傾斜角の一般的な形式は次のとおりです。

有効傾斜角 = C * S * M * HF * VF

次に、この値にセル サイズまたは sqrt(2) * セル サイズを掛けて、既存の高さを加算し、ネットワークの方向の高さの推定値のうちの 1 つを取得します。 アイコナール ステップでは、高さの推定値を取得するために、有効傾斜角のさらに複雑な関数が使用されます。

有効傾斜角は、累積コストを直線距離で割った単位 (比率) を持つ必要があります。 たとえば、累積コストサーフェスが、移動時間を時間単位で計測し、解析のセル サイズがメートル単位である場合、有効傾斜角は、時間/メートルの単位を持つ必要があります。

有効傾斜角は複数の項の積であるため、個々の項の単位が組み合わさって、正しい有効傾斜角の単位になることを保証する必要があります。 たとえば、単純なコスト摩擦ラスターのみを使用して、方向と無関係な移動時間を表す場合、コスト摩擦ラスターのセル値は、時間/メートルの単位を持つ必要があります。 または、垂直方向ファクター関数としてトブラーのハイキング関数も使用する場合、そのハイキング関数は時間/メートルの単位を持つことになり、コスト摩擦サーフェスが存在する場合、コスト摩擦サーフェスは単位のない重みとして解釈される必要があります。 その場合、コスト摩擦セル値をそのように解釈できるということを保証する必要があります。 言い換えると、垂直方向関数とコスト摩擦が両方とも比率になることはできません。

サーフェス入力 (S) を直接制御することはありません。 サーフェス入力 (S) は、セルの中心間の実際の 3D サーフェスの距離をカバーするためにセル サイズを引き伸ばす、単位のない重みです。 図 2 では、サーフェス再構築アルゴリズムは、中心セルでの入力コスト摩擦ラスターからの傾斜角を、隣接セルの仮定された既知の高さと共に使用して、高さに関する複数の近似を行うことによって、中心セルの高さ z5 を計算します。

バリアは接続されたエッジ

[距離累積 (Distance Accumulation)] ツールおよび [距離アロケーション (Distance Allocation)] ツールでのバリアは、通過できない入力セルです。 バリアは、計算時に NoData のセルとして表されます。 バリアは、ツールのパラメーターとして明示的に指定するか、他のラスター入力 (コスト摩擦ラスターなど) のいずれかで、NoData 値として暗黙的に指定します。 最初のケースでは、バリアはラスター化され、コスト ラスター内の NoData に変えられます。 サーフェス再構築アルゴリズムは、バリア セルの高さの推定値を下げることができないため、代わりにバリアの周囲の経路を検出します。

サーフェス再構築アルゴリズムは、セルの 8 つの隣接セルをすべて使用して、高さの推定値を検出します。 角で接続されたバリアである隣接セルは、高さの推定値を取得するために対角線の隣接セルが使用されるのを妨げません。 下の図では、セル z2 および z6 がバリアである場合でも、z3 から z5 の高さの推定値を取得できます。

角で接続されたバリアを含むグリッド

z2 および z6 が線形バリア フィーチャ (運河や河川など) の一部になるよう意図された場合、この動作はバリアの意図を無効化します。 これを防ぐために、サーフェス再構築アルゴリズムは、バリア以外のセルを接続することよりも、バリア セルを接続することを優先します。 つまり、すべての既存のバリア セルがエッジを共有することを保証するために、追加の NoData セルがコスト ラスターに導入されます。 上の図では、セル z5 またはセル z3 のいずれかもバリア セルになります。

解析でバリアを使用する場合、この動作を考慮し、それに応じてバリアの周囲の意図した接続性が維持されるように、解析セル サイズを調整してください。 線形フィーチャをバリアとして、または隣接するバリア セルによって中断されない線形ネットワークとして使用するために、フォーカル統計 ツールを使用して線形フィーチャのラスター バージョンの密度を高くすることができます。

参考文献

Douglas, D. "Least-cost Path in GIS Using an Accumulated Cost Surface and Slopelines", Cartographica: The International Journal for Geographic Information and Geovisualization, 1994, Vol. 31, No. 3, DOI: 10.3138/D327-0323-2JUT-016M

Goodchild, M.F. "An evaluation of lattice solutions to the problem of corridor location", Environment and Planning A: Economy and Space, 1977, vol. 9, pages 727-738

Sethian, J.A. Level Set Methods and Fast Marching Methods (Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science) 2nd Edition, Cambridge University Press, 2nd edition (June 1, 1999)

Warntz, W. "Transportation, Social Physics, and the Law Of Refraction", The Professional Geographer, 1957, Vol. 9, No. 4, pp. 2-7.

Zhao, H. "A fast sweeping method for Eikonal equations", Mathematics of Computation, 2004, Vol. 74, No. 250, pages 603-627