一种改进KNN的无人机图像快速拼接方法

罗 凯，徐俊武，杨 敏

武汉工程大学计算机科学与工程学院，湖北 武汉430205

随着时间推移，无人机技术和遥感技术发展迅速，利用无人机航拍遥感图像对病虫害治理已成为人们熟用的手段。由于无人机具有较强的灵活性、拍摄清晰等特点，可马上为灾情调查和病害防控提供资料。但同时无人机航拍存在视角小、易受天气和地貌等因素的影响的问题，导致拍摄无法看清其全貌，单张图像往往无法展示全部的目标区域，或者目标区域较为模糊，通常是拍摄多幅图像进行图像拼接。图像拼接是将两幅或者多幅图像拼成一幅清晰度较高的全景图像。其中图像拼接最重要的步骤就是图像配准。

Harris于1988年提出了Harris角点检测算法［1］，采用角点响应函数R并提取R的局部最大值来提取特征点。潘梅等［2］改进了Harris算法，利用无人机技术实现了图像拼接，拼接质量得到提升。2004年Lowe提出的尺度不变特征变换算法［3］（scale-invariant feature transform，SIFT）对图像缩放、旋转有强适应性。后来Bay在SIFT算法的基础上，提出了加速健壮特征算法［4］（speeded-up robust features，SURF），加入Hessian矩阵快速选取候选点，并对其进行非极大抑制。

针对KNN算法特征匹配耗时慢等问题提出一种基于图像像素点经纬度改进KNN的无人机航拍图像特征点配准算法。首先利用SIFT算法提取图像的特征点然后对其进行描述，然后提取出无人机机载系统里拍摄的数据信息计算出图像像素点的经纬度，然后计算出两张图像重合部分，由于两张图像重合部分特征点经纬度大致相似，因此利用这一特点加快KNN算法匹配特征点的时间，然后使用随机抽样一致算法（random sample consensus，RANSAC）算法［12］筛选出错误匹配点，最后图像融合利用最佳缝合线算法。实验结果表明，本文所提出的算法是一种能够快速匹配到正确特征点、效率高并且能够得到一副清晰全景图的航拍图像拼接方法。

1 图像配准方法

1.1 改进KNN算法

KNN匹配算法通过两点向量之间的距离来判断这两个向量是否相似，一般选取K个与特征点相似的点，K通常取2，如果选取的点相似度低，那么其中最相似的点为最近邻匹配点。在进行配准时，将配准图像中提取出来的特征向量与待配准图像中提取的特征向量求距离，找到两个向量间最近的距离，将两个匹配向量距离的比值与阈值进行比较，判断是否正确。由于无人机拍摄角度小，低高度飞行，相邻拍摄图像间存在大面积的重叠区域，并且正确的特征匹配对都在该重叠区域内，所以对全图进行特征提取，计算量非常大，效率也因此降低。

为了加快KNN算法的匹配时间，本课题组从无人机机载系统里提取出无人机拍摄时的经纬度坐标、高度和飞行速度等信息，通过这些信息计算出相邻图像的重叠区域和图像像素点的经纬度数据，那么就可以通过计算出来的重叠区域，对该区域进行特征提取，在特征匹配时，只对该区域进行匹配点对的判断，由于相邻图像间重叠区域里的特征点经纬度数据是大致相同的，可以很快地定位到待配准图像匹配点所在的位置，那么在该匹配点邻域内的其他特征点就可以快速匹配成功，从而不仅使得匹配成功的概率大幅提升，匹配的时间也将缩短。

1.1.1 重叠区域计算 在本次实验中无人机飞行时间为20 m/s，利用飞行航向偏角和成像中心点经纬度数据建立相邻图像的位置关系，以此估计重叠区域大小，确定特征提取区域，计算具体步骤如下：

步骤1：设两张相邻照片为P和Q，图像P中心点经度为x1，纬度为y1；图像Q中心点经度为x2，纬度为y2，那么两点之间距离l为：

