An Optimization Algorithm for Multi-characteristics Road Network Matching

doi:10.11947/j.AGCS.2016.20150388

Abstract

Abstract: Identifying homonymous road objects is a crucial prerequisite to the integration, updating and fusion of road data. Road networks matching is of great theoretical research value and practical significance in aspect of intelligent transportation system and location-based Service. This paper proposed an optimization algorithm for multi-characteristics road network matching. Designed from shape, distance and semantics aspects, three similarity characteristics-shape differences based on area accumulated, mixed median Hausdorff distance and distance with global weighted attributes, described candidate corresponding pairs more accurately. Then, the matching regression model could be then constructed by training the similarity samples set through SVM algorithm. Finally, the constructed model can be used to predict whether the road matching pairs were matched. A great number of experiments show that the algorithm achieves a robust matching precision and recall even for road networks data with apparent non-rigid deviation. And the proposed method can be effectively applied for road networks matching with multiple matching relationship.

Key words: road networks matching, SVM, median Hausdorff distance, regression model

CLC Number:

P208

FU Zhongliang, YANG Yuanwei, GAO Xianjun, ZHAO Xingyuan, FAN Liang. An Optimization Algorithm for Multi-characteristics Road Network Matching[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(5): 608-615.

References

[1] 安晓亚,孙群,肖强,等.一种形状多级描述方法及在多尺度空间数据几何相似性度量中的应用[J]. 测绘学报, 2011, 40(4): 495-501, 508. AN Xiaoya, SUN Qun, XIAO Qiang, et al. A Shape Multilevel Description Method and Application in Measuring Geometry Similarity of Multi-scale Spatial Data[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 495-501, 508.
[2] SAALFELD A. Conflation Automated Map Compilation[J]. International Journal of Geographical Information Systems, 1988, 2(3): 217-228.
[3] LI Linna, GOODCHILD M F. An Optimisation Model for Linear Feature Matching in Geographical Data Conflation[J]. International Journal of Image and Data Fusion, 2011, 2(4): 309-328.
[4] DENG Min, LI Zhilin, CHEN Xiaoyong. Extended Hausdorff Distance for Spatial Objects in GIS[J]. International Journal of Geographical Information Science, 2007, 21(4): 459-475.
[5] YANG Bisheng, ZHANG Yunfei, LUAN Xuechen. A Probabilistic Relaxation Approach for Matching Road Networks[J]. International Journal of Geographical Information Science, 2013, 27(2): 319-338.
[6] SAFRA E, KANZA Y, SAGIV Y, et al. Ad Hoc Matching of Vectorial Road Networks[J]. International Journal of Geographical Information Science, 2013, 27(1): 114-153.
[7] 安晓亚, 孙群, 尉伯虎. 利用相似性度量的不同比例尺地图数据网状要素匹配算法[J]. 武汉大学学报(信息科学版), 2012, 37(2): 224-228, 241. AN Xiaoya, SUN Qun, YU Bohu. Feature Matching from Network Data at Different Scales Based on Similarity Measure[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2): 224-228, 241.
[8] RODRÍGUEZ M A, EGENHOFER M J. Comparing Geospatial Entity Classes: An Asymmetric and Context-Dependent Similarity Measure[J]. International Journal of Geographical Information Science, 2004, 18(3): 229-256.
[9] MUSTIÈRE S, DEVOGELE T. Matching Networks with Different Levels of Detail[J]. GeoInformatica, 2008, 12(4): 435-453.
[10] 罗国玮, 张新长, 齐立新, 等. 矢量数据变化对象的快速定位与最优组合匹配方法[J]. 测绘学报, 2014, 43(12): 1285-1292. DOI: 10.13485/j.cnki.11-2089.2014.0191. LUO Guowei, ZHANG Xingchang, QI Lixin, et al. The Fast Positioning and Optimal Combination Matching Method of Change Vector Object[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12): 1285-1292. DOI: 10.13485/j.cnki.11-2089.2014.0191.
[11] 栾学晨, 杨必胜, 李秋萍. 基于结构模式的道路网节点匹配方法[J]. 测绘学报, 2013, 42(4): 608-614. LUAN Xuechen, YANG Bisheng, LI Qiuping. Pattern-based Node Matching Approach for Road Networks[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4): 608-614.
[12] WALTER V, FRITSCH D. Matching Spatial Data Sets: A Statistical Approach[J]. International Journal of Geographical Information Science, 1999, 13(5): 445-473.
[13] 巩现勇, 武芳, 姬存伟, 等. 道路网匹配的蚁群算法求解模型[J]. 武汉大学学报(信息科学版), 2014, 39(2): 191-195. GONG Xianyong,WU Fang,JI Cunwei,et al.Ant Colony Optimization Approach to Road Network Matching[J]. Geomatics and Information Science of Wuhan University, 2014, 39(2): 191-195.
[14] 张云菲, 杨必胜, 栾学晨. 利用概率松弛法的城市路网自动匹配[J]. 测绘学报, 2012, 41(6): 933-939. ZHANG Yunfei, YANG Bisheng, LUAN Xuechen. Automated Matching Urban Road Networks Using Probabilistic Relaxation[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 933-939.
[15] 赵东保, 盛业华. 全局寻优的矢量道路网自动匹配方法研究[J]. 测绘学报, 2010, 39(4): 416-421. ZHAO Dongbao, SHENG Yehua. Research on Automatic Matching of Vector Road Networks Based on Global Optimization[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 416-421.
[16] TONG Xiaohua, LIANG Dan, JIN Yanmin. A Linear Road Object Matching Method for Conflation Based on Optimization and Logistic Regression[J]. International Journal of Geographical Information Science, 2014, 28(4): 824-846.
[17] YUAN Shuxin, TAO Chuang. Development of Conflation Components[C]//Proceedings of Geoinformatics'99 Conference. Ann Arbor:[s.n.], 1999: 1-13.
[18] VOLZ S. An Iterative Approach for Matching Multiple Representations of Street Data[C]//Proceedings of the ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data. Hanover: ISPRS, 2006: 101-110.
[19] NAVARRO G. A Guided Tour to Approximate String Matching[J]. ACM Computing Surveys, 2001, 33(1): 31-88.
[20] 刁兴春, 谭明超, 曹建军. 一种融合多种编辑距离的字符串相似度计算方法[J]. 计算机应用研究, 2010, 27(12): 4523-4525. DIAO Xingchun, TAN Mingchao, CAO Jianjun. New Method of Character String Similarity Compute Based on Fusing Multiple Edit Distances[J]. Application Research of Computers, 2010, 27(12): 4523-4525.