顾及尺度变化和数据更新的道路网匹配算法

道路网数据匹配是地理空间数据库进行变化探测和数据更新的重要前提,不同比例尺下的道路网之间的匹配是一个非常重要的部分。本文总结和分析了道路网匹配的已有算法,针对不同比例尺道路网之间的匹配可能存在的问题和难点,设计了一个融合多种匹配技术的算法。在考虑不同比例尺下道路网数据的特点基础上,改进了空间场景结构的评价方法;分析了stroke匹配算法在不同比例尺道路网数据下的局限性,提出了一种可针对不同比例尺下道路数据存在变化与更新的stroke部分匹配算法。试验表明,文中所提出的方法能够适应不同比例尺下道路网的匹配,匹配效果较好,运行效率较高。     

道路网多特征匹配优化算法

同名道路匹配技术是道路数据集成、更新和融合的重要前提。道路网匹配在智能交通(intelligent transportation system,ITS)与位置服务(location-based service,LBS)等方面具有重要的研究价值和应用意义。本文提出了一种道路网多特征匹配优化算法:首先从形状、距离、语义3方面分别设计了基于面积累积的形状差、综合中值Hausdorff距离和全局加权属性项距离3种相似性度量,以更准确地描述道路待匹配对之间的特征差异;然后通过SVM对相似性特征样本集训练,以构建道路网回归匹配模型;最后利用此模型对未知匹配结果道路待匹配对进行匹配结果预测。大量试验结果表明,本文算法对非线性偏差明显的道路网数据能够实现较高的匹配准确率和召回率,能有效地用于包含多重匹配关系的道路网匹配。     

An improved probabilistic relaxation method for matching multi-scale road networks

Matching multi-scale road networks in the same area is the first step in merging two road networks or updating one based upon the other. The quality of the merge or update depends greatly on the matching accuracy of the two road networks. We propose an improved probabilistic relaxation method, considering both local and global optimizations for matching multi-scale of road networks. The aim is to achieve local optimization, as well as to address the identification of the M:N matching pattern by means of inserting virtual nodes to achieve global optimization effects. Then, by adding two attribute-related evaluation indicators, we developed four evaluation indicators to evaluate the matching accuracy, considering both geographic and attribute information. This paper also provides instructions on how to identify the proper buffer threshold during matching procedures. Extensive experiments were conducted to compare the proposed method with the traditional approach. The results indicate that: (1) the overall matching accuracy of each evaluation indicator exceeds 90%; (2) the overall matching accuracy increases by 6–12% after an M:N matching pattern is added, and by 4–6% following the addition of topology indicators; and (3) the proper buffer threshold is about twice the average value of the closest distance from all nodes.     

利用概率松弛法的城市路网自动匹配

多源空间数据匹配是空间数据集成与互操作,变化检测与数据更新的重要前提。路网数据匹配在导航、智能交通和基于位置服务等领域具有重要的研究意义和实用价值。本文提出一种基于概率松弛方法的城市路网自动匹配方法,该方法首先通过路段间几何差异性估算候选路段的初始概率,然后根据邻接候选匹配路段的兼容性不断更新原概率矩阵直到收敛于某一极小值。最后基于收敛的概率矩阵计算各候选路段的结构相似性,并通过设定相应的规则选取和提炼1: 1, 1: M和M: N匹配对。实验选取中国武汉,瑞士苏黎世地区的OpenStreetMap数据与导航数据进行匹配算法的验证。结果表明：本文算法对非刚性偏差较大的路网数据能达到较高精度,不存在匹配方向性问题,且能够识别1: 0, 1: M和M: N匹配。     

Experimental Analysis of Various Types of Road Intersections for Interchange Detection

