基于直方图插值的均值移动小尺寸目标跟踪算法

陈建军 安国成 张索非 吴镇扬

①(东南大学信息科学与工程学院 南京 210096)②(中国科学院软件所人机交互技术与智能信息处理实验室 北京 100190)

1 引言

视觉跟踪技术自动检测和跟踪视频序列中的目标，估计目标的运动参数和运动状态。其在智能视频监控、友好人机交互、基于内容的视频检索和压缩、视频会议和大型活动安防等领域中应用广泛。

在远距离室外视频监控和点光源跟踪等应用中都会遇到小尺寸目标跟踪的问题[1]。有时也会把大尺寸目标分成多个小区域，分别跟踪各区域的低维运动参数(如位移)，再将所有跟踪结果融合起来估计目标整体的高维运动参数(如位移、尺寸和旋转等)[2]。小尺寸目标包含的像素非常少，而其外表特征又很容易发生变化，所以很难用传统的方法来跟踪它们。近几年，研究人员提出了很多小目标的检测和跟踪算法[3,4]。Formont等人[3]使用非线性最优滤波器，提出了基于自适应相关的小目标跟踪算法。Wang等人[4]研究了海面上小尺寸运动目标的检测和跟踪问题。他们把背景相减法和对称差分法结合起来检测目标，使用均值移动和卡尔曼滤波来跟踪目标。

近几年，均值移动算法在视觉跟踪中得到广泛应用[5−12]，其原理简单，实时性能优越。均值移动是在1975年由Fukunaga等人[5]在非参概率密度估计中求解概率密度的极值问题而提出，当时并没有受到人们的重视。直到1995年，Cheng对均值移动迭代算法加以推广，并应用于聚类分析中[6]，引起研究人员的关注。Comaniciu在将均值移动算法应用于视频目标跟踪方面做了大量工作，提出了鲁棒高效的均值移动视觉跟踪算法[7]。随后对均值移动算法的研究基本是在他提出框架下进行的。近年来，有学者在跟踪特征的选择，直方图单元的划分等方面对其加以改进。Bajramovic等人[8]采用多种不同特征，把各种特征的直方图加权组合作为跟踪线索，使用均值移动和信赖域优化方法跟踪目标。Li等人应用均值移动算法的聚类功能自适应划分颜色空间，并用独立分量分析(ICA)对每个单元内的颜色分布进行建模[9]。Chu等人使用最大模糊熵高斯聚类算法将观测点加入到跟踪窗中，并把Kalman滤波与均值移动算法相结合来快速跟踪目标[10]。Li等分别使用背景加权直方图和颜色加权直方图来表示目标模型和候选目标，可以自适应地获得目标尺寸，通过由粗到细的方法实现均值移动寻找全局极大值点，减少了所需的迭代次数[11]。

本文使用均值移动算法来跟踪小尺寸目标。论文首先对均值移动算法在跟踪小尺寸目标中计算权值时容易出现的除以零问题进行了分析，并指出了其一般处理方法所导致的跟踪中断问题；然后将Parzen窗密度估计方法加以改进，并用来对候选目标区域的直方图进行插值；本文采用Kullback-Leibler距离来度量目标模型和候选目标的相似性，增加了度量的可分辨性，提高了算法的跟踪精度和鲁棒性。论文在多段视频中跟踪目标，结果表明，本文提出的算法可以有效地跟踪只有6×12个像素的小目标。

2 均值移动算法跟踪小尺寸目标的主要问题

2.1算法跟踪中断问题

均值移动在当前帧中跟踪目标时，需要按照下式[7]迭代计算新位置y1

其中xi是以y0为中心，h为带宽的核窗内的像素坐标；g(⋅)为核函数的影子函数；这里权值ωi的计算公式为

其中qu和pu(y0), u=1,…, m分别为目标模型和y0处候选目标的直方图；b(xi)是点xi所在直方图单元的指示函数。

可见均值移动算法需要把目标模型和候选目标的相应直方图单元qu和pu(y0)相除来计算权值ωi。小尺寸目标包含的像素很少，因此其直方图中只有很少单元有非零值，绝大部分的数值都为零。当pu取值为零时，就会出现除以零问题。文献中的一般处理方法是[7]：如果像素xi所对应的直方图单元pu=0，则将其权值设置为零，即ωi=0。在跟踪过程中，受外部环境变化和目标自身运动等因素的影响，目标颜色值会发生变化，从而引起候选目标直方图分布的变化。当对于核窗内所有像素xi，qu和pu(y0)的非零单元都不重叠时，即qu* pu(y0)=0,u=1,…,m，得到的所有权值ωi都为零。这样式(1)就是零除以零运算，计算的目标新位置为奇异值，从而导致跟踪中断。

