多源居民地面要素的免阈值自动稳健匹配方法

摘要

本发明涉及多源居民地面要素的免阈值自动稳健匹配方法，有效解决既能够准确获取同名面要素之间存在的1:1匹配关系、1:N匹配关系和M:N匹配关系，又不要求两组待匹配面要素在位置上准确靠近，允许存在较大的位置偏差，甚至是非一致性的位置偏差的问题，方法是，用计算机分别读取两组待匹配居民地数据，一组居民地为参考面要素组合，记为R，另一组居民地为目标面要素组合，记为T；生成候选匹配对；判定同名面要素匹配关系；匹配结果的冲突探测和消除，发明方法稳定可靠，易操作使用，不要求两组待匹配面要素在位置上准确靠近，允许存在较大的位置偏差，无须设置阈值，减少预处理的工作量，有效用于矢量地图合并、地图更新和变化检测。

说明书

技术领域

本发明涉及地图，主要指地图的数据集成和生产，特别是指一种多源居民地面要素的免阈值自动稳健匹配方法。

背景技术

伴随着空间数据采集技术的快速发展，人们已经积累了丰富的空间数据，即便是覆盖相同区域，不同部门出于不同需要也反复采集了各具特色的数据。例如，房产部门和测绘部门都采集了居民地数据，但是房产部门更看重居民地数据的属性信息(如权属、面积等)，而测绘部门更看重数据的精度，如果能够将不同部门的数据进行有效集成，就能够集各种版本空间数据的优势于一身，从而可以节省大量的外业重复开支。为了能够对多源空间数据进行准确的集成、复用和共享，其核心和前提步骤就是要能够实现不同来源空间数据同名要素的自动识别和匹配。为此，本发明特别针对矢量地图中不同来源的面要素数据(主要以居民地面要素为例)开展数据匹配的发明工作。

在各种面要素匹配算法中，常见的是通过降维处理来简化面要素匹配问题的复杂性，通过比较面要素对应特征点或者质心之间的距离、质心与面要素的位置关系来确定面要素的匹配关系；或者提取面要素的轮廓，通过计算轮廓线在距离上的邻近程度来确定匹配关系，常采用的距离测度有Fréchet距离、Hausdorff距离等，或是计算轮廓线在形状上的相似程度来确定匹配关系，其相似性测度如形调函数，傅里叶描述子等，少数算法则提取面要素内部的骨架线，通过对比骨架线的形状相似度来确定面要素的匹配关系。也有一些算法则利用面要素的内部区域来进行匹配，常见的特征指标是计算面要素之间的重叠面积，待匹配的两个面要素其重叠面积占各自面积的比值越大，则它们是同名要素的可能性也就越大。当然，一些匹配算法并不单独使用以上某一个特征指标，而是会将各种指标进行联合使用，但其难点在于权值的准确确定上。还有一些算法在对面要素匹配过程中，不但会考虑待匹配面要素的匹配相似程度，还会考虑相邻其他面要素的匹配情况，进一步提高了匹配算法适应复杂情况的能力。

尽管在面要素匹配问题上已经取得丰硕的研究进展，但现有算法对一些难点问题仍没有较好解决，其一是，难以准确获取同名面要素之间存在的M:N匹配关系；例如那些降维算法和基于轮廓线的方法，由于缺乏对面要素内部区域的利用，当存在M:N匹配关系时，获取组合面要素整体上的轮廓线将变得费时且困难，这些算法都无法对复杂的M:N匹配关系进行自动处理，只能处理1:N，甚至是1:1的匹配情况。其二是，要求同名面要素在位置上尽可能接 近，不少算法常使用距离作为匹配阈值；一些算法虽然能够获得同名面要素之间的M:N匹配关系，但该类方法有一个重要前提，即待匹配的两组面要素之间已经在位置上较为接近，或者明确符合地图制图规范，然而在实践中，由于数据来源的广泛性和复杂性，待匹配的面要素之间可能存在着一致性的位置偏差，即有些地方普遍偏差大，而有些地方又偏差小。即使通过整体性的坐标系统纠正，两组面要素之间仍不能精确配准，在这些情况下这些算法也将难以奏效，因此，其改进和创新势在必行。

