基于自适应多模板匹配的目标跟踪

何华丽，唐普英，唐湘成，杨建熙，曾 军，黄自力，李 晶

(1.电子科技大学，四川 成都611731;2.西南技术物理研究所，四川 成都610041)

责任编辑:任健男

运动目标跟踪一直是视频处理领域的热点和难点之一，近年来发展很快，很多研究者都在不同的跟踪算法上取得了不错的研究成果。其中，比较热门的跟踪算法有相关跟踪、Mean Shift、Sift、光流法、粒子滤波等[1-4]。在智能化高速发展的今天，跟踪技术已经被广泛应用到了军事、视频监控等领域。解决目前跟踪技术的缺陷，追求更精准、更可靠的跟踪技术将会是研究人员的长期课题。

模板相关匹配又称模板匹配，一直以算法简单、易于实现等优点受到很多研究人员的青睐，模板匹配算法对于图像色度不敏感，在目标图像不出现大的形状和尺度变化的时候，可以进行良好的跟踪。而模板匹配算法最主要的缺点就是计算量大、对于遮挡和旋转敏感[5]，简单的模板匹配在跟踪的准确度上往往会随着时间降低，且模板匹配结果总是存在匹配模糊或多位置匹配、错误匹配等偶然误差，在这样的情况下，总是信任某个模板的匹配结果将会导致错误的跟踪结果，有很多学者提出了模板匹配跟踪的改进方法[6-9]，有些学者提出了多级模板匹配，以增加匹配结果的可信度。但由于实时性的要求，模板的级数和运算时间支出之间很难找到平衡。

本文提出了一种DSP和FPGA分工合作的系统方法。建立通信，由FPGA来代替DSP完成耗时计算部分。多级不同尺寸的模板和旋转模板的加入，使系统在目标发生旋转和膨胀时也能进行准确的跟踪。本文算法的特点就是，为了对抗目标尺寸变化和旋转，生成了各级旋转匹配模板，并在多级模板融合时做了合理处理，以求得跟踪结果的准确性，同时又保证了跟踪系统的实时性。

1 模板匹配原理

模板匹配的基本做法是把模板图像T和搜索区域S内的每一个T规模大小的图像作相似性比较，相似性最大的位置视为T在S内的正确匹配点。基本流程如下:

1)创建或直接获取模板图像，其中，模板图像包含兴趣对象，即待跟踪的目标;

2)设定一个相似性比较的方法和准则;

3)以T为大小的范围框在S内逐点移动，求取在每个坐标点处与模板的相似度结果;

4)从所有坐标点的结果中选出相似度最大的点作为目标匹配点。

假设，模板图像是一个W×H的矩形区域图像，搜索区域S是一个M×N的矩形。相似度以图像的绝对灰度值和(SAD)为度量标准。从S的第一个像素点开始，获取一个T大小的比较图像T'，计算T'和T的绝对差值和，逐点移动比较图像的位置，一共有可以获取比较图像的(M-W+1)×(N-H+1)个位置，计算每个点处的T’和T的绝对差值和。最终得到一个(M-W+1)×(N-H+1)大小的匹配结果。如图1所示，分别是6×4的模板在10×8的搜索区域内逐点移动，从坐标点(0，0)到(2，2)、最后到(4，4)的模板匹配过程示例图，最终可以得到5×5的相关数据数组。

图1 模板匹配示例图

其中，在搜索过程中，模板匹配需要一个相似度的度量。本算法中采用的是归一化去均值互相关系数NCC(Normalized mutual Correlation Coefficient)，传统的相关系数Cur计算如下

相关系数能够很好地表征模板和搜索区域内某点的相似度，但是对于光线亮度变化却很敏感。一旦图像的亮度发生变化，Cur的值会整体偏离实际相似度。为了克服这个缺点，本算法中采用了去均值处理，计算方法如式(2)所示

2 多级模板匹配算法介绍

2.1 多级模板介绍

在传统的模板匹配算法中，在搜索区域内完成一次完整的匹配得到一个匹配结果信息相关的三维相关曲面。理想的匹配结果中，相关曲面的峰值出现在理论上的最优匹配坐标处，峰值有且只有一个。实际应用中的匹配结果，相关曲面不总是理想的单峰，相关曲面的状态可以大致划分为平坦、单峰、多峰、边缘峰四种情况。针对相关曲面的多种状态，引入多级模板，以降低单模板匹配结果的偶然误差。图2是一个三级模板匹配实验中的三级模板图像。根据实验验证，在本算法中，三级模板已经能够得到良好的跟踪结果。

