広島市立大学
情報科学研究科 知能工学専攻 酒井康裕
階層グラフカットを用いたステレオマッチング
<課題>
α拡張アルゴリズム，階層グラフカットアルゴリズムをそれぞれ用いて，ステレオマッチングを行い視差画像を出力するプログラムの作成
| 環境 |
| OS | Ubuntu 10.04 LTS - Lucid Lynx - |
| コンパイラ | gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) |
| プログラミング言語 | C++ |
| 使用ライブラリ | OpenCV , MAXFLOW |
上記環境以外での動作確認はしておりません．
<使用方法>
1. 上記ソースファイルをダウンロード
2. OpenCVをインストール
3. MAXFLOWライブラリをダウンロードしソースファイルと同じ場所に保存
4. ソースファイルをコンパイル
・コンパイル例 g++ -w -I/usr/local/include/opencv $1 -lcxcore -lcv -lhighgui -lcvaux -lml hierarchical.cpp maxflow.cpp graph.cpp
※環境によってコンパイル方法が異なります（特にUNIX系以外のOS）
5. 以下の形式で実行
・実行ファイル名 左視差画像 右視差画像
・読み込み可能な画像形式はBMP,DIB,JPEG,JPG,PBM,PGM,PPM,SR,RAS,TIFF,TIF,EXR,jp2
・視差画像は以下のサイトからダウンロード可能
http://vision.middlebury.edu/stereo/data/
<アルゴリズム>
階層グラフカット，α拡張ともに講義資料に掲載されていたアルゴリズムを使用した．
以下は階層グラフカットアルゴリズムを用いた場合のアルゴリズムである．
- 現在のラベルβを初期化
- 階層ラベルAを作成
- グラフの総コストEを初期化
- 階層の深さdepthだけ以下をループ
- グラフを初期化
- ノードを追加
- 全ての画素kに対して
- 現在の深さiの階層ラベルA[i]のうち最もβ[k]に最も近い値
をαkに設定
- ノードのソース側にD(βk)，シンク側にD(αk)を設定
- 全てのエッジに対して，(以下では，画素p, qのエッジ)
- 現在の深さiの階層ラベルA[i]のうち最もβ[p]に最も近い値をαpに設定
- 現在の深さiの階層ラベルA[i]のうち最もβ[q]に最も近い値をαqに設定
- ノードaソース側にV(βp, βq)，シンク側にV(αp, αq)を設定
- もし，V(βp, βq) ≦ V(αp, αq)ならば，
- ノードaからノードpへのエッジの重みに10000(比較的大きい数)を設定
- ノードaからノードqへのエッジの重みに10000(比較的大きい数)を設定
- ノードpからノードaへのエッジの重みに，V(αp, βq)-V(βp, βq)か0のうち大きいほうを設定
- ノードqからノードaへのエッジの重みに，V(βp, αq)-V(βp, βq)か0のうち大きいほうを設定
- もし，V(βp, βq) ≧ V(αp, αq)ならば，
- ノードpからノードaへのエッジの重みに10000(比較的大きい数)を設定
- ノードqからノードaへのエッジの重みに10000(比較的大きい数)を設定
- ノードaからノードpへのエッジの重みに，V(αp, βq)-V(αp, αq)か0のうち大きいほうを設定
- ノードaからノードqへのエッジの重みに，V(βp, αq)-V(αp, αq)か0のうち大きいほうを設定
- 最大流・最小カットアルゴリズムを適用し，総コストE'を計算
- もし，E > E' ならば
- 現在のラベルβkを求まったラベル更新
- 総コストの更新(E = E')
- グラフの消去
- 総コストが収束するまで4を繰り返す
<実行例>
上記のアルゴリズムに基づいて作成したプログラムの実行例を示す．
画像のサイズはすべて641×551である．(クリックで拡大)
| 左視差画像 | 右視差画像 |
 |  |
| α拡張アルゴリズム | 階層グラフカットアルゴリズム |
 |  |
| 実行時間 |
| α拡張アルゴリズム | 階層グラフカットアルゴリズム |
| 260sec | 80sec |
<比較>
α拡張アルゴリズムと階層グラフカットアルゴリズムの比較を行う．
α拡張アルゴリズムでは，ややノイズが目立つものの，階層グラフカットアルゴリズムを用いた結果と比べてシャープな画像が得られている．
一方で，階層グラフカットアルゴリズムでは，線の境界線が曖昧で少しボヤけた画像になっている．
これは，階層グラフカットでは，ラベル選択を，その階層内の限られた値の中から選択しているためではないかと考えられる．
実行時間に関しては階層グラフカットアルゴリズムの方がかなり短かった．（α拡張の3分の1程度）
不要なノードの削除を行っていないため実行時間が長くなってしまっている．
|