2.2 跟踪目标丢失问题

在均值移动跟踪算法中，目标模型与候选目标之间的相似性度量函数非常重要，它决定了在计算新位置时各个像素的权值大小。目前常用的均值移动算法[7,8]把Bhattacharyya系数作为相似性度量函数：

可以看出在Bhattacharyya系数中，目标模型和候选目标的作用是平等的。但是在跟踪过程中，目标模型是固定的(如果不更新模板)，而候选目标区域却是时刻变化的。所以把目标模型和候选目标的作用等同起来是不合适的，会降低算法的跟踪精度和鲁棒性，从而导致丢失跟踪目标。另外Bhattacharyya系数还有辨别能力弱，计算量按样本数量的平方增长等缺点[12]。

3 基于直方图插值的改进算法

3.1 直方图插值

式中c为归一化常数，δ(⋅)为Kronecker delta函数，b()是点所在直方图单元的指示函数。

如前所述，小尺寸目标的像素少，易使候选目标与目标模型不匹配，导致跟踪中断。一些传统的数值处理手段和模板更新等可以在一定程度上解决这个问题。但是模板更新面临着更新时机难确定，易把背景像素引入模板中，算法实现复杂等问题。本文使用一种简单有效的直方图插值方法来解决这个问题。本文用Parzen窗法对候选目标的直方图进行插值。Parzen窗法是一种常用的非参概率密度估计方法，其由Parzen于1962年提出[13]。对于n个d维训练样本U={u1,u2,…,un}，Parzen窗密度估计法为[14]

其中ϕ(⋅)是非负窗函数；hn是窗口尺寸。

可以看出原Parzen窗法没有利用插值直方图单元u周围单元的信息，所以原Parzen窗法不能直接应用到本文的直方图插值处理中。本文对原算法进行改进，得到新的基于Parzen窗的直方图插值处理方法为

其中v是窗ϕ(⋅)中所包含的直方图单元的索引值；hN是插值窗函数的带宽；C是归一化系数，其是要保证所以有C=

经过直方图插值处理的结果如图1所示。本文选择在归一化rg颜色空间中建立直方图，其中rg划分的单元数为64×64。图1(a)是视频序列中的一帧图像以及目标区域(6×12)。图1(b)是目标区域的直方图，可见由于目标包含的像素很少，只有极少直方图单元有非零值。图1(c)是使用改进直方图插值方法得到的直方图。可以看出，原非零值单元的数值未发生变化，而这些单元附近的原零值单元有了较小数值。这样既没有对真实直方图的数值分布产生很大影响，又给目标颜色区域的单元赋予了一定数值，有效地解决了权值计算中的除以零问题。

图1 直方图插值处理结果

3.2 相似性度量函数

建立了目标模型和候选目标的颜色直方图，就可以度量两者之间的相似性。相似性度量函数的选择非常重要，其直接影响着算法的跟踪精度和鲁棒性。本文采用Kullback-Leibler距离代替Bhattacharyya系数来度量两者之间的相似性，即有

用Bhattacharyya系数和Kullback-Leibler距离来度量不同距离的结果如图2所示。假设qu是服从均值为10，方差为1的高斯分布；而(y)是均值从0变到10，方差为1的高斯分布。图中横坐标为(y)的均值，纵坐标为两者之间的距离。可以看出随着两个分布越来越接近，Bhattacharyya系数反映了两者的相似程度，因此其逐渐增大；Kullback-Leibler距离是度量两者之间的区别，所以其逐渐减小。后者比前者的变化范围大，这就意味着其有更强的辨别能力，可以更好地区分目标模型和候选目标。

3.3 跟踪算法

图2 两个分布之间的不同距离度量

其中权值ωi的计算公式为

式(9)右边的前两项是常数，与y的值无关，因此要使ρ(y)最小，只要使等式右边的第3项最大。可以看出该项是在给各像素xi赋予了权值ωi之后，基于核函数k(⋅)估计的y处的概率密度，因此可以用均值移动算法来计算ρ(y)的极值点。ρ(y)不断迭代从当前位置y0移动到新位置y1，就能够以最快的速度收敛到极值点，这里的新位置迭代公式为

其中g(x)=−k'(x)，这里假设k(x)在x∈[0,∞)上的导数总是存在。

