基于多核DSP的图像实时相关匹配研究*

宋 丹

(中国西南电子技术研究所，四川 成都 610036)

基于多核DSP的图像实时相关匹配研究*

宋 丹

(中国西南电子技术研究所，四川 成都 610036)

针对目标精确定位中图像实时匹配性能的瓶颈问题，提出了一种基于TMS320C6678多核DSP的图像实时相关匹配方法。该方法采用并行处理设计，将复杂耗时的互相关运算分解并平均分配到多个核中同时进行；采用算法优化设计，将优化的快速匹配算法与预处理、搜索策略控制等方法相结合，实现图像的快速匹配。实验结果表明，该方法在保证匹配准确性的同时，还能显著降低图像相关匹配的计算时间，满足实时处理要求。

相关匹配；实时；并行处理；多核DSP

0 引 言

图像匹配技术是数字图像处理的关键技术之一。它在飞机辅助导航、远程武器或精确制导武器系统如巡航导弹的末制导、光学与雷达图像目标搜索与定位等军事领域具有重要的应用价值[1]。

图像匹配算法主要分为两大类：一类是基于灰度相关的匹配，另一类是基于特征的匹配[2]。目前，运用比较广泛的是基于灰度相关的匹配算法，其抗噪声能力强，在灰度及几何畸变不大的情况下，匹配概率及精度较高，缺点是计算量大，匹配速度慢，抗灰度及几何畸变能力较弱。以800×800大小的图像与480×480大小的图像相关匹配为例，仅计算互相关系数就需乘加运算多达700亿次，另外还需开方运算20万次。显然，如此巨大的计算量很难实时处理实现，必须减少其计算量或提高处理速度。

并行处理技术是提高计算处理速度的有效途径，其核心思想是将复杂的运算分解并尽可能平均分配到多个处理单元中同时进行。而并行处理结构和并行处理算法则是实现并行性的基本方法[3]。随着近年来芯片技术的发展，多核DSP越来越多的用于图像的实时并行处理，其在单个芯片内集成了多个高频率内核，多内核通过高速总线共享内部存储器和芯片外设，从而获得高性能的并行处理能力[4]

TI公司推出的TMS320C66x系列DSP为多核定点/浮点处理器，每个核的最高主频可以达到1.25 GHz。其中，TMS320C6678号称是业界性能最高、功耗最低的DSP[5]，其具有8个1.25 GHz DSP内核，定点运算能力高达320GMACS，浮点运算能力高达160GFLOPS[6],非常适合于图像实时处理这种需要超高性能以及并行运算的应用。

这篇文章基于TMS320C6678 DSP的特点开展了图像实时相关匹配的研究，在TI 公司的TMDS EVM6678L DSP评估板上实时处理实现，并进行了实验验证，给出了实验结果。

1 多核并行处理设计

1.1 C6678 DSP简介

TMS320C6678属于TI公司的C66xDSP系列，采用Keystone多核体系结构，内部集成最新的C66x DSP内核，其主要特性如下：

1)集成8个C66x内核，每个内核频率可达1.25 GHz。

2)具有双运算模块，能够进行定点和浮点运算。

3)集成了大量片上存储器资源，包括每个内核32 KB L1程序和32 KB L1数据缓存、512 KB的可配置专用存储器以及4 096 KB多核共享存储器，还提供了运行速率达1 600 MHz的64 bit DDR3存储器接口。

4)集成了大量片上外设及高速接口，其中串行Rapid IO、PCIE接口适用于芯片级、板级的互连，能提供极高的传输速率。

1.2 并行处理框架

C6678拥有8个内核，相当于8个独立的处理单元。为了实现并行处理，需要将复杂的运算分解，并基于一定的规则合理分配到各个处理单元中同时进行，一般有两种主要的运行方式[7]：

1)主从方式：即用一个处理单元(主核)完成处理的流程控制及任务分配，协调管理其它处理单元(从核)进行相应的处理运算。

2)数据流方式：即流水线处理，各个核为流水线中的一环，由上级处理单元数据驱动，完成自身运算后输出到下级处理单元。