Road interchanges are a major pattern type in road networks. Recognition of road interchanges benefits automated road network generalization, car navigation and traffic flow analysis. This study first investigated several existing approaches to automatically detecting interchanges in a road network, and determined that the recognition of characteristic road intersections is essential for the effective detection of interchanges. Several experiments were carried out to investigate nine types of road intersections for interchange detection and to analyze characteristic ones. Furthermore, an approach to the detection of both intersections and segments of interchanges was proposed and validated. The road networks across different scales were tested and results show that: (1) the T‐shaped and Cross‐shaped junctions are very common in road networks, but they are not the most characteristic ones for interchange detection; (2) the y‐shaped, Y‐shaped types, X‐shaped, Fork‐shaped and Multi‐leg may be the characteristic types for interchange detection; (3) the proposed approach to detecting interchanges is effective, and most of the intersections and segments of interchanges can be detected. In addition, taking multiple characteristic types into consideration for interchange detection is suggested.     

多尺度道路网的距离匹配算法研究

根据道路网折线的匹配特点,提出基于格网索引的折线——结点距离匹配算法,将复杂的折线与折线之间的几何相似度计算转换为求结点到折线距离的匹配方法,降低了计算复杂度,并通过建立格网索引来提高计算效率。在应用实例中,采用曲线拟合的最小二乘法确定算法的匹配容差和匹配成功率之间的关系,并通过与现有统计匹配算法比较,可知该算法效率高且匹配成功率较理想,能够满足多尺度道路网数据匹配的应用需求。     

A topographically preserved road‐network tile model and optimal routing method for virtual globes

Virtual globes enable the combination of heterogeneous datasets for optimal routing analyses in transportation, environmental ecology, and construction engineering. In this study, considering the advantages of the hierarchical tiling structure and topography of virtual globes, we propose a tile‐based optimal routing method for large‐scale road networks in a virtual globe. This method designs a topographically preserved road‐network tile model by partitioning roads into tiles and constructs the road‐network pyramid from the bottom to the top. During construction, a TileArc is calculated and flagged as the shortest path in a tile. Based on the built road‐network pyramid carrying hierarchical TileArcs, a multi‐level and flexible shortest path query can be executed efficiently. The proposed method is implemented with large road networks with different road grades in a virtual globe. Experimental results verify its validity, efficiency, and exactness. Moreover, the length of the shortest path with surface distance is approximately 1.3 times longer than that with Euclidean distance.     

利用路段连接图识别道路网中的格网模式

提出一种基于路段连接图的格网模式识别方法.该方法以路段连接对作为研究的基本单元,以节点路段为点,路段的连接为边用路段连接图表达道路网.将在道路网中识别格网转化为在路段连接图中搜索格网回路.提出了描述路段连接对几何与连接关系的5个参量,用于筛选图中符合格网特点的节点和边.设计了图搜索的约束条件,使用广度优先遍历搜索连接关...     

一种基于平行系数的双线主干道识别方法

城市主干道路的识别和提取是路网综合的关键步骤,而双线道路则是大比例尺地图数据中道路综合的难点。针对城市双线主干道识别问题,基于Gestalt视觉准则构建候选双线主干道线对的约束条件,提出了一种基于平行系数的双线主干道识别方法。首先对道路网数据进行拓扑处理,然后借助道路匹配思想,结合Hausdorff（HD）距离匹配方法识别出可能构成双线主干道的候选线对。再对候选线对进行平行系数计算,当平行系数满足阈值条件时,就判定该线对是构成双线主干道的弧段。最后根据构成双线主干道路段间的空间关系,将已识别的弧段连接成整条道路。实验证明,选取典型样本方法正确设置阈值后,该方法能有效地提取道路网中的双线主干道。     

面向道路网VGI数据的匹配与融合方法

自发地理信息(VGI)是一种新兴的地理数据采集方式,具有数据更新快、细节丰富、覆盖范围广等优势。利用VGI数据可以对道路网实现快速更新;但是由于VGI数据是非专业自发共享的,且数据采集时多使用非专业设备,所以存在数据质量不高的问题。大量VGI数据对同一地理要素的重复采集与融合处理则可改善数据的质量,文中以多人采集的道路网数据为例,结合矢量要素的匹配与融合理论,设计一种适用于道路网VGI数据的匹配与融合算法。首先在路段结点处建立缓冲区进行结点匹配,再根据路段距离相似度进行路段匹配,最后再利用Delaunay三角剖分融合算法对匹配后的同名路段进行融合。将匹配融合后的道路网与原始道路网VGI数据及Google影像图叠加对比分析,结果表明利用本文算法可有效地实现道路网VGI数据的匹配与融合。     

