一种复杂矢量面状实体的匹配方法

张家新，韩保民 ，逯跃锋，颜怀成

(山东理工大学 建筑工程学院，山东 淄博 255049)

一种复杂矢量面状实体的匹配方法

张家新，韩保民 ，逯跃锋，颜怀成

(山东理工大学 建筑工程学院，山东 淄博 255049)

针对复杂面状实体要素匹配问题，采用一种公共边对象化的Douglas-Peucker改进算法对面实体形状进行简化，然后将简化后的面实体所提取的节点以及基于面实体周长的均匀采样点作为面实体轮廓特征点.利用提取的轮廓特征点，采取一种极坐标方法对面实体进行形状描述，并分别计算出同名实体在节点和均匀采样点处的距离差异，将获取两者综合差异作为最终匹配标准.通过实验对比分析可知，该方法能有效解决复杂面状实体匹配速度和准确率问题.

矢量匹配；Douglas-Peucker算法；极坐标；轮廓特征点；匹配距离

在地理信息领域中，空间数据集成更新是维持数据库完整性和现势性的基础，而矢量匹配是其关键技术. 面状实体要素匹配是矢量要素匹配的重、难点问题，现实应用中通常采用面状实体之间几何形状相似程度来进行匹配，即几何匹配技术[1]，其难点就是在于如何对面状实体准确描述以及实体之间的匹配距离的量度. 针对面实体之间的几何相似度度量问题，国内外学者提出了很多解决方法.文献[2]中，通过求取两个面实体的重叠面积比来判别其匹配的可能性，由于需要重复计算面实体重叠面，运算量较大且容易出现误匹配现象.文献[3]提出一种基于面实体形状中心距离差异的匹配方法，对要素节点位置依赖较大，精度不高.文献[4]通过一种基于拱高半径的傅里叶形状描述子进行面实体形状描述，采用综合相似度进行要素匹配，较好的对面实体进行描述，但该方法涉及大量运算，耗时较长.文献[5]提出基于重心射线的实体描述方法来进行面实体匹配，适用于简单面实体匹配，对复杂面实体之间匹配精度不高.

现实生产中，面状实体要素形状复杂程度不一，而现有匹配方法缺乏对形状较为复杂的面实体要素的匹配研究，本文在综合分析现有匹配方法对复杂面状实体匹配不足的基础上，提出一种基于轮廓特征点极坐标的面实体匹配方法，为了兼顾匹配速度和精度，采用一种公共边对象化的Douglas-Peucker(DP)算法对复杂面装实体进行形状简化操作，然后通过提出面实体质心和轮廓特征点的极坐标描述方法进行匹配分析. 通过将本文方法同文献中不同方法的实验比较分析可得，本文提出的方法能够较好的解决复杂面实体匹配问题.

1 复杂面实体形状匹配方法

1.1 基于改进的Douglas-Peucker算法的形状简化

DP算法的基本思路：将面实体要素用一系列点P0，P1，…，Pn(实体的节点)组成的集合表示. 设定简化距离阈值为Dthreshold，求出与P0距离最大的节点Pk，连接P0和Pk。计算弧段P0-Pn上的节点到直线P0-Pn的距离Di，并选出其中距离最大的点Pj，如果Di大于阈值Dthreshold，保留该点，反之删除. 连接节点P0-Pj和Pk-Pj，将原弧段分成两段，运用以上同样方法对位于它们之间的节点进行删减，采用递归的方法，重复此操作，直至所有节点满足算法要求为止[6-7]. 如图1所示.

图1 DP算法形状简化示意图

DP算法能成功的对面实体形状实施简化，但由算法对实体简化原理可知，设定的距离阈值Dthreshold对实体的简化精度产生直接影响，同时由闭合曲线表示的复杂多边形可能存在相邻等拓扑关系，在应用DP算法对存在拓扑关系的复杂多边形进行形状简化时，可能产生如图2(b)所示的部分“裂缝”现象。假设两个相邻的多边形A1和A2，如图2(a)所示：设定距离阈值为Dthreshold对多边形A1选择节点2和节点6作为起始点和终点，对多边形A2选择节点18和节点12作为起始点和终点，当对多边形A1图形简化时，公共弧段上节点9距离线段L2-6的距离小于Dthreshold被剔除，节点8距离线段L2-6大于距离阈值被保留，而对A2多边形简化时，节点9距离线段L18-12的距离大于Dthreshold被保留，节点8距离线段L18-12小于距离阈值被剔除，结果导致简化后的两多边形公共边处出现“裂缝”(如图2(b)所示).

(a)DP前两相邻多边形 (b) DP后两相邻多边形图2 DP算法的缺陷

由于“裂缝”现象的存在，在对复杂面实体匹配过程中可能导致匹配错误，需要对DP算法进行改进. 因此，为了解决上述的“裂缝”问题，本文采用文献[8]提出的公共边对象化的DP改进算法实现.

