数字正射影像(DOM)的生产需要将由单张影像生成的数字微分纠正影像拼接成整个区域的正射影像图^[1]，这需要选择合适的镶嵌线^[2]。当前，很多国内数字摄影测量生产软件^{[3, 4]}仍需要人工编辑来完成镶嵌，作业效率低下。自动搜索影像镶嵌线对于DOM的生产就具有重要意义^[5]。文献^[6]提出利用Twin Snakes模型自动选取影像镶嵌线的方法，该方法仅对林区影像效果较好。文献^[7]采用Dijkstra算法在差分影像上搜索最佳镶嵌线，但算法复杂度较高，文献^[8]在此基础上提出结合最小化最大算法的搜索策略，很好地抑制了局部最大灰度。文献^[9]提出利用GRASP算法进行镶嵌线选择的方法，文献^[10]将该方法扩展到八邻域搜索，能够选择绕开房屋密集区域的镶嵌线。文献[11—13]提出基于Voronoi图生成镶嵌线网格的方法，并对镶嵌线进行了优化。文献[14—15]提出基于蚁群算法的自动镶嵌线选择方法，能有效地避开房屋、树木、水域等影像反差较大的区域。

本文旨在改进文献^[8]的正射影像镶嵌线的最小化最大搜索算法。首先根据影像区域范围和坐标得到待拼接影像的重叠区域，并计算其差分影像。针对文献^[8]方法的不足提出改进算法，并在差分影像上进行镶嵌线搜索。最后通过试验证明，自动生成的正射影像镶嵌线能够很好地绕开房屋等影像大反差的区域，相比于原算法，提高了搜索效率。

传统的正射影像是基于数字高程模型(DEM)对每一幅影像进行数字微分纠正得到的，由于DEM不包括地物(如房屋、树木等)的高度，这些区域在影像正射纠正的过程中没有得到正确的平面位置，产生投影差。根据透视成像原理，同一地物在不同影像上的投影差不一样^[1]。待拼接影像中对应像素灰度差异较大的区域称之为障碍区域(图 1(a))，通过障碍区域的镶嵌线会留下明显的拼接痕迹(如图 1(b)中椭圆线标示的区域)，达不到影像无缝拼接的效果。因此，正射影像镶嵌线必须避开障碍区域^{[8, 9, 10, 14, 15]}。

图 1 房屋在正射影像和差值影像上产生的障碍区域 Fig. 1 Obstacle region caused by buildings on orthoimage and differential image

图选项

在差分影像上，障碍区域表现为灰度值较大的高亮度区域(图 1(a))，搜索镶嵌线实质上是在差分影像上寻找一条可以避开高亮度区域的最优路径的过程^{[14, 15]}。

设差分影像上像素(i,j)的灰度d_ij为

点击浏览公式

式中，g_ij、g′_ij为像素(i,j)在两幅待拼接正射影像上对应像素的灰度值。

视差分影像像素看做节点、像素的灰度为节点的带权路径长度，则镶嵌线的搜索即为最优路径的搜索问题，考虑到需要绕开障碍区域，镶嵌线应为目标节点间的局部最优路径。

在差分影像上，理想的镶嵌线应沿着灰度值小的区域前进。这里给出两个镶嵌线质量评价准则^{[9, 10]}。

准则1

点击浏览公式

准则2

点击浏览公式

式中，L(path)为路径长度，即路径上像元个数；N为灰度大于给定灰度值G_t的像素集合；num(N)为集合N中的像元个数。

准则1定义为镶嵌线上像素灰度的平均值最小；准则2定义为镶嵌线上灰度值较大(灰度值大于G_t)的像素个数最少，能较好地反映镶嵌线上像素灰度的分布状况。

最小化最大搜索算法是在使局部极大值极小化的前提下进行的最优策略搜索算法^[8]。用降水位模型来描述，影像视为测地学上的拓扑地貌，像素的坐标视为该点的平面坐标、灰度视作该点的高程。给定一灰度阈值，假想该阈值所代表高程为水位高度，则灰度小于阈值的像素就在“水平面”以下。目标点之间的“水路”如图 2所示，“水位”越低，则“水路”越少。当仅存一条“水路”时，该路径认为是一条理想的拼接线。

图 2 最小化最大搜索算法示意图[8] Fig. 2 Scheme for minimizing local maximum algorithm[8]

