基于FPGA实现多级模板并行匹配

薛顺瑞，张 文，高 原，刘 怡，李 游

(1.电子科技大学，四川 成都 611731;2.内江师范学院，四川 内江 641112;3.西南技术物理研究所，四川 成都 610041;4.云南大学，云南 昆明 650091)

责任编辑:时 雯

1 图像匹配技术现状分析

在大规模战争中，具有高精确性的制导武器对战争的结局起关键性作用，图像匹配技术作为精确制导图像处理器的关键技术具有重要的理论意义和实用价值。对于精确制导武器，匹配性能决定着制导武器的精确度［1］。通常情况下，匹配性能是随着模板面积的增加而提高，但是实际情况存在着几何失真的干扰，几何失真的强度会随着模板面积的增加而增加，从而导致匹配性能下降，因而单纯提高模板面积来提高匹配性能，在实际情况下是不可行的。由于单模板相关系数是包括模板图和搜索图每个像素点的函数，当搜索图受到某种干扰导致搜索图的某一部分发生变化，相关系数会有很大的影响。解决此问题，需要将模板图进行划分为多个模块，采用多个模板最优相关系数子集方法［2］。

多个模板相关算法是为了解决几何失真带来的匹配精度下降的问题，将大模板划分为多个子模板，然后分别将每个子模板与实时图像进行相关匹配，由于子模板的像素点少，所以当部分像素发生变化时，主要影响的是相对的子模板，而对其他子模板影响较小，将每个子模板的相关系数矩阵进行综合。这样综合之后匹配性能与大模板匹配性能相似，也减少了几何失真所导致的匹配性能下降［3］。

在基于灰度图像，本文采用的相关匹配算法是差的绝对值和相关法(Sum of Absolute Difference，SAD)［4］。由于SAD算法具有计算简单、重复性大等特点，因而可以并行处理多个像素点，使得计算时间降低。如果采用DSP计算多个模板的SAD，由于DSP是逐点计算，所以实时性往往不能达到要求。但是FPGA具有并行处理多个进程的特点和SAD算法具有被并行处理特性，采用FPGA来实现多个模板的SAD算法，是在基于并行处理特性上和实时性要求很高的情况下完成对多个模板的SAD计算，在规定时间内得到相关系数，能够提供足够的时间让DSP处理跟踪算法，从而提高整体系统实时性和精确性［5］。

2 多级模板并行匹配原理

2.1 模板匹配原理

基于图像灰度值模板匹配，本文采用的是SAD算法(差的绝对值和相关法)。如图1所示，设搜索图为(M+N)×(M+N)，模板图为N×N。

图1 搜索图和模板图

SAD算法公式定义为

式中:i∈(0，M+N)，j∈(0，N);R(i0，j0) 为相似性度量函数在偏移量是(i0，j0)时的匹配度量值也称之为相关系数;S(i0+i，j0+j)为实时图像中搜索区域中各像素点灰度值;T(i0+i，j0+j)为模板图中各像素点灰度值;(i，j)为搜索图与模板图之间的偏移量，当R(i0，j0)取值最小时认为 (i0，j0) 为最佳匹配位置［2］。

2.2 实现过程

如图1所示，最初模板T坐标(0，0)和搜索图S坐标(0，0)对齐，计算完毕之后模板图T在搜索窗上进行滑动一次，使得模板图T坐标(0，0)与搜索窗坐标(0，1)对齐，同样进行相同SAD计算，计算出相关系数R(i0，j0)。每滑动一次计算出偏移量为(i，j)的相关系数R(i0，j0)。当滑动M×M次之后，得到全部偏移量对应的相关系数R(i0，j0)［6］。

当模板级数达到多级时，如果采用DSP进行计算，则一级模板所有的匹配度量值计算完毕之后，才会进行下一级模板计算。用此方案时间会成倍增加，比如模板有N级，计算时间是单个模板时间的N倍，因此DSP在计算多个模板，实时性不能满足要求。如果采用FPGA来实现多级模板的优势是显而易见的，FPGA并行处理特性可以并行处理多个模板，计算模板相关系数R(i0，j0)所用时间将会大大降低，多个模板所耗费时间等于单个模板耗费时间，比DSP计算时间减少N倍。采用FPGA实现多个模板SAD算法，能够很大程度上降低匹配时间，满足实时性要求。为DSP完成跟踪算法提供了足够时间，并且能够提高整个目标跟踪系统的可靠性和精确性［7］。

3 多级模板并行匹配的FPGA上实现

