符合认知规律的时空轨迹融合与路网生成方法

唐炉亮，刘 章，杨 雪，阚子涵，李清泉，董 坤

1．武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉430079；2．航天恒星科技有限公司（503所），北京100086

1 引 言

随着城乡交通的飞速发展，人们出行时对精细程度高、现势性好的道路信息需求迫在眉睫［1］，同时，人们每天穿行于城市道路网中，会产生海量时空轨迹数据，是精细道路数据的产生者和感知者，如何从人们日常出行的海量时空轨迹中挖掘和提取出人们出行需求的道路信息，成为全世界科学家们面临的科学难题。

目前，从时空GPS轨迹数据中提取道路网信息的研究已经开展了相关的探索性工作，主要分为3类方法：第1类研究主要采用栅格化方法将轨迹数据栅格化后提取道路的中心线，如文献［2］将GPS轨迹数据生成栅格地图并从中提取矢量路网地图，文献［3］将车辆行驶轨迹栅格化，再利用图像细化算法提取出道路中心线，生成道路网络，这类方法主要是将轨迹数据栅格化后提取道路网信息，但栅格化会丢失了原始轨迹的连通信息，对于路网拓扑的提取存在困难；第2类研究主要是采用增量化的方法，如文献［4］提出了一种基于单个轨迹线与原有路网图形增量的路网生成方法，文献［5］通过判断轨迹点与候选路网的空间和语义关系来实现路网增量化生成，这类方法需要旧的路网图作为参考，精度也会受到参考路网的限制；第3类研究主要是采用轨迹聚类的方法，如文献［6］利用轨迹聚类方法进行车道位置的提取和道路交叉口结构的生成，文献［7］利用统计分析方法，从大量GPS轨迹中生成高精度路网地图，文献［8］通过路口转向判断模型来实现轨迹的分类，最终利用轨迹聚类来实现路网的提取，这类研究主要采用轨迹聚类的方法，将大量轨迹进行一次性聚类融合，但基于轨迹提取路网从其实现过程来说，是将多次体验得到的轨迹进行多次融合加工与不断对路网精细化的过程，是人们对陌生环境不断体验和认知加工的过程，因此，这种一次将所有轨迹进行聚类提取路网的研究不符合认知规律和加工过程。

本文通过研究发现，从时空GPS轨迹数据生成城市道路信息的本质，是人们对城市路网进行多次体验，将得到的轨迹进行多次融合加工，并对路网不断精细化和修正的过程，是一个从少到多、从粗到细、从简到繁、从局部到整体的过程，也是符合人们对陌生环境不断体验和认知加工的过程，符合人们的空间认知规律。因此，从时空GPS轨迹数据中提取道路网信息应该遵循空间认知规律，实现对城市道路网络信息不断丰富和精细化。

2 空间认知规律与基于时空轨迹融合生成路网的本质

对空间的认知包含空间特征感知、空间对象认知和空间格局认知［9－11］3个层次。第1个认知层次是空间局部特征感知阶段，当人们对某陌生空间进行初次体验和感知时，会应用各种有关感知手段和方法来观察空间实体的各个组成部分，以获得有关空间实体各组成部分的特征；第2个认知层次是对空间进行了多次（一定数量）认知体验后，会形成该空间内实体的“部分—整体”（part－whole）关系，将空间实体各组成部分之间的特征进行集成，来实现对于该空间实体的对象化认识，属于对象认知阶段［12－13］；第3个认知层次是当人们对该空间进行更多次体验后，会以有关空间实体的“部分—整体”关系为指导，对空间实体进行对象化符号表达，实现有关空间组织、结构与关系的逻辑判断、归纳演绎与推理分析，形成该空间的格局认知，属于空间格局认知阶段［14－16］。基于出租车时空GPS轨迹融合生成路网的本质是通过出租车GPS对城市路网的多次体验，形成城市路网空间格局的认知过程。

2．1 路网特征感知层次

司机对路网的初次体验是司机首次对路网探测行为，司机在道路选择上会形成自己的认知［17］，当出租车GPS轨迹首次记录到城市路网的体验时，会感知城市路网的道路形状等特征，是对路网的一种局部的、抽象的特征感知，属于空间认知的第1个特征感知层次，初次体验的轨迹探测出来的是城市路网的骨干道路与路网基本轮廓。