发明内容

针对上述情况，为克服现有技术之缺陷，本发明之目的就是提供一种多源居民地面要素的免阈值自动稳健匹配方法，可有效解决既能够准确获取同名面要素之间存在的1:1匹配关系、1:N匹配关系和M:N匹配关系，又不要求两组待匹配面要素在位置上准确靠近，允许存在较大的位置偏差，甚至是非一致性的位置偏差的问题。

本发明解决的技术方案是，包括以下步骤：

步骤一、数据获取：

用计算机分别读取两组待匹配居民地数据，一组居民地为参考面要素组合，记为R，另一组居民地为目标面要素组合，记为T；

步骤二、生成候选匹配对：

对于待匹配的参考面要素组合R和目标面要素组合T，通过空间位置相交关系的交迭判断，依次从参考面要素组合和目标面要素组合中选择候选匹配面要素组合，并生成候选匹配对，候选匹配对包含1:1、1:N、M:1和M:N等同名面要素之间可能存在的各种匹配关系；

步骤三、同名面要素匹配关系的判定：

采用双向计算面要素的匹配相似度来确定同名面要素的匹配关系，即对于参考面要素组合R和目标面要素组合T而言，当根据所计算出的匹配相似度能够互相为对方的最佳匹配面要素组合，而二者匹配对应关系成立；

为了有效处理各种复杂匹配对应关系，所述的匹配相似度其计算思路在于通过衡量不同来源面要素之间相互重叠的程度来判定面要素之间的匹配程度；为了确保即使在同名面要素具有较大位置偏差时，依然进行有效匹配，则首先提取参考面要素组合的包络矩形及相应特征点的全局形状特征，自动获取同名面要素上同名特征点的匹配对应关系，将参考面要素组合R进行位置偏移，使得两组待匹配面要素组合在位置上能够进一步配准，继而再通过衡量重叠程度来评判参考面要素组合R与目标面要素组合T的匹配程度；

分别从两个方向进行面要素匹配相似度的计算，以获取匹配对，方法是，先以参考面要 素组合R为基准，根据所计算出的匹配相似度，从目标面要素找到最佳匹配目标面要素组合T，而后再以目标面要素组合T为基准，根据所计算出的匹配相似度，从参考面要素组合中找到最佳匹配参考面要素组合，当该最佳匹配面要素组合为参考面要素组合R时，则参考面要素组合R和目标面要素组合T形成一组互为最佳匹配面要素组合；

所述的匹配相似度的计算方法为：通过利用不同来源面要素之间相互重叠的程度来衡量面要素的匹配程度，设参考面要素组合R的面积为A_r，目标面要素组合T的面积为A_t，参考面要素组合R与目标面要素组合T的重叠面积为A_o，则重叠相似度Sim为：

$\mathrm{Sim}=\frac{A_o{A}_o}{A_r{A}_t}---\left(1\right)$

通过计算重叠相似度来判定候选匹配对之间的匹配程度，提取参考面要素组合的包络矩形及相应特征点的全局形状特征，利用同名面要素上同名特征点的匹配对应关系，将参考面要素组合R进行位置偏移，使得两组待匹配面要素组合在位置上能够进一步配准，通过衡量重叠程度来评判参考面要素组合R与目标面要素组合T的匹配程度，对目标面要素组合T中的每一个面要素分别计算参考面要素组合R移动前和参考面要素组合R移动后的重叠相似度，取平均值，记为匹配相似度ρ，公式如下：

$\rho =(\frac{A_p{A}_p}{A_r{A}_t}+\frac{A_q{A}_q}{A_r{A}_t})/2---\left(2\right)$

公式(2)中，A_r为参考面要素组合的面积，A_t为目标面要素组合的面积，A_p为R平移前二者的重叠部分面积，A_q为R平移后二者的重叠部分面积；