根据图像数据块的结构特点，把大图像分割成小数据块并分配给各个核中处理是实现相关并行处理的可行方法，宜采用主从处理方式。而从数据接口考虑，数据输入输出与数据处理之间为串行结构，则最好采用数据流方式。因此，这篇文章中基于C6678的图像相关匹配并行处理采用主从方式和数据流方式的混合架构，其架构设计如图1所示。

图1 基于C6678的图像并行处理架构设计

由图1可见，C6678中的8个处理单元分为3类，分别用作接口控制(接口单元)，任务管理控制(主处理单元)和图像匹配处理运算(从处理单元)。其中接口单元和主处理单元之间采用数据流方式处理，接口单元负责对外设命令或者中断的响应及数据接收，然后将图像匹配处理所需的数据传递给主处理单元，启动图像匹配处理。主处理单元和从处理单元之间则采用主从方式，主处理单元接收到任务后(来自接口单元的数据和命令)，负责对任务分解管理，并调度从处理单元协同处理，共同完成。

1.3 任务管理

任务管理由主处理单元负责，其目的是采用一定的策略将复杂运算分解成多个子任务，然后再合理管理调度从处理单元资源，并将子任务分配给从处理单元处理，最后收集各从处理单元的处理结果并综合处理得出最终结果。其中的关键在于任务分解和资源调度，由DSP参与各种控制盒并行多任务的处理[8]。

任务分解是一个系统性工作，需考虑分解后各子任务的相对独立性。如果分解后的子任务相互之间关联较大，将很难做到并行处理。对于图像处理来说，将大图像分解成相对较小的子图像是一个简单快捷并行之有效的任务分解方法。而针对图像相关匹配处理，可将大匹配搜索区域分解成较小的子区域，这样就将运算量最大的相关系数运算进行了分解，如图 2所示。在分解时，需要注意从处理单元的数量，尽可能将大图像分割成从处理单元数的整数倍个数据块，从而使子任务能平均分配到各从处理单元，这样才能最大效率发挥并行处理能力。

图2 图像匹配任务分解

在该设计中，主处理单元采用循环查询的方式进行资源调度和任务分配。主处理单元不间断的循环顺序查询6个从处理单元的状态，若发现其空闲，则分配一个子任务给该从处理单元进行处理，并等待其结果返回。每个从处理单元对于主处理单元，被设计标识为3种状态：空闲(未分配任务)、数据发送(分配任务)、结果等待(等待从处理单元处理，接收结果)。状态转换如图 3所示。

图3 从处理单元状态转换

1.4 核间通信

多核协同处理必然涉及到核之间的通信，包括数据通信和状态通信。而其通信效率会影响到整个并行处理的运行效率，因此核间通信也是并行处理的关键。

该设计采用共享存储空间的方式来进行核间通信，需要通信的两个核之间分别设计数据存储空间和状态存储空间。数据存储空间用于存储待处理的数据，由一个核写入，一个核读取，完成写入或者读取操作后，再将状态信息写入状态存储空间。各核仍采用查询的方式获取共享空间的数据和状态。同时，为数据提高传输效率，核之间的数据交互设计为乒乓操作。

2 算法优化设计

2.1 相关匹配算法简介

采用应用广泛、成熟的归一化互相关匹配算法，具体描述如下：

已知基准图Z尺寸为M×N，实时图Y尺寸为m×n，实时图Y在基准图Z中逐行逐列搜索匹配，在基准图上可依次形成(M-m+1)×(N-n+1)个子图。每个子图尺寸为m×n。则第k个子图X与实时图Y的相关系数：

(1)

式中，xij为子图X中第i行、第j列像元的灰度值；yij为实时图Y中第i行、第j列像元的灰度值。相关系数极大值对应子图在基准图上的位置即为最佳匹配位置[9]。

由公式可知，计算相关系数的运算量相当巨大，乘加运算次数与3×(M-m+1)×(N-n+1)×m×n成正比，开方运算次数与2×(M-m+1)×(N-n+1)成正比，而开方运算对于DSP来说又相当复杂，需要耗费大量处理时钟周期。仍以计算800×800大小基准图与480×480大小实时图的相关系数为例，约需乘加运算700亿次，开方运算20万次。即使采用上节中基于TMS320C6678多核DSP的并行处理设计，每核仍需承担约120亿次乘加运算，4万次开方运算。再根据DSP处理能力进行估算可知，完成这些运算需耗时10秒左右，显然还达不到实时处理的要求。因此，还需对算法加以优化改进，以减少运算量及运算复杂度。

