はじめに

Image Segmentation Using Topological Persistenceを読んだのでメモ．2007年の少し古めの論文．Image segmentationにpersistent homologyを取り入れた論文．

Background in Topology

Alpha Complexes and Delaunay Triangulations

$X=\{x_1,\dots,x_n\}$ を画像 $I$ に存在する点の集合とする．さらに $X$ の各点を中心とする正の半径 $\alpha$ の円の集合を考える． $\alpha$ を大きくした時，画像中のカバーされる領域が広がり円同士の重なりも大きくなる(論文の図１参照)．この時重なり合う円の中心をつなげることで辺と三角形を作ることができる．

辺は二つの円が他の円に内部にない点(もし他の円の内部にある点で交わる時には辺ではなく三角形になる)で交わる時にその二つの円の中心を頂点とする線分で定義される．同様に三つの円が他の円の内部にない一点(他の円の内部にある点の場合は三角形の作り方に自由度が生じる)で交わる時にそれらの円の中心を頂点とする三角形が定義される．この三角形の構成方法をDelaunay triangulationといい，二次元の場合には $O(n\log n)$ で計算することができる．

$\alpha$ が与えられたとき，頂点，エッジ，三角形の集合はsubcomplex $K_\alpha$ を定義する．この複体は各頂点を中心とする半径 $\alpha$ の円の和集合によって生成された位相を正確に表現する．複体の重要な特徴として，二つの半径 $\alpha,\alpha',\alpha\lt\alpha'$ において $\alpha$ の部分複体は $\alpha'$ の部分複体の部分集合 $K_\alpha\subset K'_\alpha$ となる．この複体の系列をfiltration)と呼ぶ．十分大きな $\alpha$ において複体はfull triangulation( $X$ にまたがるグラフのすべての領域がDelaunay trianglesによって覆われている状態)となる．この複体は $X$ の他のすべての部分複体の上位集合となる．

今回は $X$ を画像 $I$ におけるエッジ検出の結果から生成されるエッジ点の集合とする．この時，問題として小さな領域が部分集合の補集合として残る可能性が存在する．このような領域は $\alpha$ を大きくすることで消すことが可能だが，同時に新たな微小領域を生じる可能性がある．このような微小領域に対処するためpersistent homologyを使う．

Persistent Homology

代数的位相幾何においてホモロジーは空間の複雑度を測る方法を与える．平面内の複雑度を調べるためにホモロジー群 $H_1(K)$ とそれに対応するベッチ数 $\beta_1$ を考える．今回の問題設定においてはベッチ数は簡単に定義することができて， $V$ と $E$ を頂点と辺とする連結グラフに対してベッチ数は $\beta_1=E-V+1$ となる．もし平面内に三角分割された部分複体を持つなら $\beta_1=C-V+E-F$ となる．ただし， $C$ は連結成分の数で $F$ は複体中の面（もしくは三角形）の数．

前で述べたように $\alpha$ の増大によって得られる部分複体の系列はfiltrationとして知られるが，filtrationの各部分複体 $K_\alpha$ のベッチ数 $\beta_1(K_\alpha)$ は(三角分割が変わるため) $\alpha$ とともに変わる． $\alpha$ が増えると，穴が塞がれる(すなわち三角形が作られる)場合には $\beta_1$ は減り，エッジが作られる場合には増える．言葉を変えれば穴が塞がれた際には $F$ が増え，非連結な成分間にエッジが作られれば $C$ が減る．

上記に関連してpersistenceは $K_\alpha$ の補集合の領域が，ある $p\gt0$ に対して $K_{\alpha+p}$ に含まれるまでの長さを指す． $K_\alpha$ の $p$ -persistentベッチ数 $\beta^p_1(K_\alpha)$ は $K_{\alpha+p}$ に含まれる $K_\alpha$ の補集合内の領域の数を $\beta_1(K_\alpha)$ から引いたものとなる．

