基于GPS数据的露天矿道路网自动提取

孙效玉，田凤亮，张 航，李 震

(东北大学 资源与土木工程学院，辽宁 沈阳 110819)

基于GPS数据的露天矿道路网自动提取

孙效玉，田凤亮，张 航，李 震

(东北大学 资源与土木工程学院，辽宁 沈阳 110819)

传统栅格法提取路网精度较低，尤其在提取露天矿道路网时，路段缺失与偏移现象更加明显。针对这一问题，摒弃了传统栅格法通过增大栅格来保证道路网连通性的处理方式，以GPS数据存在偏移这一事实为根据，假设GPS数据偏移服从正态分布，提出了通过求取GPS轨迹点在道路上的概率进行栅格初始化的方法，建立了相应模型;采用二维中值滤波方法对初始栅格数据进行修正;对查表细化算法进行改进，采用改进的细化算法对道路网栅格图像进行细化处理，得到道路网骨架信息;采用追踪法实现道路矢量化。实验表明，该方法较传统栅格方法的覆盖率提高6.43%～11.54%，错误率降低42.13%～83.02%，为道路网提取工作提供了一种有效办法，揭示了栅格大小对于路网提取结果的重要影响。

露天矿;道路网;GPS;图形细化

对露天矿采运系统进行优化调度被视为提高设备效率、降低生产成本的重要手段[1]。尽管众多学者在调度原则、理论、方法等方面做了大量工作，但优化调度效果并不理想。其症结主要在于:所有的调度方法都基于道路网固定不变这一前提，而露天矿道路网在开采过程中变化十分频繁。因此，矿山道路网的及时更新成为了优化调度的重要前提和基础。

同时，道路网络智能提取、更新和发布也是智能交通与交通地理信息系统研究的热点问题。传统获取路网的方法主要有以下两类:一类是传统测绘方法，该方法历史悠久，精度高，但周期长，成本高;另一类是基于遥感图像的自动生成方法[2-3]，该方法成本高，精度受图像质量影响较大，同时获取的图像并不能及时反映当前路网情况。

随着GPS技术在生产生活中的广泛应用，越来越多的学者开始思考如何利用GPS数据来获取路网信息[4]。主要有以下4类方法:第1类主要采用轨迹聚类的方法，如文献[5]通过对GPS散点数据进行聚类的方式稀疏样本点，并对聚类结果进行聚类点分割与中心线拟合两步处理获得路网;文献[7]改进了WILLIAM等的道路交叉口判断方法[6-7]，在文献[6]的基础之上获得了路网的拓扑关系;文献[8]针对道路网更新不及时的问题，提出了一种基于轨迹聚类从GPS轨迹中提取道路网的方法。该类方法降低了直接处理大量轨迹数据带来的难度，生成的路网具有较高精度，但路口交叉点的提取依赖于聚类半径的选择。第2类方法主要采用增量化的方式获得路网，如文献[9]利用轨迹线与原路网图形增量的方式获得路网;文献[10]通过判断单个轨迹点与原有路网关系来生成路网;文献[11]提出了一种利用GPS轨迹实时更新现有路网地图的方法。这类方法需要原有路网数据作为参考，生成结果也受限于原有路网的精度。第3类方法通过Delaunay三角剖分的方式不断融合新旧轨迹线，得到更加细致的路网信息，但在提取复杂多变的支路时存在困难[12]。第4类方法主要采用栅格化的方法提取道路的中心线，如文献[13]利用设置缓冲区的办法将车辆行驶轨迹栅格化，再利用图像细化算法提取出道路中心线，生成道路网络。对比前3类方法，栅格法在处理大量轨迹信息时具有更高的效率，适合露天矿道路网提取，但道路网提取结果依赖于道路栅格图像的完整程度，为了获得完整的路网信息，通常采用增大栅格的方法，这对道路网提取结果有一定影响。

针对以上问题，同时兼顾矿山道路网形态复杂、变化频繁的特点，本文在传统栅格方法的基础上提出了一种适用于露天矿复杂条件下的路网提取方法。并利用抚顺西露天矿卡车调度系统历史数据进行验证，结果表明该方法能够有效提取路网信息，具有较高精度。

