0 引言

数字正射影像（Digital Orthophoto Map，DOM）是测绘行业的主要产品之一，具有直观表达丰富的地形、地物及地貌等特征的特点，在地理信息领域得到了广泛的应用^[1]．DOM的制作须选择合适的镶嵌线，由多张经过数字微分纠正后的影像根据镶嵌线拼接产生^[2]．因此，镶嵌线的自动提取方法是大范围DOM制作的一项关键技术．影像镶嵌线要求避开建筑物、植被等区域，不能因镶嵌线穿过视觉显著地物而损害影像中地物的完整性^[3]．而现阶段影像镶嵌线依旧需要大量的人工编辑，因此研究高质量的镶嵌线自动提取算法有利于提高制作DOM的效率，受到了国内外研究人员的广泛关注^[4-5]．

镶嵌线的自动提取问题通常被转化为最短路径的最优搜索问题^[6]．Chon等^[7]和刘瀚阳等^[8]利用Dijkstra算法搜索重叠区域影像中最短路径，并将其作为影像的镶嵌线，但Dijkstra算法的权值确定复杂度高、计算量大，降低了影像镶嵌线提取的效率．文献^[9-11]通过对经典Dijkstra算法的改进，虽然进一步提高了镶嵌线提取的质量，但算法效率低的缺陷依然存在．上述基于Dijkstra原理的镶嵌线提取算法均需要定义一个能量函数用于反映镶嵌线上像元的灰度变化，但不能反映重叠区域地物的差异，缺乏对影像中地物多样性的利用．启发式搜索的A^*算法具有计算复杂度低的优点，被应用于处理最短路径搜索问题^[12]．文献^[13-15]根据影像的边缘像素建立带权无向图，后结合A^*最短路径搜索算法实现正射影像镶嵌线的提取，但提取的镶嵌线质量受限于边缘检测结果的优劣．由于边缘检测算法只考虑了影像灰度差异和梯度变化，对于正射影像中各类地物丰富的光谱信息未充分利用，导致边缘检测结果中存在大量的非边缘噪声，镶嵌线穿过视觉显著物的现象未得到改善．文献^[16]在差分影像上设置代价函数，通过蚁群算法获得最优镶嵌线，然而这类算法对影像光谱感知能力弱，镶嵌线不能有效避开影像中的地物，并且蚁群算法要经历长时间算法迭代才能获得最优路径，因此算法执行效率不高．也有学者提出辅以其他数据的镶嵌线自动提取算法，依靠正射影像测区范围已有三维激光点云^[17-18]、数字线画图（DLG）^[19]、数据集矢量图^[20]、数字高程模型（DSM）^[21]等数据的辅助，采用最短路径搜索算法可有效地提取优化的影像镶嵌线，但辅助数据获取困难，并且前期需要投入大量的时间和人力完成采集与制作，因此此类算法的实用性不高．

综上所述，已有辅以其他数据的镶嵌线自动提取算法由于数据获取困难、辅助数据制作周期长，实用性不高．基于影像边缘特征的最短路径优化方法提取影像镶嵌线，仅利用正射影像中像素的梯度信息和灰度差异，对光谱特征未有效利用；提取到的边缘像素中含有过量的非边缘噪声，不能很好地避免镶嵌线穿过视觉显著物的情况发生．已有最短路径搜索算法计算复杂度高，降低了镶嵌线自动提取的效率．线性谱聚类能利用影像中的颜色、亮度及纹理特征形成具有区域一致性的像素块，有利于提取影像中地物的边界线．为提高地物边界线的提取质量和镶嵌线提取算法的运行效率，避免镶嵌线穿过影像中地物的情况发生，本文将线性谱聚类的影像分割理论引入到正射影像图镶嵌线提取算法中，通过边缘强度因子对其进行优化，同时改进传统A^*最短路径搜索算法，提出结合边缘信息优化LSC（Linear Spectral Clustering）和改进A^*算法的正射影像图镶嵌线提取方法．首先，由线性谱聚类（LSC）和A^*算法结合的方式，解决已有镶嵌线提取算法对影像光谱信息利用的缺陷．提出边缘强度因子对经典线性谱聚类算法进行优化，在类中心函数中添加边缘强度因子，充分利用影像中的边缘特征．然后，将优化的线性谱聚类算法分别作用于两幅影像的重叠区域，获得影像中地物的边界线，使用数字形态学的方法，去除边界线中的孤立噪声并获得整齐的边缘像素，形成候选影像镶嵌线．最后，由曼哈顿距离函数作为启发函数改进A^*算法，在候选镶嵌线中进行最短路径搜索，高效地提取最终影像镶嵌线．

