IEEE CVPR 2000 - Dorin Comaniciu

1 IEEE CVPR 2000. Real-Time Tracking of Non-Rigid Objects using Mean Shift Dorin Comaniciu Visvanathan Ramesh Peter Meer Imaging & Visualization Department Electrical & Computer Engineering Department Siemens Corporate Research Rutgers University 755 College Road East, Princeton, NJ 08540 94 Brett Road, Piscataway, NJ 08855. Abstract 2 Mean Shift Analysis A new method for real-time tracking of non-rigid ob- We de ne next the sample mean shift, introduce the jects seen from a moving camera is proposed. The cen- iterative mean shift procedure, and present a new the- tral computational module is based on the mean shift orem showing the convergence for kernels with convex iterations and nds the most probable target position in and monotonic pro les. For applications of the mean the current frame. The dissimilarity between the target shift property in low level vision ( ltering, segmenta- model (its color distribution) and the target candidates tion) see [6].

2 Is expressed by a metric derived from the Bhattacharyya coe cient. The theoretical analysis of the approach Sample Mean Shift shows that it relates to the Bayesian framework while Given a set fxi gi=1:::n of n points in the d- providing a practical, fast and e cient solution. The dimensional space Rd, the multivariate kernel density capability of the tracker to handle in real-time partial estimate with kernel K (x) and window radius (band- occlusions, signi cant clutter, and target scale varia- width) h, computed in the point x is given by tions, is demonstrated for several image sequences. n . f^(x) = 1 d K x ; xi : X. 1 Introduction nh i=1 h (1). The e cient tracking of visual features in complex The minimization of the average global error between environments is a challenging task for the vision com- the estimate and the true density yields the multivariate munity. Real-time applications such as surveillance and Epanechnikov kernel [25, ]. monitoring [10], perceptual user interfaces [4], smart 1 ;1.

3 KE (x) = 02 cd (d + 2)(1 ; kxk ) ifotherwisekxk < 1. rooms [16, 28], and video compression [12] all require 2. the ability to track moving objects. The computational complexity of the tracker is critical for most applica- (2). tions, only a small percentage of a system resources be- where cd is the volume of the unit d-dimensional sphere. ing allocated for tracking, while the rest is assigned to Another commonly used kernel is the multivariate nor- preprocessing stages or to high-level tasks such as recog- mal . 1.. ; 2. KN (x) = (2 ) exp ; 2 kxk : d= 2 (3). nition, trajectory interpretation, and reasoning [24]. This paper presents a new approach to the real-time tracking of non-rigid objects based on visual features Let us introduce the pro le of a kernel K as a func- such as color and/or texture, whose statistical distribu- tion k : [0; 1) ! R such that K (x) = k(kxk2 ). For tions characterize the object of interest. The proposed example, according to (2) the Epanechnikov pro le is 1 ;1.]

4 Tracking is appropriate for a large variety of objects with di erent color/texture patterns, being robust to partial kE (x) = 02 cd (d + 2)(1 ; x) ifotherwise x<1 (4). occlusions, clutter, rotation in depth, and changes in camera position. It is a natural application to motion and from (3) the normal pro le is given by analysis of the mean shift procedure introduced earlier [6, 7]. The mean shift iterations are employed to nd kN (x) = (2 );d=2 exp ; 21 x : (5). the target candidate that is the most similar to a given Employing the pro le notation we can write the density target model, with the similarity being expressed by a estimate (1) as metric based on the Bhattacharyya coe cient. Vari- n ! x ; xi 2. ous test sequences showed the superior tracking perfor- ^ 1 X. fK (x) = nhd k h : (6). mance, obtained with low computational complexity. i=1. The paper is organized as follows. Section 2 presents We denote and extends the mean shift property. Section 3 intro- g(x) = ;k0 (x) ; (7).

5 Duces the metric derived from the Bhattacharyya coef- assuming that the derivative of k exists for all x 2. cient. The tracking algorithm is developed and ana- [0; 1), except for a nite set of points. A kernel G. lyzed in Section 4. Experiments and comparisons are can be de ned as given in Section 5, and the discussions are in Section 6. G(x) = Cg(kxk2 ); (8). 1. where C is a normalization constant. Then, by taking estimates computed with kernel K in the points (14). the estimate of the density gradient as the gradient of are n o n o the density estimate we have f^K = f^K (j ) j=1;2::: f^K (yj ) j=1;2::: : (15). n 2 ! r^ f (x) rf^ (x)= 2 X (x ; x ) k0 x ; x i These densities are only implicitly de ned to obtain K K nhd+2 i=1 i h r^ fK . However we need them to prove the convergence n 2 ! of the sequences (14) and (15). = nh2d+2 (xi ; x) g X x;x i = 2 . h nh d+2 Theorem 1 If the kernel K has a convex and mono- i=1. " !#2 Pn xx ; . i 2. 3 tonic decreasing pro le and the kernel G is de ned ac- n x ; xi 2 i=1 x g X i h cording to (7) and (8), the sequences (14) and (15) are g h 4.]

