三角网模型多目标加权最短路径的特征线提取

朱 庆，尚琪森，胡 翰，于昊加，钟若飞，丁雨淋,5

（1.西南交通大学地球科学与环境工程学院，四川成都611756；2.国土资源部城市土地资源监测与仿真重点实验室，广东深圳518034；3.首都师范大学北京市成像技术高精尖创新中心，北京100048；4.香港理工大学建设及环境学院，香港999077；5.香港中文大学太空与地球信息科学研究所，香港999077）

近年来倾斜摄影测量已经成为城市三维建模的主要途径[1-2].不同于如地面等手段重建的三维模型，倾斜摄影测量三维模型会受到摄影测量精度不足、构网时对密集匹配点云抽稀简化等因素的影响，噪声明显且难以保留如建筑物拐角棱线、道路边界等的完整尖锐特征，需要通过修复才能满足真实感展示和分析等深度应用需求.特征线是模型修复的基础[3]，但这些区域模型规则性缺失、特征不明显，人工交互式选取特征点的特征线提取方式效率低、效果差，亟须一种自动化、智能化的快速特征线提取方法.

现有三维模型的特征线提取方法主要分为基于面和基于边两种类型：

1）基于面的方法要么通过多个种子点各自生长出曲率一致的面，将它们的交线作为特征线[4]；要么计算局部曲率，提取特征点或特征边，将它们连接起来得到完整特征线[5].基于面的方法依赖曲率等对噪声敏感的微分不变量[6]，所以通常针对点、面密度均匀的平滑模型，难以顾及粗糙的复杂模型中细碎三角形产生的噪声；同时计算量大，不适合特征线的快速提取，提取结果也没有基于现有三角形边，难以利用.

2）基于边的方法通过计算模型三角形边的二面角等手段来估计微分量从而提取特征边，设定阈值将满足条件的特征边连接成闭合环提取到特征线[7].或利用正规张量框架[8]、局部邻域的矩[9]等来提取特征线.基于边的特征线提取方法计算简单、速度快，但目标性差、正确率低，需要后续处理对结果进行过滤[10].

针对现有方法面对数据密集、噪声明显的倾斜摄影测量复杂模型特征线提取存在的严重缺陷，本文提出了一种快速准确的基于多目标加权最短路径的半自动智能化方法.

1 特征线提取方法描述

本文方法流程如图1所示.首先对倾斜摄影测量三维模型进行预处理重建拓扑；然后选取两个特征点作为目标特征线的起终点，生成包围盒，忽略盒外无关模型，并使用有向图结构组织模型数据；之后考虑距离、方向和变化趋势等多种因素对有向图边进行加权；最后利用Dijkstra算法获取起终点间的加权最短路径，提取到目标特征线，并对棱线特征进一步进行修复，确保质量.

图1 基于多目标加权最短路径的倾斜摄影测量三维模型特征线提取算法流程Fig.1 Flow of feature line extraction from3D model of oblique photogrammetry based on multi-objective weighted shortest path

1.1 数据的预处理

由倾斜摄影测量获取的三角网模型虽然含有或者隐含正确拓扑关系，但在如OSGB等格式的三维模型数据中顶点与纹理坐标是一一对应关系，这些格式的数据会将对应多个纹理坐标的一个顶点拆分为多个顶点，具体为共用同一顶点的三角面片可能有纹理图片上不连续的贴图，这样同一空间位置就会出现多个顶点，它们空间坐标相同、纹理坐标不同.这种数据组织形式虽然有利于三维模型的绘制[11]，但模型却丢失了完整、连续的拓扑结构，出现三角网局部的“断裂”，难以获取顶点和面片的邻域信息[12]，增大了模型几何处理[13]的难度.

为了解决该问题，本文采用如图1所示的模型计算与更新方法：首先通过预处理对模型进行拓扑重建[12,14]，预处理结果就是待计算数据，之后所有几何处理都针对待计算数据，计算结果用以更新显示数据和文件.

其中重建拓扑的预处理主要有以下步骤：

步骤1 维护一个用于存储处理结果的空三维模型对象T和一个以顶点坐标为关键码、顶点在T列表中的索引为值的哈希表M.

步骤2 遍历原始模型中的三角面片.

步骤3 遍历每个面片中的顶点.对于每个顶点，首先根据M判断该顶点位置是否已经存在其它顶点，如果不存在，就添加该顶点相关信息和其所在三角面片相关信息到T中，并将顶点坐标信息和其在模型T列表中的索引插入到M；如果存在，就通过M找到该位置顶点的索引，并按照查找到的索引添加该顶点所在三角面片的相关信息到T中.

