IPSJ SIG Technical Report Vol.2013-CVIM-188 No /9/2 1,a) D. Marr D. Marr 1. (feature-based) (area-based) (Dense Stereo Vision) van der Ma

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2013-CVIM-188 No /9/2 1,a) D. Marr D. Marr 1. (feature-based) (area-based) (Dense Stereo Vision) van der Ma"

せせらわかはら
5 years ago
Views:

1 ,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) Vogiatzis 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

2 Ford-Fulkerson Push-Relabel Kolmogorov IV D. Marr [6] D. Marr GPU(Graphics Processing Unit) FPGA (Field Programmable Gate Array) (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

3 t 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

4 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) ( ) 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

)), s(u, v +, max(u, v + ))} (5) となり p はペナルティエッジのコストを示している関数 in (s(v), s(n)) は左右のカメラから見えるはずのない表面の傾きを禁止するための関数である大きな傾きに対してコストを付加することによって傾きを小さくする方向への図 7 実験で用いた画像の一部動きを促す働きをもつ v = (vu, vv, vw )

実験の概要れる { in (s(v), s(n)) = q nw un n ( nw vn > d) 0 (wise) 実験では小栗らによるグラフカットによる表面検出 [2] (6) と本研究における協調的アルゴリズムを用いた手法の 2 つを 43 組のステレオ画像で比較した比較の対象は処理時そして c(s(v)) は表面存在仮説点 s(v) の尤度か

5 情報処理学会研究報告今回用いた評価関数は ϕ (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.

6 cost of cut iteration 8 ( ) Fig. 8 The transition of the cost of cut (best likelihood in depth) ,, ,, Fig. 9 cost of cut ( ) Results of the processing (best likelihood in depth) iteration Fig. 0 0 ( ) The transition of the cost of cut (planar surface) 2 sec c 203 Information Processing Society of Japan 6

7 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 (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, CVPR IEEE Computer Society Conference on, Vol. 2, pp 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 (2004). [5] Goldberg, A. V. and Targan, R. E.: Journal of the Association of Computing Machinery, Vol. 35, No. 4, pp (988). [6] Marr, D.: (987). Fig. ( ) Results of the processing (planar surface) ( ) Table processing time (best likelihood in depth) (77.2 steps) (54.76 steps) Table 2 2 ( ) processing time (planar surface) 0.63 (73.47 steps) (50.7 steps) /0 c 203 Information Processing Society of Japan 7

IPSJ SIG Technical Report 1,a) 1,b) 1,c) 1,d) 2,e) 2,f) 2,g) 1. [1] [2] 2 [3] Osaka Prefecture University 1 1, Gakuencho, Naka, Sakai,

IPSJ SIG Technical Report 1,a) 1,b) 1,c) 1,d) 2,e) 2,f) 2,g) 1. [1] [2] 2 [3] Osaka Prefecture University 1 1, Gakuencho, Naka, Sakai, 1,a) 1,b) 1,c) 1,d) 2,e) 2,f) 2,g) 1. [1] [2] 2 [3] 1 599 8531 1 1 Osaka Prefecture University 1 1, Gakuencho, Naka, Sakai, Osaka 599 8531, Japan 2 565 0871 Osaka University 1 1, Yamadaoka, Suita, Osaka