基于局部特征和Mean Shift的目标跟踪算法研究

席志红，李永佳，段 炼

(1.哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨 150000;2.哈尔滨体育学院财务处，黑龙江哈尔滨 150000)

目标跟踪［1］是计算机处理视频邻域的典型问题，主要是寻找指定目标在下一帧的位置，应用的主要技术是图像处理、模式识别等方法。现在研究的跟踪算法主要可分为两个方向，分别是根据特征进行跟踪和根据假设进行跟踪。根据特征进行跟踪的方法，是通过在不同图像中检测出目标的特定特征实现对目标的跟踪，这样特征的优劣直接影物体效果。基于特征的跟踪方法计算复杂程度低，能保持较好的实时性。Mean Shift算法［2］是基于特征跟踪的典型代表。根据假设进行跟踪的方法［3］，首先分析跟踪物体与背景环境的不同点，找到有用信息作为假设条件，然后根据这些假设对跟踪建立模型，从而实现对目标的跟踪。这种算法具有较高的准确性，但采样数量大，实时性比根据特征进行跟踪方法差。粒子滤波、卡尔曼滤波的跟踪等都是根据假设进行跟踪的经典算法。

图像的局部特征［4］也是目前计算机图像处理的一个热点，是许多方法的基础，对实现目标跟踪有直接的影响，在寻找每个图像间的对应点和目标特征描述有着重要的作用。在视觉领域刊物和会议上都有特征描述论文发表。同时也被广泛的应用。在实际的三维图像重建和场景恢复中，当建立每幅图像之间点与点之间的对应关系时，优秀的局部图像特征描述算子必不可少。在实现物体跟踪算法中，目前比较流行的算法就是根据局部特征进行跟踪，这是因为局部特征通常是利用物体局部形状，这样物体可以存在遮挡、复杂背景等情况下被识别。表示目标的局部特征有很多种，目标的轮廓特征最容易被感知，稳定性相对其他特征是最好的，能够直接描述物体的形状。形状上下文(Shape Context)一种基于边界轮廓的表示方法，能够很好的描述物体的形状特征。

1 Shape Context算法

Shape Context［5］特征是由 Serge Belongie 于 2002年提出的一个形状描述方法。依据以往的学术研究，Shape Context的形状描述比基于边界的形状在理论上能够实现更精确的匹配，该方法能够很好地表示图像区域的内部特征。并经过大量测试，在仅有轮廓的匹配信息时，Shape Context仍然可以保证到很高的精确度。

首先，要获得物体轮廓特征，利用轮廓上的一系列离散的点就可以表示整个目标轮廓，提取Shape Context特征。在提取离散点时，应做到的是使这些提取点能准确反映出物体的轮廓信息，尤其是物体中形态发生变化部位的重要信息，并尽量做到提取点集的质心与目标质心能够保持相同位置。在提取目标边缘时，采用微分算子法，这种算法通过卷积完成，这是因为导数算子有使灰度变化突出的作用。将导数算子应用的图像中，就可以使图像灰度变化较大的点处得到的数值较高，因此把这些导数值作为对应点的边界强度值，通过设置阈值的方法，提取边界点集合。实验证明，这种方法准确性较高。其次，就是要提取轮廓采样点。利用均匀采样的方法，将提取到的轮廓线上曲率最大的点确定为采样的开始点。如果轮廓有不止一个曲率最大的像素点，则比较曲率最大的点的毗邻点的曲率，比较毗邻点曲率较大的点所对应的曲率最大点作为起始点，如果毗邻点的曲率也相同，则在比较毗邻点，直到找出较大的相邻像素点为止。找到起始点后，依次均匀抽样。

Shape Context方法的理论基础是:对任一图像通过上文叙述方法得到的N个离散边界点来说，其中任意一个点与其他的N－l个点之间都存在对应关系，可以将这种对应关系看成不同向量，这N－l个向量包含了有用的的边界信息，由这N－1个向量就能表示物体的形状特征，这可以看出，当N值越大时，表示目标信息越多，表示目标的形状也就越准确。在提取到轮廓点后［6］，利用坐标变换得到该点对应的直方图，对数极坐标直方图能够直观反映基准点与其他点之间的空间位置关系，从而正确表示物体的特征。

对任一图像，在提取目标边缘点后，可以得到一组离散边界点集，设点集为 Pi={p1，p2，…，pn}，对任一个点pi，其余点与该点能构成的向量组，这就能很好的反映该点在目标中的位置信息。

为更直观反映Shape Context特征方法，引入一种常用的圆形的对数极坐标系，如图1所示，图1(a)为原图，图1(b)为特征提取结果图。

