李晖宙

（海军工程大学电子工程学院 武汉 430033）

1 引言

近几年，Mean-Shift算法以其优良的性能在目标跟踪中得到了很好的应用。然而传统的Mean-Shift算法存在以下缺点：当目标移动较快时易丢失目标；缺乏目标模型的更新方法；搜索窗口大小固定等等。许多学者和研究人员针对这些缺点进行了许多改进［1，3］。然而无论是最初的Mean-Shift算法还是改进后的 Mean-Shift算法大都采用Bhattacharyya系数或者Ln距离范数作为候选目标模型和目标模型之间的相似性度量。事实上，许多文献和实践证明它们并非最有效的比较方法［4］，An［5］证明 Bhattacharyya系数会降低Mean-Shift算法的准确度并建议用直方图交集（histogram intersection）取代Bhattacharyya系数作为新的相似度度量。然而他并没有给出优化直方图交集函数找到最相似的候选目标的方法。

另一方面，大多数基于 Mean-Shift的跟踪算法仅利用了颜色信息也造成了算法准确度的降低，例如在光照较弱时或者目标和背景颜色接近时等等。众所周知，人类的视觉系统综合利用了颜色、纹理、形状等信息，当某种信息无法单独完成任务时，其他信息可作为有效的补充。虽然颜色特征在目标跟踪中起着很重要的作用，但是纹理等其他类型的特征能提供与颜色特征完全不同的信息。将这些信息结合在一起可以提高目标跟踪的精度，包括颜色与形状特征的结合［6］，运动信息和颜色信息［7］的结合等等。文献［8］提出了一种采用联合直方图将颜色与纹理特征相结合并融入Mean-Shift算法的目标跟踪算法，但是他并没有考虑不同特征之间，甚至同类特征内部不同部分之间对目标和背景不同的区分能力。

本文提出一种自适应地结合颜色和纹理信息，并采用直方图交集作为相似性度量的目标跟踪算法。算法首先利用基本的局部二元模式（Local binary pattern，LBP）算子提取目标和候选目标的纹理信息。再用对数比加权直方图取代传统直方图构建目标和候选目标的颜色和纹理模型，以便体现出直方图中不同bin之间区分目标和背景能力的差异。然后根据场景对两类不同特征的区分能力进行动态评估，并依据评估结果自适应地融合颜色模型和纹理模型。最后，以直方图交集作为新的相似性度量并采用Powell方法确定最相似的候选目标的位置作为当前帧中目标位置的估计值。

2 Mean-Shift算法概述

Mean-Shift算法在每一帧中寻找与目标接近且与目标颜色直方图最相似的区域作为当前帧中目标位置的估计值。它首先在初始帧中通过人工或其他识别算法确定目标窗口并构建目标模型；然后在后续帧中靠近目标窗口的局部邻域内计算候选目标模型；以Bhattacharyya系数作为度量函数比较两个模型的相似度，并利用Mean-Shift算法寻找局部邻域内的最大值点（即最相似点），作为当前帧中目标位置的估计值，同时将该估计值作为下一帧中目标窗口的初始位置开始新一轮的搜索从而实现对目标的连续跟踪。下面简要介绍文献［9］中的算法。

首先，在第一帧中初始化一个包含目标的目标窗口。x0为该窗口的中心，｛xi｝i＝1，…，n表示该窗口中n个像素的位置，则目标模型可表示如下：

其中，q为目标模型，qu为q中第u个特征的概率，m为特征的总数，δ为delta函数，b（xi）的作用是求点xi的特征值，k（x）为核函数，h为核函数的带宽，C是归一化常数。

类似地，假设第N帧中候选目标位于以y为中心的搜索窗口内，则候选目标模型可表示为

相似度度量函数ρ［p（y），q］用来衡量候选目标模型与目标模型的相似程度。最常用的相似度度量函数为Bhattacharyya系数：

用y0表示前一帧中目标位置的估计值。将Bhattacharyya系数在y0附近Taylor展开可得：

式中g（x）＝－k′（x），依次迭代，当满足一定条件时停止迭代，完成目标定位。通过这种方式，候选目标的窗口中心y会逐渐调整到与目标模型最相似的位置。

