基于分块颜色直方图的MS跟踪算法

张红颖，王赛男，胡文博

（中国民航大学电子信息与自动化学院，天津 300300）

基于视觉的目标跟踪一直是计算机视觉领域的一个热门分支[1-2]，其广泛应用于智能人机交互、视频监控及国防安全等领域。自从Comaniciu等[3]使用结合颜色直方图的MS（mean shift）算法进行目标跟踪后，MS跟踪算法凭借其简单、有效的优势受到广泛关注，但当目标与背景颜色相近或出现遮挡时，使用该算法会出现跟踪丢失的情况。

为解决该问题，许多学者提出了各种改进算法[4]。文献[5]在MS算法中引入自适应Kalman滤波作为辅助手段，使其能够预测跟踪发生短时间遮挡的目标，但是该方法对运动模型有一定的要求。文献[6]提出使用遮挡因子作为遮挡的判定条件，但由于增加了计算的复杂度，无法满足跟踪的实时性要求。文献[7]首先利用Bhattacharyya系数下降率来判断跟踪目标是否出现了遮挡，若系数急剧下降，判断出现遮挡，然后利用改进的GM（1，1）预测模型，对后续帧中的目标位置进行预测，若目标脱离遮挡，则继续使用MS算法进行后续跟踪，该方法复杂且对遮挡的判断易受其他因素影响。

针对复杂场景下目标遮挡问题，提出了一种基于分块颜色直方图的MS跟踪算法。首先将目标的整体区域颜色特征划分成几个局部区域的颜色特征。然后利用分块颜色直方图作为目标表征模型，这样得到的目标特征具有较强的局部特征表达能力。最后为了准确跟踪目标，提出了一种基于分块颜色直方图的置信图生成方式，相较于传统MS算法中使用的反向投影图，置信图能够更精确地表示目标的位置信息。实验结果表明，该方法简单易行，能有效解决复杂环境下的遮挡问题，具有较好的鲁棒性。

1 MS跟踪算法

对于d维空间中的n个点，点x处的MS向量表示为

其中：k表示n个点中，只有k个点落入区域；Sr是一个半径为r的高维球区域，定义如下

可看出，MS向量就是对落入区域Sr（x）中的k个样本点相对于点x的偏移量求和后取平均。因此，MS算法会使当前点向点密度最高的区域移动，如图1所示。

图1 MS原理图Fig.1 Schematic diagram of MS

考虑到每个样本点的重要程度不同，离中心点较近的样本点对估计更有效，因此在计算MS向量时给不同样本点赋以不同的权值，可提高算法的鲁棒性。MS算法使用径向对称的核函数进行加权，即

其中，cd是d维单位球的体积。

引入核密度梯度估计后，MS向量变为

其中：g（x）=-K′（x）；h为核函数窗口宽。MS算法就是从xi起向两个模型相比颜色变化最大的方向不断移动，直到最后两次的移动距离小于阈值，即找到当前帧的目标位置，并以此作为下一帧的起始点，直到视频跟踪结束。

2 基于分块颜色直方图的MS跟踪算法

2.1 分块颜色直方图

普通颜色直方图统计的是目标整体区域的颜色信息，因此无法有效地表达出目标区域不同颜色的分布状况。为解决上述问题，改进算法将HOG算法[8]的分块思想引入颜色直方图中，将目标区域划分成互不重叠的子单元box，将几个box组成一个块block，block之间相互重叠，如图2所示。提取并记录每个block的颜色直方图特征，最后将所有的block特征组合形成整块目标区域的特征向量。

图2 分块子区域Fig.2 Block subregion

设目标整体区域为宽高w×h的窗口，提取分块颜色直方图时，首先将该窗口分成m个大小为x×y的重叠子区域block，对每个block单独提取颜色直方图，然后将各block的短颜色直方图按照固定顺序连接成一个长颜色直方图作为目标区域的颜色特征。

为有效地提取分块颜色直方图特征的同时能尽量提高处理速度，计算分块颜色直方图特征前，需先对图像进行降维处理。图像的降维过程实际是采用线性差值法对图像的尺寸进行比例缩小，降维因子scale根据跟踪目标大小和图像质量进行选择。

