基于重叠度和匹配距离的面实体匹配方法

基于重叠度和匹配距离的面实体匹配方法 赵宝贵～李大军 ,东华理工学院测量系～江西 抚州 344000 , 摘要:为了充分利用已有的地图数据～减少数据重复采集的高额费用～地图合并技术已成为当前 研究的一个重要课题～其中面实体的匹配是地图合并的关键技术之一。在现有匹配方法不足的基 础上～本文将计算机视觉、模式识别中的多边形形状匹配的思想引入到地图数据面实体匹配当中～并 对计算匹配距离的算法进行了改进～提出一种新的面实体匹配方法。实验结果明该方法算法简单、 容易实现～对于相同比例尺地形图面实体的匹配具有较高的效率。 关键词:地图合并;重叠度;匹配距离;面实体匹配; Entity Matching Method Based on Overlap Degree and Matching Distance ZHAO Bao-gui, LI Da-jun (Dept. of Surveying and Mapping, East China Institute of Technology, Fuzhou Jiangxi 344000,China) Abstract: In order to use map data fully and decrease the expense of repeating collection, map conflation has become an important problem for present. The area entity matching is one of the critical technologies in map conflation. Based on the deficiency analysis on the existing matching method, the idea of shape matching in computer vision and pattern recognition was introduced into map conflation. The algorithm of matching distance computation was improved and a new area entity matching method was presented. Experimental results indicate that the method has simple algorithm, is realized easily and has high efficiency for area entity matching of maps with the same scale. Key words: Map conflation; Overlap degree; Matching distance; Area entity matching 测绘信息网 1 引言 地理信息系统构建费用中，硬件、软件和数据的比通常为1:2:7，可见数据在地理信息系统中有着 [1]十分重要的地位。尽管GIS的数据采集费时费力，但实际情况通常是现实世界同一地物的数据还是被不同部门重复的采集，这样就形成了同一地物的多源地图数据。为了充分利用已有信息，减少数据采集的高额费用，GIS应用部门经常需要将这些不同来源的地图数据合并在一起使用，这就产生了地图合并(Map [2]Conflation)技术。地图数据的合并包括点、线、面实体的合并，而同名实体匹配的成功与否将直接决定后续合并工作的成败。在地图数据中存在着大量的面状实体，因此面实体的匹配技术研究成为地图合并的关键技术。 在现有的度量面实体相似度指标中，单纯的距离相似度、形状相似度和方向相似度都不足以确定两个面实体是否是同名实体。文献[3]利用基于模糊拓扑关系进行同名面实体匹配。该方法中形态距离的计算非常复杂，而且没有一个用于相似度定量描述的指标。文献[4,6]利用多边形间的匹配距离确定其是否匹配，这种方法在计算匹配距离时，起始点的随机选择使得计算的时间复杂度很高，导致匹配效率不高。文献[7]探讨了基于位置的区域相似度计算，理论上不失为一种较好的方法，但计算中将涉及大量的求交运算，计算过程复杂。鉴于上述方法存在的不足，本文提出了一种新的面实体匹配方法。其基本的思想是:在面实体匹配时不仅利用实体重叠度信息，还利用实体间的匹配距离得到实体的综合相似度指标进行面实体匹配。该方法计算过程简单、容易实现，能较好地应用于相同比例尺地图面实体的匹配。 2 面实体的匹配距离 2.1 面实体正切空间表示 如图1所示，给定某一面实体，依公式(1)和(2)可求得各条边的边长和各顶点处的偏转角(设右偏为正，左偏为负)，具体计算公式如下 22(x,x)，(y,y)L= (1) 12121 ,,,,,11201pppp (2) y,yy,y1021,arctan(),arctan()x,xx,x2110 ,,P0P1P1P2其中:L为线段PP的边长，，分别为直线PP, PP的方位角。在计算偏转角时要顾1121201 及方位角的范围及偏转角的偏转方向。可以根据顶点的凸凹性判断其左偏还是右偏(顺时针前进，凸点为右偏，凹点为左偏)。如将所有顶点处的偏转角相加，则其和应为2π，可用于计算检核。正切空间表示具 knLi/Li,,11体过程如下:(1)用横轴表示从起点(如图1中P)到各点的边长之和除以整个周长()的归1 一化距离。(2)纵轴表示从起始点到该点的所有偏转角之和(?θ)。对于任意闭合多边形终点P处的纵坐n标应为2π。显然正切空间表示为一分段函数，且正切空间表示具有平移、旋转和缩放不变性。图2为图1所表示的面实体的正切空间表示。 测绘信息网 图1 顶点处的偏转角 图2 多边形正切空间表示 2.2 匹配距离 ,(s),(s),AB设A，B两个待匹配面实体化为正切空间表示后的表达式为，。S表示横轴坐标，表示纵轴坐标，则匹配距离为d(A, B); 12 (3) d(A,B),|,(s),,(s)|dsAB,0 3 基于重叠度和匹配距离的面实体匹配方法 3.1 已有面实体匹配方法分析 文献[3]先利用匹配了的同名点求出两幅图的相对点位中误差σ再计算隶属度θ，而同名点的匹配中本来就存在着误匹配，点位中误差的计算存在着不确定性，且隶属度计算过程也非常复杂。文献[4]在计算匹配距离时根据两个多边形的最大凸弧段数m, n，将各凸弧段起点分别作为起始点，计算m×n次，求出最小值min(d(A, B))作为两个多边形的匹配距离。在具有大量面实体的地图中，如果对于每一对待匹配实体都进行这样的计算，其耗费的计算时间是相当可观的。文献[7]计算实体Α,Β重叠度(|A?B|/|A?B|,|A?B|/max(|A|,|B|),|A?B|/(|A|+|B|))作为衡量实体的相似度指标，但计算中将涉及大量的求交运算，计算过程复杂。 3.2 基于重叠度和匹配距离的面实体匹配方法的基本思想 (1)为了减小搜索范围，提高匹配效率，首先利用面实体重叠度大小确定面实体的候选匹配实体集。采用重叠度overlap(A, B)计算为 overlaparea(A,B)overlap(A,B),area(A) (4) 测绘信息网 显然若重叠度大于一定的阈值(如:0.6)，则面实体B有可能和面实体A相匹配。 (2)将待匹配面实体分别用正切空间表示，计算面实体的匹配距离。在计算匹配距离时，本文提出先找出待匹配面实体中距离在一定阈值内，其前后连线方位角相差最小的同名点作为起始点进行计算, 提高了计算效率同时确保了求出的面实体匹配距离最小。 (3)考虑到重叠度与匹配距离指标各自优点，笔者采用了一种综合相似度指标sim(A，B)，该指标定义为 (1,overlap(A,B))，d(A,B)sim(A,B),2 (5) 显然对于待匹配的面实体如果重叠度越大、匹配距离越小，则实体越有可能是相匹配的。采用上述相似度指标进行面实体匹配不仅考虑了面实体的重叠度信息，还利用了其形状相似度，匹配结果符合视觉效果。 3.3 基于重叠度和匹配距离的面实体匹配基本步骤 面实体匹配的基本步骤为: (1)利用重叠度信息确定面实体的候选匹配实体集。 (2)根据计算出的实体面积的正负性判断其顶点存储方式是顺时针还是逆时针，将实体顶点坐标统一用顺时针方向存储。 (3)计算面实体各边长及各顶点处两端连线的方位角及偏转角。并将其与坐标数据链成循环链表。 (4)确定匹配距离计算中的起始点。将(2)中两个循环链表的结点信息相互比较，找出给定的距离阈值内与其相连接的方向线的方位角差异最小的结点，作为待匹配面实体的同名点。 (5)从(4)中同名点开始，将待匹配面实体分别用正切空间表示，并计算实体的匹配距离。同名点的选择能够保证同名面实体间的匹配距离最小，而且计算时间效率高。 (6)结合重叠度和匹配距离计算出综合相似度指标。用综合相似度指标作为实体是否匹配的衡量依据进行面实体匹配。 4 匹配结果及分析 已有方法根据模糊拓扑关系进行匹配时矢量数据面实体间形态距离的计算困难，而且模糊拓扑关系不适合对相似度的定量比较。本文将计算机模式识别中形状匹配的思想引入到矢量地图同名面实体的匹配中，结合重叠度与匹配距离各自的优点，提出了一种新的用于同名面实体匹配的相似度指标。利用该指标进行同名面实体的匹配过程中能够得到面实体的重叠度、形状上的相似程度信息及相似度值。以下就同名面实体与非同名面实体的目视判读效果与匹配过程中得到的重叠度、匹配距离及相似度值进行对比分析。下表1所示为图3同名面实体的重叠度、匹配距离及相似度值。 测绘信息网 图3 同名面实体匹配结果 表1同名面实体的重叠度、匹配距离及相似度值 值 类别 Id 重叠度 匹配距离 相似度值 1025 0.930663 0.080717 0.075027 23 1030 0.805138 0.444548 0.319705 7 1023 0.885146 0.397307 0.256081 21 1024 0.936889 0.154284 0.108698 22 通过目视判读可知图3中面实体对的重叠度都较大，而且形状都非常相似(匹配距离值很小)，它们应 该为同名面实体(相似度值很小)。对照表1中列出的重叠度、匹配距离及相似度值完全符合目视判读的效 果。 而对于非同名面实体的匹配效果与得到的重叠度、匹配距离及相似度值的比较见下图4与表2。 表2非同名面实体的重叠度、匹配距离及相似度值 值 类别 Id 重叠度 匹配距离 相似度值 1026 0.383229 1.443108 1.029939 15 1026 0.479278 0.928207 0.724464 19 1029 0.172195 1.177460 1.002632 15 1029 0.026698 0.921536 0.947419 19 1027 0.654817 1.483296 0.919240 16 1021 0.727714 1.753633 1.012959 17 测绘信息网 1014 0.900556 2.421684 1.260564 18 图4 非同名面实体匹配结果 对照图4可知id为1026的实体与15、19，1029与15、19，1021与17，1014与18这些实体对，由于测图精度、综合程度的不同或者地物的变化等因素造成的面状实体的重叠度较小，形状差异较大的面实体(匹配距离较大)，匹配得到的相似度值都较大(上图4所示面实体)，我们不能认为它们是同名面实体。对照表2可以看出上述分析可以通过表中数据体现出来。 通过以上分析可知本文提出的相似度指标能够区分出同名面实体、非同名面实体之间的差异，运用于同名面实体匹配有其合理性与可行性。 5 结束语 本文将计算机视觉、模式识别中的多边形形状匹配的思想引入到地图数据的面实体匹配当中，提出了一种新的面实体匹配方法。该方法不仅利用了面实体的重叠度信息，还考虑到它们的形状相似度，采用了一种新的综合相似度指标进行面实体匹配。实验结果表明:利用综合相似度指标进行匹配较为合理，所提的面实体匹配方法具有较高的准确率，其结果也符合视觉效果。另外该方法算法简单、容易实现。当然，所提方法也存在一些不足，如对非一对一匹配时出现了漏匹配，面实体重叠度及综合相似度阈值的取值还受到人为因素的影响等，这些都是下一步需要认真解决的问题。 [参考文献] [1] 龚健雅.地理信息系统基础[M],北京:科学出版社～2001.9 [2] 张桥平,李德仁,龚健雅,地图合并技术[J] ,测绘通报,2001,7: 6-8. [3] 张桥平.地图数据库实体匹配与合并技术研究[D],博士学位,武汉大学,2002.5:72-94. [4] 谢 萍,马小勇,张宪民等.一种快速的复杂多边形匹配算法[J].计算机工程,2003,29,16,:177-181. [5] Arkin M, Chew L P, Huttenlocher D P, et al. An Efficiently Computable Metric for Comparing Polygonal Shapes[C]. IEEE Trans. Pattern Analysis and Machine Intelligence, 1991, 13: 206-209. [6] Latecki L J, Lakamper R. Shape Similarity Measure Based on Correspondence of Visual Parts[C]. IEEE Trans. Pattern Analysis and Machine Intelligence, 2002, 22: 1185-1190. 测绘信息网 [7] Stephan Winter～Location-based Similarity Measures of Regions. ,2006-12-20,[J/OL] [8] Saalfeld A. Conflation: Automated Map Conflation [J]. International Journal of Geographical Information Systems, 1998, 2(3):217-228. 作者简介: 赵宝贵,1978-,～男～江苏泗阳人～助教～硕士研究生～主要研究领域为GIS理论与应用。李大军,1965-,～ 男～湖南澧县人～博士～教授～主要研究领域为GIS空间数据不确定性理论与应用。