模板匹配算法的具体步骤是:取模板Template，得到搜索区域SearchWindow，逐点计算出模板在搜索区域内各个坐标位置的相似度，得到相关曲面，找出最优匹配点坐标。在多模板匹配算法中，在得到每级模板的相关曲面结果以后，加入了相关曲面融合的步骤。

图2 三级模板示例图

每个W×H的模板在M×N的区域内进行相关匹配后都会得到一个(M-W+1)×(N-H+1)的相关曲面。对相关曲面进行处理，得到各曲面状态以及尖锐度情况，根据曲面状态判定可信度，根据尖锐度计算各级曲面在融合过程的权值，再由各级曲面加权融合得到置信曲面，最终由置信曲面得到最优匹配点。

2.2 抗旋转多级模板匹配

多级模板匹配算法中，各级模板各不相同，具体所需级数以及每一级模板大小的选取都根据视频图像的大小和目标的预测和训练尺寸所得。除了直观的模板外，本算法中，为了适应跟踪过程中目标发生旋转的情况，在待匹配的模板库里增加了旋转后的模板。

在进行每一帧的模板匹配时，旋转前的模板和旋转后的模板都要和当前目标进行匹配。由于帧与帧之间物体运动的有限性，在目标缓慢旋转的情况下，帧间旋转±3°可以有效地跟踪[10]，本算法为了克服快速旋转，帧间角度差确定为10°。其中，旋转模板同原始模板得到旋转模板的基本方法如下

式中:old_x和old_y是原始模板中像素点的位置坐标，center_x和center_y是旋转后模板图像的中点，(i，j)是旋转后模板数据数组的位置。图3是一组原始模板和顺时针、逆时针各旋转30°后的模板示例图。

图3 模板旋转前后对比图

3 模板实时更新策略

每一场图像的目标匹配过程中，需要由FPGA完成一共9次完整的相关曲面计算。在进行相关曲面融合之前，必须要作两次判断和选择:

1)判断目标是否旋转，确定将进行融合的多级模板来源;

2)判断多级模板的相关曲面置信度，判断每级曲面是否加入融合，计算加入融合的曲面权值，根据选择和权值进行曲面融合，得到置信曲面。

模板的更新是为了让模板信息更接近目标当前的信息，越接近真实目标的模板越能得到正确的匹配结果。图4是各级相关曲面的旋转更新流程图，假设三级原始模板为T_1，T_2和T_3，由T_1顺时针旋转5°后得到的模板为T_1_CW，由T_1逆时针旋转5°后得到的模板为T_1_CCW;由T_2顺时针旋转5°后得到的模板为T_2_CW，由T_2逆时针旋转5°后得到的模板为T_2_CCW;由T_3th顺时针旋转5°后得到的模板为T_3_CW，由T_3逆时针旋转5°后得到的模板为T_3_CCW。

图4 旋转模板更新流程图

在跟踪过程中，随着目标自身的变化和摄像头的位置、角度等变化，实际应用中的跟踪目标不可能一直保持为最初获取的模板。如果用一成不变的模板进行跟踪，匹配度会不断下降，最后造成目标的丢失或误匹配。所以，很多学者提出了模板实时更新。其中，在本算法中，模板的实时更新主要分为两方面:

1)在判断目标是否旋转的结果中，如果目标旋转了，将各级模板更新成为旋转后的模板，作为之后搜索目标的源模板。

2)在目标的每场跟踪过程中，如果本场跟踪有效，以一定的系数将当前目标信息叠加到模板信息中，以此获得继承了原始模板信息、又不断靠近当前目标真实信息的模板。图5是更新模板的基本流程。

图5 模板的实时更新流程图

4 DSP和FPGA的系统介绍

由于DSP的优势在算法的实现和流程的控制上，而FPGA的优势在并行运算上，于是本算法中建立了双方的通信，耗时的计算部分由FPGA来计算和完成，其他的由DSP完成。图6是DSP和FPGA的通信连接示意图。

