基于降维与聚类的无人机航拍图拼接配准算法

鲁萍萍 梅 雪(南京工业大学电气工程与控制科学学院 江苏 南京 211800)

0 引 言

目前，无人机航拍已经运用于各种地面的勘察工作。然而，无人机飞行高度较低和无人机搭载相机焦距的受限，导致无人机获取的图像视野较小，难以拍摄到完整的目标区域。为了获取完整的目标区域信息，需要通过拼接多幅视角不同的图像以扩大无人机图像视野，从而更好地理解地面状况[1]。

无人机图像拼接已经得到越来越多的关注，其中图像配准成为关键问题，目前已经有一些基于特征的代表性配准技术。David Lowe于计算机视觉国际会议ICCV上发表尺度不变特征变换SIFT算法，并完善了SIFT，实现了图像的良好匹配[2]。但由于SIFT提取的图像特征为128维，在图像匹配过程中消耗了很多时间并占用大量内存。Ke等[3]针对SIFT特征维数太大的问题提出了PCA-SIFT算法，利用PCA对特征进行降维，一定程度地缩短了匹配时间。Bay等[4]在SIFT的基础上提出了加速稳健特征SURF算法，将特征降成64维，在实现良好匹配效果的基础上大大减少了匹配时间降低了内存占用率。之后各种基于特征的改进配准算法被提出[5-9]。文献[5-9]配准算法在准确率和快速性上已经取得了一定的成就，但都是基于整张图像做匹配处理，添加了未重叠区域中的误匹配噪声。

无人机拼接图像中除了重叠部分的其他区域，我们希望减少匹配点数量以缩短时间和提高匹配正确率。基于这种思想，本文基于SURF配准算法，结合PCA降维与K-means聚类提出了一种改进的子区域配准算法。首先给出无人机图像拼接的流程。其次提出了改进的匹配算法，采用PCA对SURF提取的64维特征再次降维，在降维的基础上用K-means聚类算法对每幅航拍图像特征值进行分类。通过计算拼接与待拼接图像类别的相似性，选取两幅图像相似性最大的区域进行匹配。最后采用FLANN粗匹配[10]与RANSAC剔除误匹配[11]，通过图像融合实现无人机航拍图的拼接。本文利用三组无人机航拍图像进行了拼接仿真实验。实验结果表明，与传统的SURF匹配算法相比，本文算法在提高拼接效果基础上也提高了拼接速度。

1 无人机图像拼接流程

无人机航拍图像一般为一系列有重叠的图像，图像拼接是将这些有重叠的图像融合成一幅广视角图。由于无人机体积比较小，自稳定性和抗风能力差，虽然装有自动驾驶与增稳陀螺，但是在拍照的过程中不可避免地会出现倾斜、抖动，相机本身也存在镜头的几何畸变。所以首先要对无人机图像进行去噪处理、几何校正、重采样等预处理[12]。无人机图像拼接的流程分为预处理、特征提取、特征配准和图像融合。本文采用的具体算法流程如图1所示。在特征提取过程中，采用传统的SURF算法，并构建64维特征描述符；在特征配准过程，采用改进的匹配方法，结合FLANN匹配与RANSAC剔除误匹配；在特征融合部分，采取渐入渐出平均加权融合方法。

图1 图像拼接算法流程

2 基于降维与聚类的特征配准

由于无人机拍摄时高度较低，拍摄间隔时间短，无人机航拍图像大多清晰度高，变形较大且图像间重复率较高，亮度变化小。目前对无人机航拍图的图像配准多采用SIFT和SURF算法[13-15]。相比于SIFT，SURF构成的特征维数少，但准确率和快速性还需要提高。因此，本文针对SURF算法又做了进一步改进。改进的配准流程如图2所示。

图2 改进的图像配准流程

2.1 SURF算法

SURF算法过程分为四步：建立尺度空间、寻找特征点、计算特征点主方向、生成描述符。

SURF算法在保持原图像尺寸不变的情况下采用不同大小的箱式滤波器建立图像的尺度空间。通过计算Hessian矩阵局部最大值以寻找特征点的位置和尺度因子。选定特征点的邻域，通过统计各特征点邻域内Haar小波的响应值以确定主方向[16]。

