赵 东 保,刘 雪 梅,张 弘 弢

(1.华北水利水电大学资源与环境学院,河南 郑州 450011;2.华北水利水电大学信息工程学院,河南 郑州 450011;3.四川省基础地理信息中心,四川 成都 610041)

基于大规模浮动车轨迹点数据的道路网变化检测与更新方法研究

赵 东 保1,刘 雪 梅2,张 弘 弢3

(1.华北水利水电大学资源与环境学院,河南 郑州 450011;2.华北水利水电大学信息工程学院,河南 郑州 450011;3.四川省基础地理信息中心,四川 成都 610041)

针对矢量道路网的变化检测与更新问题，提出一种基于大规模浮动车轨迹点数据的道路网快速变化发现与更新方法。首先对矢量道路网进行栅格化处理，并根据若干天内浮动车GPS轨迹点落在栅格内的个数对栅格赋值。经过对轨迹栅格图像的低通滤波、边界清理后，采用数学形态学方法提取轨迹栅格图像的骨架线，通过判断道路骨架线与更新前道路网缓冲区之间的位置关系，快速识别出变化道路，即新增道路和消失道路。最后，对更新道路的骨架线分别进行剪枝处理、断线连接以及节点融合，实现对原有道路网道路数据的提示性更新。结果表明：与传统方法相比，该方法能够以更低的成本和更好的现势性对现有道路网进行在线增量式快速变化检测和更新。

道路网更新;变化检测;浮动车技术;GPS轨迹点;志愿者地理信息

0 引言

矢量道路网是导航地图的重要基础性地理要素。伴随着经济社会的快速发展，我国城市道路的建设变化多、发展快，如果导航地图无法做到及时快速更新，其现势性将不能满足应用需求[1]。为了实现电子地图的快速更新，近年来涌现出的志愿者地理信息采集是一个切实可行的有效手段[2-4]，即每一个地理信息采集爱好者都可以对地图的变化部分进行主动测量和修订。对于矢量道路网而言，还存在一种宝贵的大众地理数据源，这就是浮动车数据[5]。国内的大城市一般有上万辆出租车(可作为浮动车)，其GPS采样间隔多在30～300 s，它们覆盖面广，全天候行驶。通过在服务器端对大数据量出租车GPS轨迹的被动式分析，就可以绘制出道路网地图，基于这种思路已经涌现出三类方法。一是K-means类算法[6-8]，将大规模出租车留下的轨迹点数据利用K-means类算法进行聚类，再从聚类中提取中心线作为道路要素。二是核密度估计算法[9-11]，首先将GPS轨迹点数据转换成栅格图像，每个像素值反映了轨迹点落入该像素的密度，设定阈值将栅格图像转换成二值图像，再提取图像骨架线，并将骨架线作为道路中心线。三是轨迹合成算法[12-15]，不但考虑单个轨迹点数据，还考虑轨迹点所连成的轨迹线，将这些轨迹线数据合成以生成道路。对上述三类方法对比发现，第二类方法效果最好[16]。

尽管上述三类方法利用大规模浮动车轨迹数据理论上足以生成道路网地图。但实际上，受限于各种复杂因素的影响，所生成的道路网在准确性上仍然无法与专业的导航地图相媲美。另一方面，道路数据也处于不断发展变化中，没有必要完全从头开始生成道路网地图。基于这种思路，本文将以核密度估计算法为基础，基于对大规模浮动车轨迹点数据的分析，快速检测道路网的几何变化情况，并实现变化道路与原有道路网的数据融合，从而形成道路网的增量式提示性更新。通过将提示性更新内容反馈给现有导航地图生产商，可服务于导航地图的及时修补测绘。

1 基于浮动车轨迹点数据的道路网自动变化发现与更新

1.1 算法总体思路

本文算法共包括三大部分，首先是数据预处理阶段；设定一定的格网尺寸，对大规模浮动车轨迹点数据进行栅格化处理，通过统计落在每个栅格内的轨迹点个数，将栅格转换为二值化轨迹栅格图像。然后是变化检测阶段，采用数学形态学方法提取轨迹栅格图像的中心线，再通过判断道路骨架线及其所在道路面状栅格区域与原有道路中心线及其缓冲区面状区域之间的空间位置关系来确定道路的变化情况。最后是更新道路与原有道路网的数据融合，在该阶段，对新增道路数据进行剪枝、断线连接、节点融合等，以确保在几何与拓扑信息上与原有道路网数据融为一体，实现对原有道路网数据的自动更新。

1.2 数据预处理——轨迹栅格图像的生成

