,a) D. Marr D. Marr. (feature-based) (area-based) (Dense Stereo Vision) van der Mark [] (Intelligent Vehicle: IV) SAD(Sum of Absolute Difference) Intel x86 CPU SSE2(Streaming SIMD Extensions 2) CPU IV [] 3 [2] (HSP: Hypothetical Surface Point) ( ) ( ) Vogiatzis [3] Vogiatzis a) bb523327@cc.nagasaki-u.ac.jp (voxel) 2 3 2 29 29 8 3 Vogiatzis 560 460 360 36 40 Kolmogorov [4] n m C O(mn 2 C ) m n O(n 3 C ) Kolmogorov Ford-Fulkerson Push-Relabel [5] (sparse graph) 30fps 30fps /30 = 33[ms] 2 c 203 Information Processing Society of Japan
Ford-Fulkerson Push-Relabel Kolmogorov IV D. Marr [6] D. Marr GPU(Graphics Processing Unit) FPGA (Field Programmable Gate Array) 2 3 4 5 2. 2. 3 (Horopter) 2 H H a, b, c Z( ) H(a, b, c) = { v = (u, v, w) Z 3 u [ a, a], v [ b, b], w [ c, c]} () Hypothetical Surface Point Left Camera Base Line Fig. w Horopter u Right Camera Horopter S 2 S = {s(v) v H } (2) u u v v w w (0, 0, 0) w = 0 u < 0 u > 0 (0, 0, ) (0, 0, ) v (0,, 0) c 203 Information Processing Society of Japan 2
t 2 0 - -2-0 3 Fig. 3 An example of Horopter t s (2, 0, -) (2, 0, ) (2, 0, 0) 2 Fig. 2 A graph which is generated by likelihood of HSPs (, 0, -) (, 0, 0) (, 0, ) 2.2 V E G(V, E) G(V, E) 2 3 w = c 2 w = c 2 ( ) [2] H(, 0, 2) H(, 0, 2) 3 3 (2, 0, -) Fig. 4 (0, 0, -) (0, 0, 0) (0, 0, ) (-, 0, -) (-, 0, 0) s those red-colored edges has constant cost. 4 (2, 0, 0) (2, 0, ) 3 (-, 0, ) A graphical representation of the Horopter 4 4 c 203 Information Processing Society of Japan 3
3. 3. ( ) initialize surface_to_cut; while (cost of cut is changing) { for (e in E surface ) { if (ϕ next (e) < ϕ prev (e)) { move(surface_to_cut); } } } points which has largest likelihood in a depth high likelihood 5 Fig. 5 low Likelihood of HSPs in the Horopter () (u, v, z) u, v w 2 max(u, v) u, v w = max(u, v) (u, v, w) 3 5 6 6 ( ) 6 t s the cut of this graph = the surface 5 Fig. 6 a cut of the graph c 203 Information Processing Society of Japan 4
情報処理学会研究報告 今回用いた評価関数は ϕ (v) = p s(n) s(v) + i (s(v), s(n)) n Sn (s(v)) +c(s(v)) ϕ2 (v) = p {s(n) s(v)} 2 n Sn (s(v)) (3) + i2 (s(v), s(n)) +c(s(v)) (4) の 2 つである まず ϕ2 を評価関数としてカットの変更を 繰り返す この評価関数 ϕ2 は表面をなめらかにする性質 をもっている カットのコストが収束すれば 次は ϕ を 評価関数としてカットの変更を繰り返す その時カットの コストが収束した時点でアルゴリズムは終了となる ここ で Sn (s(v)) は近傍を表す表面存在仮説点の集合で Sn (s(v)) = {s(u, v, max(u, v)), s(u +, v, max(u +, v)), s(u, v, max(u, v )), s(u, v +, max(u, v + ))} (5) となり p はペナルティエッジのコストを示している 関数 in (s(v), s(n)) は 左右のカメラから見えるはずのない表面 の傾きを禁止するための関数である 大きな傾きに対して コストを付加することによって 傾きを小さくする方向への 図 7 実験で用いた画像の一部 動きを促す働きをもつ v = (vu, vv, vw ) n = (nu, nv, nw ) Fig. 7 A part of an image which was used in this experiment とし q を禁止エッジの大きさとすると以下のように表さ 4. 実験の概要 れる { in (s(v), s(n)) = q nw un n ( nw vn > d) 0 (wise) 実験では小栗らによるグラフカットによる表面検出 [2] (6) と本研究における協調的アルゴリズムを用いた手法の 2 つ を 43 組のステレオ画像で比較した 比較の対象は処理時 そ し て c(s(v)) は 表 面 存 在 仮 説 点 s(v) の 尤 度 か 間とカットのコストである 加えて 協調的アルゴリズ ら 導 出 さ れ た グ ラ フ に お け る コ ス ト で あ る こ の ムでは最初に与えるカットによる解の違い および反復 評 価 関 数 を s(u, v, max(u, v)), s(u, v, max(u, v) ), 回数の検証を行った 今回の実験で用いた画像の一部を s(u, v, max(u, v) + ) で計算し 評価関数の小さい方を 図 7,, に示す 新しいカットとする 4.2 実験環境 実験で用いたマシンは以下の通りである 3.2 計算量 本手法の計算量であるが グラフ全体を見て計算を行う CPU: Intel Core i7 920 のではなく あくまで事前に与えられたカット つまり検出 メモリ: 2GB DDR3 された表面の周辺のみを見て計算を行うので計算量はホロ OS: Ubuntu 2.04 LTS (64bit) プタ座標 H(a, b, c) のとき反復回数を n とすれば O(nab) となる 対して Kolmogorov らのグラフカットアルゴリズ 4.3 実験結果 ムの最悪の場合の時間計算量は O(mn C ) である ホロ 4.3. カットのコスト 2 プタ座標 H(a, b, c) とすれば 計算量は O((abc) C ) とす 3 ることができる 4. 実験 本研究における実験について以下に述べる c 203 Information Processing Society of Japan ホロプタの奥行き方向で最も尤度の高い表面存在仮説点 を選択して初期カットを求めたときのカットのコストの推 移を図 8 に示す 図 8 は反復回数を変化させた時にカット のコストがどのように変化するかを表したグラフである グラフ中では 43 組のステレオ画像の中から 0 組を選択 5
000 00 cost of cut 0 0 50 00 50 200 250 300 iteration 8 ( ) Fig. 8 The transition of the cost of cut (best likelihood in depth) 3 7 8 40-500 50 2.2 7,, 9 9 2 0 2 7,, 9 4.3.2 43 9 Fig. 9 cost of cut 000 00 0 ( ) Results of the processing (best likelihood in depth) 0 50 00 50 200 250 300 iteration Fig. 0 0 ( ) The transition of the cost of cut (planar surface) 2 sec 2 60 70 c 203 Information Processing Society of Japan 6
Simulated Annealing(SA) [] van der Mark, W. and Gavrilla, D. M.: Real-time dense stereo for intelligent vehicles, IEEE Trans. Intelligent Transportation Systems, Vol. 7, No., pp. 38 50 (2006). [2] CVIM (203). [3] Vogiatzis, G., Torr, P. H. S. and Cipolla, R.: Multi-view stereo via volumetric graph-cuts, Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, Vol. 2, pp. 39 398 vol. 2 (2005). [4] Boykov, Y. and Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 26, No. 9, pp. 24 37 (2004). [5] Goldberg, A. V. and Targan, R. E.: Journal of the Association of Computing Machinery, Vol. 35, No. 4, pp. 92 940 (988). [6] Marr, D.: (987). Fig. ( ) Results of the processing (planar surface) ( ) Table processing time (best likelihood in depth) 0.462 (77.2 steps) 27.4243 0.36 (54.76 steps) 24.9659 Table 2 2 ( ) processing time (planar surface) 0.63 (73.47 steps) 27.60 0.36 (50.7 steps) 25. 5. 3 /0 c 203 Information Processing Society of Japan 7