步骤4 对三角面片的遍历结束后，模型T就是完成拓扑重建的预处理结果.

1.2 数据的组织

原始数据经过预处理后虽然有了完整、连续的拓扑结构，但仍以顶点和三角面片的形式进行组织，该组织方式难以对边进行加权，获取邻接顶点、面片和最短路径也要付出很大代价[12]，同时边的方向也是加权目标之一，所以本文以有向图结构对三角网模型进行组织.

如图2所示，为了获取指定特征线，首先在模型现有顶点中选取两个特征点作为目标特征线的起终点，为了提高计算效率，再根据两个特征点的坐标极值生成包围盒，忽略模型中包围盒外无关三角网.然后遍历模型中的三角面片，将三角形每条边的顺、逆时针两个方向分别录入有向图，方便后续加权和最短路径求解[15].

图2 数据的组织Fig.2 Data organization

1.3 多目标加权

将模型以有向图形式进行组织后，就要考虑多种影响特定特征线提取的因素对有向图边进行加权.王钦瑞等[5,16-17]从曲率相似性、顶点间距、边的方向、三角面片法矢夹角方面对特征线进行提取，验证了其可行性和有效性，本文为了提取到理想特征线，从图3所示的三角形边长、边的方向和邻接三角形平面变化趋势3个方面对有向图边进行加权.△ABC和△BCD有公共边BC，点A1和D1分别为点A和D在公共边BC上的垂足，则与的夹角β就叫做共边三角形二面角，该角可表示共边三角形所在平面间的关系.二面角范围为 0°～180°，180°时表示两三角形共面.

图3 加权目标Fig.3 Weighted objects

本文特征线提取方法基于最短路径，将有向图边初始权重设置为模型对应边长，可一定程度上控制寻径结果与理想特征线间偏差从而提取到目标特征线.所以首先计算有向图两节点在模型中对应顶点的空间距离，对边进行距离加权.

目标特征线起终点通过交互式选点确定，根据方向给边设置一定的通过代价就可避免寻径方向与目标方向相反.图4所示为方向加权方式，图中∶黑色实线为当前图边，红色实线为交互式选取的起点、终点构成的向量，红色虚线由红色实线平移而来；α为有向图边在模型中对应边的方向向量与起终点向量之间的夹角，取值范围为0°～180°.计算模型中每条有向图边对应的方向向量与起终点构成向量的夹角：若为锐角，说明该方向与寻径方向一致，不作处理；若为钝角，则说明该方向与寻径方向相反，就将该边权重加上一个远大于模型三角形边长的值.

图4 方向加权Fig.4 Weighting by direction

特征通常是指曲面上具有至少一个较大主曲率的区域[6]，倾斜摄影测量三维模型的编辑和修复所需特征线不是传统沿主曲率方向极值点连线所构成的特征线[18]，而是基于现有三角形边的特征线，所以要对每条边进行特征识别.特征线处总伴随着模型的突变，计算模型中有向图边对应的共边三角形二面角大小就能快速识别该边特征.通过设定二面角阈值[7]可判断边的特征是否明显：若二面角小于阈值，说明模型在该边变化明显，可作为特征线的一部分，不作处理；若二面角大于阈值，就可认为两三角形共面，模型在该边没有发生突变，特征不明显，就将该边权重加上一个远大于模型三角形边长的值，从而在寻径过程中避开此边.

综合上述3个因素，本文通过式（1）对有向图边加权.

式中：dcost为加权距离即为通过代价；d为有向图边对应的三角形边长；β为模型中对应边的二面角，取值范围为0°～180°；γ为二面角阈值；k为远大于三角形边长的常数.

1.4 特征线提取

考虑多种因素对有向图进行权重设置，将不符合特征识别条件的边权重设置为远大于边长的值从而控制边的通过性[19]，就能通过获取两特征点之间的最短路径来提取理想的目标特征线[20-21].

最短路径算法可分为标号设定（label setting，LS）算法和标号改正（label correcting，LC）算法.LS算法不能处理权重为负值的网络，但权重为正时效率高[21].本文以加权有向图的方式组织数据，且权重均为正值，综合空间复杂度、时间复杂度、易实现性等因素，采用LS算法中最具代表性的Dijkstra算法获取最短路径[20-21].

1.5 棱线修复