1 生成道路网栅格图像

生成道路网栅格图像的目的是利用生产中卡车返回的GPS轨迹点作为样本点再现道路网的真实形态，包括道路形状、拓扑关系等。与城市道路不同的是，露天矿道路随生产进行而不断延伸、扩展，使得露天矿道路网具有空间上形态复杂、时间上变化频繁的特点。因此，及时获取露天矿道路栅格图像是提取露天矿道路网的基础。

1.1 栅格初始化

在露天矿生产过程中，卡车不断地行驶于各个路段，同时以一定频率返回卡车所处的位置，当这些位置信息足够多时，能够发现这些点的分布呈现一定的规律，如图1所示。

图1 卡车GPS数据分布Fig.1 Distribution of truck GPS data

图1中横纵坐标表示矿区坐标，不同颜色的点代表不同卡车。从图1可以发现这样的规律:①整体上看GPS点密集且集中地分布于道路之上;②同一路段上GPS点的密度基本不变。

因为GPS数据存在偏差，给定GPS读数属于区域Xi，其真实位置为区域Xj的概率为P(Xj)。为简单起见，不妨假设P(X)服从正态分布，如图2所示。

图2 GPS数据概率分布Fig.2 Probability distribution of GPS data

因此，对于任意一个区域X，该点附近存在GPS点X1，X2，X3，…,Xn，各点真实位置为X区域的概率分别为p1，p2，p3，…,pn，则区域X有车经过的概率为

P(X)=1-(1-p1)×(1-p2)×(1-p3)×

…×(1-pn)

设轨迹点p，在轨迹空间上定义矩形区域G使得∀p∈G。将G分为m×n个子区域，记为Gi，j，其中1≤i≤m，1≤j≤n。

定义m×n阶初始矩阵R，对于矩阵中任何一个元素ri，j满足如下关系:

ri，j=P(Gi，j)

1.2 道路网图像修正

显然初始化后的道路网并不规整，道路内可能存在中空点，道路外可能存在孤立的点。这些噪声对道路网提取精度影响很大。

目前已出现很多去除噪声的算法，如高斯滤波、维纳滤波、中值滤波等，不同滤波算法滤除噪声的原理不同，滤波效果也存在差别[14]。中值滤波作为一种非线性的信号处理方法，在一定条件下可以克服线性滤波器处理图像细节模糊的问题，而且它对滤除图像噪声非常有效[15]。对于初始道路中存在的中空点与孤立点，采用中值滤波更为合理。对于矩阵中元素ri，j二维中值滤波可以表示为

图3 道路网栅格Fig.3 Road network raster image

2 道路网骨架提取

2.1 栅格图像细化

为了方便对道路网进行矢量化处理，图像细化应满足以下原则:① 骨架提取不能破坏原有道路网的拓扑结构;② 骨架提取应保证道路网的连通性;③ 提取出的骨架应为单像素的细线;④ 道路网骨架中的交叉点应具有明显特征，以方便提取;⑤ 尽量避免“毛刺”现象的产生。

图像细化算法种类繁多，每一种方法都有其优点与不足，有着不同的适用条件。在诸多图像细化算法中比较常用的有以下几种:① ZHANG快速并行细化法，细化结果能够最大限度保持图像连通性，较好地保持图像原有形态，且不会出现“毛刺”现象，但细化结果不能保证是一条单像素的细线[16];② HILDITCH细化法能够保证图像原有形态，但细化结果存在毛刺与断点[17];③ OPTA细化算法能够保证图像连通性，但细化质量不高，“毛刺”较多[18];④ 文献[19]基于OPTA细化算法原理提出了一种八邻域查表细化算法，运算速度快，细化质量较高。

本文修正了文献[19]的细化算法，针对道路网细化问题，提出如下细化判据:① 保留内部点;② 保留直线端点;③ 若连通分量不增加，可以删除边界点。以此为基础进行八邻域查表细化，得到图4所示的细化结果。

图4 道路网细化结果Fig.4 Road network skeleton

2.2 道路网矢量化