图1 Shape Context特征提取示意图

如图1所示，整个空间被分成12×5=60个区域，每个区域所占的大小按从外到里逐渐增强，这是因为对于某点，离其近的点比距离远的点有更好的鉴别能力。而在同一个圆弧范围内的区域所占空间相同，这是因为相同距离的点对基准点的鉴别能力是相同。在本文算法中，对给定点pi，在以该点为原点所组成的极坐标系中，通过统计分布在每个区域中点个数来表示目标的边界特征信息。根据利用不同的点，可依次计算得到每个点的直方图，这样物体的边界特征就可以用n×60的矩阵表示。

通过上述介绍可知，对于给定点pi，其特征可以用以该点为中心的极坐标系的60个区域中落入每个区域中的像素点个数Qi(k)来表示，公式显示如下

式(1)中，k=0，…，60，#操作符代表了落入第 k 个区域中的不同于点的所有其余点的个数，通过这种方法能得到有60个分量的直方图值，逐一计算所有的离散点，得到n个形状直方图。这样所有物体的形状信息我们都可以量化为一个n×60的矩阵。根据这些点的直方图中分布在不同区域的点数，就可以建立图像的Shape Context直方图。

对于原图像上的点pi和需要匹配的图像上的点qj，可以用 Cij=C(pi，qj)表示点 pi和 qj的 Shape Context直方图的相似度，计算公式如式(2)所示。

其中，hi(k)和hj(k)表示在这两个不同点的第k个标准化的直方图。

2 本文跟踪算法

2.1 Mean Shift算法

经典的Mean Shift［7］目标跟踪算法采用的颜色直方图作为搜索特征，通过不断迭代使得算法趋向于目标的真实位置，从而实现目标的跟踪。传统的Mean Shift算法在跟踪中优势明显。这些优势［8］主要体现在计算量不大，基本上可以做到实时跟踪。

假设给定d维空间Rd中的n个样本点xi，i=1，2，…，n。在x点的Mean Shift向量的基本形式定义为

其中，Sh是一个高维球区域，半径为h，满足以下关系的y点的集合

K是落入Sh区域内的所有样本点的个数。

Mean Shift向量［9］表示被采样点的平均偏移量，不断向样本分布最多的区域迭代，这也就是概率密度函数的梯度方向。一般来说，在Sh中，离x越近的样本点，对x周围的统计特征关联行越大，所以将核函数的引入，并根据每个样本点的位置不同赋予其不同的权值，经扩展后的Mean Shift向量表示为

Mean Shift算法是一个不断迭代直至达到最佳位置的过程，如果假设初始点为x，允许的误差为ε，则Mean Shift算法按照以下步骤进行:第1步，计算mh(x);第 2步，把 mh(x)付给 x;第 3步，如果mh(x)－x ＜ε结束循环，否则，继续执行第1步。

2.2 本文跟踪算法

Mean Shift算法方法简单、计算速度快，在现实得到广泛应用。但与此同时，Mean Shift算法也存在着一些缺点，这是由于直方图特征［10］在目标颜色特征描述方面略显单一，缺少空间信息，对目标变形和遮挡不能实现正确的跟踪。尽管颜色特征是简单可行的，但颜色特征不能很好地解决跟踪中出现的遮挡问题，并且在复杂背景下跟踪的效果也不理想。所以，在目标跟踪领域，但考虑到其缺点，在本文算法中用 Shape Context特征替代颜色特征，来解决颜色特征缺陷的问题。

在跟踪的起始帧中，通过人工选定方法来选取要跟踪的目标，然后对所选取的目标提取轮廓点，对提取的轮廓点进行抽样，将所得抽样点按在极坐标分布区域不同分成m块，分布在不同区块的点进行Epanechnikov核函数加权，构成图像的Shape Context直方图，该直方图模型就叫做目标模型，在后续帧的目标跟踪图像帧上可能包含目标的区域是候选区域。

为了直观反映跟踪算法，假设现有两个归一化的直方图分别为ha={ha(1)，ha(2)，…，ha(n)}和hb={hb(1)，hb(2)，…，hb(n)}，则它们之间的 Bhattacharyya距离ρ(ha，hb)计算公式如下

为使目标模型与候选模型的相似性最大，即使得Bhattacharyya系数ρ^(y)的值最大。由于前面部分的研究q^u已经得出，对式子p^u(y0)进行泰勒展开，Bhattacharyya系数ρ(y)可以表示成

3 实验结果及分析

