基于大规模船舶轨迹数据的航道边界提取方法
|
摘要
传统的道路数据获取方法成本高、更新慢等无法适用于海洋航道的获取,从众源轨迹数据中提取道路或航道信息具有成本低、更新快等特性,然而,由于船舶轨迹数据噪声多、数据量大、不同区域分布不均使得航道边界提取面临较大挑战。针对该问题,提出一种基于大规模船舶轨迹数据进行航道边界提取的方法。首先对大规模的船舶轨迹数据进行并行化去噪、插值、轨迹分段;然后,基于并行化及基于Geohash编码的空间聚类,将轨迹数据化简为多个方形区域的点集数据;其次,对其进行窗口划分,对传统的Ni Black方法进行扩展,提出Spatial Ni Black算法,对方形区域进行航道识别;最后,提出一种新的提取算法del-alpha-shape,基于航道识别结果获得航道边界。理论分析与实验结果表明,所提方法在最大密度值是200,最小密度值是10,窗口长和宽分别为5和5时,可同时达到86. 7%的准确率和79. 4%的召回率。实验结果表明,该方法可以从大规模的轨迹数据中提取有价值的航道边界,是一种有效的航道提取方法。
The traditional road information extraction method is high-cost and slow-update. Compared with it, road or marine lane information extraction from crowdsourcing trajectory data is low-cost and easier to update. However, it is difficult to extract lane boundary due to vessel trajectory data with high noise, large data volume and uneven distribution across different regions. To solve this problem, an extraction method of marine lane boundary from exploiting trajectory big data was proposed. Firstly, the parallelized denoising, interpolation and trajectory segmentation for trajectory big data was conducted.Then, based on parallelization and Geohash-encoded spatial clustering, trajectory data was simplified into multiple square regions. The regions were divided and the Ni Black method was extended as Spatial Ni Black algorithm to recognize regions on lane. Finally, based on the filtering results, del-alpha-shape algorithm was proposed to construct a Delaunay triangulation network and obtain marine lane boundary. The theoretical analysis and experimental results show that the proposed method can achieve an accuracy of 86. 7% and a recall rate of 79. 4% when the maximum density value is 200, minimum density value is10, length and width of window are 5 and 5 respectively. The experimental results show that the proposed method is effective to extract valuable marine lane boundaries from large-scale trajectory data.
The traditional road information extraction method is high-cost and slow-update. Compared with it, road or marine lane information extraction from crowdsourcing trajectory data is low-cost and easier to update. However, it is difficult to extract lane boundary due to vessel trajectory data with high noise, large data volume and uneven distribution across different regions. To solve this problem, an extraction method of marine lane boundary from exploiting trajectory big data was proposed. Firstly, the parallelized denoising, interpolation and trajectory segmentation for trajectory big data was conducted.Then, based on parallelization and Geohash-encoded spatial clustering, trajectory data was simplified into multiple square regions. The regions were divided and the Ni Black method was extended as Spatial Ni Black algorithm to recognize regions on lane. Finally, based on the filtering results, del-alpha-shape algorithm was proposed to construct a Delaunay triangulation network and obtain marine lane boundary. The theoretical analysis and experimental results show that the proposed method can achieve an accuracy of 86. 7% and a recall rate of 79. 4% when the maximum density value is 200, minimum density value is10, length and width of window are 5 and 5 respectively. The experimental results show that the proposed method is effective to extract valuable marine lane boundaries from large-scale trajectory data.
引文
[1]WANG Y, ZHU Y, HE Z, et al. Challenges and opportunities in exploiting large-scale GPS probe data, HPL-2011-109[R]. Palo Alto, CA:HP Laboratories, 2011.
[2]ZHANG W, GOERLANDT F, KUJALA P, et al. An advanced method for detecting possible near miss ship collisions from AIS data[J]. Ocean Engineering, 2015, 107(1):60-69.
[3]WANG X, LIU X, LIU B, et al. Vessel route anomaly detection with Hadoop MapReduce[C]//Proceedings of the 2015 IEEE International Conference on Big Data. Piscataway, NJ:IEEE, 2015:25-30.
[4]NIBLACK W. An Introduction to Digital Image Processing[M]. Englewood Cliffs, NJ:Prentice-Hall, 1986:115-116.
[5]EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the shape of a set of points in the plane[J]. IEEE Transactions on Information Theory,1983,29(4):551-559.
[6]SUN F, DENG Y, DENG F, et al. Unsupervised maritime traffic pattern extraction from spatio-temporal data[C]//Proceedings of the2015 International Conference on Natural Computation. Piscataway,NJ:IEEE, 2015:1218-1223.
[7]MAZZARELLA F, FERNANDEZ ARGUEDAS V, VESPE M.Knowledge-based vessel position prediction using historical AIS data[C]//Proceedings of the 2015 Sensor Data Fusion:Trends, Solutions, Applications. Piscataway, NJ:IEEE, 2015:1-6.
[8]FERNANDEZ ARGUEDAS V, PALLOTTA G, VESPE M. Maritime traffic networks:from historical positioning data to unsupervised maritime traffic monitoring[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(3):722-732.
[9]PALLOTTA G, VESPE M, BRYAN K. Vessel pattern knowledge discovery from AIS data:a framework for anomaly detection and route prediction[J]. Entropy, 2013, 15(6):2218-2245.
[10]SPILIOPOULOS G, ZISSIS D, CHATZIKOKOLAKIS K. A big data driven approach to extracting global trade patterns[C]//Proceedings of the 2017 International Workshop on Mobility Analytics for Spatio-temporal and Social Data. Berlin:Springer, 2017:109-121.
[11]ETIENNE L, DEVOGELE T, BOUJU A. Spatio-temporal trajectory analysis of mobile objects following the same itinerary[C]//Proceedings of the 2010 International Symposium on Spatial Data Handling. Hong Kong:[s. n.], 2010:86-91.
[12]杨杰,李小平,陈湉.基于增量时空轨迹大数据的群体挖掘方法[J].计算机研究与发展,2014,51(s2):76-85.(YANG J, LI XP, CHEN T. A group mining method for incremental spatio-temporal trajectory big data[J]. Journal of Computer Research and Development, 2014, 51(s2):76-85.)
[13]欧阳鸿,刘建勋,刘毅志,等.基于步行GPS轨迹的路网提取方法[J].计算机与现代化,2014(2):124-128.(OUYANG H, LIU J X, LIU Y Z, et al. An extraction method of road network based on walking GPS trajectories[J]. Computer and Modernization,2014,(2):124-128.)
[14]杨伟,艾廷华.基于车辆轨迹大数据的道路网更新方法研究[J].计算机研究与发展,2016,53(12):2681-2693.(YANG W,AI T H. A method for road network updating based on vehicle trajectory big data[J]. Journal of Computer Research and Development, 2016,53(12):2681-2693.)
[15]杨伟,艾廷华.运用约束Delaunay三角网从众源轨迹线提取道路边界[J].测绘学报,2017,46(2):237-245.(YANG W, AI T H. The extraction of road boundary from crowdsourcing trajectory using constrained Delaunay triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2):237-245.)
[16]李云帆,谭德宝,高广,等.双阈值Alpha Shapes算法提取点云建筑物轮廓研究[J].长江科学院院报,2016,33(11):1-4.(LI Y F, TAN D B, GAO G, et al. Extraction of building contour from point clouds using dual threshold Alpha Shapes algorithm[J]. Journal of Yangtze River Scientific Research Institute, 2016,33(11):1-4.)
[17]朱杰,孙毅中.多约束的平面点集形状重构方法[J].测绘学报,2017,46(2):253-264.(ZHU J, SUN Y Z. An efficient approach to shape reconstruction from planar point set based on multi-constraints[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2):253-264.)
[18]WU L, XU Y, WANG Q, et al. Mapping global shipping density from AIS data[J]. Journal of Navigation, 2017, 70(1):67-81.
[2]ZHANG W, GOERLANDT F, KUJALA P, et al. An advanced method for detecting possible near miss ship collisions from AIS data[J]. Ocean Engineering, 2015, 107(1):60-69.
[3]WANG X, LIU X, LIU B, et al. Vessel route anomaly detection with Hadoop MapReduce[C]//Proceedings of the 2015 IEEE International Conference on Big Data. Piscataway, NJ:IEEE, 2015:25-30.
[4]NIBLACK W. An Introduction to Digital Image Processing[M]. Englewood Cliffs, NJ:Prentice-Hall, 1986:115-116.
[5]EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the shape of a set of points in the plane[J]. IEEE Transactions on Information Theory,1983,29(4):551-559.
[6]SUN F, DENG Y, DENG F, et al. Unsupervised maritime traffic pattern extraction from spatio-temporal data[C]//Proceedings of the2015 International Conference on Natural Computation. Piscataway,NJ:IEEE, 2015:1218-1223.
[7]MAZZARELLA F, FERNANDEZ ARGUEDAS V, VESPE M.Knowledge-based vessel position prediction using historical AIS data[C]//Proceedings of the 2015 Sensor Data Fusion:Trends, Solutions, Applications. Piscataway, NJ:IEEE, 2015:1-6.
[8]FERNANDEZ ARGUEDAS V, PALLOTTA G, VESPE M. Maritime traffic networks:from historical positioning data to unsupervised maritime traffic monitoring[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(3):722-732.
[9]PALLOTTA G, VESPE M, BRYAN K. Vessel pattern knowledge discovery from AIS data:a framework for anomaly detection and route prediction[J]. Entropy, 2013, 15(6):2218-2245.
[10]SPILIOPOULOS G, ZISSIS D, CHATZIKOKOLAKIS K. A big data driven approach to extracting global trade patterns[C]//Proceedings of the 2017 International Workshop on Mobility Analytics for Spatio-temporal and Social Data. Berlin:Springer, 2017:109-121.
[11]ETIENNE L, DEVOGELE T, BOUJU A. Spatio-temporal trajectory analysis of mobile objects following the same itinerary[C]//Proceedings of the 2010 International Symposium on Spatial Data Handling. Hong Kong:[s. n.], 2010:86-91.
[12]杨杰,李小平,陈湉.基于增量时空轨迹大数据的群体挖掘方法[J].计算机研究与发展,2014,51(s2):76-85.(YANG J, LI XP, CHEN T. A group mining method for incremental spatio-temporal trajectory big data[J]. Journal of Computer Research and Development, 2014, 51(s2):76-85.)
[13]欧阳鸿,刘建勋,刘毅志,等.基于步行GPS轨迹的路网提取方法[J].计算机与现代化,2014(2):124-128.(OUYANG H, LIU J X, LIU Y Z, et al. An extraction method of road network based on walking GPS trajectories[J]. Computer and Modernization,2014,(2):124-128.)
[14]杨伟,艾廷华.基于车辆轨迹大数据的道路网更新方法研究[J].计算机研究与发展,2016,53(12):2681-2693.(YANG W,AI T H. A method for road network updating based on vehicle trajectory big data[J]. Journal of Computer Research and Development, 2016,53(12):2681-2693.)
[15]杨伟,艾廷华.运用约束Delaunay三角网从众源轨迹线提取道路边界[J].测绘学报,2017,46(2):237-245.(YANG W, AI T H. The extraction of road boundary from crowdsourcing trajectory using constrained Delaunay triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2):237-245.)
[16]李云帆,谭德宝,高广,等.双阈值Alpha Shapes算法提取点云建筑物轮廓研究[J].长江科学院院报,2016,33(11):1-4.(LI Y F, TAN D B, GAO G, et al. Extraction of building contour from point clouds using dual threshold Alpha Shapes algorithm[J]. Journal of Yangtze River Scientific Research Institute, 2016,33(11):1-4.)
[17]朱杰,孙毅中.多约束的平面点集形状重构方法[J].测绘学报,2017,46(2):253-264.(ZHU J, SUN Y Z. An efficient approach to shape reconstruction from planar point set based on multi-constraints[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2):253-264.)
[18]WU L, XU Y, WANG Q, et al. Mapping global shipping density from AIS data[J]. Journal of Navigation, 2017, 70(1):67-81.