3 特征提取与目标表示

颜色信息是目前跟踪算法中最常用的目标特征。传统的Mean-Shift算法就采用RGB颜色直方图作为目标的参考模型。Camshift算法则以HSV颜色空间代替RGB空间。本文仍沿用RGB空间，但所描述的算法对颜色空间并没有特殊要求，可以扩展到其他颜色空间。

许多情况下，仅用颜色信息无法有效地区分背景和目标，例如光照较弱时或者目标和背景颜色接近时等等，这时跟踪算法的准确度较低甚至丢失目标。如果能结合纹理、形状等信息可提高目标跟踪的准确度。常用的纹理算子，如灰度共生矩阵、Gabor滤波器等，由于计算量太大不适宜在实时性要求较高的跟踪算法中使用。近几年，LBP算子以其计算简单，效果好，具有旋转不变性等优点广泛应用于纹理特征提取领域。LBP算子通过将局部邻域内的像素以中心像素为阈值实现二值化，然后将二值化后的像素值乘以相应的像素的权值获得最后的LBP模式。基本LBP算子的计算方法如下：gc表示邻域的中心像素（xc，yc）的灰度值，gp表示距离中心半径为R的圆上P个等间距的像素的灰度值。LBP算子有多种形式，其中一致性模式（Uniform Pattern）应用最广，它只用少量代表性的模式就可以到达几乎全部LBP模式集合的描述能力。然而在实验中，我们发现一致性模式的LBP算子对目标和背景的区分能力并不及原始的LBP算子，因为一致性模式的LBP算子主要考虑信息压缩的效果，或多或少都丧失了一部分描述物体的能力。

纹理特征提取后，用直方图来对目标进行建模。传统的直方图将特征空间划分成若干个小的区间（称为bin），每个bin具有相同的权重，无法反映出不同bin之间不同的区分目标和背景的能力。事实上，那些最能区分目标和背景的bin理所应当被赋予更高的权值。另一方面，许多时候目标和背景混杂在一起无法清晰地分割开来，而 Mean-Shift算法采用矩形窗口对目标和候选目标进行建模，该窗口中不仅包含目标还不可避免地将一部分背景选入其中，导致模型失真。特别是当目标较小时，背景与目标在窗口中所占的比重相当，使得作为目标模型的直方图中包含大量的背景信息，从而产生错误的跟踪结果。文献［9］和［12］建议采用比例直方图，赋予那些主要包含在背景中的bin较低的权值，然而比例直方图将目标和背景合在一起考虑，并没有真正反映不同bin区别目标和背景的能力。如图1所示，虚线框以内为目标，设为100个白色像素，虚线框以外为背景，设为200个白像素和100个黑色像素，根据文献［9］和［12］，白像素的权值为1／3（即0.25／0.75），而黑像素的权值为1（即0.25／0.25）。因此黑像素在目标模型中的比重提高，事实上恰恰相反黑像素并不属于目标。

这里我们采用目标背景的对数比来衡量直方图中各个bin区分目标和背景的能力。显然，识别一个目标只需要目标与其直接邻域有较大差别 即 可。设 q＝｛qu｝u＝1，…，m、O＝｛ou｝u＝1，…，m分 别 为 目 标 区 域 和 背 景区域的归一化直方图，背景区域一般取目标区域的2～3倍，每个直方图都包含有m个bin，δ为一个非常小的数，则第u个bin的目标背景对数比为

图1 比例直方图错误计算权值的实例

4 多特征融合

虽然颜色和纹理信息相结合可以提高算法的准确度，然而许多算法仅仅使用了简单直接的融合策略。实际上，不同场景中颜色和纹理特征所能具备的区分能力并不相同。因此有必要根据场景自适应地调整它们在融合过程中的比重。

对wC、wT进行归一化得w′C，w′T。设PT（X）、PC（X）分别为像素X的纹理概率密度函数和颜色概率密度函数，PI（X）为融合后总的概率密度函数，则PI（X）可用PT（X）、PC（X）的加权和来表示：

类似地，基于融合后的概率密度函数的模型相似性度量也可用下式表示：

