階層グラフカットを用いたステレオマッチング 広島市立大学 情報科学研究科　知能工学専攻　1367008　高森貴大 <内容> 階層グラフカットとα 拡張によるステレオマッチングの結果の比較 環境 　OS Ubuntu 11.10 CPU intel(R) Xeon(R) CPU X5460@3.16GHz コンパイラgcc version4.6.3 opencv version　opencv 2.4.5 ライブラリ　MAXFLOW 用いたライブラリ こちら のMAXFLOW 作成したプログラム gazou.zip 階層グラフカットとα拡張によるステレオマッチングの両方＋MAXFLOW、画像が入ってる。 FGCSMに階層グラフカットでASMにα拡張のプログラムが入っている。 コンパイル方法 階層グラフカット g++ -o FGCSM FGCSM.cpp graph.cpp maxflow.cpp `pkg-config --cflags opencv` `pkg-config --libs opencv` α拡張 g++ -o ASM ASM.cpp graph.cpp maxflow.cpp `pkg-config --cflags opencv` `pkg-config --libs opencv` <実行方法> 階層グラフカット ./FGCSM α拡張 ./ASM 入力画像は両方ともcppファイルの中の IplImage* rightimg = cvLoadImage("rightb.bmp",CV_LOAD_IMAGE_GRAYSCALE); IplImage* leftimg= cvLoadImage("leftb.bmp",CV_LOAD_IMAGE_GRAYSCALE); の"rightb.bmp"で右画像が、"leftb.bmp"で左画像が選択されている <アルゴリズム> 階層グラフカット，α拡張ともに講義資料に掲載されていたアルゴリズムを使用している． 以下は階層グラフカットアルゴリズムを用いた場合のアルゴリズムである． 現在のラベルβを初期化 階層ラベルAを作成 グラフの総コストEを初期化 コストの更新が終わるまで すべての階層ラベルにたいして グラフを初期化 ノードを追加 全ての画素kに対して 現在の深さiの階層ラベルA[i]のうち最もβ[k]に最も近い値 をαpに設定 ノードのソース側にD(βp)，シンク側にD(αp)を設定 全てのエッジに対して，(以下では，画素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へのエッジの重みに100000(比較的大きい数)を設定 ノードaからノードqへのエッジの重みに100000(比較的大きい数)を設定 ノード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へのエッジの重みに100000(大きい数)を設定 ノードqからノードaへのエッジの重みに100000(大きい数)を設定 ノード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を繰り返す <実行結果> 画像のサイズはすべて200×200である パラメータはC=0.9,ウィンドウサイズは9 左画像 右画像 階層グラフカットアルゴリズム α拡張アルゴリズム 実行時間 階層グラフカット6.810　 α拡張14.870 <考察> 階層グラフカットとα拡張によるステレオマッチングの結果を比較するとα拡張のほうが精度は高かった、α拡張のほうが探索している場所が多いと考えられるためこの結果は妥当と言える。実行時間についても同様の理由から階層グラフカットの方が早い。 ただどちらの結果でも不自然に白い場所があるなど、どちらもあまり良い結果ではない