基于均值漂移的快速模板匹配算法

段亮弟, 宋平, 陈众, 赵鹏

(63870部队, 陕西 华阴 714200)

目标跟踪是计算机视觉的一个重要分支,其在军事侦察、精确制导、火力打击、战场评估以及安防监控等诸多方面均有广泛的应用前景。目标的不定向运动改变了目标和场景的外观模式、非刚性目标结构,目标间及目标与场景间的遮挡、摄像机的运动等情况使目标跟踪任务变得更加困难。

跟踪单目标最常用的方法是模板匹配方法,它一直以算法简单、易于实现等优点被广泛应用于光电吊舱的目标跟踪器中。但模板匹配算法是一种穷尽搜索,当目标运动过快时,需要加大搜索波门,模板匹配的计算量会成倍增加,对工程应用来说实时性难以保证;另外,模板匹配算法对目标形变敏感,当目标发生旋转、变形等姿态变化时,目标特征受到很大影响,会发生中心点漂移现象,导致跟踪不准确。为此,可以采用对旋转、变形不敏感的均值漂移算法进行目标跟踪。Comaniciu等提出的均值漂移算法是一种非参数估计方法,采用颜色特征和核函数直方图进行建模和匹配,具有特征稳定、计算速度快和跟踪效果好等诸多优势,但是以颜色为特征的均值漂移算法在光照、颜色变化及有相似颜色干扰时,跟踪结果往往会出现偏差,甚至丢失目标。

为了适应环境变化,提高跟踪算法的鲁棒性,本文联合颜色和边缘2个特征,在模板匹配算法之前加入均值漂移算法来预测目标位置,缩小整幅图像上目标检测的搜索范围,满足目标跟踪的实时性;最后采用快速模板匹配算法寻找最佳匹配位置,以及利用模板匹配结果自适应地更新目标模板。仿真实验结果表明,算法能够随着目标位置的变化自动调整目标模板,进行稳定和实时的跟踪,当目标被物体遮挡时仍能有效地跟踪目标。

1 均值漂移预测算法

均值漂移[1]算法是一种基于核密度直方图的非参数估计方法,漂移向量(迭代向量)即密度梯度上升方向。算法通过确定目标模型,再选择候选模型计算其与目标模型的相似度以及下一次的迭代坐标,并在最大迭代次数内进行迭代运算,直到目标模型和候选目标模型的相似度满足一定条件时(大于设定阈值)停止迭代。算法经过不断的迭代运算得到的坐标点即是算法最终确定的当前目标中心点。

利用传统的均值漂移算法,在建立目标模型区域的加权直方图时,被跟踪目标图像像素与背景图像像素都会对目标直方图的分布产生影响。当目标模型区域中包含的背景区域像素较少时,传统的均值漂移算法可以得到较好的跟踪效果,但在目标模型区域中包含背景图像像素较多或者背景不断变化的情况下,容易造成候选区域直方图与目标模型区域直方图的最佳匹配位置有所偏差,尤其对于快速运动目标的跟踪,容易导致目标丢失[2-4]。

为减少背景像素对目标预测产生的影响,本文对目标模型采用背景加权的方法[5]。如果某特征值在背景模型直方图中所占权值较大,在建立目标模型时对此特征值赋予较小权重,相反如果某特征值在背景直方图中所占权值较小,则在建立目标模型时对此特征值赋予较大权重。利用此方法可以有效抑制背景像素对目标跟踪产生的影响,实现对均值漂移预测算法准确性的有效改进,具体实现方法如下所示。

1.1 计算背景区域直方图

首先计算目标模型以外一定区域的背景模型直方图,如(1)式所示

(1)

(2)

1.2 计算背景加权系数

通过ou可以计算得到背景加权系数λu(u=1,…,m),如(3)式所示

(3)

式中,omin是ou中最小的非零值。

1.3 计算背景加权后的目标模型和候选目标模型

定义被跟踪目标为“目标模型”,在得到背景加权系数vu后,即可计算背景加权后的目标模型。首先需要对目标模型进行描述,确定被跟踪目标模型的特征空间并计算该区域的加权直方图,通过n级核加权直方图来表示目标模型的特征分布,如(4)式所示

(4)

(5)

