IPSJ SIG Technical Report Vol.2009-CVIM-168 No /8/ (2003) Costeira Kanade (1998) AIC Vidal (2005) GPCA Taubin 3 2 EM Multi-stage Opt

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2009-CVIM-168 No /8/ (2003) Costeira Kanade (1998) AIC Vidal (2005) GPCA Taubin 3 2 EM Multi-stage Opt"

えいしろうおおはし
4 years ago
Views:

1 () osteira Kanade (998) AI Vidal (5) GPA Taubin EM Multi-stage Optimization of Multi-body Motion Segmentation Using Generalized Principal omponent Analysis Shinya Tanaka, Yuuki Tanaka, Hirotaka Hara, Yasuyuki Sugaya and Kenichi Kanatani We propose a new method for segmenting multi-body motions in a video stream. Our method improves the multi-stage optimization of Sugaya and Kanatani (). While they computed initial segmentation by search based on the shape interaction matrix of osteira and Kanade (998) and model selection by the geometric AI, we fit two planes in -D by the Taubin method based on the GPA of Vidal et al. (5). As a result, we can obtain without doing any search an initial segmentation which is by itself a very good approximation. It is then progressively optimized by the EM algorithm. Using simulated and real video data, we demonstrate the effectiveness of our method. We also visually display the underlying geometric structure.. osteira ) osteira ) Gear ) 6) QR 5) 7) 4),5) AI Wu 6) Gruber 4) EM 9) Vidal 4),5) (GPA) Fan ) Yan 7) Schindler 7) Rao 6) (MDL) 9) Vidal 4),5) (GPA) 9) Tron ) EM EM ) 9) osteira ) AI 9) Vidal 4),5) GPA EM Johns Hopkins Hopkins55 ) Department of omputer Science, Okayama University Department of Information and omputer Sciences, Toyohashi University of Technology c 9 Information Processing Society of Japan

2 . N {p α } M κ α p α (x κα, y κα), κ =,..., M, α =,..., N M p α = (x α y α x α y α x Mα y Mα ) () M Z XY Z p α (a α, b α, c α ) κ t κ {i κ, j κ, k κ} p α κ r κα r κα = t κ + a α i κ + b α j κ + c α k κ () 8) r κα ( ) x κα y κα = A κ r κα + b κ () A κ, b κ κ ( ) () () x κα y κα = m κ + a α m κ + b α m κ + c α m κ (4) m κ, m κ, m κ, m κ κ κ =,..., M () () p α p α = m + a αm + b αm + c αm (5) m i, i =,,, m iκ κ =,..., M M. (5) p α M {m, m, m, m } 4 m m m m m (a) O m m m m m m O (b) (a) (b) {p α } 4 (5) m α p α {m, m, m, m } 4 {p α } Z XY k κ Z (5) m m, m, m (a) () i κ, j κ X Y i, j (5) m, m (b) osteira ) 9) EM osteira ) AI 9) 5) Vidal 4) GPA m c 9 Information Processing Society of Japan

3 EM 4. () M M 5 5 M M d ( ) {p α } p p α p = N p N α, p α = p α p (6) ( ) M N ) ( p,..., p N = U diag(σ,..., σ r )V (7) r = min(m, N) U r M r V r N r σ σ r ( ) diag(σ,..., σ r ) ( ) U i u i d r α, α =,..., N ( r α = ( p α, u ),..., ( p α, u d )) (8) 5. Ax + By + z + D = n, x n = (A, B,, D), x = (x, y, z, ) (9) (n, x) = a, b (a, b) n n (n, x) =, (n, x) = (n, x)(n, x) = (x, n n x) = (x, Qx) = () Q ) Q = n n + n n () Q ) λ > = > λ u, u, u, u 4 Q ) ( Q = λ u u λ u 4u λ 4 = u + ( ) λ + u λ u 4 + λ ( λ u + )( u4 λ u 4 ) λ u λ u4 ) () () n, n Q n, n n = λ u + λ u 4, n = λ u λ u 4 () N (9) x x,..., x N (x α, Qx α ), α =,..., N (4) Q () n, n (x, y, z) Ax + By + z + D = d ) d = Ax + By + z + D A + B + (5) c 9 Information Processing Society of Japan