对道路网细化结果进行矢量化，首先应获得道路交叉点、道路端点等特征信息，在此基础之上进行追踪处理，最终得到道路网的矢量信息。

设点P为细化结果上任意一点，则与P点相邻的8个像素点称为八邻域，指定黑色为1，白色为0，则依次遍历八邻域，得到8个邻域之和就是点P的八邻域值，如图5所示，P点的八邻域值为3。通过分析图像中道路各像素点的特征可以发现这样一个事实:端点的八邻域值为1，交叉点的八邻域值大于2，道路上其他像素点的八邻域值为2。

图5 八邻域Fig.5 Eight neighborhood

由于道路上各像素点具有以上特点，因此可根据这些特点将道路上各像素点进行归类。定义集合T为道路网上特征点集，包括道路交叉口、道路端点。对于集合T中任意一点T1，以T1为中心查找8邻域中值为1的点，作为下一点，为避免重复追踪需将当前点置为0，并将下一点作为当前点，重复以上操作直到当前点属于集合T。如图6所示。

图6 二值图像矢量化Fig.6 Algorithm of vectorization in a binary image

通过追踪可以得到以T1作为起点的一条路段，该路段包含了端点以及道路上各点的坐标信息。对集合T中各点依次进行追踪处理，就可以获得矢量化的道路网骨架。矢量化流程如图7所示。

图7 矢量化流程Fig.7 Algorithm of vectorization

3 实验结果及分析

试验数据来源于抚顺西露天矿卡车调度系统2012-01-01～02采集的卡车GPS数据，各类卡车GPS数据总计191 654条。实验在普通PC机上进行，采用Python语言实现了道路网骨架提取模型。

在进行栅格图像初始化的过程中，为了降低计算量，首先设存在GPS轨迹的栅格属于道路的概率为1，并利用卷积核A进一步求取各点在道路上的概率，其中，

求得各栅格属于道路的概率后，采用中值滤波对栅格图像进行处理，中值滤波窗口为3×3的矩形窗口。设置阈值t=0.8，即认为当某点有车经过的概率大于0.8时，就认为该点为道路上的点。最终经过二值图像细化与矢量化处理后获得如图8所示的道路网。

图8 道路网提取结果Fig.8 Results of road network extraction

为了定量评价试验结果，本文参考了文献[20]提出的缓冲区检测方法来评价道路提取数据的有效性[20]。如图9所示，红色线条为本文方法提出的道路，蓝色线条为传统方法提出的道路，黑色线条为参考道路，灰色区域为缓冲区。

图9 提取结果对比Fig.9 Comparison of extraction

由于露天矿道路宽度多在10 m以上，因此以5 m为缓冲半径对传统栅格方法与本文提出的方法进行对比分析，其中覆盖率为正确提取道路的总长度与参考路网总长度的百分比，错误率为错误提取道路的总长度与提取路网总长度的百分比。结果见表1。

表1道路网提取结果对比
Table1Comparisonofroadnetworkextractionresults

栅格大小/m传统栅格方法覆盖率/%错误率/%本文提出的方法覆盖率/%错误率/%相对提升效果覆盖率增加/%错误率减少/%277.131.0686.030.1811.5483.02482.521.9789.061.147.9342.13687.143.8692.742.716.4342.44

由表1可以发现，随栅格的增大，覆盖率增大，这是因为随栅格的增大，原本因为GPS数据稀疏而未连通的路段变为连通，进而被检测出来;另一方面，随栅格的增大，原本不是道路的区域被检测为道路，使得错误率上升。

对比传统栅格法与本文提出的方法，在栅格大小一定时，本文提出的方法具有更高的覆盖率与较小的错误率，且栅格越小，效果越明显。这是由于在面对部分路段不连通的问题时，本文提出的方法并没有采用直接增大栅格的方式谋求路段的连通性，而是从GPS数据可能存在偏移的事实出发，求取各个栅格可能为道路的概率，以此保证路段的连通性，因而具有较低的错误率与较高的覆盖率。

当栅格大小增加到6 m时，仍有一部分道路未被提取出来。这些道路车辆通过量很小，因而GPS数据更为稀疏，生成栅格图像连通性差，因此很难被提取出来。此外，对比图1与图8，可以发现在某些路段上存在细节丢失的现象。这些区域多为装、卸点处形成的短小支路。这表明该方法在提取GPS数量较少的路段与部分支路时仍存在一定困难。