目标模型建立后,运动目标在第2帧和以后每帧中可能包含目标的区域称为候选目标区域。令yi(i=1,…,n)表示像素在候选目标区域中的位置,其中心位置设为y0,与(4)式相似,以y0为中心的候选目标模型可表示成pu(y),如(6)式所示

(6)

1.4 相似性度量

在利用均值漂移算法预测运动目标位置时,需要相似性函数度量目标模型和候选模型的匹配程度,即pu(y)与qu的相似程度。本文使用Bhattacharyya系数作为相似性函数,如(7)式所示

(7)

Bhattacharyya系数的值在0～1之间。ρ′(y)越大,表示候选目标与模板目标越匹配,那么对应的中心y越有可能是被跟踪目标在当前帧图像中的位置,目标预测的过程即是寻找最优的y,使得Bhattacharyya系数最大。

1.5 预测位置定位

均值漂移算法目标预测的过程是利用计算得到的均值向量反复迭代,不断更新核函数窗口的中心位置,直到满足判断条件,算法主要分为以下几个步骤:

1) 计算当前窗口内各像素点的权重

(8)

2) 计算候选目标的下一个新位置

(9)

式中,g(x)=-k′(x)。

3) 判断是否需要继续计算

首先判断是否‖yi-y0‖<ε,如不等式成立,则停止计算,得到被预测目标的位置信息,否则将yi替y0返回到目标预测定位过程的第一步,继续寻找满足判断条件的候选目标位置。由于光电跟踪系统对实时性具有较高的要求,所以实际应用中设定迭代次数最多是15次。

2 快速模板匹配算法

模板匹配是一种原理简单的跟踪算法,我们要把跟踪的目标保存好,称为目标模板,然后在每一帧到来时,按照某个指定的判定准则将目标模板和搜索区域内的每一个目标模板规模大小的图像作相似性比较,相似性最大的位置视为模板在搜索窗内的正确匹配点。

传统的模板匹配算法虽然原理简单,但是计算量大,从跟踪器工程应用的实时性考虑,本文采用一种改进的快速模板匹配机制。在模板匹配阶段,结合上一节提到的均值漂移算法预测的目标位置生成搜索窗口的边缘图像,将目标的边缘模板与搜索窗口的边缘图像进行由粗到精的快速匹配,并找出最大匹配系数所在的位置对目标进行定位,再由模板匹配的输出结果控制更新过程以更新目标的边缘模板,最终完成对目标的快速稳定跟踪。

如果只使用边缘特征本身在搜索波门内进行快速匹配跟踪,在目标运动速度快的情况下需要很大的搜索窗,从而加大了计算量,并容易受局部极点干扰,若首先使用均值漂移方法预测目标位置,然后在预测位置区域很小范围内使用边缘特征进行快速模板匹配,可有效提高模板匹配的效率。

3 基于均值漂移预测的快速模板匹配目标跟踪方案设计

3.1 算法流程

本文联合颜色和边缘2个特征,结合2种跟踪算法的优缺点,形成一种组合的跟踪策略,在模板匹配算法之前加入均值漂移算法来预测目标位置。假设在第(k-1)帧跟踪得到的目标位置为(x(k-1),y(k-1)),且经过更新后的目标模板为Tk,那么在第k帧图像输入后,算法需要在该帧中对目标进行跟踪,具体步骤如下:

1) 人工指示目标的方式得到目标初始位置,并根据实际场景设定转换阈值ε。

2) 根据初始位置建立初始目标核直方图模型、初始背景核直方图模型和初始搜索窗口,获取目标的边缘模板T0。

3) 第2帧结合第(k-1)帧跟踪得到的目标位置,利用均值漂移算法预测当前帧图像中目标的可能位置,并以预测位置中心定义搜索图像S(k)。

4) 开始快速模板匹配,模板Tk在搜索图像S(k)的边缘图像上平移，将模板Tk与待搜索子图进行由粗到精的匹配,计算最大互相关系数R1,如果匹配度R1大于阈值ε,则将匹配的结果作为第k帧图像的跟踪结果,否则,以均值漂移算法预测的目标位置作为第k帧图像的跟踪结果。

5) 根据快速模板匹配的输出结果对目标模板和目标核直方图模型以及背景核直方图模型进行更新,至此,第k帧的跟踪结束。

整个算法流程图见图1。

3.2 算法实现

