基于三维直方图的改进Camshift目标跟踪算法

摘 要： 经典的连续自适应均值漂移算法Camshift通过HSV空间的色调Hue分量建立一维直方图，在有光照变化及有相似颜色目标或背景的干扰下，跟踪效果不好。提出一种融合HSV空间中色调、饱和度以及反应物体形状信息的边缘梯度的三维直方图特征，并基于背景模型自适应调整特征直方图三种分量的权重值，提高了算法的跟踪准确度。通过与传统Camshift跟踪实验比较，提出的改进算法在光照变化及相似颜色目标/背景干扰下具有更好的鲁棒性，同样也满足跟踪系统的实时性要求。

关键词： 目标跟踪； Camshift算法； 边缘梯度； 三维直方图

中图分类号： TN919?34； TP391.4 文献标识码： A 文章编号： 1004?373X（2014）02?0029?05

0 引 言

目标的检测与跟踪是计算机视觉与模式识别领域一个非常活跃的课题，也是智能视频监控及机器人自动导航等领域的核心问题。在目前已经提出的各种目标跟踪算法中，Meanshift算法由于其计算简单以及良好的实时性而得到广泛的应用。

Camshift跟踪算法是对Meanshift的改进，它是由Gray R.Bradski等提出的自适应缩放跟踪模板尺寸的算法[1]。两种算法本质上都是爬山算法，即在一种数据的密度分布中通过反复迭代而寻找出局部极值稳定的方法。

传统的Camshift算法对于光照的变化以及在前景与背景颜色相似的条件下，跟踪效果并不理想。对此不少学者在Camshift算法中引入其他特征目标模型，如贝叶斯概率框架[2?4]，但由于贝叶斯概率框架等模型固有的计算复杂度，难以实现跟踪的实时性。

考虑到传统的Camshift算法仅引入了HSV空间中的色调Hue分量来建立直方图，从而导致颜色背景相似情形下跟踪效果变差这一事实，本文提出增加颜色空间的S分量以及边缘轮廓的形状信息建立三维联合直方图，以弥补在某些情况下只依靠色调来描述目标特征的不足。

由于该算法主要在目标的直方图统计特征上进行改进，没有涉及到复杂的计算操作，所以效率较高，在稳定性提高的同时易满足实时性的要求。

1 三维特征分量提取

1.1 Hue与Saturation分量

传统Camshift使用HSV空间中的色调Hue通道建立直方图，以致在饱和度S或亮度V变化较大的情形下，其跟踪灵敏度明显降低[5]。本实验首先把RGB颜色空间图像转换为HSV颜色空间图像，如图1（a），（b）所示，并提取H与S两个通道的分量[6]：[H=0， if max=min（60°×g-bmax-min+360°）mod360°， if max=r60°×b-rmax-min+120°， if max=g60°×r-gmax-min+240°， if max=b] （1）

[S=0， if max=0max-minmax=1-minmax， otherwise] （2）

[V=max] （3）

式中：设max等于r， g和b中的最大者；min等于这些值中的最小者。所提取的H与S两个通道的分量如图1（c），（d）所示。

在传统的Camshift算法中，对于Hue通道采用均匀量化以建立直方图模型。计算初始化的搜索窗口内H分量的直方图，对初始搜索窗口中每个像素的H通道值进行采样（如图2（a）蓝色方框所示），从而得到待跟踪目标的色调（Hue）直方图，将该直方图保存下来作为目标的颜色直方图模型，如图2（b）所示。本文提取H与S两通道，在量化HSV图像各通道的位数深度时，类似3通道8位的RGB图像每通道均占8 b为 0～255共256等级，H和S通道也都分配为8位深度。H分量的值域范围是[[0，360°]]，S分量的值域范围是[0，1]，本实验中将H分量的值域范围量化为30个bin （量化长度为[12°]），将S分量的值域范围量化为16个bin （其中量化长度为[116）]。

图2 色调H分量的一维直方图

对于初始化窗口区域的二维直方图的构成，可以看作由H分量与S分量联合而成的二维分布函数，如图3所示。

