Contents
【 トップ 】
【 プログラム 】
【 アルゴリズム 】
【 実行環境 】
【 実行結果 】
【 考察 】

階層グラフカットを用いたステレオマッチング

向井友宏

Go to English Page

作成したプログラム
  • ダウンロード

    • alpha.zip
    kaisou.zip
    今回作成したプログラム、ライブラリ、makefile、画像ファイルをまとめたzipファイルです。これだけあればプログラムを動かすことができます。上が懼ｧｱ拡張グラフカット、下が階層グラフカットです。プログラムとライブラリは C++ で記述されています。


  • コンパイル方法・実行方法（コマンドライン）

    • 上のzipファイルを解凍後 "alpha" または "kaisou" フォルダに移動し、makeコマンドを実行すればコンパイルできます。
    ※　コンパイラとしてg++が必要

    実行ファイルに２つの引数を順番通りに与えて実行すると（順に「左視差画像」「右視差画像」）結果画像 "result.pgm" を出力します。同フォルダにある "start.sh" を実行すると試しにプログラムを動かせます。
    ※　画像形式は "pgm" に限ります


  • MAXFLOWライブラリ

    • 使用ライブラリ
    今回作成したプログラムは V.Kolmogorov によって作成された MAXFLOW ライブラリを使用しています。上のzipファイルの中に含まれているため、あらためてダウンロードする必要はありません。


  • 画像

    • middlebury callege １
    middlebury callege ２
    今回使用した画像やその他ステレオマッチングに利用できる画像をダウンロードできます。本プログラムで利用する場合はこれを画像編集ソフト等で "pgm" 形式に変換してお使いください。


アルゴリズム

  1. ２つの視差画像読み込み
  2. グラフのノード数、エッジ数を求める
    3. ※グラフの初期化の際に用いる
  3. 出力画像の初期化
    4. ※今回の結果画像は初期値は全て０で計算
  4. 階層グラフカットの場合はαの配列作成
  5. 第１のループに入る。以下第１のループ
    6. ・success=0とする
  6. 第２のループへ。以下第２のループ
    7. ・α拡張のとき　　　　　→0〜64
    ・階層グラフカットのとき→0〜αの配列の行数
  7. グラフの初期化
  8. 全てのピクセルについてノードを追加
    9. ・階層グラフカットの場合、αの配列中で現在のピクセル値に最も近いものをαとする
    ・ノードを追加し、ソース側にD(βp)、シンク側にD(αp)を設定
  9. 全ての隣接点についてノードを追加
    10. ・階層グラフカットの場合、隣接する２つのピクセル値に最も近いものをα配列の中から選びそれぞれα1、α2とする
    ・階層グラフカットの場合、もしα1==α2かつβp==βqであるならノード、エッジの追加は行わない（無駄を除去）
    ・α拡張の場合、もしβp==βqであるならノード、エッジの追加は行わない
    ・各隣接点ノードについてソース側にV(βp,βq)、シンク側にV(αp,αq)を設定
    ・隣接するピクセルに対して適切な重みのエッジを設定する
  10. maxflowを実行。もしそれまでの最小総コストよりも小さければsuccess=1とし、出力画像の画素値を書き換える
    11. ・全てのピクセルノードについて
    　もしそのピクセルノードがSOURCE側に割り振られていたなら値をαに更新する
  11. 第２のループを抜けた時、success=0ならば第１のループを抜ける
  12. 画像をメディアンフィルタにかけ、ノイズ除去
  13. 各ピクセルノード値を違いが分かりやすいように最適化
  14. 画像を出力し終了

※D(β) = | β - I | (Iは入力画素値)
※V(α,β) = c | α - β | (cは定数)

実行環境
  • OS:　Windows Vista + cygwin
  • CPU:　IntelCore2Quad Q9550
  • RAM:　4.00GB
  • コンパイラ:　gcc 3.4.4

実行結果

画像一覧　（サイズは全て450×375のものを使用）
画像表示中
左目画像

性能評価

  1. 画質

    2. 階層グラフカットを用いた結果画像よりも、α拡張グラフカットを用いたものの方がうまく出来ているといえる。



  2. 実行時間（初期値0で計測）

    3. α拡張グラフカット 階層グラフカット
    １回目 31.71 [s] 10.00 [s]
    ２回目 31.82 [s] 9.92 [s]
    ３回目 31.85 [s] 9.97 [s]
    平均 31.79 [s] 9.96 [s]

    実行速度は階層グラフカットを用いた実装のほうが約３倍高速であった。

考察
  • 画質について

    • どちらの手法を用いた場合もほぼ同じくらいの画質になると予想していたが、実際はα拡張グラフカットを用いたものの方が綺麗な画像を生成できた。原因として、α拡張グラフカットの場合、αの値を１つずつ増やしていく手法であるのに対し、階層グラフカットでは現在の出力画像の値によってαの値をとばしとばし決定しているため、多少大雑把になってしまうのではないかと考えられる。また階層グラフカットの場合、上記の理由から初期値に依存しやすいともいえる。
    また、どちらの手法も改良の余地がある。スムーズコスト関数に用いる定数を工夫するなどすることで、よりよい結果を得ることができると考える。(今回は定数c = 1 とした)


  • 実行時間について

    • 実行時間については、階層グラフカットを用いた手法のほうがかなり短かった。これは、ループの回数の違いが顕著に表れた結果であると考える。