3.1 基本思路

本文采用的FPGA芯片是Altera公司CycloneIII系列EP3C40F484I7，总逻辑单元Total logic elements为39600，Total memory bit为 1161216 bit，M9K 为126 个［7］。

通过深入理解SAD算法原理之后，容易采用D触发器阵列存储模板图和搜索窗每个点，为了便于实现SAD算法，经资源分析之后此方案是不可能实现的。为此设计一种方法优化该设计，能够在满足性能情况下实现资源优化。该芯片逻辑单元不多，应该减少逻辑单元使用，虽然不能得到所有点的D触发器flip-flop阵列，但是能够得到一行数据的D触发器flip-flop，通过这样的思路可以降低资源消耗。

在模板一行数据和搜索窗一行数据都已经保留的情况下，搜索窗进行移位的同时计算行所有点的绝对差之和，并且能够在规定时间内计算出全部偏移量对应的相关系数 R(i0，j0) 。

3.2 设计方法

如图2所示，整个系统分为4个模块:存储模块、乒乓移位模块、SAD计算模块、SAD值存储模块。

图2 系统框图

1)存储模块

如图3所示，模板图数据和搜索窗数据各有一个存储器，在写使能有效时，将模板数据和搜索窗数据分别存入各自存储器中，读取模板数据和搜索窗数据以128 bit数据读出，输出位宽越大，读数据所消耗的时间越少，该模块的输出作为兵乓移位模板的数据输入。

图3 存储模块

2)乒乓移位模块

该模块设计如图4所示，基本思想是根据换行信号为高电平时，读取搜索图一行数据到移位寄存器A中，模板图一行数据读取到锁存器A中。同时移位寄存器B进行移位操作，锁存器B数据不变，锁存器B和移位寄存器B并行输出一行数据给SAD计算模块进行行相关系数值的计算。换行信号为低电平时，读取搜索图一行数据到移位寄存器B中，模板一行数据读取到锁存器B中。同时移位寄存器A进行移位操作，锁存器A数据不变，锁存器A和移位寄存器A并行输出一行数据给SAD计算模块进行行相关系数值的计算。

图4 乒乓锁存和移位

该模块优点为:首先，在计算当前行的SAD值时，就在存储下一行的数据，形成了行流水方式，节约了读取行消耗时间，减少匹配时间;其次，行与行相关系数计算占用逻辑单元少，有利于在有限的资源下计算多个模板。

3)SAD计算模块和SAD存储模块

如图5 所示，T_data［n:0］和 S_data［n:0］分别是模板图行数据和搜索窗行数据，SUB为16 bit减法器，ABS为16 bit取绝对值模块，多路ADD的作用是将行中所有点的绝对差值进行累加运算，SAD存储器用于暂存行相关系数值以及存储最终结果。

图5 SAD模块和行值累加

通过乒乓移位模块输出模板图行和搜索窗行的数据到SAD计算模块中，对它们进行减法，绝对值和求和运算。得到的一行相关系数将它送入2路ADD模块中用于累加。用模板图的滑动次数也就是偏移量作为SAD值存储器的读写地址。计算SAD值时，一直让SAD存储器处于读状态，便于下一行的相关系数能够与上一行的相关系数进行累加。最后滑动M×M次之后，完成了所有偏移量对应相关系数的计算，这样SAD存储器就存储了所有的相关系数，其中存储器地址于偏移量所对应，比如偏移量是(i0，j0)，那么在SAD存储器地址为i0×16+j0的空间中就是偏移量(i0，j0)的相关系数。然后将所得到相关系数发送给DSP，DSP在相关系数基础上进行后续算法运算。

4 系统运行结果性能分析

4.1 Modelsim仿真结果及分析

首先定义4个模板图和搜索图分别是:模板图24×24对应搜索图40×40;模板图32×32对应搜索图40×40;模板图48×48对应搜索图为64×64;模板图64×64对应搜索图72×72。以模板图为24×24和搜索图是40×40为例，对仿真结果进行分析。如图6所示，模板图每行的数据0～23，搜索图每行数据16～55。

图6 模板图为24×24和搜索图是40×40

如图7和图8所示，在开关信号为低电平时，一行数据从存储器中读出来并且存储到移位寄存器当中，该图反应了一个时钟周期读出8个像素点数据并且存入移位寄存器当中。等待开关信号为高电平时移位寄存器进行移位操作，这样每移动一位就相当于模板图在搜索图中滑动一位。模板行数据的保存类似搜索图行数据的保存，只是在计算过程中模板行数据不进行移位操作，只是维持值不改变，等待一行计算完毕，再进行下一行存储。