图4的示意说明了一维直方图与二维直方图之间的关系，其中一维H直方图量化为6个bin，二维H?S联合直方图量化为6×5共30个bin，并且一维Hue通道直方图相当于其边缘分布函数。在本文实验中，实际采用的H?S二维直方图共30（色调）×16（饱和度）=480个bin。

1.2 边缘梯度方向分量

对于框定的初始化目标跟踪区域进行RGB到灰度图转化，然后对该灰度图进行Canny边缘检测。再利用形态学方法先腐蚀后膨胀处理，将图中细小琐碎的边缘点与噪声删除，找到最主要的显著边缘轮廓。假设待跟踪目标的检测结果较为准确，采用Canny算子即可提取到较连续的显著轮廓边缘，如图5所示。

对于所有的边缘像素点，其梯度向量的定义为：

[G（i，j）=GxGy=?x?f?y?f] （4）

利用边缘像素点的梯度方向统计信息，可建立基于边缘梯度方向直方图[7]。实验中计算梯度向量时选用Sobel算子，其可采用如下两个方向模板卷积计算得到：

[Mx=-101-202-101， My=121000-1-2-1] （5）

式中Mx与My为Sobel算子的水平与竖直模板矩阵，分别用于检测水平边缘与竖直边缘。若边缘上位于（i，j）处的像素点P的邻域灰度矩阵标记为：

[P=a0a1a2a3（i，j）a4a5a6a7] （6）

则该点的梯度向量G的水平与竖直分量值Gx和Gy分别为：

[Gx=（a2+2a4+a7）-（a0+2a3+a5）Gy=（a0+2a1+a2）-（a5+2a6+a7）] （7）

该点梯度向量的方向z由水平方向梯度分量值与竖直方向梯度分量值的反正切函数表示为：

[z=arctanGxGy] （8）