filtration内の二つの部分複体 $K_\alpha,K_{\alpha+p}$ について考える． $K_\alpha\subset K_{\alpha+p}$ は少なくとも $K_{\alpha+p}$ が $K_\alpha$ と同じ頂点，辺，三角形を含むことを意味する． $K_\alpha$ と $K_{\alpha+p}$ 両方に共通する穴は $p$ でのpersistentな領域であり，これを $p$ -persistent regionと呼ぶ．一方で $K_\alpha$ における穴で $K_{\alpha+p}$ で塞がれている領域は $p$ においてpersistentではない．これを $p$ -transient regionsと呼ぶ．そして最後に $K_\alpha$ ですでに塞がれている穴，すなわち個々の三角形を $d$ -trianglesと呼ぶ．

$\beta^p_1(K_\alpha)$ のより一般的な定義は $\beta^p_1(K_\alpha)=C-V+E-F-R$ で与えらる． $R$ は $K_{\alpha+p}$ に含まれる $K_\alpha$ の補集合の領域の数を表す．ただしこれは高次元においては必ずしも成り立つわけではないので注意．

Segmentation Algorithm

ここからが本題のsegmentationの話．提案法はsplit-anad-merge segmentation algorithmに基づいており，画像のaplittingとregion mergingのための領域の特徴量としてtopologyとpersistent homologyを利用する．まず，Cannyやwaveletを使ったエッジ検出を行いエッジ点の集合 $X$ を作る．Topological splittingにより３つのタイプの初期分割， $p$ -persistent regions, $p$ -transient regions， $d$ -trianglesを生成する．topological splittingは $\alpha$ と $p$ の二つのパラメータで調整され， $\alpha$ は円の半径で $p$ はpersisteceを表す．アルゴリズムの最後に $p$ -transientと $d$ -triangleを $p$ -persistent regionまたは相互にmergeして最終的なsegmentation結果を得る．

各領域の整理をしておくと， $p$ -persistentは $K_{\alpha+p}$ において塞がれていない穴で，(塞ぐことができない=)他の領域に比べて比較的大きい． $p$ -transientは $K_\alpha$ から $K_{\alpha+p}$ の間で塞がれた穴で比較的小さい． $d$ -trianglesは $K_\alpha$ ですでに存在する三角形で最も小さい領域となる． $p$ -persistentはエッジによって囲まれていて，内部に半径 $\alpha+p$ の縁を含むという点で初期分割時において中心となる物体を定義する重要な領域となる．

初期分割を拡張することで完全な分割を行うことが可能で，この拡張の過程でpersistent homologyを利用する．最も単純な方法はhomological informationを保ちながら各領域を広げることでこれは既存手法が存在する．ただ，この方法はエッジの情報しか利用しないため，領域としての情報を考量しないという欠点がある．

別な方法として各領域固有の特徴を利用して隣接領域をマージするというアプローチもある．ここでは領域の平均色を特徴量とした方法を用い，homological persistenceを利用して領域をマージする順序を決定する．具体的には三角形を構成する円の半径 $\alpha$ に従って小さい順にマージしていく．分割された領域のトポロジーを保つためベッチ数が変わらない場合にのみマージを行うとする．

最終的なアルゴリズムは次のようになる．

画像からエッジ点の集合 $X$ を作成
$X$ のDelaunay triangulationを作成
$\beta^p_1(K_\alpha)$ を計算し各領域を $p$ -persistent， $p$ -transient， $d$ -triangleに分類する．
$\alpha$ が小さい順に領域を並べた集合 $F$ を作る
$F$ が空集合となるまで以下を繰り返し
$\sigma$ を $F$ の先頭の領域とし $\sigma$ を $F$ から取り除く
$\beta^p_1(\text{merged regions})=\beta^p_1(K_\alpha)$ が成り立つ(ベッチ数を変えない)最も類似度(この論文では色の類似度)が高い隣接領域を $\sigma$ にマージする

まとめ

ちょっとした興味で読んでみたが，そういえば位相についてまともに勉強したことなかったなと．ただ論文がだいぶ厳密な定義を省いて説明してくれているから用語が入って来難い以外はよく読めた気がする．ただ $p$ -persistent， $p$ -transient， $d$ -triangleに区別するのがアルゴリズムにどう効いているのかはよくわからなかった(多分ベッチ数の計算が楽になる？)．