More than 5 years have passed since last update.

pythonで画像領域分割を実装 (Union-Find)

Posted at 2016-05-29

前の記事で少し画像処理を齧って面白かったので、今回は論文を読んで簡単な画像処理を実装してみました。
(以下の画像の様な感じです。)

src	dst

今回読んだ論文は割と古め(2004年)でそこまで実装自体は難しそうではなかったのでやってみました。（ただ、論文に掲載されている結果ほどうまく行っていません・・・）

今回のソースコードはgithubに上げてあります。
https://github.com/aratakokubun/GraphBasedSegmentationWithUnionFind.git

画像処理の概要

今回実装したのは画像領域分割の処理で、輝度
結合の条件として、近傍の画素との境界(Edge)を小さい順番に判定して次々と領域を結合していきます。

アルゴリズム

以下の1-5を実行し、結果として独立したComponentのリストを得ます。このComponentが画素同士が結合された領域になります。

各画素の8近傍(grid)もしくは一定距離内(nearest-neighbor)の画素との境界(Edge)を全て抽出する。
初期状態では全ての画素が結合されていない状態であり、この各要素をComponentとして扱う。
各画素に関して、結合の基準として用いる値を計算する。

例えば、今回の場合は輝度値(luminance)を用いており、輝度の近い画素同士を同じ領域として結合する。
抽出した各Edgeの差(diff)を計し、diff値の小さい順にソートする。
ステップ５をEdgeの小さい順に繰り返す
Edgeの値が、境界の両側のComponentの内部差(MInt)より小さい場合、２つのComponentを結合して１つのComponentとする。

※ このステップはEdgeの結合条件で詳細を記載します。

Edgeの結合条件

ステップ5の結合に関して、Edgeの差diffと、2つのComponent C1, C2の内部差Mintに関して、以下の条件の場合に結合します。

diff <= MInt(C1, C2)

２つのComponentの内部差Mintは以下の様に定義します。

MInt(C1, C2) = min(Int(C1)+τ(C1), Int(C2)+τ(C2))

各Componentの内部差Intは、Componentに今までに結合された境界の最大値をとります。Componentが１画素要素の場合は0になります。(ただし、この記述は厳密には正しくないので、詳しく知りたい方は参考文献1を参照してください。)

また、τはComponentのサイズに応じた境界値関数で、以下の様に定義されます。

τ(C) = k/|C|

kは定数のパラメータで、kが大きいほどEdgeの結合が起きやすく、結果のComponentが大きくなりやすいです。

高速化のためのテクニック

処理を高速化するためにUnion-Findというアルゴリズムを用います。

Union-Findでは集合Sに対して互いに素なSの部分集合を考えます。今回の画像領域分割の処理では、集合Sが画素の集合である画像、部分集合がComponentに該当します。
これをDisjointSetと言い、union, findの操作を以下の様に定義します。

union(C1, C2)
部分集合C1, C2を合併し、新たにC1とする。(Componentを結合するステップ5の処理に該当します。)
find(a)
要素a(画素)が属する部分集合を取得する。

このunion処理の際、各Componentの代表となる要素を１つずつ定義しておき、結合される側(C2)の各要素から結合する側(C1)の代表の要素へリンクを張る様にすることで１つの配列で簡易に処理が実装できます。

また、TreeによるUion-Findを利用することでさらに高速化が可能になります。

実装方法はここでは細かく記載しませんが、Union-Findに関してはかなり詳細な解説が参考文献2に記載されていますので、是非ご参照ください。また、参考文献3では計算量などの解説もありますので、併せてご参照ください。