2．2 路网对象认知层次

当出租车进行多次体验时，局部的、低等级道路会被遍历到，城市路网图形细节层次进一步丰富，形成对城市道路实体的对象认知，这属于空间认知的第2个空间对象认知层次。多次体验的轨迹线在路口处会产生各种不同的行驶选择，轨迹线相互之间存在部分重叠，首先对新加入的轨迹线进行轨迹分段，针对轨迹间重叠区域，利用下文所叙述的基于Delaunay三角网的轨迹线融合方法，依次将不同轨迹段中相似的轨迹线部分融合起来，以实现多次体验的路网图的生成，形成包含丰富实体对象的城市道路网图。

2．3 路网格局认知层次

随着体验次数的进一步增加，路网图形信息会变得越来越丰富与精细，通过对道路空间特征与道路实体对象进行简化、关联及综合加工，使得道路网图形与真实路网越来越逼近，形成对路网的精细化表达，属于路网格局认知阶段，最终实现道路网数据的生成。

3 基于认知规律的时空GPS轨迹融合与路网生成方法

初次体验的轨迹线在图上表现为道路网粗略的道路轮廓信息，随着体验次数的增加，司机对于道路网的认知会越来越丰富与完善，具体表现在新道路的识别和重复道路的细节层次进一步精细加工。本文提出基于Delaunay三角网的时空轨迹线融合方法，不断将新添加的轨迹线与之前融合生成的融合轨迹线进行再次融合，得到更加丰富细致的道路图。

3．1 路网特征感知层次

出租车在道路网上的行驶轨迹，是对路网的一次次体验，把它们抽象为路网的组成部分。路网特征感知阶段就是从GPS轨迹点数据中还原出一条条出租车行驶轨迹，以获得关于路网各组成部分的特征。

出租车轨迹点数据包含车辆的ID、采样时间、行驶速度、地理坐标等信息，因此直接根据一辆车的GPS轨迹点的时间序列将轨迹点数据连接起来就能得到一条出租车行驶轨迹。但是当出租车行驶在城市道路上时，一方面由于城市道路两旁的高楼、树木等物体的遮挡，会造成GPS定位不准的问题［18］；另一方面在城市隧道和高架桥等区域会存在GPS信号中断的问题。

针对定位不准所造成的轨迹点漂移的情况，需要跟踪轨迹点前后点的速度与位置信息来预判该点可能出现的范围，如果该点的实际位置超出了预判范围，则视为偏移点，将偏移点按照轨迹还原的方法纠正到正确的位置上，以此排除定位不准所带来的不利影响。

针对信号中断所造成的GPS轨迹点丢失的情况，需要对丢失段的GPS轨迹进行轨迹还原。如果丢失轨迹段较短，并没有跨越多条道路段，则通过丢失路段前后的轨迹点行驶速度和距离来内插实现丢失轨迹段的还原；如果丢失轨迹段跨越了多条道路段，由于还原后的轨迹点往往误差较大，则直接将该轨迹数据视为无效的轨迹数据进行删除，以此排除信号中断所带来的不利影响。

3．2 路网对象认知层次

路网的对象认知阶段就是通过GPS轨迹线之间的不断融合，将不同GPS轨迹线所包含的特征进行集成，实现对路网的对象化认知，以提取出更加丰富细致的路网。

3．2．1 轨迹分段

将初次体验得到的轨迹作为融合前轨迹，将新轨迹逐条与融合前轨迹进行融合，如果新轨迹线与融合前轨迹没有任何交集，则直接将新轨迹添加到融合前轨迹中，如果新轨迹与融合前轨迹有轨迹重合部分，则需要将轨迹重合部分进行分段融合，因此轨迹分段是融合前必备的准备工作（图1），图1（a）和（b）部分是两种不同的分段情况，图1（a）中新轨迹与融合前轨迹存在部分重合轨迹段，在轨迹分离的地方打断（如图1（a）轨迹分段所示），将重合轨迹部分标记为待融合的相似轨迹（如图1（a）融合后的轨迹所示）。图1（b）中新轨迹与融合前轨迹相交，但没有重合的轨迹段，在轨迹相交的部分将两条轨迹打断并记录交点（如图1（b）轨迹分段所示），将交点插入到两条轨迹之中，生成融合后轨迹。