图选项

设定一初始灰度阈值T作为初始水位，以这一阈值计算每个像素的成本值cost_ij，其定义为

点击浏览公式

灰度大于阈值的像素具有正成本值，是“水面”上的点。每次搜索都选择成本值为0的像素作为路径点，若当前路径上累积的成本值min(∑cost_ij)=0，便设当前路径为最优路径，使T=T－ΔT(这里的ΔT为阈值下降幅度)，计算新阈值下各像素的成本值，并重新搜索。重复以上搜索过程直到使min(∑cost_ij)>0为止。

在差分影像上，搜索过程保证了路径上所有像素灰度都小于阈值，得到的镶嵌线不经过高亮度区域，可满足正射影像无缝拼接的需要。从算法可知，对任意影像，T均会从最大灰度开始自动调整，因此算法具有自适应性。

文献^[8]里在路径搜索过程中采用了Dijkstra最短路径搜索算法^{[7, 8, 16]}，明显存在如下不足：① Dijkstra算法搜索时需要给定路径起点；② Dijkstra算法的时间复杂度很大^[16]，算法效率非常低；③ Dijkstra算法的空间复杂度也很大，搜索过程需要占用大量的计算机内存单元。针对以上不足，本文对搜索镶嵌线的起点选择、局部搜索和迭代判据进行了改进。

一般说来，单幅正射影像的中心区域微分纠正效果较好，边缘区域纠正效果较差，镶嵌线应远离影像的边缘区域，即镶嵌线应尽量靠近重叠区域的中心线^{[14, 15]}。路径的起点若选在中心线上，则其可能位于障碍区域，致使镶嵌线穿过障碍区域，从而导致质量较差。本文采用动态选取镶嵌线起点的方法，在以差分影像的起始行中点为中心、r为半径的区域内随机选择一个像素作为镶嵌线的起点。设差分影像宽度为w，r=αw，则起点的搜索范围为(0.5w－r,0.5w+r)。其中，α为比例因子，通常取0.25<α<0.35。通过多次搜索，总能够获得较好的镶嵌线起点。

由于随机贪心选择法具有时间复杂度低的优点^[10]，本文采用随机贪心法进行局部路径选择。在选择下一路径像素时，将备选像素中成本值最低的像素作为下一个路径点。备选像素为前方五邻域像素(如图 3所示)，灰色像素表示当前像素，白色像素为备选像素，箭头方向指示当前路径的前进方向。采用前方五邻域可避免路径迂回，使搜索变得简单，从而提高搜索效率。

图 3 前方5邻域像素 Fig. 3 Forward 5-neighbourhood pixels

图选项

由于起点选择和局部搜索都带有随机性，在每一个阈值下，都需要进行多次搜索，每次都要计算成本的累积值∑cost_ij，从中找出最小的累积值min(∑cost_ij)。

由于随机贪心搜索法在搜索上具有一定的局限性，只能使每一阈值下得到的min(∑cost_ij)为较小，若仍以min(∑cost_ij)=0为判据，会使搜索过程过早结束，从而获得质量较差的镶嵌线。为此，这里将判据改为允许路径上存在比例不超过p的灰度大于阈值的像素，即

点击浏览公式

式中，L为路径长度；p为常数，取0.001～0.05。

镶嵌线搜索的具体流程如下：

(1) 给定初始灰度阈值T。该阈值通常设置为较大的灰度值。

(2) 计算差分区域对应的成本值矩阵。各个像素的成本值按式(4)计算。

(3) 选择路径起始点，并根据影像微分纠正效果给定合适的α值。

(4) 采用随机贪心搜索法在前方五邻域内搜索下一路径点，直至差分影像的最后一行。

(5) 计算当前路径成本累积值，若为最小累积值，则设当前路径为最优路径，并将其作为最小成本累积值。

(6) 重复步骤3～步骤5，达到规定的搜索次数n为止。若满足式(5)，则设T=T－ΔT，并从步骤2开始重复以上过程；否则终止搜索，输出最优路径。

为了验证本文改进算法的有效性，在Intel酷睿Ⅱ 3.0 GHz CPU、内存为1 GB的台式计算机上用Visual C++编程实现正射影像镶嵌线搜索程序，并对包含房屋密集区和平坦农田的两幅数字微分纠正影像进行镶嵌线搜索试验，图 4为试验影像的缩略图。本节测试改进算法的运行效率，并分析所搜索的影像镶嵌线的质量。

