() 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
. 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
EM 4. () M 7 7 7 7 7 7 7 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
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 α ] = B @ 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
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
4 6 8 σ 4 6 8 σ (a) (b) (c) 4 6 8 σ ( ) (4 ) (a) (b) (c) 5 σ ) Taubin ) ) 5 ) 7 AI 9) 7 8. 8. 4 5 5 5 (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) % % http://www.vision.jhu.edu/data/hopkins55 http://www.iim.ics.tut.ac.jp/~sugaya/public-e.html 6 c 9 Information Processing Society of Japan
情報処理学会研究報告 フレーム数 4 軌跡数 フレーム数 9 軌跡数 5 フレーム数 軌跡数 5 フレーム数 軌跡数 59 フレーム数 軌跡数 469 フレーム数 軌跡数 7 表 図 の画像例に対する提案手法の各段階の正解率 (%) と菅谷ら Vidal ら RANSA Yan らの 結果 (a) (b) (c) (d) (e) 初期分類 第 段階 第 段階 第 段階 菅谷ら Vidal ら RANSA Yan ら (a) (b) (c) (d) (e) 88.8 99. 98. 99.7 99.6. 98.8 99.6.... 99.7 99.6. 88. 99.6 99. 9.8 99.6 96.6 98.5 98. 97.4..... 99.4 97.5 94........ 99.8 (f) 98.6...... 8.8 (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. 998. ) 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. 998. 4) 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. 769 775, June-July 4, Washington, D, U.S.A. 5) 市村直幸, 形状空間への直交射影行列と判別基準を用いた複数運動の分割, 情報処理学 会研究報告, -VIM--, 7 4, Jan.. 6) 市村直幸, 富田文明, 形状行列からの特徴選択に基づく動きの分割, 電子情報通信学会 論文誌 D-II, J8-D-II-, 757 766, Dec. 998. ま と め 本論文ではビデオ画像上の複数の運動を分離する新しい方法を提案した これは著者らの 以前の方法 菅谷ら9) を改良したものである 最大の改良点は 菅谷ら9) では初期分類 を osteira ら) の作用行列と幾何学的 AI9) による探索によって求たのに対して 本論文 では Vidal ら4),5) の GPA の考え方に基づいた Taubin 法による 次元空間の 平面 の当てはめを用いたことである これにより解が探索なしに直接に求まるだけでなく そ れ自身でよい精度の分離が得られ これを段階的な EM アルゴリズムによって最適化した さらに菅谷ら9) では 8 次元空間において分離を行っていたが 本論文では段階ごとに 次 元 5 次元 7 次元と次元を上げた また菅谷ら9) では誤差のないシミュレーションデータ で計算が破綻することがあったが 本論文ではそれを判定して破綻を防いでいる そして 7 c 9 Information Processing Society of Japan
7),,, PRMU-45, 9 6, July. 8),,,, D-II, J74-D-II-8, 497 55, Aug. 99. 9) 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-), 67 88. ) 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. 59 77. 8),,,, -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; http://vision.stanford.edu/~birch/klt/. ) 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-), 945 959. 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), 85 5. 6) 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