算法基本思路：首先采用面向对象编程技术，创建公共边类和最小外接矩形方法，判断待匹配面实体之间是否存在公共边，若不存在，直接采用DP算法将该待匹配面实体进行简化；若存在，则需判断此公共边是否为已经提取. 若此公共边为首次提取，则用创建的公共边类将此公共边进行实例化(对象化)并存入动态数组中，然后分别对公共边和非公共边部分采用DP算法进行简化；否则，只简化非公共边部分，并直接将先前已简化的公共边替换此公共边. 如此循环直至所有要素简化完成. 该算法有效避免了因公共边重复简化所引起的“裂缝”现象，提高简化效率.

1.2 基于极坐标的形状描述

在多边形的形状描述中，本文采用一种基于极坐标的形状描述方法. 首先对采用改进的DP算法简化后的面实体提取节点和均匀采样点作为面实体的轮廓特征点，然后分别由面实体的几何中心(质心)向特征点引向量得到特征向量集；最后分别统计节点向量集的距离ρ和方向α得到极坐标(ρ，α)，(图3(a))和均匀采样点的向量集的距离ρ和方向β得到极坐标(ρ，β)(图3(b))，根据极坐标来描述目标形状.

1.2.1 轮廓特征点的提取

面实体节点最能表述实体轮廓，提取面实体节点，并单独保存至数组，同时对面实体轮廓采用均匀插值的方式得到均匀采样点，并单独保存至数组。提取均匀采样点：首先计算面实体周长L，选取实体上节点坐标pi(xi,yi)中yi值最大的节点，记为p0(x0,y0)，作为均匀采样的起始点，根据面实体周长L，设定采样距离阈值，对面实体轮廓等距离采样，提取采样点.

1.2.2 特征向量集和特征点极坐标表示

为了计算特征向量集，需要计算面实体的几何中心O(本文采用质心)，其定义如下：

(1)

其中(xi,yi)为面实体轮廓特征点坐标，m为特征点的个数.

特征向量定义为由质心向特征点所引的向量，所有特征向量的集合成为特征向量集[9]. 选取质心为极坐标原点，X轴方向为极坐标正方向，逆时针方向为角度的正方向，将面实体上所有特征点用极坐标方式表示.

(a)节点极坐标表示 (b) 采样点极坐标表示 (c) 面实体相似度度量图3 面实体极坐标表示

1.2.3 面实体匹配方法

面实体之间的相似度用待匹配实体特征点与相应候选匹配实体的轮廓交点之间的距离差异量度[10]，如图3(c)所示，基于面实体A和面实体B形状匹配，从面实体A中心点(质心)出发连接轮廓特征点PAi，旋转角为θi，并与实体B轮廓边界相交，交点为PBi，计算PAi和PBi与原点的距离分别为DA(θi)=ρAi和DB(θi)=ρBi，将面实体A和B在θi方向上的距离差异DA-B(θi)=ρAi-ρBi作为相似性特征，则它们在θi方向上的相似度为：

(2)

面实体轮廓由一系列的轮廓特征点表示(节点和均匀采样点)，通过统计方法分别计算实体A和B在节点和均匀采样点的相识度：

(3)

(4)

则面实体A和B综合相似度定义如下：

(5)

公式(5)中ω为节点描述实体形状的权值，面实体形状描述过程中，由于节点位置更能表现实体轮廓信息，ω取值应当满足ω值大于0.5(本文实验中ω取值为0.65). 由公式(5)可得，Sim(A,B)值越接近于1，表明面实体之间相似度越高.

2 实验与分析

2.1 面实体形状简化与分析

采用上述改进的DP算法对图4(a)数据进行形状简化实验，设定简化阈值Dthreshold分别为5m、10m和20m，其简化效果图如图4所示.

通过采用提取面实体公共边对象化的方法对简化算法改进之后，很好的解决了常规DP算法在进行形状简化时产生的“裂缝”现象. 利用本文提出的基于极坐标的形状描述方法，对比原要素与简化阈值Dthreshold分别为5m、10m和20m的简化后要素的面积匹配和周长匹配距离(如表1所示)，并将简化后的匹配阈值设定为0.85，可以看出，通过形状简化，面要素节点数大幅度减少，要素的面积和周长在5m和10m的简化阈值下可以满足匹配要求.

图4 形状简化效果图

表1 形状简化实验效果图

匹配要素编号节点简化后节点采样点周长/m周长匹配面积/m2面积匹配原要素A1238238752327.7831.0000014167.7321.00000A2274274662071.2821.0000011683.6821.000005m简化A1238103732163.3290.9295214301.8210.99063A2274117641896.6380.9154911769.2350.9926910m简化A123872692028.5780.8715014037.2900.99082A227478611768.2660.8536911551.7230.9887020m简化A123848631945.0520.8358413624.6570.96167A227443551687.2130.8145811202.5330.95883

2.2 面实体形状匹配与分析

2.2.1 形状匹配

本文以山东某地区2006年与2012年的图斑(如图5所示)要素进行形状匹配，采用ArcGIS Engine10.1与VS.Net 2010为开发平台，进行形状匹配实验(表2). 为了兼顾匹配速度和正确率，本文将改进后的DP 算法简化阈值Dthreshold设为8m，特征采样点定义为从起始点(节点中yi值最大的点)，沿面实体周长顺时针方向每30m插入一个采样点，并将实体匹配阈值设置为0.85.

