流域（画像処理）

画像処理の研究では、分水界はグレースケール画像上で定義される変換です。この名前は比喩的に、隣接する流域を分ける地質学上の分水界または分水界を指します。分水界変換では、操作対象の画像を地形図のように扱い、各ポイントの明るさがその高さを表し、尾根の頂上に沿って走る線を見つけます。

流域にはさまざまな技術的な定義があります。グラフでは、流域線はノード、エッジ、またはノードとエッジの両方のハイブリッド線で定義されます。流域は連続領域で定義されることもあります。^[1]流域を計算するためのさまざまなアルゴリズムもあります。流域アルゴリズムは、主にオブジェクトのセグメンテーション、つまり画像内のさまざまなオブジェクトを分離する目的で画像処理に使用されます。これにより、オブジェクトの数え上げや、分離されたオブジェクトの詳細な分析が可能になります。

• 
  勾配の大きさの緩和
• 
  勾配振幅画像
• 
  勾配の分水嶺
• 
  勾配の分水嶺（起伏）

地質学では、流域とは隣接する集水域を分ける境界のことです。

このアイデアは、1979年にS. BeucherとC. Lantuéjoulによって導入されました。^[2]基本的なアイデアは、起伏の各地域最小値に水源を配置し、水源から起伏全体を洪水にし、異なる水源が出会う場所に障壁を構築するというものでした。結果として得られる障壁のセットは、洪水によって流域を構成します。このアルゴリズムには、その後、Priority-Floodと呼ばれるいくつかの改良が加えられました。^[3]

直感的に、地形の起伏に落ちた水滴は、「最も近い」最小値に向かって流れます。「最も近い」最小値とは、最も急な下り坂の経路の終わりにある最小値です。地形の観点から言えば、これは、ポイントがその最小値の集水域にある場合に発生します。前の定義では、この条件は確認されていません。

直感的に言えば、分水界とは、一滴の水が明確な最小値に向かって流れ落ちることのできる局所的な最小値の分離です。この直感的なアイデアの形式化は、^[4]でエッジ重み付きグラフの分水界を定義するために提供されました。

S. BeucherとF. Meyerは、ウォーターシェッド法のアルゴリズム的なピクセル間実装を導入し、^[5]以下の手順を示しました。

1. 各最小値に個別のラベルを付けます。ラベル付けされたノードでセットS を初期化します。
2. Sから最小高度Fのノードx を抽出します。つまり、F ( x ) = min{ F ( y )| y  ∈  S } です。 xに隣接するラベルのない各ノードyにxのラベルを割り当て、y をSに 挿入します。
3. Sが空になるまで手順 2 を繰り返します。

これまでの考え方は集水域に焦点を当てており、生成された分離線に焦点を当ててはいませんでした。位相的流域は、1997 年に M. Couprie と G. Bertrand によって導入され、^[6]次の基本的性質の恩恵を受けています。関数 W が関数 F の流域であるためには、W ≤ F であり、W が F の局所的最小値間のコントラストを維持する必要があります。ここで、2 つの局所的最小値 M ₁と M _{2間のコントラストは、M 1}からM ₂に移動するために登らなければならない最小高度として定義されます。^[7]効率的なアルゴリズムは、論文で詳しく説明されています。^[8]

ウォーターシェッドアルゴリズム

画像セグメンテーションに分水嶺原理を使用するには、さまざまなアプローチを採用できます。

• 画像の勾配の局所的最小値がマーカーとして選択されることがあります。この場合、過剰セグメンテーションが生成され、2 番目のステップで領域のマージが行われます。
• マーカー ベースのウォーターシェッド変換では、ユーザーによって明示的に定義されたか、形態学的演算子またはその他の方法で自動的に決定された特定のマーカー位置が使用されます。

最も一般的なウォーターシェッドアルゴリズムの1つは、1990年代初頭にF.マイヤーによって導入されましたが、その後、このアルゴリズムには、総称してPriority-Floodと呼ばれる多くの改良が加えられており、^[9]数兆ピクセルからなるデータセットに適したバリエーションも含まれています。^[10]

このアルゴリズムはグレースケール画像で動作します。グレー値レリーフの連続的なフラッディング中に、隣接する集水域を持つ流域が構築されます。このフラッディング プロセスはグラデーション画像で実行されます。つまり、流域はエッジに沿って出現します。通常、これにより、特に医療用 CT データなどのノイズの多い画像データの場合、画像が過剰に分割されます。画像を事前に処理するか、後で類似性基準に基づいて領域を結合する必要があります。