4 EM Vidal 4),5) GPA () 6. Taubin (4) Q x (9) Q (x, Qx) = ) ) (4) Q ),) 9 z α, u z α = (x α, y α, z α, y αz α, z αx α, x αy α, x α, y α, z α) v = (Q, Q, Q, Q, Q, Q, Q 4, Q 4, Q 4 ) (6) (4) (z α, v) + Q 44, α =,..., N (7) v, Q 44 Taubin ),),) ),),) x α, y α, z α σ x α, y α, z α z α z α (6) x α, y α, z α z α = (x α x α, y α y α, z α z α, y αz α + y α z α,..., z α) (8) z α V [z α ] = E[ z α z α ] E[ x α ] = E[ y α ] = E[ z α ] =, E[ y α z α ] = E[ z α x α ] = E[ x α y α ] =, E[ x α] = E[ y α] = E[ z α] = σ V [z α ] = σ V [z α ] (9) V [z α ] = x α z αx α x αy α x α yα y αz α x αy α y α zα y αz α z αx α z α yα + zα x αy α z αx α z α y α zα + x α y αz α z α x α x α + y α y α x α Taubin J TB ),),) ) N ((z α, v) + Q 44 J TB = N (v, V [z α ]v) v, Q 44 ),) ( ) {z α } z z α z α z = N z α, z α = z α z () N ( ) 9 9 M TB, N TB N N M TB = z α z α, N TB = V [z α ] () ( ) A () () M TBv = λn TBv (4) λ v ( 4 ) Q 44 Q 44 = ( z, v) (5) 7. EM ( ) ( ) 5 ( ) 7, 4 c 9 Information Processing Society of Japan

5 9) n r α, α =,..., N d (n d + ) EM ) ( ) r α k =, W (k) α { W α (k) r α k = ( ) k =, ( a ) k w (k) w (k) = N W α (k) (7) N (6) ( b ) w (k) d/n d ( c ) k r (k) N r (k) = W (k) α r α N W (k) α ( d ) k M (k) = N W (k) α (r α r (k) N W (k) α n λ (k) λ (k) n )(r α r (k) ) u (k) ( e ) k P (k) P (k) P (k) = d i= (8) (9),..., u(k) n u (k) i u (k) i, P (k) = I P (k) () ( ) σ ˆσ N = min[ (n d)(n d ) tr(w() P () M () P () + w() P () M () P () ), σ min] () σ min. tr ( 4 ) k =, V (k) V (k) = P (k) M (k) P (k) + ˆσ P (k) () ( 5 ) r α, α =,..., N ( a ) r α P (α k), k =, (k),v (k) (r α r (k) ))/ P (α k) = e (rα r () det V (k) ( b ) r α W (k) α W (k) α = ( 6 ) {W (k) α, k =, w (k) P (α k) w () P (α ) + w () P (α ) } ( 7 ) r α W α (k), k =, k n = 5, d = n = 7, d = n =, d = (d) M (k) M = w () M () + w () M () (5) n λ λ n u,..., u n P (k) P (k) P () = P () = P, P () = P () = P d P = u iu i, P = I P (6) i= σ ˆσ N = min[ (n d)(n d ) tr(p MP ), σmin] (7) 7 P (α k) () V (k) n () det V (k) (4) 5 c 9 Information Processing Society of Japan

6 4 6 8 σ σ (a) (b) (c) σ ( ) (4 ) (a) (b) (c) 5 σ ) Taubin ) ) 5 ) 7 AI 9) (a) (b) (c) (a) (b), (c) Taubin x, y σ( ) σ 5 Taubin Vidal 4),5) GPA (a) (b) (c) Taubin 8. Johns Hopkins Hopkins55 ) 6 Vidal 4) RANSA, Yan 7) % % c 9 Information Processing Society of Japan

情報処理学会研究報告フレーム数 4 軌跡数フレーム数 9 軌跡数 5 フレーム数軌跡数 5 フレーム数軌跡数 59 フレーム数軌跡数 469 フレーム数軌跡数 7 表図の画像例に対する提案手法の各段階の正解率 (%) と菅谷ら Vidal ら RANSA Yan らの結果 (a) (b) (c) (d) (e) 初期分類第

