画像応用数学特論　12/13課題　 浜岡裕之

アドレス:hamaoka@ime.info.hiroshima-cu.ac.jp

提出日2013年12月16日

 

階層グラフカットによるステレオ

階層グラフカットによる視差画像を生成するプログラムを作成し，α拡張によるステレオと階層グラフカットによるステレオの結果を比較する．

 

ソースファイル

α拡張

stereobygcalpha.cpp

階層グラフカット

stereobyhgc.cpp

 

アルゴリズム(階層グラフカット)

For p=全てのピクセル

=初期値

end for

A={{0}…{3…63}}

E=とても大きな値

for ループ=0からとても大きな値

success=0

for i=0～11

グラフの初期化

全てのノードの追加

for p=全てのピクセル

              A[i]のうちに最も近い値をに設定

              ノードのソース側に,シンク側にを設定

end for

for (p,q)=すべての隣接点

              A[i]のうちに最も近い値をに設定

              A[i]のうちに最も近い値をに設定

              ノードaのソース側に,シンク側にに設定

              もし,の場合

                            ノードaからノードpへのエッジの重みを10000

                            ノードaからノードqへのエッジの重みを10000

                            ノードpからノードaへのエッジの重みに

か0のうち大きい方を設定

                            ノードqからノードaへのエッジの重みに

か0のうち大きい方を設定

              もし,の場合

                            ノードpからノードqへのエッジの重みを10000

                            ノードqからノードaへのエッジの重みを10000

                            ノードaからノードqへのエッジの重みに

か0のうち大きい方を設定

                            ノードaからノードqへのエッジの重みに

か0のうち大きい方を設定

end for

                            最大流・最小カットアルゴリズムの適用

                            E’=求まったラベルで計算した総コスト関数

                            E’<Eなら現在のラベルを求まったラベルにし、E=E’にし、success=1 

                            グラフの消去

              end for

              もしsuccess==0ならループを脱出する

end for

 

 

データコスト

・SAD

または

・相関

 

スムーズコスト

cは定数または

 

環境

OS:windows7

開発環境:visual studio 2010 Express

CPU:Intel Core i5  2.60GHz

メモリ:4GB

使用ライブラリ:maxflow  openCV 2.4

 

 

 

 

 

 

実験結果

今回の入力画像は以下のサイト内の2001 datasetsのTsukubaを使用した．

http://vision.middlebury.edu/stereo/data/

 

この画像を入力画像とし，

・α拡張(SAD ペナルティ:c=1)

・階層グラフカット(SAD ペナルティ:c=1)

・階層グラフカット(相関 ペナルティ:c=1)

・階層グラフカット(SAD ペナルティ: T=80 c0=1 c1=10)

この4つのパラメータで実験を行った．

以下に結果を示す．なお，視差画像は値を定数倍することで見やすくしている．

 

 

scene1.row3.col3

scene1.row3.col4

scene1.row3.col3(左)

scene1.row3.col4(右)

図1 入力画像

 

サイズ3×3

サイズ7×7

サイズ11×11

図2 α拡張 SAD ペナルティ:c=1

 

サイズ3×3

サイズ7×7

サイズ11×11

図3 階層グラフカットSAD ペナルティ:c=1

 

 

サイズ3×3

サイズ7×7

サイズ11×11

図4 階層グラフカット 相関 ペナルティ:c=1

 

 

 

表1 処理時間

 

サイズ3×3

処理時間(秒)

サイズ7×7

処理時間(秒)

サイズ11×11

処理時間(秒)

α拡張 SAD ペナルティ:c=1

27(13)

45(22)

84(41)

階層グラフカットSAD ペナルティ:c=1

50(16)

66(21)

90(30)

階層グラフカット 相関 ペナルティ:c=1

68(16)

60(20)

86(28)

(かっこ内は1ループの平均時間)

 

 

 

 

 

(処理時間: 108秒　平均17秒)

サイズ3×3

図5階層グラフカットSAD スムーズコスト T=80 c0=1 c1=10

 

 

 

考察

図2と図3より，α拡張と比べて階層グラフカットはすべての値と比較しているわけではないので精度が落ちている．また，表1より1ループ平均の処理時間は階層グラフカットのほうが良いが，収束するまでのループ回数が増えてしまったので全体の処理時間は悪くなった．

次に階層グラフカットにおけるSADと相関を使った場合を比較する．図3と図4より，サイズ7×7とサイズ11×11の場合，相関はSADに比べ前景の像とライトの部分にノイズが多い．これらは輝度が滑らかに変化する場所である．相関は平均値との輝度の差でコストを計算するので，場所が変化してもコストに影響を与えにくく，ノイズが増加したと考えられる．

図5のエッジを考慮したスムーズコストを使用した場合，ノイズが残っているものの，ペナルティが定数の場合に比べて精度は上昇した．tukubaのデータでは物体の端とエッジが一致していない場所が多いのでノイズを取りきれなかったと考えられる．