新算法与传统均值移动算法的主要区别在于权值ωi的不同(式(2)和式(10))。在跟踪过程中，目标模型是由检测或手工标注得到的，通常比较准确，因此其直方图中目标颜色分量较多，对应直方图单元的数值比较大，非目标颜色单元的数值较小。对还没有跟踪到目标真实位置的候选目标区域而言，情况恰恰相反，其包含的背景区域相对较多，因此目标颜色分量对应直方图单元的数值较小，而非目标颜色分量对应单元的数值较大。因此由式(10)计算的权值总体上是目标区域像素的权值大于1，而非目标区域像素的权值小于1。而传统均值移动算法在计算权值时要在式(10)的基础再做开方运算，这样会减小目标区域像素的权值，增大非目标区域像素的权值，缩小权值的变化范围。这样就不能很好地区分目标和非目标区域，影响算法的跟踪精度。另一方面，新权值无需做开方运算，减少了算法的计算量。

本文选择Epanechnikov核，则y1的计算公式可以简化为

在给出以上准备工作之后，将本文提出的基于直方图插值处理和新型度量函数的均值移动小尺寸目标跟踪算法的主要流程总结如下：

给定目标模型的颜色直方图{qu}；目标在上一帧中的位置y0。

(1)初始化目标在当前帧中的位置y0，并计算以y0为中心的候选目标的核颜色直方图{pu(y0)}；

(2)通过检查候选目标{pu(y0)}与目标模型{qu}是否有非零单元重叠来判断两者是否匹配：如果匹配转到步骤(4)继续跟踪；否则转到步骤(3)进行直方图插值处理；

(3)用式(7)对候选目标的直方图{pu(y0)}进行插值处理，得到插值后的直方图{(y)}；0

(4)根据新型权值计算式(10)计算各像素的权值{ωi}, i=1,…,nh；

(5)按照位置更新公式(12)计算候选目标的新位置y1；

(6)判断如果‖y1－y0‖＜ω，则停止迭代，并令y0＝y1，输出目标在当前帧中的位置，读入下一帧，开始新的跟踪；否则，赋值y0＝y1，返回到步骤(1)，继续迭代跟踪。

4 实验结果

本文所提算法在多段视频中进行测试，这里给出部分结果。rg颜色空间被划分为64×64个单元；直方图插值选择高斯窗，窗函数带宽hN为10；算法的最大迭代次数为15次；迭代终止门限ω为1个像素。初始帧中的目标真实位置是由手工标注的。

表1给出了基本均值移动算法(Traditional Mean Shift，TMS)和本文的基于直方图插值的均值移动算法(Histogram Interpolation-based Mean Shift，HIMS)对视频序列的总体跟踪性能。表中列出了3段视频序列的跟踪结果。目标的真实位置由手工标注。在每帧中对目标区域标注3次，然后求其平均值作为真实值。如果连续两次标注的误差超过某个阈值(标注误差)，则重新标注该帧图像。X误差和Y误差分别表示在X，Y方向上的误差。在每帧中，如果跟踪的目标中心落在手工标注的目标区域内，则认为跟踪成功，否则认为跟踪失败。整段视频的跟踪率定义为全部成功跟踪的帧数除以该序列的总帧数，即

表1 算法跟踪的总体性能比较

从表中可以看出：除序列OurSeq_001的Y方向平均误差之外，本文所提的HIMS算法对所有序列跟踪的X，Y方向误差的均值和标准差都小于TMS算法。这说明HIMS比TMS跟踪的更加准确，而且跟踪更加稳定，算法鲁棒性更高。HIMS的跟踪率也明显高于TMS。

4.1 跟踪中断问题

序列OurSeq_001共有751帧，每帧大小为160×120，目标尺寸为8×16。目标有转圈、停留、转身等动作，而且运动到树荫区域。图3给出了两种算法的跟踪结果。TMS在第175，253和532帧时跟踪中断，在第541，550，570，587和711帧时丢失目标。HIMS能够一直跟踪目标。图4是TMS和HIMS的跟踪误差。图中横坐标是帧标号，纵坐标是欧氏距离误差(像素)。图中实线和虚线分别是TMS算法和HIMS算法的跟踪误差(后面同)。TMS跟踪失败的次数较多，多次重新开始跟踪，相当于进行模板更新。但其在中断帧处产生非常大的误差，而且在后续帧中的误差也变化较大。HIMS的跟踪误差大多在5个像素以内，而且比较稳定，有效地解决了除以零运算问题，提高了算法的鲁棒性。

4.2 跟踪目标丢失问题

CAVIAR项目[15]视频是监控类视频，主要用于目标行为识别和分析。序列Fight_OneManDown(FOMD)中跟踪目标出现在第168帧到436帧共269帧中，每帧大小为384×288，目标尺寸为14×16。目标与他人打斗，并将对方打倒在地，然后逃窜。目标运动较快，动作幅度较大，而且目标上衣颜色与地面颜色非常接近，因此跟踪难度很大。图5给出了两种算法的跟踪结果。TMS在第181，297，436帧时丢失目标。HIMS可以始终跟踪目标。图6给出了TMS和HIMS的跟踪误差。在第296帧之前，HIMS跟踪的更加准确；之后目标直线快速奔跑，两种算法的跟踪精度差别不是很明显。

