階層グラフカットでステレオマッチング
2011/01/25
舩田 祐子
yfunada@cv.info.hiroshima-cu.ac.jp



ダウンロード
alpha_GraphCut.zip
Kaisou_GraphCut.zip

今回実装したプログラム、ライブラリ、makefile、画像ファイルをまとめたzipファイルです。
上がα拡張、下が階層グラフカットです。
これだけでプログラムを動かすことが可能です。


実装に用いたライブラリ
MIST
最大流最小カットのライブラリ

各ページからダウンロードできます。


コンパイル方法
make
コンパイラはg++です。


実行方法
./GraphCut 左画像 右画像 最大視差

画像形式は.bmpです。
各サンプルプログラムには実行用perlファイルAOUT.plがあります。
コマンドラインでperl AOUT.plと入力すれば、サンプル画像を用いた組み合わせで
プログラムが実行されます。

作成される画像は
・左画像、右画像をグレースケールに変換した画像(l_grayscale.bmp, r_grayscale.bmp)
・左画像にソーベルフィルタを適用した画像(sobel.bmp)
・0〜最大視差の濃淡画像(tmp.bmp)
・tmp.bmpを0〜255の濃淡画像に変換した画像(out.bmp)
です。


コスト関数
本プログラムに用いたコスト関数は以下のとおりです。

データコスト関数
SAD
D(fx,y) = Σ_Wx,y||Il(x,y) - Ir(x - fx,y ,y)||

スムーズコスト関数
V(fp, fq) = c|fp - fq|
・c = 1 if d > 50
・c = 5 if d <= 50
dはソーベルフィルタを適用し求めた各ピクセルのエッジの強度


アルゴリズム
実装したアルゴリズムを以下に示します。

・階層グラフカットを用いたステレオマッチング
  1. 左画像、右画像、最大視差を読み込む
  2. 最大視差から総ラベル数(2の累乗)を求める
  3. 左画像にソーベルフィルタをかけ、エッジの強度を求める
  4. グラフのノードの数とエッジの数を求める
  5. 初期値0としてラベルを初期化する
  6. 階層構造の配列Aを計算する
  7. E = とても大きな値
  8. for 0〜とても大きな値
    1. success = 0
    2. for i =0〜階層構造の配列の数
      1. グラフを初期化する
      2. ノードの追加を行う
        1. for p=すべてのピクセル
        2. A[i]のうち、βpに最も近い値をαpとする
        3. ノードの、SOURCE側にD(βp)、SINK側にD(αp)を設定
      3. end for
      4. for(p,q) = すべての隣接点
        1. A[i]のうち，βpに最も近い値をαpに設定
        2. A[i]のうち，βqに最も近い値をαqに設定
        3. ノードaの，SOURCE側にV(βp, βq), SINK側にV(αp, αq)を設定
        4. もし、V(βp, βq) <= V(αp, αq)の場合
          • ノードaからノードpのエッジの重みに10000を設定
          • ノードpからノードaのエッジの重みに, V(αp, βq) - V(βp, βq)か0のうち大きいほうを設定
          • ノードaからノードqのエッジの重みに10000を設定
          • ノードqからノードaのエッジの重みに, V(βp, αq) - V(βp, βq)か0のうち大きいほうを設定
        5. もし、V(βp, βq) > V(αp, αq)の場合
          • ノードpからノードaのエッジの重みに10000を設定
          • ノードaからノードpのエッジの重みに, V(αp, βq) - V(βp, βq)か0のうち大きいほうを設定
          • ノードqからノードaのエッジの重みに10000を設定
          • ノードaからノードqのエッジの重みに, V(βp, αq) - V(βp, βq)か0のうち大きいほうを設定
      5. end for
      6. 最大流・最小カットアルゴリズムの適用
      7. E' = 求まったラベルで計算した総コスト関数
      8. E' < Eなら、現在のラベルを求まったラベルにし、E = E'にし、success = 1にする
      9. 3*3のメディアンフィルタを適用する
      10. グラフの消去
    3. end for
    4. もしsuccess == 0ならループ脱出
  9. end for
  10. 0-255へ濃度階調変換を行う

・α拡張を用いたステレオマッチング
  1. 左画像、右画像、最大視差を読み込む
  2. 左画像にソーベルフィルタをかけ、エッジの強度を求める
  3. グラフのノードの数とエッジの数を求める
  4. 初期値0としてラベルを初期化する
  5. E = とても大きな値
  6. for 0〜とても大きな値
    1. success = 0
    2. for i =0〜最大視差
      1. グラフを初期化する
      2. ノードの追加を行う
        1. for p=すべてのピクセル
        2. ノードの、SOURCE側にD(fp)、SINK側にD(α)を設定
        3. ノードpとノードaのエッジの重み(双方向)にV(fp,α)を設定
        4. ノードqとノードaのエッジの重み(双方向)にV(α, fq)を設定
      3. end for
      4. 最大流・最小カットアルゴリズムの適用
      5. E' = 求まったラベルで計算した総コスト関数
      6. E' < Eなら、現在のラベルを求まったラベルにし、E = E'にし、success = 1にする
      7. 3*3のメディアンフィルタを適用する
      8. グラフの消去
    3. end for
    4. もしsuccess == 0ならループ脱出
  7. end for
  8. 0-255へ濃度階調変換を行う


実行結果
cones 最大視差63
teddy 最大視差63
tsukuba 最大視差15
それぞれステレオマッチングを行い、階調変換を行いました。
リンク先の画像は、
左画像　右画像
階層グラフカット　α拡張
と並んでいます。

計算時間
各例の計算時間は以下のとおりです。
単位:sec
階層グラフカットα拡張
cones13.17144.46
teddy13.25108.95
tsukuba7.6818.59


考察
階層グラフカットとα拡張では、α拡張の方が精度は高くなった。
計算時間を比較すると、階層グラフカットの方が全体的に短くなった。
全体として、最大視差が大きくなると計算時間が長くなり、
また、ステレオマッチングに用いるマスクのサイズを大きくすると計算時間が長くなった。