摘要：本文详细介绍了基于高性能TigerSHARC DSP处理模块和模板匹配算法(template matching)的实时图像跟踪处理系统的优化设计方法；深入分析了SAD操作中涉及到的地址对齐问题，提出了一种优化的设计方案，将并处理效率提高20倍，并在实际的实时图像跟踪系统中得到应用。

关键字：图像跟踪，TigerSHARC，并行流水，地址对齐 

Abstract:This paper focuses on the optimized design and implementation of the template matching real time image tracking system utilizing high performance TigerSHARC DSP module. Severe address aligning issues encountered on SAD are discussed thoroughly, and get well solved.

Keywords: Image Tracking, TigerSHARC, Pipeline, Address aligning

1.  引言

随着电子技术的不断进步，目前越来越多的实用数字图像跟踪系统采用高性能DSP COST模块实现快速构建实时处理原型[1]。在众多型号的DSP处理芯片中，TigerSHARC系列DSP处理器具有大的定点、浮点处理能力，成为目前世界上最快的浮点DSP处理器，由于其具有强大的可扩展能力，TigerSHARC DSP处理器也一直引领可扩展并行多DSP实时处理系统的发展方向，被称为“多DSP系统实现的标准”[2]。同时，TigerSHARC DSP处理器对字节数据的处理提供了良好的支持，例如，支持基于字节的SAD（SUM-ABS-Difference）操作，非常适合构建实时图像处理系统。但由于严重的地址对齐问题，需要对系统进行优化设计，以实现在满足严格的实时性要求的条件下，限制系统规模，降低系统成本。

2.  实用实时图像跟踪处理系统

2.1 实时图像跟踪处理系统组成

首先给出实用实时成像处理系统的结构组成框图，如图1所示，系统包括PMC 视频采集模块，TigerSHARC DSP处理模块（内部集成4片TigerSHARC DSP处理器），cPCI工控机主板，控制手柄和VGA显示器等。视频采集板的输入为PAL制式黑白图像信号，输出768×288×8-bit的数字图像数据并通过TigerSHARC DSP专用的LINK接口以每场20毫秒的间隔送至TigerSHARC DSP处理模块进行模板匹配(template matching)检测算法。之后，DSP处理模块在原始图像上叠加目标信息，通过cPCI工控机主板传送到VGA显示器进行显示。

 
图 1. 基于TigerSHARC处理模块的实时图形跟踪系统框图

2.2 模板匹配算法

模板匹配算法是在一幅图像场景中检测目标的基本算法，将已知的目标图像模板在一幅未知图像场景中滑动，并与对应的未知场景图像块进行比较，如果结果足够接近，就将该图像块标识为目标。一般采用目标模板与未知场景图像块之间的各像素值的差异绝对值之和的形式来度量其接近程度。如下式所示，其中各像素之间的运算操作定义为SAD（SUM-ABS-Difference），整个过程如图2所示。某目标模板T，为M×N维的像素阵列，以像素为单位在未知图像场景中沿水平方向和垂直方向依次滑动。每滑动一步，T即与未知图像场景中对应的待检测像素矩阵S进行如式1所示的SAD操作，并将所得结果D(i,j)作为接近程度的度量（Difference measure）存入度量矩阵D，其中，S是与T同样大小的像素矩阵。

   (1)

图 2. SAD 模板匹配操作

2.3 SAD模板匹配中的地址对齐问题

TigerSHARC处理器的ALU提供了对SAD操作的指令支持，如图3a所示。在一个时钟周期（3.3ns/300MHz/ADSP-TS101S）内，单个ALU可以通过指令PR+=ABS（BRmd-BRnd）完成模板T中8个像素的SAD操作，其中PR为处理器ALU中的64-bit累加器，用于存储SAD操作中图像字节数据的累加结果。BRmd和BRnd均为32-bit×2的寄存器对，分别读取T和S中的8个对应像素字节数据。因为TigerSHARC DSP处理器为双核结构，具有两个ALU，所以，其单周期最多可以完成模板T中16个像素的SAD操作。显而易见，使TigerSHARC DSP处理器的指令流水线中不间断地执行SAD指令是获得其峰值处理能力的必要条件，而其ALU从内存取操作数时产生的地址对齐问题则是制约处理效率提升的主要瓶颈。

