x-means 1 2 2 x-means, x-means k-means Bayesian Information Criterion BIC Watershed x-means Moving Object Extraction Using the Number of Clusters Determined by X-means Clustering Naoki Kubo, 1 Kousuke Imamura 2 and Hideo Hashimoto 2 The present paper proposed a moving object extraction based on x-means clustering which is capable of providing the number of cluster automatically The proposed technique is an extended k-means clustering and can determine the optimal number of clusters by using a stopping rule based on Bayesian Information Criterion(BIC). In the proposed method, the feature points are selected in each segmented region obtained by morphological watershed algorithm, and x-means clustering classifies these feature points based on their affine motion parameters. Suitable number of moving objects are estimated based on clustering result of the feature points. 1 Graduate school of Natural Science and Technology, Kanazawa University 2 1. MPEG-4 1) 5) 3) 4) 5) Morphological Watershed x-means x-means 2. x-means x-means 6) k-means 7) 1 Bayesian Information Criterion(BIC) 8) n p 9) 1. k 0 ( 2) 2. k = k 0 k-means C 1, C 2,..., C k0 3. i = 1, 2,, k 0 4 9 Institute of Science and Engineering, Kanazawa University 1 c 2010 Information
4. C i k = 2 k-means C 1 i, C 2 i 5. C i x i p [ f(θ i ; x) = (2π) p 2 Vi 1 2 exp (x µ ] i) t V 1 i (x µ i ) 2 BIC BIC = 2 log L( ˆθ i ; x i C i ) + q log n i (2) ˆθ i = [ ˆµ i, ˆV i ] p µ i p V i p p q q = 2p x i C i p n i C i L L( ) = f( ) 6. C 1 i, C 2 i θ 1 i, θ 2 i p 2 g(θ 1 i, θ 2 i ; x) = α i [f(θ 1 i ; x)] δ i [f(θ 2 i ; x)] 1 δ i (3) { 1, x i Ci 1 δ i = 0, x i Ci 2 α i α i = 0.5/K(β i ) (5) K( ) β i f(θ 1 i ; x) f(θi 2 ; x) µ1 µ 2 β i = 2 V 1 + V 2 2 BIC BIC = 2 log L ( ˆθ i ; xi Ci) + q log n i (7) ˆθ i = [ ˆθ 1 i, ˆθ 2 i ] p (1) (4) (6) p 2 q = 2 2p = 4p 7. BIC > BIC 2 2 C i Ci 1 Ci 2 p BIC 4 8. BIC BIC 2 C i 1 2 7 C i Ci 2 4 9. C i 2 4 8 2 C i 10. k 0 2 11. 3. x-means x-means 3.1 Morphological Watershed Watershed Watershed 10) Watershed Morphological Filter 11)12) Watershed 3.2 l 2 c 2010 Information
S r l min = log 2 100 S r ( ) 1 P max P max 100 P DBD(P ) = {I t (P i ) I t 1 (P i + d)} 2 (9) P i B(P ) I t (P ) P I t 1 (P + d) P d = (d x, d y) B(P ) P 15 15 pixel ±7 pixel Gauss Newton Gauss Newton (v x (x, y), v y (x, y)) v x(x, y) = ax + by + c (10) v y (x, y) = dx + ey + f (11) a, b, d, e c, f 13) Gauss Newton { DBD(P ) > µ e + σ e σ 2 I > T I (12) µ e σ e σ 2 I (8) T I 3.3 x-means x-means p = 6 p 1 3.4 Voting x-means Watershed 4. 14). Penguin and Mouse( 320 240 pixel) 2 1 Morphological Watershed 121 2 3 c 2010 Information
1 (121 ) Fig. 1 Region segmentation result (121 regions). 2 (6,254 ) Fig. 2 Feature points and estimated motions(6,254 points). 1 x-means Table 1 Clustering result by x-means. () Voting 1 3482 10 (7) 2 (12) 11 73 3 (36) 12 417 4 (16) 13 (41) 5 63 14 (23) 6 (50) 15 (45) 7 (43) 16 (12) 8 (22) 17 (45) 9 161 18 1082 3 Fig. 3 Accurate moving object traction result. 6,254 624 1 x-means 18 3 4 5 2 / 97.5% 95.9% 3 Uncovered Background Foreman( 352 288 pixel) Foreman 6 Morphological Watershed 100 7 5,333 461 3 x-means 4 Fig. 4 Moving object extraction result by the region merging method. Table 2 5 Fig. 5 Moving object extraction result by the proposed method. 2 Evaluation of moving objects extraction. =121 =76800 [%] 4 72455/4345 116/5 95.9 5 76274/526 118/3 97.5 4 c 2010 Information
6 100 Fig. 6 Region segmentation result (100 regions). 7 5,333 Fig. 7 Feature points and estimated motions(5,333 points). 3 x-means Table 3 Clustering result by x-means. () Voting 1 1857 5 (21) 2 109 6 140 3 91 7 (34) 4 (33) 8 2644 8 Fig. 8 Accurate moving object extraction result. 8 8 9 10 4 97.0% 90.0% 3 3,. Penguin and Mouse 3 5 Foreman 2 4 5. x-means x-means Watershed 9 Fig. 9 Moving object extraction result by the region merging method. Table 4 10 Fig. 10 Moving object extraction result by the proposed method. 4 Evaluation of moving objects extraction. =100 =101376 [%] 3 91055/10321 90/10 90.0 4 100481/895 97/3 97.0 5 c 2010 Information
Uncovered Backgound 12) Wang, D.: A Multiscale Gradient Algorithm for Image Segmentation Using Watersheds, Pattern Recongnition, Vol.30, No.12, pp.2043 2052 (1997). 13) Wang, Y.A. and Adelson, H.: Representing Moving Images with Layers, IEEE Trans. Image Process., Vol.3, No.5, pp.625 638 (1994). 14) Vol.63, No.11, pp.1625 1629 (2009). 1) Schoeneman, T. and Cremers, D.: Near Real-time Motion Segmentation Using Graph Cuts, Springer, LNCS, Vol.4174, pp.455 464 (2006). 2) Yang, W., Loe, K.-F., Tan, T., and Jian-Kang, W.: Spatiotemporal Video Segmentation based on Graphical Models, IEEE Trans. Image Process., Vol.14, No.7, pp.937 947 (2005). 3) Rousson, M. and Paragios, N.: Prior Knowledge, Level Set Representations and Visual Grouping, International Journal of Computer Vision, Vol.76, No.3, pp.231 243 (2008). 4) Chen, L.-H., Lai, Y.-C., Su, C.-W. and Liao, H.-Y.M.: Extraction of Video Object with Complex Motion, Pattern Recognition Letters, Vol.25, No.11, pp.1285 1291 (2004). 5) Mochieni, F., Bhattacharjee, S. and Kunt, M.: Spatiotemporal Segmentation Based on Region Merging, IEEE Trans. Pattern Anal. Machine Intell., Vol.20, No.9, pp. 897 915 (1998). 6) Pelleg, D. and Moore, A.: X-means: Extended K-means with Efficient Estimation of the number of Clusters, Proc. of the 17th International Conference on Machine Learning, pp.727 734 (2000). 7) Hartigan, J.A. and Wong, M.A.: A K-means Clustering Algorithm, Applied Statistics, Vol.28, pp.100 108 (1979). 8) Jolion, j.m., Meer, P. and Bataouche, S.: Robust Clustering with applications in computer vision, IEEE Trans. Pattern Anal. Machine Intell., Vol. 13, No. 8, pp. 791 802 (1991). 9) x-means k-means Vol.18, No.1, pp.3 13 (2006). 10) Vincent, L. and Soille, P.: Watersheds in Digital Spaces:An Efficient Algorithm Based on Immersion Simulations, IEEE Trans. Pattern Anal. Machine Intell., Vol.13, No.6, pp.583 598 (1991). 11) Vincent, D.: Morphological Grayscale Reconstruction in Image Analysis: Applications and Efficient Alogorithms, IEEE Trans. Image Process., Vol.2, No.2, pp. 177 201 (1993). 6 c 2010 Information