一种复杂道路网中心线自动提取算法

刘昌振，马红

(1.重庆市勘测院，重庆 401121； 2.重庆市地理国情监测工程技术研究中心，重庆 401121)

1 引 言

道路作为地理信息要素的重要组成部分，是数据生产过程中重点采集的对象，道路中心线是路径规划、导航等应用的基础数据。基础测绘数据入库一般要求提取道路中心线，并建立正确的拓扑关系和连通性。在实际生产中，一般先采集道路边线，再根据道路边线获取道路中心线，因此，实现从道路边线中自动提取中心线可以有效提高生产效率。目前，关于中心线自动提取的研究较多，如董箭等[1]提出了一种基于缓冲区边界相向逼近求交模型的中心线生成算法，杨得志等[2]提出一种单位圆滚动追踪算法提取中心线，艾廷华等[3]、钟世彬等[4]、罗小飞等[5]、李功权等[6]通过建立约束Delaunay三角网提取中心线，并基于三角网的邻接关系确定道路起点和交叉口，杨伟等[7]基于Delaunay三角网从众源轨迹数据提取中心线，朱庄生等[8]基于道路轮廓自动生成道路中心线，乔庆华[9]等通过改进Voronoi图提取面状河流中轴线，江岭等[10]提出一种基于欧式距离分配的面状河流图斑中轴线提取方法，王新生等[11]对比了Voronoi图矢量法和欧式距离区域分配栅格法提取复杂多边形中轴线，胡鹏等[12]总结和对比了多种中心线提取的算法，并提出了理论上较为严密的点对序列法和地图代数多边形中轴法。以上算法对提取中心线有较好的效果，基于三角网的邻接关系可以确定简单道路的交叉口，但很难正确提取复杂道路交叉口。针对以上问题，本文提出一套新的、可应用于实际生产的道路网中心线自动提取算法，可以从较复杂的道路网中自动提取中心线并构建正确的拓扑关系。

2 道路网中心线提取算法原理

2.1 道路网交叉拆分

道路边线的成果数据一般是连通的，较复杂的道路可能有多个交叉口，直接对原始道路网提取中心线难度较大，提取效果也不理想。通过交叉拆分的方式将道路网拆分成简单道路边线对，此处的简单道路边线对，指由两条边线组成、无交叉口的道路。本文路网交叉拆分的思想是设置最大宽度阈值，从一条道路边开始，以最大宽度阈值建立缓冲区，搜索其他道路边，获得和缓冲区相交的所有边线，取搜索结果中距离起始边较近、在缓冲内长度较长的道路，计算距离起始道路的最短距离，截取在缓冲区范围内的部分，用比最短距离稍大的宽度(本文使用最短距离1.5倍)建立截取部分的缓冲区，得到起始道路边在缓冲区范围内的部分，最终获得的这两部分组成道路边线对，并记录边线对的信息。依次类推，直到处理完所有的边线，获得所有边线对。

道路网交叉拆分原理如图1(a)所示，首先根据最大宽度阈值为道路边线a建立缓冲区A，获得和缓冲区A中相交的道路边线，取在缓冲区A长度最长的边线b，计算到边线a和到边线b的最短距离，用比最短距离稍大的距离(本文取最短距离的1.5倍)为边线b建立缓冲区B，获得边线a在缓冲区B内的部分a1，道路边线a1和b组成一个简单道路边线对，对剩余的道路边线用同样的方法建立道路边线对，直到所有道路边线拆分完毕，图1(b)中的道路边线对1、2、3就是实例数据交叉拆分的结果。

图1 道路网交叉拆分

2.2 约束迭代三角网建立

获得边线对后，对两条边线建立约束三角网。道路边线作为约束建立三角网，符合提取中心线需要的三角网在两条边线之间。经过第一步拆分的道路边线对，长度差别不大，我们通过最短边线法建立三角网。算法过程如图2(a)所示，取第一条边线的前两个节点a1、a2和第二条边线的前两个节点b1、b2，节点a1、a2、b1构成一个三角形，节点b1、b2、a1构成另外一个三角形，计算第一个三角形边a2b1的长度和第二个三角形b2a1的长度，取长度小的边所在三角形为第一个三角形，如图2(a)取节点a1、a2、b1组成的三角形为第一个三角形，这个三角形的其中两个节点a1、a2在第一条边线，另外一个节点b1在第二条边线。取a1、a2所在边线的节点a2、a3和第二条边线的节点b1、b2，以同样的方式获得第二个三角形，以此类推，直到处理完两条边的所有节点，最终获得两条边线的约束迭代三角网，结果如图2(b)所示。三角网建立的关键在于约束和迭代，两条边线约束可以保证三角网始终在两条边线范围内，通过迭代获得所有边线约束的三角网。

图2 建立迭代约束三角网

2.3 中心线提取和连接成网

通过迭代建立的约束三角网，每一个三角形中的两个节点为其中一条道路边节点，另外一个点属于另外一条道路边的节点，通过记录三角形的生成顺序，连接三角形中不属于道路边的边线中点，即可获得道路边线对的中心线。

获得所有道路边线对的中心线后，依据道路交叉拆分设置的最大宽度阈值，在生成中心线的起点和终点搜索周围是否有中心线生成，一般连接分为如下两种情况，第一种连接搜索到的中心线组成一条中心线，第二种是将起点或终点连接到搜索到的中心线上。经过最后这一步处理，即可获得较完整的道路网。连接成网的时候可以根据实际情况设置条件(例如设置匝道中心线只能和匝道中心线或高速中心线连接)，从而控制最终的道路网，中心线自动提取和连接成网如图3所示。

图3 中心线自动提取和连接成网

3 实验与分析

我们用C#语言基于ArcObjects编写程序实现以上算法，以重庆市 1∶2 000地形图生产航测立体采集成果数据为实验数据。

3.1 几种典型道路网提取结果

道路网中心线提取的难点和关键点在于交叉口的自动提取和连接，以三种典型道路网为例，展示本文算法中心线提取结果。

(1)乡村道路网

乡村道路形状不规则，交叉口多且类型复杂。乡村道路网中心线提取结果如图4所示。

图4 乡村道路网

(2)街区道路网

街区道路形状规整，某些地方交叉口多。街区道路网提取结果如图5所示。

(3)立交路网

立交路网一般由匝道连接不同高速，交叉口众多，不同的立交形状差别大。立交路网提取结果如图6所示。

图5街区道路网 图6立交路网

3.2 多种路网组合

以一幅1∶2 000地形图中的道路网为例，自动提取道路网中心线，原始数据有一条省道，两条乡道和数条机耕路交叉成网，提取结果如图7所示。

图7 多种路网组合

从提取结果来看，道路中心线基本可以正确提取，大部分道路交叉口可以正确连接，14个道路交叉口中，有12个正确连接，2个未连接，只需要人工处理2个未连接的交叉口即可获得最终的结果。

4 结 论

本文提出一种新的道路网中心线自动提取算法，通过道路网交叉拆分、建立迭代约束三角网和中心线提取并连接成网三个算法过程。可以快速、准确地提取道路网中心线。实验表明：本文提出的算法可以提取多种复杂类型的道路网中心线，提取效果较好。