图1 相似轨迹分段Fig．1 Similar trajectory subsection

3．2．2 基于两条相似轨迹线约束的Delaunay

三角形构网

Delaunay三角网在空间邻近分析上是一种较好的支持模型，在多边形群的合并、地图综合冲突关系探测与移位处理、地貌形态分析中，取得了令人满意的结果［19－21］。本文针对相似轨迹段的融合，将两条相似轨迹作为约束线，采用基于线约束的Delaunay三角形构网，如图2所示，具体的三角形构网方法如下：

（1）在图2中，粗线为融合前轨迹，细线为新轨迹。注意轨迹点上带有权重值，定义新添加的轨迹线上轨迹点的权重值为1，初始轨迹线上融合轨迹点的权重值与生成该轨迹线的轨迹线数目n相等。

（2）判断轨迹是否存在相交部分，若存在，在交点处打断并记录交点。

（3）依据Delaunay构网的准则：三角网中任何三角形的外接圆范围内不会有其他点存在并与其通视。

图2 相似轨迹段基于线约束的Delaunay三角形构网Fig．2 Constrained Delaunay TIN making in the similar trajectory segment

3．2．3 轨迹的融合

从上一步构造的Delaunay三角网中提取融合后轨迹，需要分析Delaunay三角网络中各个三角形相互之间边与边的邻接关系，主要存在两类邻接状态，如图3所示，其融合后轨迹生成的方式分别为：

第Ⅰ类三角形，与其他三角形有两条邻接边的三角形，融合后轨迹是两条邻接边的权值比分割点的连线。

第Ⅱ类三角形，与其他三角形只有一条邻接边的三角形，融合后轨迹是邻接边权值比分割点与其相对的端点的连线。

在第Ⅰ类、第Ⅱ类三角形中，权值比分割点P是由A、B点计算得出

剔除掉包含辅助点的三角形中的融合线段，依次连接其余各个Delaunay三角形中所生成的融合线段，并记录方向和经验权值，即可得到基于Delaunay三角网的融合后轨迹，当需要进行进一步进行轨迹融合时，将生成的融合后轨迹线作为融合前轨迹线，与新添加的轨迹一起重新融合，构建三角网生成融合轨迹，直到所有相似轨迹线参与融合为止。

综上所述，基于Delaunay三角网的轨迹融合方法，重点在于针对具有相似轨迹的轨迹线簇，逐条加入进行Delaunay三角形构网，使得融合得到的轨迹线逐步完善，趋近于真实的道路线。

3．3 路网格局认知层次

在路网特征感知和对象认知的基础上，通过对道路空间特征与道路实体对象进行简化、关联及综合加工，使得道路网的图形更加逼真，形成对路网的精细化表达，最终实现道路网数据的生成，属于路网格局认知阶段。

随着更多的轨迹线参与融合，生成的融合后轨迹线会更趋近于真实的道路线，这符合空间认知的规律——随着体验次数的增加，司机对于道路网的认知会更为丰富和完善。司机对路网的初次体验是司机首次对路网探测行为，从中可以获取到一条理论可行的行驶轨迹线，当对路网进行多次体验时，在路口处会产生各种不同的行驶选择，轨迹线相互之间存在部分重叠，首先对新加入的轨迹线进行轨迹分段，针对轨迹间重叠区域，利用上文所叙述的基于Delaunay三角网的轨迹线融合方法，依次将不同轨迹段中相似的轨迹线部分融合起来，来实现多次体验的路网图（road network）的生成，如图3所示。

图3 路网图形数据的生成Fig．3 The road network graphical data generation

4 试验分析与同类方法比较

