一种基于重叠区指数化互相关和优化Dijkstra算法的航摄影像镶嵌线选取方法

刘瀚阳，王博帅，王凤艳，牛雪峰

吉林大学地球探测科学与技术学院，长春 130026

0 引言

航摄影像因包含大量语义和位置信息且相对容易获取而成为广泛使用的可视化产品，在环境监测和管理等方面均有所应用[1-6]。目前受分辨率的制约，单张航摄影像通常不能覆盖整个研究区域，因此需要用多张航摄影像组成一张大范围航摄影像[7-8]。然而因正射影像拍摄位置、照明条件和曝光参数等不同，同一地物在不同正射影像上会有颜色、纹理、形状和位置的差异[9-10]。因此需颜色校正、平滑处理和镶嵌线选取等步骤校正扭曲。以上步骤均需在镶嵌线附近处理，因此镶嵌线选取是航摄影像镶嵌中的重要步骤。

航摄影像镶嵌线即相邻影像拼接时的分界线，航摄影像的重叠区被分为两部分，每张航摄影像选取镶嵌线一侧组成一张大范围影像。一条理想的航摄影像镶嵌线应尽量避免穿过独立地物，尤其是尽量避免穿越在相邻影像上几何形状差异较大的独立地物(相对地表较高的地物，如建筑物等)。本研究专注于选取最优镶嵌线，实现航摄影像高质量镶嵌。

航摄影像镶嵌线选取的方法按照候选区域范围不同分为基于全区域的镶嵌线选取方法和基于限制区域的镶嵌线选取方法。基于全区域的镶嵌线选取方法在整个相邻航摄影像重叠区中逐像素搜索匹配差异最小的路径作为镶嵌线。此类方法可以在重叠区找到最优镶嵌线，但其耗时较长。目前存在的基于全区域的镶嵌线选取方法如下：Kerschner[1]提出“两蛇”方法，在重叠区根据对应像素颜色和纹理差异选取镶嵌线。Chon等[11]最先提出一个理念，即一条较长的视觉差异较小的镶嵌线比一条较短的误匹配较大的镶嵌线更好；其使用分水岭瓶颈算法限制重叠区对应像素错位差异的最大值，再逐层用Dijkstra算法寻找最优镶嵌线。Li等[12]及Dong等[13]使用图割算法，并联合考虑各区域色彩、梯度和纹理的差异来选取镶嵌线。Pan等[14]使用平均转换算法(MS)获取明显地物的位置，进而从非明显地物区域选取镶嵌线。

另一类镶嵌线选取方法是基于限制区域的方法，其通过人为制定策略在相邻影像重叠区的部分子区域选取镶嵌线。使用此类方法获取的镶嵌线不一定是整个重叠区中的最优解，但用时较少。目前已有的基于限制区域的镶嵌线选取方法如下：Pan等[15-16]在重叠区构造泰森多边形，再制定有效镶嵌多边形(EMP)策略沿着候选多边形边线形成镶嵌线，并进一步优化以适应不同形状的重叠区域。Yuan等[17]使用D-LinkNet神经网络获取影像中的道路区域，并在道路区域选取镶嵌线，此方法只适用城市道路覆盖密集的区域。Wang等[4]用矢量建筑物位置图识别重叠区中的建筑物，并沿建筑物间空地的中线选取镶嵌线以避免镶嵌线穿越明显建筑物。Wan等[18]根据矢量道路图联合重叠区中线的骨架选取镶嵌线。然而用额外矢量信息的方法有一定限制性。首先有时矢量信息图不易获取，其次矢量信息图有实效性，新的地物不会包含在旧矢量信息图中，从而可能影响后续镶嵌线选取操作。

基于全区域的镶嵌线选取方法可以在重叠区获取最优镶嵌线，因此本文提出一种基于全区域的航摄影像镶嵌线选取方法。首先构造一种指数化互相关方法高质量地表达航摄影像重叠对应区域的错位程度，再提出一种优化Dijkstra算法高效寻找匹配差异最小的路径来作为最优镶嵌线。

1 原理与方法

1.1 重叠区损失函数构建

