基于MBR组合优化算法的多尺度面实体匹配方法
|
摘要
针对多尺度匹配中同名实体位置偏差较大,无法直接通过面积重叠法获得候选匹配的问题,本文提出了一种基于最小外包矩形(MBR)组合优化算法的多尺度面实体匹配方法。本文方法的基本思想是通过MBR组合优化和简要的形状特征来筛选1∶1、1∶N和M∶N候选匹配,然后构建多因子人工神经网络模型来评估候选匹配。试验选取浙江省舟山市1∶2000岛礁基础数据和1∶10 000陆地基础数据中的居民地与设施面进行匹配算法的验证。结果表明,本文方法相对于基于面积重叠-神经网络的匹配方法表现出显著的优势,对存在位置偏移的匹配数据准确率和召回率分别达到了达到96.5%,达到89.0%,且能够识别所有匹配类型。
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:(1)identifying the potential matching pairs of 1∶1,1∶N and M ∶N with combinatorial algorithm and simple shape characteristic;(2)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∶Nand M∶N matching pair.
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:(1)identifying the potential matching pairs of 1∶1,1∶N and M ∶N with combinatorial algorithm and simple shape characteristic;(2)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∶Nand M∶N matching pair.
引文
[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,UREA 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-LPEZ F J,UREA-CMARA 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 Multiscale 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-toMulti 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 Multiweighted 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 NonRectangular Maps[J].Computers&Geosciences,2000,26(9-10):1001-1010.
[2]SAALFELD A.Automated Map Conflation[D].Washington DC:University of Maryland,1993:1-10.
[3]RUIZ J J,ARIZA F J,UREA 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-LPEZ F J,UREA-CMARA 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 Multiscale 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-toMulti 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 Multiweighted 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 NonRectangular Maps[J].Computers&Geosciences,2000,26(9-10):1001-1010.