2.2 HSV空间提取颜色信息

图像多以RGB颜色空间的形式保存，但其空间各分量之间冗余信息较多，而HSV空间能独立感知各分量的变化，较好地反映人眼对色彩的感知和鉴别能力。由RGB空间转化为HSV空间的表达式如下

式中，0≤V≤1，0≤S≤1，0≤H≤360。在 HSV 空间提取颜色信息，为了减弱光照条件的影响，忽略亮度信息V，仅根据H和S通道像素值投票至颜色直方图。在构建颜色直方图时遍历子区域block中的每一个像素，得到每一子区域block的颜色直方图后，逐一进行归一化并按照各自的位置顺序连接起来，组成完整的分块颜色直方图向量v。

2.3 基于分块颜色直方图的置信图生成方法

如果一幅图像的区域中显示的是一种结构纹理或一个独特的物体，那么这个区域的直方图可看成一个概率函数，其表现形式是某个像素属于该纹理或物体的概率。改进算法所提出的置信图[9-10]实质上相当于概率密度图，其代表了目标区域的特征在一幅新图像中存在的概率，置信图的灰度值越大则概率越高。

目标模板和候选区域的直方图之间的相似性选用相关方法，得到取值范围为0～1的相似度系数d（H1，H2），可表示为

为了获得置信图，在获得目标区域完整的分块颜色直方图向量v0后，读取下一帧图像frame，按照如下步骤对图像进行处理：

1）图像降维；

2）按照从左到右，从上到下的顺序用宽高为w×h的检测窗口按照自定义的步长stride去移动检测窗口；

3）求取当前检测窗口下的分块颜色直方图向量v，采用相关对比方法对 v[i]和 v0[i]，（i=0，1，…，m-1）进行直方图对比，得到相似度系数di（v0[i]，v[i]）（i=0，1，…，m-1），对di（v0[i]，v[i]）相加并求出均值dmean，将dmean×255作为灰度值依次写入到置信图相应的像素中；

4）若遍历未结束，跳转到第2步；

5）对置信图的灰度值归一化到区间0～255，并采用线性插值方法进行上采样，调整到与图像frame的尺寸一致。

传统MS算法是在反向投影图中进行迭代来寻找最佳匹配目标位置，而改进算法则是采用置信图的方式。置信图的概念与反向投影类似但不完全一样，置信图相比反向投影图具有更优越的表达性能，在目标跟踪中具有更出色的表现，如图3所示。

图3 目标区域的反向投影图和置信图对比Fig.3 Comparison between back projection and confidence map of target area

从图3中反向投影图和置信图对比可知，反向投影图目标区域位置分散，不能精确地反映目标区域特征，而置信图中目标区域位置集中，能够很好地反映出目标区域特征在下一帧图像frame中的位置。

2.4 算法框架

MS算法是一种不需要任何先验知识而完全依靠特征空间中样本点来计算其密度函数值的核密度估计法。针对目标遮挡问题，提出的基于分块颜色直方图的改进算法，整体流程图如图4所示。

图4 改进算法流程图Fig.4 Flow chart of impoved algorithm

首先在第1帧图像中标注目标位置，然后对目标区域提取分块颜色直方图特征作为目标表征模型，接着读取下一帧图像，生成置信图，最后利用MS算法在置信图中迭代从而寻找目标区域，实现跟踪。循环直至整个视频序列全部读取完毕。

3 实验结果与分析

为保持较好的精度，又能大幅缩短运行时间，实验采用分块重叠的子区域block提取颜色直方图特征，参数设置为 m=9，scale=2，stride=6。

3.1 目标未被遮挡情况分析

该情况下采用Visual Tracker Benchmark[11]中BoBot数据集的部分图片序列，针对的主要是图片中移动的人物目标，背景较为复杂。该图片序列为RGB三通道彩色图像序列，分辨率为320×240。仿真结果如图5～图8所示。

