基于TS201 归一化互相关快速算法探讨

　　摘要：归一化互相关算法因其图像匹配稳定性高的特点被广泛应用于SAR成像和红外成像的制导系统中。为增强其应用的实时性，讨论一种基于TS201处理器，在保证全图遍历条件下，结合处理器的自身特性，采用递推与多模板思想构建的归一化互相关快速算法。实验证明，该执行效率常规算法的实现方案有了很大提高，可以实现低对比度条件下的目标匹配。

　　1 归一化互相关算法实现过程分析

　　基于灰度图像匹配技术中经典的算法的归一化互相关算法，虽然具有抗白噪声能力强，匹配准确性高的突出特点，但其大计算量，对于算法应用的实时性造成了严重影响。

　　设F（x，y）为一幅M×N的基准图像，B（x，y）是一幅m×n的实时图像、Sx,y是一幅与实时图像做互相关运算的匹配子图，且m<M，n<N。

　　标准归一化互相关算法计算公式如下：

　　观察上述公式可知，对应数据的减法运算、乘法运算和累加运算占据了绝大部分的计算量。针对TS20l处理器，可以借助其宽总线、大内存及并行指令的特点实现图像数据的高速存取和并发计算，提升标准算法的执行效率，由于该处理器仅支持32位取值，计算单元不支持8位数据乘法的特性，也给提升标准算法的执行效率造成阻碍。

    实验发现，导致算法效率下降的主要原因有两个：一个是其本身庞大的计算量；另一个是处理器32位取值的特性难以获取匹配子图数据。

　　2 递推多模板方案快速算法

　　2.1 递推方案

　　递推多模板方案快速算法首先要解决算法本身计算量大的问题。观察式（1）可知，式（2）为匹配子图与实时图协方差计算过程，式（3）为匹配子图方差的计算过程，式（4）为实时图的方差计算过程。对于实时图的方差计算部分，在整个匹配过程中只需要计算，而对于匹配子图的方差计算和两张图像的协方差计算则需要多次重复执行，共需要约（M-m）x（N-n）×3×m×n次加乘计算，计算量庞大。本文采用匹配子图递推方案来减少计算量。

　　结合实际图像，互相关算法实际是将实时图在匹配基准图像上做逐点逐行平移，并与其覆盖的匹配子图做相关运算，求取相关系数并比对，以获取匹配位置。在实时图平移的过程中，其覆盖的新匹配子图数据遵循如下递推原则：

　　（1）当实时图进行水平平行移动时，因Sx,y+1是Sx,y在基准图中右移1列的位置所对应的新匹配子图，即Sx,y+1的前n-1列是Sx,y的后n-1列，有：

　　（2）当实时图进行垂直平行移动时，因Sx+1,y是Sx,y在基准图中下移1行的位置所对应的新匹配子图，即Sx+1,y的前m-1行是Sx,y的后m-1行，有：

　　利用此递推原则，可以将归一化互相关式中的式（3）进行简化。观察式（3）中数据计算结果是以各个数据平方和的累加形式出现的，所以先将式（5）和式（6）进行平方运算，得到对应的式（7）和式（8）。

　　使用式（7）和式（8）对式（3）进行变换，得到全图遍历过程中使用的匹配子图递推方差计算：

　　在全图遍历的过程中，式（9）每次需要得到的计算结果只是在上次累加结果的基础上，减去移出数据的累加值和增加移人数据的累加值，中间重复数据的累加结果不再重复计算，以减少了计算量。匹配子图递推方案将会使单次子图方差计算的计算量由2×m×n次加乘减少至2×m或者2×n次加乘。

　　2.2 多模板方案

　　递推多模板方案的快速算法需要解决的另一个重要问题是匹配子图的数据准备问题。有两个不利因素导致产生此问题，一个是匹配子图数据准备过程重复进行（M-m）×（N-n）次，占据了大量处理时钟；另一个由式（2）的分析可知，算法运行过程中，每次相关匹配运算需要将实时图数据块与匹配子图数据块中的像素一一对应进行乘法运算。由于TS201自身只支持32位取值（字取值），所以无法将直接获取数据的方法获得的起始像素不位于字首的匹配子图数据块用于计算，也即不能利用DMA使用双缓冲的常规方式准备数据。

　　本文采用多模板计算方案来解决匹配子图数据的准备问题。

　　多模板计算方案首先将处理器定位于4字取值工作模式，加载并行指令，使处理器的计算能力化；其次将实时图予以适当的横向放大，构建多个与匹配子图等高的大实时图块，并分别在大实时图块范围内将真实实时图像数据进行逐点平移，与预匹配子图像素相对应，非真实实时图像素位置零，如图1、图2所示。

　　以图2为例，上半部分图像为构建的大实时图块，大实时图块中连续像素“4”点集为起始像素不位于字位上的真实模板图像；下半部分图像为大实时图块对应的大匹配子图，大匹配子图中连续像素“4”点集为真实实时图对应的起始像素不位于字位上的真实匹配子图。将这两个扩大后的数据块各个像素对应相乘并累加，其结果即为真实实时图与真实匹配子图对应像素的乘累加结果。这样做不仅建立了两个图像数据块各个像素间的对应相乘关系，而且也解决了起始像素不位于字位数据块的数据获取问题。

　　构建的这些大实时图块可直接与基准图像上对应的放大子图进行相关计算，省去匹配子图数据的重复准备过程，以适当增加计算量的方式消去了多次重复数据准备占用的处理周期。配合4字处理工作模式，只需在算法运行的初期性地构建16个（m+16）×n的大实时图块，即可与全部匹配子图进行相关运算，而原有的匹配子图数据准备模式则需要构建（M-m）×（N-n）个m×n像素的图像块。

　　3 实验结果

　　对使用汇编语言和递推多模板方案构建的归一化互相关快速算法进行测试。输入由红外图像拉伸而来的128×128像素的8位基准图像和64x 64像素的实时图像，如图3所示。

　　使用TS201处理器的运行快速算法。可以获得实时图像匹配坐标，运算时间统计结果见表1。

　　4 结语

　　归一化互相关快速算法充分结合了ADSP-TS201处理器的特性，构建了递推多模板互相关快速算法。实验证明，该算法大大缩短了执行时间，执行效率也得到了提高。

　　关于ADSP-TS201

　　ADSP-TS201是美国模拟器件ADD公司继TSl01之后推出的一款高性能处理器。其采用超级哈佛结构，静态超标量操作适合多处理器模式运算，可直接构成分布式并行系统和共享存储式系统。此系列DSP性价比很高，兼有FPGA和ASIC信号处理性能和指令集处理器的高度可编程性，适用于大存储量、高性能、高速度的信号处理和图像处理。如雷达信号处理、无线基站、图像音频处理等。

  

参考文献:

[1]. n-1 datasheet https://www.dzsc.com/datasheet/n-1_1997158.html.