基于移动对象轨迹的室内导航网络构建方法
|
摘要
室内导航网络是行人导航、信息推荐和商业分析的基础。传统人工测绘或半自动提取的室内三维导航网络无法满足复杂室内空间结构高频变化需求。随着室内定位技术的不断发展,室内移动对象轨迹数据爆发式增长,为室内导航网络快速构建与变化监测更新提供了可能。本文提出一种基于移动对象轨迹的室内导航网络构建方法,在基于ST-DBSCAN的轨迹简化预处理基础上,提出了室内轨迹自适应栅格化算法,减弱栅格图像分辨率对导航网络提取的影响,有效避免廊道轨迹密度差异造成的导航网络拓扑连通失效,并通过CFSFDP自适应聚类算法自动识别楼层之间连通点,实现室内导航网络的快速构建。实验数据来源于上海图聚智能科技股份有限公司提供的某商城真实的室内移动对象轨迹数据,实验结果表明,与普适栅格化方法相比,本文提出的方法将导航网络构建准确率平均提高2.43%,拓扑正确度提高12.8%。
The indoor navigation network is the basis for pedestrian navigation, information recommendation,and business analysis. The traditional method of manual mapping or semiautomatic extraction of threedimensional indoor navigation network cannot meet the requirement of high-frequency change of complex indoor space structures. With the continuous development of indoor positioning technology, there is an explosion of trajectory data of indoor moving objects, which provides a possibility for rapid construction and change monitoring of indoor navigation networks. This paper proposes a method of crowdsourcing construction of indoor navigation network based on the trajectory of moving objects. Based on trajectory simplification preprocessing using ST-DBSCAN, an indoor trajectory adaptive rasterization algorithm is proposed to reduce the influence of raster image resolution on the extraction of navigation networks. This approach effectively avoids the failure of navigation networks' topological connection that is caused by the difference of track trajectory density. Moreover, it automatically identifies the connection points between floors by the CFSFDP adaptive clustering algorithm to realize the rapid construction of indoor navigation networks. The experimental data is derived from the real indoor moving object trajectory data provided by Shanghai Palmap Science & Technology Co., Ltd. The experimental results show that, compared with the universal rasterization method, the proposed method improves the accuracy of navigation network construction by an average of 2.43% and improves the accuracy of topology by 12.8%.
The indoor navigation network is the basis for pedestrian navigation, information recommendation,and business analysis. The traditional method of manual mapping or semiautomatic extraction of threedimensional indoor navigation network cannot meet the requirement of high-frequency change of complex indoor space structures. With the continuous development of indoor positioning technology, there is an explosion of trajectory data of indoor moving objects, which provides a possibility for rapid construction and change monitoring of indoor navigation networks. This paper proposes a method of crowdsourcing construction of indoor navigation network based on the trajectory of moving objects. Based on trajectory simplification preprocessing using ST-DBSCAN, an indoor trajectory adaptive rasterization algorithm is proposed to reduce the influence of raster image resolution on the extraction of navigation networks. This approach effectively avoids the failure of navigation networks' topological connection that is caused by the difference of track trajectory density. Moreover, it automatically identifies the connection points between floors by the CFSFDP adaptive clustering algorithm to realize the rapid construction of indoor navigation networks. The experimental data is derived from the real indoor moving object trajectory data provided by Shanghai Palmap Science & Technology Co., Ltd. The experimental results show that, compared with the universal rasterization method, the proposed method improves the accuracy of navigation network construction by an average of 2.43% and improves the accuracy of topology by 12.8%.
引文
[1]Behar J V.The National Human Activity Pattern Survey(NHAPS):A resource for assessing exposure to environmental pollutants[J].Journal of Exposure Analysis and Environmental Epidemiology,2000,11(3):231-252.
[2]方志祥,徐虹,萧世伦,等.绝对空间定位到相对空间感知的行人导航研究趋势[J].武汉大学学报·信息科学版,2018,43(12):2173-2182.[Fang Z X,Xu H,Xiao S L,et al.Pedestrian navigation research trend:From absolute space to relative space-based approach[J].Geomatics and Information Science of Wuhan University,2018,43(12):2173-2182.]
[3]王培晓,王海波,傅梦颖,等.室内用户语义位置预测研究[J].地球信息科学学报,2018,20(12):1689-1698.[Wang P X,Wang H B,Fu M Y,et al.Semantic location prediction of indoor users[J].Journal of Geo-information Science,2018,20(12):1689-1698.]
[4]武恩超,张恒才,吴升.基于中轴变换算法的室内外一体化导航路网自动生成方法[J].地球信息科学学报,2018,20(6)730-737.[Wu E C,Zhang H C,Wu S.Automatic generation method of indoor and outdoor integrated navigation network based on mid-axis transformation algorithm[J].Journal of Geo-information Science,2018,20(6)730-737.]
[5]徐战亚,钟赛尚,王媛湲.一种易于更新的室内导航路网构建方法[J].计算机仿真,2015,32(12):267-271.[Xu ZY,Zhong S S,Wang Y W.An easy-to-update method for building indoor navigation network[J].Computer simulation,2015,32(12):267-271.]
[6]Wang J,Rui X,Song X,et al.A novel approach for generating routable road maps from vehicle GPS traces[J].International Journal of Geographical Information Science,2015,29(1):69-91.
[7]Aronov B,Driemel A,Kreveld M V,et al.Segmentation of trajectories on nonmonotone Criteria[J].Acm Transactions on Algorithms,2015,12(2):1-28.
[8]Li J,Qin Q,Han J,et al.Mining trajectory data and geotagged data in social media for road map inference[J].Transactions in Gis,2015,19(1):1-18.
[9]Tang L,Ren C,Liu Z,et al.A road map refinement method using delaunay triangulation forbig trace data[J].ISPRSInternational Journal of Geo-information,2017,6(2):45.
[10]杨伟,艾廷华.基于车辆轨迹大数据的道路网更新方法研究[J].计算机研究与发展,2016,53(12):2681-2693.[Yang W,Ai T H.Research on road network renewal method based on vehicle trajectory big data[J].Computer Research and Development,2016,53(12):2681-2693.]
[11]Ahmed M,Karagiorgou S,Pfoser D,et al.A comparison and evaluation of map construction algorithms using vehicle tracking data[J].Geoinformatica,2015,19(3):601-632.
[12]Huang J,Deng M,Zhang Y,et al.Complex road intersection modelling baded on low-frequency GPS track data[J].ISPRS-International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences,2017,XLII-2/W7:23-28.
[13]Biagioni J,Eriksson J.Map inference in the face of noise and disparity[C].International Conference on Advances in Geographic Information Systems,2012:79-88.
[14]Jiang Y,Xiang L I,Xiaojie L I,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.
[15]Kuntzsch C,Sester M,Brenner C.Generative models for road network reconstruction[J].International Journal of Geographical Information Science,2016,30(5):1012-1039.
[16]Li Q,Zheng Y,Xie X,et al.Mining user similarity based on location history[C].ACM Sigspatial International Conference on Advances in Geographic Information Systems,2008:1-10.
[17]Birant,Derya,Kut.ST-DBSCAN:An algorithm for clustering spatial-temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.
[18]Davies J J,Beresford A R,Hopper A.Scalable,distributed,real-time map generation[J].IEEE Pervasive Computing,2006,5(4):47-54.
[19]A R,A L.Machine learning.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492.
[20]Jin P,Cui T,Wang Q,et al.Effective Similarity search on indoor moving-object trajectories[C].International Conference on Database Systems for Advanced Applications.Springer International Publishing,2016:181-197.
[21]Zhang L,Thiemann F,Sester M.Integration of GPS traces with road map[C].San Jose:International Workshop on Computational Transportation Science,2010:17-22.
[2]方志祥,徐虹,萧世伦,等.绝对空间定位到相对空间感知的行人导航研究趋势[J].武汉大学学报·信息科学版,2018,43(12):2173-2182.[Fang Z X,Xu H,Xiao S L,et al.Pedestrian navigation research trend:From absolute space to relative space-based approach[J].Geomatics and Information Science of Wuhan University,2018,43(12):2173-2182.]
[3]王培晓,王海波,傅梦颖,等.室内用户语义位置预测研究[J].地球信息科学学报,2018,20(12):1689-1698.[Wang P X,Wang H B,Fu M Y,et al.Semantic location prediction of indoor users[J].Journal of Geo-information Science,2018,20(12):1689-1698.]
[4]武恩超,张恒才,吴升.基于中轴变换算法的室内外一体化导航路网自动生成方法[J].地球信息科学学报,2018,20(6)730-737.[Wu E C,Zhang H C,Wu S.Automatic generation method of indoor and outdoor integrated navigation network based on mid-axis transformation algorithm[J].Journal of Geo-information Science,2018,20(6)730-737.]
[5]徐战亚,钟赛尚,王媛湲.一种易于更新的室内导航路网构建方法[J].计算机仿真,2015,32(12):267-271.[Xu ZY,Zhong S S,Wang Y W.An easy-to-update method for building indoor navigation network[J].Computer simulation,2015,32(12):267-271.]
[6]Wang J,Rui X,Song X,et al.A novel approach for generating routable road maps from vehicle GPS traces[J].International Journal of Geographical Information Science,2015,29(1):69-91.
[7]Aronov B,Driemel A,Kreveld M V,et al.Segmentation of trajectories on nonmonotone Criteria[J].Acm Transactions on Algorithms,2015,12(2):1-28.
[8]Li J,Qin Q,Han J,et al.Mining trajectory data and geotagged data in social media for road map inference[J].Transactions in Gis,2015,19(1):1-18.
[9]Tang L,Ren C,Liu Z,et al.A road map refinement method using delaunay triangulation forbig trace data[J].ISPRSInternational Journal of Geo-information,2017,6(2):45.
[10]杨伟,艾廷华.基于车辆轨迹大数据的道路网更新方法研究[J].计算机研究与发展,2016,53(12):2681-2693.[Yang W,Ai T H.Research on road network renewal method based on vehicle trajectory big data[J].Computer Research and Development,2016,53(12):2681-2693.]
[11]Ahmed M,Karagiorgou S,Pfoser D,et al.A comparison and evaluation of map construction algorithms using vehicle tracking data[J].Geoinformatica,2015,19(3):601-632.
[12]Huang J,Deng M,Zhang Y,et al.Complex road intersection modelling baded on low-frequency GPS track data[J].ISPRS-International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences,2017,XLII-2/W7:23-28.
[13]Biagioni J,Eriksson J.Map inference in the face of noise and disparity[C].International Conference on Advances in Geographic Information Systems,2012:79-88.
[14]Jiang Y,Xiang L I,Xiaojie L I,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.
[15]Kuntzsch C,Sester M,Brenner C.Generative models for road network reconstruction[J].International Journal of Geographical Information Science,2016,30(5):1012-1039.
[16]Li Q,Zheng Y,Xie X,et al.Mining user similarity based on location history[C].ACM Sigspatial International Conference on Advances in Geographic Information Systems,2008:1-10.
[17]Birant,Derya,Kut.ST-DBSCAN:An algorithm for clustering spatial-temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.
[18]Davies J J,Beresford A R,Hopper A.Scalable,distributed,real-time map generation[J].IEEE Pervasive Computing,2006,5(4):47-54.
[19]A R,A L.Machine learning.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492.
[20]Jin P,Cui T,Wang Q,et al.Effective Similarity search on indoor moving-object trajectories[C].International Conference on Database Systems for Advanced Applications.Springer International Publishing,2016:181-197.
[21]Zhang L,Thiemann F,Sester M.Integration of GPS traces with road map[C].San Jose:International Workshop on Computational Transportation Science,2010:17-22.