本试验在普通PC上进行，配置为Intel Core i3，CPU 3．07 GHz，内存8 GB，以 Microsoft Visual Studio 2010 C＃为工具开发了时空轨迹融合与路网生成模型与算法。试验数据来源于武汉市出租车3月8日至3月14日之间一周内采集的出租车GPS轨迹数据，选取武汉体育中心周围一定范围作为试验区域（图4）。首先对GPS轨迹点数据进行预处理，经过漂移和丢失情况的处理后，依据车辆ID和采样时间将轨迹点依次连接，生成一条轨迹线；依据时间序列将轨迹线逐条加入基于Delaunay三角网的融合模型，依次进行轨迹分段、Delaunay三角构网和轨迹融合，生成路网图。本文实现的轨迹线共有3765条，分别截取4条轨迹线（初次体验）、400条轨迹线（多次体验）以及3765条轨迹线（全部体验）的融合结果，得到不同阶段的路网图进行分析。试验结果显示初次体验的轨迹探测出来的是城市路网的骨干道路与路网基本轮廓（图4（a））；随着出租车司机对路网体验次数的增加，局部的、低等级道路会被遍历，城市路网的图形细节层次进一步丰富，形成对城市道路实体的对象图（图4（b））；随着体验次数的进一步增加，路网图形信息会变得丰富和精细，通过对道路空间特征与道路实体对象进行简化、关联及综合加工，形成对路网的精细化表达，最终实现道路网数据的生成（图4（c））。

将试验结果图与影像图叠加在一起进行定性评价，如图4（d）所示，可以清晰看出，生成的道路图基本完全覆盖了试验区域的所有道路，且准确性很高。

图4 武汉体育中心试验结果与影像图对比Fig．4 Wuhan Sports Center results in contrast with the image maps

为了定量检测试验结果的位置精度，本文采用文献［22］提出的缓冲区检测方法来评价道路数据提取的有效性，该方法以标准矢量地图为基准，作缓冲区分析，计算试验结果与标准路网数据的距离，通过缓冲区的叠合对试验结果进行质量百分比统计。本文选择了标准矢量地图总长度221．53 km的武汉城市道路为试验路网，将本文提出方法试验结果与文献［23］方法试验结果进行对比，采用相同精度2 m、5 m和7 m为半径建立缓冲区进行分析，得到不同精度半径缓冲区的道路长度统计百分比结果，如图5所示。

图5 精度评价Fig．5 Accuracy assessment

从图5分析可知，当精度分别以2 m、5 m和7 m为半径建立缓冲区时，本文方法提取路网长度百分比分别达到64．3%、76．2%和81．6%，与文献［23］的结果相比统计百分比有明显的提高，尤其在2 m高精度为半径缓冲区得到的路网占64．3%，较27．4%有大幅度提高，说明本文提出的方法所得到的试验结果更贴近于真实的道路网，进一步验证了基于认知的道路网提取方法能更准确地从浮动车时空轨迹数据中提取道路网。

5 结 论

本文方法对于城市主干支路道路网的形状、轮廓信息能有效获取，但是部分小区级支路复杂、形状变化多样，而出租车GPS采样频率为40 s左右，导致小区级道路形状探测困难。在今后的研究中，将进一步优化模型，解决小区级支路探测难题。

致谢：感谢深圳市北斗卫星应用工程技术研究中心提供的帮助。

［1］ AGO Y．Availability and Pricing of Georeferenced Data in Asia Pacific［M］∥TAYLOR D R F．Policy Issues in Modern Cartography．London：Pergamon，1998：46－69．

［2］ KONG Qingjie，SHI Wenhuan，LIU Yuncai．A GPS－track－based Method for Automatically Generating Roadnetwork Vector Map［J］．Journal of University of Science and Technology of China，2012，42（8）：623－627．（孔庆杰，史文欢，刘允才．基于GPS轨迹的矢量路网地图自动生成方法［J］．中国科学技术大学学报，2012，42（8）：623－627．）

［3］ 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．（蒋益娟，李响，李小杰，等．利用车辆轨迹数据提取道路网络的几何特征与精度分析［J］．地球信息科学学报，2012，14（2）：165－170．）

［4］ BRUNTRUP R，EDELK A MP S，JABBAR S，et al．Incremental Map Generation with GPS Traces［C］∥Proceedings of the 2005 Intelligent Transportation Systems．Vienna：IEEE，2005：574－579．

［5］ LI Jun，QIN Qiming，XIE Chao，et al．Integrated Use of Spatial and Semantic Relationships for Extracting Road Networks from Floating Car Data［J］．International Journal of Applied Earth Observation and Geoinformation，2012，19：238－247．