为了更直观地体现匹配效果，将本文方法与文献[2]和文献[3]的方法在匹配时间和效率上进行比较，比较结果见表3.

图5 匹配实例

表2 要素匹配

算法类型要素编号节点数简化后节点采样点匹配度算法时间/s是否匹配本文算法A11与A21B13与B25C3与D17A11∶67213488A21∶65811889B13∶726107101B25∶68411293C3∶4607354D17∶47180540.982010.536匹配0.725720.654不匹配0.974290.347匹配

表3 匹配算法对比

算法类型要素编号匹配度算法时间/s是否匹配文献[2]算法A11与A210.987531.092匹配B13与B250.854071.120匹配C3与D170.988600.608匹配文献[3]算法A11与A210.908550.391匹配B13与B250.637220.419不匹配C3与D170.880570.248匹配

2.2.2 分析

文献[2]算法通过计算面实体形状的重叠面积来描述要素相似性，由于重复计算面要素之间的面积重叠度，计算量较大，耗时较多，从表2和表3可以看出，本文算法在匹配速度上明显优于文献[2]算法，并且当两面要素形状接近时，文献[2]算法会出现错误匹配现象，如本文中的B13和B25要素匹配. 文献[3]算法通过计算比较几何中心的差异来描述形状之间的相似度，模型描述相对简单，计算量较小，算法在匹配速度上明显占优，由于此算法中要素几何中心对节点坐标依赖性较大，节点数和节点位置的变化对几何中心的坐标都会产生较大的影响，比较表2和表3中算法的匹配度，算法[3]的匹配精度明显较低，如果本文中提高设定匹配阈值至0.90，文献[3]算法就会出现错误匹配情况. 综合比较，本文算法在匹配速度和准确率上都具有优势.

3 结束语

面状实体匹配是矢量要素匹配中重要的组成部分，其匹配效果直接影响到数据集成和更新的效果,具有相邻等拓扑关系的复杂面实体匹配是矢量匹配的重点和难点问题[10]. 本文采用一种公共边对象化的DP算法对复杂面实体进行形状简化，较好的解决了常规DP算法在形状简化时产生的“裂缝”现象，提升了匹配速度，并提出一种基于极坐标的实体轮廓特征点的形状相似度度量方法，较好的解决了匹配的准确率问题. 最后，通过将本文方法与不同匹配方法的比较分析可得，本文方法在匹配的速度和准确率上都具优势，说明本文的方法是可行的.

[1]张桥平,李德仁,龚健雅.城市地图数据库面实体匹配技术[J].遥感学报,2004,8(02): 107-112.

[2]吴建华,傅仲良.数据更新中要素变化检测与匹配方法[J].计算机应用,2008(06):1612-1615.

[3]郝燕玲,唐文静,赵玉新,等.基于空间相似性的面实体匹配算法研究[J].测绘学报,2008(04):501-506.

[4]付仲良,逯跃锋.一种基于拱高半径复变函数的面实体匹配算法[J].计算机应用研究, 2012(09):3303-3306.

[5]郑宇志,张青年. 基于拓扑及空间相似性的面实体匹配方法研究[J]. 测绘科学技术学报, 2013,30(5): 510-514.

[6]DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[7]YU J, CHEN G, ZHANG X, et al. An improved Douglas-Peucker algorithm aimed at simplifying natural shoreline into direction-line[C]//Geoinformatics (GEOINFORMATICS), 2013 21st International Conference on. IEEE, 2013:1-5.

[8]谢亦才,李岩. Douglas-Peucker算法在无拓扑矢量数据压缩中的改进[J].计算机工程与应用,2009(32):189-192.

[9]CERRI A, FABIO B D. Comparing shapes through multi-scale approximations of the matching distance[J]. Computer Vision & Image Understanding, 2014, 121(121): 43-56.

[10]ALT H, BEHRENDS B, BLÖMER J. Approximate matching of polygonal shapes[J]. Annals of Mathematics and Artificial Intelligence, 1995, 13(3-4): 251-265.

(编辑：姚佳良)

A matching method of complex vector polygon elements

ZHANG Jia-xin, HAN Bao-min, LU Yue-feng, YAN Huai-cheng

(School of Civil and Architectural Engineering,Shandong University of Technology, Zibo 255049, China)

Aiming at the problem of the method of complex vector polygon matching, a named common boundary objected Douglas-Peucker improved algorithm is adopted to compress the polygon elements, then extracted feature points of elements profile which consist of the nodes of polygon and uniform sampling points based on the polygon perimeter. Polar coordinates is exploited to shape description through features points, and computed the distance difference of nodes and sampling points of elements, respectively, then obtained the comprehensive difference as the final matching standards. Experiments shows that the method effectively improved the matching speed and accuracy of the complex vector polygon elements.

vector matching; Douglas-Peucker algorithm; polar coordinates; feature points; matching distance

2016-12-15

张家新，男，935290034@qq.com

1672-6197(2017)05-0065-05

P228.4

A