生成描述符，即生成图像每个特征点的特征向量。选取以特征点为中心的方形邻域，边长为20s(s为特征点所在的尺度)，旋转方形邻域的方向至特征点的主方向。将方形区域划分为16个子区域(5s×5s)，统计子区域内每个像素的Haar小波特征，计算每个子区域内水平方向小波特征和∑dx，水平方向小波特征绝对值的和∑d|x| ，垂直方向小波特征和∑dy，垂直方向小波特征绝对值的和∑d|y|，其中水平方向和垂直方向都是相对于主方向而言的[17]，如图3所示。

图3 构造描数子

每个子区域生成4维的特征描述符(∑dx，∑d|x|，∑dy，∑d|y|)，每个特征点对应生成16×4=64维特征描述符,其中i对应特征点的序号。因此可用若干个64维的向量去描述一幅图像。

但是由于SURF算子在生成描述符时过度依赖特征点周围的邻域特征，导致邻域内某些不重要的特征也被考虑进来，由此增大了特征提取的噪声。

2.2 基于降维的SURF算法

主成分分析法PCA算法是一种在较大样本中抽取重要数据以降噪和去除冗余的数据处理方法。介于SURF在特征提取时有可能提取某些不重要的特征，我们结合了PCA剔除某些在特征提取过程中对图像匹配贡献不大的特征，以提高图像匹配的精确度与速度。

但在降维过程中为了防止数据的失真，需要找到使原始信息最大保存的映射方法。对于航拍图的特征向量矩阵，更大的分散度才能使得原始信息保存最大化。同时，特征向量矩阵中的特征值存在冗余和错误值，需要减小筛选后每个样本中数据维度的相关性以及增大方差。

航拍图经过SURF提取特征后得到特征描述符 (xi1,xi2,…,xi64)，i对应特征点的序号。PCA-SURF将特征描述符(xi1,xi2,…,xi64)进行降维，筛选除去m个特征，使选取的特征最大保留原始图像信息。

PCA-SURF选取特征过程如下：

1) 样本图的所有特征描述符为(xi1,xi2,…,xi64)，i=1,2,,…,k，其中i为对应特征点的序号，k为特征点总个数。假设提取所有特征描述符中前64组数据组成一个64行64列的矩阵A，则:

2) 计算矩阵A64×64每一行数据的均值Mi:

(1)

式中：i对应矩阵A的行号，i=1,2,…,64。同时将矩阵A每一行所有数据减去该行的均值，得到Yij：

Yij=xij-Mi

(2)

式中：i、j分别为该数据所在矩阵A的行号和列号，i=1,2,…,64，j=1,2,…,64。由此得到进行零均值化处理后的新矩阵B。

3) 构建协方差矩阵c:

(3)

4) 得到协方差矩阵c的特征值λi与特征向量ei，并给特征值和特征向量排序，选取前m个最大的特征值，即选取64维样本中对应于m维的航拍图像特征数据，并找到前m个最大的特征值对应的特征向量，组成投影变换矩阵P。

5) 将拼接图与待拼接图的所有64维描述符按照对应变换P投影至m维空间，得到去除冗余和错误的新描述符xi=(xi1,xi2,…,xim)，i=1,2,…,k。其中i为对应特征点的序号，m为特征描述符降维后的维数k为特征点总个数。

由此，航拍图的特征描述符由64维降维成m维，去除了特征描述符中冗余信息以及错误信息。虽然降维使得特征提取消耗更多的时间，但是由于特征描述符变少，也使得特征匹配的速度更快，且匹配率更高。

2.3 基于聚类的子区域匹配算法

考虑到航拍图中参考图与待拼接图重合部分较大，并且两幅图重合部分的特征描述符相差不大，本文采用K-means聚类对图像进行分类，并提取两幅图的相似区域进行匹配。

