分水嶺(画像処理)

地質学では、流域は隣接する流域を分ける分水嶺である。

洪水による流域編集

このアイデアは、S.BeucherとC.Lantuéjoulによって1979年に導入されました。 基本的な考え方は、救済の各地域の最小値に水源を配置し、ソースからの救済全体を洪水させ、異なる水源が出会うときに障壁を構築することで構成されていました。 結果として得られる一連の障壁は、洪水による流域を構成します。 このアルゴリズムには、集合的にPriority-Floodと呼ばれる多くの改善が行われています。

地形距離による分水界

直感的には、地形レリーフに落ちる水滴は”最も近い”最小値に向かって流れます。 「最も近い」最小値は、最急降下の経路の終わりにある最小値です。 地形の面では、ポイントがその最小値の集水域にある場合に発生します。 前の定義では、この条件は検証されていません。

水の滴による流域原則それ

直感的には、流域は、水の滴が異なる最小値に向かって流れることができる地域の最小値の分離です。 この直感的なアイデアの形式化は、エッジ重み付けグラフの流域を定義するために提供されました。

ピクセル間watershedEdit

S.BeucherとF.Meyerは、次の手順を考慮して、watershedメソッドのアルゴリズム的なピクセル間実装を導入しました:

1. それぞれの最小値に個別のラベルを付けます。 ラベル付きノードを使用してセットSを初期化します。
2. sから、最小高度Fのノードx、つまりF(x)=min{F(y)|y≤S}を抽出します。
3. Sが空になるまでステップ2を繰り返します。
4. Sが空になるまでステップ2を繰り返します。
5. Sが空になるまでステップ2を繰り返します。

トポロジカルな流域編集

以前の概念は集水域に焦点を当てていますが、生成された分離線には焦点を当てていません。 位相的分水界は1997年にM.CouprieとG.Bertrandによって導入され、以下の基本的性質を利用している。関数Wが関数Fの分水嶺であるための必要十分条件は、W≤FおよびWがFの局所最小値の間のコントラストを保持することである。 効率的なアルゴリズムを詳細に述べた。

分水界アルゴリズム

画像分割の分水界原理を使用するために、異なるアプローチを採用することができる。

• 画像の勾配の局所最小値をマーカーとして選択することができ、この場合、オーバーセグメンテーションが生成され、第二のステップは領域マージを含む。
• マーカーベースの流域変換は、ユーザーによって明示的に定義された特定のマーカー位置を使用するか、形態学的演算子または他の方法で自動的に決定します。

Meyerの洪水アルゴリズム編集

最も一般的な流域アルゴリズムの1つがFによって導入されました。 1990年代初頭のMeyerは、集合的にPriority-Floodと呼ばれるいくつかの改善がなされたが、その後、数兆ピクセルからなるデータセットに適した変種を含む、このアルゴリズムに加えられている。

このアルゴリズムはグレースケール画像で動作します。 灰色の価値救助の連続的な洪水の間に、隣接した集水域の洗面器が付いている流域は組み立てられる。 このフラッディングプロセスは、勾配画像上で実行されます。 通常、これは、特にノイズの多い画像素材の場合、画像のオーバーセグメンテーションにつながります。 医療CTデータ。 画像を前処理するか、後で類似性基準に基づいて領域をマージする必要があります。

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

ラベル付けされていないピクセルは分水界線です。

医薬品ペレットの母集団に対するマーカーでサポートされた流域変換の例。 分水界線は、CTイメージスタック上に黒で重ね合わされます。

最適なスパニングフォレストアルゴリズム（流域カット）編集

最適なスパニングフォレストとしての流域は、Jean Coustyらによって導入されています。 それらは、これらの流域の一貫性を確立する：それらは、それらの「集水域」（最も急な降下特性を介して）またはこれらの集水域を分離する「分割線」（水の滴の原則を介して）によって等価的に定義することができる。 そして、それらは同値定理を通して、最小スパニング森林の観点からのそれらの最適性を証明する。 その後、彼らはそれらを計算するための線形時間アルゴリズムを導入します。 同様の特性は他のフレームワークでは検証されておらず、提案されたアルゴリズムは理論的にも実践的にも最も効率的な既存のアルゴリズムであることに注意することは価値がある。

• 二つのマーカー（緑）と、画像の勾配で計算された最小スパニングフォレストを持つ画像。

• 最小スパニングフォレストによるセグメンテーションの結果