步骤四、匹配结果的冲突探测和消除：

根据匹配相似度取值大小，对发生冲突的匹配结果进行舍弃或者保留，即保留匹配相似度值大的，而舍弃匹配相似度较小的，从而实现匹配结果的矛盾消除。

本发明方法稳定可靠，易操作使用，可应用于多源多尺度情形下的同名面要素自动匹配算法，既能够准确获取同名面要素之间存在的1︰1匹配关系、1︰N匹配关系和M︰N匹配关系，又不要求两组待匹配面要素在位置上准确靠近，允许存在较大的位置偏差，甚至是非一致性的位置偏差，无须用户设置阈值，能够适应更为复杂的情况，因此可以称之为一种稳健匹配方法(算法)。该方法拓展了地图合并领域面要素匹配技术的适用性，使其对数据条件的要求和限制进一步降低，减少预处理的工作量，促进空间数据的集成、共享和复用，有效用于矢量地图合并、地图更新和变化检测，具有很强的实用性，经济和社会效益巨大。

附图说明

图1为本发明候选匹配对组合的生成示意图。

图2为本发明确定最佳匹配面要素组合的示意图。

图3为本发明匹配结果的矛盾消除图。

图4为本发明两组待匹配的面要素数据集示意图。

图5为本发明匹配关系为1:1的匹配结果示意图。

图6为本发明匹配关系为1:N的匹配结果示意图。

图7为本发明匹配关系为M:1的匹配结果示意图。

图8为本发明匹配关系为M:N的匹配结果示意图。

图9为本发明算法抵抗面要素位置偏差的能力图。

具体实施方式

以下结合具体情况对本明的具体实施方式作进一步说明。

本发明在具体实施中，可由以下步骤实现：

步骤一、数据获取：

用计算机分别读取两组待匹配居民地数据，一组居民地为参考面要素组合，记为R，另一组居民地为目标面要素组合，记为T；

步骤二、生成候选匹配对：

同名面要素之间可能存在多种匹配关系，包括1:1、1:N、M:1和M:N，为了能够正确获取同名面要素之间各种匹配关系，首先生成潜在的候选匹配对集合，且该集合应能尽可能地将所有正确的匹配对包含在内，对于待匹配的两组面要素数据集合，一组称之为参考面要素集合，另一组称之为目标面要素集合，算法交迭地依次从参考面要素集合和目标面要素集合中选择候选匹配面要素组合，并形成候选匹配对(如图1所示)，参考面要素R有三个面要素，即第一参考面要素R₁、第二参考面要素R₂和第三参考面要素R₃，目标面要素组合T中有三个面要素，即第一目标面要素T₁、第二目标面要素T₂和第三目标面要素T₃；顺序选取参考面要素集合中的每一个面要素，当在目标面要素集合中与第一参考面要素R₁存在相交关系的为第一目标面要素T₁，可获得第一组候选匹配对(R₁):(T₁)，然后再在参考面要素集合中寻找与第一目标面要素T₁存在相交关系的参考面要素为第一参考面要素R₁、第二参考面要素R₂，则又可获得第二组匹配对为(R₁,R₂):(T₁)，进一步获取与第一参考面要素R₁、第二参考面要素R₂相交的目标面要素，可获得第三组候选匹配对为(R₁,R₂):(T₁,T₂,T₃)，直至最后获得第四个候选匹配对为(R₁,R₂,R₃):(T₁,T₂,T₃)；当满足两个条件时，候选匹配对的生成终止，这两个条件是：一是无法进一步获取候选匹配对(如图2所示)，在获得第四组候 选匹配对后，各个面要素均已参与运算，已无法再获得新的候选匹配对；二是准备生成的候选匹配对在此前已经生成过；

但候选匹配对的生成终止并不代表是最终的匹配结果，如第四组候选匹配对为(R₁,R₂,R₃):(T₁,T₂,T₃)，还需要进一步从目标面要素组合中提取出与(R₁,R₂,R₃)组合最为相似的(T₁,T₂)组合，才是最终的正确匹配结果；