其中地球半径R=6 371.01 km，π取3.141 59。

2）注浆压力变化。注浆过程中，压力要在控制范围内，防止出现过大或过小现象，若压力过低，要检查是否漏浆或查找浆液是否通过地下某管道流走；压力过大，应检查是否管路或混合器被堵塞，施工时需要控制注浆压力小于规定的注浆压力值。

步骤2：根据每张图像经纬度数据，通过代码模拟出无人机飞行轨迹。

步骤3：图像拍摄间隔为3 s，两张图像间转向角度不会太大，从飞行轨迹可以发现，拍摄图片按照设定好的运行轨迹飞行，从两张图像的航向偏角可知图像走势在既定航线上平移，将图像放到同一坐标系中，以P作为参考，图像P中心点向下平移了l的距离到了Q的位置，重叠区域如图1所示的区域S：

图1 重叠区域Fig.1 Overlapping area

至此重叠区域为P缩小宽度l的下半部分区域以及Q缩小宽度l的上半部分区域，重叠区域计算出来后，实验就只需要在该区域里进行特征提取。

1.1.2 计算像素点经纬度 每张图片的图像坐标与其对应的地面坐标的相对位置关系是不变的。已知每张图片的尺寸，机载系统数据里包含摄影中心的坐标、摄像头拍摄角度和拍摄高度，从而计算出图像像素点经纬度坐标。利用经纬度数据找到特征点所在区域，使用KNN算法快速匹配，完成图片的拼接。计算图像各点到图像中心的距离，公式如下：

其中H为图像拍摄高度，θ为拍摄角度，A为拍摄照片实际长度，M为图像像素长度，N为图像像素宽度，k为长度与图像像素的比例，以此计算出拍摄照片实际宽度，运用勾股定理，根据k计算出每个像素点到中心像素点的横向距离x和竖向距离y。

保持纬度大小不变，两条距离为1 m的经线之间经度的间隔为0.000 05°，同理，保持经度大小不变，两条距离为1.1 m的纬线之间纬度的间隔为0.000 05°，这样我们能通过每个像素点到中心像素点的距离计算出每个像素点的经纬度。

那么基于经纬度数据改进的KNN算法主要过程为：计算两张图片重叠区域，在重叠区域进行特征配准，选取特征点a，利用其经纬度数据找到待配准图像中相同经纬度数据的特征点b，因为计算出来的经纬度数据存在误差，所以需要利用算法对像素点邻域内的所有特征点进行匹配，找到特征点a在待配准图像中特征点b邻域内的最近邻点m和次近邻点n，如果两点距离dam和dan的比值小于阈值τ，那么a和m特征点匹配成功。因此根据该改进的算法，可以很快的将重叠区域内的特征点匹配成功，极大地提高了效率。

1.2 图像拼接

本文选取SIFT算法进行特征点粗提取，使用经纬度数据加快KNN算法对特征点的粗匹配，通过欧式距离度量特征点是否匹配成功。再使用RANSAC算法监测错误匹配点，该算法在最小二乘法的基础上对一个样本集合计算出能够拟合样本分布的模型，主要过程为随机抽取匹配成功的特征点集合里n个匹配点对，计算出这n个点对的初始变换矩阵M，然后将M验证集合里的其他点对，如果大部分匹配点对满足该矩阵模型，那么该模型是正确的，然后将满足该模型的点记为内点，不满足的记为外点。重复此操作就可以找到正确模型，筛选出最终准确的匹配点对。

由于每张图像拍摄时受外部因素影响，导致拼接出来的图片存在鬼影和缝隙，因此需要选取合适的融合算法进行拼接，以消除鬼影和拼接缝，最佳缝合线融合方法能使图像达到无缝或者逼近无缝合成，使图像合成的效果最佳。缝合线检测的公式如下［13-15］：

其中，Ecolor(x,y)代表图像重叠区域像素点的颜色强度差值，Egeometry(x,y)代表图像重叠区域像素点的结构差值。其中Egeometry(x,y)采用改进的梯度算子：