6 Pn x hx ; . i 2. ; x5 ; (9) convergent. i=1 i=1 g . The Theorem 1 generalizes the convergence shown where ni=1 g x;hxi 2 can be assumed to be in [6], where K was the Epanechnikov kernel, and G. P. nonzero. Note that the derivative of the Epanechnikov the uniform kernel. Its proof is given in the Appendix. pro le is the uniform pro le, while the derivative of the Note that Theorem 1 is also valid when we associate to normal pro le remains a normal. each data point xi a positive weight wi . The last bracket in (9) contains the sample mean 3 Bhattacharyya Coe cient Based shift vector Pn x;x 2. Metric for Target Localization i=1 xi g h The task of nding the target location in the current i Mh;G(x) Pn x;x 2 ;x (10) frame is formulated as follows. The feature z repre- g i=1 h i senting the color and/or texture of the target model is and the density estimate at x assumed to have a density function qz , while the target n ! candidate centered at location y has the feature dis- C X.

7 F^G(x) nh g x ; xi 2 (11) tributed according to pz (y). The problem is then to d i=1. h nd the discrete location y whose associated density pz (y) is the most similar to the target density qz . computed with kernel G. Using now (10) and (11), (9) To de ne the similarity measure we take into account becomes that the probability of classi cation error in statistical r^ fK (x) = f^G (x) 2h=C2 Mh;G(x) (12) hypothesis testing is directly related to the similarity of the two distributions. The larger the probability of from where it follows that error, the more similar the distributions. Therefore, 2 ^ (contrary to the hypothesis testing), we formulate the Mh;G(x) = 2h=C r^fK (x) : (13) target location estimation problem as the derivation of fG(x) the estimate that maximizes the Bayes error associated Expression (13) shows that the sample mean shift vec- with the model and candidate distributions. For the tor obtained with kernel G is an estimate of the normal- moment, we assume that the target has equal prior ized density gradient obtained with kernel K.

8 This is a probability to be present at any location y in the neigh- more general formulation of the property rst remarked borhood of the previously estimated location. by Fukunaga [15, p. 535]. An entity closely related to the Bayes error is the Bhattacharyya coe cient, whose general form is de- A Su cient Convergence Condition ned by [19] Z. The mean shift procedure is de ned recursively by p computing the mean shift vector Mh;G(x) and trans- (y) [p(y); q] = pz (y)qz dz : (16). G by Mh;G (x). lating the center of kernel Properties of the Bhattacharyya coe cient such as its Let us denote by yj j=1;2::: the sequence of succes- relation to the Fisher measure of information, quality sive locations of the kernel G, where of the sample estimate, and explicit forms for various . Pn yj ;xi 2 distributions are given in [11, 19]. i=1 xi g h Our interest in expression (16) is, however, moti- yj+1 = P y ;xi 2 ; j = 1; 2; : : : (14) vated by its near optimality given by the relationship n g j to the Bayes error.

9 Indeed, let us denote by and i=1 h two sets of parameters for the distributions p and q and is the weighted mean at yj computed with kernel G by = ( p ; q ) a set of prior probabilities. If the value and y1 is the center of the initial kernel. The density of (16) is smaller for the set than for the set , it 2. can be proved [19] that, there exists a set of priors 4 Tracking Algorithm for which the error probability for the set is less than We assume in the sequel the support of two modules the error probability for the set . In addition, starting which should provide (a) detection and localization in from (16) upper and lower error bounds can be derived the initial frame of the objects to track (targets) [21, 23], for the probability of error. and (b) periodic analysis of each object to account for The derivation of the Bhattacharyya coe cient from possible updates of the target models due to signi cant sample data involves the estimation of the densities p changes in color [22].

10 And q, for which we employ the histogram formulation. Although not the best nonparametric density estimate Color Representation [25], the histogram satis es the low computational cost imposed by real-time processing. We estimate the dis- Target Model Let fx?i gi=1:::n be the pixel loca- crete density q^ = fq^u gu=1:::m (with m P. u=1 q ^ u = 1) tions of the target model, centered at 0. We de ne a from the m-bin histogram ofPthe target model, while function b : R2 ! f1 : : : mg which associates to the p^ (y) = fp^u(y)gu=1:::m (with mu=1 p^u = 1) is estimated pixel at location x?i the index b(x?i ) of the histogram at a given location y from the m-bin histogram of the bin corresponding to the color of that pixel. The prob- target candidate. Hence, the sample estimate of the ability of the color u in the target model is derived by Bhattacharyya coe cient is given by employing a convex and monotonic decreasing kernel m p X pro le k which assigns a smaller weight to the locations ^(y) [^p(y); q^ ] = p^u (y)^qu : (17) that are farther from the center of the target.