步骤三、同名面要素匹配关系的判定：

分别从两个方向进行面要素匹配相似度的计算，以获取匹配对，方法是，先以参考面要素组合R为基准，根据所计算出的匹配相似度，从目标面要素找到最佳匹配目标面要素组合T，而后再以目标面要素组合T为基准，根据所计算出的匹配相似度，从参考面要素组合中找到最佳匹配参考面要素组合，当该最佳匹配面要素组合为参考面要素组合R时，则参考面要素组合R和目标面要素组合T形成一组互为最佳匹配面要素组合；

在获取了候选匹配对之后，需要衡量参考面要素组合与目标面要素组合之间的匹配程度，并据此从候选匹配对中确定最佳的匹配结果，为了充分利用面要素的边界及内部信息，采用面要素之间相互重叠的程度来衡量面要素的匹配程度，如上设参考面要素组合为R，目标面要素组合为T，设参考面要素组合R的面积为A_r，目标面要素组合T的面积为A_t，参考面要素组合R与目标面要素组合T的重叠面积为A_o，则重叠相似度Sim为：

$\mathrm{Sim}=\frac{A_o{A}_o}{A_r{A}_t}---\left(1\right)$

通过计算重叠相似度来判定候选匹配对之间的匹配程度，其前提条件是二者在位置上能够吻合得足够好，然而在实际情况中，二者可能具有较大的位置偏差，如图2所示的一种极端情况，假设有一个候选匹配对，其参考面要素组合为(R₁,R₂)，目标面要素组合为(T₁-T₆)，二者在位置上偏差很大，此时无法通过衡量重叠程度来反映二者之间的匹配程度，为此，需要解决在位置偏差较大情况下，如何使用重叠相似度确定最佳匹配面要素组合的问题；

由图2所示，当将T₁至T₃组合在一起时，其形状与(R₁,R₂)颇为相似，它们互为匹配的可能性最大；但现在的问题是如何才能正确地将T₁至T₃组合在一起，对于(R₁,R₂)而言，T₁-T₆中的某个或若干个面要素的组合均与(R₁,R₂)可能存在M:N匹配关系，当按照穷举法列出其所有候选匹配面要素的组合，其组合数目共有个，显然，按照穷举法从中找出与(R₁,R₂)最为相似的匹配面要素组合将是非常耗时的，因此，欲进行面要素的自动匹配，必须首先找到一种能够快速且准确地确定最佳匹配面要素组合的方法；

注意到对于同名面要素而言，它们的全局形状特征将颇为相似，由此可通过以下四个步骤较快地确定候选匹配面要素组合：

(1)提取参考面要素组合R的全局形状特征：全局形状特征是指R的包络矩形及相应特征点，如图2所示，首先找到参考面要素组合R中各个顶点之间距离最远的两个顶点，分别为r₁、r₃，接着分别在线段r₁、r₃的左侧和右侧寻找距离线段r₁、r₃具有最远距离的点，为r₂和r₄，则由r₁、r₂、r₃和r₄四个特征点组成的矩形显然是参考面要素组合R的包络矩形，包络矩形的一条边与r₁r₃的连线平行，另一条边则与r₁r₃连线垂直，这种包络矩形具有与相似变换无关的特点，当参考面要素组合R整体发生偏移、旋转及缩放，所提取的包络矩形仍是由r₁、r₂、r₃和r₄四个特征点组成；

(2)对于目标面要素组合T，寻找与r₁、r₂、r₃和r₄的最佳匹配对应顶点：方法为，顺序选取目标面要素组合T中的每一个面要素，再顺序选取该面要素的每一个顶点，设选择的一个顶点为t₁(如图2所示)，在T中寻找一个顶点p，使得由点t₁到p所组成的向量U与由点r₁到r₂所组成的向量V的向量相似度取值最大，即向量之间最为相似，此处向量相似度α的计算公式如下：