在提取到特征线后，为了解决模型直线型棱线处结构粗糙、噪声较大、特征不明显的问题，拟合提取结果所经顶点到起终点所在直线实现对棱线尖锐特征的修复.

具体拟合方法如图5所示，利用式（2）把特征线上的顶点O投影到由起、终点S、E构成的向量上，得到投影向量，再通过已知的S点坐标计算出投影点P的坐标.将O点坐标修改为P点坐标，完成O点向所在直线的拟合.

图5 特征线的拉直Fig.5 Straightening of feature line

2 试验与分析

本文选用无人机倾斜摄影测量获取的实景三维模型进行试验，首先通过实际提取和修复结果，验证了本文特征线提取和修复方法的可行性与有效性.之后与单一目标加权方法进行对比，说明各个加权目标的有效性，验证了综合考虑时效果最优.最后与现有方法进行对比，突显了本文方法的优越性.

2.1 特征线提取与修复结果

地物模型特征线处总伴随着由诸如河面与河岸高差、道路与道边差异等因素造成的突变.所以在面对不同地物特征线的提取时，设置合适的二面角阈值就能利用本文方法提取到较为理想的结果.

不同场景和地物的特征提取需求不同，二面角阈值大小可交互式的通过提取效果来确定，本文将二面角阈值设置为160°进行实验，不同地物利用本文方法提取到的特征线结果如图6所示.红色点为提取结果所经模型顶点，均具有明显特征，提取结果较为理想.同时也体现出本文方法不仅适用于直线特征的提取，对曲线甚至不规则特征也有很好的提取效果.

验证了本文提取方法的有效性后，利用1.5节中修复方法，对建筑物棱线进行修复.修复前后模型如图7所示，红色线框内为目标棱线所在区域，相比修复前模型，修复后模型的棱线区域结构清晰、特征明显.

图6 特征线提取结果Fig.6 Feature line extraction results

图7 建筑物棱线修复效果Fig.7 Remediation of the edge line

2.2 单一目标与多目标提取方法对比

不同加权目标的特征线提取结果如图8所示.其中模型变化趋势用有向图边在模型中对应的二面角大小衡量.

由图 8（b）、（c）可知：只考虑距离时，提取结果是起终点间路程最短的路径；只考虑方向时，提取结果是保证正确寻径方向下步数最少的路径.两种方法均无法保证提取结果具有明显特征，提取效果很差.

由图8（d）可知：仅考虑模型变化趋势时，提取效果与本文方法最为接近.该方法在保证提取结果有明显特征的前提下找到了步数最少的路径，但只考虑了局部特征，没有顾及寻径结果与目标特征线间的整体偏差，所以提取效果与本文方法有一定差距.

对比图 8（a）～（d）可知：距离、方向和模型变化趋势对特征线提取结果均有影响，综合考虑3种因素时提取效果最好.

图8 不同加权目标的提取结果Fig.8 Extraction results of different weighted objectives

2.3 与交互式等特征提取方法对比

利用不同方法得到的特征线提取结果如图9所示，图中虚线框为目标特征所在区域.图9（c）为利用文献[10,22,23]中综合面曲率和边锐利程度方法的特征线提取结果，图9（d）～（f）分别是将边锐利度[10]阈值设置为10000、20000 和 50000 对图 9（c）中特征线进行过滤得到的结果.

对比图 9（a）、（b）可看出：本文方法与交互式选点方法提取效果相当，但仅需选取两点，大大提升了效率；同时量化特征，避免人工选点主观性和随机性强的问题.

图9（c）～（f）显示传统方法对噪声敏感、目标性差，提取结果难以利用.对比图 9（a）和图 9（c）～（f）可明显看出本文方法面对复杂倾斜摄影测量三维模型时的优势：目标性强，能提取到指定特征线；抗噪声能力强，能够正确提取粗糙复杂模型的特征线.现有方法提取结果即使经过一系列过滤，效果仍和本文方法有较大差距.

图9 特征线提取效果对比Fig.9 Comparison of extracted feature lines

3 结束语

本文提出的特征线提取方法对倾斜摄影测量三维模型提取效率高、效果好、目标准.同时，该方法还具有较强的适应性和可拓展性特点，不仅能提取不同类型特征线，还能通过引入新的加权目标来满足特定情况下的特征线提取需求.

进一步的研究将在几何特征提取基础上，综合考虑影像纹理特征，提高各种复杂特征提取的自动化与智能化水平和能力.