由图5～图8分析可知：在第100帧，两种算法都能较好地找到目标区域；在第619帧，置信图仍能够较好地反映目标区域位置，而反向投影图的目标区域已被严重干扰；在第924帧，改进算法依然精确地找到目标区域位置，而传统MS算法已完全跟丢目标。

图5 BoBot反向投影图Fig.5 Back projection of BoBot

图6 BoBot改进算法的置信图Fig.6 Confidence map of BoBot based on improved algorithm

图8 改进算法在BoBot中的跟踪结果Fig.8 Tracking result of BoBot based on improved algorithm

3.2 目标部分被遮挡情况分析

该情况下采用Visual Tracker Benchmark中faceocc1数据集的图片序列，针对的主要是图片中被遮挡的人脸目标，遮挡情况由轻微遮挡到大面积遮挡，变化范围较大。该图片序列为RGB三通道彩色图像序列，分辨率为352×288。仿真结果如图9～图12所示。

由图9～图12分析可知：在第41帧，由于目标区域仅被轻微遮挡，两种算法都能较好地找到目标区域；在第555帧，目标区域被严重遮挡，由于手部的颜色与面部颜色接近，置信图出现了误差，但由于MS算法是在局部寻找极值，所以手部的干扰并不会造成影响，置信图仍能够较好地反映目标区域位置，而反向投影图的目标区域已被严重干扰，跟踪错误；在第899帧，目标区域几乎恢复到了未被遮挡状态，改进算法依然精确地找到了目标区域位置，而传统MS算法已无法再次找到目标。

图9 faceocc1反向投影图Fig.9 Back projection of faceocc1

图10 faceocc1改进算法的置信图Fig.10 Confidence map of faceocc1 based on improved algorithm

图11 传统MS算法在faceocc1中的跟踪结果Fig.11 Tracking result of traditional faceocc1 based on MS algorithm

图12 改进算法在faceocc1中的跟踪结果Fig.12 Tracking result of faceocc1 based on improved algorithm

3.3 目标大面积被遮挡情况分析

该情况下采用VisualTrackerBenchmark中的Babenko数据集的部分图片序列，针对的主要是图片中移动的人脸目标，背景颜色与人脸颜色相似，且存在大面积遮挡。该图片序列为RGB三通道彩色图像，分辨率为320×240。仿真结果如图13～图16所示。

由图13～图16分析可知：在第47帧，虽然人脸外形稍微变大，但两种算法都能较好地找到目标区域；在第105帧，人脸完全背向镜头，但由于在初始目标区域中，分块颜色直方图包含了黑色头发的颜色特征，即使人脸完全背向镜头，改进算法也能检测出黑色的头发，而反向投影图的目标区域已经丢失；在第308帧，图像背景颜色和初始区域目标颜色相近，改进算法的置信图仍然给出了精确的目标位置，而反向投影图已无法找到目标区域，这是因为分块颜色直方图细致地划分了初始目标区域的颜色特征。

图13 Babenko反向投影图Fig.13 Back projection of Babenko

图14 Babenko改进算法的置信图Fig.14 Confidence map of Babenko based on improved algorithm

图15 传统MS算法在Babenko中的跟踪结果Fig.15 Tracking result of Babenko based on traditional MS algorithm

图16 改进算法在Babenko中的跟踪结果Fig.16 Tracking result of Babenko based on improved algorithm

4 结语

针对复杂场景中的目标遮挡问题，对MS跟踪算法进行了研究和改进。为了得到较强的局部特征表达能力，将目标的整体区域颜色特征划分成几个局部区域的颜色特征，利用分块颜色直方图作为目标表征模型。为了准确跟踪目标，提出了一种基于分块颜色直方图的置信图生成方式，使MS算法在置信图中迭代，得到目标最佳区域。从目标未被遮挡、目标被部分遮挡、目标与背景相似且存在大面积遮挡3种情况进行实验，改进算法的效果优于传统MS跟踪算法。由于改进算法对目标的颜色直方图进行了细致的划分，且得到了可靠的置信图，该算法对于目标遮挡问题具有较好的鲁棒性。