基于多核CPU的无人机影像连接点并行匹配方法

邹亚未，刘玉红

(1. 东华理工大学 测绘工程学院，江西 抚州 344000； 2. 中国测绘科学研究院，北京 100830)

一、引 言

近年来，无人机低空平台因其具有机动灵活、响应快、使用成本低、维护操作简单等技术特点，成为低空摄影测量与遥感研究领域的热点[1]。影像连接点匹配是无人机影像摄影测量处理中的核心问题之一，由于匹配算法自身的复杂性，消耗的计算资源多、运行速度慢，在大规模无人机影像处理中该问题表现得更为突出。针对无人机影像匹配问题，文献[1—3]介绍了基于SIFT算法的无人机影像匹配方法，但是由于SIFT算子计算速度慢，单纯利用该方法不能获得较高的匹配效率。近年来出现的并行处理技术为大幅提高处理效率提供了有效的解决方案，主要为“高性能集群并行处理技术”和“大规模分布式处理技术”，典型的商业系统有Pixel Factory、INPHO’s Photogrammetric System、PCI Geomatics公司的Geo-Imaging Accelerator(GXL)等。但是这些系统所依赖的硬件平台成本昂贵、软件开发过程复杂，无法满足某些领域对处理平台小型化、移动化的要求[4-5]。

由于无人机影像具有重叠度不规则、像幅较小、像片数量多、倾角过大且倾斜方向没有规律等缺点，导致其匹配存在一定困难。在保证匹配算法可靠、稳定的前提下，为提高无人机影像匹配的效率，引入了多核处理器并行处理的思想，提出了一种基于几何约束条件的影像连接点匹配方法，多组试验表明了该方法的高效性。

二、基于几何约束的无人机影像连接点匹配方法

1. 基于SURF特征的影像初匹配

SIFT算子是计算机视觉和摄影测量领域非常著名的算子，由于其具有抗旋转、尺度不变等特性，在多个领域有着广泛应用。但SIFT算法也存在检测和匹配速度慢、对视角变化较敏感等缺点。2006年提出的SURF(speeded up robust feature)算法[6],除在可重复性、鲁棒性方面优于现有方法外，还能够获得较快的计算速度，因此在图像配准、图像拼接、检索等领域有着更大的应用价值。尽管SURF特征匹配有着上述优良特性，但是该算法本身是在基准影像上和搜索影像上同时提取特征点，然后进行特征描述和匹配。这就产生了两个问题：一是影像特征点匹配是全局遍历计算搜索，相对于其他常见灰度相关算法，特征描述和匹配花费了大量时间，效率不高；二是由于低空影像像幅小，SURF算法在匹配多度连接点(3度以上)时因为重叠区域提取的特征点不同而导致匹配稳定性不高。然而，在大区域、多像幅的低空遥感数据处理中，匹配速度的快慢非常关键，直接影响着处理效率，更多的多度连接点有利于低空影像的区域网平差，因此单纯地直接利用SURF算法并不能满足低空遥感影像匹配处理的要求。

有鉴于此，在利用SURF特征匹配抗旋转、尺度不变等特性的同时，能够提高匹配效率则是比较理想的结果。该方法在进行匹配的两张影像的金字塔顶层，首先进行SURF特征匹配，这样大大降低了计算量，缩小了搜索范围，提高了匹配速度；然后利用基于多项式的随机采样法(RANSAC)进行粗差剔除，该方法能够较好地剔除较大粗差点；最后把匹配结果映射到影像底层，利用匹配点对建立起两张影像的像方空间仿射变换关系。该匹配建立的影像间像方关系，大大缩小了后续影像精匹配的搜索范围，提高了匹配速度。

2. 几何约束条件的影像连接点匹配思路

在基准影像与搜索影像建立起仿射变换关系后，利用仿射变换系数可以将搜索影像窗口纠正采样到基准影像的像方空间坐标系下，使基准影像和搜索影像的共轭实体在像方空间上一致，即两者不存在旋转、几何变形和尺度变化，之后就可以直接进行相关系数的匹配。首先在基准影像上提取一定个数的特征点，并把特征点的位置映射到影像金字塔的各层；其次在影像金字塔顶层，通过两者的仿射变换关系，把特征点对应在搜索影像的匹配窗口采样纠正到基准影像上；然后在基准影像的像方空间坐标系下，进行相关系数匹配，保留匹配成功的点对，同时对匹配结果进行多项式迭代剔除粗差，并把最终解算的多项式系数作为基准影像与搜索影像间新的仿射变换关系；最后进行下层影像匹配，迭代直至底层影像，并进行最小二乘匹配，提高匹配精度。