在相邻正射影像重叠区域，一条最优镶嵌线应穿越对应像素匹配较好的点。一条可能较长的高匹配镶嵌线比一条较短的低匹配镶嵌线的镶嵌质量要高[11]。因此获取重叠区对应像素间的错位程度是一个关键问题。Chon等[11]使用5×5归一化互相关(NCC)来评价重叠区匹配情况。Yuan等[17]在此基础上用5×5快速归一化互相关(QNCC)加快计算过程。然而这两种方法获取的重叠区对应像素的匹配程度范围为(0, 1)，越靠近0匹配效果越好，越靠近1匹配越差，无法充分表达不同点间错位程度的差异。例如，匹配结果为0.3表示匹配结果较好，匹配结果为0.6表示匹配结果较差，而在用上述方法选取镶嵌线时，镶嵌线经过两个匹配结果为0.3的点的代价和经过一个匹配结果为0.6的点的代价相同，这显然是不合理的。

本文基于经过一个高不匹配点的代价应远高于经过多个低不匹配点的代价的理念，提出一种基于指数化互相关的方法充分扩大高不匹配点和低不匹配点间的错位表达差异。

首先，优化QNCC，提出平均快速归一化互相关。QNCC如式(1)所示：

(1)

式中：RQNCC(x,y)为点(x,y)处的QNCC值；Il(i,j)和Ir(i,j)分别是左影像和右影像在点(i,j)处的灰度值。然而，对应点灰度值相近不代表它们在红绿蓝(RGB)3个波段值都相近，只有RGB 3个波段值均相近才代表对应像素匹配程度较高。因此，本文提出平均快速归一化互相关(mQNCC)，分别从RGB 3个波段计算对应像素匹配程度：

(2)

式中：RmQNCC(x,y)为点(x,y)处的mQNCC值，RRQNCC(x,y)、RGQNCC(x,y)和RBQNCC(x,y)分别为点(i,j)的RGB 3个波段QNCC值。

接着，提出一种指数化互相关函数，以充分表达对应像素匹配程度的差异：

(3)

式中，ω是常数。使用此函数可将线性变化的归一化互相关函数进行指数化放大，从而成倍扩大低匹配精度像素与高匹配精度像素的结果差异，使镶嵌线经过低匹配像素点的代价远高于经过高匹配点的代价。

1.2 优化Dijkstra算法

Dijkstra算法是一种全局动态最优路径选取方法。它使用有向图处理非负权重区域的单源最短路径问题[11, 19-20]。一些方法[11, 14]基于Dijkstra算法决定镶嵌线。其在决定镶嵌线前进方向时会不断更新当前点邻域内8个点的全局损失值，以确定从起始点到每个点的最小损失值和最优路径。此类方法对重叠区中大部分点进行8次损失值计算和路径更新，计算量较大，对含有千万级像素的航摄影像而言处理时间较长。

本文提出一种优化Dijkstra算法，使镶嵌线不断沿最小全局损失点方向前进，且在重叠区每个像素点位置只运算一次便可求得由起始点到该点的最小损失值和最优路径，从而大幅减少计算时间。优化Dijkstra算法为

(4)

式中：点(k,l)表示当前重叠区中到起始点全局损失值最小的点，且需要其邻域内还有一个或多个点尚未计算全局损失值；S(k,l)表示点(k,l)邻域内8个点中尚未计算全局损失值的点集合；IDijk(k,l)表示从起始点到点(k,l)的全局损失值。本方法通过一次运算便能得到从起始点到点(x,y)的全局损失值和最优路径，高质高效实现最优镶嵌线选取。

2 实验

2.1 实验环境

本文算法基于Python3.7编写，使用OpenCV库和NumPy库进行图像处理操作。本文算法在64位Win10操作系统下测试，硬件包括Intel i5-8400 2.8 GHz处理器、Nvidia 3090显卡、56 GB内存和2 TB硬盘。

用于测试本文算法的两组图像分别来自城市和城镇区域。城市区域航空影像包含商业区、居民区和公园区域。其分辨率为0.05 m，单张影像宽10 000 pt，高7 800 pt。相邻影像航向重叠率75%,旁向重叠率45%。城镇区域航空影像包含一个小村庄和部分耕地及道路。其分辨率为0.07 m，单张影像宽8 000 pt,高5 300 pt。相邻影像航向重叠率77%,旁向重叠率50%。

