"Efficient Graph-Based Image Segmentation"の手法と実装

記事概要
1. Felzenszwalbらの提案したEfficient Graph-Based Image Segmentation *1の手法と実装を解説
2. 手法：画像中の各画素を1つのノードとした木から、輝度が類似なノードをまとめていきセグメンテーションを行う
3. 実装：Union-Findを用いることでo(nlogn)となる

Felzenszwalbらの提案したEfficient Graph-Based Image Segmentation を解説してみる。

画像のセグメンテーション*2は1枚の画像を同じような特徴(明るさ、色、テクスチャなど)を持つ複数の領域に分割する処理で、基本的な画像処理技術の1つである。画像合成処理、物体認識、ジェスチャ認識などの前処理として幅広く利用されている。

中でも、2004年にFelzenszwalbらが提案したEfficient Graph-Based Image Segmentationは、現時点で2703回*3も引用されてる重要な論文の1つと言える。プログラムのソースコード(C++)も公開されている。

この辺りはあまり詳しくないものの、最近興味があって勉強していたあるstate-of-the-artな論文がこの論文をベースにしていたことと、これまで何度もこの論文をベースにした手法に出会ったことから、さすがに理解しておこうと思ったのがきっかけ。

手法

入力： ${n}$ 個のノードと ${m}$ 個のエッジからなるグラフ ${G=(V,E)}$
出力： ${V}$ のセグメンテーション結果 ${S=(C_1,...,C_r)}$

初期化
1.1 各画素を表すノード ${v \in V}$ と、画像中で隣り合うノード(画素)を結ぶエッジ ${e \in E}$ から構成される無向グラフ ${G=(V,E)}$ を構成
1.2 エッジで結ばれるノード(画素)間の輝度差をエッジの重みとして設定
1.3 エッジ ${E}$ を重みが昇順になるように並べ ${\pi = (e_1, ..., e_m)}$ を構成
1.4 各ノードにそれぞれ個別のコンポーネントを割り当て ${S^{0}}$ を構成
${q = 1,..,m}$ に対して下記を繰り返す
2.1 ${e_q}$ で結ばれるノード ${v_i, v_j}$ が ${S^{q-1}}$ においてそれぞれコンポーネント ${C_k^{q-1}, C_l^{q-1}}$ に含まれているとする。この時、
${C_k^{q-1} \neq C_l^{q-1} }$ かつ
${w(e_q) \leq MInt(C_k^{q-1},C_l^{q-1}) }$
を満たした場合に ${C_k^{q-1}と C_l^{q-1}}$ をマージすることで ${S^{q}}$ が得られ、それ以外の場合は ${S^{q} = S^{q-1}}$ 。
ここで、 ${w(e_q)}$ はエッジ ${e_q}$ の重みであり、論文ではエッジ ${e_q}$ で結ばれるノード(画素)の輝度値の差となっている。また、 ${MInt(C_1,C_2)}$ は、
${MInt(C_1,C_2) = \min(Int(C_1) + \tau(C_1), Int(C_2) + \tau(C_2))}$
として定義される。 ${\tau}$ は ${\tau (C) = k/|C|}$ (kは定数、|C|はCのノード数)で定義される閾値関数であり、 ${Int(C)}$ は最小全域木 ${MST(C,E)}$ の最大重み ${\max_{e \in MST(C,E)} w(e)}$ である。
最終的に、 ${S = S^{m}}$ が得られる

高速であることと、高い変動性を無視しながら低い変動性を残すことがポイントである。

実装

実装では、素集合としてコンポーネントを捉え、コンポーネントの統合にUnion-Find を用いることで高速な処理を実現している。各コンポーネントを1つの木として表し、ノードが属するコンポーネントの判定(Find)と木の統合(Union)で経路圧縮とランクを用いた高速化を行っている*4。

ランク：木の高さを持っておき、低い方を高い方に繋げるようにする。
経路圧縮：上向きに辿って再帰的に根を調べる際に、調べたら辺を根に直接つなぎ直す。

なお、各コンポーネント ${C}$ に対応する ${Int(C) + \tau(C)}$ は個別に保持され、木を統合する際にこの値も更新される。それゆえ最小全域木 ${MST(C,E)}$ がコンポーネント間の比較の度に計算されることはない。

ソースコードが簡潔＆完結！(標準ライブラリ以外にライブラリを用いない！)で、利用しやすいというのも引用回数が多いことに影響していると思う。

*1:P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient Graph-Based Image egmentation,”International Journal of Computer Vision, vol. 59, no. 2, 2004.

*2:参考：領域分割 - SICE オンライン・ハンドブック - 計測自動制御学会

*3:2014年10月5日時点

*4:参考：プログラミングコンテストでのデータ構造