A Multi-scale Polygonal Object Matching Method Based on MBR Combinatorial Optimization Algorithm

doi:10.11947/j.AGCS.2018.20160625

Abstract

Abstract: Aiming to solving the problem of positional discrepancy of corresponding objects in multi-scale polygonal object matching and that the potential matching pairs can't be directly identified by the method of areal overlapping, it is proposed that a multi-scale polygonal object matching method based on minimum bounding rectangle combinatorial optimization algorithm. The basic idea of our method is that:①identifying the potential matching pairs of 1:1, 1:N and M:N with combinatorial algorithm and simple shape characteristic;②establishing multi-characteristic artificial neural network model to evaluate these potential matching pairs. The proposed method is demonstrated in the experiment of matching between 1:2000 and 1:10000 polygonal objects of residential buildings and industrial facilities in Zhoushan, Zhejiang Province. The experimental results showed that the proposed matching method show superior performance against a method of area overlapping and artificial neural network. Its precision and recall are 96.5% and 89.0% under the positional discrepancy scenario, and it successfully match 1:0, 1:1,1:N and M:N matching pair.

Key words: multi-scale, polygonal object matching, combinatorial algorithm, spatial district, artificial neural network

CLC Number:

P208

LIU Lingjia, ZHU Daoye, ZHU Xinyan, DING Xiaohui, GUO Wei. A Multi-scale Polygonal Object Matching Method Based on MBR Combinatorial Optimization Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(5): 652-662.

References

