保持移动速度特征的轨迹线化简方法

doi:10.11947/j.AGCS.2017.20170023

测绘学报 ›› 2017, Vol. 46 ›› Issue (12): 2016-2023.doi: 10.11947/j.AGCS.2017.20170023

保持移动速度特征的轨迹线化简方法

杨敏^1,3,4, 陈媛媛^1,2, 金澄⁵, 程前¹

1. 武汉大学资源与环境科学学院, 湖北武汉 430072;
2. 北京大学遥感与地理信息系统研究所, 北京 100871;
3. 国土资源部城市土地资源监测与仿真重点实验室, 广东深圳 518034;
4. 地理国情监测国家测绘地理信息局重点实验室, 湖北武汉 430072;
5. 西安测绘研究所, 陕西西安 710054

收稿日期:2017-01-13 修回日期:2017-09-29 出版日期:2017-12-20 发布日期:2017-12-28
通讯作者: 陈媛媛 E-mail:ygrittechen@pku.edu.cn
作者简介:杨敏(1985-),男,博士,副教授,研究方向为地图综合、多源数据集成与更新。E-mail:yangmin2003@whu.edu.cn
基金资助:
国家自然科学基金（41401447）；国土资源部城市土地资源监测与仿真重点实验室开放基金（KF-2016-02-020）；地理国情监测国家测绘地理信息局重点实验室开放基金（2015NGCM）

A Method of Speed-preserving Trajectory Simplification

YANG Min^1,3,4, CHEN Yuanyuan^1,2, JIN Cheng⁵, CHENG Qian¹

1. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430072, China;
2. Institute of Remote Sensing & Geographical Information System, Peking University, Beijing 100871, China;
3. Key Laboratory of Urban Land Resources Monitoring and Simulation, Ministry of Land and Resources, Shenzhen 518034, China;
4. Key Laboratory for National Geographic Census and Monitoring, National Administration of Surveying, Mapping and Geoinformation, Wuhan 430072, China;
5. Xi'an Research Institute of Surveying and Mapping, Xi'an 710054, China

Received:2017-01-13 Revised:2017-09-29 Online:2017-12-20 Published:2017-12-28
Supported by:
The National Natural Science Foundation of China (No. 41401447) The Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation,Ministry of Land and Resources (No. KF-2016-02-020) The Open Fund of Key Laboratory for National Geographic Census and Monitoring,National Administration of Surveying,Mapping and Geoinformation (No. 2015NGCM)

摘要/Abstract

摘要： 轨迹线数据实施化简处理对于缓解数据存储、传输压力以及后期的分析可视化效率具有重要意义。常规方法（如Douglas-Peucker算法）主要考虑线目标的几何形态结构，直接应用到轨迹线化简中容易丢失移动物体的运动状态特征。本研究从保持轨迹线隐含速度特征出发，提出了一种基于移动速度相似性原则的轨迹线层次化剖分与分区化简处理方法。首先，以相邻轨迹点构成的直线段为基本单元，在拓扑连接关系约束下基于速度指标对轨迹直线段进行层次化聚类，并将聚类结果组织为层次树结构；然后，以建立的层次树结构为约束条件对原始轨迹线实施分区处理，使得同一区域内轨迹线片段的中间点距首尾基准线的最大时间同步偏移距离小于设定的阈值；最后，依次连接各分区轨迹线片段首尾点导出化简结果。采用真实的车辆轨迹线作为试验数据，通过与其他多种方法进行对比分析验证了本文提出方法的有效性。

关键词: 轨迹线数据, 化简, 聚类分析, 速度保持

Abstract: Trajectory simplification plays an important role in trajectory data storage,transmission,temporal-spatial analysis and visualization.Traditional simplification methods,such as Douglas-Peucker algorithm,concern the geometric information while ignore the temporal information,which may result in loss of implied mobility features in the original trajectory.Aiming at minimize speed error in the trajectory simplification transformation,this paper presents a new method based on hierarchical clustering and regionalization operations.First,the line segments of the original trajectory are clustered at different levels based on the similarity of speed measure.With the support of the hierarchical clusters,the original trajectory is then divided into a series of segments.For each segment,the maximum synchronized Euclidean distance from the points to the segment line connecting two end points is no larger than the predefined threshold value.Finally,the simplified results is outputted by organizing the end points of each trajectory segments.Real life data was used to verity the effectiveness of the proposed method,and results of comparing with other existing methods showed that our method performs better in speed preserving.

Key words: trajectory data, simplification, clustering analysis, speed preservation

