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

doi:10.11947/j.AGCS.2018.20160625

测绘学报 ›› 2018, Vol. 47 ›› Issue (5): 652-662.doi: 10.11947/j.AGCS.2018.20160625

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

刘凌佳¹, 朱道也¹, 朱欣焰^1,2,3, 丁小辉⁴, 呙维^1,2

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

收稿日期:2016-12-07 修回日期:2017-11-09 出版日期:2018-05-20 发布日期:2018-06-01
通讯作者: 朱欣焰 E-mail:xinyanzhu@whu.edu.cn
作者简介:刘凌佳(1990-),男,博士生,研究方向为空间数据融合与地图更新。E-mail:liulingjia_office@163.com
基金资助:
国家重点研发计划（2016YFB0502204）；测绘遥感信息工程国家重点实验室专项科研项目；测绘遥感信息工程国家重点实验室重点开放基金；航天科技联合基金

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

LIU Lingjia¹, ZHU Daoye¹, ZHU Xinyan^1,2,3, DING Xiaohui⁴, GUO Wei^1,2

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:2016-12-07 Revised:2017-11-09 Online:2018-05-20 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

摘要/Abstract

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

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

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

中图分类号:

P208

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

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.

参考文献

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

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张新长, 何显锦, 孙颖, 黄健锋, 张志强. 多尺度空间数据联动更新技术研究现状及展望[J]. 测绘学报, 2022, 51(7): 1520-1535.
[2]	艾廷华, 张翔. 地理信息科学中尺度概念的诠释与表达[J]. 测绘学报, 2022, 51(7): 1640-1652.
[3]	梁哲恒, 黎宵, 邓鹏, 盛森, 姜福泉. 融合多尺度特征注意力的遥感影像变化检测方法[J]. 测绘学报, 2022, 51(5): 668-676.
[4]	孙伟伟, 常明会, 孟祥超, 杨刚, 任凯. 空谱协同多尺度顶点成分分析的高光谱影像端元提取[J]. 测绘学报, 2022, 51(4): 587-598.
[5]	杜佳威, 武芳, 朱丽, 刘呈熠, 王安东. 图形、图像融合利用的集成学习智能化简方法及其在岛屿岸线化简中的应用[J]. 测绘学报, 2022, 51(3): 373-387.
[6]	洪亮, 冯亚飞, 彭双云, 楚森森. 面向对象的多尺度加权联合稀疏表示的高空间分辨率遥感影像分类[J]. 测绘学报, 2022, 51(2): 224-237.
[7]	邓敏, 谌恺祺, 石岩, 陈袁芳, 郭艺文. 多尺度空间同位模式挖掘的点过程分解方法[J]. 测绘学报, 2022, 51(2): 258-268.
[8]	高晓蓉, 闫浩文, 禄小敏. 多尺度地图空间居民地语义相似度计算方法[J]. 测绘学报, 2022, 51(1): 95-103.
[9]	张玉鑫, 颜青松, 邓非. 高分辨率遥感影像建筑物提取多路径RSU网络法[J]. 测绘学报, 2022, 51(1): 135-144.
[10]	叶健, 胡鑫, 徐鸿蒙, 陈曦, 吕琦. 多尺度GTWR城市住宅价格建模与分析[J]. 测绘学报, 2021, 50(9): 1266-1274.
[11]	李静, 刘海砚, 郭文月, 陈欣. 基于深度学习的人群活动流量时空预测模型[J]. 测绘学报, 2021, 50(4): 522-531.
[12]	续东, 柳景斌, 花向红, 陶武勇. 道路空间特征与测量距离相结合的LiDAR道路边界点提取算法[J]. 测绘学报, 2021, 50(11): 1534-1545.
[13]	刘鹏程, 肖天元, 肖佳, 艾廷华. 曲线多尺度表达的Head-Tail信息量分割法[J]. 测绘学报, 2020, 49(7): 921-933.
[14]	赵传, 郭海涛, 卢俊, 余东行, 张保明. 基于深度残差网络的机载LiDAR点云分类[J]. 测绘学报, 2020, 49(2): 202-213.
[15]	赵泉华, 谢凯浪, 王光辉, 李玉. 全卷积网络和条件随机场相结合的全极化SAR土地覆盖分类[J]. 测绘学报, 2020, 49(1): 65-78.