4.3 算法整体性能验证

序列OurSeq_002既有多次跟踪中断，也有多次丢失跟踪目标，因此其可以用来验证直方图插值和新型相似性度量函数的总体性能。序列共有683帧，目标出现在第196帧到第524帧共329帧中，每帧大小为160×120，目标尺寸为6×12。目标在光照有较大变化的区域内行走，且有部分遮挡。图7给出了TMS和HIMS的跟踪结果。由于目标的尺寸非常小，而且光照变化较大，TMS在第219，311，331，367，384，387，425和471帧跟踪中断，在第295，302，478，500和520帧丢失跟踪目标；HIMS可以一直跟踪目标。图8给出了两种算法的跟踪误差。可以看出，HIMS的跟踪误差基本都在5个像素以内；TMS算法多次发生跟踪中断和丢失跟踪目标，因此其跟踪误差波动较大。

图3 对序列OurSeq_001的跟踪结果，依次是第53，291，541，570，587，711帧

图4 对序列OurSeq_001的跟踪误差

图5 对序列FOMD的跟踪结果，依次是第181，265，297，436帧

图6 对序列FOMD的跟踪误差

图7 对序列OurSeq_002的跟踪结果，依次是第219，295，302，478，500，520帧

图8 对序列OurSeq_002的跟踪误差

5 结论

本文提出了一种基于直方图插值处理的均值移动小尺寸目标跟踪算法。论文分析了均值移动算法权值计算中的除以零问题和其一般处理方法，以及其所导致的跟踪中断问题。论文提出在候选目标与目标模型不匹配时，对候选目标的直方图进行插值处理来增加其非零单元数，然后再用均值移动进行跟踪。此外论文还选用Kullback-Leibler距离来度量目标模型和候选目标的相似性。实验结果表明，本文所提算法可以有效地跟踪小尺寸目标，算法的跟踪精度也有一定提高。

[1] Kaewtrakulpong P and Bowden R. A real time adaptive visual surveillance system for tracking low-resolution colour targets in dynamically changing scenes [J]. Image and Vision Computing, 2003, 21(10): 913-929.

[2] Han B and Davis L S. Probabilistic fusion-based parameter estimation for visual tracking [J]. Computer Vision and Image Understanding, 2009, 113(4): 435-445.

[3] Formont S, Laude V, and Refregier P. Small target tracking on image sequence using nonlinear optimal filtering [C].Signal and Data Processing of Small Targets, 1995. San Diego,CA, USA, SPIE, 1995, 2561: 299-307.

[4] Wang L, Hu S, and Zhang X. Detecting and tracking of small moving target under the background of sea level [C]. The 9th International Conference on Signal Processing, ICSP'2008,Beijing, China, 2008: 989-992.

[5] Fukunaga K and Hostetler L. The estimation of the gradient of a density function, with applications in pattern recognition[J]. IEEE Transactions on Information Theory, 1975, 21(1):32-40.

[6] Yizong C. Mean shift, mode seeking, and clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1995, 17(8): 790-799.

[7] Comaniciu D, Ramesh V, and Meer P. Kernel-based object tracking [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-577.

[8] Bajramovic F, Gr C, and Denzler J. Efficient combination of histograms for real-time tracking using mean-shift and trust-region optimization [C]. The 27th Symposium on German Association for Pattern Recognition, DAGM2005,Vienna, Austria, Springer Verlag, 2005, 3663: 254-261.

[9] Li P. An Adaptive Binning Color Model for Mean Shift Tracking [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2008, 18(9): 1293-1299.

[10] Hongxia C and Wang K. Target tracking based on mean shift and improved kalman filtering algorithm [C]. IEEE International Conference on Automation and Logistics, ICAL'09. Shenyang, China, 2009: 808-812.

[11] Li S X, Chang H X, and Zhu C F. Adaptive pyramid mean shift for global real-time visual tracking [J]. Image and Vision Computing, 2010, 28(3): 424-437.

[12] Yang C, Duraiswami R, and Davis L. Efficient mean-shift tracking via a new similarity measure [C]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR '2005. San Diego, CA, United states,2005: 176-183.

[13] Parzen E. On estimation of a probability density function and mode [J]. Annals of Mathematical Statistics, 1962, 33(3):1065-1076.

[14] Shen H and Yan X. Probability density estimation over evolving data streams using tilted Parzen window [C]. IEEE Symposium on Computers and Communications, ISCC'2008,Marrakech, 2008: 585-589.

[15] CAVIAR: EU funded project, IST 2001 37540, URL:http://homepages.inf.ed.ac.uk/rbf/CAVIAR/(2004).