一种基于关键点的轨迹-区域拓扑过程模型

doi:10.11947/j.AGCS.2015.20140261

测绘学报 ›› 2015, Vol. 44 ›› Issue (11): 1277-1284.doi: 10.11947/j.AGCS.2015.20140261

一种基于关键点的轨迹-区域拓扑过程模型

吴涛¹, 向隆刚^2,3, 龚健雅^2,3

1. 中南大学地球科学与信息物理学院, 湖南长沙 410083;
2. 武汉大学测绘遥感信息工程国家重点实验室, 湖北武汉 430079;
3. 地球空间信息技术协同创新中心, 湖北武汉 430079

收稿日期:2014-05-19 修回日期:2015-07-05 出版日期:2015-11-20 发布日期:2015-11-25
作者简介:吴涛(1984-),男,博士生,主要从事轨迹数据处理与分析。E-mail:blackender@163.com
基金资助:
国家自然科学基金(41001296;60903035)

A Topological Process Model of Trajectories-regions Based on Critical Points

WU Tao¹, XIANG Longgang^2,3, GONG Jianya^2,3

1. School of Geosciences and Info-physics, Central South University, Changsha 410083, China;
2. State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China;
3. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, ChinaAbstract

Received:2014-05-19 Revised:2015-07-05 Online:2015-11-20 Published:2015-11-25
Supported by:
The National Natural Science Foundation of China(Nos. 41001296; 60903035)

摘要/Abstract

摘要： 定位技术的广泛应用带来了铺天盖地的移动数据,为诸如时空查询和数据挖掘等各种时空的研究及应用提供了重要素材,使得对于轨迹数据的研究成为当前的一个热点。当前,无论是对于原始轨迹数据的研究,还是对语义化轨迹数据的研究,都较少考虑轨迹移动过程中所潜藏的拓扑不变量。本文提出二维空间上基于关键点的轨迹-区域拓扑过程模型,以矩阵描述轨迹与区域的14种基本点集拓扑交叠类型,既而组织交叠序列描述轨迹和区域对象间的拓扑关联关系。模型不仅描述了轨迹与区域之间的拓扑不变量,而且结合轨迹特有行为的语义关联模型,描述轨迹相对区域的复杂拓扑过程。同时,本文还以模型中相邻两次交叠的相接交叠模式,探讨了区域间拓扑关系对于轨迹移动描述的约束。

关键词: 拓扑过程, 交叠类型, 语义关联, 相接交叠

Abstract: The increasing pervasiveness of movement data, as a consequence of ubiquitous positioning techniques, has made researches on trajectories in the spotlight, which can facilitate and convey valuable knowledge to various kinds of studies as well as applications, such as spatio-temporal query and data mining. Despite recent research interest on trajectories switched from raw data to semantic trajectories, neither of them take into account topological invariants harbored in movements. This paper develops a topological process model of trajectories-regions based on critical points in a two-dimensional space, which distinguishes 14 basic intersection types, in point set topological theory, between trajectories and region objects by the pattern of a nested matrix, combined as sequences of intersections for describing topological correlations of trajectories-regions. The model is not only a description of topological invariants among trajectories and regions, but also the complicated topological process covering multi-trajectory and multi-region, by incorporating semantics of trajectories' behaviors. Also, constraints on trajectories' movements, brought by topological relations among regions, are discussed in the model by means of intersection linkage patterns between two adjacent intersection events.

Key words: topological process, intersection types, semantic relations, linkage of intersection

中图分类号:

P208

吴涛, 向隆刚, 龚健雅. 一种基于关键点的轨迹-区域拓扑过程模型[J]. 测绘学报, 2015, 44(11): 1277-1284.

