图像匹配最大互相关算法的专用ASIC硬件实现方式研究

摘要：探讨一种专用ASIC硬件实现方法，这种方法将DSP的灵活性与ASIC的高效性相结合，构造了单DSP+多ASIC的嵌入式计算机，对图像匹配获得了满意的效果。并由此提出了更高性能的硬件实现结构。

关键词：图像匹配 最大互相关 硬件实现

图像匹配是把从同一景物利用两个不同的传感器录取下来的两幅灰度图像在空间上进行对准，以确定两幅图像之间相对偏移的过程，通常是在已知的MxM个象素的光学或雷达基准图中寻找NxN个象素的实时图像的匹配位置。图像匹配是计算机图像科学的一种基本处理方法，在飞行器导航、目标跟踪、资源分析、文字识别等领域中具有极其重要的作用。这些高科技领域往往要求极高的实时性，而且要求运算速度要高达每秒几亿甚至10亿次操作以上。图像匹配的运算量非常大，如对较小的36x36的实时图和150x150的基准图，采用最大互相关算法进行全搜索图像匹配，它的运算量（约与（M-N+1）2xN2成正比）高达1714万次乘法和1714万次加法以上（不计对基准图数据预处理运算次数）。这些特点使一般的基准图数据预处理运算次数）。这些特点使一般的单CPU计算机结构难以甚至无法满足要求，特别是在航空航天等高恶劣环境的嵌入式应用中，更是无法满足高可靠性要求，因而必须采用高速灵活的计算机结构，才能可满足上述的要求。

图像匹配一般可采用如下几种方式实现：①软件；②高速DSP；③面向算法的专用ASIC器件。软件方法灵活，可大大降低计算量，但它必须以高速DSP硬件平台为基础，才可能满足高实时性要求；高速DSP方法简单灵活，能够满足高实时性要求，如TI公司的TMS320C6X系列高速DSP芯片，速度高达1600MIPS[4]，单片机就可实现高速实时处理系统。以这高速DSP芯片组成的硬件结构应是图像匹配计算机首选的硬件实现结构。但对应用于尖端科技的这些高速DSP芯片，西文发达国家对我国采取禁售策略，这使我国的某些科技领域受到很大的制约，因此在我国必须另辟途径以避免禁售策略的制约。面向算法的专用ASIC器件方法，采用大量的并行功能单元，速度高、可以满足嵌入式应用中的高速实时计算要求，而且结构简单、软件编程简单、硬件实现容易、体积小、成本低，特别适应我国国情。因此开发研究专用ASIC组成的高速图像匹配计算机实现结构具有重要的意义。

从图像匹配整个过程来看，虽然它具有非常大的运算量，但是它的运算主要为大量重复进行的乘法和加法运算，这就使它具有高度并行性、简单笥和重复性的特点。例如图1（每一方格代表一8位灰度图像数据）各对象素之间的计算以及各组子图之间的计算均没有结果的依赖性，这些特点使它非常适合于采用流水并行技术的ASIC电路。同时，图像匹配理论和诸机并行结构理论以及超大规模集成电路VLSI技术的飞速发展也为图像匹配的专用硬件实现方法提供了理论和物质基础，使图像匹配的高实时性能够进一步得到提高。

1 图像匹配最大互相关算法分析

基于灰度的图像匹配算法有许多种，其中最基本的有最小绝对差算法、最小平方差算法，最小卷积算法、最大互相关算法、不变矩算法等十几种。它们各有优缺点，其中最大互相关算法具有去直流噪声、匹配位置准确等特点，因而成为图像匹配采用的主要方法。它的原始公式为：

由于原始公式中的变量X（i,j）,Y(i+u,j+v)为去均值后的图像数据，不是原始图像象素数据，这样的算法结构有正有负、中间结果量多、计算量大、规律性差，不利于专用硬件实现[3]，因此必须对原始公式进行变换。把（2）和（3）式代入原始公式（1）中，变换后的公式为：

由于在图像匹配搜索过程中基准图是已知的，可预先对基准图子图数据进行均值和平方均值计算，然后预先装配在相关计算机上。在图像匹配过程中可不记其所需时间，因此图像匹配所需时间主要为求实时图数据和基准子图数据的卷积。这一结论也可通过实际图像匹配运算得到。在TI公司TMS320C30DSP（33M）上，采用公式（4）对不同象素数的实时图和参考图进行全搜索图像匹配，其运算时间如表1所示（汇编程序、程序放置在片内存储器，数据片外零等待存储器）。

从表1可看出，图像匹配的最大互相关算法主要归结为卷积运算，因此采用专用的硬件卷积电路必将大大加快图像匹配运算速度。

表1 采用互相变换公式图象匹配运算周期数和时间

2 以TMS320C30和专用ASIC器件LS9501组成的图像匹配计算机结构介绍

2.1 专用图像匹配器件LS9501介绍