K-means聚类算法是一种经典的事先确定聚类个数的无监督聚类方法。本文针对无人机航拍图像采用K-means聚类算法，对每幅图的特征描述符进行无监督分类。其中航拍图像每个特征点对应的特征描述符为一个一维的数组Xi。因此一幅图所有特征点的特征描述符为Ti(Xi1,Xi2,…,xij)，其中i表示图像序列号，j表示图像特征点序列号。以两幅图为例，参考图所有特征点的特征描述符为T1，待拼接图所有特征点的特征描述符为T2。两幅图相似区域选取流程如图4所示。

图4 相似区域选取流程

通过K-means聚类算法对无人机航拍图的特征描述符进行分类，本文分为4类，因此Ti矩阵被分为4组矩阵，分别设为ti1、ti2、ti3、ti4，其中i为图像序号。选取相邻两幅图像的4组矩阵，以两幅图为例，图像对应的矩阵为(t11、t12、t13、t14)(对应图4中参考图的4种图形)和(t21、t22、t23、t24)(对应图4中待拼接图的4种图形)，每一类tij的类均值为mij，其中i为图像序列号，j为类别号。分别比较t11和t21、t11和t22、…、t14和t24的类均值差dmn，其中m为第一张图对应的类别号，n为第二张图对应的类别号，每一类对应的类均值差分别为：

d11=|m11-m21|;d12=|m11-m22|;…;d14=|m11-m24|;

⋮

d41=|m14-m21|;d42=|m14-m22|;…;d44=|m14-m24|

(4)

比较得到dmn中的最小值，假设d11最小，则t11与t21最相似，由此可以得到所有邻近图最相似的两部分。

针对邻近图最相似的两部分，采用FLANN粗匹配，再采用RANSAC剔除误匹配以缩小误匹配数量。实验结果证明，在匹配前先采用K-means聚类缩小图像对应的区域可以减少误匹配数量，且减小了匹配时间。

3 实验结果与分析

由于传统的SURF算法很大依赖于关键特征周围的邻域特征，降低了图像匹配的准确率，同时SURF算法采用64维特征描述符，在匹配过程中占用了大量的内存，并增加了匹配时间。本文通过在SURF过程中加入PCA算法，对特征进行降维，并在匹配前，利用K-means对两幅图像进行分类选择图像重复性较大的区域，剔除了大多数的误匹配点，这样使得图像拼接更加准确和快速。分别利用传统的SURF算法和改进的拼接算法对图5中三组无人机拍摄的待拼接图做了实验。为了探寻图像相似度的大小对本文算法的影响，图5中的三组待拼接图分别为不同相似度的图像组。图5中第一组实验图像相似度较小；第二组实验图像相似度较高且相似度干扰小，即相似度高的图像部分对应真实世界坐标中的同一物体；第三组实验图像相似度高且干扰大，即相似度高的图像部分不一定对应真实世界坐标中的同一物体。

(a) 第一组图

(b) 第二组图

(c) 第三组图图5 三组待拼接航拍图

实验在Visual Studio 2013平台上结合OPEN CV的视觉库，采用C++算法语言对图5中三组待拼接图进行了拼接实验。

用传统SURF算法与本文改进算法对图5中的三组无人机航拍图做拼接比较，图6、图7、图8分别表示每组实验中传统算法与改进算法对图像拼接效果的对比。表1表示三组实验中传统算法与改进算法对匹配准确率以及拼接速度的影响对比。

(a) 传统算法拼接结果图(左图)与细节图(右图)

(b) 改进算法拼接结果图(左图)与细节图(右图)图6 第一组拼接结果比较

(a) 传统算法拼接结果图(左图)与细节图(右图)

(b) 改进算法拼接结果图(左图)与细节图(右图)图7 第二组拼接结果比较

(b) 改进算法拼接结果图(左图)与细节图(右图)图8 第三组拼接结果比较

表1 传统拼接算法与改进拼接算法比较

图5、图6、图7显示，传统的SURF拼接算法错位情况(图5(a)右图,图6(a)右图与图7(a)右图)明显比改进的拼接算法(图5(b)右图,图6(b)右图与图7(b)右图)严重。结果表明改进的拼接算法匹配率更高，能很好改善图像拼接效果，且对不同相似度的图像拼接有较好的鲁棒性。