1. フラッディングが開始されるピクセルであるマーカーのセットが選択されます。それぞれに異なるラベルが付けられます。
2. 各マークされた領域の隣接ピクセルは、ピクセルの勾配の大きさに対応する優先レベルを持つ優先キューに挿入されます。
3. 優先度レベルが最も低いピクセルが優先キューから抽出されます。抽出されたピクセルの隣接ピクセルのうち、すでにラベル付けされているピクセルがすべて同じラベルを持っている場合、そのピクセルはそれらのラベルでラベル付けされます。優先キューにまだ入っていないマークされていない隣接ピクセルはすべて優先キューに入れられます。
4. 優先キューが空になるまで手順 3 をやり直します。

ラベルのないピクセルは分水界線です。

最適全域森林としての流域は、Jean Cousty らによって導入されました。^[12]彼らはこれらの流域の一貫性を確立しました。つまり、流域は「集水域」（最急降下特性による）またはこれらの集水域を分離する「境界線」（水滴原理による）によって同等に定義できます。次に、同値定理によって、最小全域森林の観点からの最適性を証明しました。その後、それらを計算するための線形時間アルゴリズムを導入しました。同様の特性は他のフレームワークでは検証されておらず、提案されたアルゴリズムは理論と実践の両方において最も効率的な既存のアルゴリズムであることは注目に値します。

• 
  2 つのマーカー (緑) が付いた画像と、画像の勾配に基づいて計算された最小スパニング フォレスト。
• 
  最小全域フォレストによるセグメンテーションの結果

2007年、C. Allèneら^[13]はグラフカットと最適スパニングフォレストの関係を確立しました。より正確には、グラフの重みのべき乗が一定の数値を超える場合、グラフカットのエネルギーを最小化するカットは最大スパニングフォレストによるカットであることを示しています。

Falcaoら^[14]の画像フォレスト変換（IFT）は、最短経路フォレストを計算する手順です。J. Coustyら^[15]は、IFTのマーカーが重み関数の極値に対応する場合、フォレストによって誘導されるカットが分水嶺カットであることを証明しました。

ランダムウォーカーアルゴリズムは、組み合わせディリクレ問題を解くセグメンテーションアルゴリズムであり、2006年にL. Gradyによって画像セグメンテーションに適応されました。^[16] 2011年に、C. Couprieらは、グラフの重みの累乗が無限大に収束する場合、ランダムウォーカーエネルギーを最小化するカットは最大スパニングフォレストによるカットであることを証明しました。^[17]

階層的流域変換は、結果をグラフ表示に変換し（つまり、セグメント化された領域の隣接関係が決定され）、さらに流域変換を再帰的に適用します。詳細については^[18]を参照してください。流域と階層的セグメンテーションを関連付ける理論は^{[19]で開発されています。}

• フェルナンド・マイヤー。最適なパルタージュ・デ・ゾーを注ぐためのアルゴリズムはありません。形式と諜報技術に関する8 つの^会議、Vol. 2 (1991)、847 ～ 857 ページ、フランス、リヨン。
• Luc Vincent と Pierre Soille。デジタル空間の分水嶺: 浸漬シミュレーションに基づく効率的なアルゴリズム。IEEE Transactions on Pattern Analysis and Machine Intelligence、第 13 巻、第 6 号 (1991 年)、583 ～ 598 ページ。
• L. Najman および M. Schmitt。流域等高線の測地線顕著性と階層的セグメンテーション。IEEE Transactions on Pattern Analysis and Machine Intelligence、第 18 巻、第 12 号 (1996 年)、1163 ～ 1173 ページ。
• JBTM Roerdink と A. Meijster。「ウォーターシェッド変換: 定義、アルゴリズム、並列化戦略」。Fundamenta Informaticae 41 (2000)、pp. 187–228。
• Laurent Najman、Michel Couprie、Gilles Bertrand。流域、モザイク、そして創発パラダイム。Discrete Applied Mathematics、Vol. 147、Num. 2–3(2005)、301–324 ページ。

• ウォーターシェッド変換とウォーターシェッドアルゴリズムのアニメーション。
• 論文、講義スライド、ソースコードを含むトポロジカル ウォーターシェッド変換。
• ImageJ用のオープンソースのウォーターシェッドプラグイン。
• トポロジー ツールキット (モース複体に基づく 2D および 3D 流域)