4 结 论

(1)针对露天矿道路网提取困难的问题，提出了一种基于GPS数据的道路网自动生成方法。提取结果具有较高精度，为露天矿道路网提取工作提供了新的思路。

(2)与传统栅格方法相比，通过求取各栅格可能为道路的概率，可以使栅格信息更加细化，在增加道路网连通性的同时，能够保证提取结果具有较低的误检率与更高的覆盖率。

(3)当路段GPS点数量很少时，道路网提取存在困难;当提取短小支路时，也会丢失部分细节。这些问题需要在道路连通性与细节的完整性之间寻找平衡，在今后的工作中，将会逐渐深入研究。

[1] 霍晓宇,杨仕教,吴长振,等.露天矿山运输调度系统粒子群优化[J].煤炭学报,2012,37(S1):234-239.

HUO Xiaoyu,YANG Shijiao,WU Changzhen,et al.Particle swarm optimization for transportation dispatching system of open-pit mines[J].Journal of China Coal Society,2012,37(S1):234-239.

[2] YAN Li,RONALD Briggs.An automated system for image-to-vector georeferencing[J].Cartography & Geographic Information Science,2012,39(4):199-217.

[3] RUIZ J J,RUBIO T J,URENA M A.Automatic extraction of road intersections from images based on texture characterisation[J].Survey Review,2011,43:212-225.

[4] BRUNTRUP R,EDELKAMP S,JABBAR S,et al.Incremental map generation with GPS traces[A].Intelligent Transportation Systems[C].Proceedings.IEEE,2005:574-579.

[5] 欧阳鸿,刘建勋,刘毅志,等.基于步行 GPS 轨迹的路网提取方法[J].计算机与现代化,2014(2):124-128.

OUYANG Hong,LIU Jianxun,LIU Yizhi,et al.An extraction method of road network based on walking GPS trajectories[J].Computer & Modernization,2014(2):124-128.

[6] WILLIAM A,GORDON A.Automating the detection and simplification of junctions in road networks[J].Geolnformatica,1999,3(2):185-200.

[7] 谭康,刘建勋,廖祝华.一种基于GPS轨迹的道路拓扑生成方法[J].计算机科学,2015,42(9):37-40.

TAN Kang,LIU Jianxun,LIAO Zhuhua.Topology generation method of road network based on GPS trajectories[J].Computer Science,2015,42(9):37-40.

[8] SCHROEDL S,WAGSTAFF K,ROGERS S,et al.Mining GPS traces for map refinement[J].Data Mining and Knowledge Discovery,2004,9(1):59-87.

[9] 杨兆升,汪健,李丽丽.导航电子地图增量更新方法研究[J].交通信息与安全,2009,27(2):10-14.

YANG Zhaosheng,WANG Jian,LI Lili.Incremental updating of digital navigation map[J].Journal of Transport Information & Safety,2009,27(2):10-14.

[10] 汪永红,张斌,郭黎,等.导航电子地图增量更新方法研究[J].地理信息世界,2011(4):40-43.

WANG Yonghong,ZHANG Bin,GUO Li,et al.Research of incremental updating method for navigation electronic map[J].Geomatics World,2011(4):40-43.

[11] TANG L,HUANG F,ZHANG X,et al.Road network change detection based on floating car data[J].Journal of Networks,2012,7(7):1063-1070.

[12] 唐炉亮,刘章,杨雪,等.符合认知规律的时空轨迹融合与路网生成方法[J].测绘学报,2015,44(11):1271-1276.

TANG Luliang,LIU Zhang,YANG Xue,et al.A method of spatio-temporal trajectory fusion and road network generation based on cognitive law[J].Acta Geodaetica et Cartographica Sinica,2015,44(11):1271-1276.

[13] 蒋益娟,李响,李小杰,等.利用车辆轨迹数据提取道路网络的几何特征与精度分析[J].地球信息科学学报,2012,14(2):165-170.