三、基于多核CPU的并行匹配算法设计

在无人机影像数据处理中，很多算法在每张影像上完成相同的计算处理，并且在处理任务之间不需要进行数据交互，算法本身具有天然的可并行性。采用单幅影像作为处理任务的基本单元，以该幅影像与其满足重叠范围要求的一组相邻影像间的多组匹配作为一个匹配单元，那么在特征提取和匹配的环节上，每张影像完成相同的计算处理，任务之间不需要进行数据交换，是独立的执行单元。针对无人机影像连接点匹配算法的并行化设计，有以下两个关键点：

1) 匹配单元的确定。根据每张影像对应的POS数据记录，易知该影像摄影时刻摄站的位置和姿态，即影像的外方位元素；同时相机的焦距，地面的概略高程是已知的，把影像4个角点的像坐标，代入共线条件方程的物方模型，如式(1)所示，可获得影像4个角点的地理坐标，如此，可获得每张影像的地理范围；然后对每张影像的地理范围和其他影像范围求交并且计算两者的重叠度，把满足航行、旁向重叠度要求的影像记作该影像的邻接影像；遍历所有影像，得到了每张影像所对应的邻接影像，把影像与其邻接的多张影像的匹配任务作为一个匹配单元。之所以这样设计而没有选择两张影像间的匹配作为匹配单元，是因为根据影像连接点匹配的流程，在更高的任务级并行的层次上，单元之间没有数据交换和冲突，是独立的，最终形成了和影像数目相同个数的匹配单元。

(1)

2) 任务并行执行的策略。在匹配单元确定以后，匹配任务的数量也就确定了。本文根据CPU处理核的数量对匹配任务进行划分和并行计算，具体方法如下：首先获取CPU处理核的个数，然后开辟相同个数的处理线程，并将各线程指定到相应的CPU处理核上，各线程按顺序选择匹配单元并同时执行匹配任务，当其中任意线程匹配任务执行完毕后，则选择下一匹配单元执行任务，直至所有匹配任务完成。

为了测试匹配算法的并行性能，通过并行加速比与并行效率来评价[8]，具体定义如下

(2)

式中，参数p表示CPU处理器的数目或者并行线程的数目；T1为串行程序运行的时间；Tp为并行处理时间；Sp为并行加速比，其理论值为p；Ep为并行效率，其理论值为1。

四、试验与结果分析

为了验证上述方法的有效性，选取了两个并行计算试验平台和两套无人固定翼飞机航拍数据。数据1的基本情况为：平均航高为430 m，共7个航带397张影像，影像大小5616像素×3744像素，影像的航向重叠度为70%～80%，旁向重叠度为30%～40%，测区主要为城区人工建筑物。数据2为山西柳林地区无人机航拍影像，平均航高360 m，影像大小7360像素×4912像素，影像分辨率为0.05 m，共4个航带，32张影像，该航拍影像像幅较大，分辨率高。试验数据的详细情况见表1。试验平台的硬件配置情况见表2，其中试验平台2包含了普通硬盘和固态硬盘。

表1 试验数据列表

表2 试验平台硬件配置列表

为了验证该匹配方法的可靠性及适应性，在试验平台1上，选取数据1、数据2进行多核并行匹配试验。图1为数据1中编号为img006和img007的两张影像匹配结果的局部效果图，图2为数据2中上、下两个航带影像匹配的6度连接点。为了便于统计和分析，文中只对参与区域网平差的连接点进行了统计，数据1选取匹配的连接点总数为14 742个。其中，三度以上连接点5034个，经区域网平差共剔除了26个粗差点，整体平差的单位权中误差为0.87像元；数据2选取匹配的连接点个数为1127个，其中，三度以上连接点409个，经区域网平差剔除了2个粗差点，整体平差的单位权中误差为0.51像元；两套数据区域网平差两套数据试验的具体情况见表3。从表3可知，该方法匹配正确率在99.8%以上，匹配可靠性高。

