A Method of Speed-preserving Trajectory Simplification

doi:10.11947/j.AGCS.2017.20170023

Abstract

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

CLC Number:

P208

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.

References

[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.