其中，φ表示候选目标模型与目标模型之间的相似度度量函数，如Bhattacharyya系数，直方图交集等等，φC，φT分别为从纹理和颜色特征获得的模型相似度，φI为最终的候选目标模型与目标模型之间的相似度。

5 目标定位

然而，直方图交集函数与Bhattacharyya系数和Ln范数有很大差别。前者是不可微函数，而后两者是可微函数，相比而言后者更容易通过求导或求梯度获得函数的最优值，而获得直方图交集的最优值则相对较难一些，这也是许多基于Mean-Shift的算法并没有选用直方图交集作为相似度函数的一个重要原因。Powell方法是一种快速有效且无需求导的局部寻优方法，非常适合无法求导的直方图交集函数。不过Powell方法易受初始点的影响，因此采用两步求取直方图交集的极值：首先利用 Mean-Shift算法求取Bhattacharyya系数的局部最优点作为Powell方法的初始点，再用Powell方法求取直方图交集的最优解作为当前帧中目标位置的估计值。

5.1 确定目标的初略位置

如第4节所述，候选目标模型与目标模型之间最终的相似度可表示为纹理模型相似度和颜色模型相似度的线性组合。将式（3）代入式（11）中的φ，可得：

大多数基于 Mean-Shift的算法都以Bhattacharyya系数或Ln范数作为候选目标模型与目标模型之间的相似性度量函数。然而它们并不是比较两个直方图最有效的方法，许多文献都表明直方图交集能给出更好的比较结果。假设I、M是两个含有n个bin的直方图，则它们之间的相交距离表示为

5.2 最优化直方图交集

Powell算法实质上是一种不计算导数和梯度的共轭方向法。对于n维极值问题，它首先沿着n个坐标方向求极小，经多n次之后得到n个共轭方向，然后沿n个共轭方向求极小，经过多次迭代后便可求得极小值。将式（12）代入式（14）中的φ，可得融合后的直方图交集，并以其作为Powell算法的待优化函数：

HIC（p（y），q）是候选目标颜色模型和目标颜色模型的相交距离，HIT（p（y），q）则是相应的纹理模型的相交距离，融合后的相交距离用 HI（p（y），q）表示。同时以5.1节中所求得的y＊作为Powell方法的初始点以减小初始点对Powell方法的影响。可利用Powell方法的迭代寻优过程获得－HI（p（y），q）的局部极小值，亦即找到最相似的候选目标的位置作为当前帧中目标位置的估计值。

直方图交集最优化方法

1）初始化i＝0，令搜索方向uk为单位向量，uk＝ekk＝1，…，N。

2）设置L0＝xi。

3）对于k＝1，…，N，寻找最小化－HI（p（Lk－1＋αk），q）的αk，并设置Lk＝Lk－1＋αk。

4）令i＝i＋1。

5）对于j＝1，…，N－1，设置uj＝uj＋1，uN＝LN－L0。

6）寻找最小化－HI（p（L0＋αuN），q）的α，并令xi＝L0＋αuN。

7）重复步骤2）至步骤6）直至算法收敛。

6 实验结果

本节以三个跟踪实例展示本文算法的有效性。所得的跟踪结果将和文献［9］中基本的 Mean-Shift算法以及文献［12］中基于比例直方图的Mean-Shift算法所得的结果进行比较，以下分别称为方法1和方法2。实验在AMD Sempren 1.81GHz的CPU，1GB内存配置的电脑上，在 Windows XP系统下用VC6.0编程实现。三个实例中的所有帧都转换为灰度图像。

实例1是一段包含一辆运动汽车的视频。跟踪的目标是汽车的左前轮。如图2所示，由于场景比较简单，三种方法都取得了较好的跟踪结果。然而与其他两种方法相比，本文算法的跟踪准确度更高。

实例2是跟踪一名穿着白色T恤的行人。与实例1相比，由于目标和周围环境有一定的相似度使得跟踪难度加大。如图3所示，无论是方法1还是方法2从第7帧开始都丢失了目标，主要是因为在目标附近有一辆和目标颜色近似的汽车影响了跟踪效果，然而本文算法由于引入了纹理特征依然能较好地跟踪目标。