WU Tao, XIANG Longgang, GONG Jianya. A Topological Process Model of Trajectories-regions Based on Critical Points[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(11): 1277-1284.

参考文献

[1] ZHENG Yu, ZHOU Xiaofang. Computing with Spatial Trajectories[M]. New York:Springer, 2011.
[2] WOLFSON O, SISTLA P, XU Bo, et al. Tracking Moving Objects Using Database Technology in DOMINO[C]//Proceedings of the 4th Workshop on Next Generation Information Technologies and Systems(NGITS).Zikhron-Yaakov, Israel:[s.n.], 1999:112-119.
[3] GVTING R H, BEHR T, ALMEIDA V, et al. SECONDO:An Extensible DBMS Architecture and Prototype[J]. Collaborative Design, 2004:439-450.
[4] CUDRÉ-MAUROUX P, WU E, MADDEN S. Trajstore:An Adaptive Storage System for Very Large Trajectory Data Sets[C]//ICDE Conference.[S.l.]:IEEE, 2010:109-120.
[5] BUCHIN K, BUCHIN M, VAN KREVELD M, et al. Trajectory Grouping Structure[C]//DEHNE F,SOLIS-OBA R, SACK J R. Proceedings of the 13th International Symposium WADS. Berlin:Springer, 2013:219-230.
[6] POPAI S, ZEITOUNI K, ORIA V, et al. Spatio-temporal Compression of Trajectories in Road Networks[J]. Geoinformatica,2015, 9(1):117-145.
[7] VIEIRA M R, BAKALOV P, TSOTRAS V J. Querying Trajectories Using Flexible Patterns[C]//Proceedings of the 13th International Conference on Extending Database Technology.New York:ACM, 2010:406-417.
[8] FRENTZOS E, GRATSIAS K, THEODORIDIS Y. Index-based Most Similar Trajectory Search[C]//Proceedings of the IEEE International Conference on Data Engineering.Istanbul:IEEE, 2007:816-825.
[9] ZHENG Kai, ZHENG Yu, YUAN N J, et al. On Discovery of Gathering Patterns from Trajectories[C]//Proceedings of the IEEE International Conference on Data Engineering.Washington, D.C.:IEEE, 2013.
[10] CAO Xin, CONG Gao, JENSEN C S. Mining Significant Semantic Locations from GPS Data[J]. Proceedings of the VLDB Endowment,2010, 3(1-2):1009-1020.
[11] HADJIELEFTHERIOU M, KOLLIOS G, GUNOPULOSD, et al. On-line Discovery of Dense Areas in Spatio-temporal Databases[C]//HADZILACOST, MANOLOPOULOS Y, RODDICK J, et al. Advances in Spatial and Temporal Databases.Berlin:Springer,2003:306-324.
[12] LEE J G, HAN Jiawei, LI Xiaolei. Trajectory Outlier Detection:A Partition and Detect Framework[C]//Proceedings of the IEEE International Conference on Data Engineering.Cancun, Mexico:IEEE, 2008:140-149.
[13] QUDDUS M A,OCHIENG W Y, NOLAND R B. Current Map-matching Algorithms for Transport Applications:State-of-the-art and Future Research Directions[J]. Transportation Research Part C:Emerging Technologies, 2007, 15(5):312-328.
[14] SPACCAPIETRA S, PARENT C, DAMIANI M L, et al. A Conceptual View on Trajectories[J]. Data & Knowledge Engineering,2008, 65(1):126-146.
[15] YING J J C, LEE W C, WENG T C, et al. Semantic Trajectory Mining for Location Prediction[C]//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago:ACM,2011:34-43.
[16] KLIPPELA. Spatial Information Theory Meets Spatial Thinking:Is Topology the Rosetta Stone of Spatio-temporal Cognition?[J]. Annals of the Association of American Geographers,2012, 102(6):1310-1328.
[17] EGENHOFER M J, FRANZOSA R D. Point-set Topological Spatial Relations[J]. International Journal of Geographical Information Systems,1991, 5(2):161-174.
[18] KURATAY. Three-valued 9-intersection for Deriving Possible Topological Relations from Incomplete Observations[M]//SESTER M, BERNARD L, PAELKE V.Advances in GIS Science.Berlin:Springer,2009:289-308.
[19] KURATAY. 9⁺-intersection Calculi for Spatial Reasoning on the Topological Relations between Heterogeneous Objects[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose, CA:ACM, 2010:390-393.
[20] LI Zhilin, ZHAO Renliang, CHEN Jun. A Voronoi-based Spatial Algebra for Spatial Relations[J]. Progress in Natural Science,2002, 12(7):528-536.
[21] DENG Min, MA Hangying. The Hierarchical Representation of Topological Relations between a Line and an Area[J]. Acta Geodaetica et Cartographica Sinica,2008, 37(4):507-520.(邓敏, 马杭英. 线与面目标间拓扑关系的层次表达方法[J]. 测绘学报,2008, 37(4):507-520.)
[22] GUO Qingsheng, CHEN Yujian, LIU Hao. Combinational Reasoning of Spatial Topological Relations between a Line and an Area[J]. Geomatics and Information Science of Wuhan University,2005, 30(6):529-532.(郭庆胜, 陈宇箭, 刘浩. 线与面的空间拓扑关系组合推理[J]. 武汉大学学报:信息科学版,2005, 30(6):529-532.)
[23] ZHOU Xiaoguang, CHEN Jun, LI Zhilin, et al. Computation of Topological Relations between Cadastral Objects Based on Euler-number[J]. Acta Geodaetica et Cartographica Sinica,2006, 35(3):293-298.(周晓光, 陈军, 李志林, 等. 基于欧拉数的地籍拓扑关系计算[J]. 测绘学报,2006, 35(3):293-298.)
[24] ZHOU Xiaoguang, CHEN Jun, ZHAN FB, et al. A Euler Number-based Topological Computation Model for Land Parcel Database Updating[J]. International Journal of Geographical Information Science,2013, 27(10):1983-2005.
[25] ZHOU Xiaoguang, CHEN Fei, CHEN Jun. A Node-degree Based Line/Region Topological Relationship Refinement Model and Its Applications[J]. Acta Geodaetica et Cartographica Sinica,2015, 44(4):445-452.(周晓光, 陈斐, 陈军. 引入结点度的线面拓扑关系细分方法与应用[J]. 测绘学报,2015, 44(8):445-452.)
[26] SESTERM, FEUERHAKE U, KUNTZSCH C, et al. Revealing Underlying Structure and Behaviour form Movement Data[J]. Künstliche Intelligenz,2012, 26(3):223-231.
[27] EGENHOFER M J, MARK D M. Modeling Conceptual Neighborhoods of Topological Line-region Relations[J]. International Journal of Geographical Information Systems,1995, 9(5):555-565.

一种基于关键点的轨迹-区域拓扑过程模型

A Topological Process Model of Trajectories-regions Based on Critical Points

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	邵晓航, 吴杭彬, 刘春, 陈晨, 蔡天池, 程帆瑾. 语素关联约束的动态环境视觉定位优化[J]. 测绘学报, 2021, 50(11): 1478-1486.
[2]	姚连璧, 秦长才, 张邵华, 陈启超, 阮东旭, 聂顺根. 车载激光点云的道路标线提取及语义关联[J]. 测绘学报, 2020, 49(4): 480-488.