Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian, 13-16 August 2006

1-4244-0060-0/06/$20.00 2006 IEEE

4024
MEAN SHIFT ALGORITHM AND ITS APPLICATION IN TRACKING OF
OBJECTS
ZHI-QIANG WEN, ZI-XING CAI
College of Information Science and Engineering, Central South University, HuNan, Changsha, 410083 China
E-MAIL: [email protected], [email protected]
Abstract:
Mean shift algorithm is recently widely used in tracking
clustering, etc, however convergence of mean shift algorithm
has not been rigorously proved. In this paper mean shift
algorithm with Gaussian profile is studied and applied to
tracking of objects. The imprecise proofs about convergence
of mean shift are firstly pointed out. Then a convergence
theorem and its rigorous convergence proof are provided.
Lastly tracking approach of objects based on mean shift is
modified. The results of experiment show the modified
approach has good performance of object tracking applied to
occlusion. The contributions in this paper are expected to
further study and application in mean shift algorithm.
Keywords:
Mean shift algorithm; Convergence; Kernel function;
Tracking of object; Bhattacharyya coefficient
1. Introduction
Mean shift, which was proposed in 1975 by Fukunaga
and Hostetler[1], is a nonparametric, iterative procedure
that shifts each data to local maximum of density function.
In spite of its good properties, it has been ignored until
Chengs paper[2] renews our interest in it. Cheng in [2]
revisited mean shift, developing a more general formulation
and demonstrating its potential uses in clustering and global
optimization. Since then, mean shift has been widely used
in object tracking[3-7], image segmentation[8,9], pattern
recognition and clustering[10,11], filtering[12], information
fusion[13] and etc.
Cheng[2] discussed the mean shift algorithm in three
ways and chiefly studied the blurring process. Let data be a
finite set S embedded in the d-dimensional Euclidean space
X. Let T X be a finite set produced in iterative procedure.
When T=S, the mean shift procedure is a blurring process,
namely the input data is recursively modified after each
mean shift step. Cheng in [2] provided the proofs for the
convergence of blurring process. However when S is fixed
through the process and T is initialized to S, it is no longer
a blurring process and Chengs theories do not apply.
Comaniciu in [14] proposed the mean shift procedure from
density estimation and proved it converge at nearest
stationary point of the underlying density function.
Comanicius work in [14] nicely is what Cheng has not
dealt with. Li in [15] found the mistake in Comanicius
convergence proof in [14] and gave some counterexamples.
Comaniciu also made the same mistake in [4,16]. Li prove
the convergence of mean shift in a new way. In fact the
proof in [4,14,15,16] is imprecise, and the convergence of
mean shift need to be studied.
Arming at mean shift algorithm with Gaussian profile,
this paper studies above problem. The main contributions
of this paper are: the imprecise proofs about convergence of
mean shift in [4,14,15,16] are pointed out and a rigorous
convergence proof is provided. Moreover the tracking
approach of objects based on mean shift is modified. The
paper is organized as follows: mean shift algorithm is
introduced in section 2. Section 3 provides the proof for the
convergence of mean shift. Modified tracking approach of
objects and its experiment are presented in section 4.
Section 5 is the conclusion.
2. Mean shift
Given n data points x
i
, i1,,n in the d-dimensional
space
d
R ,iterative formula of mean shift is as follows.

=
=
+
|
|
.
|

\
|

|
|
.
|

\
|

=
n
i
i t
n
i
i t
i
t
h
x y
g
h
x y
g x
y
1
2
1
2
1
(1)
We can yield
t t t t
d y y + =
+