语义与几何相结合的道路网融合研究与实现

道路网是最重要的地理空间要素之一,空间数据融合能够把不同来源道路空间数据或信息加以结合,以获得信息量更丰富或更适于处理、分析、决策的新的数据集。传统的方法受限于道路网数据模型、属性数据类型以及缺少唯一标识的属性信息,道路网融合方法多以各个弧段或道路的位置、形状、方向等几何特征进行匹配,而忽略了道路的语义匹配。本文在数据来源与技术分析的基础上,提出了一种在工程化应用中可行的语义与几何相结合的道路网匹配方法,并通过FME实现空间数据融合,旨在为两个或多个道路网数据融合、联动更新提供方法参考。     

顾及上下级空间关系相似性的道路网联动匹配方法

现有道路网匹配方法中,大多利用道路自身结点和弧段特征进行匹配,而较少注意道路邻域要素在道路网匹配中的重要定位参考作用,从而影响匹配效率和正确率的进一步提高。针对上述问题,本文提出了一种顾及上下级空间关系相似性的道路网联动匹配方法,即模仿人在读图时通过特征地物和空间关联寻找目标地物的思维过程,将匹配看作是一种特征目标寻找、信息关联传递的推理过程。首先,运用Stroke技术将复杂道路网进行等级划分。其次,通过道路骨架关联关系树构建道路网联动匹配模型。最后,选取高等级骨干道路作为起始特征对象,计算道路间的上下级空间关系相似性,逐级迭代使匹配信息在道路网联动匹配模型中传递,从而得到匹配结果。试验表明,本文算法缩小了待匹配数据的搜索范围,能够有效提高匹配正确率和效率,尤其在数据位移较大、存在非系统性几何位置偏差的情况下优势明显。     

Detection of clusters in traffic networks based on spatio‐temporal flow modeling

Spatio‐temporal clustering is a highly active research topic and a challenging issue in spatio‐temporal data mining. Many spatio‐temporal clustering methods have been designed for geo‐referenced time series. Under some special circumstances, such as monitoring traffic flow on roads, existing methods cannot handle the temporally dynamic and spatially heterogeneous correlations among road segments when detecting clusters. Therefore, this article develops a spatio‐temporal flow‐based approach to detect clusters in traffic networks. First, a spatio‐temporal flow process is modeled by combining network topology relations with real‐time traffic status. On this basis, spatio‐temporal neighborhoods are captured by considering traffic time‐series similarity in spatio‐temporal flows. Spatio‐temporal clusters are further formed by successive connection of spatio‐temporal neighbors. Experiments on traffic time series of central London's road network on both weekdays and weekends are performed to demonstrate the effectiveness and practicality of the proposed method.     

A Hybrid Link‐Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions

Turn restrictions, such as ‘no left turn’ or ‘no U‐turn’, are commonly encountered in real road networks. These turn restrictions must be explicitly considered in the shortest path problem and ignoring them may lead to infeasible paths. In the present study, a hybrid link‐node Dijkstra's (HLND) algorithm is proposed to exactly solve the shortest path problem in road networks with turn restrictions. A new hybrid link–node labelling approach is devised by using a link–based labelling strategy at restricted nodes with turn restrictions, and a node‐based labelling strategy at unrestricted nodes without turn restrictions. Computational results for several real road networks show that the proposed HLND algorithm obtains the same optimal results as the link‐based Dijkstra's algorithm, while having a similar computational performance to the classical node‐based Dijkstra's algorithm.     

基于SOM的高分辨率遥感影像道路网自动提取

本文研究基于SOM(Self-Organizing Feature Map)神经网络学习模型的高分辨率遥感影像道路网自动提取算法。首先利用数学形态学提取遥感图像道路的初始道路区域信息,自动对原始图像进行分区并确定神经元初始权值,用SOM网络学习模型对神经元进行训练学习,经迭代获取道路网中心点位置,最后运用"中心点四邻域跟踪判别法"跟踪连接形成道路中心线。实验表明,该方法在高分辨率遥感影像道路网的提取上有较好的效果,特别在主干道路网的提取上效果更佳,对噪声干扰具有良好的鲁棒性。     