表3 参与平差连接点统计情况

图1 img006和img007影像匹配结果局部效果图

为了分析利用CPU处理核的数量变化对匹配效率的影响，利用数据2，在两个试验平台上，进行了三组匹配试验，其中在试验平台2上，针对匹配的原始影像数据在普通硬盘和固态硬盘两种情况，分别进行了试验。根据匹配算法利用不同数量的CPU处理核，得到统计分析结果如图2、表4和表5所示。其中表4和图2(a)给出了在试验平台1上，无人机影像连接点匹配算法利用1～4核并行处理条件下的处理时间、加速比和并行效率；表5和图2(b)给出了在试验平台2上，匹配的原始影像数据在普通硬盘和固态硬盘两种情况下，无人机影像连接点匹配算法利用1～8核并行处理条件下的处理时间、加速比和并行效率。

图2 匹配的6度连接点效果图

表5 CPU处理核数变化条件下的连接点并行匹配处理结果表(平台2)

从表4和图3(a)可知，在试验1平台上，在利用4个处理核时，影像匹配算法的加速比达到3.92，并行效率达到了98.3%；加速比与处理核的个数成近线性的关系；从表4和图3(b)可知，在试验平台2上，原始影像数据在普通硬盘上时，当匹配利用的处理核个数在1～5个时，加速比与处理核的个数成近线性的关系，并行效率也在97%以上；而当匹配利用的处理核个数在6～8个时，加速比分别为5.22、5.37、5.38，即加速比变化不大，并行效率也迅速下降。原始影像数据在固态硬盘上时，加速比与处理核的个数一直成近线性的关系，当利用8个处理核时，加速比达到了7.41，并行效率仍在92%以上。从分析来看，原始影像数据在普通硬盘上，当利用处理核个数在5个以上时，匹配过程中的影像数据读写操作，已受限于硬盘的读写速度，使得加速比增加量变小；而在固态硬盘上，硬盘的读写速度对多核并行匹配影响较小。试验表明，该并行算法能够充分利用已有的计算资源，大幅提高处理效率，尤其是在高配置的硬件环境上，其加速效果更加明显。

图3 CPU处理核变化条件下的加速比和CPU并行效率图

五、结束语

影像连接点匹配是无人机遥感影像几何处理的一个关键步骤，高效的匹配算法对于无人机影像数据快速应急服务具有重要意义。本文提出的匹配方法具备了多核并行处理的高效率、SURF特征匹配的抗旋转、尺度不变，相关系数匹配可靠性高，最小二乘匹配高精度等多种方法的优良特性，有着较大的应用潜力和价值。如何把多核并行处理的思想引入到无人机影像几何处理的全过程，是下一步的研究重点。

参考文献：

[1] 胡庆武,艾明耀,殷万玲,等.大旋角无人机影像全自动拼接方法研究[J].计算机工程,2012,38(15)：152-155.

[2] 柯涛,张永军. SIFT特征算子在低空遥感影像全自动匹配中的应用[J].测绘科学, 2012, 34(4): 23-26.

[3] 索效荣,齐苑辰.基于SIFT算法的无人机航空遥感影像匹配[J] .测绘科学, 2012,37(1):89-91.

[4] 李劲澎,龚志辉,张婷.无人机影像SIFT特征匹配的集群并行处理方法[J].测绘科学技术学报,2012,26(6):440 -444.

[5] 纪松.多视匹配策略与优化方法研究[D].郑州:信息工程大学,2012.

[6] BAY H, ESS A， TUYTELAARS T, et al. SURF: Speeded up Robust Features[C]∥Proceedings of the 9th European Conference on Computer Vision.[S.l.]:ECCV,2006: 404-417.

[7] AKHTER S,ROBERT J.多核程序设计技术——通过软件多线程提升性能[M].北京：电子工业出版社，2007.

[8] 邹贤才，李建成，汪海洪，等．OpenMP并行计算在卫星重力数据处理中的应用[J]．测绘学报，2010，39(6)：636-641．