目标跟踪中巴氏系数误差的分析及其消除方法

目标跟踪中巴氏系数误差的分析及其消除方法文志强1,2蔡自兴11(中南大学信息科学与工程学院湖南长沙410083)2(湖南工业大学计算机与通信学院湖南株洲412008)摘要：在meanshift的目标跟踪方法中，Taylor公式的近似展开会造成优化过程中Bhattacharyya系数值的误差，这种误差会给目标跟踪带来偏差，同时不适合快速运动目标的跟踪。针对Bhattacharyya系数的Taylor公式近似表示情形，研究了这种近似表示引起的系数误差和对目标跟踪的影响，在此基础上，将Bhattacharyya系数的优化问题转化为求解约束优化问题，从而提出一种改进的目标跟踪方法，以达到提高目标跟踪的精度，而且证明了该改进方法的收敛性。实验表明本文方法对于快速运动目标的跟踪具有更好的跟踪精度。关键字：meanshift,目标跟踪,目标模型,Bhattacharyya系数中图法分类号:TP3011引言Meanshift是一个由Fukunaga和Hostetler在1975年提出的一种无监督聚类方法，它使每一个点“漂移”到密度函数的局部极大值点。1995年，Cheng[1]重新研究了meanshift，提出了更一般的表达形式并预示该算法在聚类和全局优化方面的巨大潜力。Comaniciu在1999年对meanshift做了应用方面的研究[2]。自此以后，meanshift已广泛应用于目标跟踪[3-5]、图像分割[6]、聚类分析[7]等领域，已成为当前研究的热点问题。Comaniciu在[3][4]中首先将meanshift算法应用到目标跟踪领域中来，他利用Bhattacharyya系数作为目标模型与候选目标之间的相似性度量标准，用meanshift算法来搜索最优候选目标，获得了很好的跟踪效果。此后，有更多的研究者投入到了此项研究之中[8~16]。文献[4]中给出的meanshift算法采用核直方图作为图像特征的描述方式，没有考虑图像的空间信息。为了克服特征信息不足造成偏差缺点，需要寻找一种可行的图像空间信息和颜色信息的综合表达方法，很多文献在这方面做了大量工作[8~10]。文献[8]提出一种空域特征空间中的相似性度量方法，允许meanshift算法跟踪更一般的运动目标；文献[9]提出了一个鲁棒的、实时的高斯圆柱形颜色模型，通过meanshift实现目标跟踪以抗不规则光照变化；文献[10]在颜色矩方图中引入旋转方向参数，采用5-degreesoffreedom(DOF)的颜色矩方图，可以跟踪旋转的运动目标。另外，不同的图像特征描述方法适合于不同的场合或背景，因此根据场景来自适应选择特征描述方法是非常值得研究的内容，如文献[11]提出一种目标跟踪中适合于评价多特征的在线特征选择机制，自适应调整特征集以提高跟踪性能。其次，目标特征的构造、组合及更新需要根据实际情况来确定，在目标跟踪中引入机器学习方法是一种行之有效的方法。对场景进行一定时间的学习后确定相应特征和参数，可提高对周围环境的适应性，例如文献[12]对目标的颜色进行聚类分析，通过矩阵分解和正交变换建立一种新的颜色模型来提高meanshift跟踪的性能；文献[13]把跟踪问题看成是二分类问题，结合adaBoost和弱分类器构成一个强分类器，通过在线训练来提高meanshift跟踪对不同场景的适应性。最后，研究集中在窗口自动选取，如Comaniciu[14]和彭宁嵩[15]分别提出了针对meanshift算法的窗口自动选取方法。虽然对meanshift跟踪算法进行了大量研究，但是该算法仍然存在跟踪偏差或者完全跟不上目标的情况。基于meanshift的目标跟踪方法[3,4]通过对Bhattacharyya系数作Taylor近似展开获得mean国家自然科学基金(60234030,60773110),国家基础研究项目(A1420060159)作者简介：文志强(1973－),男,湖南湘乡人,博士研究生,主要研究领域为目标检测､目标跟踪.Email:[e-mail],联系地址:湖南长沙中南大学铁道校区研究生楼310号,邮编:410075.联系电话:[phone];蔡自兴(1938－),男,福建莆田人,教授,博士生导师,主要研究领域为人工智能,进化计算,智能控制,移动机器人协作与导航等.shift的迭代公式，当跟踪目标的位置在两帧图像之间变化不大时，这种Taylor近似展开可以获得好的跟踪效果，但是当目标快速运动或突然转向时，这种系数近似的误差就较大，应用meanshift算法计算所得到的局部最优位置和应用原始的Bhattacharyya系数穷举搜索得到的位置之间存在误差。为了克服这种误差，本文对由于Bhattacharyya系数的Taylor近似公式表示所引起的误差进行了分析和研究，并在此基础上推导出一种降低误差方法。与原始的meanshift方法不同的是，该方法仅仅更改了权值的计算方法，不会增加算法的时间复杂度。提出的方法适合于目标突然改变方向或快速运动的情形。本文的安排如下：第1节是全文的引言；第2节介绍基于meanshift的目标跟踪方法；第3节对Bhattacharyya系数误差进行了分析；第4节提出目标跟踪方法；第5节为实验结果及分析；第6节是全文的结束语。2基于meanshift的目标跟踪方法2.1目标模型视频目标跟踪是meanshift算法应用的一个重要方面，大多文献沿用Comaniciu[3,4]的方法，采用Bhattacharyya系数作为相似性度量标准，使用meanshift算法来获取目标位置。基于mean-shift的跟踪算法将颜色核直方图作为目标特征的描述，假定目标模型和候选目标特征分别表示为：muuq,...,1}{q和muup,...,1)}({)(yyp，其中y是候选目标区域的中心位置，且11muuq，11muup，m为特征值bin的个数。目标模型与候选目标的相似性采用Bhattacharyya系数来衡量，即]),([)(qypy。为了得到一个相对于空间位置y平滑的相似函数，目标模型的特征分布表示为：])([)||(||*12*ubkCqiniiuxx，其中δ(•)为Kroneckerdelta函数，nii,...,1*}{x是归一化的目标模型像素位置，归一化后目标模型中心像素的位置为0，2:{1,,}bRm为像素点到像素特征的映射，C是归一化常数。相应的候选目标的特征分布为：])([)(*12ubhkCpiniihuhxxy，其中Ch是归一化常数，nh为候选目标区域中的像素总数，这里k(·)称为核函数，h为带宽。2.2基于Bhattacharyya系数的目标跟踪相似函数定义了目标和候选目标的距离，为了提供各种目标的比较，距离应有一个度量函数。定义两个离散分布之间的距离如下：]),([1)(qypyd（1）式中，muuuqp1)(]),([yqyp为q和p之间的Bhattacharyya系数。最小化（1）式相当于最大化Bhattacharyya系数]),([qyp。在)(0yup处使用Taylor展开式，得到]),([qyp的线性近似式如下：muuuumuuuappropqpqp1010)()(21)(21]),([yyyqyp（2）当候选目标muup...1)}({y从初始值不发生急剧变化时，上述近似成立。假设0)(0yup，对于所有的mu...1成立，可得hniiihmuuuapprohkwCqp12102)(21]),([xyyqyp（3）式中，])([)(10ubpqwimuuuixy。（3）式的第二部分最大化，可得meanshift算法的迭代公式如下：hhniiiniiiihgwhgw1201201xyxyxy（4）式中，g(x)=-k’(x)。首先初始化y0，计算wi，并重复(4)式的计算，直到||yi+1-yi||ε或大于预定的最大迭代次数，ε为预先设定的大于0的正数，得到的最终位置即为目标所在的位置。在目标跟踪时，目标模型必须进行自适应更改，以适应光照、环境的变化，如采用Kalman滤波更新目标模型[16]。3系数误差分析（2）式虽然对运动目标不发生急剧变化的情形不会产生很大影响，但对于急剧变化的情形，（2）的近似表示会造成很大的偏差。为了对Taylor近似表示造成的误差进行研究，给出下面两个定理。定理1：如果Bhattacharyya系数用（2）式近似表示，设系数误差为]),([]),([qypqypappro，则0，当且仅当y=y0时等号成立。证明在)(0yup处根据Taylor展开式，并作一些转换可得(5)式muuuuuuumuuupppppqqp100010)()()()()(21)(]),([yyyyyyqyp（5）其中10。（2）引起误差的原因是省略)()(0yyuupp项。设)()(0yyuuupp，易知11u，因此muuuuuuumuuuuuuuupppqpqpq1000100)()(1)(21)()(21yyyyy（6）在（2）式中系数误差分下列三种情况讨论：1)0u时，则0；2)0u时，则0；3)0u时，则0；只有当y=y0时，0u成立。□下面利用图形来进一步说明上述结论。设uuuuuuupppq)()(1)()(000yyy，假设2.0)(0uuqpy，分别取不同的值，得到θu—φ(θu)曲线如图1所示，由图1可见]1,1[u，0)(u。所以0)(1muu。由定理1知，Bhattacharyya系数的Taylor近似表示使得系数的值偏大。定理2：设n为每次meanshift迭代时的系数误差，如果迭代次数n时，则0limnn证明设第n次迭代时，对于（6）右边的第u项，分两种情况讨论1）当0u时，uuuuuuuuuuuuppqpppq)()()()(1)(00000yyyyy-10110.50图1θu—φ(θu)曲线,其中1,2,3,4代表δ=0.02,0.05,0.1,0.15θuφ(θu)2）当0u时，uuuuuuuuuuuuppqpppq)()()()(1)(00000yyyyy所以muuuuuuunppq100)()(210yy0)()(lim21)()(21lim1000100muuuuuuumuuuuuuunppqppquyyyy故0limnn□从定理2可得出结论：从理论上看，Bhattacharyya系数用（2）式近似表示，利用meanshift来实现跟踪，这种方法并不影响跟踪的效果。但问题是在利用meanshift进行迭代优化时，迭代结束的条件是||y-y0||ε或者迭代次数小于预先设定的次数，很难达到θu0的情形，因而导致目标跟踪误差，特别是初始目标位置离收敛位置比较远时，误差更大。这就是（2）式不适合于运动目标发生急剧变化情形的原因，如图2所示，在乒乓球下落较快时，跟踪不上目标。图2meanshift目标跟踪的实验结果4目标跟踪方法基于第3节的分析，为了适合于运动目标发生急剧变化的情形，本节提出一种改进目标跟踪方法，以消除系数误差。4.1改进的跟踪方法根据上节分析，将Bhattacharyya系数优化问题转化为求解约束优化问题：]),([maxqypappro