Level Set法

はじめに

　今回はLevel Set法と呼ばれるアルゴリズムを紹介し、その実行例を示す。

Level Set法とは

　最初に、画像にLevel Set法を適用した結果を示す（動画）。

上の動画のように、初期閉曲線を物体の縁に沿って成長させていく仕組みがLevel Set法である。本手法は2Dの画像だけでなく3D物体に対しても適用できる（3D物体への適用例）。Level Set法は任意次元に適用できる汎用性の高い輪郭抽出アルゴリズムである。

アルゴリズム

　Level Set法は、n次元空間内に存在する物体の境界面を、(n+1)次元空間内の曲面（超曲面）を時間発展させることにより検出する手法である。n=2のときの様子を以下に示す。

　右図の黄色の物体はxy平面内にあるとする。最初にこの物体を囲む閉曲線\gamma_0をxy平面内に作り、この閉曲線を用いて曲面z=\psi(\vec{x},t=0)を作る（作り方は後述）。この曲面とxy平面との交線が閉曲線\gamma_0である。さて、この曲面を内側に向かって少しずつ収縮させていく。収縮時の速度は物体との距離が縮まるにつれ小さくなるように定義される。速度が0になったときの曲面z=\psi(\vec{x},t)とxy平面との交線が物体の境界線\gamma_t（赤線）である。Level Set法は、対象とする空間（今の場合2次元）より1次元高い空間（今の場合3次元）内の曲面を考えることにより、特異的な形状（窪みや尖り）やトポロジーの変化（上の動画で見たような穴の生成など）に自然に対応できる強力な手法である。物体の外側に初期閉曲線を設定し内側に曲面を収縮させるだけでなく、最初の動画で見たように、物体の内側に初期閉曲線を設定し外側に曲面を膨張させることもできる。

　初期閉曲線\gamma_0から曲面を作る手順は以下の通りである。xy平面上の点p,qを考える（右図の緑丸）。点pは閉曲線\gamma_0の外側に、qは閉曲線の内側にある。それぞれの点から閉曲線までの距離をd_p,d_qとする。pを上側にd_pだけ動かし点p^{'}を作る（青丸）。一方、qに対しては下側にd_qだけ動かし点q^{'}を作る（青丸）。xy平面内の全ての点に対し同じことを繰り返すと（閉曲線の外側の点は上に動かし内側の点は下に動かす）初期閉曲線\gamma_0から曲面z=\psi_0(\vec{x})を作ることができる。ここで時間を変数に持つ曲面

    \begin{align*} z=\psi(\vec{x},t) \end{align*}

を考え、\psi(\vec{x},t=0)=\psi_0(\vec{x})と考える。曲面とxy平面の交線を\gamma(t)と書くことにすれば

    \begin{align*} \gamma(t)=\{\vec{x}|\psi(\vec{x},t)=0\} \end{align*}

と書くことができ、\gamma_0=\gamma(t=0)となる。以上で曲面の初期状態が定義された。次に曲面の時間発展を考える。xy平面上では\psi(\vec{x},t)=0を満たす。この両辺をtで偏微分する。

    \begin{align*} \frac{\partial\psi(\vec{x}, t)}{\partial t}+\vec{\nabla}\psi(\vec{x},t)\cdot\frac{\partial\vec{x}}{\partial t}=0 \end{align*}

\psi(\vec{x},t)はあらわにtに依存する部分と\vec{x}を通してtに依存する部分とを持つことに注意する。速度\vec{v}=\frac{\partial\vec{x}}{\partial t}を使うと

    \begin{align*} \frac{\partial\psi(\vec{x}, t)}{\partial t}+\vec{\nabla}\psi(\vec{x},t)\cdot\vec{v}=0 \end{align*}

を得る。ただし、\vec{\nabla}=(\frac{\partial}{\partial x},\frac{\partial}{\partial y})とした。ここで

    \begin{align*} \vec{n}=\frac{\vec{\nabla}\psi(\vec{x},t)}{\|\vec{\nabla}\psi(\vec{x},t)\|} \end{align*}

を導入すると

(1)   \begin{align*} \frac{\partial\psi(\vec{x}, t)}{\partial t}+\|\vec{\nabla}\psi(\vec{x},t)\|\vec{n}\cdot\vec{v}=0 \end{align*}

となる。\vec{n}は閉曲線の法線ベクトルである（下図参照）。接線の向きと直交し外側へ向かうベクトルである。

いま、\gamma(t)は法線に平行な方向に時間発展すると仮定すると

    \begin{align*} \vec{v}=F(K)\vec{n} \end{align*}

と書くことができる。ここで、F(K)は速度の大きさを表す関数（速度関数）であり、閉曲線の曲率Kに依存させる。これを使うと式(1)は

(2)   \begin{align*} \frac{\partial\psi(\vec{x}, t)}{\partial t}+F(K)\|\vec{\nabla}\psi(\vec{x},t)\|=0 \end{align*}

となる。この式が\psi(\vec{x},t)の時間発展を記述する偏微分方程式である。これを初期条件\psi(\vec{x},t=0)=\psi_0(\vecz{x})の下で解く。時間発展が終了（速度が0）した時点の曲面とxy平面の交線が求めるべき閉曲線、すなわち物体の輪郭線となる。次に行うことは、F(K)を具体的に定義し、式(2)を数値的に解くことができるよう差分方程式に変換するこであるが、難しい話になるので理論の話はこれで終わりにする。

プログラム

　10年ほど前にC++で実装したプログラムがここにある。この記事の冒頭に掲げた動画（画像に適用した例と3D物体に適用した例）も10年前に作成したものである。今回記事にするにあたりプログラムが動作することを確認した。

まとめ

　Level Set法は1990年ころに提案された手法である。OpenCVもこれをサポートしているが、引数の意味が今一つ理解できないし、計算速度も遅い。そこで、昔の自作ライブラリを掘り出してきた。十分高速に精度良く動いていると思う。

参考文献

  • R. Malladi, J. A. Sethian, and B. C. Vemuri, Shape modeling with front propagation: a level set approach, IEEE Trans, on PAMI, Vol. 17, No. 2, pp.158-175(1995).
  • J. A. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press
    (1999).
  • D. Adalsteinsson and J. A. Sethian, A Fast Level Set Method For Propagating Interfaces,
    Journal of Computational Physics, 118(2) 269-277 (1995).

    • Kumada Seiya

    Kumada Seiya

    仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

    最近の記事

    • 関連記事
    • おすすめ記事
    • 特集記事

    アーカイブ

    カテゴリー

    PAGE TOP