中图分类号:

P208

杨敏, 陈媛媛, 金澄, 程前. 保持移动速度特征的轨迹线化简方法[J]. 测绘学报, 2017, 46(12): 2016-2023.

YANG Min, CHEN Yuanyuan, JIN Cheng, CHENG Qian. A Method of Speed-preserving Trajectory Simplification[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(12): 2016-2023.

参考文献

[1] ZHENG Yu,XIE Xing,MA Weiying.GeoLife:A Collaborative Social Networking Service among User,Location and Trajectory[J].IEEE Data(Base)Engineering Bulletin,2010,33(2):32-39.
[2] 刘瑜,肖昱,高松,等.基于位置感知设备的人类移动研究综述[J].地理与地理信息科学,2011,27(4):8-13. LIU Yu,XIAO Yu,GAO Song,et al.A Review of Human Mobility Research Based on Location Aware Devices[J].Geography and Geo-Information Science,2011,27(4):8-13.
[3] 李清泉,黄练.基于GPS轨迹数据的地图匹配算法[J].测绘学报,2010,39(2):207-212. LI Qingquan,HUANG Lian.A Map Matching Algorithm for GPS Tracking Data[J].Acta Geodaetica et Cartographica Sinica,2010,39(2):207-212.
[4] 唐炉亮,刘章,杨雪,等.符合认知规律的时空轨迹融合与路网生成方法[J].测绘学报,2015,44(11):1271-1276,1284.DOI:10.11947/j.AGCS.2015.20140591. 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,1284.DOI:10.11947/j.AGCS.2015.20140591.
[5] MUCKELL J,OLSEN Jr P W,HWANG J H,et al.Compression of Trajectory Data:A Comprehensive Evaluation and New Approach[J].GeoInformatica,2014,18(3):435-460.
[6] 武芳,邓红艳.基于遗传算法的线要素自动化简模型[J].测绘学报,2003,32(4):349-355.DOI:10.3321/j.issn:1001-1595.2003.04.013. WU Fang,DENG Hongyan.Using Genetic Algorithms for Solving Problems in Automated Line Simplification[J].Acta Geodaetica et Cartographica Sinica,2003,32(4):349-355.DOI:10.3321/j.issn:1001-1595.2003.04.013.
[7] 钱海忠,武芳,陈波,等.采用斜拉式弯曲划分的曲线化简方法[J].测绘学报,2007,36(4):443-449,456.DOI:10.3321/j.issn:1001-1595.2007.04.014. QIAN Haizhong,WU Fang,CHEN Bo,et al.Simplifying Line with Oblique Dividing Curve Method[J].Acta Geodaetica et Cartographica Sinica,2007,36(4):443-449,456.DOI:10.3321/j.issn:1001-1595.2007.04.014.
[8] 艾廷华,郭仁忠,刘耀林.曲线弯曲深度层次结构的二叉树表达[J].测绘学报,2001,30(4):343-348.DOI:10.3321/j.issn:1001-1595.2001.04.013. AI Tinghua,GUO Renzhong,LIU Yaolin.A Binary Tree Representation of Curve Hierarchical Structure in Depth[J].Acta Geodaetica et Cartographica Sinica,2001,30(4):343-348.DOI:10.3321/j.issn:1001-1595.2001.04.013.
[9] DOUGLAS D H,PEUCKER T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].Cartographica:The International Journal for Geographic Information and Geovisualization,1973,10(2):112-122.
[10] LI Zhilin,OPENSHAW S.Algorithms for Automated Line Generalization¹ Based on a Natural Principle of Objective Generalization[J].International Journal of Geographical Information Systems,1992,6(5):373-389.
[11] VISVALINGAM M,WHYATT J D.Line generalisation by repeated elimination of points[J].The Cartographic Journal,1993,30(1):46-51.
[12] KEOGH E,CHU S,HART D,et al.An online algorithm for segmenting time series[C]//Proceedings of 2001 IEEE International Conference on Data Mining (ICDM).San Jose,CA:IEEE,2001:289-296.
[13] POTAMIAS M,PATROUMPAS K,SELLIS T.Sampling Trajectory Streams with Spatiotemporal Criteria[C]//Proceedings of the 18th International Conference on Scientific and Statistical Database Management (SSDBM).Vienna,Austria:IEEE,2006:275-284.
[14] TRAJCEVSKI G,CAO Hu,SCHEUERMANN P,et al.On-line Data Reduction and The Quality of History in Moving Objects Databases[C]//Proceedings of the 5th ACM International Workshop on Data Engineering for Wireless and Mobile Access(MobiDE).Chicago,Illinois:ACM,2006:19-26.
[15] CHEN Yukun,JIANG Kai,ZHENG Yu,et al.Trajectory Simplification Method for Location-Based Social Networking Services[C]//Proceedings of the 2009 International Workshop on Location Based Social Networks.Seattle,Washington:ACM,2009:33-40.
[16] LONG Cheng,WONG R C W,JAGADISH H V.Trajectory Simplification:on Minimizing the Direction-Based Error[J].Proceedings of the VLDB Endowment,2014,8(1):49-60.
[17] 唐炉亮,杨雪,牛乐,等.一种众源车载GPS轨迹大数据自适应滤选方法[J].测绘学报,2016,45(12):1455-1463.DOI:10.11947/j.AGCS.2016.20160117. TANG Luliang,YANG Xue,NIU Le,et al.An Adaptive Filtering Method Based on Crowdsourced Big Trace Data[J].Acta Geodaetica et Cartographica Sinica,2016,45(12):1455-1463.DOI:10.11947/j.AGCS.2016.20160117.
[18] ASSUNÇÃO R M,NEVES M C,CÂMARA G,et al.Efficient Regionalization Techniques for Socio-Economic Geographical Units Using Minimum Spanning Trees[J].International Journal of Geographical Information Science,2006,20(7):797-811.
[19] GUO D.Regionalization with Dynamically Constrained Agglomerative Clustering and Partitioning (REDCAP)[J].International Journal of Geographical Information Science,2008,22(7):801-823.