$\alpha =\frac{\min \left(\right|\left|U\right||,|\left|V\right|\left|\right)}{\max \left(\right|\left|U\right||,|\left|V\right|\left|\right)}\times \frac{[U·V]}{\left|\right|U\left|\right|V\left|\right|}---\left(2\right)$

在图2中可以找到该顶点为t₂，按照相同步骤还可以分别找到顶点t₃和t₄，因为向量t₁t₃与向量r₁r₃最为相似，向量t₁t₄与向量r₁r₄最为相似。

按照上述方法，依据T中面要素的每一个顶点，都可以找到另外三个顶点，并相继计算三次最大向量相似度，取三次最大向量相似度的平均值作为综合向量相似度，当综合向量相似度取值最大时，即获得了参考面要素组合与目标面要素组合之的全局形状特征的最佳匹配点对关系，如图2所示，r₁、r₂、r₃和r₄四个特征点分别与t₁、t₂、t₃和t₄四个特征点存在匹配对应关系；

(3)计算匹配相似度：在通过全局形状特征获取最佳匹配点对后，计算r₁、r₂、r₃和r₄四个特征点的平均位置，记为r，同理也计算出t₁、t₂、t₃和t₄四个特征点的平均位置，记为t，将R从位置r点处整体移动到位置t处，此时R与T之间将较好地实现了配准，于是可以通过衡量重叠程度来评判R与T的匹配程度，对T中的每一个面要素分别计算R移动前和R移动后的重叠相似度，取平均值，记为匹配相似度ρ，公式如下：

$\rho =(\frac{A_p{A}_p}{A_r{A}_t}+\frac{A_q{A}_q}{A_r{A}_t})/2---\left(3\right)$

以上公式中，A_r为参考面要素组合的面积，A_t为目标面要素组合的面积，A_p为R平移前二者的重叠部分面积，A_q为R平移后二者的重叠部分面积；

(4)对目标面要素组合T中的每一个面要素都计算匹配相似度，并以大小为序对匹配相似度进行排序：按照降序依次选取目标面要素组合T中的每一个面要素，当参考面要素组 合与已经选取的目标面要素组合其匹配相似度值变小，则停止加入T中的面要素，反之则继续加入T中的面要素，则所组成的面要素组合即为最佳匹配面要素组合；如图2所示，当将参考面要素组合R平移至虚框所在位置处时，分别计算单个面要素T₁至T₆与R的匹配相似度，假设匹配相似度是按照T₁至T₆的顺序依次降低，则首先选取T₁面要素，此时的匹配相似度假设为ρ1，而后目标面要素组合中再加入T₂面要素，结果发现当将T₁与T₂组合在一起，再计算与R的匹配相似度时，该值比ρ1增大了，则接受T₁与T₂的组合并继续加入T₃面要素，结果发现匹配相似度又进一步增大，则继续加入T₄面要素，结果发现匹配相似度减少，则停止加入任何面要素，最后可依次选取出T₁、T₂和T₃三个面要素，且它们组合在一起成为R₁和R₂的最佳匹配面要素组合；

步骤四匹配结果的冲突探测和消除：

当候选匹配对按照公式(3)进行匹配相似度的计算后，可能会导致匹配结果出现相互矛盾的现象，如图3所示，可以存在六组匹配关系，分别是(R₁):(T₁)匹配相似度0.82、(R₂):(T₂)匹配相似度0.82、(R₃):(T₃)匹配相似度0.85、(R₁,R₂):(T₁,T₂)匹配相似度0.9、(R₁,R₃):(T₁,T₃)匹配相似度0.82、(R₁,R₂,R₃):(T₁,T₂,T₃)匹配相似度0.85，显然匹配结果之间存在了相互矛盾和冲突的现象，为此，可根据匹配相似度取值大小，对匹配结果进行舍弃或者保留，图3中应该首先予以保留的匹配结果为(R₁,R₂):(T₁,T₂)，因为其匹配相似度最大，而后再保留匹配结果(R₃):(T₃)，采用该方法可以较好地解决匹配结果的矛盾和冲突，从而实现多源多尺度面要素的稳健匹配。

