こちらのpdfファイル

GPUによるステレオ視
アルゴリズムの高速化
独立行政法人産業技術総合研究所
デジタルヒューマン研究センター 研究員
山崎 俊太郎
[email protected]
http://staff.aist.go.jp/shun-yamazaki/
GPUとは
„
Graphics Processing Unit
…
„
「3Dグラフィックスアクセラレータ」から「GPU」へ
演算性能の向上
…
3次元座標変換（4x4行列演算）
… ラスター処理（サンプリング・フラグメント処理）
… SIMD型計算機
„
処理の柔軟性の向上
…
…
プログラム可能
IEEE 32bit 浮動小数点演算
CPU vs GPU
後藤弘茂氏のWebサイトより
http://pc.watch.impress.co.jp/docs/2004/0421/kaigai085.htm
CPU vs GPU
„
Pentium4 (Prescott)
…
3.4GHz∼
… 総トランジスタ数=125M
… ロジック用=68M
„
GeForce6800 (NV40)
…
400MHz∼
… 総トランジスタ数=222M
GPU = SIMDプロセッサ
後藤弘茂氏のWebサイトより
http://pc.watch.impress.co.jp/docs/2004/0421/kaigai085.htm
GPUを用いた汎用計算
„
GPUを演算器として利用
…
…
„
CPUと比べて各種の制限がある
…
…
„
座標変換行列・テクスチャとしてデータを入力
フレームバッファの内容を主記憶に読み出す
動的な分岐・反復の計算コストが高い
メモリアクセス・レジスタ数・命令長に制限がある
汎用計算アルゴリズムの実装
…
…
…
…
線型代数演算
物理シミュレーション・衝突判定
ビジョンアルゴリズム
参考サイト： GPGPU（http://www.gpgpu.org/）
ステレオ視による立体復元
„
入力
同一物体を撮影した2つの画像
… 画像を計測したカメラの姿勢，レンズ歪み
…
„
出力
…
1つの画像の各画素に対する物体の深度
… または画像間の対応点
„
アルゴリズム
…
1次元の領域探索
„
エピポーラ拘束
ステレオ視アルゴリズムの分類
„
大域最適化
高精度
… 計算量が多い・データ依存
… オクルージョンの扱いなど高度な処理が可能
… 例） Scan-line DP, Graph Cut Minimization, など
…
„
局所最適化
精度は必ずしも良くない
… 計算量が少ない・計算速度を一定にできる
… 実時間アルゴリズムは画素相関を用いる方法が主流
…
ステレオ視の高速化
„
専用ハードウェアを利用する方法
„
CPU内臓のDSP演算機能を利用する方法
…
MMX，SSE，SSE2，SSE3など
… CPUの資源を食い尽くしてしまう
… 認識など他の処理を行う必要があるとき不都合
„
GPUを用いる方法
…
CPUの負荷は非常に小さい
… CPUで行うより高速！
GPUを用いた実時間ステレオ法
„
今回は2眼ステレオを扱う
…
„
多視点への拡張は比較的容易
参考にした論文
…
R. Yang, M. Pollefeys, H. Yang, G. Welch,
"A Unified Approach to Real-Time, Multi-Resolution, Multi-Baseline 2D View
Synthesis and 3D Depth Estimation using Commodity Graphics Hardware",
International Journal of Image and Graphics (to appear), 2004
… J. Woetzel and R. Koch,
"Real-time multi-stereo depth estimation on GPU with approximative discontinuity
handling",
1st European Conference on Visual Media Production (CVMP), 2004
処理の流れ
1.
2.
3.
4.
5.
準備
レクティフィケーション
対応コストの計算
対応コストの集合化
対応点の決定
GPUの準備
1.
2画像をテクスチャTref,Tobjとして読み込む
2.
四角形ポリゴンを画像と同サイズで描画
„
描画先は別のテクスチャ
ポリゴンにテクスチャを割り当てる
3.
„
„
マルチテクスチャを利用
ポリゴンと画像がちょうど重なるようにテクスチャ座標を設定
レクティフィケーション
„
カメラの主軸の平行化
対応点の探索範囲を画像の走査線方向と一致させる
… x軸（横軸）方向とする
…
„
レンズ歪みの除去
GPUによるレクティフィケーション
„
カメラの平行化＝3x3行列変換（ホモグラフィ）
…
…
„
射影テクスチャマップを利用
Vertex Shaderでテクスチャ座標を前処理
レンズ歪みの除去
…
…
ポリゴンをグリッドに分割し変形
依存テクスチャマップを利用
1.
2.
3.
„
1つの画像読み込みのためにテクスチャを2つ準備
テクスチャ１から歪みを取得
それをテクスチャ座標としてテクスチャ２（ Tref,Tobj ）から画素を取得
平行化された画像の画素に対応するフラグメントを生成
対応コストの計算
„
Tref の座標(x,y)における画素に対し
Tref から (x,y) の画素 tref を取得
… Tobj から (x+d,y) の画素 tobj を取得
… AD = | tref - tobj | を取得
（AD ＝ Absolute Distance ）
…
„
以上を N 個の d に対して行う
…
„
N disparity hypothesis
N 個の対応コストを元に対応点を決定
GPUによる対応コストの計算
„
座標(x,y)におけるフラグメントに対し
…
…
…
„
（ｄ：視差）
以上をN種類の d に対して行う
…
…
„
Tref から (x,y) の画素 tref を取得
Tobj から (x+d,y) の画素 tobj を取得
| tref - tobj | を取得
ポリゴンをN回描画する
テクスチャに書き出す（ADテクスチャ）
テクスチャのRGBAチャネルを使った高速化
…
…
4個の異なる d に対する AD を同時に評価
画像のRGB値に対する AD を同時に評価
対応コストの集合化
„
画素単位のADは信頼性が低い
ノイズの影響
… 画像のサンプリングの影響
…
„
近傍画素の対応コストの和（SAD）を用いて処理を頑健化
…
領域窓を用いたコスト関数
„
„
窓サイズの決定が困難
オクルージョン領域で誤差が拡大
階層的な対応点探索
… 適応的な窓形状の変形
…
（SAD ＝ Sum of AD）
GPUを用いた階層的な探索
„
階層化
…
テクスチャのMIPMAP（4分木による多重解像度表現）を利用
ADテクスチャのMIPMAP ＝ 階層的SADテクスチャ
… MIPMAPの生成は高速
… 領域窓の位置やサイズの自由度は小さい
… 2のべき乗の位置にある座標でのみ正確なSADが得られる
…
„
その他の位置での値はSADテクスチャを線型補間
GPUを用いた適応的窓形状選択
„
窓形状の選択
1.
2.
3.
„
2．
フラグメントごとにコストを計算し，
ADテクスチャに書き出す
テクスチャの双線型補間を用いて
4x4領域のコストの和を取得（4x4-SADテクスチャ）
隣接する4つの領域のうち
3．
4x4-SADが最小の2つを選択して中央に加える
（適応的SADテクスチャ）
6種類の窓形状に対応
対応点の決定
„
領域窓内のSADが最小となる視差dを選択
„
GPUによる視差の選択
視差dをフラグメント色として描画
… 対応コストをフラグメントの「Z値」として描画
… Zバッファ法を用いて最小のｄを得る
…
計算結果の正当性の評価
„
交差テスト
… Tref,Tobjを入れ替えて視差を計算
… 対称にならない画素の対応は不定とする
画素
„
GPUによる交差テスト
視差
… SADテクスチャをそれぞれ作成
… テクスチャを右図のように比較
TrefのSAD
TobjのSAD
実験結果
„
„
„
Pentium4 2.8GHz 512MB RAM
Radeon9800 XT 256MB VRAM
OpenGL ＋ ARB extensions
disparity estimation / sec
CPU
80 M
GPU
289 M
その他のビジョンアルゴリズム
„
Visual Hull
…
„
Ming Li, Marcus Magnor, Hans-Peter Seidel,
"Improved Hardware-Accelerated Visual Hull Rendering",
VISION, MODELING, AND VISUALIZATION 2003 (VMV2003)
Space Carving
…
Ming Li, Marcus Magnor and Hans-Peter Seidel,
"Hardware-Accelerated Rendering of Photo Hulls",
EUROGRAPHICS 2004