本論文では運動のタイプデータを次元表示によって提案方法の幾何学的な構造を視覚的に示したとその退化などの幾何学的構造の解析に立脚しているためそのような考察が可能となる謝辞: 本研究に関して有益な議論をして頂いた米国 Johns Hopkins 大学の Re ne Vidal 博士の感謝する本研究の一部は文部科学省科学研究費基盤研究

Kanade, A multibody factorization method for independently moving objects, Int. J. omputer Vision, 9-, 59 79, Sept. 998. ) Z. Fan, J. Zhou and Y.

Gear, Multibody grouping from motion images, Int. J. omput. Vision, 9-, 5, Aug./Sept. 998. 4) A. Gruber and Y.

769 775, June-July 4, Washington, D, U.S.A. 5) 市村直幸, 形状空間への直交射影行列と判別基準を用いた複数運動の分割, 情報処理学会研究報告, -VIM--, 7 4, Jan.

7 情報処理学会研究報告フレーム数 4 軌跡数フレーム数 9 軌跡数 5 フレーム数軌跡数 5 フレーム数軌跡数 59 フレーム数軌跡数 469 フレーム数軌跡数 7 表図の画像例に対する提案手法の各段階の正解率 (%) と菅谷ら Vidal ら RANSA Yan らの結果 (a) (b) (c) (d) (e) 初期分類第段階第段階第段階菅谷ら Vidal ら RANSA Yan ら (a) (b) (c) (d) (e) (f) (f) 図 Hopkins55 データベースのビデオ画像の特徴点上と軌跡の次元表示下学的な議論に基いているためどのような状況で正しく分離できどのような状況では正しシミュレーションおよび実ビデオデータを用いて提案方法の有効性を実証したさらに軌跡く分離されにくいのかが考察できないためであるそれに対して本論文では運動のタイプデータを次元表示によって提案方法の幾何学的な構造を視覚的に示したとその退化などの幾何学的構造の解析に立脚しているためそのような考察が可能となる謝辞: 本研究に関して有益な議論をして頂いた米国 Johns Hopkins 大学の Re ne Vidal 博士の感謝する本研究の一部は文部科学省科学研究費基盤研究 (No. 57) の助成によった図の下段から分かるように複雑な次元運動をしているように見えても次元表示では軌跡がほぼ平行な平面上に載ることが多く提案方法の高い性能はこの事実に立脚し参考文献ている従来この事実には十分注意が払われていなかった 9. ) J. P. osteira and T. Kanade, A multibody factorization method for independently moving objects, Int. J. omputer Vision, 9-, 59 79, Sept ) Z. Fan, J. Zhou and Y. Wu, Multibody grouping by inference of multiple subspace from high-dimensional data using oriented-frames, IEEE Trans Patt. Anal. Mach. Intell., 8- (6-), 9 5. ). W. Gear, Multibody grouping from motion images, Int. J. omput. Vision, 9-, 5, Aug./Sept ) A. Gruber and Y. Weiss, Multibody factorization with uncertainty and missing data using the EM algorithm Proc. IEEE onf. omput. Vision Patt. Recog., Vol., pp , June-July 4, Washington, D, U.S.A. 5) 市村直幸, 形状空間への直交射影行列と判別基準を用いた複数運動の分割, 情報処理学会研究報告, -VIM--, 7 4, Jan.. 6) 市村直幸, 富田文明, 形状行列からの特徴選択に基づく動きの分割, 電子情報通信学会論文誌 D-II, J8-D-II-, , Dec まとめ本論文ではビデオ画像上の複数の運動を分離する新しい方法を提案したこれは著者らの以前の方法菅谷ら9) を改良したものである最大の改良点は菅谷ら9) では初期分類を osteira ら) の作用行列と幾何学的 AI9) による探索によって求たのに対して本論文では Vidal ら4),5) の GPA の考え方に基づいた Taubin 法による次元空間の平面の当てはめを用いたことであるこれにより解が探索なしに直接に求まるだけでなくそれ自身でよい精度の分離が得られこれを段階的な EM アルゴリズムによって最適化したさらに菅谷ら9) では 8 次元空間において分離を行っていたが本論文では段階ごとに次元 5 次元 7 次元と次元を上げたまた菅谷ら9) では誤差のないシミュレーションデータで計算が破綻することがあったが本論文ではそれを判定して破綻を防いでいるそして 7 c 9 Information Processing Society of Japan

