基于MeanShift和块匹配的目标跟踪技术

基于MeanShift和块匹配的目标跟踪技术【摘要】Meanshift算法作为一种非参密度估计算法,目前已被广泛应用于视频运动目标的跟踪。该算法具有运算效率快,对目标变形、旋转不敏感,在部分遮挡的情况下有一定鲁棒性等特点。但该算法跟踪低分辨率视频目标时只能跟踪到部分轮廓。针对此问题，提出了利用MeanShift和块匹配相结合的方法对目标进行跟踪。该算法在确定主要目标模型与次要目标模型后，首先利用MeanShift算法跟踪次要目标模型在当前帧的位置，而后利用块匹配的方法跟踪主要目标模型在次要目标模型范围内的确切位置。实验结果表明，该算法对于低分辨率视频目标跟踪的精确度比原算法有很大提高。【关键词】MeanShift;块匹配；相关系数；1引言Meanshift算法是一种非参数密度估计算法[1],由Fukunaga于1975年首先提出。其作为一种高效的模式匹配算法,已被成功地应用于实时性要求较高的目标跟踪系统中[2]。DormComaniciu首先将Meanshift算法应用于图像滤波、分割与目标跟踪等领域[3-4]。Bradski提出以颜色直方图为目标模式的Meanshift目标跟踪算法[5]。该算法先利用颜色直方图得到每帧图像的颜色投影图,然后自适应调整搜索窗口的位置和大小,并通过不断收敛将得到的最优中心位置作为目标的中心。另外,Nummiaro等人采用粒子滤波结合Meanshift的方法进行目标跟踪,但是粒子滤波器本身的复杂计算降低了跟踪的实时性[6]。与其他的运动目标跟踪算法相比较,Meanshift算法具有如下特点:1)计算量不大,可以满足实时跟踪要求;2)对运动目标变形、旋转、背景变化不敏感;3)对于部分遮挡情况下的目标跟踪具有一定的鲁棒性;4)Meanshift算法作为一个无参估计算法,很容易作为一个模块与其他算法集成。Meanshift算法也存在以下一些不足:1)缺乏必要的模板更新算法,由于跟踪过程中窗宽的大小保持不变,因此当目标有尺度变化时,可能跟踪失败;2)直方图是一种对目标特征进行描述较弱的方法,当背景和目标的颜色分布较相似时,算法效果欠佳;3)当场景中目标的运动速度很快时,或者当视频图像帧率较低，帧间时间间隔较长时,目标区域在相邻两帧间会出现没有重叠区域的情况,此时目标往往收敛于背景中与目标颜色分布比较相似的物体,而不是场景中的目标。本文针对MeanShift算法在进行低分辨率视频跟踪所表现出来的不足，提出了一种改进算法。该算法在确定主要目标模型与次要目标模型后，首先利用MeanShift算法跟踪次要目标模型在当前帧的位置，而后利用块匹配的方法跟踪主要目标模型在次要目标模型范围内的确切位置，此算法对于低分辨率视频目标跟踪的精确度比原算法有很大提高。2MeanShift算法概述Meanshift算法是一种非参数概率密度估计算法,可以通过迭代快速的收敛于概率密度函数的局部极大值。算法的跟踪过程就是不断寻找概率密度局部最大值的过程,其步骤如下:2.1目标模型的描述关于目标模型的描述,首先是目标的初始化,即在起始帧图像中确定被跟踪的目标区域,其可以通过手工选择的方式来确定目标区域,也可以根据运动检测的结果自动选取目标区域。如果目标区域的中心为x0,那么目标模型可以描述为在目标区域上的所有特征值的概率值,该特征值一般指RGB颜色特征或其他特征。用目标模型的特征值u=1,…,m估计的概率密度为201ˆ()[()](1)niuiixxqCkbxuh其中，K(x)为核函数的轮廓函数,由于目标模型中心附近的像素比外围像素更可靠,因此K(x)对于中心像素给一个大的权值,而对于远离中心的像素则给一个小的权值。b(xi)表示像素xi属于哪种特征值，δ(x)是Delta函数,δ[b(xi)-u]的作用是用于判断目标区域中任一像素xi的颜色值是否等于第u个特征值，若等于，则颜色值为1,否则为0。C是一个标准化的常量系数，使得所有特征值的概率和为1。2.2候选模型的描述运动目标在第2帧及以后的每一帧中，可能包含目标的区域称为候选区域,其中心坐标为y，候选模型的像素特征值u=1,…,m的概率密度为201ˆ()()[()](2)niuhiiyxpyCkbxuh其中,h为带宽参数，MeanShift的跟踪窗口大小依赖于带宽h，Ch为归一化常数,该常数为121hnihiyxCKh2.3相似性函数相似性函数用于描述目标模型和候选目标之间的相似程度,可使用Bhattacharyya系数作为相似性函数,即1ˆˆˆˆˆ()((),)()muuuypyqpyq(3)其值在0~1之间。ˆ()y的值越大,表示两个模型越相似。2.4目标定位为使ˆ()y最大,应当先将当前帧的目标中心定位为前一帧中目标中心的位置y0,然后从这一点开始寻找最优匹配的目标,其中心为y1。定位时,先在0ˆ()y处对函数(式(3))进行泰勒展开,相似性函数可近似为20111ˆˆˆˆ[()]()22mnhiuuiuiCyxpyqpyqwkh(4)其中，10ˆ[()]ˆ()muiiuuqwbxupy(5)通过对相似性函数求最大值，可以推导出MeanShift向量01,10001ˆ()()ˆ()niiiinhGiiiyxxwghmyyyyyxwgh(6)MeanShift算法反复迭代，最后得到在当前帧目标的最优位置y。3块匹配3.1块匹配准则本文采用基于互相关系数的块匹配准则。假设两幅进行匹配计算的图像中的小图像为g,大小为m×n,大图像为S，大小为M×N。用表示Sx,y中以(x，y)为左上角点与g大小相同的子块，利用相关系数公式计算小图像和大图像中每一个和小图像尺寸相同的块之间的相关系数，得到相关系数ρ(x,y)，找出使大图像中与小图像的相关系数最大的块。如图3所示，尺寸较小的框即为块匹配在尺寸较大框范围内所匹配出的最佳位置。(,)xy的定义为,,(,)(,)=xyxySgxyDD(7)式中:,(,)xySg是,xyS和g的协方差；,xyD为,xyS的方差,2x,,,111(,)mnyxyxyijDSijSmn；D为g的方差,2111(,)mnijDgijgmn；,xyS和g分别表示图像,xyS和g的灰度均值。4基于MeanShift和块匹配的目标跟踪4.1算法流程图图1算法流程图4.2改进算法首先读取视频，而后确定起始帧，在起始帧范围内选取主要目标模型与次要目标模型。具体步骤如下：①确定首要目标模型与次要目标模型读取视频，在视频的第一帧手动选取感兴趣的目标作为首要目标模型，在该首要目标模型周围扩展n个像素作为次要模型。②用MeanShift算法求出次要目标模型所处位置基于次要目标模型的RGB颜色分布特征，利用MeanShift算法根据前一帧的信息跟踪次要目标模型，找出该次要目标模型在当前帧的最佳位置。③采用块匹配得出首要目标模型的位置。使用MeanShift算法反复迭代得出次要目标模型在当前帧的最佳位置y。而后主要目标模型在次要目标模型的范围内利用基于互相关系数的块匹配准则，得到视频获得起始帧确立首要目标模型与次要目标模型得到下一帧利用MeanShift得到次要目标在当前帧的位置在次要目标模型的范围内使用块匹配得到主要目标模型位置视频是否结束是否跟踪结束从左上角逐点求取次要目标中与主要目标模型相同大小的块的相关系数，找出次要目标模型范围内与主要目标模型最相似的块。5.实验结果及分析我们选取两个视频进行试验，读取视频后，确定起始帧，改进算法选取主要目标模型与次要目标模型进行跟踪。在第一个视频中，选取对人脸进行跟踪，选取人脸为主要目标模型，整个人为次要目标模型。图2、3为视频在起始帧及30帧之后跟踪的结果，改进算法能够精确的跟踪到人脸，而原算法处于即将跟丢的状态。具体结果如下图所示。图2.1改进算法跟踪结果图2.2原算法跟踪结果图3.1改进算法跟踪结果图3.2原算法跟踪结果从上图中的实验结果可以看出，本文所提出的基于MeanShift和块匹配的目标跟踪技术比起原算法在精确度上有了非常大的提高。6.结论本文首先确定首要目标模型与次要目标模型，然后采用MeanShift算法求出次要目标模型在当前帧所处位置。得出结果后，再采用块匹配在次要目标模型范围内得出首要目标模型的位置。实验结果表明，本文方法极大的提高了MeanShift算法的精度，实现了对某些MeanShift所不能跟踪到的情形的精确跟踪。参考文献[1]FukunagaK,HostetlerL.Theestimationofthegradientofadensityfunction,withapplicationsinpatternrecognition[J].IEEETransactionsonInformationTheory,1975,21(1):32.[2]ChengY.Meanshift,modeseeking,andclustering[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,1995,17(8):790.[3]ComaniciuD,MeerP.Meanshiftanalysisandapplication[C]ProceedingsoftheSeventhIEEEInternationalConferenceonComputerVision.Kerkyra,Greece,1999,2:1197-1203.[4]ComaniciuD,RameshV,MeerP.Real-timeTrackingofNon-rigidObjectsUsingMeanShift[C]ProceedingsoftheIEEEConferenceonComputerVisionandPatternRecognition.LosAlamitos,CA,USA:IEEEPress,2000:142-149.[5]BradskiGR.ComputerVisionFaceTrackingforUseinPerceptualUserInterface.[6]NummiaroKatja,Koller-MeierEsther,VanGoolLuc.Colorfeaturesfortrackingnon-rigidobjects[J].ChineseJournalofAutomation,SpecialIssueonVisualSurveillance,2003,29(3):345-355.ObjectTrackingTechnologybasedonMeanShiftandBlockMatchingAbstract:Meanshiftalgorithmasanon-parametricdensityestimationalgorithmhasbeenwidelyusedinthevideomovingtargettracking.Thealgorithmisnotonlyhashighcomputationalefficiencybutalsonotsensitiveforthetargetdeformationandrotation.However,thisalgorithmcanonlypartoftheprofilewiththeconditionoflow-resolutionvideo.Forthisproblem,proposethemethodcombiningMeanShiftandblock-matchingmethodforthetracking.Afterthedetermineofmainobjectmodelandsecondarymodel,thenweusethemeanshiftalgorithmtotrackthepositionof