□α拡張を用いたステレオマッチングアルゴリズム

1. 現在のラベルβを初期化
2. グラフの総コストEを初期化
3. 最大視差の分だけ以下をループ
   1. グラフを初期化
   2. ノードを追加
   3. 全ての画素kに対してノードのソース側にD(βk)，シンク側にD(α) を設定
   4. 全てのエッジに対して，(以下では，画素p, qのエッジ)
      1. ノードaソース側にV(βp, βq)，シンク側にV(α, α)を設定
      2. ノードpとノードaのエッジの重み(双方向)にV(βp, βq)を設定
      3. ノードpとノードaのエッジの重み(双方向)にV(α, α)を設定
   5. 最大流・最小カットアルゴリズムを適用し，総コストE'を計算
   6. もし，E > E' ならば
      1. 現在のラベルβkをαに更新
      2. 総コストの更新(E = E')
   7. グラフの消去
4. 総コストが収束するまで4を繰り返す

□階層グラフカットを用いたステレオマッチングアルゴリズム

1. 現在のラベルβを初期化
2. 階層ラベルAを作成
3. グラフの総コストEを初期化
4. 階層の深さdepthだけ以下をループ
   1. グラフを初期化
   2. ノードを追加
   3. 全ての画素kに対して
      1. 現在の深さiの階層ラベルA[i]のうち最もβ[k]に最も近い値 をαkに設定
      2. ノードのソース側にD(βk)，シンク側にD(αk)を設定
   4. 全てのエッジに対して，(以下では，画素p, qのエッジ)
      1. 現在の深さiの階層ラベルA[i]のうち最もβ[p]に最も近い値をαpに設定
      2. 現在の深さiの階層ラベルA[i]のうち最もβ[q]に最も近い値をαqに設定
      3. ノードaソース側にV(βp, βq)，シンク側にV(αp, αq)を設定
      4. もし，V(βp, βq) ≦ V(αp, αq)ならば，
         1. ノードaからノードpへのエッジの重みに10000(比較的大きい数)を設定
         2. ノードaからノードqへのエッジの重みに10000(比較的大きい数)を設定
         3. ノードpからノードaへのエッジの重みに，V(αp, βq)-V(βp, βq)か0のうち大きいほうを設定
         4. ノードqからノードaへのエッジの重みに，V(βp, αq)-V(βp, βq)か0のうち大きいほうを設定
      5. もし，V(βp, βq) ≧ V(αp, αq)ならば，
         1. ノードpからノードaへのエッジの重みに10000(比較的大きい数)を設定
         2. ノードqからノードaへのエッジの重みに10000(比較的大きい数)を設定
         3. ノードaからノードpへのエッジの重みに，V(αp, βq)-V(αp, αq)か0のうち大きいほうを設定
         4. ノードaからノードqへのエッジの重みに，V(βp, αq)-V(αp, αq)か0のうち大きいほうを設定
      6. 最大流・最小カットアルゴリズムを適用し，総コストE'を計算
      7. もし，E > E' ならば
         1. 現在のラベルβkを求まったラベル更新
         2. 総コストの更新(E = E')
   5. グラフの消去
5. 総コストが収束するまで4を繰り返す

コスト関数

コスト関数は，アルファ拡張，階層グラフカットのどちらも講義で紹介されたものを参考にした．

• データコスト
  • 出力画像fpが入力画像Ipに出来るだけ近くなるようにする項
  • D(β) = SAD(β) = Σ|I(x, y) - I(x - β, y)|
• スムーズコスト
  • 隣り合った画素fp，fqの明るさが出来るだけ近くなるようにする項
  • V(fp) = |fp - fq|

---

実行結果

α拡張を用いたステレオマッチング，階層グラ フカットを用いたステレオマッチングを行った．現在のラベルβ の初期値は0とした．入力画像とα拡張を用いた場合の実行結果， 階層グラフカットを用いた結果を示す．なお，どちらの視差画像も，最大階調を 256に変換した結果である．

入力画像

左画像 (300×250)	右画像 (300x250)

結果画像

階層グラフカットによる結果画像 実行時間：13.8sec	α拡張による結果画像 実行時間：50.3sec

α拡張と階層グラフカットによるステレオマッチングの結果を比較すると， 精度に明らかな差が生じていることがわかる．α拡張ではラベルαを0〜最大視差 まで変化させているのに対して，階層グラフカットではラベルを段階的に変化 させているため精度が悪いと考えられる．しかし，実行速度ではα拡張よりも 訳4〜5倍の速度を計測した． 今回はラベルの初期値をすべて0にしているが，ブロックマッチングの結果を 初期値とすることなどにより精度の向上が見込めると考える．

---

ソースプログラム等
　

□用いたライブラリ

MAXFLOW

グラフカットのライブラリ

http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/software.html

□α拡張

alphaExtend DownLoad (zip)

階層グラフカット

hierarchicalGraphCut DownLoad (zip)

ソースプログラムを用いるにあたって

以下の点に注意してください．

1. 入力画像はppmまたはppm，かつascii形式でしか実行できません．
2. また出力画像はpgm形式のみとなっています．
3. 出力は，最大階調を256に調整したものです．
4. コンパイル方法は，makeコマンドで．
5. 以下のコマンドを実行

 
  $ ./GraphCut [leftimagefile] [rightimagefile] [outputfile]