LS9501[2]是西安微电子技术研究所根据图像匹配的特点研制成功的一个高速[20M]二维具有3x3内核的卷积器，它的主要功能是可同时对9对象素值实现乘加运算，即实现：。LS9501的输入是二维无符号8位的图像数据，输出是无符号20位卷结果和二维串行移位无符号8位的图像数据。其内部结构采用流水线并行技术，主要的功能单元有寄存器组、快速乘法器、加法器和控制电路，如图2所示。电路中设置的两组寄存器A和B由9个8位的移位寄存器构成，可存放9个图像象素数据。9个快速乘法器可保证在每一个时钟内同时进行9对图像数据相乘。其工作原理为：向A寄存器输入9个实时图象素数据后，再向B寄存器输入入九个基准图像素数据，当9对象素值输入完后，经过一定时间延迟，即可得到卷积结果。此后，如A寄存器的数据不变，B寄存器继续输入数据，则每输入一个数据，即可获得一个9个图像象素数据卷积结果。如果将多个LS9501卷积器级连起来，可实现更多对象素数据的卷积运算。例如，将4个LS9501级连，可实现36对象素数据的卷积，但要将4个卷积器的结果加起来，才能得到最后的结果。为此，西安微电子技术研究所研制了级连加法器LS9502，它的功能是在60ns内将4LS9501的输出结果求和。

3 图像匹配计算机结构

将4个卷积器LS8501和级连加法器LS9501组合起来作为TMS320C30数字信号处理器的快速协处理器部件，可组成一种高速的单DSP+多ASIC系统结构的嵌入式计算机，如图3所示。其工作过程为：首先TMS320C30按一定次序把36个实时图象素数据从实时图存储器中取出并输入LS9501的A寄存器中，然后，从基准图存储中将基准图像素数据输入B寄存器。输入36个基准图像素数据后，经过一定时间延迟，即可读出第一个36对图像象素数据卷积结果。此后即建立起流水，每输入一个基准图数据可得到相应36对图像象素数据卷积结果，直至对整个基准图匹配计算完。当实时图比较大时，可把实时图分成若干子图，然后对每一个子图分别进行卷积运算，最后再把它们的结果加在一起。这样，工作量最大的匹配计算任务由LS8501完成，TMS320C30将各个图匹配结果进行累加，求最大互相关值，并对卷器控制输入8位灰度图像数据。

4 图像匹配结果与讨论

在上述图像匹配计算机中，采用美国TI公司的TMS320C30（33M）DSP芯片主为处理器，4片关并行的LS9501和级连加法器LS9502组成图像匹配协处理器，外部图像存储器读写为零等待状态。根据组成的计算机系统结构，把36x36的实时图分成36个4x9的子图，然后计算每一子图与相应基准图子图卷积，最后把各个子图卷积结果累加在一起。通过编写TMS320C30汇编程序，对不同大小实时图和基准图进行搜索（即匹配所有（M-N+1）2个子图）最大互相差匹配运算，运算结果匹配位置正确。匹配运算时间如表2所示（对基准图像素数据预处理，不计运算时间）。

表2 实时图和基准图匹配运算时间

从表2可看出，采用专用集成电路LS9501可大大加快图像匹配运算速度，而且编程比较简单，实现容易，实测结果令人满意的。

本研究为国家“九五”预研项目“高速数字信号处理机技术”的一部分，已通过国家验收，并已应用于高速图像相关计算机中。这一研究的成功使我们看到了打破西方禁售策略的一种简单可行的方法。在实验中我们发现LS9501具有非常大的提高其实时性的潜力，现分析如下：

在实验中发现，LS9501内部图像数据移位寄存器时钟和3级加法器寄存器时钟不为同一时钟，这使得卷积模块的并行效率大为降低。如果将其改进为同一时钟，那笃在图3所示单机系统结构中，对（36x36）实时图与（128x128）或（150x150）基准图图像匹配时间将分别为394ms和592ms，图像匹配速度提高约1倍（软件模拟）。另外在实验的单机系统结构中，卷积模块完全靠TMS320C30控制，其时钟输入依赖TMS320C30读写信号，而且TMS329C30对外部存储器连续时读写信号不变化[1]，必须加NOP指令以使读写信号变化。这样LS9501的性能没有得到完全发挥，而且TMS320C30也不能处理其它任务，二者依赖性太大，相互制约，并行度和实时性难以得到提高。卷积模块发展为智能卷积处理器，那么硬件结构右发展为主从式双机计算机系统结构：主机为DSP，从机为卷积处理器。这种系统结构可使DSP与卷积器的依赖 性降到最低，提高任务级并行性，也可最大限挥LS9501的性能，从而提高图像匹配的速度。在不增加单芯片实现的卷积规模条件下，开发更高速度的LS9501，同样可提高图像匹配的速度。不容质疑，提高单芯片实现的卷积规模必将较大地提高图像匹配的速度。

由实验结构及以上分析可以预见，图像匹配最大互相关的专用ASIC实现方法是一个简单可行的方法，并具有很好的发展前景，完全可以开发体积小、成本低、速度与TI公司C6000系列高性能DSP的速度相比美的卷积处理器。