在实际跟踪系统中,由于对图像处理的实时性要求很高,因此均值漂移预测可以在FPGA中实现,当FPGA预测完当前帧的目标位置后,通过中断触发的方式把预测目标位置的坐标值传送给DSP,由DSP完成快速模板匹配。实现,当FPGA预测完当前帧的目标位置后,通过中断触发的方式把预测目标位置的坐标值传送给DSP,由DSP完成快速模板匹配。

图1 基于均值漂移预测的快速模板匹配算法流程图

4 实验结果与分析

为验证本文方法的效果,需要进行目标跟踪实验,测试3种跟踪算法的跟踪效果。采用VS2010软件编写了实验程序,为了验证均值漂移算法对颜色特征的鲁棒性,本文采用2组彩色图片序列来测试3种跟踪算法的效果,如图2所示。图3是均值漂移算法跟踪结果,图4是快速模板匹配算法跟踪结果,图5是基于均值漂移预测的快速模板匹配算法跟踪结果。

图2 输入图像

图4 快速模板匹配算法跟踪结果

图5 基于均值漂移预测的快速模板匹配算法跟踪结果

从上图可以看出,对于basketball图像序列,从图3、图5可直观看出,均值漂移算法和基于均值漂移预测的快速模板匹配算法跟踪效果较好,在每帧图像内都能稳定跟踪到目标人物(绿色球衣运动员),特别是在遇到遮挡时(2位穿白色球衣运动员)依然能保持稳定跟踪,抗遮挡能力较好,而从图4可看出,利用快速模板匹配算法跟踪时在第11帧图像中由于目标人物(绿色球衣运动员)受到2位白色球衣运动员的干扰和遮挡,在第15帧出现错误跟踪现象,一直到第70帧始终处于目标丢失状态,不能重新捕获到目标,故可知快速模板匹配算法的抗遮挡能力较差;对于people图片序列,目标人物的大小和姿态一直在不断变化,背景图像也在缓慢变化,快速模板匹配算法在第177帧发生跟踪丢失现象,之后一直处于丢失状态,相比起来,均值漂移算法和基于均值漂移预测的快速模板匹配算法则有较好的表现,能稳定跟踪目标人物,说明均值漂移算法对目标的形状和姿态变化具有较好的鲁棒性。

表1是对这2组图片序列的跟踪效果统计,从该表可以看出,对于这2组图片序列,本文提出的基于均值漂移预测的快速模板匹配算法跟踪效果最好。在快速模板匹配算法之前加入均值漂移算法对目标位置进行预测,既能保证搜索波门的合理性和可预测性,又能避免在目标受到遮挡时因快速模板匹配算法的失效而导致跟踪丢失现象的发生,此时可将均值漂移算法预测的目标位置作为当前帧的跟踪结果,保证在下一帧图像到来时能稳定跟踪目标。

表1 3种跟踪算法跟踪效果比较

表2 3种跟踪算法平均运行时间比较 ms

表2是对3种跟踪算法在VS2010上的平均运行时间比较,从该表可以看出,在时间性能上,快速模板匹配算法耗时最多,均值漂移算法运行时间最短,改进算法虽然是前2种算法的组合,实时性却比快速模板匹配算法要好,因为改进算法增加了预测机制,搜索波门比快速模板匹配算法的搜索波门小,故改进算法满足实时性要求,后期可将均值漂移预测算法放在并行性较高的FPGA中去做,以缓解DSP的计算压力。

5 结 论

给出了均值漂移方法和快速模板匹配跟踪算法的原理,针对均值漂移和模板匹配算法各自的优缺点将两者很好地结合在一起,提出了一种基于颜色和边缘特征的目标跟踪算法。实验验证结果表明:所提算法在目标无遮挡时,采用均值漂移算法对目标位置进行预测以提供较可靠的搜索区域,继而通过模板匹配方法对目标进行快速定位和跟踪;在目标发生遮挡时使用均值漂移算法对目标在下一帧中的位置进行预测,能够对目标进行稳定跟踪。

与只使用单一颜色特征的均值漂移跟踪算法或单一边缘特征的快速模板匹配跟踪算法比较,本文算法综合了颜色特征对旋转、变形不敏感的优点和边缘特征对光照、颜色变化不敏感的优点。从直观跟踪效果和跟踪误差定量分析两方面可以看出,本文算法能够在光照变化以及目标发生旋转、变形条件下实现稳定跟踪,提高了模板匹配算法的鲁棒性。