顾及形态特征约束的大范围道路中心线提取算法_蔡昊琳.pdf

第 卷第期 年月测绘科学 作者简介：蔡昊琳（），女，山东威海人，博士研究生，主要研究方向为计算机自动制图综合算法。：收稿日期：基金项目：国家自然科学基金项目（）；国家重点研发计划项目（）；中国测绘科学研究院基本科研业务费项目（，）通信作者：殷勇 副研究员 ：引文格式：蔡昊琳，殷勇，艾波，等 顾及形态特征约束的大范围道路中心线提取算法 测绘科学，（）：（，（）：）：顾及形态特征约束的大范围道路中心线提取算法蔡昊琳，殷勇，艾波，吴创奇，郭沛沛（山东科技大学 测绘与空间信息学院，山东 青岛 ；中国测绘科学研究院，北京 ；西安市勘察测绘院，西安 ）摘要：针对规则格网分块提取大范围路网（地级城市及以上）中心线算法在分块边界处极容易出现结构严重变形等问题，该文提出了一种顾及形态特征约束的大范围道路中心线分块提取算法。首先，基于道路面数据获取道路边线数据，计算其曲率，探测边线中的平直部分；然后，以边线中的平直部分作为分块基础，建立“转盘法”将大范围道路分割为多个小范围道路；最后，以分割的小范围道路作为处理单元，基于德洛内（）三角网分区域进行中心线提取，并在分割边界处进行中心线拟合，完成大范围路网中心线提取，提高了中心线提取的准度和精度。以江苏省某市地理国情普查道路数据进行实验，结果表明，该文方法所提中心线形态均自然、光滑，且效率较规则分块方法提高 倍。关键词：大范围道路；中心线提取；分块策略；形态特征【中图分类号】【文献标志码】【文章编号】（），（，；，；，）：（），；，：；测绘科学第 卷引言道路作为地图骨架要素，在城市规划、自动驾驶、智慧城市建设等领域发挥着重要的作用。截至目前，我国开展了多项国土利用调查，如第二次国土资源调查、地理国情普查、第三次国土资源调查等，获取了大量道路面数据。而如何从形态复杂、数据量大的原始数据中提取道路中心线实现道路多尺度表达一直是研究的热点和难点问题。根据数据源的不同，将道路中心线的提取分为两种方式：基于栅格数据和基于矢量数据。目前，基于矢量数据提取道路中心线主要有种算法：中轴线提取、直骨架 和 三角剖分 。很多学 者 对 基 于 矢 量 数 据 提 取 道路中心线的算 法做 了 大量 的改 进 和 优 化，消 除了抖动问题，提高了十 字路 口 等复 杂 区 域 提 取的准确性。虽然基于矢 量数 据 提取 道 路 中 心 线的算法 较 为成熟，但 只 适 用 于 小 范 围 提 取。随着提取范围越 来越 大，要 处理 的数 据 量 也 越 来越多，按照以上方法对 大范 围 道路 面 直 接 提 取道路中 心 线时计 算 量 大，所 需 时 间 长，对 计 算机性能要求高。分布式计算和并行计算是提高海量数据综合效率的有效方式，基于此，将分块引入到大范围道路提取中心线中。但分块方法直接影响数据处理的质量和效率，因此，选择合理的分块方法尤为 重 要。现 有 分 块 方 法 主 要 为 规 则 格 网 分块 ，基本原理是先生成研究数据的最小边界矩形，构建的规则格网，用生成的格网分割道路面。这种分块方式过程简单，所需时间短，但每个分块区域中道路面积不均衡，导致每块之间的计算量相差大，且不合适的分割边界会降低道路中心线提取的准确性和稳定性，需要对提取得到的结果在边界连接处进行复杂的中心线修复。文献 在规则格网分块的基础上顾及面积均衡进行网格的分割和合并，并在生成细碎图斑的分割边界处进行边界检测和修复。该方法充分考虑了面积均衡对计算效率的影响，但只做了细碎图斑处的边界修复，未对边界处更复杂的连接模式进行检测和修复。为此，本文提出了一种顾及形态特征约束的大范围道路中心线分块提取算法。首先，在远离道路弯曲处的平直区域选择合适的分割位置生成分割线进行道路分割，得到道路粗分块结果；然后采用改进的约束 三角网的方法分块提取道路中心线，在接合处进行中心线拟合生成大范围道路的完整中心线。算法原理本文方法的流程见图。图流程图 探测道路平直部分分析规则格网分块结果可以发现在道路弯曲处分割会出现接合处变形严重的问题，在平直部分分割拟合效果较好。因此，本文算法首先探测道路平直部分。主要思路是将道路由面要素转为线要素，此时，道路边线可看作曲线，其曲率可以定量表示道路的弯曲程度。通过计算道路边线的曲率判断道路的弯曲处和平直处，去除弯曲处即可得到道路的平直区域。计算曲率曲线的曲率是指曲线上某个点的切线方向角对弧长的转动率，表明曲线偏离直线的程度。曲率越大，曲线的弯曲程度越大。在连续的情况下曲率有着严格的数学定义，其计算见式（）。（）（）（）（）（）（）（）（）式中：（）为点上的曲率；（），（）为点上、轴的一阶导数；（），（）为点上、轴的二阶导数。但道路边线是复杂的非规则曲线，由一系列离散点构成，不存在解析表达式。由于曲率反映的是曲线上邻近点之间的相对位置关系，因此，离散点曲率可以基于局部离散点的相对位置关系得到。本文选取道路的个相邻离散点确定的二次曲线的曲率作为中间点（，）的近似曲率，如图所示。第期蔡昊琳，等 顾及形态特征约束的大范围道路中心线提取算法图个相邻离散点确定的二次曲线 加密道路边线节点道路边线的原始节点并非等距，直接用原始节点进行近似曲率计算，会造成计算得到的曲率与该点真实的曲率有较大的差距。因此，采用加密节点的方式使得道路边线上节点的间距尽量相等。加密的点数越多，道路边线就会由原本离散的分布更接近于连续的分布，该点曲率的计算就越准确。本文中，将加密之后的节点数量确定为原本总节点数量的 倍。用道路的总长度除以加密后的节点个数，即可获得节点之间的加密间距。加密公式如式（）、式（）所示。（）式中：表 示 加 密 后 的 节 点 总 数；表示原本节点总数。（）式中：表示加密距离；表示道路总长度。加密后的结果如图所示。图加密节点 缓冲区过滤越平直的线曲率越接近于，直线的曲率为。结合实验，认为曲率 的点所在的线为直线，曲率 的点为弯曲点。当分割线远离道路弯曲处时，生成的中心线在边界处较为平滑，因此，通过缓冲区处理去除弯曲点一定范围内的道路边线，见图（），得到远离道路弯曲处的平直道路边线，见图（）。经实验验证，缓冲区半径为 时，即便分割线靠近探测得到的平直道路线端点，生成的中心线也不会产生抖动。经过缓冲区过滤后，会得到大量平直道路边线，考虑分块数量以及计算效率，可增加长度阈值筛选部分平直道路边线参与后续步骤。图缓冲区过滤 建立转盘分割算法获取道路平直区域后，以每个平直区域的中间横截线对道路面进行分割，既可以将大范围道路网切分为面积较小的子区域，又可以避免分割线对中心线提取形态的影响。然而，由图（）可以发现，作业区域内获取的平直区域较多，如何自动计算每个平直区域的中间横截线成为一个难点。为此，本文建立转盘分割算法，以每一个平直区域的边线为计算基本单元，自动捕捉与该边线属于同一平直区域的对侧边线，即建立平直道路边线的一一对应关系。转盘分割算法的核心思想是从最长的平直道路边线开始旋转一定角度，探测到与该旋转边线存在交点的另一条平直道路边线，连接该交点与旋转边线的中点，并按一定距离在两点间进行内插，若所有内插点均位于道路面内，则认为中点与交点的连线为道路面的一条分割线。主要步骤如下：）直接求交。如图（）所示，将旋转线旋转 ，直接求得交点。）转盘求交。如图（）所示，如果旋转线旋转 没有得到交点，则依次将该线段顺时针旋转测绘科学第 卷 、和 ，直至求得交点为止。若旋转至 时仍然没有与其相交的线，则舍弃该线段。图转盘分割算法 ）判断交点正确性。如图（）所示，旋转求得的交点不一定正确，相交线段有可能为另一道路面的道路边线。因此，求得交点之后还需要进一步判断交点是否正确。判断方法为：连接旋转线的中点和相应交点，判断连线上按比例分割的点是否都在道路面内。若如图（）所示，存在比例点不在道路面内，则舍弃该错误交点，按转盘法重新旋转相应角度进行判断；若如图（）所示，所有比例点都在道路面内，则保留该正确交点。记录正确交点和对应的旋转线中点。图生成相应比例点 ）分割道路面。连接旋转线的中点和转盘法得到的对应交点，生成分割线，如图（）所示。在分割线处将大范围整块道路分割成细碎道路图斑，如图（）所示。图分割 中心线提取及拟合用改进的约束 三角剖分的方法提取每块道路中心线，主要分为两步：首先，在道路内部生成 三角网，如图所示。根据相邻三角形的数量将三角网的三角形分为类，只有个相邻三角形的为类三角形，有个相邻三角形的为类三角形，有个相邻三角形的为三角形。然后，对于类三角形，连接相邻边的中点和其对应的三角形顶点；对于类三角形，连接两个相邻边的中点；对于类三角形，连接三角形重心和相邻边的中点，得到中心线。图 三角网 提取每块道路的中心线后，需要在接合处对中心线进行拟合，从而生成大范围道路的完整中心线，如图所示。图中心线拟合 第期蔡昊琳，等 顾及形态特征约束的大范围道路中心线提取算法实验分析依托中国测绘科学研究院研制的 地图工作站，嵌入本文提出的分块算法，通过与规则格网分块方法进行对比，对本文方法的合理性和有效性进行验证。实验数据与环境实验数据选自江苏省某地区地理国情普查道路数据，空间范围为 。实验包括两部分：在实验数据中，选取一小范围空间数据，分别使用规则格网分块、本文方法提取道路中心线，并通过与未分块的中心线提取结果进行对比，进行中心线形态保持效果及计算效率对比分析；选择实验区域内全部数据，此时因数据量较大，无法应用未分块方法提取中心线，分别使用规则格网分块、本文方法提取道路中心线，进行效率对比分析。实验测试的环境为单台 机，装备 位操作系统，为 （），主频为 ，内存（）为，硬盘总大小为 （固态）。效果分析本文根据分割线穿越的三角形类型将实验区域分为简单区域和复杂区域，简单区域定义为分割线穿越类三角形的区域，复杂区域定义为分割线穿越类三角形的区域。从简单区域和复杂区域对两种分块方法进行效果分析。简单区域可视化分析）如图 所示，当分割线穿越类三角形区域且分割线与道路边线接近垂直时，规则格网分块和本文分块方法提取的中心线与参考结果基本相同。图 分割线穿越类三角形区域（平直区域）（）如图 所示，规则格网的分割线穿越类三角形区域时会出现分割线靠近十字路口的情况，此时，提取得到的中心线出现抖动；而本文方法经过缓冲区处理和长度筛选避开了该区域，得到的结果与参考结果完全相同。图 分割线穿越类三角形区域（靠近十字路口）（）如图 所示，规则格网的分割线穿越类三角形区域时会出现分割线与道路边线平行的情 况，此 时，提 取 到 的 道 路 中 心 线 为 两 条，与原始道 路 面 结 构明 显不一致；而 本 文 通 过 转盘分割算法生成的分割线只会与道路边线垂直或成 一 定 锐 角，得 到 的 结 果 与 参 考 结 果 完 全相同。图 分割线穿越类三角形区域（与道路边线平行）（）复杂区域可视化分析）如图 所示，规则格网的分割线会穿越多个类三角形区域且横穿道路交叉口和道路面，在该情况下，提取得到的中心线形态和结构与道路面明显不一致；而本文方法通过缓冲区处理和转盘分割算法避开了该区域，得到的结果与参考结果完全相同。测绘科学第 卷图 分割线穿越类三角形区域（横穿道路交叉口和道路面）（）如图 所示，当规则格网的分割线仅穿越一次（仅横向穿越或仅竖向穿越）多个类三角形区域时，提取得到的中心线会出现抖动和“工”字型结构，而本文方法通过曲率约束避开了该区域，得到的结果与参考结果完全相同。图 分割线穿越复杂区域（仅穿越一次）（）如图 所示，当规则格网的分割线多次穿越（既横向穿越又竖向穿越）多个类三角形的复杂区域时，提取得到的中心线出现抖动且在部分边界处与道路面结构明显不一致，而本文方法通过曲率约束避开了该区域，得到的结果与参考结果基本相同。图 分割线穿越复杂区域（穿越两次）（）从实验结果来看，规则格网在大部分简单区域接合处效果较好，在复杂区域接合处效果极差；本文方法在简单区域和复杂区域接合处效果都与参考结果相同。定量化分析分别统计规则格网和本文方法的分割线穿越类三角形、类三角形和类三角形的总个数，将分割处生成