画像応用数学特論 第6回レポート H22年1月14日(火)18時〆切

広島市立大学院

知能工学専攻　画像メディア工学研究室

重富　卓哉

課題内容

• 理論とアルゴリズムと仮定と考察をまとめよ
• ソースコードとその使用方法・コンパイル方法，画像形式・ライブラリの インストール方法について述べよ

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

講義資料に掲載されたアルゴリズムを以下に転載．

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を繰り返す

階層ラベルの作成

階層ラベルは以下に示す式により作成を行った．以下の図に，ラベル数が64の場 合の実行結果を示す．

図より，各階層ごとに正しくラベルが作成されていることが確認できる．

コスト関数

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

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

実行結果

上記のアルゴリズムによりアルファ拡張を用いたステレオマッチング，階層グラ フカットを用いたステレオマッチングを実装し，実験を行った．現在のラベルβ の初期値は0とした．入力画像(左画像)とアルファ拡張を用いた場合の実行結果， 階層グラフカットを用いた結果を示す．なお，どちらの視差画像も，最大階調を 256に変換した結果である．上からtsukuba，poster，venusである．

次に，実行速度を計測し，表にまとめた．

【実行速度】

入力画像	アルファ拡張	階層グラフカット	アルファ/階層
tsukuba	30.16	8.39	3.60
poster	44.49	10.20	4.36
venus	44.34	10.07	4.40

使用したライブラリ等

MAXFLOW

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

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

実験に用いたソースプログラム

アルファ拡張

alphaExtend.zipの中身と内容

Makefile : make でコンパイル可能

header.h : このソースプログラムのヘッダ

main.cpp : このソースプログラムのメイン

alphaExtend.cpp : アルファ拡張を行う関数など

costFunction.cpp : コストを計算する関数など

pnmread.cpp :　pgm, pnm画像を読み込む関数

pnmread.h : pnmread.cppのヘッダ

graph.h : MAXFLOWグラフカットのライブラリ

graph.cpp : MAXFLOWグラフカットのライブラリ

maxflow.cpp : MAXFLOWグラフカットのライブラリ

階層グラフカット

hierarchicalGraphCut.zipの中身と内容

Makefile : make でコンパイル可能

header.h : このソースプログラムのヘッダ

main.cpp : このソースプログラムのメイン

hierarchicalGraphCut.cpp : 階層グラフカットを行う関数など

costFunction.cpp : コストを計算する関数など

calchierachicalLabel.cpp : 階層ラベルを作成する関数など

pnmread.cpp :　pgm, pnm画像を読み込む関数

pnmread.h : pnmread.cppのヘッダ

graph.h : MAXFLOWグラフカットのライブラリ

graph.cpp : MAXFLOWグラフカットのライブラリ

maxflow.cpp : MAXFLOWグラフカットのライブラリ

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

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

1. 入力画像はpgmまたはppm，かつascii形式でしか実行できません．実験で 用いた画像は次のリンクでダウンロードできます． ImageData DownLoad (zip)
2. また出力画像はpgm形式のみとなっています．
3. 最大視差(MAX_DISPARITY)，階層ラベル数(NUM_OF_HIERARCHY)はそれぞれ header.hにあります．
4. 現在の出力は，最大階調を256に調整していません．
5. コンパイル方法は，makeコマンドで．

広島市立大学院

知能工学専攻　画像メディア工学研究室

重富　卓哉