1 算法原理

1.1 边缘信息优化的线性谱聚类算法

影像中的超像素是指影像局部具有区域一致性的像元集合而成的数据集，线性谱聚类（LSC）超像素分割算法对噪声具有良好的鲁棒性，能有效利用影像的颜色、亮度及纹理结构等特征，避免造成过分割，生成高紧凑度的地物边界.改进线性谱聚类超像素分割算法原理就是将影像像元数据映射到高维空间后聚类.

首先将图像由RGB颜色空间转为Lab颜色空间，每个像元表示为一个5维特征向量，如像元p的特征向量表示为$\left(l_p，{\alpha }_p，{\beta }_p，x_p，y_p\right)\cdot l，\alpha ，\beta$分别表示Lab颜色空间中像元p的颜色分量l， α和β；l为颜色亮度，α 和β是两个颜色通道.α的颜色包括深绿色到亮粉红色；β包括亮蓝色到黄色.x和y分别表示点p在影像中位置的横、纵坐标.针对经典线性谱聚类算法对边缘信息利用的不足，提出用边缘强度因子优化经典线性谱聚类算法，增强影像边缘信息在算法中的表达能力，从而得到高质量的地物边缘特征，边缘强度因子为

其中：E_G（p）为图像中点p的梯度值，表示边缘特征的强度；edge为提取的图像边缘二值图.设定经验阈值T=0.65，保留大于T的边缘强度因子，小于T的边缘强度因子归零.

设计核函数$\phi （p）$将图像集合V中的像素特征映射到高维的特征空间，并在高维特征空间中添加边缘强度因子，然后使用加权K-means聚类算法实现图像分割.从低维像素空间映射到高维特征空间的核函数$\phi （p）$定义：