保持移动速度特征的轨迹线化简方法

A Method of Speed-preserving Trajectory Simplification

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	杜佳威, 武芳, 朱丽, 刘呈熠, 王安东. 图形、图像融合利用的集成学习智能化简方法及其在岛屿岸线化简中的应用[J]. 测绘学报, 2022, 51(3): 373-387.
[2]	晏雄锋, 袁拓, 杨敏, 孔博, 刘鹏程. 建筑物形状特征分析表达与自适应化简方法[J]. 测绘学报, 2022, 51(2): 269-278.
[3]	李毓照, 闫浩文, 王世杰, 杨维芳. BDS三频信号最优组合的模糊聚类分析法[J]. 测绘学报, 2020, 49(8): 974-982.
[4]	尹烁, 闫小明, 晏雄锋. 基于特征边重构的建筑物化简方法[J]. 测绘学报, 2020, 49(6): 703-710.
[5]	程绵绵, 孙群, 徐立, 陈换新. 面轮廓线相似性和复杂性度量及在化简中的应用[J]. 测绘学报, 2019, 48(4): 489-501.
[6]	张立华, 唐露露, 贾帅东, 戴泽源. 多条海岸线协同化简的层次化三角网分区法[J]. 测绘学报, 2019, 48(4): 520-531.
[7]	杜佳威, 武芳, 李靖涵, 行瑞星, 巩现勇. 一种河口湾海岸线渐进化简方法[J]. 测绘学报, 2018, 47(4): 547-556.
[8]	李成名, 郭沛沛, 殷勇, 武鹏达, 顾腾. 一种顾及空间关系约束的线化简算法[J]. 测绘学报, 2017, 46(4): 498-506.
[9]	晏雄锋, 艾廷华, 杨敏. 居民地要素化简的形状识别与模板匹配方法[J]. 测绘学报, 2016, 45(7): 874-882.
[10]	陈竞男, 钱海忠, 王骁, 何海威, 胡慧明. 提高线要素匹配率的动态化简方法[J]. 测绘学报, 2016, 45(4): 486-493.
[11]	刘民士, 龙毅, 费立凡. 顾及拓扑一致性的水系三维曲线化简[J]. 测绘学报, 2016, 45(4): 494-501.
[12]	何海威, 钱海忠, 王骁, 胡慧明, 陈竞男. 采用弯曲进行道路化简冲突避免的方法[J]. 测绘学报, 2016, 45(3): 354-361.
[13]	彭福凯, 沈云中. 长江口EnviSat测高数据的波形分类重构分析[J]. 测绘学报, 2015, 44(6): 616-624.
[14]	邓敏樊子德刘慧敏. 基于层次信息量的线要素化简算法性能评价研究[J]. , 2013, 42(5): 767-773.
[15]	黄亚锋艾廷华刘耀林张航峰. 顾及地理特征保持的溺谷海岸线化简算法[J]. , 2013, 42(4): 0-0.