1
(2)
Where
0 ) (

2
,
2
> =
t g h t
y f c h
, ) (

, t k h t
y f d = .
Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian, 13-16 August 2006
4025

=
|
|
.
|

\
|

=
n
i
i
d
d k
k h
h
x x
k
nh
c
x f
1
2
,
,
) (

is a multivariate kernel density

estimator with profile k which is Gaussian profile.

=
|
|
.
|

\
|

=
n
i
i
d
d g
g h
h
x x
g
nh
c
x f
1
2
,
,
) (

, where c
g,d
, c
k,d
is the
corresponding normalization constant. We define derivative
x
h
x x
g
h
x x
g x
x m
n
i
i
n
i
i
i
g h

|
|
.
|

\
|

|
|
.
|

\
|

=

=
=
1
2
1
2
,
) (
(3)
From (2) we can yield
) (
, 1 t g h t t
y m y y + =
+
(4)
where
) (

) (

2
1
) (
,
, 2
,
x f
x f
c h x m
g h
k h
g h

=

(2) shows mean shift alternates toward the gradient
direction and leads the original points shift to a local
maximum point of distributing density function. The step
size
t
changes going with the whole iterative process.
3. Convergence of mean shift
Literature [4,14,16] provided the convergence theories.
However differing from [4,14], Literature [16] studied the
variable-bandwidth mean shift. Li in [15] found that the
proofs, which were provided for convergence of mean shift
in literature [4,14,16], are wrong. When literature [14] was
proving the convergence of sequence {y
t
, t=1,2...}, Li in[15]
considered it is wrong to deduce {y
t
, t=1,2...} converge
from ||y
t+1
-y
t
|| converges to zero and gave some
counterexamples. Li in [15] used a weighting parameter
c
k,i,h
in Comanicius method. Li proved the convergence of
mean shift in a new way. The work Li did in [15] is to find
above mistakes and correct it but he did not drastically
correct it. Li[15] and Comaniciu

[4,14,16] use the property
of convex function to prove the sequences
) (

, t k h
y f
, t=1,2...
converge and is monotonically increasing but function k(x)
is rewritten in k(||y
t
-x
i
||
2
) which is not always a convex
function, possibly is a concave function or neither of them.
When k(x) is a convex function, sequences ) (

, t k h
y f are also
not always converge to a local maximum point. The
definitions and properties about convex set, convex
function and concave function may consult literature[17] or
other literatures. Theorem 1. and its proof are provided as
follows for the imprecise proof in [14,15].
Theorem 1. The proof of theorem (for example: If the
kernel K has a convex and monotonically decreasing
profile, the sequences {y
t
}, t=1,2,... and
.. 2 , 1 , )} (

{
. ,
= t t f
K h
converge and
.. 2 , 1 , )} (

{
. ,
= t t f
K h
is
monotonically increasing[14]) in [14,15] is imprecise.
Proof. The details about the proof can be found in
[14,15]. We suppose the proof in [14,15] is accurate, so
sequences ) (

, t k h
y f converge and monotonically increase.
From [14,15] we know
t
y converge at a point assuming
y , and then the expression
0 ) (

,
= y f
k h
is true.
Literature [14] provided the proof for its theory
according to property of convex function:
k(x
2
)k(x
1
)+k(x
1
)(x
2
-x
1
) as follows (the expression in [14]
is used):
(

|
|
.
|

\
|
+
+
=
+

2
1
2
1
2
2
,
, ,
) (

) 1 (

i j i
n
i
i
d
d k
K h K h
x y x
h
x
g
nh
c
j f j f

Here the author considered
|
|
.
|

\
|

2
h
x y
k
i is a convex
function(the proof in [15] is similar to that in [14]).
According to the property of convex function, ) (

, t k h
y f is
convex and Hessian matrix ) (

,
2
t k h
y f is a positive
semidefinite matrix.
According to second-order Taylor series expansion
formula around y , we have:
) ( ) (

) (

) (

, , ,
y y y f y f y f
T
k h k h k h
+ =


) ))( (

) (
2
1
,
2
y y y f y y
k h
T
+

where ) ( y y y y + = , 1 0 < < . After y is replaced by y
t
,
we yield
) )( (

) (
2
1
) (

) (

,
2
, ,
y y y f y y y f y f
t k h
T
t k h t k h
=

From ) (

) (

, , t k h k h
y f y f > we have
0 ) )( (

) (
,
2
< y y y f y y
t k h
T
t
.
Assuming the
k h
f
,

has continuous partial derivatives of

second order, there exits a Neighborhood of y ,
satisfying
) (

,
2
y f
k h

is a negative definite matrix, where

y . When y y
t
, y y and
t
y y . So there at
least exits a

y
,...) 2 , 1 (
, satisfying

y , which
implies
) (

,
2

y f
k h

is a negative definite matrix. This is

paradoxical with the property that
) (

,
2
t k h
y f ,...) 2 , 1 ( t
is a
positive semidefinite matrix. So the proofs in [14,15] are
imprecise.
From the proof of Theorem 1, we suppose if
sequence ) (

, t k h
y f , ,... 2 , 1 = t converge and monotonically
increase, the Hessian matrix ) (

,
2
t k h
y f is a negative definite
Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian, 13-16 August 2006
4026
matrix, so there is Theorem 2. In order to provide proof for
the Theorem 2, a lemma is given as follows
Lemma If k(x) is Gaussian function, the following
expression is true.
0 ) (

) (

1 , ,
>
+ t k h
T
t k h
y f y f t=0, 1, 2 (5)
Proof. From [14], we know that if k(x) is Gaussian
function, the following expression is true
0
|| ) ( || || ) ( ||
) ( ) (
1 , ,
1 , ,
>


+
+
t g h t g h
t g h
T
t g h
y m y m
y m y m
(6)
From the (6), we can yield
0
) (

) (

2
1
) (

) (

2
1
1 ,
1 , 2
,
, 2
>

(
(

+
+
t g h
t k h
T
t g h
t k h
y f
y f
c h
y f
y f
c h

So 0 ) (

) (

1 , ,
>
+ t k h
T
t k h
y f y f
Theorem 2. (Convergence Theorem) Assuming
d
R S is nonempty open convex set,
R S f
k h
:

,
has
continuous partial derivatives of second order in S .
If S y
t
,
) ( k
is Gaussian function and
) (

,
2
t k h
y f
,... 2 , 1 = t ,
the Hessian Matrix of
k h
f
,

in y
t
is negative definite matrix,
sequences
) (

, t k h
y f
converge and monotonically increase,
moreover sequences {y
t
} converge.
Proof. According to the properties of profile, k(x) is
bounded, so
k h
f
,

is also bounded. It will explain the

convergence of ) (

, t k h
y f , if ) (

, t k h
y f monotonically
increases.
As t1, according to first-order Taylor series
expansion formula around y
t
, and after y is replaced
by S d y
t t t
+ , we have:
t
T
t t t k h t t k h t t t k h
d d y f y f d y f ) (

) (

) (

, , ,
+ + = +
where 1 0 < < .
Assuming ) (

) (

) (
, , t k h t t t k h
y f d y f + =
t
T
t t t k h t
d d y f ) (

,
+ =
the following expression is true.
t
T
t t t k h t
d d y f ) (

) ( lim
, 0

+ =

0 || ) (

||
2
,
> =
t k h t
y f
t t
T
t t t k h
d d y f

) (

) ( lim
, 1
+ =

0 ) (

) (

, 1 ,
> =
+ t k h
T
t k h t
y f y f (Lemma)
Function ) ( is continuous and differentiable, implying
t
T
t t t k h
T
t t
d d y f d ) (

) ( '
,
2 2
+ =
0 ) ( ) (

) (
1 ,
2
1
< + =
+ + t t
T
t t t k h
T
t t
y y d y f y y
(Easily yielding S d y
t t t
+ ).
So ) ( monotonically decrease and 0 ) ( >
) 1 , 0 ( and expression
) (

) (

, 1 , t k h t k h
y f y f >
+
can be
concluded. Consequently, sequence ) (

, t k h
y f converges and
monotonically increases.
Assuming sequence ) (

, t k h
y f converges to the
point ) (

,
y f
k h
,
S y
, we can drive the equality
0 ) ( lim
) (

) (

, ,
=

y f y f
k h t k h
.
In addition,for ) ( ) 1 ( 0 < < , we have two equalities
(7a) and (7b)
0 ) (

) (

lim
, 1 ,
) (

) (

, ,
=
+

t k h
T
t k h
y f y f
y f y f
k h t k h
(7a)
0 ) (

) (

lim
1 , ,
) (

) (

, ,
=
+

t k h
T
t k h
y f y f
y f y f
k h t k h
(7b)
The left term of (7a) and (7b) are multiplied by each
other, yielding
0 || ) (

|| || ) (

|| lim
2
,
2
1 ,
) (

) (

, ,
=
+

t k h t k h
y f y f
y f y f
k h t k h

which implies 0 ) (

lim
,
) (

) (

, ,
=

t k h
y f y f
y f
k h t k h
,that is
0 ) ( lim
1
) (
,

) (
,

=
+

t t
y
k h
f
t
y
k h
f
y y
, so y
t
is convergent.
For the continuity of function
k h
f
,

, y
t
is easily known
to converge to point y and 0 ) (

,
= y f
k h

The adaptive step sizes is adopted in mean shift to
guarantee convergence which also eliminates the need for
additional procedures to choose the adequate step sizes (for
example finding the optimum step sizes in steepest descend
method[17,18]). This is a major advantage over the
traditional gradient-based methods. The bandwidth h only
decides the number of observed peak values[10] and the
size of region where
) (

, t k h
y f
is concave. Generally the
number of peaks decreases with the increase of the
bandwidth h. So for Hessian matrix H is
(

y
x
h
h
0
0
, mean
shift can converge to a steady point.
4. Experiment on tracking based on mean shift
The tracking algorithm based mean shift in [19] is
adopted in this paper, and more details about this algorithm
can be found in [19]. But in this paper there are some
differences from [19], as follows.
1) Hessian matrix H is
(

y
x
h
h
0
0
, where h
x
, h
y
is the
width and height of object respectively.
Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian, 13-16 August 2006
4027
2) The profile k is Gaussian function.

>

|| || 0
|| ||
) (
x
x e
x k
x

3) Optimum h
x
, h
y
is searched, satisfying that
) (

, t k h
y f

is maximum.
The video in our experiments is acquired in outdoor


(a) distribution of Bhattacharyya coefficient (b) iterative times
Figure 1. Analysis in process of experiment


(a) 20th frame (b) 30th frame ( c) 70th frame, (d) 120th frame
Figure 2. The result of experiment when=2





environment through vision system installed in robot of our
Lab[20]. A object and its initial location are hypothetically
known. Through the mean shift algorithm, the location of
object is found after some times. Figure1(a) shows the
distribution of Bhattacharyya coefficientaround the initial
location of object. After some iterative times, the next
location is found. Figure1 (b) shows the iterative times in
process of finding the object from the first frame to 120th
frame. Figure2 shows the result of experiment. After 120th
frames, the object can be found; even there are some
occlusions. Figure 3 shows the alterative Bhattacharyya
coefficient in each frame, so the curve in Figure3 has two
minimum points, A and B that show there are two

(a) 20th frame (b) 30th frame
Figure 3. Alterative Bhattacharyya coefficient Figure 4. The result of experiment when=1
Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian, 13-16 August 2006
4028
occlusions in process of object moving. For occlusions, the
Bhattacharyya coefficient value is quickly decreasing. After
that, it is quickly increasing. The time of occlusion can not
be too long; otherwise the object will be lost. is important
for the performance of object tracking applied to occlusion.
If is too small, the object is easily lost. If is too large,
the computed time is too long and real time performance is
bad. When =1, the results of experiment in Figure4 show
the object is lost. Generally =1.5-2.5. when =2 in
Figure2, it shows the good results.
5. Conclusions
This paper primarily studies the convergence on mean
shift algorithm with Gaussian profile and presents a
modified tracking approach of object based on mean shift.
At first, this paper review the mean shift algorithm, then the
imprecise proof in [14,15] is pointed out. Third, a new
convergence theorem and its proof are provided; lastly a
modified tracking approach of object is presented. This
approach can be applied to occlusion issue. However the
parameter has an important effect on performance of
tracking of object in occlusion environment. Generally
=1.5-2.5 can ensure the good results.
Acknowledgements
This work was supported by the National Natural
Science Foundation of China under Grant No. 60234030.
The authors thank the whole member in institute of
intelligent robot of Central South University. Besides, we
thank the anonymous reviewers for their good advice.
References
[1] Fukunaga K, and Hostetler LD, The estimation of the
gradient of a density function, with applications in pattern
recognition, IEEE Trans. Information Theory, vol. 21,
pp.32-40, 1975.
[2] Cheng Y, Mean shift, mode seeking, and clustering, IEEE
Trans. on Pattern Analysis and Machine Intelligence, vol.17,
no.8, pp.790-799, 1995.
[3] Comaniciu D, and Ramesh V, Mean shift and optimal
prediction for efficient object tracking, In: Mojsilovic A,
Hu J, eds. Proc. of the IEEE Intl Conf. on Image Processing
(ICIP), pp.70-73, 2000
[4] Comaniciu D, Ramesh V, and Meer P, Real-Time tracking
of non-rigid objects using mean shift, In: Proc. of the IEEE
Conf. on Computer Vision and Pattern Recognition (CVPR),
pp.142-149, 2000.
[5] Collins RT, Mean shift blob tracking through scale space,
In: Proc. of the Conf. on Computer Vision and Pattern
Recognition (CVPR), pp.18-20, 2003.
[6] Shan C, Wei Y, and Tan T et al, Real Time Hand Tracking
by Combining Particle Filtering and Mean Shift, In: Proc.
of the 6th IEEE International Conf. on Automatic Face and
Gesture Recognition, 17-19, May, pp.669-674, 2004.
[7] Maggio E, and Cavallaro A, Hybrid Particle Filter and
Mean Shift tracker with adaptive transition model, In: Proc.
of IEEE Signal Proc. Society Int. Conf. on Acoustics,
Speech, and Signal Processing (ICASSP), Philadelphia, PA,
USA, March pp.19-23, 2005.
[8] Comaniciu D, Image segmentation using clustering with
saddle point detection, In: Proc. of the IEEE Intl Conf. on
Image Processing (ICIP), pp.297-300, 2002.
[9] Wang J, Thiesson B, and Y. Xu et al, Image and Video
Segmentation by Anisotropic Kernel Mean Shift, In: Proc.
European Conf. on Computer Vision (ECCV), 2004.
[10] Comaniciu D, Ramesh V, and A. D. Bue, Multivariate
saddle point detection for statistical clustering, In: Proc. of
the European Conf. Computer Vision (ECCV). Pp.561-576,
2002.
[11] Georgescu B, Shimshoni I, and Meer P, Mean Shift Based
Clustering in High Dimensions: A Texture Classification
Example, In: Proc. ICCV, Oct. pp. 456-463, 2003.
[12] Comaniciu D, and Meer P, Mean shift analysis and
applications, In: Proc. of the IEEE Intl Conf. on Computer
Vision (ICCV), pp.1197-1203, 1999.
[13] Comaniciu D, Nonparametric information fusion for
motion estimation, In: Proc. of the IEEE Conf. on
Computer Vision and Pattern Recognition (CVPR), pp.59-66,
2003.
[14] Comaniciu D, and Meer P, Mean shift: A robust approach
toward feature space analysis, IEEE Trans. on Pattern
Analysis and Machine Intelligence, vol.24, no.5, pp.603-619,
2002.
[15] Li X, and Wu F et al, Convergence of a mean shift
algorithm, Journal of Software, vol.16, no.3, pp.365-374,
2005, in Chinese.
[16] Comaniciu D, Ramesh V, and Meer P, The variable
bandwidth mean shift and data-driven scale selection, In:
Proc. of the IEEE Intl Conf. on Computer Vision (ICCV),
pp.438-445, 2001.
[17] Xie Z, Li J, and Tang Z, non-linear optimization,
Changsha: National University of Defence Technology
Publish House, pp.167-174, 2003, in Chinese.
[18] Shi Y, Globally convergent algorithms for unconstrained
optimization, Computational Optimization and
Applications, vol.16, pp.295-308, 2000.
[19] Comaniciu D, Ramesh V, Meer P, Kernel-Based Object
Tracking, IEEE Trans. on Pattern Analysis and Machine
Intelligence, Vol. 25, no. 5, 2003, pp564-577.
[20] Cai ZX, Zou XB, et al, Design of Distributed Control
System for Mobile Robot, J. Cent. South Univ. (science and
technology), vol.36, no.5, 2005,pp: 727-732, in Chinese