图 4 试验影像缩略图 Fig. 4 Thumbnail of testing district

图选项

为估计本文改进算法的搜索时间，对试验影像中的两个区域(如图 4中的两个方框所示)进行搜索，并统计迭代次数和搜索时间。其中，区域1为房屋密集区域，影像大小为4500像素×5400像素；区域2主要为农田区，影像大小为3000像素×4000像素。表 1给出了搜索过程中各阈值下所需的迭代次数(最大迭代次数设为1000次)以及搜索耗时。一般情况下，阈值降得越低，搜索越困难，所需的迭代次数就越多，耗时越长。因此，对房屋较密集的区域1，算法在阈值较高的情况下即达到了最大迭代次数，搜索耗时较多；而对于纹理较简单的区域2，阈值降到很低时才达到最大迭代次数，耗时较少。

若待搜索区域影像大小为m×n像素，沿竖直方向进行搜索，本文改进算法搜索的镶嵌线平均长度为2n像素，待选像素数为5个，一次迭代的时间复杂度为O(10n)。由表 1的数据得知，一次搜索所需的迭代次数小于5000次，则平均时间复杂度小于O(c×n)，c<50000。而Dijkstra算法的时间复杂度^[16]为O(m²×n²)，由于m和n取值均在3000以上，则(m×n)²远大于c×n。利用复杂度估计，采用Dijkstra算法对上述区域进行搜索，耗时将达到约1000h，相比之下，本文方法只需要几分钟，提高了搜索效率。

鉴于Dijkstra算法用于航摄正射影像拼接过于巨大的耗时而导致的实现困难，本文将改进算法的搜索效果与数字摄影测量网格系统DPGrid中的正射影像模块所采用的基于蚁群算法^{[14, 15]}的镶嵌线搜索算法进行对比试验。采用两种算法分别对图 4中区域1的影像进行镶嵌线搜索，在原始影像上得到的镶嵌线如图 5所示；采用式(2)和式(3)作为镶嵌线的质量评价指标，在差分影像上的镶嵌线的像素统计结果列于表 2。试验中，本文改进算法的相关参数设置为：T=250，ΔT=20，α=0.3，p=0.01。

图 5 原始影像上搜索的镶嵌线 Fig. 5 Seam line on original image

图选项

从图 5可以看出，改进算法得到的镶嵌线很少经过灰度大的像素，较好地避开了差分影像的高亮度区域而沿着暗区域前进。这是因为起点的随机性，算法选择了较优的位置，避免了起点落入障碍区域。由于较矮的房屋在靠近重叠区域中间部分产生的投影差较小，在差分影像上房屋大部分区域并不表现为高亮区域，仅在房屋边缘出现部分高亮区域，使得基于差分影像的镶嵌线搜索都不能完全避免镶嵌线穿过房屋。而在影像的底部区域，两种算法都不可避免地出现镶嵌线穿过部分房屋的情况。但整体上看，本文改进算法得到的镶嵌线比由蚁群算法得到的镶嵌线能绕开更多的房屋，能更好地避免拼接缝的出现。图 6示意了本文改进算法在其他正射影像的镶嵌线搜索结果，镶嵌线均能够很好地避开房屋区域。

图 6 本文改进算法提取的镶嵌线 Fig. 6 Seam line searched with improved method

图选项

表 2的统计结果表明，在平均灰度、最大灰度、“大灰度”像素数3个方面，本文改进算法得到的镶嵌线均小于蚁群算法搜索出的镶嵌线。依据1.3节的准则1和准则2，其质量明显优于采用蚁群算法搜索的镶嵌线质量。

本文为提高最小化最大算法的效率，采用时间复杂度较低的贪心算法替代时间复杂度极高的Dijkstra算法作为镶嵌线局部搜索方法；为保持原有算法所能达到的效果，改进其迭代判据。试验表明，改进算法能够在差分影像上搜索出可避开高亮度区域的镶嵌线，从而实现数字微分纠正影像的无缝拼接，从整体效果和质量上看，采用改进算法搜索出的镶嵌线明显优于基于蚁群算法的搜索结果；保持了原最小化最大算法的自适应性，无需给定经验阈值。