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

[前の記事](http://qiita.com/artk/items/d4f342a3ba526345907b)で少し画像処理を齧って面白かったので、今回は論文を読んで簡単な画像処理を実装してみました。
(以下の画像の様な感じです。)

|src|dst|
|:-----------:|:------------:|
|![sample8.jpg](https://qiita-image-store.s3.amazonaws.com/0/40655/b6ad6a8e-1426-1798-c5a4-0c7f0a4726d2.jpeg)|![result_sample8.png](https://qiita-image-store.s3.amazonaws.com/0/40655/8f48ef22-5d54-0d12-383d-5429476ab27d.png)|


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

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

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

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

1. 各画素の8近傍(grid)もしくは一定距離内(nearest-neighbor)の画素との境界(Edge)を全て抽出する。
初期状態では全ての画素が結合されていない状態であり、この各要素をComponentとして扱う。
2. 各画素に関して、結合の基準として用いる値を計算する。<br>
例えば、今回の場合は輝度値(luminance)を用いており、輝度の近い画素同士を同じ領域として結合する。
3. 抽出した各Edgeの差(diff)を計し、diff値の小さい順にソートする。
4. ステップ５をEdgeの小さい順に繰り返す
5. Edgeの値が、境界の両側のComponentの内部差(MInt)より小さい場合、２つのComponentを結合して１つのComponentとする。<br>
※ このステップはEdgeの結合条件で詳細を記載します。

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

```math
diff <= MInt(C1, C2)
```

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

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

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

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

```math
τ(C) = k/|C|
```

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

### 高速化のためのテクニック
処理を高速化するためにUnion-Findというアルゴリズムを用います。<br>
Union-Findでは集合Sに対して互いに素なSの部分集合を考えます。今回の画像領域分割の処理では、集合Sが画素の集合である画像、部分集合がComponentに該当します。
これをDisjointSetと言い、union, findの操作を以下の様に定義します。

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

このunion処理の際、各Componentの代表となる要素を１つずつ定義しておき、結合される側(C2)の各要素から結合する側(C1)の代表の要素へリンクを張る様にすることで１つの配列で簡易に処理が実装できます。<br>
また、TreeによるUion-Findを利用することでさらに高速化が可能になります。

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


## 結果
今回pythonで実装した結果が以下になります。
全ての領域ではなく、領域サイズの大きい上位40を色付けしています。

| src| dst|
|:-----------:|:------------:|
|![sample2.jpg](https://qiita-image-store.s3.amazonaws.com/0/40655/0004c5db-3234-433b-bf48-05cc17781e05.jpeg)|![result_sample2.png](https://qiita-image-store.s3.amazonaws.com/0/40655/08bf0e41-6292-1116-6945-39118040a9dd.png)|
|![sample4.jpg](https://qiita-image-store.s3.amazonaws.com/0/40655/0fa657c8-31af-9691-0876-d29d563afd4b.jpeg)|![result_sample4.png](https://qiita-image-store.s3.amazonaws.com/0/40655/16eabaab-839f-5534-82c1-524673f8ac27.png)|
|![sample5.jpg](https://qiita-image-store.s3.amazonaws.com/0/40655/8c7cfa67-d077-875c-ab12-17e26fb380f3.jpeg)|![result_sample5.png](https://qiita-image-store.s3.amazonaws.com/0/40655/ea713820-afe9-2c14-192e-fc45bfd82c5b.png)|
|![sample8.jpg](https://qiita-image-store.s3.amazonaws.com/0/40655/b6ad6a8e-1426-1798-c5a4-0c7f0a4726d2.jpeg)|![result_sample8.png](https://qiita-image-store.s3.amazonaws.com/0/40655/8f48ef22-5d54-0d12-383d-5429476ab27d.png)|
|![sample11.jpg](https://qiita-image-store.s3.amazonaws.com/0/40655/f60e71f1-c52c-1d16-d612-60efee29bbf7.jpeg)|![result_sample11.png](https://qiita-image-store.s3.amazonaws.com/0/40655/abb86685-fa96-9fe2-943d-de3bc314dce1.png)|
|![sample12.jpg](https://qiita-image-store.s3.amazonaws.com/0/40655/4a749ffe-7350-f105-369a-337c0a998a45.jpeg)|![result_sample12.png](https://qiita-image-store.s3.amazonaws.com/0/40655/6f3389ed-7740-5fb3-8a3c-723a8bc195df.png)|


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

### 参考文献
1. Efficient Graph-Based Image Segmentation <br>
http://cs.brown.edu/~pff/papers/seg-ijcv.pdf
2. Union Findの実装 <br>
http://www.geocities.jp/m_hiroi/light/pyalgo61.html
3. Disjoint-Set Data Structures <br>
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec16.pdf