$\phi \left(p\right)=\frac{1}{w\left(p\right)}\left[C_{\mathrm{c}}\mathrm{c}\mathrm{o}\mathrm{s}\frac{\pi }{2}{l}_p,C_{\mathrm{c}}\mathrm{s}\mathrm{i}\mathrm{n}\frac{\pi }{2}{l}_p,2.55C_{\mathrm{c}}\mathrm{c}\mathrm{o}\mathrm{s}\frac{\pi }{2}{\alpha }_p,\right.$

$\text{2.}55C_{\mathrm{c}}\mathrm{s}\mathrm{i}\mathrm{n}\frac{\pi }{2}{\alpha }_p,2.55C_{\mathrm{c}}\mathrm{c}\mathrm{o}\mathrm{s}\frac{\pi }{2}{\beta }_p,2.55C_{\mathrm{s}}\mathrm{s}\mathrm{i}\mathrm{n}\frac{\pi }{2}{\beta }_p\text{,}$

$C_s\mathrm{c}\mathrm{o}\mathrm{s}\frac{\pi }{2}{x}_p,C_s\mathrm{s}\mathrm{i}\mathrm{n}\frac{\pi }{2}{x}_p,C_s\mathrm{c}\mathrm{o}\mathrm{s}\frac{\pi }{2}{y}_p,$

$w\left(p\right)=\sum _{q\in V}\left(C_c^2\left(l_{qp}+{\alpha }_{pq}+{\beta }_{pq}\right)+C_s^2\left(x_{pq}+y_{pq}\right)+\right.$

其中，V为图像像素点集，p，q为像素点，颜色、空间和边缘信息分别由参数C_c，C_s，C_e控制.在影像上设置k个均匀分布的种子点，种子点间间隔为d，将大小为m×n的图像分为k个超像素块.设置迭代次数t，初始化类中心C_k和类内均值m_k.计算类中心邻域$\tau d\times \tau d（\tau >0.5）$内像素点p与m_k的距离.通过式（10）、（11）更新类别标记label和类中心m_k，直到到达迭代次数，完成影像的超像素分割.

1.2 改进 A ^∗最短路径搜索算法

A^∗算法是启发式搜索算法中的一种，它具有 Dijkstra 算法的优点，通过设置估价函数修正搜索节点，从而求解最优路径．

A^∗路径搜索算法的特点是使用估价函数对各个位置节点进行评估，选择起始节点 8 邻域中最小代价的位置节点进行扩展，循环这一过程，直到搜索到终止节点结束算法．估计函数表达式为

其中：F（x）为节点x的估价函数，表示起始节点经节点x到目标节点的最佳路径估计值；G（x）为代价函数，为起始节点到节点x的实际路径；H（x）为启发函数，表示节点n到目标节点的最佳路径代价估计.启发函数控制了A^*算法的搜索路径的方向，是影响路径效率和结果的关键因素.为进一步提升A^*算法最短路径的搜索效率，本文使用曼哈顿距离替换传统欧式距离作为启发函数改进A^*算法，增大距离估计的成本，减少A^*算法遍历节点数，从而提高算法效率.曼哈顿距离表示为

式中，$\left(x_n，y_n\right)$表示当前节点的坐标，$\left(x_{\text{end}}，y_{\text{end}}\right)$表示目的节点坐标.当启发函数满足式（14）的条件时，A^*算法可得到路径最优解，即估计代价H（x）小于等于真实代价h（x）. A^*算法流程如图1所示，搜索起始节点的邻域点并判断其是否为路径可行点，然后将F（x）估计函数计算出的最小值f设置为当前节点，不断循环，直到当前节点位置与终结节点位置重合，结束算法，获得最优路径.

2 结合边缘信息优化LSC和改进A^*算法的正射影像图镶嵌线提取步骤

本文将结合边缘信息优化LSC和改进A^*算法应用于正射影像的镶嵌线自动提取，通过对影像颜色、亮度及纹理结构和边缘信息在高维空间的聚类，获得具有区域一致性的地物斑块，从而减少镶嵌线穿过建筑物、道路等视觉显著物的情况.流程主要步骤包括：地物边界提取、数学形态学优化及A^*最短路径搜索.完整流程如图2所示.

2.1 地物边界获取

提取即将镶嵌的影像A和影像B的重叠数据集，分别对重叠区域应用边缘信息优化的线性谱聚类算法，设置k个种子点，将图中的视觉显著物分割为k个超像素块，从而得到A、B两个影像的地物边界线E_A（i，j）和E_B（i，j）.将两幅影像的边界线叠加，得到叠加后的边界图C（i，j），边界像素为镶嵌线可通过像素，非边界像素则为障碍像素，边界图为正射影像的候选镶嵌线.

2.2 数学形态学优化

由2.1得到的候选镶嵌线A=C（i，j）存在边界不整齐和噪声点的情况，因此采用数学形态学的方法进行优化.使用数学形态学中的膨胀和腐蚀方法对边界图进行优化.设置结构元素B，z为结构元素B的中心点.膨胀符号为$\oplus$，腐蚀符号为$\ominus$.膨胀和腐蚀计算方法分别如式（16）和式（17）所示.

2.3 改进A^*最短路径搜索算法镶嵌线检测

对优化后的边界图使用A^*算法求取最优路径，从而获得影像的最佳镶嵌线．在边界图中选取起始像素点s和结束像素点e，将s点放入Open列表，e点放入Close列表．Open列表存放的是镶嵌线不能通过的像素点位置，Close表存放镶嵌线可以通过的像素点位置．由A^*算法从起始点s开始搜索，根据启发函数判断像元是否为镶嵌线路径点，若该像元点可作为镶嵌线点，则列入Close表，否则列入Open表．不断更新Open表和Close表，直到找到终点s，则完成最短路径搜索任务，最短路径即为影像的最佳镶嵌线．

3 仿真实验

3.1 实验环境

为验证本文算法的有效性和先进性，在实验数据上进行镶嵌线提取，并与蚁群算法、文献^[8]和文献^[13]算法做对比分析．本文在运行环境为Windows11系统，CPU为Intel（R）Core（TM）i7-11800H @ 2.30 GHz，内存RAM 16 GB，GPU为NVIDIA GEFORCE RTX 3060的硬件设备上进行仿真实验．文中所有实验方法均在MATLAB R2021a上编程实现．

文中采用实验数据为无人机搭载航拍相机获取的某地同地区不同时间的正射影像图重叠区域数据集，表1列出了数据集影像的详细信息．影像分辨率分别为0.5、0.4和0.5 m，数据集1影像大小为311×300，数据集2影像大小为396×448，数据集3影像大小为448×374．

数据集包含有道路、建筑物、林地、农田及操场等视觉显著物（图3），其中数据集1主要为城市地区，包括道路、建筑和绿化区等地物．数据集2主要为乡村地区，包括小路、建筑、农田和林地等地物．数据集3主要为运动场、建筑物、农田和草地等地物．基准影像与待镶嵌影像是几何校正后用于提取影像镶嵌线的数据，分别来源于影像数据采集时各自航向和旁向的重叠部分，使要镶嵌的影像数据在采集时尽量处在摄影中心周围，进一步减弱了影像几何形变．而由于基准影像与待镶嵌影像是在不同时段拍摄，设备曝光条件不同，因此影像数据存在一定的色差．为解决镶嵌影像间色差不一致的问题，提高镶嵌影像的质量，本文运用直方图匹配的方法使基准图像和待镶嵌影像具有相似的直方图分布，从而达到匀色的目的．图3c为数据集中待镶嵌影像匀色后的结果，匀色后的待镶嵌影像具有和基准影像一致的色调．

3.2 基于边缘信息优化LSC算法影像地物边界线提取

图4为重叠数据集影像分别经过边缘特征信息优化LSC超像素分割后的结果，应用边缘特征信息优化的LSC算法时，数据集1、数据集2均设置超像素块k=42，因此迭代种子点数也为42，种子点的距离d=48个像元，数据集3设置超像素块k=56，种子点的距离d=60个像元．从图4中可以看出，在对影像进行分割时，该方法利用影像的颜色、亮度、纹理结构及边缘等特征，形成的地物边界线将视觉显著物分割，使得形成的超像素块具有良好的区域一致性，避免了大量边界线穿过视觉显著物的情况．同时提取的地物边界未产生大量的孤立噪声，边缘更加整齐．因影像的采集时间不同，影像数据中部分地物面积发生了微小的变化，当对基准影像和待镶嵌影像分别进行LSC超像素分割时，所获取的地物边界结果有一定的差异．因此将基准影像和待镶嵌影像获取的边界结果叠加，形成最终地物边界线．

3.3 镶嵌线提取结果与分析

图5a、5b、5c与5d分别为蚁群算法、文献^[8]方法、文献^[13]的A^*方法及本文方法在实验数据集1上的镶嵌线提取结果．从结果上看本文方法提取的镶嵌线与视觉显著物（建筑物、道路及绿化区）边界重叠，穿过地物的情况较少．蚁群算法、文献^[8]和文献^[13]方法提取的镶嵌线穿过了道路及绿化区，并且穿过地物的像素点数较多，损害了地物的完整性．图6a、6b、6c及6d分别为蚁群算法、文献^[8]算法、文献^[13]算法及本文方法在实验数据集2上的镶嵌线提取结果．由数据集2中的实验结果可见:文献^[13]中采用的A^*算法提取的镶嵌线穿过了道路，虽然未对其他地物造成影响，但损害了道路的完整性; 蚁群算法和文献^[8]的方法对比文献^[13]方法，镶嵌线穿过部分农田和小路．本文方法将边缘特征信息优化的LSC超像素分割结果通过数学形态学优化后，以地物边界作为候选镶嵌线，减少了镶嵌线穿过视觉显著物的像元数量，提取的镶嵌线大部分与地物边缘重叠，未对其他地物造成损害．从图7数据集3的实验结果中可以看出，本文方法相比其他方法得到的影像镶嵌线穿过的地物更少，进一步验证了本文所提算法的有效性．

由表2定量分析可得：虽然文献^[13]的A^*算法得到的镶嵌线路径长度较短，但产生了过多穿过地物的像元，蚁群算法由于算法迭代次数多的原因，在提取影像镶嵌线时耗费了更多的时间．本文方法相比蚁群算法、文献^[8]和文献^[13]的算法在数据集1的实验中，穿过地物的像素数分别减少173、95和195个; 在数据集2的实验中，本文方法相比蚁群算法、文献^[8]和文献^[13]的算法穿过地物的像元数分别减少120、35和380个，更好地保留了地物的完整性．数据集3的实验中，本文方法提取的影像镶嵌线只穿过部分道路，穿过地物的像元数量仅为89个．在算法效率上，本文方法通过对经典A^*算法的改进，由曼哈顿距离函数替换传统欧式距离函数，并增加了代价函数计算成本，降低了计算的冗余．对比其他方法，用时均有降低，进一步提高了算法的运行效率．

4 结论

针对已有镶嵌线提取算法存在未利用影像光谱信息，导致镶嵌线穿过视觉显著地物，损害影像中地物的完整性的不足，地物边缘不规整以及算法效率低的缺陷，本文提出结合边缘信息优化LSC和改进A^*算法的正射影像图镶嵌线提取方法．

1）将经典线性谱聚类与A^*算法结合，有效利用影像的光谱特征，将影像分割成不同地物类别，得到不同地物类别的边界线，解决已有正射影像镶嵌线提取算法对影像光谱特征利用不足的问题．

2）引入边缘强度因子优化经典线性谱聚类算法，在核函数中增加对边缘信息项的考虑，并通过数学形态学的方法获得了更加规整的地物边界．

3）改进传统A^*算法在地物边界中搜索最短路径，完成镶嵌线的提取．由曼哈顿距离函数替换欧式距离函数，提高算法运行效率．

实验结果表明本文所提方法可高效、高质量地提取到影像镶嵌线，有效地绕过了视觉显著地物，满足实际正射影像图制作的应用需求．

参考文献