表1显示，针对不同相似度的图像组，本文改进的拼接算法减少了匹配对数，显著提高了正确匹配率。因此，结合降维与聚类的改进算法剔除了大部分的误匹配特征点。同时，三组实验中传统SURF算法与本文改进算法拼接时间的比较，表明改进的拼接算法有效缩短了图像拼接时间。

实验表明，该算法针对无人机航拍图的拼接具有较好效果，能显著提高航拍图正确匹配率，有效减少图像拼接的时间，且很好地改善了图像拼接的错位情况，该算法对不同相似度的图像组有很好的鲁棒性。

4 结 语

本文提出了一种基于无人机图像拼接的改进配准算法，适用于无人机的图像拼接，提高了图像匹配精度的同时也减小了匹配时间。在图像预处理和图像融合部分采用传统的方法，对于图像配准做了改进。在特征提取部分采用PCA-SURF算法，将图像对应的特征描述符降维，方便减小匹配时间。对于图像匹配部分，采用K-means先对图像特征描述符分类，用类均值衡量类别相似度，选择相似性较大的部分做区域匹配。该方法相比于传统SURF拼接算法增大了正确匹配率，缩短了拼接时间，且对不同相似度的图像组有较好的鲁棒性。最后，给出无人机图像拼接的结果图，结果表明，本文提出的算法可以较好实现无人机的图像拼接。

[1] 余淮,杨文. 一种无人机航拍影像快速特征提取与匹配算法[J]. 电子与信息学报, 2016, 38 (3) : 509- 516.

[2] Lowe D G．Distinctive image features from scale2 invariant keypoints[J]．International Journal of Computer Vision，2004,60(2):91- 110.

[3] Ke Y, Sukthankar R. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors[C]// Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on. IEEE, 2004:506- 513.

[4] Bay H, Tuytelaars T, Gool L V. SURF: speeded up robust features[C]// European Conference on Computer Vision. Springer-Verlag, 2006:404- 417.

[5] Chen L, Liu J, Cao L. Image Matching by Affine Speed-Up Robust Features[C]// Proceedings of the SPIE, MIPPR 2011:Pattern Recognition and Computer Vision.2011,8004.

[6] Bu F，Qiu Y H,Liu J,et al. Improved bidirectional image registration based on Randon-SIFT[J].Journal of Computational Information Systems,2012,8(12):4997- 5004.

[7] 张东,余朝刚. 基于特征点的图像拼接方法[J]. 计算机系统应用, 2016, 25 (3) : 107- 112.

[8] 董强,刘晶红,王超,等.基于改进BRISK的图像拼接算法[J]. 电子与信息学报, 2017, 39 (2) : 444- 450.

[9] 贾银江,徐哲男，苏中滨,等.基于优化SIFT算法的无人机遥感作物影像拼接[J].农业工程学报,2017,33(10):123- 129.

[10] Andoni A, Indyk P. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[J]. Communications of the Acm, 2006, 51(1):459- 468.

[11] Martin A F，Robert C B. Random sample consensus：a paradigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM，1981，24 (6)：381- 395.

[12] 狄颖辰,陈云坪,陈莹莹,等．无人机图像拼接算法综述[J]．计算机应用,2011, 31 (1) : 170- 174.

[13] Sun Shujuan, Zeng Zhe. UAV image mosaic based on adaptive SIFT algorithm[C]// International Conference on Geoinformatics, Kaifeng, China: IEEE, 2013: 1- 7.

[14] Bi J, Mao W, Gong Y. Research on image mosaic method of UAV image of earthquake emergency[C]// International Conference on Agro-Geoinformatics. IEEE, 2014:1- 6.

[15] 韩天庆, 赵银娣, 刘善磊,等. 空间约束的无人机影像SURF特征点匹配[J]. 中国图象图形学报, 2013, 18(6):669- 676.

[16] Zhou W, Li H, Lu Y,et al.SIFT match verification by geometric coding for large-scale partial-duplicate web image search[J].Acm Transactions on Mutimedia Computing Communications & Applications,2013,9(1):319- 339.

[17] Bradski G,Kaehle A.学习OpenCV[M].于仕琪，译.北京：清华大学出版社，2009.