（a）           

（b）

图 3. TigerSHARC 中的SAD 指令执行流程和带来的地址对其问题

如图3b所示，SAD指令执行时前，两个ALU分别需要从内存读8个字节目标模板数据和8个字节待检测场景图像数据至内部寄存器，且要求该数据存放首地址须为64-bit对齐，否则会导致内部总线访问异常。T与S虽然是同样大小的像素矩阵，但其大小一般远大于16个字节，在T内地数据地址是连续的，而S作为从场景图像中切割出的一部分，其地址通常不连续。同时，随着T在场景图像中不断以字节为单位逐行滑动，地址对齐问题所造成的效率损失会更加突出，势必需要对非对齐的数据地址进行计算，零散字节数据的收集合并（bytes adjust and merging），以及非常复杂的多重循环控制。以单片TigerSHARC DSP处理器对处理效率进行评估，经编译器优化过后的ANSI C程序，可以实现在100ms左右完成一场背景图像匹配任务。以此计算，至少需要将背景数据分为5个部分，并分配至5个TigerSHARC DSP处理器中，才可以勉强达到20ms实时性要求的下限，这样，系统内就不得不添加一个TigerSHARC DSP处理模块，这对于功耗、成本、重量、体积等指标都是不可接受的。因此，直接实现如式1和图3所表示的计算过程是不可行的，必须考虑优化的计算方案。

3.  SAD优化设计方案

重新对图2中描述的SAD过程进行分析，发现T中的每一个字节像素在背景图像中需要滑动的次数是一样的，由于其每一次移动的计算结果都存入D的对应位置，因此滑动次数与D中的元素个数也是一样的，且为一一对应。换句话说，D中的某一个元素涉及到T中的全部字节像素的某一次滑动。则根据加法结合律，可由式1得出优化后的SAD处理过程如下式所示。

 (2)

犹如蚂蚁搬家，可以先使T中16个字节像素数据在背景图像上滑动，进行应有的SAD操作，并将每一次滑动得到的结果存入D中的对应位置，这时D的累加和为中间结果；再使T中的之后的16个字节像素数据在背景图像上完成滑动SAD操作，并将此次的结果与前次保存在D中的中间结果相加，再存入相应位置，以此类推，直至T中的全部字节像素数据完成滑动，并更新D中累加结果。根据上式可得优化实现方案如图6所示，优化方案与直接实现方案相比，并没有减少SAD操作的次数，但由于调整了算法执行结构，和运算次序，大大提升了访问内存数据的效率，简化了实现流程，处理器指令流水线得到了较好的组织。对前述同样的处理任务进行评估，优化实现方案可以使用1个TigerSHARC DSP处理器在5ms内完成。因为在优化实现方案中，T内的数据具有良好的可分性，采用2个TigerSHARC DSP处理器在2.6ms内便可完成。采用优化实现方案不但可以很好的提升系统的实时性能，而且还可以减少一个TigerSHARC DSP处理模块，大大降低了系统的复杂度，体积，功耗和成本。同时还可以提供约15ms的时间供压缩，传输等其他处理任务分配。

图 4.优化设计方案中的SAD指令流水操作

4.  结论

本文详述了一种实用的实时数字图像跟踪系统的优化设计方法，指出了地址对齐问题在处理系统优化设计中的重要性，着重针对模板匹配处理算法进行了创新的优化设计实现，满足了系统整体对实时性、功耗、体积、成本等多方面的需求。该系统实现在实际工程中收到了良好的效果，实际系统组成如下图所示。

图 5. 实际的实时图形跟踪系统

参考文献

[1]阎青, 张桂林, 张鹏. 基于DSP的实时图像目标搜索与跟踪系统设计［J］, 微计算机信息, 2005，8-2： 90-92.

[2]刘书明, 苏涛,  TigerSHARC DSP应用系统设计., 电子工业出版社, 北京, 2004.

[3] Analog devices, inc., TigerSHARC hardware specifica-tion part # ADSP-TS101S, Analog devices, inc., 2002.

[4] William K. Pratt, Digital image processing 3rd edition, John Wiley and Sons, inc., New York, 2001.