第４０卷第４期２０１５年４月
测绘科学
ＳｃｉｅｎｃｅｏｆＳｕｒｖｅｉｎａｎｄＭａｉｎ ｙｇｐｐｇ
Ｖｏｌ．４０Ｎｏ．４
Ａｒ
．ｐ
利用泰森多边形的点实体匹配算法
吴建华，万洋洋
（）江西师范大学地理与环境学院／鄱阳湖湿地与流域研究教育部重点实验室，南昌 ３３００２２
摘 要：针对众源地理数据中的同名点实体之间存在距离、方向等非一致性偏差，导致匹配困难的问题，该文提出了基于泰森多边形的点实体匹配算法。利用相匹配的点实体数据集其对应的泰森多边形具有较高的对应关系这一特点，将不确定的点与点之间的匹配转化为匹配度更高的对应泰森多边形的匹配。首先统计出被彼此泰森多边形包含的点对，根据点对的距离概率分布，计算出距离阈值作为确认同名实体的条件之一；然后将泰森多边形的位置及形状相似性作为匹配条件二；最后将相似度最高的实体确认为同名实体。通过实验与现有的几种点实体匹配算法进行了比较，结果表明，该算法具有较高的查全率和查准率，且普适性强。关键词：形状相似度；实体匹配；数据融合；泰森多边形；众源地理数据
【（）中图分类号】Ｐ文献标识码】Ａ 【文章编号】１２０８ 【００９２３０７２０１５０４００９７０５－－－：１／ＤＯＩ０．１６２５１２３０７．２０１５．０４．０２２．ｃｎｋｉ．１００９－ｊ
１ 引言
实体匹配是指通过相似性指标识别出不同来源地图数据中同名实体并建立实体对应关系的过
］１３－
，它是地图数据融合与更新中的一个关键环程［
点实体局部环境的整体相似性，在一定程度上解决了非一致性偏差问题，但点实体密度对各种因素比较敏感，会降低该方法的普适性。随着志愿者地理信息的兴起，许多公司或普通民众都可以上传、分享或标注地图，这些非测绘或ＧＩＳ专业
人士上传的地图含有丰富的属性或拓扑信息，但其精度并不一定高。而小比例尺地图更多地是注重地理形态与结构的表示，地图的几何精确性通常让位于地理适应性。将这些不同来源的同一专题的数据进行叠加必然会存在数据的非一致性偏差。为了提高点实体的匹配精度及可靠性，本文以相近比例尺的城市兴趣点数据匹配为例，设计并实现了基于泰森多边形的点实体匹配方法。
节。点实体匹配是指识别出两个数据集中反映现实世界同一地物的独立点实体（比如：酒店、医院、超市、公交站点等）的过程。点实体的匹配结果可以用于属性信息的转换、实体替换更新、建立两幅地图之间局部坐标转换关系等。针对点实体的匹配，学者们已经提出了一些方法，比如位
］４５６］－
、相互位置最近的方法［、基于置最近的方法［
］７８９］－
、基于属性相似的方法［，但是这概率的方法［
些方法只是片面地强调位置或属性，而实际上位置最近或属性相似的两个点实体并非是同名实体，即不适用于较多同名实体存在非一致性偏差的数
１０］
，考虑了据集。虽然基于环境特征相似的方法［
２ 基于泰森多边形的匹配算法原理
２．１ 泰森多边形在点匹配中的应用分析
表达同一地区相同专题的两个点集中，其点实体之间的关系及整体布局结构应相同或相似。泰森多边形是按欧氏距离最近这一原则将平面上分类，所有点（ｐｐｐ１，２，…，ｎ是其中的一部分）分别得到距离每个ｐ最近的点集：１≤ｉｎ）≤ｉ（，ｐＶＲ（＝｛ｉｐｑ｜ｑｐｑｐｊ≠ｉ）ｉ｜≤｜ｉ，ｊ｜，
，其中，｜Ｐ｝ｐｑｐ｜表示两点之间的欧氏距离，ｊ∈
为站点Ｐ＝｛ＶＲ（ｐｐｐｐ１，２，…，ｎ｝的集合，ｉ）
ｐｉ的泰森多边形。形态结构形似的点集，点实体对应的泰森多边形有较好的一对一关系，从而可以将不可靠的点与点匹配转化为可靠性强的面与面的匹配。匹配时存在以下几种情况：①若两个点实体数
，男，江西作者简介：吴建华（１９８１）鄱阳人，副教授，博士，主要从事地理空间数据匹配与融合，地理信息工程等方面的研究。：ｗＥ－ｍａｉｌｈｉｓ２６．ｃｏｍ＠１ｊｇ收稿日期：２０１４０７２９－－
基金项目：国家自然科学基金项目
（）；江西省教育厅青年科学基金项目４１２０１４０９，４１２６１０８６
（）；鄱阳湖湿地与流域研究教育部重点实验室主任ＧＪＪ１２２０）开放基金项目（ＺＫ２０１３００８
９８测绘科学第４０卷
据集完全匹配，则同名实体所对应的泰森多边形的面积及形状具有极高的相似性；②当两个点实体数据集不完全匹配时（即存在新增、修改、删除数据的，若两同名实体及其周边环境相似时，则两个情况）
同名实体的泰森多边形形状形似，若同名实体邻近数据部分发生变化，则两个同名实体的泰森多边形局部边界存在局部相似性；③当某个实体为新增或待删除对象时，在其泰森多边形内，要么不包含目超标匹配数据集中的点实体，要么包含离其比较远（过某一距离阈值）的目标实体。
２．２ 算法流程
设Ａ＝｛ａａａ１，２，…，ｎ｝为源点实体数据集（，Ｂ＝｛ａｂｂｂｎ为Ａ中的点要素）１，２，…，ｎ｝为。基于泰目标点实体数据集（ｂｎ为Ｂ中的点要素）森多边形的点实体匹配算法的步骤如下：
）分别为Ａ、Ｂ建立泰森多边形图层Ｐ＝１｛ｐｐｐ１，２，…，ｐｎ｝（ｎ为Ｐ中的泰森多边形要
、Ｑ＝｛素）ｑｑｑｑ１，２，…，ｎ｝（ｎ为Ｑ中的泰森多。边形要素）
）建立匹配条件。遍历Ｐ中的每个要素ｐ２ｐｉ（ｉ
，找出仅包含１个Ｂ中要为ａｉ对应的泰森多边形）素（设为ｂ的所有多边形。计算这些多边形中ａｉｊ）与ｂｊ的距离值，借鉴拉依达准则对其改进，将小
及大于μ＋于μ－δ（δ为距离标准差）μ为平均距离，
δ的值作为异常值剔除，计算出剩余点对的距离均值μ和距离标准差δ，将匹配点对距离小于等于μ＋３δ作为选择候选集的条件之一。
）进行匹配计算。查看包含在ｐ３ｉ中的Ｂ中的要素数目，①若包含在ｐｉ中的Ｂ中的要素数目为０，则看ｐｉ是否存在与其相交且Ｑ中的泰森多边形（ｐｉ与ｑｉ与ｑｊ要满足一定的相似度，即要求ｐｊ的，若不存在相交面积与ｐ０％）ｉ的面积之比大于２符合条件的ｑｉ无匹配对象，若仅存１ｊ，则表示ｐ个与ｐｉ相交的泰森多边形，则计算两个面中对应点之间的距离是否符合条件一，若符合则将对应的点视为匹配对象，若存在多个与ｐｉ相交的泰森多边形，先剔除不符合条件一的匹配对象，然后比较符合条件一的对应泰森多边形的形状相似性，））将相似度（计算方法见公式（最高的ｑ１ｊ视为匹配对象，并建立对应点的匹配关系；②若包含在ｐｉ中的Ｂ中的要素数目为１，则检查其是否满足条件一，若满足则建立对应点的匹配关系，否则记录对应的ｂｉ中的Ｂ中的ｊ为新增要素；③若包含在ｐ要素数目大于等于２，先剔除不符合条件一的匹配对象，然后比较符合条件一的对应泰森多边形的
）形状相似性，将相似度（计算方法见公式（最高１）的ｑｊ视为匹配对象，并建立对应点的匹配关系。２．３ 泰森多边形相似度计算方法
考虑到大部分同名点实体其对应的泰森多边形有较高的重叠度，而在点实体数据集的一些弱覆盖区域其对应的泰森多边形重叠度偏低，为了得到较好的匹配质量，设计了以下综合相似度计）。算模型，见公式（１
，ａｂａｂＡｒｅａ（ｉ，Ａｒｅａ（ｉ，≥Ｔｊ）ｊ）ρρ
，＝ａｂρｉｊ
，ａｂａｂＳｈａｅ（ｉ，Ａｒｅａ（ｉ，＜Ｔｐｊ）ｊ）ρρ（ｉ）（，）ａｂ＝Ａｒｅａｉｊρ［（，（］ｍｉｎｓａｓｂｉ）ｊ）
｛
（）１（）２
其中，表示面积相似度，从一定程度ａｂＡｒｅａ（ｉ，ｊ）ρ
１１］
，计算上可以反映多边形位置与形状的相似性［
；Ｔ为面积相似度阈值，当两泰森方法见公式（２）多边形面积重叠度较高时，建议采用面积相似度作为评判对应泰森多边形的依据，反之使用形状相似度作为评判对应泰森多边形的依据，根据实验数据观察分析，本文Ｔ取０表．５；ａｂｓｈａｅ（ｉ，ｊ）ｐρ示对应泰森多边形的轮廓形状相似度，其计算方
１２］
，将其改进后法借鉴基于折线段方位编码方法［
应用到多边形轮廓形状的匹配，即将多边形的轮廓形状通过各边的方位编码来描述。其设计思路如下：首先，将直角坐标系中围绕坐标原点构成的圆周按照一定的角度间隔进行角度分区，并对每个角度分区进行编码；如图１中的间隔角度为（经过前期实验，该角度间隔可区分泰森多边形１５°
，整个圆周被分为２边方向）４个区，可分别用Ａ～Ｘ字符来编码。当边的方位角恰好位于圆周分割线
，需要将计算出的编上时（除Ｘ坐标轴的正方向）码降为它的下一级，比如将编码Ｄ变为编码Ｃ。为了便于待匹配多边形之间各边方位的比较，计算方位编码前需将两个待匹配的多边形上的节点统一按顺时针（或逆时针）进行排列。每边的方位编
图１ 圆周角度分区Ｆｉ．１ ＡｎｌｅＺｏｎｅｓｏｆＣｉｒｃｌｅ ｇｇ
］引用格式：吴建华，万洋洋．利用泰森多边形的点实体匹配算法［Ｊ．测绘科学，２０１５，４０
第４期
（）：９４７１００．－
９９
ｃｏｄｅ＝Ｃｈｒ６５＋Ｉｎｔ
（
ａｚｉｍｕｔｈｌｌ１）＋
１５
（…，ｉ＝１，２，ｎ）
］）
（）３
其中，Ｃ的函ｈｒ为将数值转换为编码字符（Ａ～Ｘ）数，Ｎｉ、Ｎｉ＋１为折线上相邻的两个结点，ａｚｉｍｕｔｈ
（］为返表示向量ＮｉＮｉＮｉ＋１）Ｎｉ＋１的方位角，ｉｎｔ［回整数部分的函数。在对多边形各边计算方位编码后，可得到由多边形各边方位编码组成的形状。图２为两个描述字符串Ｓｉ∈１，２，３，…，ｎ）ｉ（
对应的泰森多边形的形状编码计算示例
。
图３ 源数据与目标数据叠加效果Ｆｉ．３ ＳｕｅｒｏｓｉｔｉｏｎＥｆｆｅｃｔｏｆＳｏｕｒｃｅ ｇｐｐ
ＤａｔａａｎｄＴａｒｅｔＤａｔ
ａ ｇ
图２ 泰森多边形的形状编码Ｆｉ．２ ＳｈａｅＣｏｄｉｎｏｆＴｈｉｅｓｓｅｎＰｏｌｏｎ ｇｐｇｙｇ
设两个待匹配的泰森多边形的形状描述字符）表示形状描述字符串串分别为ＳｓＮｕｍ（ｉ和Ｓｊ，
中的字符个数，遍历Ｓｉ中的每个字符看其在Ｓｊ中能否找到相同字符，若找到则将配对的字符放入集合Ｅ表示集合中的字符总ｕｍＥｃ中，设Ｎｓａｍｅ（ｃ）进行数目，则多边形的形状相似度可用公式（４）计算。
ＮｕｍｓＥａｍｅ（ｃ））（ａｂ４＝Ｓｈａｅ（ｉ，ｐｊ）ρｓＮｕｍＳＮｕｍｓ＋ｓｉｊ）公式（表明若ρ４ａｂ≥Ｔ则相似度计算Ａｒｅａ（ｉ，ｊ）采用指标ρＡｒｅａ，否则采用泰森多边形形状相似度指
，最终选取相似度指标值最高的对标ρａｂｓｈａｅ（ｉ，ｊ）ｐ
应的点实体作为最佳匹配对象。
图４ 源数据与目标数据的泰森多边形叠加效果Ｆｉ．４ ＳｕｅｒｏｓｉｔｉｏｎＥｆｆｅｃｔｏｆＴｈｉｅｓｓｅｎＰｏｌｏｎｓ ｇｐｐｙｇ
ｆｒｏｍＳｏｕｒｃｅＤａｔａａｎｄＴａｒｅｔＤａｔａ ｇ
况。图５黑色加ａ中源要素２８对应的泰森多边形（粗）不包含目标要素，但是通过算法处理，先找到两个相交的目标多边形，然后通过多边形面积及形状相似度计算可找出最佳匹配目标要素１７。图５ｂ为包含１个目标要素的情形，源要素点１８对应的泰森多边形包含目标要素１２，且当前泰森多边形相交多个目标泰森多边形，通过面积及形状相似度计算最终找出最佳匹配目标要素１２。图５ｃ为包含２个目标要素的情形，３１号对应的泰森多边形与相交的目标泰森多边形的面积相似度均小于０．５，为此采用形状相似度比较，最终确定最佳匹配目标要素４５。
此外，本文选取４种不同的算法：位置最近算
４］６］
、互相位置最近算法［、点环境相似度算法［
１０］
以及本文提出的基于泰森多边形的算法进行法［
３ 实验及结果分析
３．１ 实验数据
本文选取同一地区不同来源的城市兴趣点（）数据进行试验。图３是两种来源的数据叠加ＰＯＩ
后的效果，其中源数据（含实体数目４Ｓ）６个，用黑色实点表示，目标数据（含实体数目４Ｔ）８个，用黑色虚点表示。图４是源数据的泰森多边形（边界线用粗黑线表示）与目标数据的泰森多边形（边界线用细虚线表示）叠加后的效果图。３．２ 实验结果分析
按照２．２节中算法流程及２．３节中的泰森多边形相似度计算方法及相关阈值进行了点实体匹配实验。图５
给出了点实体匹配过程中的几种典型情
１００测绘科学第４０
卷
最近算法及点环境相似度算法均需要使用缓冲区。在缓冲区半径为１事先通过人工量算相关同名２ｍ（点之间的距离后设定的一个值）时，位置最近算法计算时间短，互相位置最近算法匹配相对前者时间增长，但该方法针对非一致性偏差数据匹配时，其查准率反而稍有降低，点环境相似度算法相对前
图５ 几种匹配情况的处理分析
Ｆｉ．５ ＰｒｏｃｅｓｓｉｎＡｎａｌｓｉｓｏｆＳｅｖｅｒａｌＭａｔｃｈｉｎＣａｓｅｓ ｇｇｙｇ
两者耗时长，但查准率高。通过加大缓冲区半径到２４ｍ，相对缓冲区半径为１２ｍ时，各算法的查全率
得到提高，仅有位置最近算法、互相位置最近算法的查准率得到提高，而由于使用更大范围的周边环境进行比较，其环境变化的可能性增大，导致点环境相似度算法的查准率降低。而基于泰森多边形的算法不需要使用缓冲区搜索目标实体，仅通过自动计算出的距离阈值作为判别同名实体的条件之一，该算法同时具有最高的查全率和查准率。
点实体匹配实验与比较，匹配结果见表１，其中，
ｒ为搜索候选集时使用的缓冲区半径，Ｒ表示源数据中能够建立匹配对的实体数目，Ｃ表示匹配正确的实体数目。设源数据集中的实体数目为Ｅ，则查／／全率为ＲＥ，查准率为ＣＲ。
从表１中可以看出，位置最近算法、互相位置
表１ 匹配算法比较
Ｔａｂ．１ ＣｏｍａｒｉｓｏｎｏｆＥｎｔｉｔＭａｔｃｈｉｎＡｌｏｒｉｔｈｍｓ ｐｙｇｇ
（ｒｍ）
是否使用缓冲区
√
１２
√√√
２４
√√
１２．２４８（自动计算出的距离阈值）
×
基于泰森多边形的算法
４４
４４
９５．６５％
１００％
３．２６５６２５
算法位置最近算法互相位置最近算法点环境相似度算法位置最近算法互相位置最近算法点环境相似度算法
Ｒ
４３ ４３ ４３ ４４ ４４ ４４
Ｃ
３７ ３３ ３８ ３８ ３４ ３４
查全率９３．４８％９３．４８％９３．４８％９５．６５％９５．６５％９５．６５％
查准率８６．０５％７６．７４％８８．３７％８６．３６％７７．２７％７７．２７％
（）匹配耗时ｔｓ０．１０９３７５０．１２５０．３１２５０．１２５０．１５６０．８５９３７５
４ 结束语
本文从全局考虑两个相匹配的点实体数据集具有相似的形态结构，从而将不确定的点与点之间的匹配关系转移到其对应泰森多边形的匹配。基于泰森多边形的点实体匹配算法相对现有的方法具有以下３点优势：①具有较高的查全率和查准率；②普适性强，不同于以往使用点缓冲区搜索候选目标时，缓冲区半径的设置依赖于地图比例尺，而本文算法能够适应不同比例尺的点实体匹配；③能够满足众源地理数据的匹配应用。不足之处是建立泰森多边形需要消耗一些时间，但随着计算机存储及计算能力的提高，构建泰森多边形时间与空间上的成本可忽略不计。
参考文献
［］１ａａｌｆｅｌｄＡ．ＡｕｔｏｍａｔｅｄＭａＣｏｎｆｌａｔｉｏｎ［Ｄ］．Ｗａｓｈｉｎ Ｓ －ｐｇ
，ｔｏｎＤＣ：ＵｎｉｖｅｒｓｉｔｏｆＭａｒｌａｎｄ１９９３：１１０． －ｙｙ
［］］龚健雅，张桥平．论地图数据库合并技术［２Ｊ． 李德仁，
（）：测绘科学，２００４，２９１１４．－
［］］李德仁，龚健雅．地图合并技术［测绘通报，３Ｊ． 张桥平，
（）：２００１７６８．－
［］地图数据库实体匹配与合并技术研究［武４Ｄ］． 张桥平．
汉：武汉大学，２００２：１１０．－
［］苏山舞．多空间数据库位置匹配方法及其应用５ 刘东琴，
［］（）：测绘科学，Ｊ．２００５，３０２７８８１．－
［］６ｅｅｒｉＣ，ＫａｎｚａＹ，ＳａｆｒａＥ，ｅｔａｌ．ＯｂｅｃｔＦｕｓｉｏｎｉｎＧｅｏ Ｂ －ｊ
／／ｒａｈｉｃＩｎｆｏｒｍａｔｉｏｎＳｓｔｅｍｓ［Ｃ］Ｐｒｏｃｅｅｄｉｎｓｏｆｔｈｅ ｇｐｙｇ，ＶＬＤＢＣｏｎｆｅｒｅｎｃｅ．Ｔｏｒｏｎｔｏ２００４：８１６８２７．３０ｔｈ －［］７ａｌｔｅｒＶ，ＦｒｉｔｓｃｈＤ．ＭａｔｃｈｉｎＳａｔｉａｌＤａｔａＳｅｔｓａＳｔａ Ｗ －ｇｐ
ｔｉｓｔｉｃａｌＡｒｏａｃｈ［Ｊ］．ＧｅｏｒａｈｉｃａｌＩｎｆｏｒｍａｔｉｏｎＳｃｉ －ｐｐｇｐ，（）：ｅｎｃｅ１９９９，１３５４４５４７３．－
［］邓愫愫，史文中．基于概率的地图实体匹配方８ 童小华，
］（）：法［测绘学报，Ｊ．２００７，３６２２１０２１７．－
［］，９ｏｂｂＭ Ａ，ＣｈｕｎＭＪＦｏｌｅＩＩＩＨ，ｅｔａｌ．ＡＲｕｌｅｂａｓｅｄＡ Ｃ － －ｇｙｐ
［］ｒｏａｃｈｆｏｒｔｈｅＣｏｎｆｌａｔｉｏｎｏｆＡｔｔｒｉｂｕｔｅｄＶｅｃｔｏｒＤａｔａＪ．Ｇｅｏ ｐ
，，（）：Ｉｎｆｏｒｍａｔｉｃｓ１９９８２１７３５．－
（下转第１２０页）
１２０测绘科学第４０卷
ＣｏｎｆｅｒｅｎｃｅｏｎＧｅｏＣｏｍｕｔａｔｉｏｎ．２００５：５５１５６２． －ｐ
，ＲｅｔｒｉｅｖａｌｏｎＣｏｍｏｓｉｔｅＫｅＪ］．ＡｃｔａＩｎｆｏｒｍａｔｉｃａ ｐｙ［（）：１９７４，４１１９．－
［，１２］ＭａＨｏｎｃｈａｏＷａｎＺｏｎｕｅ．ＤｉｓｔｒｉｂｕｔｅｄＤａｔａＯｒ －ｇｇｇｙ
ａｎｄＰａｒａｌｌｅｌＤａｔａＲｅｔｒｉｅｖａｌＭｅｔｈｏｄｓｆｏｒａｎｉｚａｔｉｏｎ ｇ
ＨｕｅＬａｓｅｒＳｃａｎｎｅｒＰｏｉｎｔＣｌｏｕｄｓ［Ｊ］．Ｃｏｍｕｔｅｒｓ＆ ｇｐ，（）：Ｇｅｏｓｃｉｅｎｃｅｓ２０１１，３７２１９３２０１．－
［］Ｗ，１３ａｎＪＳｈａｎＪ．ＳａｃｅＦｉｌｌｉｎＣｕｒｖｅＢａｓｅｄＰｏｉｎｔ ｇｐｇ
［／／ＣｌｏｕｄｓＩｎｄｅｘＣ］Ｐｒｏｃｅｅｄｉｎｓｏｆｔｈｅ８ｔｈＩｎｔｅｒｎａｔｉｏｎａｌ ｇ
［］Ｂ１４ｅｎｔｌＪＬ．ＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＢｉｎａｒＳｅａｒｃｈＴｒｅｅＵｓｅｄ ｙｙ
］ＡｓｓｏｃｉａｔｉｖｅＳｅａｒｃｈｉｎＪ．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅｆｏｒ ｇ［（）：ＡＣＭ，１９７５，１８９５０９５１７．－
［］林祥国，张继贤．机载Ｌ１５ｉＤＡＲ数据的多回波信息分析
］（）：及滤波方案［测绘科学，Ｊ．２０１３，３８３３２３４．－［］雷随．三维激光点云数据组织与可视化研究［武１６Ｍ］．
汉：武汉大学，２０１２．
ｏｉｎｔＲｅｓｅａｒｃｈｏｎｃｌｏｕｄｄａｔａｍａｎａｅｍｅｎｔｂａｓｅｄｏｎｓａｔｉａｌｉｎｄｅｘａｎｄｄａｔａｂａｓｅ ｐｇｐ
：，ｗ，ｂＬａｓｅｒｓｅｔｈａｓａｍａｓｓｉｖｅｏｆｄａｔａｈｉｃｈｎｏｔｏｎｌｉｎｃｒｅａｓｅｓｓｓｔｅｍｌｏａｄｕｔｏｉｎｔｕａｎｔｉｔＡｂｓｔｒａｃｔ ｙｙｐｑｙ ａｌｓｏｒｅａｔｌｒｅｄｕｃｅｓｔｈｅｆｏｌｌｏｗ－ｕｒｏｃｅｓｓｉｎｅｆｆｉｃｉｅｎｃａｓｗｅｌｌ．Ｃｏｎｓｉｄｅｒｉｎｔｈｅｄｉｆｆｉｃｕｌｔｏｆｍａｓｓｏｉｎｔ ｇｙｐｐｇｙｇｙｐ
，ｇｃｌｏｕｄｄａｔａｏｒａｎｉｚａｔｉｏｎａｎｄｍａｎａｅｍｅｎｔｒｉｄｉｎｄｅｘｏｆｏｉｎｔｃｌｏｕｄｄａｔａｂａｓｅｄｏｎｔｈｅｄｅｃｉｍａｌｌｉｎｅａｒ ｇｇｐ，ｐｕａｄｔｒｅｅｗａｓｉｎｔｈｉｓｃｌｏｕｄｄａｔａｗａｓｓｅｍｅｎｔｅｄａｎｄｅｎｃｏｄｅｄｂｍｅａｎｓｏｆｌｉｎｅａｒｒｏｏｓｅｄａｅｒｏｉｎｔ ｑｐｐｐｐｇｙ
，ｐｕａｄｔｒｅｅｏｉｎｔｂａｓｅｄｏｎｄｅｃｉｍａｌｓｓｔｅｍ，ｗｈｉｃｈｗｏｕｌｄｂｅｓｔｏｒｅｄｉｎＳＱＬＳｅｒｖｅｒ．Ｔｈｅｎｃｌｏｕｄｃｏｕｌｄｂｅ ｑｙ，ｃａｎｄｉｎｄｅｘｅｄｉｎｔｅｒｍｓｏｆＭｏｒｔｏｎｃｏｄｅｏｒｒｅｃｔａｎｕｌａｒｒｅｉｏｎｏｍｂｉｎｅｄｗｉｔｈｔｈｅａｄｖａｎｔａｅｓｏｆｂｏｔｈｂｌｏｃｋｅｄ ｇｇｇｏｉｎｔｒｏｓａｔｉａｌｉｎｄｅｘａｎｄｄａｔａｂａｓｅｔｏｍａｎａｅｃｌｏｕｄｅｆｆｉｃｉｅｎｔｌａｎｄｓａｆｅｌ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｅｄｔｈａｔｔｈｅ －ｐｐｐｇｙｙ ｏｓｅｄｒｏｂｌｅｍｏｉｎｔｍｅｔｈｏｄｉｄｅａｌｌｓｏｌｖｅｄｔｈｅｏｆｃｌｏｕｄｄａｔａｏｒａｎｉｚａｔｉｏｎａｎｄｍａｎａｅｍｅｎｔ． ｐｐｐｙｇｇ
：；ｓ；ｄ；ｖＫｅｗｏｒｄｓｏｉｎｔｃｌｏｕｄａｔｉａｌｉｎｄｅｘａｔａｂａｓｅｉｓｕａｌｉｚａｔｉｏｎ ｐｐｙ
１２１３，Ｌ，Ｔ，ＭＡ ＬＩＪｉａｎＥＩＳｕｉＩＡＮ ＺｈｉｈｕｉＹｕ－ｒｏｎ１．ＣｏｌｌｅｅｏｆＷａｔｅｒＣｏｎｓｅｒｖａｎｃａｎｄＥｎｖｉｒｏｎ － －ｇｙｇ（
，Ｚ，Ｚ；２ｍｅｎｔａｌＥｎｉｎｅｅｒｉｎｈｅｎｚｈｏｕＵｎｉｖｅｒｓｉｔｈｅｎｚｈｏｕ４５０００３，Ｃｈｉｎａ．ＳｃｈｏｏｌｏｆＲｅｍｏｔｅＳｅｎｓｉｎａｎｄ ｇｇｇｙｇｇ
，Ｗｕ，Ｗｕ；３，ＩｎｆｏｒｍａｔｉｏｎＥｎｉｎｅｅｒｉｎｈａｎＵｎｉｖｅｒｓｉｔｈａｎ４７０００３，Ｃｈｉｎａ．ＺｈｅｎｚｈｏｕＵｎｉｖｅｒｓｉｔＬｉｂｒａｒ ｇｇｙｇｙｙ
）Ｚｈｅｎｚｈｏｕ４５０００１，Ｃｈｉｎａ ｇ
檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿
（上接第１００页）
］吴建华．［顾及环境相似的多特征组合的实体匹配方法１０
［］（）：地理与地理信息科学，Ｊ．２０１０，２６４１６．－
［］吴建华，付仲良．数据更新中要素变化检测与匹配方法１１
［］（）：计算机应用，Ｊ．２００８，２８６１３８３１３８６．－
［］Ｆ，１２ｕＺｈｏｎｌｉａｎＷｕＪｉａｎｈｕａ．ＥｎｔｉｔＭａｔｃｈｉｎｉｎＶｅｃｔｏｒ ｇｇｙｇ
［／／，，ＤａｔａＣ］Ｔｈｅ２１ｓｔＩＳＰＲＳＣｏｎｆｅｒｅｎｃｅＢｅｉｉｎ２００８， ｊｇ３７，ＰａｒｔＢ４：１４６７１４７２． －
ＰｏｉｎｔｅｎｔｉｔｍａｔｃｈｉｎａｌｏｒｉｔｈｍｂａｓｅｄｏｎＴｈｉｅｓｓｅｎｏｌｏｎ ｙｇｇｐｙｇ
：ＡｒｏｂｌｅｍＡｂｓｔｒａｃｔｉｍｉｎａｔｔｈｅｔｈａｔｔｈｅｒｅａｒｅｓｏｍｅｉｎｃｏｎｓｉｓｔｅｎｔｄｅｖｉａｔｉｏｎｓｏｆｄｉｓｔａｎｃｅａｎｄｄｉｒｅｃｔｉｏｎ ｐｇ
，ｗｉｎｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓｆｒｏｍｃｒｏｗｄｓｏｕｒｃｉｎｄａｔａｈｉｃｈｍａｋｅｓｉｔｄｉｆｆｉｃｕｌｔｆｏｒｅｎｔｉｔｅｏｒａｈｉｃｅｘｉｓｔ ｐｇｇｙｇｇｐ
，ａｍａｔｃｈｉｎｍａｔｃｈｉｎａｌｏｒｉｔｈｍｏｆｅｎｔｉｔｉｅｓｂａｓｅｄｏｎＴｈｉｅｓｓｅｎｗａｓｉｎｔｈｉｓｏｉｎｔｏｌｏｎｒｏｏｓｅｄａ －ｇｇｇｐｐｙｇｐｐｐ ｅｒ．ＢｅｃａｕｓｅｏｌｏｎｓｏｉｎｔｏｆｔｈｅｈｉｈｅｒｃｏｒｒｅｓｏｎｄｉｎｒｅｌａｔｉｏｎｓｈｉｏｆｒｅｌａｔｅｄＴｈｉｅｓｓｅｎｏｆｔｈｅｍａｔｃｈｅｄｅｎ －ｐｐｙｇｐｇｐｇｐ ，ｔｉｔｉｅｓｔｈｅｕｎｃｅｒｔａｉｎｏｉｎｔｅｎｔｉｔｍａｔｃｈｉｎｗａｓｃｏｎｖｅｒｔｅｄｔｏｃｏｒｒｅｓｏｎｄｉｎＴｈｉｅｓｓｅｎｏｌｏｎｍａｔｃｈｉｎ ｐｙｇｐｇｐｙｇｇ ，，ａｗｉｔｈｈｉｈｅｒｓｉｍｉｌａｒｉｔ．ＦｉｒｓｔｌｔｈｅｃｏｎｔａｉｎｅｄｂｍｕｔｕａｌＴｈｉｅｓｓｅｎｗｅｒｅｃｏｕｎｔｅｄｎｄｏｉｎｔａｉｒｓｏｌｏｎｓ ｇｙｙｙｐｐｐｙｇ ｔｈｅｄｉｓｔａｎｃｅｔｈｒｅｓｈｏｌｄｒｅａｒｄｅｄａｓｏｎｅｃｏｎｄｉｔｉｏｎｏｆｃｏｎｆｉｒｍｉｎｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓｗａｓｃａｌｃｕｌａｔｅｄａｃｃｏｒｄ －ｇｇｐｇ
；Ｔ，ｉｎｔｏｄｉｓｔａｎｃｅｒｏｂａｂｉｌｉｔｄｉｓｔｒｉｂｕｔｉｏｎｏｆｏｉｎｔａｉｒｓｈｅｎｔｈｅｏｓｉｔｉｏｎｓｉｍｉｌａｒｉｔａｎｄｓｈａｅｓｉｍｉｌａｒｉｔｏｆ ｇｐｙｐｐｐｙｐｙ ；Ｌ，Ｔｈｉｅｓｓｅｎｏｌｏｎｓｗｅｒｅｒｅａｒｄｅｄａｓｔｈｅｓｅｃｏｎｄｃｏｎｄｉｔｉｏｎｏｆｕｄｉｎｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓａｓｔｌｔｈｏｓｅｅｎｔｉｔｉｅｓ ｐｙｇｇｊｇｇｐｇｙ ｔｈｅｈｉｈｅｓｔｓｉｍｉｌａｒｉｔｗｅｒｅｒｅａｒｄｅｄａｓｔｈｅｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓ．Ｃｏｍａｒｉｎｗｉｔｈｅｘｉｓｔｉｎｍａｔｃｈｉｎａｌｏｗｉｔｈ －ｇｙｇｐｇｐｇｇｇｇ
，，ｐｒｉｔｈｍｓｔｈｅｒｅｓｕｌｔｓｓｈｏｗｅｄｔｈａｔｔｈｉｓａｌｏｒｉｔｈｍｈａｄｈｉｈｅｒｒｅｃａｌｌｒａｔｅａｎｄｕｎｉｖｅｒｓａｌｉｔ．ｒｅｃｉｓｉｏｎ ｇｇｙ
：；ｅ；ｄ；ＴＫｅｗｏｒｄｓｓｈａｅｓｉｍｉｌａｒｉｔｎｔｉｔｍａｔｃｈｉｎａｔａｆｕｓｉｏｎｈｉｅｓｓｅｎｏｌｏｎ；ｃｒｏｗｄｓｏｕｒｃｉｎｅｏ －ｐｙｙｇｐｙｇｇｇｙ ｒａｈｉｃｄａｔａ ｇｐ
，ａｎＷＵ Ｊｉａｎ－ｈｕａ，ＷＡＮ ＹａｎＳｃｈｏｏｌｏｆＧｅｏｒａｈａｎｄＥｎｖｉｒｏｎｍｅｎｔＪｉａｎｘｉＮｏｒｍａｌＵｎｉｖｅｒｓｉ －ｇｐｙｇｙｇ（ｇ－ ／，ＮｔＫｅＬａｂｏｆＰｏａｎＬａｋｅＷｅｔｌａｎｄａｎｄＷａｔｅｒｓｈｅｄＲｅｓｅａｒｃｈ，ＭｉｎｉｓｔｒｏｆＥｄｕｃａｔｉｏｎａｎｃｈａｎ３３００２２， ｙｙｙｇｙｇ
）Ｃｈｉｎａ
第４０卷第４期２０１５年４月
测绘科学
ＳｃｉｅｎｃｅｏｆＳｕｒｖｅｉｎａｎｄＭａｉｎ ｙｇｐｐｇ
Ｖｏｌ．４０Ｎｏ．４
Ａｒ
．ｐ
利用泰森多边形的点实体匹配算法
吴建华，万洋洋
（）江西师范大学地理与环境学院／鄱阳湖湿地与流域研究教育部重点实验室，南昌 ３３００２２
摘 要：针对众源地理数据中的同名点实体之间存在距离、方向等非一致性偏差，导致匹配困难的问题，该文提出了基于泰森多边形的点实体匹配算法。利用相匹配的点实体数据集其对应的泰森多边形具有较高的对应关系这一特点，将不确定的点与点之间的匹配转化为匹配度更高的对应泰森多边形的匹配。首先统计出被彼此泰森多边形包含的点对，根据点对的距离概率分布，计算出距离阈值作为确认同名实体的条件之一；然后将泰森多边形的位置及形状相似性作为匹配条件二；最后将相似度最高的实体确认为同名实体。通过实验与现有的几种点实体匹配算法进行了比较，结果表明，该算法具有较高的查全率和查准率，且普适性强。关键词：形状相似度；实体匹配；数据融合；泰森多边形；众源地理数据
【（）中图分类号】Ｐ文献标识码】Ａ 【文章编号】１２０８ 【００９２３０７２０１５０４００９７０５－－－：１／ＤＯＩ０．１６２５１２３０７．２０１５．０４．０２２．ｃｎｋｉ．１００９－ｊ
１ 引言
实体匹配是指通过相似性指标识别出不同来源地图数据中同名实体并建立实体对应关系的过
］１３－
，它是地图数据融合与更新中的一个关键环程［
点实体局部环境的整体相似性，在一定程度上解决了非一致性偏差问题，但点实体密度对各种因素比较敏感，会降低该方法的普适性。随着志愿者地理信息的兴起，许多公司或普通民众都可以上传、分享或标注地图，这些非测绘或ＧＩＳ专业
人士上传的地图含有丰富的属性或拓扑信息，但其精度并不一定高。而小比例尺地图更多地是注重地理形态与结构的表示，地图的几何精确性通常让位于地理适应性。将这些不同来源的同一专题的数据进行叠加必然会存在数据的非一致性偏差。为了提高点实体的匹配精度及可靠性，本文以相近比例尺的城市兴趣点数据匹配为例，设计并实现了基于泰森多边形的点实体匹配方法。
节。点实体匹配是指识别出两个数据集中反映现实世界同一地物的独立点实体（比如：酒店、医院、超市、公交站点等）的过程。点实体的匹配结果可以用于属性信息的转换、实体替换更新、建立两幅地图之间局部坐标转换关系等。针对点实体的匹配，学者们已经提出了一些方法，比如位
］４５６］－
、相互位置最近的方法［、基于置最近的方法［
］７８９］－
、基于属性相似的方法［，但是这概率的方法［
些方法只是片面地强调位置或属性，而实际上位置最近或属性相似的两个点实体并非是同名实体，即不适用于较多同名实体存在非一致性偏差的数
１０］
，考虑了据集。虽然基于环境特征相似的方法［
２ 基于泰森多边形的匹配算法原理
２．１ 泰森多边形在点匹配中的应用分析
表达同一地区相同专题的两个点集中，其点实体之间的关系及整体布局结构应相同或相似。泰森多边形是按欧氏距离最近这一原则将平面上分类，所有点（ｐｐｐ１，２，…，ｎ是其中的一部分）分别得到距离每个ｐ最近的点集：１≤ｉｎ）≤ｉ（，ｐＶＲ（＝｛ｉｐｑ｜ｑｐｑｐｊ≠ｉ）ｉ｜≤｜ｉ，ｊ｜，
，其中，｜Ｐ｝ｐｑｐ｜表示两点之间的欧氏距离，ｊ∈
为站点Ｐ＝｛ＶＲ（ｐｐｐｐ１，２，…，ｎ｝的集合，ｉ）
ｐｉ的泰森多边形。形态结构形似的点集，点实体对应的泰森多边形有较好的一对一关系，从而可以将不可靠的点与点匹配转化为可靠性强的面与面的匹配。匹配时存在以下几种情况：①若两个点实体数
，男，江西作者简介：吴建华（１９８１）鄱阳人，副教授，博士，主要从事地理空间数据匹配与融合，地理信息工程等方面的研究。：ｗＥ－ｍａｉｌｈｉｓ２６．ｃｏｍ＠１ｊｇ收稿日期：２０１４０７２９－－
基金项目：国家自然科学基金项目
（）；江西省教育厅青年科学基金项目４１２０１４０９，４１２６１０８６
（）；鄱阳湖湿地与流域研究教育部重点实验室主任ＧＪＪ１２２０）开放基金项目（ＺＫ２０１３００８
９８测绘科学第４０卷
据集完全匹配，则同名实体所对应的泰森多边形的面积及形状具有极高的相似性；②当两个点实体数据集不完全匹配时（即存在新增、修改、删除数据的，若两同名实体及其周边环境相似时，则两个情况）
同名实体的泰森多边形形状形似，若同名实体邻近数据部分发生变化，则两个同名实体的泰森多边形局部边界存在局部相似性；③当某个实体为新增或待删除对象时，在其泰森多边形内，要么不包含目超标匹配数据集中的点实体，要么包含离其比较远（过某一距离阈值）的目标实体。
２．２ 算法流程
设Ａ＝｛ａａａ１，２，…，ｎ｝为源点实体数据集（，Ｂ＝｛ａｂｂｂｎ为Ａ中的点要素）１，２，…，ｎ｝为。基于泰目标点实体数据集（ｂｎ为Ｂ中的点要素）森多边形的点实体匹配算法的步骤如下：
）分别为Ａ、Ｂ建立泰森多边形图层Ｐ＝１｛ｐｐｐ１，２，…，ｐｎ｝（ｎ为Ｐ中的泰森多边形要
、Ｑ＝｛素）ｑｑｑｑ１，２，…，ｎ｝（ｎ为Ｑ中的泰森多。边形要素）
）建立匹配条件。遍历Ｐ中的每个要素ｐ２ｐｉ（ｉ
，找出仅包含１个Ｂ中要为ａｉ对应的泰森多边形）素（设为ｂ的所有多边形。计算这些多边形中ａｉｊ）与ｂｊ的距离值，借鉴拉依达准则对其改进，将小
及大于μ＋于μ－δ（δ为距离标准差）μ为平均距离，
δ的值作为异常值剔除，计算出剩余点对的距离均值μ和距离标准差δ，将匹配点对距离小于等于μ＋３δ作为选择候选集的条件之一。
）进行匹配计算。查看包含在ｐ３ｉ中的Ｂ中的要素数目，①若包含在ｐｉ中的Ｂ中的要素数目为０，则看ｐｉ是否存在与其相交且Ｑ中的泰森多边形（ｐｉ与ｑｉ与ｑｊ要满足一定的相似度，即要求ｐｊ的，若不存在相交面积与ｐ０％）ｉ的面积之比大于２符合条件的ｑｉ无匹配对象，若仅存１ｊ，则表示ｐ个与ｐｉ相交的泰森多边形，则计算两个面中对应点之间的距离是否符合条件一，若符合则将对应的点视为匹配对象，若存在多个与ｐｉ相交的泰森多边形，先剔除不符合条件一的匹配对象，然后比较符合条件一的对应泰森多边形的形状相似性，））将相似度（计算方法见公式（最高的ｑ１ｊ视为匹配对象，并建立对应点的匹配关系；②若包含在ｐｉ中的Ｂ中的要素数目为１，则检查其是否满足条件一，若满足则建立对应点的匹配关系，否则记录对应的ｂｉ中的Ｂ中的ｊ为新增要素；③若包含在ｐ要素数目大于等于２，先剔除不符合条件一的匹配对象，然后比较符合条件一的对应泰森多边形的
）形状相似性，将相似度（计算方法见公式（最高１）的ｑｊ视为匹配对象，并建立对应点的匹配关系。２．３ 泰森多边形相似度计算方法
考虑到大部分同名点实体其对应的泰森多边形有较高的重叠度，而在点实体数据集的一些弱覆盖区域其对应的泰森多边形重叠度偏低，为了得到较好的匹配质量，设计了以下综合相似度计）。算模型，见公式（１
，ａｂａｂＡｒｅａ（ｉ，Ａｒｅａ（ｉ，≥Ｔｊ）ｊ）ρρ
，＝ａｂρｉｊ
，ａｂａｂＳｈａｅ（ｉ，Ａｒｅａ（ｉ，＜Ｔｐｊ）ｊ）ρρ（ｉ）（，）ａｂ＝Ａｒｅａｉｊρ［（，（］ｍｉｎｓａｓｂｉ）ｊ）
｛
（）１（）２
其中，表示面积相似度，从一定程度ａｂＡｒｅａ（ｉ，ｊ）ρ
１１］
，计算上可以反映多边形位置与形状的相似性［
；Ｔ为面积相似度阈值，当两泰森方法见公式（２）多边形面积重叠度较高时，建议采用面积相似度作为评判对应泰森多边形的依据，反之使用形状相似度作为评判对应泰森多边形的依据，根据实验数据观察分析，本文Ｔ取０表．５；ａｂｓｈａｅ（ｉ，ｊ）ｐρ示对应泰森多边形的轮廓形状相似度，其计算方
１２］
，将其改进后法借鉴基于折线段方位编码方法［
应用到多边形轮廓形状的匹配，即将多边形的轮廓形状通过各边的方位编码来描述。其设计思路如下：首先，将直角坐标系中围绕坐标原点构成的圆周按照一定的角度间隔进行角度分区，并对每个角度分区进行编码；如图１中的间隔角度为（经过前期实验，该角度间隔可区分泰森多边形１５°
，整个圆周被分为２边方向）４个区，可分别用Ａ～Ｘ字符来编码。当边的方位角恰好位于圆周分割线
，需要将计算出的编上时（除Ｘ坐标轴的正方向）码降为它的下一级，比如将编码Ｄ变为编码Ｃ。为了便于待匹配多边形之间各边方位的比较，计算方位编码前需将两个待匹配的多边形上的节点统一按顺时针（或逆时针）进行排列。每边的方位编
图１ 圆周角度分区Ｆｉ．１ ＡｎｌｅＺｏｎｅｓｏｆＣｉｒｃｌｅ ｇｇ
］引用格式：吴建华，万洋洋．利用泰森多边形的点实体匹配算法［Ｊ．测绘科学，２０１５，４０
第４期
（）：９４７１００．－
９９
ｃｏｄｅ＝Ｃｈｒ６５＋Ｉｎｔ
（
ａｚｉｍｕｔｈｌｌ１）＋
１５
（…，ｉ＝１，２，ｎ）
］）
（）３
其中，Ｃ的函ｈｒ为将数值转换为编码字符（Ａ～Ｘ）数，Ｎｉ、Ｎｉ＋１为折线上相邻的两个结点，ａｚｉｍｕｔｈ
（］为返表示向量ＮｉＮｉＮｉ＋１）Ｎｉ＋１的方位角，ｉｎｔ［回整数部分的函数。在对多边形各边计算方位编码后，可得到由多边形各边方位编码组成的形状。图２为两个描述字符串Ｓｉ∈１，２，３，…，ｎ）ｉ（
对应的泰森多边形的形状编码计算示例
。
图３ 源数据与目标数据叠加效果Ｆｉ．３ ＳｕｅｒｏｓｉｔｉｏｎＥｆｆｅｃｔｏｆＳｏｕｒｃｅ ｇｐｐ
ＤａｔａａｎｄＴａｒｅｔＤａｔ
ａ ｇ
图２ 泰森多边形的形状编码Ｆｉ．２ ＳｈａｅＣｏｄｉｎｏｆＴｈｉｅｓｓｅｎＰｏｌｏｎ ｇｐｇｙｇ
设两个待匹配的泰森多边形的形状描述字符）表示形状描述字符串串分别为ＳｓＮｕｍ（ｉ和Ｓｊ，
中的字符个数，遍历Ｓｉ中的每个字符看其在Ｓｊ中能否找到相同字符，若找到则将配对的字符放入集合Ｅ表示集合中的字符总ｕｍＥｃ中，设Ｎｓａｍｅ（ｃ）进行数目，则多边形的形状相似度可用公式（４）计算。
ＮｕｍｓＥａｍｅ（ｃ））（ａｂ４＝Ｓｈａｅ（ｉ，ｐｊ）ρｓＮｕｍＳＮｕｍｓ＋ｓｉｊ）公式（表明若ρ４ａｂ≥Ｔ则相似度计算Ａｒｅａ（ｉ，ｊ）采用指标ρＡｒｅａ，否则采用泰森多边形形状相似度指
，最终选取相似度指标值最高的对标ρａｂｓｈａｅ（ｉ，ｊ）ｐ
应的点实体作为最佳匹配对象。
图４ 源数据与目标数据的泰森多边形叠加效果Ｆｉ．４ ＳｕｅｒｏｓｉｔｉｏｎＥｆｆｅｃｔｏｆＴｈｉｅｓｓｅｎＰｏｌｏｎｓ ｇｐｐｙｇ
ｆｒｏｍＳｏｕｒｃｅＤａｔａａｎｄＴａｒｅｔＤａｔａ ｇ
况。图５黑色加ａ中源要素２８对应的泰森多边形（粗）不包含目标要素，但是通过算法处理，先找到两个相交的目标多边形，然后通过多边形面积及形状相似度计算可找出最佳匹配目标要素１７。图５ｂ为包含１个目标要素的情形，源要素点１８对应的泰森多边形包含目标要素１２，且当前泰森多边形相交多个目标泰森多边形，通过面积及形状相似度计算最终找出最佳匹配目标要素１２。图５ｃ为包含２个目标要素的情形，３１号对应的泰森多边形与相交的目标泰森多边形的面积相似度均小于０．５，为此采用形状相似度比较，最终确定最佳匹配目标要素４５。
此外，本文选取４种不同的算法：位置最近算
４］６］
、互相位置最近算法［、点环境相似度算法［
１０］
以及本文提出的基于泰森多边形的算法进行法［
３ 实验及结果分析
３．１ 实验数据
本文选取同一地区不同来源的城市兴趣点（）数据进行试验。图３是两种来源的数据叠加ＰＯＩ
后的效果，其中源数据（含实体数目４Ｓ）６个，用黑色实点表示，目标数据（含实体数目４Ｔ）８个，用黑色虚点表示。图４是源数据的泰森多边形（边界线用粗黑线表示）与目标数据的泰森多边形（边界线用细虚线表示）叠加后的效果图。３．２ 实验结果分析
按照２．２节中算法流程及２．３节中的泰森多边形相似度计算方法及相关阈值进行了点实体匹配实验。图５
给出了点实体匹配过程中的几种典型情
１００测绘科学第４０
卷
最近算法及点环境相似度算法均需要使用缓冲区。在缓冲区半径为１事先通过人工量算相关同名２ｍ（点之间的距离后设定的一个值）时，位置最近算法计算时间短，互相位置最近算法匹配相对前者时间增长，但该方法针对非一致性偏差数据匹配时，其查准率反而稍有降低，点环境相似度算法相对前
图５ 几种匹配情况的处理分析
Ｆｉ．５ ＰｒｏｃｅｓｓｉｎＡｎａｌｓｉｓｏｆＳｅｖｅｒａｌＭａｔｃｈｉｎＣａｓｅｓ ｇｇｙｇ
两者耗时长，但查准率高。通过加大缓冲区半径到２４ｍ，相对缓冲区半径为１２ｍ时，各算法的查全率
得到提高，仅有位置最近算法、互相位置最近算法的查准率得到提高，而由于使用更大范围的周边环境进行比较，其环境变化的可能性增大，导致点环境相似度算法的查准率降低。而基于泰森多边形的算法不需要使用缓冲区搜索目标实体，仅通过自动计算出的距离阈值作为判别同名实体的条件之一，该算法同时具有最高的查全率和查准率。
点实体匹配实验与比较，匹配结果见表１，其中，
ｒ为搜索候选集时使用的缓冲区半径，Ｒ表示源数据中能够建立匹配对的实体数目，Ｃ表示匹配正确的实体数目。设源数据集中的实体数目为Ｅ，则查／／全率为ＲＥ，查准率为ＣＲ。
从表１中可以看出，位置最近算法、互相位置
表１ 匹配算法比较
Ｔａｂ．１ ＣｏｍａｒｉｓｏｎｏｆＥｎｔｉｔＭａｔｃｈｉｎＡｌｏｒｉｔｈｍｓ ｐｙｇｇ
（ｒｍ）
是否使用缓冲区
√
１２
√√√
２４
√√
１２．２４８（自动计算出的距离阈值）
×
基于泰森多边形的算法
４４
４４
９５．６５％
１００％
３．２６５６２５
算法位置最近算法互相位置最近算法点环境相似度算法位置最近算法互相位置最近算法点环境相似度算法
Ｒ
４３ ４３ ４３ ４４ ４４ ４４
Ｃ
３７ ３３ ３８ ３８ ３４ ３４
查全率９３．４８％９３．４８％９３．４８％９５．６５％９５．６５％９５．６５％
查准率８６．０５％７６．７４％８８．３７％８６．３６％７７．２７％７７．２７％
（）匹配耗时ｔｓ０．１０９３７５０．１２５０．３１２５０．１２５０．１５６０．８５９３７５
４ 结束语
本文从全局考虑两个相匹配的点实体数据集具有相似的形态结构，从而将不确定的点与点之间的匹配关系转移到其对应泰森多边形的匹配。基于泰森多边形的点实体匹配算法相对现有的方法具有以下３点优势：①具有较高的查全率和查准率；②普适性强，不同于以往使用点缓冲区搜索候选目标时，缓冲区半径的设置依赖于地图比例尺，而本文算法能够适应不同比例尺的点实体匹配；③能够满足众源地理数据的匹配应用。不足之处是建立泰森多边形需要消耗一些时间，但随着计算机存储及计算能力的提高，构建泰森多边形时间与空间上的成本可忽略不计。
参考文献
［］１ａａｌｆｅｌｄＡ．ＡｕｔｏｍａｔｅｄＭａＣｏｎｆｌａｔｉｏｎ［Ｄ］．Ｗａｓｈｉｎ Ｓ －ｐｇ
，ｔｏｎＤＣ：ＵｎｉｖｅｒｓｉｔｏｆＭａｒｌａｎｄ１９９３：１１０． －ｙｙ
［］］龚健雅，张桥平．论地图数据库合并技术［２Ｊ． 李德仁，
（）：测绘科学，２００４，２９１１４．－
［］］李德仁，龚健雅．地图合并技术［测绘通报，３Ｊ． 张桥平，
（）：２００１７６８．－
［］地图数据库实体匹配与合并技术研究［武４Ｄ］． 张桥平．
汉：武汉大学，２００２：１１０．－
［］苏山舞．多空间数据库位置匹配方法及其应用５ 刘东琴，
［］（）：测绘科学，Ｊ．２００５，３０２７８８１．－
［］６ｅｅｒｉＣ，ＫａｎｚａＹ，ＳａｆｒａＥ，ｅｔａｌ．ＯｂｅｃｔＦｕｓｉｏｎｉｎＧｅｏ Ｂ －ｊ
／／ｒａｈｉｃＩｎｆｏｒｍａｔｉｏｎＳｓｔｅｍｓ［Ｃ］Ｐｒｏｃｅｅｄｉｎｓｏｆｔｈｅ ｇｐｙｇ，ＶＬＤＢＣｏｎｆｅｒｅｎｃｅ．Ｔｏｒｏｎｔｏ２００４：８１６８２７．３０ｔｈ －［］７ａｌｔｅｒＶ，ＦｒｉｔｓｃｈＤ．ＭａｔｃｈｉｎＳａｔｉａｌＤａｔａＳｅｔｓａＳｔａ Ｗ －ｇｐ
ｔｉｓｔｉｃａｌＡｒｏａｃｈ［Ｊ］．ＧｅｏｒａｈｉｃａｌＩｎｆｏｒｍａｔｉｏｎＳｃｉ －ｐｐｇｐ，（）：ｅｎｃｅ１９９９，１３５４４５４７３．－
［］邓愫愫，史文中．基于概率的地图实体匹配方８ 童小华，
］（）：法［测绘学报，Ｊ．２００７，３６２２１０２１７．－
［］，９ｏｂｂＭ Ａ，ＣｈｕｎＭＪＦｏｌｅＩＩＩＨ，ｅｔａｌ．ＡＲｕｌｅｂａｓｅｄＡ Ｃ － －ｇｙｐ
［］ｒｏａｃｈｆｏｒｔｈｅＣｏｎｆｌａｔｉｏｎｏｆＡｔｔｒｉｂｕｔｅｄＶｅｃｔｏｒＤａｔａＪ．Ｇｅｏ ｐ
，，（）：Ｉｎｆｏｒｍａｔｉｃｓ１９９８２１７３５．－
（下转第１２０页）
１２０测绘科学第４０卷
ＣｏｎｆｅｒｅｎｃｅｏｎＧｅｏＣｏｍｕｔａｔｉｏｎ．２００５：５５１５６２． －ｐ
，ＲｅｔｒｉｅｖａｌｏｎＣｏｍｏｓｉｔｅＫｅＪ］．ＡｃｔａＩｎｆｏｒｍａｔｉｃａ ｐｙ［（）：１９７４，４１１９．－
［，１２］ＭａＨｏｎｃｈａｏＷａｎＺｏｎｕｅ．ＤｉｓｔｒｉｂｕｔｅｄＤａｔａＯｒ －ｇｇｇｙ
ａｎｄＰａｒａｌｌｅｌＤａｔａＲｅｔｒｉｅｖａｌＭｅｔｈｏｄｓｆｏｒａｎｉｚａｔｉｏｎ ｇ
ＨｕｅＬａｓｅｒＳｃａｎｎｅｒＰｏｉｎｔＣｌｏｕｄｓ［Ｊ］．Ｃｏｍｕｔｅｒｓ＆ ｇｐ，（）：Ｇｅｏｓｃｉｅｎｃｅｓ２０１１，３７２１９３２０１．－
［］Ｗ，１３ａｎＪＳｈａｎＪ．ＳａｃｅＦｉｌｌｉｎＣｕｒｖｅＢａｓｅｄＰｏｉｎｔ ｇｐｇ
［／／ＣｌｏｕｄｓＩｎｄｅｘＣ］Ｐｒｏｃｅｅｄｉｎｓｏｆｔｈｅ８ｔｈＩｎｔｅｒｎａｔｉｏｎａｌ ｇ
［］Ｂ１４ｅｎｔｌＪＬ．ＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＢｉｎａｒＳｅａｒｃｈＴｒｅｅＵｓｅｄ ｙｙ
］ＡｓｓｏｃｉａｔｉｖｅＳｅａｒｃｈｉｎＪ．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅｆｏｒ ｇ［（）：ＡＣＭ，１９７５，１８９５０９５１７．－
［］林祥国，张继贤．机载Ｌ１５ｉＤＡＲ数据的多回波信息分析
］（）：及滤波方案［测绘科学，Ｊ．２０１３，３８３３２３４．－［］雷随．三维激光点云数据组织与可视化研究［武１６Ｍ］．
汉：武汉大学，２０１２．
ｏｉｎｔＲｅｓｅａｒｃｈｏｎｃｌｏｕｄｄａｔａｍａｎａｅｍｅｎｔｂａｓｅｄｏｎｓａｔｉａｌｉｎｄｅｘａｎｄｄａｔａｂａｓｅ ｐｇｐ
：，ｗ，ｂＬａｓｅｒｓｅｔｈａｓａｍａｓｓｉｖｅｏｆｄａｔａｈｉｃｈｎｏｔｏｎｌｉｎｃｒｅａｓｅｓｓｓｔｅｍｌｏａｄｕｔｏｉｎｔｕａｎｔｉｔＡｂｓｔｒａｃｔ ｙｙｐｑｙ ａｌｓｏｒｅａｔｌｒｅｄｕｃｅｓｔｈｅｆｏｌｌｏｗ－ｕｒｏｃｅｓｓｉｎｅｆｆｉｃｉｅｎｃａｓｗｅｌｌ．Ｃｏｎｓｉｄｅｒｉｎｔｈｅｄｉｆｆｉｃｕｌｔｏｆｍａｓｓｏｉｎｔ ｇｙｐｐｇｙｇｙｐ
，ｇｃｌｏｕｄｄａｔａｏｒａｎｉｚａｔｉｏｎａｎｄｍａｎａｅｍｅｎｔｒｉｄｉｎｄｅｘｏｆｏｉｎｔｃｌｏｕｄｄａｔａｂａｓｅｄｏｎｔｈｅｄｅｃｉｍａｌｌｉｎｅａｒ ｇｇｐ，ｐｕａｄｔｒｅｅｗａｓｉｎｔｈｉｓｃｌｏｕｄｄａｔａｗａｓｓｅｍｅｎｔｅｄａｎｄｅｎｃｏｄｅｄｂｍｅａｎｓｏｆｌｉｎｅａｒｒｏｏｓｅｄａｅｒｏｉｎｔ ｑｐｐｐｐｇｙ
，ｐｕａｄｔｒｅｅｏｉｎｔｂａｓｅｄｏｎｄｅｃｉｍａｌｓｓｔｅｍ，ｗｈｉｃｈｗｏｕｌｄｂｅｓｔｏｒｅｄｉｎＳＱＬＳｅｒｖｅｒ．Ｔｈｅｎｃｌｏｕｄｃｏｕｌｄｂｅ ｑｙ，ｃａｎｄｉｎｄｅｘｅｄｉｎｔｅｒｍｓｏｆＭｏｒｔｏｎｃｏｄｅｏｒｒｅｃｔａｎｕｌａｒｒｅｉｏｎｏｍｂｉｎｅｄｗｉｔｈｔｈｅａｄｖａｎｔａｅｓｏｆｂｏｔｈｂｌｏｃｋｅｄ ｇｇｇｏｉｎｔｒｏｓａｔｉａｌｉｎｄｅｘａｎｄｄａｔａｂａｓｅｔｏｍａｎａｅｃｌｏｕｄｅｆｆｉｃｉｅｎｔｌａｎｄｓａｆｅｌ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｅｄｔｈａｔｔｈｅ －ｐｐｐｇｙｙ ｏｓｅｄｒｏｂｌｅｍｏｉｎｔｍｅｔｈｏｄｉｄｅａｌｌｓｏｌｖｅｄｔｈｅｏｆｃｌｏｕｄｄａｔａｏｒａｎｉｚａｔｉｏｎａｎｄｍａｎａｅｍｅｎｔ． ｐｐｐｙｇｇ
：；ｓ；ｄ；ｖＫｅｗｏｒｄｓｏｉｎｔｃｌｏｕｄａｔｉａｌｉｎｄｅｘａｔａｂａｓｅｉｓｕａｌｉｚａｔｉｏｎ ｐｐｙ
１２１３，Ｌ，Ｔ，ＭＡ ＬＩＪｉａｎＥＩＳｕｉＩＡＮ ＺｈｉｈｕｉＹｕ－ｒｏｎ１．ＣｏｌｌｅｅｏｆＷａｔｅｒＣｏｎｓｅｒｖａｎｃａｎｄＥｎｖｉｒｏｎ － －ｇｙｇ（
，Ｚ，Ｚ；２ｍｅｎｔａｌＥｎｉｎｅｅｒｉｎｈｅｎｚｈｏｕＵｎｉｖｅｒｓｉｔｈｅｎｚｈｏｕ４５０００３，Ｃｈｉｎａ．ＳｃｈｏｏｌｏｆＲｅｍｏｔｅＳｅｎｓｉｎａｎｄ ｇｇｇｙｇｇ
，Ｗｕ，Ｗｕ；３，ＩｎｆｏｒｍａｔｉｏｎＥｎｉｎｅｅｒｉｎｈａｎＵｎｉｖｅｒｓｉｔｈａｎ４７０００３，Ｃｈｉｎａ．ＺｈｅｎｚｈｏｕＵｎｉｖｅｒｓｉｔＬｉｂｒａｒ ｇｇｙｇｙｙ
）Ｚｈｅｎｚｈｏｕ４５０００１，Ｃｈｉｎａ ｇ
檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿
（上接第１００页）
］吴建华．［顾及环境相似的多特征组合的实体匹配方法１０
［］（）：地理与地理信息科学，Ｊ．２０１０，２６４１６．－
［］吴建华，付仲良．数据更新中要素变化检测与匹配方法１１
［］（）：计算机应用，Ｊ．２００８，２８６１３８３１３８６．－
［］Ｆ，１２ｕＺｈｏｎｌｉａｎＷｕＪｉａｎｈｕａ．ＥｎｔｉｔＭａｔｃｈｉｎｉｎＶｅｃｔｏｒ ｇｇｙｇ
［／／，，ＤａｔａＣ］Ｔｈｅ２１ｓｔＩＳＰＲＳＣｏｎｆｅｒｅｎｃｅＢｅｉｉｎ２００８， ｊｇ３７，ＰａｒｔＢ４：１４６７１４７２． －
ＰｏｉｎｔｅｎｔｉｔｍａｔｃｈｉｎａｌｏｒｉｔｈｍｂａｓｅｄｏｎＴｈｉｅｓｓｅｎｏｌｏｎ ｙｇｇｐｙｇ
：ＡｒｏｂｌｅｍＡｂｓｔｒａｃｔｉｍｉｎａｔｔｈｅｔｈａｔｔｈｅｒｅａｒｅｓｏｍｅｉｎｃｏｎｓｉｓｔｅｎｔｄｅｖｉａｔｉｏｎｓｏｆｄｉｓｔａｎｃｅａｎｄｄｉｒｅｃｔｉｏｎ ｐｇ
，ｗｉｎｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓｆｒｏｍｃｒｏｗｄｓｏｕｒｃｉｎｄａｔａｈｉｃｈｍａｋｅｓｉｔｄｉｆｆｉｃｕｌｔｆｏｒｅｎｔｉｔｅｏｒａｈｉｃｅｘｉｓｔ ｐｇｇｙｇｇｐ
，ａｍａｔｃｈｉｎｍａｔｃｈｉｎａｌｏｒｉｔｈｍｏｆｅｎｔｉｔｉｅｓｂａｓｅｄｏｎＴｈｉｅｓｓｅｎｗａｓｉｎｔｈｉｓｏｉｎｔｏｌｏｎｒｏｏｓｅｄａ －ｇｇｇｐｐｙｇｐｐｐ ｅｒ．ＢｅｃａｕｓｅｏｌｏｎｓｏｉｎｔｏｆｔｈｅｈｉｈｅｒｃｏｒｒｅｓｏｎｄｉｎｒｅｌａｔｉｏｎｓｈｉｏｆｒｅｌａｔｅｄＴｈｉｅｓｓｅｎｏｆｔｈｅｍａｔｃｈｅｄｅｎ －ｐｐｙｇｐｇｐｇｐ ，ｔｉｔｉｅｓｔｈｅｕｎｃｅｒｔａｉｎｏｉｎｔｅｎｔｉｔｍａｔｃｈｉｎｗａｓｃｏｎｖｅｒｔｅｄｔｏｃｏｒｒｅｓｏｎｄｉｎＴｈｉｅｓｓｅｎｏｌｏｎｍａｔｃｈｉｎ ｐｙｇｐｇｐｙｇｇ ，，ａｗｉｔｈｈｉｈｅｒｓｉｍｉｌａｒｉｔ．ＦｉｒｓｔｌｔｈｅｃｏｎｔａｉｎｅｄｂｍｕｔｕａｌＴｈｉｅｓｓｅｎｗｅｒｅｃｏｕｎｔｅｄｎｄｏｉｎｔａｉｒｓｏｌｏｎｓ ｇｙｙｙｐｐｐｙｇ ｔｈｅｄｉｓｔａｎｃｅｔｈｒｅｓｈｏｌｄｒｅａｒｄｅｄａｓｏｎｅｃｏｎｄｉｔｉｏｎｏｆｃｏｎｆｉｒｍｉｎｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓｗａｓｃａｌｃｕｌａｔｅｄａｃｃｏｒｄ －ｇｇｐｇ
；Ｔ，ｉｎｔｏｄｉｓｔａｎｃｅｒｏｂａｂｉｌｉｔｄｉｓｔｒｉｂｕｔｉｏｎｏｆｏｉｎｔａｉｒｓｈｅｎｔｈｅｏｓｉｔｉｏｎｓｉｍｉｌａｒｉｔａｎｄｓｈａｅｓｉｍｉｌａｒｉｔｏｆ ｇｐｙｐｐｐｙｐｙ ；Ｌ，Ｔｈｉｅｓｓｅｎｏｌｏｎｓｗｅｒｅｒｅａｒｄｅｄａｓｔｈｅｓｅｃｏｎｄｃｏｎｄｉｔｉｏｎｏｆｕｄｉｎｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓａｓｔｌｔｈｏｓｅｅｎｔｉｔｉｅｓ ｐｙｇｇｊｇｇｐｇｙ ｔｈｅｈｉｈｅｓｔｓｉｍｉｌａｒｉｔｗｅｒｅｒｅａｒｄｅｄａｓｔｈｅｃｏｒｒｅｓｏｎｄｉｎｅｎｔｉｔｉｅｓ．Ｃｏｍａｒｉｎｗｉｔｈｅｘｉｓｔｉｎｍａｔｃｈｉｎａｌｏｗｉｔｈ －ｇｙｇｐｇｐｇｇｇｇ
，，ｐｒｉｔｈｍｓｔｈｅｒｅｓｕｌｔｓｓｈｏｗｅｄｔｈａｔｔｈｉｓａｌｏｒｉｔｈｍｈａｄｈｉｈｅｒｒｅｃａｌｌｒａｔｅａｎｄｕｎｉｖｅｒｓａｌｉｔ．ｒｅｃｉｓｉｏｎ ｇｇｙ
：；ｅ；ｄ；ＴＫｅｗｏｒｄｓｓｈａｅｓｉｍｉｌａｒｉｔｎｔｉｔｍａｔｃｈｉｎａｔａｆｕｓｉｏｎｈｉｅｓｓｅｎｏｌｏｎ；ｃｒｏｗｄｓｏｕｒｃｉｎｅｏ －ｐｙｙｇｐｙｇｇｇｙ ｒａｈｉｃｄａｔａ ｇｐ
，ａｎＷＵ Ｊｉａｎ－ｈｕａ，ＷＡＮ ＹａｎＳｃｈｏｏｌｏｆＧｅｏｒａｈａｎｄＥｎｖｉｒｏｎｍｅｎｔＪｉａｎｘｉＮｏｒｍａｌＵｎｉｖｅｒｓｉ －ｇｐｙｇｙｇ（ｇ－ ／，ＮｔＫｅＬａｂｏｆＰｏａｎＬａｋｅＷｅｔｌａｎｄａｎｄＷａｔｅｒｓｈｅｄＲｅｓｅａｒｃｈ，ＭｉｎｉｓｔｒｏｆＥｄｕｃａｔｉｏｎａｎｃｈａｎ３３００２２， ｙｙｙｇｙｇ
）Ｃｈｉｎａ