结合引力场理论的道路自动选取方法

针对复杂网络模型被广泛应用于道路选取的研究中,少有方法顾及道路网对偶图中多级邻居节点的影响,导致对道路的重要性评价缺乏准确性和可靠性的问题。该文将道路网对偶图节点的结构特征值视作质量,将节点间的最短距离视作距离,结合引力场方程实现道路自动选取,较好地将道路网对偶图中多级邻居节点的影响纳入到道路重要性的计算中,从而实现对道路重要性的准确评估。通过对兰州市城关区的路网进行实验,结果表明本文方法所选取的路网较好地保持了原始道路网的整体结构、覆盖范围、密度分布、拓扑特征和连通性。     

A generic space definition framework to support seamless indoor/outdoor navigation systems

Contemporary public buildings are becoming conglomerates of open, semi‐open and closed spaces, with indoor, outdoor and underground sections. For humans and robots to navigate seamlessly through such environments, new flexible approaches need to be developed. Navigation systems generally rely on a network (nodes and edges) as an abstraction of underlying space availability. However, indoor and outdoor networks have different origins. While indoor systems rely on indoor space subdivision approaches, current outdoor systems utilize road‐based network approaches. Linking such networks via particular nodes is possible but restrictive. Many spaces in the built environment are not strictly indoor or outdoor spaces and are thus often omitted from navigation networks, further limiting navigation options. To overcome these shortcomings, we introduce a new space definition framework in which the entire built environment is categorized into indoor, outdoor, semi‐indoor and semi‐outdoor spaces. We provide strict definitions for the four space categories. Our framework allows the same navigation network extraction approaches to be used and therefore enables seamless indoor/outdoor path computation for single or combinations of locomotion modes. The notions of semi‐indoor and semi‐outdoor spaces offer new options for further tailoring of the navigation path with respect to environmental factors, which we demonstrate with two use cases.     

A fast algorithm for finding K shortest paths using generalized spur path reuse technique

The problem of finding the K shortest paths (KSPs) between a pair of nodes in a road network is an important network optimization problem with broad applications. Yen's algorithm is a classical algorithm for exactly solving the KSP problem. However, it requires numerous shortest path searches, which can be computationally intensive for real large networks. This study proposes a fast algorithm by introducing a generalized spur path reuse technique. Using this technique, shortest paths calculated during the KSP finding process are stored. Accordingly, many shortest path searches can be avoided by reusing these stored paths. The results of computational experiments on several large‐scale road networks show that the introduced generalized spur path reuse technique can avoid more than 98% of shortest path searches in the KSP finding process. The proposed algorithm speeds up Yen's algorithm by up to 98.7 times in experimental networks.     

均值漂移与卡尔曼滤波相结合的遥感影像道路中心线追踪算法

基于模板匹配的道路追踪方法是道路提取中较实用的一类方法,但传统模板匹配方法主要以相关系数作为相似性测度,对车辆、树荫等遮挡敏感,不适用于高分辨率遥感影像道路提取。针对这一问题,本文采用一种稳健的相似性测度,设计了一种基于均值漂移的道路中心点匹配算法,克服了传统模板匹配对遮挡敏感的缺点;然后运用卡尔曼滤波,实现高分辨率遥感影像道路中心线追踪。试验表明,该方法能够准确提取高分辨率遥感影像道路中心线,对车辆、树荫等遮挡具有稳健性。     

道路数据综合的融合算法研究

针对目前还没有一种算法能在道路化简(删点)的同时又能实现道路光滑(增点)的情形,提出了将Douglas-Peucker算法和Li-Openshaw算法组合优化起来对道路进行综合的思想。本文首先对线状要素综合的两种经典算法Douglas算法和Li-Openshaw算法各自的优缺点进行了分析,在此基础上对Li-Openshaw算法进行了改进,最后融合两种算法的优点,设计了一种道路综合的组合优化算法,在实践中取得了较好的效果。