基于MBR组合优化算法的多尺度面实体匹配方法

刘凌佳; 朱道也; 朱欣焰; 丁小辉; 呙维

doi:10.11947/j.AGCS.2018.20160625

测绘学报 >

2018 , Vol. 47 >Issue 5: 652 - 662

DOI: https://doi.org/10.11947/j.AGCS.2018.20160625

地图学与地理信息

基于MBR组合优化算法的多尺度面实体匹配方法

刘凌佳 ,
朱道也 ,
朱欣焰 ,
丁小辉 ,
呙维

展开

1. 武汉大学测绘遥感信息工程国家重点实验室, 湖北武汉 430079;
2. 武汉大学地球空间信息技术协同创新中心, 湖北武汉 430079;
3. 武汉大学空天信息安全与可信计算教育部重点实验室, 湖北武汉 430072;
4. 中国科学院东北地理与农业生态研究所, 吉林长春 130102

刘凌佳(1990-),男,博士生,研究方向为空间数据融合与地图更新。E-mail:liulingjia_office@163.com

收稿日期: 2016-12-07

修回日期: 2017-11-09

网络出版日期: 2018-06-01

基金资助

国家重点研发计划（2016YFB0502204）；测绘遥感信息工程国家重点实验室专项科研项目；测绘遥感信息工程国家重点实验室重点开放基金；航天科技联合基金

收起

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

LIU Lingjia ,
ZHU Daoye ,
ZHU Xinyan ,
DING Xiaohui ,
GUO Wei

Expand

1. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China;
2. Collaborative Innovation Center of Geospatial Technology, Wuhan University, Wuhan 430079, China;
3. Key Laboratory of Aerospace Information Security and Trusted Computing of Ministry of Education, Wuhan University, Wuhan 430072, China;
4. Northeast Institute of Geography and Agroecology, Chinese Academy of Sciences, Changchun 130102, China

Received date: 2016-12-07

Revised date: 2017-11-09

Online published: 2018-06-01

Supported by

The National Key Research and Development Program of China (No.2016YFB0502204);The LIESMARS Special Research Funding;The Open Fund of State Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing (2016Key Project);The Aerospace Science and Technology Innovation Foundation of China

Fold

摘要

针对多尺度匹配中同名实体位置偏差较大，无法直接通过面积重叠法获得候选匹配的问题，本文提出了一种基于最小外包矩形（MBR）组合优化算法的多尺度面实体匹配方法。本文方法的基本思想是通过MBR组合优化和简要的形状特征来筛选1∶1、1∶N和M∶N候选匹配，然后构建多因子人工神经网络模型来评估候选匹配。试验选取浙江省舟山市1∶2000岛礁基础数据和1∶10 000陆地基础数据中的居民地与设施面进行匹配算法的验证。结果表明，本文方法相对于基于面积重叠-神经网络的匹配方法表现出显著的优势，对存在位置偏移的匹配数据准确率和召回率分别达到了达到96.5%，达到89.0%，且能够识别所有匹配类型。

关键词： 多尺度; 面匹配; 组合算法; 空间域; 人工神经网络

本文引用格式

刘凌佳 , 朱道也 , 朱欣焰 , 丁小辉 , 呙维 . 基于MBR组合优化算法的多尺度面实体匹配方法[J]. 测绘学报, 2018 , 47(5) : 652 -662 . DOI: 10.11947/j.AGCS.2018.20160625

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

参考文献

[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.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献