2.2 相关系数计算公式变换

(2)

2.3 事先预处理

H(i,j)=∑∑X(i,j)2

(3)

如图 4(a)所示，基准图像素灰度平方和积分图像H中任意一点H(i,j)表示的是基准图X中阴影部分的所有像素灰度平方和。利用该积分图像，对于任意大小的矩形区域，即任意基准图子图，只需4个点进行3次加法运算就可以计算出该区域的像素灰度平方和。如图 4(b) 所示，设阴影区域内的像素灰度平方和为S，则：

S=H(i1,j1)-H(i1,j2)-H(i2,j1)+H(i2,j2)

(4)

图4 基准图子图像素灰度平方和计算

∑∑xijyij为基准图子图与实时图的灰度互相关值，这也需要每个子图重新计算，且不能再优化。

可见，经过事先预处理优化后，相关匹配的主要运算量只剩∑∑xijyij，已大大减少。

2.4 搜索策略优化

相关匹配的基本搜索策略是遍历性搜索，即在搜索区域内逐行逐列每个像素位置上计算相关系数值。因此，如果能改进搜索策略，实现非遍历性搜索，将大大减少相关匹配的运算量。

3 实时处理实现

采用上述的多核并行处理设计和算法优化设计方法，在C6678多核DSP中实时处理实现归一化互相关图像匹配。其中，Core0为主处理单元，负责图像的分割和任务分配，Core2～Core7为从处理单元，根据主处理单元分配的任务完成相应处理。

归一化互相相关图像匹配的主要运算量在相关系数计算上，且相关系数计算彼此之间没有关联，因此可以将相关系数计算分解并分配给从处理单元协同处理；而图像预处理(含金字塔分解)以及相关系数极大值计算需用到全部图像数据，因此使用主处理单元单独处理。处理流程如图5所示。

Core0为主处理单元，控制整个相关匹配的工作流程。接收到待处理的图像数据后，首先对图像进行预处理，包括图像滤波去噪，旋转、几何校正等，并对图像进行金字塔分解。然后，根据从处理单元资源(如从处理单元个数、从处理单元内部存储空间大小、数据交互缓存空间大小等)，将基准图(大图)分解为从处理单元数整数倍个数据块，并分配给从处理单元进行处理。从处理单元接收到任务后，完成指定的相关系数计算后，将结果送回给Core0，由Core0综合所有的相关系数形成相关面，并求得最高峰所在位置即为匹配位置。每一级金字塔都如此操作，直至在原始图像中获得最终的匹配结果。

图5 相关匹配多核处理流程

4 实验结果

使用800×800大小基准图，480×480大小实时图共20余组光学图像进行实验验证，其中实时图从基准图中裁剪，并经过模糊、加噪等处理后获得。实验分别在PC(CPU 双核3.2 GHz，内存4 G，Matlab实现)和DSP(TI公司的TMDS EVM6678L DSP评估板)上进行，所用时间统计如表 1所示，而DSP实时匹配效果如图6和图7所示。

由表1统计结果可知，这篇文章提出的基于多核DSP的图像实时相关匹配设计很好的解决了以往图像相关匹配处理速度慢的问题，能够满足高实时处理要求。同时，图 6和图 7的匹配结果表明，该设计方法在降低处理时间的同时可以保证匹配的准确性。

图6 相关匹配实验结果图1

图7 相关匹配实验结果图2

表1 相关匹配运行时间比较

5 结 语

针对图像相关匹配计算量大，匹配速度慢，难以实时处理实现的缺点，这篇文章基于多核DSP提出了一种图像实时相关匹配方法。该方法采用了并行处理设计和算法优化设计，提高了相关匹配的处理速度。实验结果表明，较传统相关匹配方法而言，该方法显著降低了相关匹配的处理时间，能有效完成图像相关匹配的实时处理，同时又保证了匹配的准确性，可应用于对处理有高实时性要求的军事领域中，如精确制导武器系统、飞机辅助导航等。

[1] 杨小冈,缪栋,曹菲.一种实用的景象匹配仿真方法[J].系统仿真学报,2004,16(03):363-365. YANG Xiao-gang, MIAO Dong, CAO Fei. A Practical Scene Matching Simulation Method[J].Journal of System Simlation,2004,16(03):363-365.