海量GPS轨迹点大都位于道路两侧区域，具有明显的聚集性质，将这些具有聚集性质的点数据相连成面，就可在一定程度上恢复出道路的路面。其方法是首先对矢量道路网进行栅格化处理，栅格尺寸可设定与车辆的大小基本一致，如5 m×5 m。接着判断落入每个格网中GPS轨迹点的个数，若超过一定阈值(本文设为1个)，则该栅格赋值为1，反之赋值为0。经过栅格化赋值处理后，初步的二值化轨迹栅格图像即可大致生成。为了确保轨迹栅格图像的准确性，还须进行如下步骤：一是轨迹栅格图像的低通滤波[17],目的在于对轨迹栅格图像进行平滑操作。由于GPS信号的缺失，或者留下的GPS轨迹点数目较少，本是相连的道路区域可能会存在小中断，低通滤波将有助于减弱这种情形的存在。图1a中道路区域存在许多中断现象，采用低通滤波后，中断区域得以相连(图1b)。二是轨迹栅格图像的边界清理，目的在于减弱轨迹栅格图像中孤立噪音的干扰，并使得轨迹栅格图像更为规整。边界清理的方法是按照规定模板窗口(如5×5模板)将整个栅格区域均匀划分为多个模板区域，且相互间无重叠。而后判断每一个模板区域内出现次数最多的栅格值，并把该像元值作为该模板区域每一栅格的值。如图1c所示，GPS测量误差导致若干GPS轨迹点落在距离道路较远的区域内，具有明显的离群现象，是孤立点。采用边界清理后，不但孤立点被删除，且道路栅格集合的边界也更为整齐(图1d)。

图1 道路栅格图像的低通滤波和边界清理Fig.1 Lowpass filter and boundary clean of road raster image

1.3 道路几何信息的变化发现

道路几何信息的变化主要借助于提取轨迹栅格图像中心线完成，可采用文献[18]所述的最大圆盘法提取轨迹栅格图像中栅格区域的骨架线，而骨架线对应着实际的道路中心线，再对所有道路中心线构建缓冲区，根据GPS单点定位精度，缓冲区半径可设为20～30 m。在构建完成骨架线后，可形成骨架线网络，遍历该网络中的每一个骨架线弧段，设某一条骨架线弧段为S，所对应的轨迹栅格区域为AS，判断S落在了哪一个道路中心线的缓冲区内部，假设落在了道路中心线L的缓冲区内部，其缓冲区域为AL，分别判断S与AL的位置关系以及L与AS的位置关系，则有：1)若S落在区域AL之内，且L落在区域AS之内，则S与L二者匹配，即可认为原有道路L未发生变化;反之则认为L发生了变化，包括新增道路和消失道路两方面。2)凡是S在原有道路网中找不到匹配对象，便可判定S为新增道路，例如若S没有落在任何一条道路中心线的缓冲区内部，则S即是新增道路。3)凡是L在骨架线网络中找不到匹配对象，便可判定L可能为消失道路，例如若L没有落在任何骨架线栅格区域内部，则预示该道路可能为消失道路。

1.4 更新道路与原有道路网的融合

在提取出道路网变化信息后，还须对变化信息做进一步处理，以使其融入到原有道路网数据中，包括对变化部分轨迹栅格图像骨架线的剪枝、断线连接与节点融合。1)骨架线剪枝：在提取轨迹栅格图像骨架线的过程中会存在一些细小分支，其并不代表真实的道路中心线，因此可设定一定阈值，将长度较短的骨架线细小分支予以删除。2)断线连接：从轨迹栅格图像中提取的骨架线并不总能保持连续，有时一条道路中心线对应着多条距离较长的骨架线,其端点间存在着较小的距离。且延伸方向也保持大体一致。因此可设定一定的距离阈值和角度阈值，将那些延伸方向大致相同且端点距离较小的骨架线予以连接。3)节点融合：节点融合类似于断线连接，不过此处特指更新道路与原有道路网数据的融合操作，对于那些新增的道路或修改的道路，其道路中心线的端点并不能恰好捕捉在原有道路数据上，需要对新生成的道路中心线进行延伸或打断等处理，本文将这些操作统称为节点融合。

图2列举了上述3种情况，图2a中黑色粗线为原始道路网数据，细线为新增道路骨架线，分别经过剪枝处理、断线连接和节点融合，转变为图2b，其中新增的道路骨架线数据经过了数据清理后与原有道路网数据融为一体。

图2 更新道路与原有道路网数据的融合Fig.2 Fusion of new road and original road network

2 算法步骤与实例验证

2.1 算法步骤