[1] LI Linna, GOODCHILD M F. Automatically and Accurately Matching Objects in Geospatial Datasets[M]//GOODCHILD M F, LEUNG Y, SHI Wenzhong, et al. Advances in Geo-Spatial Information Science. London, UK:CRC Press, 2012:71-79.
[2] SAALFELD A. Automated Map Conflation[D]. Washington DC:University of Maryland, 1993:1-10.
[3] RUIZ J J, ARIZA F J, UREÑA M A, et al. Digital Map Conflation:A Review of the Process and a Proposal for Classification[J]. International Journal of Geographical Information Science, 2011, 25(9):1439-1466.
[4] GIRRES J F, TOUYA G. Quality Assessment of the French OpenStreetMap Dataset[J]. Transactions in GIS, 2010, 14(4):435-459.
[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] DEVOGELE T, PARENT C, SPACCAPIETRA S. On Spatial Database Integration[J]. International Journal of Geographical Information Science, 1998, 12(4):335-352.
[7] WALTER V, FRITSCH D. Matching Spatial Data Sets:A Statistical Approach[J]. International Journal of Geographical Information Science, 1999, 13(5):445-473.
[8] GOODCHILD M F. Chapter Four-attribute Accuracy[M]//GUPTILL S C, MORRISON J L. Elements of Spatial Data Quality:A Volume in International Cartographic Association. Amsterdam:Elsevier, 1995:59-79.
[9] GUPTILL S C, MORRISON J L. Elements of Spatial Data Quality[M]. Oxford, UK:Elsevier Science, 1995.
[10] ZHANG Xiang, AI Tinghua, STOTER J, et al. Data Matching of Building Polygons at Multiple Map Scales Improved by Contextual Information and Relaxation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 92(2):147-163.
[11] DEVOGELE T, TREVISAN J, RAYNAL L. Building a Multi-scale Database with Scale-transition Relationships[C]//Proceedings of the 7th International Symposium on Spatial Data Handling. Delft, The Netherlands:SDH, 337-351.
[12] SAMAL A, SETH S, CUETO K, et al. A Feature-based Approach to Conflation of Geospatial Sources[J]. International Journal of Geographical Information Science, 2004, 18(5):459-489.
[13] KIM J O, YU K, HEO J, et al. A New Method for Matching Objects in Two Different Geospatial Datasets Based on the Geographic Context[J]. Computers & Geosciences, 2010, 36(9):1115-1122.
[14] XAVIER E M A, ARIZA-LÓPEZ F J, UREÑA-CÁMARA M A. A Survey of Measures and Methods for Matching Geospatial Vector Datasets[J]. ACM Computing Surveys, 2016, 49(2):39.
[15] ZHANG X, ZHAO X, MOLENAAR M, et al. Pattern Classification Approaches to Matching Building Polygons at Multiple Scales[C]//ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Melbourne:ISPRS, 2012:19-24.
[16] 郭泰圣, 张新长, 梁志宇. 神经网络决策树的矢量数据变化信息快速识别方法[J]. 测绘学报, 2013, 42(6):937-944. GUO Taisheng, ZHANG Xinchang, LIANG Zhiyu. Research on Change Information Recognition Method of Vector Data Based on Neural Network Decision Tree[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(6):937-944.
[17] 付仲良, 杨元维, 高贤君, 等. 道路网多特征匹配优化算法[J]. 测绘学报, 2016, 45(5):608-615. DOI:10.11947/j.agcs.2016.20150388. FU Zhongliang, YANG Yuanwei, GAO Xianjun, et al. An Optimization Algorithm for Multi-characteristics Road Network Matching[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(5):608-615. DOI:10.11947/j.agcs.2016.20150388.
[18] WANG Yanxia, CHEN Deng, ZHAO Zhiyuan, et al. A Back-propagation Neural Network-based Approach for Multi-represented Feature Matching in Update Propagation[J]. Transactions in GIS, 2015, 19(6):964-993.
[19] FU Zhongliang, WU Jianhua. Entity Matching in Vector Spatial Data[C]//International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Beijing:ISPRS, 2008, 37(5):1467-1472.
[20] VON GOESSELN G, SESTER M. Change Detection and Integration of Topographic Updates from ATKIS to Geoscientific Data Sets[C]//Proceedings of International Conference on Next Generation Geospatial Information. Boston:International Conference on Next Generation Geospatial Information, 2003.
[21] HUH Y, KIM J, LEE J, et al. Identification of Multi-scale Corresponding Object-set Pairs between Two Polygon Datasets with Hierarchical Co-clustering[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 88(1):60-68.
[22] ARKIN E M, CHEW L P, HUTTENLOCHER D P, et al. An efficiently Computable Metric for Comparing Polygonal Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3):209-216.
[23] XU Yongyang, XIE Zhong, CHEN Zhanlong, et al. Shape Similarity Measurement Model for Holed Polygons Based on Position Graphs and Fourier Descriptors[J]. International Journal of Geographical Information Science, 2017, 31(2):253-279.
[24] 许俊奎, 武芳, 朱健东, 等. 相邻比例尺居民地匹配[J]. 武汉大学学报(信息科学版), 2014, 39(3):340-345. XU Junkui, WU Fang, ZHU Jiandong, et al. A Multi-to-Multi Matching Algorithm between Neighborhood Scale Settlement Data[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3):340-345.
[25] ZHANG Meng, MENG Liqiu. An Iterative Road-matching Approach for the Integration of Postal Data[J]. Computers, Environment and Urban Systems, 2007, 31(5):597-615.
[26] COBB M A, PETRY F E, SHAW K B. Fuzzy Spatial Relationship Refinements based on Minimum Bounding Rectangle Variations[J]. Fuzzy Sets and Systems, 2000, 113(1):111-120.
[27] KNUTH D E. The Art of Computer Programming[M]. Upper Saddle River, NJ:Addison-Wesley, 1968.
[28] LI Z, YAN H, AI T, et al. Automated Building Generalization Based on Urban Morphology and Gestalt Theory[J]. International Journal of Geographical Information Science, 2004, 18(5):513-534.
[29] TSAI V J D. Delaunay Triangulations in TIN Creation:An Overview and a Linear-time Algorithm[J]. International Journal of Geographical Information Systems, 1993, 7(6):501-524.
[30] CRACKNELL M J, READING A M. Geological Mapping Using Remote Sensing Data:A Comparison of Five Machine Learning Algorithms, Their Response to Variations in the Spatial Distribution of Training Data and the Use of Explicit Spatial Information[J]. Computers & Geosciences, 2014, 63(1):22-33.
[31] FUNAHASHI K I. On the Approximate Realization of Continuous Mappings by Neural Networks[J]. Neural Networks, 1989, 2(3):183-192.
[32] 汪汇兵, 唐新明, 邱博, 等. 运用多算子加权的面要素几何匹配方法[J]. 武汉大学学报(信息科学版), 2013, 38(10):1243-1247. WANG Huibing, TANG Xinming, QIU Bo, et al. Geometric Matching Method of Area Feature Based on Multi-weighted Operators[J]. Geomatics and Information Science of Wuhan University, 2013, 38(10):1243-1247.
[33] FAN Hongchao, ZIPF A, FU Qing, et al. Quality Assessment for Building Footprints Data on OpenStreetMap[J]. International Journal of Geographical Information Science, 2014, 28(4):700-719.
[34] DOYTSHER Y. A Rubber Sheeting Algorithm for Non-Rectangular Maps[J]. Computers & Geosciences, 2000, 26(9-10):1001-1010.