本发明方法通过实际应用，取得了非常满意的有益技术效果，以图4给出的实施例为例，具体情况如下：

通过图4a、4b给出的一组不同来源、不同时段的居民地面要素来验证本发明算法，其中，参考居民地要素类见下图4a，共有个703面要素，目标居民地要素类见图4b，共有820个面要素。尽管总体看上去两组数据较为相似，但事实上有不少面要素不但在形状上有较大差异，在位置上也存在非一致性的距离偏差，有些地方偏差较大，有些地方则较小。

(1)算法处理复杂匹配关系的能力

算法能够对1:1，1:N，M:N，1:0，0:1等各种匹配关系进行面要素的自动匹配，表1统计了该实例中各种匹配关系的匹配情况和匹配相似度，对该实例，参考数据集中共有7个面要素发生了误匹配，10个面要素发生了漏匹配，12个面要素其匹配类型识别错误。目标数据集中共有10个面要素发生了误匹配，16个面要素发生了漏匹配，13个面要素其最终的匹配类型错误。总的匹配准确率为1-(7+10+12+10+16+13)/(703+820)＝94.9％。

图5展示了匹配关系为1:1时的参考面要素数据集和目标面要素数据集，图6展示了匹 配关系为1:N时的参考面要素数据集和目标面要素数据集，图7展示了匹配关系为M:1时的参考面要素数据集和目标面要素数据集，图8展示了匹配关系为M:N时的参考面要素数据集和目标面要素数据集。

表1各种匹配类型匹配情况的统计及匹配相似度

(2)算法抵抗面要素位置偏差的能力

本发明方法不要求两组面要素数据在位置上非常靠近，即便待匹配的两组面要素存在非一致性位置偏差现象，即在有些地方位置偏差很小，在有些地方位置偏差很大，依然能够得到正确的匹配结果。图9为图4中的一个局部放大图，该处的匹配结果见表2，匹配结果有1:1、1:N以及M:N三种匹配类型。观察图9可以发现，参考面要素数据集(见实线多边形)的13号要素(见黑体标注)与目标面要素数据集(见虚线多边形)中的58号要素(见斜体标注)距离偏差很大，同样，参考面要素数据集的338号要素与目标面要素数据集中的197号要素距离偏差也相当大，但查看表2的匹配结果，可以看出算法依然能对这两例进行正确匹配。由表2可知，对于该实例，算法无论在同名面要素位置偏小，或者同名面要素位置偏差较大，均可获得正确的匹配结果，这就表明算法能够较好地抵抗同名面要素之间的非一致性位置偏差，降低了对数据的要求和限制，使得算法具有更广泛的应用场合。

表2匹配结果列表

源要素目标要素匹配类型匹配相似度291911:10.58272071:10.723381971:10.411171831:10.66262141:10.651191651:10.56

1358,59,60,61,621:N0.545282,851:N0.371,2,328,12M:N0.5725,27,2813,14,15,16,18,20M:N0.52

由上述可以清楚的看出，本发明的有益技术效果是：

1、能够获取同名面要素之间的1:1、1:N和M:N等各种匹配关系；

2、即使在同名面要素存在较大位置偏差甚至是非一致性的位置偏差时，依然能够对同名面要素进行有效匹配；

3、不像其他方法那样，需要设置阈值，而本发明无须阈值的设定，本发明通过进行双向匹配，当参考面要素和目标面要素能够彼此互为对方的最佳匹配对象时，就确定它们的匹配关系，这就避免了阈值的设置。整个过程是自动完成的。

综上所述，该发明拓展了地图合并领域面要素匹配技术的适用性，使其对数据条件的要求和限制进一步降低，减少预处理的工作量，促进空间数据的集成、共享和复用，有效用于矢量地图合并、地图更新和变化检测，具有很强的实用性。