本文具体算法步骤：1)选取一定时间段内所有浮动车的轨迹点数据，并对矢量道路网进行栅格化处理，判断每个栅格中落入的GPS轨迹点个数，若大于阈值，则该处栅格赋值为1，反之赋值为0，从而生成轨迹栅格图像。2)按照对初步的二值化轨迹栅格图像先进行低通滤波，将滤波后栅格属性值大于0的栅格赋值为1，其余仍为0。而后进行边界清理，消除孤立噪音。3)借助数学形态学提取轨迹栅格图像中道路栅格区域的骨架线，其对应道路栅格集合的道路中心线，再生成原有道路网数据的缓冲区。4)通过对比判断骨架线与原有道路缓冲区区域之间的空间位置关系，可判定该骨架线所代表的道路是否为新增道路、修改道路或被删除道路，实现道路网几何变化信息的提取。5) 对那些被确定为新增道路的道路骨架线做进一步处理，包括剪枝、断线连接、节点融合等，实现新增道路与原有道路网的融合。

2.2 实例验证

以下结合具体实例进行验证，数据实例为2006年深圳市1∶5 000矢量道路网数据，2008年5月10日1 800辆采样间隔为3～5 min的深圳市出租车GPS轨迹数据。图3为深圳市福田区局部区域矢量道路网，图4为全天所有出租车在该区域留下的GPS轨迹点，共计31 641个。经过步骤1)后可生成初步的二值化轨迹栅格图像(图5)，其中栅格尺寸设置为5 m×5 m。图6和图7为步骤2)运行结果，其中边界清理模板窗口取5×5。图8和图9为步骤3)运行结果，其中缓冲区半宽度为30 m。图10为提取道路网几何变化信息，其中新增道路为实线。图11则为步骤5)的运行结果，其中剪枝阈值设为100 m，即某短小分支不超过100 m，即可删除。断线连接中相邻端点的距离阈值设为不超过50 m，延伸方向角度之差不应超过20°。节点融合中相邻节点距离阈值可设为不超过50 m。重叠相似度阈值设为0.8，在步骤5)完成后，图11中的新增道路最终与原有道路网进行了融合处理。

图3 原始道路网数据 图4 浮动车GPS轨迹点数据 图5 初步生成二值化道路栅格图像Fig.3 Origin road network Fig.4 Float car GPS track points Fig.5 Preliminary construction of binarized road network image

图6 低通滤波 图7 边界清理 图8 骨架线生成

Fig.6 Lowpass filter Fig.7 Boundary clean Fig.8 Construction of skeleton lines

图9 原有道路网缓冲区与骨架线叠加显示 图10 新增道路发现 图11 新增道路与原有道路网的融合

2.3 实例分析

为验证本文方法对道路网变化检测及更新的准确性，特将算法结果与深圳市福田区局部区域最新版导航电子地图(图12，来自于最新访问的主流导航电子地图——“天地图”网站[19])进行比对，道路网的变化部分包括新增道路和消失道路。图11给出了本文方法自动发现的新增道路，图12中黑色粗实线所在道路则是这些新增道路在最新版电子地图中的对应情况，可以看出，图11中的新增道路在现实世界中均有对应道路实体，这就验证了发现新增道路的准确性。

图12 深圳市福田区某区域最新道路网电子地图Fig.12 Newest road network electronic map of Futian District in Shenzhen City

对于消失或封闭道路，一个简单的判断标准是：当某条道路较长时间未有GPS轨迹点落入其缓冲区范围内，则提示该道路可能已消失或封闭。如图11中的道路b，在一天内鲜有浮动车在其缓冲区范围内留下轨迹点(图4)，由此预示道路b为消失道路，但实际生活中，也有一些小路出租车很少行驶，如图11的道路c是公园内一条道路，因此，即使某条道路长时间内无浮动车在缓冲区范围内留下轨迹点，也不能完全说明该条道路已经消失或者封闭，有必要进行实地测量以确保其现势性。

3 结论与展望

本文通过对浮动车轨迹进行数据分析，给出了一种利用大规模浮动车数据发现和更新旧版本道路网数据的有效方法，其意义在于快速发现道路变化，并给出发生变化道路较为准确的位置和形状，而后，导航地图生产商仍可采用原有测量技术，仅对变化信息实地测绘,从而加快更新效率。该技术既具有充分的现势性，且成本较低。事实上，利用浮动车轨迹数据除了可以检测矢量道路网几何信息的变化外，还可从浮动车的运行轨迹推理出道路属性信息的变化，诸如道路车道、单双向限行、转弯限制等的变化。未来随着个人智能手机的进一步普及，大数据的日益充分，通过对这些大众地理数据源的充分和有效分析，将会促进导航地图的持久更新以及挖掘背后所隐藏的数据规律。

[1] 崔铁军,李宏利,郭鹏,等 .导航电子地图增量更新服务及关键技术研究[J].地理信息世界，2011,9(4):36-39.

[2] 王钊.车辆导航电子地图的自增量更新[D].北京:清华大学,2012.

