4．1．跟踪算法的基本流程
在本文的智能视频监控系统中，运动目标跟踪的基本流程如图4．1所示。

主要包括以下几个部分：
(1)运动目标检测部分：在视频图像中定位、检测运动目标；
(2)建立目标模板部分：根据检测到的目标，提取其特征建立跟踪模板；
(3)目标运动预测部分：利用预测算法预测目标可能出现的位置；
(4)运动目标跟踪部分：在预测范围内，利用跟踪算法搜索匹配的运动目标；
如果在预测范围内找到与目标模板匹配的目标，则更新该模板；否则建立
一个新的模板。

运动目标检测
图4．1本文的目标跟踪算法结构框图
4．2．Mean Shift算法
Mean Shifl这_个概念最早是有Fukunaga和Hostetle于1975年提出的一种无参嚣；|
一板]l_]一
～
一竺竺～～模一皈I|
一
王一目|! 离一
估计算法，其主要思想是沿着概率梯度上升的方向找到分布的峰值，即寻找极
值【61】；1 995年，Yizong Cheng等人定义了一簇核函数，并且设定了权重系数，这大大扩展了该算法的适用范围并使得其逐渐被不同领域所应用；自1 998年开
始，该算法被Bradski应用于人脸跟踪，其在目标跟踪领域的优势显现出来，并
不断被应用在目标跟踪的各个领域中‘621。

在Mean shift算法中非常重的一个概念就是核函数。

其定义为：若函数K：
当X—R，存在剖面函数k：【0，叫一R，即式4．1：
K(x)=k(㈣x 2) (4．1)
核函数必须是一个非负非增函数，并且是分段连续的，同时满足式4．2：
【k(r)dr<oo (4．2)
常用的核函数有Epanechnikov核函数、单位均匀核函数、高斯核函数等，
其中由于Epanechnikov核函数能够产生最小平均积分平方误差(MISE)，所以
在众多的跟踪方法中是最常使用的。

其函数定义为：
KE(x)={co_卜82) “乏熄1 (4．3)
Mean Shift算法的实质是Mean Shift向量的转移过程。

所谓Mean Shift向
量是通过核函数推导而来的。

首先定义d维空间Ro中的样本集合为{Xi)i=l，．．．n，
K(x)表示该空间的核函数，其窗131半径是h，则点X出的核密度估计是：
m，=嘉喜文寻) ㈤4，
K(x)的剖面函数k(x)，其使得K(x)=k(1lxll2)。

将上式的核密度估计写成剖面
函数形式：
觚垆嘉驯等『] ∽5，
V‰五
班“，”e㈤(=x堕)r三thd+2喜=vf”(x)=—盟Z(。

一x砧t。

蚓(0f t I÷等『0 ] ((44．．6))
V夕九K cx ，=音等
等≥喜cx一一，g(8寻『]=妄等等
≥[善g[|I 等『]]J粼一x f
36
上式中的第一项是在X处的基于核函数G(x)Ij9无参密度估计值。

第二项则
是Mean Shift向量，表示的是以G(x)为权值加权平均值与X的差值。

通常，K(x)被称为是G(x)的阴影函数。

根据推导可知，Epanechnikov核函
数是均匀核的影子，因此，若在目标跟踪中选用Epanechnikov核，其剖面函数
k(x)为：
m)=悟0 II娈1 (4．8)
经过简单的推导，可以得到g(x)为：
贴)_-纵垆亿II裴1 (4．9)
将其带入到Mean Shift向量中，可以化简该向量，得到如下的形式：
m(工)=去Σ＆一x) (4．10)
从上式可以看出，选用Epaneclmikov核函数可以大大的减小计算复杂度，
这也是人们选用该核函数的一个重要原因。

Mean Shift算法是一个迭代的过程，它循环执行下面的步骤，直到满足一
定的条件，才‘结束循环：
(1)计算H的值，H定义如下：
H=
“剜’]
刹斟] (4．11)
(2)如果IIH ．xll<￡，则结束循环；否则继续执行步骤(1)。

上式中的￡是指容许误差，当满足上述条件时，Mean Shift 过程结束，此 时Mean Shift 向量收敛到数据密度的峰值，并且其估计密度梯度为0。

可以看 出，这个迭代过程就是不断的沿着概率密度的梯度方向移动，而其移动的步长 与梯度大小以及该点处的概率密度有关。

经过试验验证，在梯度密度大的地方， 更接近概率密度的峰值，其移动步长较小；反之，在密度小的地方，移动步长 较大。

因此，也可以认为Mean Shift 是一个步长可变的梯度上升算法【63|。