［6］ 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．

［7］ GUO Tao，IWAM URA K，KOGA M．Towards High Accuracy Road Maps Generation from Massive GPS Traces Data［C］∥Proceedings of the 2007 IEEE International Geoscience and Remote Sensing Symposium．Barcelona：IEEE，2007：667－670．

［8］ KARAGIORGOU S，PFOSER D．On Vehicle Tracking Data－based Road Network Generation［C］∥Proceedings of the 20th International Conference on Advances in Geographic Information Systems．New York：ACM，2012：89－98．

［9］ HART R A，MOORE G T．The Development of Spatial Cognition： A Review ［M ］． Chicago： Aldine Transaction，1973．

［10］ DENIS M．The Description of Routes：A Cognitive Approach to the Production of Spatial Discourse［J］．Cahiers de Psychologie Cognitive，1997，16（4）：409－458．

［11］ WANG Xiaoming，LIU Yu，ZHANG Jing．Geo－spatial Cognition：An Overview［J］．Geography and Geo－Information Science，2005，21（6）：1－10．（王晓明，刘瑜，张晶．地理空间认知综述［J］．地理与地理信息科学，2005，21（6）：1－10．）

［12］ BURGESS N．Spatial Cognition and the Brain［J］．Annals of the New York Academy of Sciences，2008，1124（1）：77－97．

［13］ ALIBALI M W．Gesture in Spatial Cognition：Expressing，Communicating，and Thinking about Spatial Information［J］．Spatial Cognition and Computation，2005，5（4）：307－331．

［14］ DENIS M，PAZZAGLIA F，CORNOLDI C，et al．Spatial Discourse and Navigation：An Analysis of Route Directions in the City of Venice［J］．Applied Cognitive Psychology，1999，13（2）：145－174．

［15］ M A Ronghua，M A Xiaodong，PU Yingxia．Spatial Association Rule Mining from GIS Database［J］．Journal of Remote Sensing，2005，9（6）：733－741．（马荣华，马晓冬，蒲英霞．从GIS数据库中挖掘空间关联规则研究［J］．遥感学报，2005，9（6）：733－741．）

［16］ GOLLEDGE R G．Wayfinding Behavior：Cognitive Mapping and Other Spatial Processes［M］．Johns Hopkins：Johns Hopkins University Press，1999．

［17］ TANG Luliang，CHANG Xiaomeng，LI Qingquan．The Knowledge Modeling and Route Planning Based on Taxi’Experience［J］．Acta Geodaetica et Cartographica Sinica，2010，39（4）：404－409．（唐炉亮，常晓猛，李清泉．出租车经验知识建模与路径规划算法［J］．测绘学报，2010，39（4）：404－409．）

［18］ SU Jie，ZHOU Dongfang，YUE Chunsheng．Real－time Map－matching Algorithm in GPS Navigation System for Vehicles［J］．Acta Geodaetica et Cartographica Sinica，2001，30（3）：252－256．（苏洁，周东方，岳春生．GPS车辆导航中的实时地图匹配算法［J］．测绘学报，2001，30（3）：252－256．）

［19］ AI Tinghua，GUO Renzhong．A Constrained Delaunay Partitioning of Areal Objects to Support Map Generalization［J］．Journal of Wuhan Technical University of Surveying and Mapping，2000，25（1）：35－41．（艾廷华，郭仁忠．支持地图综合的面状目标约束Delaunay三角网剖分［J］．武汉测绘科技大学学报，2000，25（1）：35－41．）

［20］ JONES C B，BUNDY G L，WARE M J．Map Generalization with a Triangulated Data Structure［J］．Cartography and Geographic Information Systems，1995，22（4）：317－331．

［21］ GROSS J L，TUCKER T W．Topological Graph Theory［M］．［S．l．］：Courier Corporation，1987．

［22］ GOODCHILD M F，HUNTER G J．A Simple Positional Accuracy Measure for Linear Features［J］．International Journal of Geographical Information Science，1997，11（3）：299－306．

［23］ ZHANG Lijuan，THIEMANN F，SESTER M．Integration of GPS Traces with Road Map［C］∥Proceedings of the 2nd International Workshop on Computational Transportation Science．New York：ACM，2010：17－22．