在模板匹配算法中，最耗时的计算部分是SAD的计算。在三级抗旋转跟踪算法中，每一次搜索都需要进行共9个模板的SAD计算，其中包括三级原始模板以及6个由三级原始模板衍生出的顺时针、逆时针旋转后的模板。要在20 ms内完成这么多的运算，对DSP来说是个难题。于是，考虑建立起DSP和FPGA之间的通信，考虑到是图像信息，设立了PPI为通信通道。

图6 DSP和FPGA的通信图

并行外部接口PPI是半双工形式，最大可进行16位数据的传输。它有1个时钟引脚、3个帧同步以及4个专用数据引脚。DSP通过PPI的几个寄存器来设置其工作方式。在DSP和FPGA的通信系统中，时钟和帧同步由FPGA给出，直接连接到引脚信号。模板和待匹配图像由DSP自PPI0口传输给FPGA，FPGA进行匹配运算后所得的相关曲面结果由PPI1口送回DSP。

DSP接收图像和曲面信息时，受时钟和同步信号的控制，这些信号和图像数据均由FPGA给出，实验中，DSP采用了两个外部帧同步的PPI通用模式。图7是时序示意图，其中，DSP_PPI1SYN[2]是场同步信号VS，DSP_PPI1SYN[1]是行同步信号HS，DSP_PPI1CLK是时钟信号，DSP_PPI1数据信号。

图7 SignalTap时序图(截图)

5 系统性能分析

首先，DSP和FPGA的通信跟踪系统是为了解决运算量大、耗时长的问题。FPGA在计算SAD上比起DSP具有明显的优势，表1是两者的计算时间对比图。

表1 FPGA和DSP计算SAD值的时间对比

由于抗旋转模板的加入，在目标旋转以及稳定膨胀的情况下，系统仍然能够进行良好的跟踪，图8是单独在DSP上完成的两级模板匹配，图9是DSP和FPGA平台上加入旋转模板后的三级模板跟踪效果演示图。

图8 二级模板跟踪效果演示图

图9 抗旋转三级模板跟踪效果演示图

6 小结

本文采用了DSP和FPGA的通信联调跟踪系统来完成多级抗旋转模板匹配的跟踪算法，有效地提高了运动目标在发生旋转时的跟踪准确度，效果良好并稳定。同时，系统利用了DSP和FPGA各自的优势，解决了DSP运算量大耗时长的问题，在保证准确性的同时满足了实际应用中的实时性要求。经大量实验测试，该系统可以进行良好的目标跟踪，并对于目标的尺寸和角度变化具有良好的适应能力。

[1]LATECKI L J，MIEZIANKO R.Object tracking with dynamic template update and occlusion detection[C]//Proc.IEEE 18th International Conference on Pattern Recognition.Hong Kong，China:IEEE Press，2006:188-193.

[2]AZGHANI M，AGHAGOLZADEH A，GHAEMI S，et al.Intelligent modified mean shift tracking using genetic algorithm[C]//Proc.2010 5th International Symposium on Telecommunications(IST).[S.l.]:IEEE Press，2010:806-811.

[3]CAO Yueyun，XU Jianghu，LI Ke.Object tracking integrating template matching and mean shift algorithm[C]//Proc.2011 International Conference on Multimedia Technology(ICMT).Hangzhou:IEEE Press，2011:3583-3586.

[4]HU W C.Adaptive template block-based block matching for object tracking[J].Intelligent Systems Design and Applications，2008(26):61-63.

[5]张彦梅，宋扬.模板匹配方法在高速目标跟踪中的应用[J].北京理工大学学报，2006，26(11):1026-1029.

[6]陈明洁.智能视频监控系统目标检测和跟踪技术分析[J].电视技术，2008，32(10):85-91.

[7]王成儒，李翠君.基于视频流的运动人体检测和跟踪的研究实现[J].电视技术，2012，36(15):124-127.

[8]王徐华，樊晓光，徐显亮.基于TMS320DM642的视频图像处理系统设计与实现[J].电视技术，2009，33(10):28-31.

[9]贾慧星，章毓晋.智能视频监控中基于机器学习的自动人数统计[J].电视技术，2009，33(4):78-81.

[10]曾晶，黄自力，王雪梅，等.基于相关匹配算法的目标角度和尺度检测研究[J].激光与红外，2010，40(3):319-324.