[3] GOODCHILD M F.Citizens as sensors:The world of volunteered geography[J].Geojournal,2007,69(4):211-221.

[4] ELWOOD S,GOODCHILD M F,SUI D Z.Researching volunteered geographic information:Spatial data,geographic research,and new social practice[J].Annals of the Association of American Geographers,2012,102(3):571-590.

[5] 王美玲，程林.浮动车地图匹配算法研究[J].测绘学报，2012,41(1):133-138.

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

[7] WORRALL S,NEBOT E.Automated process for generating digitised maps through GPS data compression[A].Australasian Conference on Robotics and Automation[C].Brisbane:ACRA,2007.1-6.

[8] AGAMENNONI G,NIETO J I,NEBOT E M.Robust inference of principal road paths for intelligent transportation systems[J].IEEE Trans.on Intelligent Transportation Systems,2011,12(1):298-308.

[9] DAVIES J J,BERESFORD A R,HOPPER A.Scalable,distributed,real-time map generation[J].IEEE Pervasive Computing,2006,5(4):47-54.

[10] CHEN C,CHENG Y.Roads digital map generation with multi-track GPS data[A].International Workshop on Geoscience and Remote Sensing,ETT and GRS[C].Shanghai:IEEE,2008.508-511.

[11] SHEN S,LIU Y.Automatic generation of road network map from massive GPS,vehicle trajectories[A].12th International IEEE Conference on Intelligent Transportation Systems[C].St.Louis:IEEE,2009.1-6.

[12] BIAGIONI J,ERIKSSON J.Map inference in the face of noise and disparity[A].The ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].Redondo Beach:ACM,2012.79-88.

[13] CAO L,KRUMM J.From GPS traces to a routable road map[A].Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].New York:ACM,2009.3-12

[14] NIEHOEFER B,BURDA R,WIETFELD C,et al.GPS community map generation for enhanced routing methods based on trace-collection by mobile phones[A].1st International Conference on Advances in Satellite and Space Communications[C].Colmar:IEEE,2009.156-161.

[15] ZHANG L,THIEMANN F,SESTER M.Integration of GPS traces with road map[A].2nd International Workshop on Computational Transportation Science[C].San Jose:ACM,2010.17-22.

[16] BIAGIONI J,ERIKSSON J.Inferring road maps from global positioning system traces:Survey and comparative evaluation[J].Transportation Research Record:Journal of the Transportation Research Board,2012,2291:61-71.

[17] 冈萨雷斯，伍兹(著).阮秋琦(译).数字图像处理(第二版)[M].北京：电子工业出版社，2007.

[18] 邹修明.栅格地图矢量化关键技术研究[D].南京:南京理工大学,2012.

[19] http://www.tianditu.cn/map/index.html[EB/OL].2013-02-15.

Automated Change Detection and Update of Vector Road Network Based on Large Scale Floating Car Data

ZHAO Dong-bao1,LIU Xue-mei2,ZHANG Hong-tao3

(1.InstituteofResourcesandEnvironment,NorthChinaUniversityofWaterConservancyandElectricPower，Zhengzhou450011;2.InstituteofInformationEngineering,NorthChinaUniversityofWaterConservancyandElectricPower，Zhengzhou450011;3.GeomaticsCenterofSichuanProvince,Chengdu610041,China)

Aiming at continued and timely map update of vector road network,this paper realizes an automated change detection and suggestive update of vector road network by analyzing crowdsourcing spatial data-large scale floating car GPS data.The method proposed in this paper firstly rasterize vector road network map by setting a proper grid size,and then assign a value to every pixel according to the count which several days of GPS track points are fall within grid,and final binarized road image can be obtained by further low pass filtering and boundary cleaning.Secondly,skeleton lines of road raster collection which correspond to vector road centerlines can be extracted by means of Mathematical Morphology,and road change including new roads,modified roads and missing roads can be quickly detected by comparing the spatial relationship between road raster area where road skeleton line lie in and buffer area of the existing road centerline.At last,after trimming,merging and connecting the broken skeleton line,skeleton lines,as the updated road centerlines,can be merged into the existing road network finally.

road network update;change detection;floating car technology;GPS track points;volunteer geographic information

2015-08-27；

2015-10-28

四川省地理国情监测工程技术研究中心开放基金项目(GC201510);卫星测绘与应用国家测绘地理信息局重点实验室开放基金项目(KLSMTA-201510);河南省高校科技创新团队支持计划项目(13IRTSTHN023);国家自然科学青年基金项目(41201467)

赵东保(1979-)，男，博士，副教授，主要研究方向为空间数据融合与集成。E-mail:zdongbao@126.com

10.3969/j.issn.1672-0504.2016.02.001

P208;P228.4;U491.116

A

1672-0504(2016)02-0001-05