JIANG Yijuan,LI Xiang,LI Xiaojie,et al.Geometrical characteristics extraction and accuracy analysis of road network based on vehicle trajectory data[J].Journal of Geo-Information Science,2012,14(2):165-170.

[14] 柴宝仁.中值滤波在气象传真图中降噪的分析[J].北京理工大学学报,2011,31(4):417-419.

CHAI Baoren.Analysis of median filter for noise reduction of meteorological facsimile map[J].Transactions of Beijing Institute of Technology,2011,31(4):417-419.

[15] LU Xuanzhong,WANG F L,CHANG Y Q,et al.Region-adaptive median filter[J].Journal of System Simulation,2007,19(23):5411-5414.

[16] 吴选忠.Zhang快速并行细化算法的扩展[J].福建工程学院学报,2006,4(1):89-92.

WU Xuanzhong.Extending of Zhang’s fast parallel thinning algorithm[J].Journal of Fujian University of Technology,2006,4(1):89-92.

[17] 周战荣,何俊发,李正亮,等.一种干涉条纹细化算法的改进[J].光学技术,2006,32(S1):563-565.

ZHOU Zhanrong,HE Junfa,LI Zhengliang,et al.Improved algorithm of interference fringe thinning[J].Optical Technique,2006,32(S1):563-565.

[18] ZHAO L,CHEN Q,CHEN Z.A new improved OPTA thinning algorithm:A new improved OPTA thinning algorithm[J].Journal of Computer Applications,2008,28(10):2639-2642.

[19] 杨威,郭科,魏义坤.一种有效的基于八邻域查表的指纹图像细化算法[J].四川理工学院学报(自科版),2008,21(2):61-63.

YANG Wei,GUO Ke,WEI Yikun.An efficient index thinning algorithm of fingerprint image based on eight neighbourhood points[J].Journal of Sichuan University of Science & Engineering(Natural Science Edition),2008,21(2):61-63.

[20] MICHAEL F Goodchild,GARY J Hunter.A simple positional accuracy measure for linear features[J].International Journal of Geographical Information Science,1997,11(3):299-306.

Automaticextractionofroadnetworkinopen-pitminebasedonGPSdata

SUN Xiaoyu，TIAN Fengliang，ZHANG Hang，LI Zhen

(SchoolofResources&CivilEngineering,NortheasternUniversity,Shenyang110819,China)

The traditional grid method for extracting road network has a low accuracy,especially for the extraction of open-pit road network,the loss and offset of road is more significant.For solving this problem,the conventional solution is to enlarge the grid so that the connectivity can be ensured.However,in this paper,by assuming the GPS bias as a normal distribution,a method of rastering the GPS data by calculating the probability of track points on the road was proposed.On this basis,the median filter algorithm was deployed to preprocess the raster image.The index table thinning algorithm was improved,and this improved thinning algorithm was used to refine the grid image of the road network.Finally,the road network was translated into vectorization.Experimental results show that the coverage ratio of this method has been improved by 6.43% to 11.54% compared with the traditional grid method,and the error rate has been reduced by 42.13% to 83.02%.This paper provides an effective method for road network extraction and reveals the important influence of grid size on road network extraction results.

open-pit mine;road network;GPS;skeletonization

孙效玉，田凤亮，张航，等.基于GPS数据的露天矿道路网自动提取[J].煤炭学报,2017,42(11):3059-3064.

10.13225/j.cnki.jccs.2017.0308

SUN Xiaoyu，TIAN Fengliang，ZHANG Hang，et al.Automatic extraction of road network in open-pit mine based on GPS data[J].Journal of China Coal Society,2017,42(11):3059-3064.doi:10.13225/j.cnki.jccs.2017.0308

TD57;P228.4

A

0253-9993(2017)11-3059-06

2017-03-10

2017-06-30责任编辑许书阁

国家自然科学基金资助项目(51674063);国家重点研发计划资助项目(2016YFC0801608)

孙效玉(1963—)，男，内蒙古赤峰人，教授。E-mail:sunxiaoyu@mail.neu.edu.cn。

田凤亮(1992—)，男，内蒙古赤峰人，博士研究生。E-mail:1719979259@qq.com