2.2 实验参数

在八位无符号航摄影像中，图像像素值范围为[0, 255]。在提出式(3)时，本文希望匹配较高的像素有接近0的较小损失值而匹配较低的像素有接近255的较高损失值，从而使低匹配像素损失值远大于高匹配像素损失值，进而易于后续使用优化Dijsktra算法寻找最优镶嵌线。

在式(3)中，将RmQNCC(x,y)经过线性反转和归一化操作后结果范围为(0, 1)，其结果越接近0像素匹配越好，越接近1像素匹配越差。因此本文将常数ω的值定为5.5，从而使匹配最差像素的损失值达到244.7，即一个较高的损失值。

2.3 重叠区损失表达图

通过式(3)获得的重叠区对应像素匹配情况如图1所示。由图1e、f可见，本文算法检测到重叠区中匹配较差的建筑、车辆和树木等区域(图中越亮像素具有越大损失值，即匹配效果较差)，与匹配较好的道路区域有明显区别，从而为后续选取最优镶嵌线提供了便利条件。

2.4 实验结果与对比

本文使用两组分别来自城市和城镇区域的航摄影像，与同样基于全区域Dijkstra类方法寻找最优镶嵌线的Chon等[11]的方法进行对比，证明本文提出方法的可行性与优势。

城市区域航摄影像镶嵌结果如图2所示。使用本文方法获取的镶嵌线为沿建筑物的边缘、道路中的无车区域及林地区中树木的间隙，避免了穿越明显建筑物(图2a、c)；使用Chon等方法获取的镶嵌线穿越了5栋建筑物，破坏了镶嵌线附近地物的连续性(图2b、d)。

a. 重叠区左影像；c. 重叠区右影像；e. 损失表达图；b、d、f分别为a、c、e同一位置子区域。在图e和f中，越亮的像素匹配精度越低。

城镇区域航摄影像镶嵌结果如图3所示。使用本文方法获取的镶嵌线沿着道路的纹理和耕地的边界，没有破坏地物的连续性(图3a、c)；由Chon等方法获取的镶嵌线同样沿着道路区域镶嵌，但其穿越了8栋房屋，产生可见镶嵌错位(图3b、d)。

a. 本文方法；b. Chon等[11]方法；c、d分别为a、b同一位置子区域。

a. 本文方法；b. Chon等[11]方法；c、d分别为a、b同一位置子区域。

在效率方面，本文使用优化Dijsktra算法在重叠区中对每个像素位置只进行一次计算便可求出该点最小损失值，而Chon等的方法需在每个点位多次运算，因此本文方法运算时间更短(表1)。使用本文方法镶嵌重叠区尺寸为6 000 pt×10 000 pt和3 000 pt×7 500 pt图像分别用时64.83 s和35.51 s，均比Chon等的方法具有明显优势。

表1 本文方法和Chon等[11]方法镶嵌两幅航摄影像用时比较

3 结论与讨论

本文提出一种基于指数化互相关和优化Dijkstra算法的航摄影像最优镶嵌线选取方法。

1)本文构造的指数化互相关函数，相比已有方法可以更充分地表达重叠区高匹配像素和低匹配像素间的差异，从而为在匹配较好的区域选取最优镶嵌线提供便利条件。

2)本文提出的优化Dijkstra算法在重叠区沿最小匹配损失方向选取镶嵌线，相比已有方法，只需在重叠区每点位计算一次便可获得从起始点到该点的最小损失值和最优路径，从而减少镶嵌线选取时间。

3)将本文方法与同样基于全区域Dijsktra类方法选取镶嵌线的Chon等的方法对比，结果表明使用本文方法选取航摄影像镶嵌线效果更好，速度更快。

本文方法仍有改进空间。本文方法在单线程环境下操作，若通过多线程操作可进一步减少镶嵌线选取时间。另外，使用本文方法选取的镶嵌线起止点为两幅影像边缘的交点，当交点落在建筑物等独立地物上时不可避免地使镶嵌线穿越该地物，通过动态改变镶嵌线起止点可提高镶嵌线质量。以上不足将在后续研究中优化。