实验中所用的硬件环境为CPU P(R)4 2.8 GHz，内存4 GB，显存512 MB。软件开发环境为 Matlab 2010b，实验数据为多组视频序列。为验证本文算法的稳定性与鲁棒性，本文从验证平移、旋转不变性、遮挡稳定性和复杂场景稳定性等3个方面进行论证，经过实验研究，都表明该算法的稳定性，受篇幅限制，以下每方面只列举出一种场景。

3.1 验证平移、旋转不变性

由于平移只是目标位置的平移，其特征并未改变，所以平移之前与之后的形状上下文特征相同，Shape Context具有平移不变形。通过对轮廓上的点建立极坐标图，统计周围点落入极坐标图的数量来建立Shape Context直方图，所以旋转之后，点的位置信息不变，所建立的直方图也不变。不同形状的目标Shape Context特征也不相同，对于颜色相似而形状不同的目标能实现良好的跟踪。为验证本文提出跟踪算法对旋转和平移具有良好的鲁棒性，提取了序列图像中两幅有颜色相似、形状不同的两个物体相互运动、物体角度变化的图片，图2中方框表示被跟踪的物体，从图中可以看到，该算法能实现良好的跟踪。

图2 验证平移、旋转不变性效果图

3.2 验证遮挡稳定性

虽然颜色特征是简单可行的，但颜色特征不能很好地解决跟踪中出现的遮挡问题，并且在复杂背景下跟踪的效果也不理想，而Shape Context特征可以弥补这些不足。图3是一组手遮挡脸的视频序列，可以看到，当跟踪人脸时，图3(b)、图3(c)图有手遮挡时，仍能实现良好的跟踪。虽然跟踪出现较小的偏差，但是跟踪没有丢失。实验表明，本算法具有较强的抗噪性。

图3 验证遮挡稳定性效果图

3.3 验证复杂场景稳定性

由于均值漂移算法根据加权的颜色直方图对目标建立模型，算法容易受颜色相似但颜色空间分布不同的目标干扰。同时由于仅仅根据颜色信息对目标进行跟踪，容易受背景颜色的干扰。图4为跟踪物体出现遮挡，且被遮挡物体与跟踪物体颜色相似，基于空间色彩直方图的方法不能实现很好的跟踪。而从图3中可以看出，基于Shape Context特征的Mean Shift目标跟踪算法跟踪效果很好，对遮挡具有良好的鲁棒性。

图4 验证复杂场景稳定性效果图

4 结束语

传统的全局特征在跟踪中容易受到背景信息的干扰，并且不能很好的处理遮挡问题。本文详细介绍了Shape Context特征，并且具体讨论了在该的鲁棒性和稳定性。随后，通过Shape Context特征对目标进行建模，在Mean Shift算法的框架下进行跟踪，并在户内外多个视频中对提出的算法进行了验证，都能实现良好的跟踪，充分说明本文算法具有良好的鲁棒性，比基于颜色特征的跟踪算法更能适应复杂场景，为下一步研究提供了新的思路。

［1］ Milan Sonka，Vaclav Hlavac，Roger Boyle．图像处理、分析与机器视觉［M］．3版．艾海舟，苏延超，译．北京:清华大学出版社，2011．

［2］ 李弼程，邵美珍，黄洁．模式识别原理与应用［M］．西安:西安电子科技大学出版社，2008．

［3］ 王辉．复杂场景下多摄像机运动目标连续跟踪研究［D］．北京:北京交通大学，2013．

［4］ Belongie S，Malik J，Puzicha J．Shape matching and object recognition using shape contexts［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(4):509－522．

［5］ 刘翔．基于视频的运动目标检测与跟踪算法研究与应用［D］．武汉:武汉科技大学，2009．

［6］ 曲明志．基于局部特征和粒子滤波的目标跟踪算法研究［D］．长春:吉林大学，2013．

［7］ 朱胜利，朱善安，李旭超．快速运动目标的Mean Shift跟踪算法［J］．光电工程，2006，33(5):66 －70．

［8］ 胡波，陈恳，徐建瑜，等．基于Kalman预测和Mean－Shift算法的视频目标跟踪［J］．光电子·激光，2009，20(11):1517－1522．

［9］ 朱英宏，李俊山，郭莉莎，等．基于 LBP的尺度不变特征的描述和匹配算法［J］．计算机辅助设计与图形学学报，2011，23(10):1758 －1763．

［10］高越，赵丹培，姜志国．复杂环境下的鲁棒目标跟踪方法［J］．计算机辅助设计与图形学学报，2010(5):817－822．