第3个实例是一段红外视频，与可见光图像相比，红外图像中的目标更为模糊，颜色信息的有效性大打折扣。在本实例中是跟踪一辆运动中的坦克。如图4所示，由于颜色特征无法提供足够的信息区分目标和背景致使方法1和方法2都收敛到了一个错误的位置。另外，正如第2节所述，该目标体积较小导致目标模型中背景与目标比例相当造成目标模型失真，也是算法准确性降低的原因之一。

图2 跟踪汽车左前轮的结果。第一行为文献［9］的跟踪结果，第二行为文献［12］的跟踪结果，第三行为本算法的跟踪结果

图3 跟踪行人的结果。第一行为文献［9］的跟踪结果，第二行为文献［12］的跟踪结果，第三行为本算法的跟踪结果

图4 红外图像序列中跟踪坦克的结果。第一行为文献［9］的结果，第二行为文献［12］的结果，第三行为本算法的结果

表1给出了以像素为单位的各种方法的平均定位误差和方差，其中目标的真实位置通过手工确定。如表1所示，在三个实例中，本文算法都取得了最小的定位误差和方差。

表1 三种方法的定位误差和方差

7 结语

本文提出了一种结合颜色和纹理信息并以直方图交集为相似性度量的扩展Mean-Shift算法。采用对数比加权直方图代替传统直方图构建目标和候选目标模型有效地体现了直方图内各bin之间不同的区分能力。通过自适应的方式结合颜色和纹理信息提高了Mean-Shift算法在复杂情况下跟踪目标的能力。基于Powell方法的两步直方图交集优化过程使得算法能更准确的跟踪目标。实验证明该算法比基本的Mean-Shift算法和基于比例直方图的Mean-Shift算法具有更好的准确性和鲁棒性。

［1］WANG Jun-qiu，Yasushi Yagi.Adaptive Mean-Shift Tracking with auxiliary Particles［J］.IEEE Transactions on System，Man，and Cybernetics，Part B：Cybernetics，2009，39（6）：1578-1589.

［2］CHEN Xiao-peng，ZHOU you-xue，HUANG Xiao-san，et al.A-daptive Bandwidth Mean Shift Object Tracking［C］／／Proceedings of the 2008IEEE Conference on Robotics，Automation and Mechatronics，2008：1011-1017.

［3］Leichter I，Lindenbaum M，Rivlin E.Mean Shift tracking with multiple reference color histograms［J］.Computer Vision and Image Understanding，2010，114（3）：400-408.

［4］Swain M J，Ballard D H.Color indexing［J］.International Journal of Computer Vision，1991，7（1）：11-32.

［5］AN Guo-cheng，ZHANG Feng－jun，DAI Guo-zhong.Mean Shift using novel weight computation and model update［C］／／Proceedings of the 2010IEEE Conference on Acoustics，Speech，and Signal Processing，2010：706-709.

［6］WANG Jun-qiu，Yasushi Yagi.Integrating Shape and Color Features for Adaptive Real-time Object Tracking［J］.IEEE Transactions on Image Processing，2008，17（2）：235-240.

［7］LIU Hong，Yu Ze，ZHA Hong-bin，et al.Robust human tracking based on multi-cue integration and mean-shift［J］.Pattern Recognition Letters，2009，30（9）：827-837.

［8］NING Ji-feng，ZHANG Lei，ZHANG D.Robust object tracking using joint color-texture histogram［J］.International Journal of Pattern Recognition and Artificial Intelligence，2009，23（7）：1245-1263.

［9］Comaniciu D，RameshV，Meer P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-575.

［10］Comaniciu D，Meer P.Mean shift：a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2002，24（5）：603-619.

［11］MäenpääT，Ojala T，Pietikäinen M，et al.Robust texture classification by subsets of local binary patterns［C］／／Proceedings of 15th International Conference on Pattern Recognition，2000：947-950.

［12］Allen J G，Xu R Y D，Jin J S.Object Tracking Using CamShift Algorithm and Multiple Quantized Feature Spaces［C］／／Proceedings of the Pan-Sydney Area Workshop on Visual Information Processing，2004：3-7.