如图9所示，SAD存储器发送地址(Mad_send_rdaddress)与模板图滑动次数即偏移量是相对应的。发送地址为0的时候表示模块处于初始位置，偏移量为(0，0)。图中0地址对应的最终绝对差之和实际值Mad_Sum为9216(地址与数据有一个时钟的延迟)。如图6所示模板图和搜索图，容易得出模板图和搜索图偏移量为(0，0)时每个点对应的差值为16，总共有24×24个点，绝对差之和理论值为16×24×24=9216。由图可以看出理论值和实际值相同，所以用FPGA实现的模板匹配具有匹配准确性。

图9 最终结果

本 文 采 用 Altera公 司 的 CycloneIII系 列EP3C40F484I7设计4个模板并行匹配处理系统，如图10所示，有4个SendMad_en读信号为高电平时，表示对于该模板的MAD计算完毕。整个系统实现了4个模板的匹配算法并行处理，由图分析可知，模板24×24首先计算完毕，64×64的最后计算完毕，由于模板越小计算量越小，所以匹配时间越小。

图10 4级模板并行匹配

4.2 匹配时间上的分析与DSP性能对比

整个系统采用50 MHz分频之后13.5 MHz时钟作为基本时钟。在表1中Les为逻辑资源，MB为memory bit存储资源，从表中的数据可以看出FPGA在并行处理多个模板匹配的优势是很明显的，FPGA计算4个模板的匹配总的耗时等于单模板中最大耗时，模板32×32比模板24×24所用时间要小是由于其对应搜索图大小不同。但是DSP总的耗时便是4个模板匹配时间之和，超过场信号周期20 ms，没有办法用DSP来做4个模板相关系数计算。现在FPGA系统时钟采用13.5 MHz进行计算，如果系统时间进行倍频，计算时间将会成倍减少。

4.3 FPGA+DSP与单独DSP对比实际的效果跟踪图

验证FPGA并行处理多模板实时性和可靠性，为此构造一个背景单一的实时场景，背景采用白色，运动物体是一把黑色的钥匙，钥匙通过一根固定在上方的线连接，使钥匙做钟摆运动。图11的跟踪图是基于FPGA+DSP系统，由FPGA来完成4个模板的相关系数，通过图11分析跟踪框中心与运动物体中心始终对齐，匹配准确性高。图12的跟踪图是基于单DSP系统，由DSP来做4个模板相关系数以及跟踪算法，通过图12分析图像每隔一场，跟踪框中心与运动物体的中心有很大的偏差，匹配性能差。通过图11和图12比较，能够得出FPGA+DSP具有良好的实时性和精确性。

表1 时间和资源统计

5 小结

本文以低端FPGA为平台，实现了实现多个模板图与多个搜索图之间像素值差的绝对值和相关法。本设计巧妙和灵活，将匹配技术中适合在并行处理的SAD算法在FPGA上移植，为DSP分担了算法中大量的计算，并且利用有限的逻辑单元和RAM资源实现了4个模板同时进行相关系数的计算。特别是乒乓移位模块，进行移位的同时也在进行读取行的操作，很大程度上节约了匹配时间。匹配时间得到很大程度的降低，为DSP完成跟踪算法提高了足够的时间，从而提高了整体系统的实时性和精确性。

［1］马莉，韩燮.主成分分析法(PCA)在SIFT匹配算法中的应用［J］.电视技术，2011，35(1):129-132.

［2］李国辉.基于多片DSP的相关匹配算法的研究与实现［D］.成都:电子科技大学，2004.

［3］TORU W，YUKIHIKO Y.Multi-template GAT/PAT correlation for character recognition with a limited quantity ofdata［J］.IEEE Computer Society，2010，10(704):2873-2876.

［4］MANZAR M A，CHEEMA T A，JALIL A，etal.New image matching technique based on hyper-vectorisation ofgrey levelsliced binary images［J］.IET Image Processing，2008，2(6):337-351.

［5］高陈强，余迪虎，李强，等.视频图像中基于特征匹配的人流量统计［J］. 电视技术，2011，35(15):20-23.

［6］陈辰，王沛，韦芳芳.图像多通道边缘信息辅助的快速立体匹配算法［J］. 电视技术，2011，35(23):17-21.

［7］MICHAEL D，CILETTI.Advanced digital design with the verilog HDL［M］.2nd ed.Beijing:Publishing House of electronics industry，2010:213-224.