对目标边缘的所有的像素点的梯度方向进行统计，可建立基于边缘梯度方向统计分布的目标形状特征模型。图6为基于边缘梯度方向的一维直方图。其中，梯度方向的值域范围是[[0，2π）]，将其量化为16个bin（量化长度为[π8]）。

2 基于三维特征直方图的改进Camshift算法

2.1 权重选择与直方图修正

2.1.1 特征权重的选择

H?S?Grad三维联合直方图的构成类似H?S二维直方图。在初始化区域内统计每个像素点信息，建立一个30（色调）×16（饱和度）×16（边缘梯度方向）共7 680个bin的三维直方图。

为了减少背景干扰，本文自适应减少目标特征直方图中与背景特征直方图相接近的直方图分量的权重，采用目标特征直方图分量自适应加权[8]策略，引入背景直方图，其定义仍为色调×饱和度×边缘梯度方向的共7 680个bin的三维直方图，该背景直方图每个bin值为：

[b=bi， i=1，2，…，7 680，且i=17 680bi=1] （9）

将背景直方图的bi集合中最小的非零值记为bmin，则其对应的目标直方图hi的特征权重为：

[wi=min{bminbi，1}， i=1，2，…，7 680] （10）

考虑到目标窗口的特征直方图，当其某个bin分量与背景对应的bin分量近似一致时，该bin分量在目标特征直方图中的使用会造成对目标跟踪准确性的不良影响，因此应该适当降低其权重值。相应地，对于背景特征直方图中某个取值较大的bin分量，即bi越大，其在对应目标特征直方图hi中的权重应较小，即其对应的hi的权重wi越小。以特征权重值wi去加权目标窗口的直方图hi，从而可进行自适应的调整：

[hi=hiwi， i=1，2，…，7 680] （11）

2.1.2 直方图的更新修正

目标直方图由于光照变化影响需要进行修正更新，根据对每次漂移前后窗口的直方图H1与H2 的Bhattacharyya距离（也称巴氏距离）[8?9]的比较：

[dBhattacharyya（H1，H2）=1-iH1（i）-H2（i）iH1（i）?2H2（i）] （12）

若巴氏距离d=0表示直方图完全相同，d=1表示完全不相同。如果漂移前后H1与H2巴氏距离小于0.4，则动态修正H2如下：

[H2=H1α1+H2α2+H3α3] （13）

式中：H1表示漂移前直方图；H2表示漂移后直方图；H3表示初始化窗口的直方图，系数权重按照统计实验经验取值为：

[α1=0.022 5， α2=0.95， α3=0.027 5] （14）

由此，每次漂移后的直方图H2会受到漂移前和最初始的直方图两者的约束修正。可以看出，此约束主要由漂移后直方图H2决定，其贡献为95%。通过此修正更新的方式可以保证跟踪所用直方图在光照突变时不至于发生剧烈的偏离改变。

2.2 概率反向投影与均值漂移

反向投影过程先利用第2.1节得到的直方图计算整张图像关于该搜索窗口内三种特征出现的概率分布。例如，在整幅图中某个像素点[H，S，Grad]分量值为[32，36，0.1]，而在上面所得到直方图中查询到该bin所占的比例为4%，那么就将该像素点的值置为0.04。这样对于整幅图像所有像素一一对应查询赋值，便得到了整张图像的反向投影图，即二维的概率分布图。

然后把反向投影图转为用8位灰度图表示。概率为1的位置值为255，概率为0的灰度值为0，概率介于1和0之间的灰度值介于255和0之间，如图7所示。经过反向投影，图像中每一个像素的值就变成了三种特征信息出现在此处的离散化概率度量：出现的可能性越大，像素的值就越大，反之就越小。相应地，投影图中对应为：越亮的像素表明该像素为目标像素的概率越大。这样就为下一步的质心计算提供了依据。

计算搜索窗口的质心时，其“质心”就类似物理计算质量分布不均匀的二维平板的重心，只不过这里各点的“面密度” 就是灰度图中各像素点的概率取值。设（x，y）为搜索窗口中的像素点，I（x，y）是反向投影图中对应（x，y）点的像素值。定义搜索窗口的零阶矩[M00]和一阶矩[M10]，[M01]如下[10]：

[M00=xyI（x，y）] （15）

[M10=xyxI（x，y）] （16）

[M01=xyyI（x，y）] （17）

则当前搜索窗口的质心位置为：

[（xC，yC）=M10M00，M01M00] （18）

接下来，将搜索窗口的中心移动到质心。显然，随着窗口的移动，窗口的内容也发生了变化。于是取移动窗口反复迭代计算质心，直到窗口中心与质心间的移动距离小于预设的固定阈值或迭代次数达到某一上限值时，认为质心坐标满足收敛条件。

2.3 Camshift窗口缩放

在做均值漂移之后，再进行Camshift窗口大小缩放。由于窗口中心已经移到了正确的质心位置。此时，对该窗口采取如下缩放策略：

首先，将窗口朝上下左右四个方向各扩增10个像素，得到一个新窗口。

然后，计算该新窗口的零阶矩[M00]，一阶矩[M10，][M01]，二阶矩[M20]，[M02]，[M11]。记：

[a=M20M00] （19）

[b=M11M00] （20）

[c=M02M00] （21）

则旋转角度为：

[θ=arctan2ba-c+4b2+（a-c）2] （22）

下一帧所用新的搜索窗口的长和宽分别为：

[length=4cos2θM20+2cosθsinθM11+sin2θM02M00] （23）

[width=4sin2θM20-2cosθsinθM11+cos2θM02M00] （24）

如果length

3 实验结果分析

本文实验采用VisualStudio 2010及OpenCV 2.3开发软件平台。实验1的场景较为简单，背景颜色与目标区分明显。主要测试在光照改变及有相似颜色干扰目标或背景的条件下，只基于色调分量的经典Camshift算法与改进后的基于多特征直方图的Camshift的性能比较。实验中待跟踪目标逐渐接近颜色相近的干扰目标，且在最后光照强度发生突变。

在图8（a）与图9（a）中显示了经典Camshift算法的跟踪效果，从左至右可见，当目标与背景颜色对比度较高时其跟踪效果还不错，但是当目标接近颜色相似的干扰目标时，Camshift窗口扩大至包含非目标的错误区域，准确性偏低。这正是由于其仅依靠色调Hue单个信息通道导致无法准确描述目标特征。

图8（b）与图9（b）为使用添加饱和度S分量后的二维特征直方图的跟踪效果。可以看出，其对于不同的色调与饱和度颜色信息有一定的区分度。但是当最后改变光照时，其仍然受到显著影响而出现误跟踪现象。这主要是由于H分量与S分量均属颜色空间信息，对光照条件的改变较为敏感以及易受相似颜色干扰物的影响。

图8（c）与图9（c）是进一步添加了目标的边缘梯度方向而改进的三维特征Camshift跟踪效果。由于边缘梯度方向的统计分布实质描述了目标的形状信息，在最后光照强度改变时，形状信息的权重值会因与背景形状信息差别显著而相应增加，提高了跟踪算法在光照变化下的抗干扰性。在整个算法的运行过程中，目标物始终被准确跟踪，如图8（c）与图9（c）所示。

这主要得益于其引入的形状信息及增强的颜色描述信息，使得跟踪算法对于有相似颜色物干扰及光照改变都具有较好的鲁棒性。由图10可见，传统的仅基于Hue通道的Camshift对于低对比度背景、背景与目标颜色非常接近的环境几乎无能为力，跟踪无法稳定进行。从反向投影图可以明显地看出，Camshift认为几乎整个背景都是前景目标，这主要是由于前景背景颜色非常接近，仅依靠色调单通道信息无法区分背景与目标。

图11中，改进的Camshift基本保持了稳定的跟踪，尤其从图11（b）的反向投影图中可以看出，此时并未出现Camshift误认为整个背景都是目标的情况发生。此时，由于背景与目标颜色比较接近，所以颜色特征直方图的权重值被抑制得比较小，跟踪的实现主要依靠于边缘梯度方向直方图提供的目标形状信息。

4 结 语

Camshift算法的核心是利用建立的目标统计特征直方图进行反向投影，从而均值漂移以跟踪上目标。传统的Camshift仅依靠单一的色调Hue通道建立一维直方图，对于光照改变及常见的相近颜色背景或干扰目标往往跟踪效果不理想。为此本文引入了饱和度与边缘梯度方向两个特征，建立了可同时描述目标颜色信息与形状信息的三维特征直方图，以处理背景颜色、形状信息与目标不同的各种环境，提高跟踪的准确性。此外，对三维直方图的这三个特征分量采取自适应加权选择，以进一步抑制背景干扰目标，增强了复杂环境下的跟踪鲁棒性。由于文中保持均值漂移定位局部极值的步骤，仅通过直方图的改进及自适应加权来改进跟踪算法，未涉及较高计算复杂度的处理过程，因此，仍能满足跟踪系统的实时性与稳定性要求。

参考文献

[1] BRADSKI G R. Computer vision face tracking for use in a perceptual user interface [J]. Intel Technology Journal， 1998， 2（2）： 1?15.

[2] HAUG A J. Bayesian estimation for target tracking： part I， general concepts [J]. WIREs Comp Stat， 2012， 4（06）： 375?383.

[3] HAUG A J. Bayesian estimation for target tracking： part II， the Gaussian sigma?point Kalman filters [J]. WIREs Comp Stat， 2012， 4（06）： 489?497.

[4] BUDIHARTO W， PURWANTO D， JAZIDIE A. A robust obstacle avoidance for service robot using Bayesian approach [J]. International Journal of Advanced Robotic Systems， 2011， 8（01）： 52?60.

[5] SANTIAGO R， PILAR S， EDUARD M. Variability estimation of hue and saturation compoents in the HSV space [J]. Color Research and Application， 2011， 37（06）： 261?271.

[6] 赵红雨，吴乐华，史燕军，等.基于HSV颜色空间的运动目标检测方法[J].现代电子技术，2013，36（12）：45?48.

[7] 林建华，刘党辉，邵显奎.多特征融合的Camshift算法及其进一步改进[J].计算机应用，2012，32（10）：2814?2816.

[8] WILKASON T J. Robust video tracking through multiple occlusions [D]. GA： Mount de Sales Academy of Warner Robins， 2009.

[9] KHALID M S， ILYAS M U， SARFARAZ M S， et al. Bhatta?charyya coefficient in correlation of gray scale objects [J]. Journal of Multimedia， 2006， 1（06）： 56?61.

[10] CHU Hong?xia， YE Shu?jiang， GUO Qin?chang， et al. Object tracking algorithm based on Camshift algorithm combinating with difference in frame [C]// Proceedings of the IEEE International Conference on Automation and Logistics. Jinan， China： IEEE， 2007： 51?55.