基于经纬度的图像拼接流程步骤如下：

步骤1：计算重叠区域，使用SIFT算法对该区域进行特征提取；

步骤2：计算像素点经纬度数据，减小相邻图片特征点匹配区域，利用经纬度数据加快KNN算法匹配时间，搜索出正确的匹配点对；

步骤3：使用RANSAC算法对匹配的特征点对进一步提纯，筛选出错误匹配点，得到精匹配点；

步骤4：使用最佳缝合线算法对配准后的图像进行融合，可以很好的消除图像之间的拼接缝，拼接完成后的全景图会显得更加自然。

2 实验与分析

选取某处松树林的航拍图像作为数据源，图像由大疆无人机的拍摄所得，型号为DJIFC6310，测试平台为CPU型号为AMD Ryzen 5＠3.40 GHz，内存为16 GB，软件开发环境为VS Code1.47+OpenCV3.4.2，图片分辨率为4 864×3 648，航拍高度H为113 m左右。

2.1 航迹数据

无人机机载系统里包含了每张图像相对应的Exif信息，比如拍摄时间，经纬度信息和无人机飞行角度等多种信息，如表1所示。

2.2 特征配准对比实验

为了验证改进的KNN匹配算法效果，使用传统SIFT算法与改进的SIFT提取算法和KNN匹配算法分别做实验对照，本次实验使用匹配准确率来评价算法是否适合无人机航拍图像拼接，匹配准确率通常采用均方误差（RMSE）来评价，公式如下：

表1 无人机POS信息Tab.1 UAV POSinformation

其中R代表均方误差值，(xi,yi)为匹配图像第i个匹配点的坐标，(x'i,y'i)为待匹配图像对应匹配点的坐标，N表示正确匹配对的数量。当RMSE值越小，准确度越高，反之准确度越低。通过对无人机拍摄的10组航拍图像进行实验，分别记录图像特征点匹配的正确率。

如图2匹配结果所示，传统算法全图提取的特征点很多，存在许多错误的匹配点，通过本文的改进算法对重叠区域进行特征配准实验，特征点匹配对明显变少，特征点分布基本集中在重叠区域里，匹配特征点大幅减少，这间接降低了误匹配现象发生的概率。

图3中实线代表SIFT算法RMSE值，虚线代表本文算法，可以对比看出，改进的算法配准精度比传统算法高，结合图3中的配准结果，本文改进算法配准精度得到了明显提升，配准效率也提高了很多。

图3 RMSE对比Fig.3 RMSE comparison

2.3 图像融合实验

为了进一步验证改进后的算法相较于传统SIFT算法在无人机林区航拍图像拼接上的优势，本次实验选取无人机飞行轨迹中的多幅图像进行拼接实验，实验图像如图4所示，通过图4的6张图像进行地理坐标计算，通过飞行轨迹计算图像间重叠区域，使用改进算法对重叠区域进行特征配准，再使用最佳缝合线算法对配准后的图像进行融合，拼接结果如图5所示。从图5中可以看出：本文改进的配准算法结合最佳缝合线算法在很大程度上消除了图像拼接误差，融合效果好，没有明显的鬼影和拼接缝，进一步证明了本文算法的可行性。

图4 实验图像Fig.4 Experimental images

图5 图像融合结果Fig.5 Image fusion result

3 结 论

松材线虫病治理的关键在于病虫的监测，目前许多松林区依然依靠人工检查的方式，效率不高，因此利用无人机技术以及图像拼接技术已成为防治松材线虫病的重要手段。针对航拍图像易受旋转、尺度变化的影响，本文使用传统的SIFT算法提取特征点，结合无人机POS系统存储的地理数据改进KNN算法，特征点匹配效率变高，然后利用RANSAC算法对特征匹配点进一步提纯，实现了局部松树林区域图像拼接技术，更加方便了树林管理员采集得了松材线虫病的松树数量和具体地理位置，能够更加快速治理好这一传染病。