[2] 刘莹,曹剑中,许朝晖等.基于灰度相关的图像匹配算法的改进[J].应用光学,2007,28(05):536-539. LIU Ying,CAO Jian-zhong,XU Chao-hui,et al.Improvement of image matching algorithm based on gray correlation[J].Journal of Applied Optics,2007,28(05):536-539.

[3] 柴震海.图像并行处理技术[J].红外,2005(03):27-33. CHAI Zhen-hai. Parallel Image Processing Technology[J].Infrared,2005(03):27-33.

[4] 张颖川.多核数字信号处理平台的设计与实现[D].西安:西安电子科技大学,2013. ZHANG Ying-chuan. Design and Implementation of Multi-core Digital Signal Processing Platform[D].Xi’an:University of Electronic Science and Technology of Xi’an,2013.

[5] 张慧娟.低功耗高性能多核DSP满足高性能计算[J].EDA CHINA, 2012(02):16. ZHANG Hui-juan.Low Power and High Performance Multi-Core DSP Meet the High Performance Computing[J]. EDA CHINA, 2012(02):16.

[6] Texas Instruments.TMS320C6678 Multicore Fixed and Floating-Point Digital Signal Processor Data Manual[DB/OL].US: Texas Instruments,2011[2015.12.24].www.ti.com.

[7] 丁有源,汪安民.基于多任务并行处理的DSP软硬件设计[J].单片机与嵌入式系统应用,2012(05):43-45. DING You-yuan,WANG An-min.Software and Hardware Designs of DSP based on Multi-core Task Parallel Processing[J].Microcontrollers & Embedded Systems,2012(05):43-45.

[8] 易克非,胡庆锋.基于DSP的实时多任务调度内核设计[J].通信技术,2011,44(06):135-137. YI Ke-fie,HU Qing-feng. Design of Real-Time Multi-Task Kernel for DSP[J].Communications Technology, 2011,44(06):135-137.

[9] 蒋运辉.光学/SAR图像的多DSP实时匹配系统的设计与实现[J].电子测量与仪器学报,2011,25(05):449-454. JIANG Yun-hui.Design and Implementation of Multi-DSPs’ Real-time Matching System based on Optical and SAR Images[J].Journal of Electronic Measurement and Instrument, 2011,25(05):449-454.

[10] 何芳芳,孙继银,刘小雷等.分层搜索在景象匹配中的应用研究[J].现代防御技术,2005,33(04):36-38,67. HE Fang-fang,SUN Ji-yin,LIU Xiao-lei,et al.Layered-searching for Scene Matching[J].Modern Defense Technology,2005,33(4):36-38,67.

[11] 曹菲,杨小冈,缪栋等.快速景象匹配算法控制策略[J].导弹与航天运载技术,2005(03):46-50. CAO Fei,YANG Xiao-gang,MIAO Dong,et al.Control Strategy of Fast Scene Matching Algorithm[J].Missiles and Space Vehicles,2005(03):46-50.

Image Real-Time Correlation Matching based on Multi-Cores DSP

SONG Dan

(Southwest China Institute of Electronic Technology, Chengdu Sichuan 610036, China)

Aiming at the bottleneck of image real-time performance matching in objective accurate positioning, an approach of image real-time correlation matching based on TMS320C6678 multi-cores DSP processor is proposed. The design of parallel processing is adopted in this appoach, thus to resolve the complicated and time-cosuming cross-correlation operation into several sections and equally assign them to multiple cores of DSP for simultaneous procesing. Meanwhile, the modified algorithm could speed up the image matching by combining fast optimized matching algorithm with pre-processing, searching strategy control etc. Experiment result shows that this algorithm could guarantee the matching accuracy while remarkably decrease the time of image correlation matching, so as to meet the demand of real-time process.

correlation matching; real-time; parallel processing; multi-cores DSP

date:2014-10-20；Revised date：2015-02-17

TN911.73

A

1002-0802(2015)04-0501-06

宋 丹(1981—)，男，工程师，主要研究方向为精确制导技术以及DSP实现。

10.3969/j.issn.1002-0802.2015.04.023

2014-10-20；

2015-02-17