8 7),,, PRMU-45, 9 6, July. 8),,,, D-II, J74-D-II-8, , Aug ) K. Kanatani, Statistical Optimization for Geometric omputation: Theory and Practice, Elsevier Science, Amsterdam, the Netherlands, 996; Reprinted, Dover, New York, NY, U.S.A., 5. ),,, 998. ),,, 5. ) K. Kanatani, Statistical optimization for geometric fitting: Theoretical accuracy analysis and high order error analysis, Int. J. omput. Vision, 8- (8-), ) K. Kanatani and Y. Sugaya, Performance evaluation of iterative geometric fitting algorithms, omp. Stat. Data Anal., 5- (7-), 8. 4), -VIM-4-4 5, Nov.. 5), -VIM-5-5, Mar.. 6) S. R. Rao, R. Tron, R. Viadl and Y. Ma, Motion segmentation via robust subspace separation in the presence of outlying, incomplete, or corrupted trajectories, Proc. IEEE onf. omput. Vision Patt. Recog., June 8, Anchorage, AK, U.S.A. 7) K. Schindler, D. Suter and H. Wang, A model-selection framework for multibody structure-and-motion of image sequences, Int. J. omput. Vision, 79- (8-8), pp ),,,, -VIM--4, 77 84, May. 9),,, -VIM-8-5, 85 9, May. ),, [II], 9-4 (9-4), 6. ) G. Taubin, Estimation of planer curves, surfaces, and non-planar space curves defined by implicit equations with applications to edge and range image segmentation, IEEE Trans. Patt. Anal. Mach. Intell., - (99-), 5 8. ). Tomasi and T. Kanade, Detection and Tracking of Point Features, MU Tech. Rep. MU-S-9-, Apr. 99; ) R. Tron and R. Vidal, A benchmark for the comparson of -D motion segmentation algorithms, Proc. IEEE onf. omput. Vision Patt. Recog., June 7, Minneapolis, MN, U.S.A. 4) R. Vidal, Y. Ma and S. Sastry, Generalized principal component analysis (GPA), IEEE Trans. Patt. Anal. Mach. Intell., 7- (5-), ) R. Vidal, R. Tron and R. Hartley, Multiframe motion segmentation with missing data using PowerFactorization and GPA, Int. J. omput. Vision, 79- (8-8), ) Y. Wu, Z. Zhang, T. S. Huang and J. Y. Lin, Multibody grouping via orthogonal subspace decomposition, sequences under affine projection, Proc. IEEE onf. omputer Vision Pattern Recog., Vol., pp.695 7, Kauai, Hawaii, U.S.A., Dec.. 7) J. Yan and M. Pollefeys, A general framework for motion segmentation: Independent, articulate, rigid, non-rigid, degenerate and nondegenerate, Proc. Euro. onf. omput. Vision., Vol. 4, pp. 94 4, Grazz, Austria, May 6. 8 c 9 Information Processing Society of Japan

(a) (b) (c) Canny (d) 1 ( x α, y α ) 3 (x α, y α ) (a) A 2 + B 2 + C 2 + D 2 + E 2 + F 2 = 1 (3) u ξ α u (A, B, C, D, E, F ) (4) ξ α (x 2 α, 2x α y α,

(a) (b) (c) Canny (d) 1 ( x α, y α ) 3 (x α, y α ) (a) A 2 + B 2 + C 2 + D 2 + E 2 + F 2 = 1 (3) u ξ α u (A, B, C, D, E, F ) (4) ξ α (x 2 α, 2x α y α, [II] Optimization Computation for 3-D Understanding of Images [II]: Ellipse Fitting 1. (1) 2. (2) (edge detection) (edge) (zero-crossing) Canny (Canny operator) (3) 1(a) [I] [II] [III] [IV ] E-mail sugaya@iim.ics.tut.ac.jp