多源同名居民地面目标识别及其同名特征点匹配方法

徐 晶 晶，赵 东 保*，邓 悦，曹 连 海，管 相 荣

(1.华北水利水电大学测绘与地理信息学院，河南 郑州 450046;2.河南省自然资源综合保障中心，河南 郑州 450016)

随着空间数据获取技术迅速发展,海量矢量空间数据涌现，由于数据尺度、精度、时相以及不同部门对同一地物的理解和服务目的等不同，即使覆盖相同地理范围的空间数据也存在各种差异，从而导致同名面目标之间存在复杂的匹配对应关系，因此需要进行空间数据融合。同名目标匹配是数据融合的关键环节[1]，由于居民地面目标在面要素类数据库中数量多、占比大、匹配关系复杂，因此以居民地为代表研究同名面目标的匹配对实现空间数据的更新与融合具有重要意义。

面目标匹配通常基于拓扑特征[2-8]和几何特征[9-13]，利用拓扑关系、形状、大小、位置等特征指标进行匹配，而语义特征也经常作为辅助信息用于匹配。在拓扑特征匹配方面，有学者利用拓扑关系的叠置特性进行面目标匹配[2-4]，但该类方法的重要前提是待匹配面目标已经消除坐标差异且位置极为接近，也有学者对空间目标的邻近关系进行分析[5-8]，但该类方法仅用拓扑关系进行匹配，未使用几何条件，未能充分利用现有信息，且对数据的质量要求较高；
在几何特征匹配方面，有学者利用面目标的形状、大小、距离、尺寸、方向、面积、外接矩形等几何指标构建几何相似度，虽有效解决了指标单一不可靠的问题，但具体权重不易判断，匹配结果的鲁棒性较差[9-13]，有学者通过引入形状描述算子(傅里叶描述子[14]、矩描述子[15]等)计算面目标形状相似程度，进而判定面目标之间的匹配关系，但该类方法仅能处理一对一匹配类型的数据，难以处理复杂数据。因此，为实现更精确的数据融合，应考虑从多特征出发，综合使用多种相似性测度进行面目标匹配，在处理复杂匹配关系的同时能有效抵抗位置偏差，也可提高同名面目标匹配的准确率。例如，将几何相似度与语义相似度结合，以完成同名面目标的准确匹配[16-18]；
针对复杂匹配类型的数据，根据多个几何指标定义面目标的上下文位置关系，再借助神经网络完成面目标匹配[19]；
将矩形相似度和空间叠置关系结合，提高位置偏差较大时同名面目标匹配的准确率[20]等，但该类算法计算繁琐、耗时较长，难以高效处理大规模数据。

综上，为实现面目标位置的进一步融合，还需对同名面目标的同名特征点进行自动匹配[21]。在数字图像处理等领域[22-27]，有RANSAC[28]、SIFT[29]与BRISK[30]等典型的图像特征点匹配算法，但缺少针对多源、多尺度情况下同名矢量面目标之间特征点匹配问题开展专门研究，尤其是缺乏针对存在复杂匹配关系的同名面目标之间特征点的匹配算法。因此，本文同时考虑多源同名面目标的自动识别以及同名面目标上同名特征点的自动匹配问题，以期为位置融合奠定重要基础。

多源同名居民地面目标的自动识别与匹配主要包括3个阶段：基于空间相交关系的候选匹配居民地面目标集合确定、参考居民地面目标与调整居民地面目标的候选匹配对获取和同名居民地面目标匹配关系确定。

1.1 基于空间相交关系的候选匹配居民地面目标集合确定

多源居民地面目标匹配类型可总结为1∶0、1∶N、M∶N等，产生原因有以下3种情况：1)在进行跨比例尺地图综合时，取舍环节会产生1∶0或0∶1匹配类型，地图概括环节会产生1∶N或M∶1及M∶N匹配类型；
2)数据采集人员对同一地物的理解以及需求等不同，导致出现多种匹配结果；
3)实地区域变化伴随着居民地面目标新增或消失，抑或是局部修改，1∶0或0∶1等匹配类型随之出现。一般而言，在进行空间数据融合时，尽管待匹配的两组面目标集合可能存在跨尺度现象，但尺度相差不大，且由于面目标通常在图幅中占据较大的空间范围，因此在绝大多数情况下，可利用空间相交关系确定候选匹配居民地面目标对象。

假设Ri为参考居民地面目标集合R中的一个居民地面目标，Tj为调整居民地面目标集合T中的一个居民地面目标，若Tj与Ri存在空间相交关系，则将该调整居民地面目标Tj加入参考居民地面目标Ri的候选匹配对象序列中，然后在T中依次找出所有符合上述条件的调整居民地面目标，并加入参考居民地面目标Ri的候选匹配对象序列中，最终获取R、T中每个居民地面目标的候选匹配对象。

1.2 参考居民地面目标与调整居民地面目标的候选匹配对获取

针对每个居民地面目标的候选匹配对象，进一步得到所有的候选匹配对集合，并使该集合尽可能包含所有正确的匹配对。对于参考居民地面目标集合R和调整居民地面目标集合T，利用算法交迭从两集合中选择候选匹配居民地面目标组合，形成候选匹配对。

以图1为例，参考居民地面目标集合R有R1、R2和R33个居民地面目标，调整居民地面目标集合T有T1和T2两个居民地面目标，R1的候选匹配居民地面目标对象为T1，R2的候选匹配居民地面目标对象为T1、T2，R3的候选匹配居民地面目标对象为T2，T1的候选匹配居民地面目标对象为R1、R2，T2的候选匹配居民地面目标对象为R2、R3。从R1开始，R1在调整居民地面目标组合中的候选匹配居民地面目标为T1，此时得到第一个候选匹配对(R1∶T1)，依次交迭判断可获得T1∶(R1，R2)、(R1，R2)∶(T1，T2)、(T1，T2)∶(R1，R2，R3)等其他匹配对，当满足以下任一条件时，候选匹配对的搜寻过程结束：1)无法进一步获取候选匹配对，如图1中在获得第四组候选匹配对后，各个居民地面目标均已参与运算，已无法再获得新的候选匹配对；
2)准备生成的候选匹配对此前已经生成，如图1中匹配对(R1，R2，R3)∶(T1，T2)先后出现两次，在第二次搜寻时即可终止。

图1 候选匹配对象查找示意Fig.1 Schematic diagram of candidate matching object searching

1.3 同名居民地面目标匹配关系确定

对于所获取的候选匹配对需进一步确定其匹配关系并给出匹配相似度。由于两组不同来源的居民地面目标之间往往存在形状差异和距离偏差，因此需要一种可靠的匹配相似度计算方法。除计算二者最初的重叠相似度以外，本文还对匹配对中的参考居民地面目标进行位置偏移，使参考居民地面目标与调整居民地面目标在位置上进一步配准。具体而言：分别将每个匹配对中的所有参考居民地面目标集合R、调整居民地面目标集合T进行合并，再将合并后R的质心移至合并后T质心的位置，实现质心的配准；
之后分别计算配准前的重叠相似度ρbefore(式(1))和配准后的重叠相似度ρafter(式(2))，取二者平均值记为居民地面目标之间的匹配相似度ρfeature(式(3))；
最后按照匹配相似度最大原则，筛选最终的多源居民地面目标匹配结果，确定多源居民地面目标匹配对应关系。

ρbefore=S2/(SRST)

(1)

ρafter=S′2/(SRST)

(2)

ρfeature=(ρbefore+ρafter)/2

(3)

式中：SR为参考居民地面目标集合R的面积；
ST为调整居民地面目标集合T的面积；
S和S′分别为R平移前后二者的重叠部分面积。

在自动识别出同名居民地面目标后，对同名面目标进行几何纠正，进而实现同名面目标在空间位置上的融合，在同名居民地面目标匹配结果基础上实现同名居民地面目标特征点的自动匹配。

2.1 基于编辑距离的同名居民地面目标上同名特征点自动匹配

本文使用编辑距离算法寻找同名居民地面目标之间特征点的匹配对应关系，该特征点是指依据待匹配面要素数据集的比例尺选择相应的阈值进行多边形化简所提取的点。编辑距离算法用于处理两个字符串str1与str2之间的匹配问题[31]，算法规定在匹配过程中只能进行插入、删除、替换3种操作，每种操作需要耗费相应代价，匹配完成后，操作所需的最小总代价可表示str1与str2的匹配程度。若将组成居民地面目标的每个特征点看作一个字符，则两个待匹配的居民地面目标可看作两个字符串，从而将编辑距离算法运用于居民地面目标的特征点匹配中，确保同名居民地面目标特征点的匹配结果保持拓扑关系一致性，避免交叉匹配现象。

假设R、T互为同名居民地面目标，分别对应特征点集合R(p1,p2,p3,…,pm-1,pm)和T(q1,q2,q3,…,qn-1,qn)，且R、T的每个特征点均有特征量U(pm)、V(qn)，共包括k组对应点{(px1,qy1),(px2,qy2),(px3,qy3),…,(pxk,qyk)},其中x1=y1=1，xk=m，yk=n，使对应顶点间特征量之差的总和最小，则此时所耗费的代价可表示为函数C(式(4))，当C取最小值时，对应的特征点配对序列为最优的特征点匹配序列。

(4)

2.2 同名居民地面目标特征点对匹配相似度计算

编辑距离算法的关键在于构建可靠特征点匹配对的匹配相似度，本文分别定义向量方向相似度、面积比相似度和距离邻近度3种特征指标。假设已经确定同名居民地面目标，且二者质心之间的平均距离为r，则针对参考居民地面目标R的每个特征点，在调整居民地面目标T中与其距离不超过r的特征点则为其候选匹配点。

图2 方向相似度和面积比相似度的计算Fig.2 Calculation of vector direction similarity and area ratio similarity

(5)

(2)面积比相似度。以图2为例，可以看出调整居民地面目标T1中的q3点内部区域的夹角为270°，与参考居民地面目标中p3、p6、p93个点的角度值(90°)明显不同，但如果构建面积比相似度，则发现其局部特征很相似。对于参考居民地面目标R2的p6点，以p6点为圆心，以r为半径做圆C1，对于调整居民地面目标T1的q3点，以q3点为圆心，同样以r为半径做圆C2，则面积比相似度可由式(6)计算；
对式(6)进一步简化，使其值域在[0,1]之间(式(7))，可以发现，尽管p6和q3点的角度值明显不同，但其面积比却极为接近，符合人眼的视觉观察。

(6)

式中：S1为各参考居民地面目标与圆C1相交部分的面积之和(图2a中阴影部分)；
S2为各调整居民地面目标与圆C2相交部分的面积之和(图2b中阴影部分)；
S为圆C1和C2的面积。

(7)

(3)距离邻近度。在匹配过程中，距离远近也是匹配对应关系的重要判别指标，为此定义特征点的距离邻近度指标，计算公式为：

ρ3=1-distance(p6,q3)/r

(8)

式中：distance(p6,q3)为p6、q3两点间的距离。

进一步综合考虑向量方向相似度、面积比相似度与距离邻近度，构成特征点之间的匹配相似度ρpoint，计算公式为：

ρpoint=w1×ρ1+w2×ρ2+w3×ρ3

(9)

式中：w1、w2、w3为3个相似度指标的权重，通常设置为1/3。

2.3 同名居民地面目标特征点序列对应关系的最短路径求取

本文算法的基本目标是找到特征点对之间的对应关系使代价函数C值最小，因此可看成求取一条同名居民地面目标特征点序列对应关系的最短路径，可采用动态规划法求取，即当沿路径的累计距离D(i,j)(式(10))最小时，该路径即为最短路径。

D(i,j)=M(i,j)+min{D(i-1,j),D(i,j-1),

D(i-1,j-1)}

(10)

式中：i∈(1,m),j∈(1,n),M(i,j)为当前格点距离。

在参考居民地面目标与调整居民地面目标匹配过程中，本文首先指定参考居民地面目标的起始特征点，然后依次变换调整居民地面目标的起始点，每变换一次，计算一次总的代价函数C，则最小代价函数所对应的路径为最短路径，将最短路径进行回溯得到特征点对之间的最佳对应关系。由于多源居民地面目标之间可能存在M∶N匹配关系，故采用编辑距离方法在参考居民地面目标与调整居民地面目标之间进行同名特征点序列匹配，即执行M×N次编辑距离算法，以获取多源居民地面目标特征点的匹配对应关系。

2.4 特征点匹配对应关系进一步处理

多源居民地面目标之间的M∶N匹配关系结果中特征点之间可能存在多重匹配对应关系，针对此种匹配结果需进行特殊处理。例如，在图3a中，多源居民地面目标之间存在M∶N匹配关系，特征点匹配结果如图3a中红色短线所示，其中，r5点与t7、t8点，t8点与r5、r6点，r4点与t4、t6点，t3点与r9、r10、r11点，其间存在非一对一的匹配对应关系。针对此种情况采用如下策略进行处理，以确保特征点之间的一一匹配对应关系。假设参考居民地面目标中特征点集合为P，调整居民地面目标中特征点集合为Q，将其特征点之间的匹配相似度构成M行N列矩阵，则有：1)当匹配相似度矩阵中i行j列的向量相似度大于i行其他列以及j列其他行的匹配相似度时，则特征点pi与特征点qj之间存在一一匹配对应关系；
2)将已经获得匹配关系的特征点排除，若此时还有特征点未获得匹配，则重复上一步，直至无法再找到特征点之间的一一匹配对应关系为止，最终可得到特征点的一一匹配对应关系(图3b)。

图3 匹配关系的进一步处理Fig.3 Further processing of matching relationships

在普通计算机环境下(Intel Core i5处理器，1.60 GHz主频)利用C#语言编写本文算法，实验数据为郑州市局部区域居民地面目标，来自高德地图和四维图新地图。

3.1 同名居民地面目标匹配类型识别

参考居民地面目标集合(图4a)共有704个居民地面目标，调整居民地面目标集合(图4b)共有821个居民地面目标，两组居民地数据总体大致吻合，但有不少同名居民地面目标在形状、位置上有较大差异。实例中1∶1(图5a)、M∶1(图5b)、1∶N(图5c)、M∶N(图5d)、1∶0、0∶1匹配类型的匹配次数分别为463、70、16、19、89、119，平均匹配相似度分别为0.77、0.74、0.67、0.74、0、0。其中，参考数据集中居民地面目标发生误匹配、漏匹配、匹配类型识别错误的数量分别为7个、9个、13个，目标数据集中居民地面目标发生误匹配、漏匹配、匹配类型识别错误的数量分别为7个、18个、15个，总匹配准确率为95.47%。在算法的实际应用中，可通过综合设定各个相似度阈值判定多源居民地面目标是否发生变化。

图4 实验数据情况Fig.4 Experimental data situation

图5 同名居民地面目标匹配结果Fig.5 Matching results of homonymous residential area targets

3.2 多源同名居民地面目标上同名特征点匹配

进一步依据多源同名居民地面目标的自动匹配结果，实现对同名居民地面目标上同名特征点的自动匹配。其中，居民地面目标化简的阈值设置为1 m，该值通过反复实验得出，普遍适用于大比例尺导航数据。由两组居民地面目标特征点的匹配结果统计可知，特征点匹配结果中共有3 236个匹配点对，其中参考数据集中发生误匹配和漏匹配的特征点分别为43个和32个，调整数据集中发生误匹配和漏匹配的特征点分别为41个和36个，总匹配准确率为95.30%。本实验中，特征点错误匹配的原因皆为居民地面目标匹配类型出现错误，因此对居民地面目标匹配结果进行核查纠正后，还可进一步提高匹配率。图6展示了不同匹配关系类型的实例。

图6 不同匹配类型特征点匹配结果Fig.6 Matching results for different matching types of feature points

根据同名居民地面目标同名特征点的匹配结果，可建立居民地面目标匹配对的局部坐标变换关系，并可根据同名特征点之间的匹配相似度确定相应权重，采用最小二乘抗差估计方法稳健估计仿射变换参数，再根据参考居民地面目标对调整居民地面目标进行几何纠正。图7展示了图4中圆框区域的几何纠正结果，可以看出，相比图7a，图7b中两组居民地面目标在位置上明显更近，同名参考居民地面目标与调整居民地面目标同名特征点间的平均距离从10.5 m减至2.5 m，明显减小了位置偏差，有效实现了几何纠正。

图7 特征点几何纠正结果的细节展示Fig.7 Geometric correction results of feature points

针对大比例尺导航地图居民地面目标数据融合问题，本文提出多源同名居民地面目标自动识别及其特征点匹配方法。首先基于空间拓扑关系确定候选匹配对象集，并根据质心重叠后的居民地面目标之间的重叠程度确定匹配相似度，完成同名居民地面目标之间1∶1、1∶N、M∶N等匹配关系的自动识别；
继而构建向量方向相似度、面积比相似度与距离邻近度等特征指标，并利用编辑距离算法实现同名居民地面目标上同名特征点的自动匹配。以郑州市局部区域居民地面目标电子地图数据对方法的验证结果表明，本文算法既能自动识别多源同名居民地面目标的1∶1、1∶N和M∶N等匹配关系，又能对同名面目标上的同名特征点进行自动匹配，且二者的匹配准确率均在95%以上。基于同名面目标上同名特征点的匹配结果，采用抗差稳健估计模型进一步实现多源居民地面目标的几何纠正，结果表明同名特征点间的平均距离从10.5 m减至2.5 m，明显减小了位置偏差，有效实现了几何纠正，可为多源面目标的位置融合奠定重要基础。

需要说明的是，当多源居民地面目标存在较大的非一致性位置偏差时，可能产生错误匹配现象。针对该现象，可在预处理阶段通过精确配准或采用人工智能算法设定最优匹配函数，以解决更为复杂的匹配问题。

猜你喜欢 同名距离居民 同名西江月(2021年3期)2021-12-21石器时代的居民阅读与作文（小学高年级版）(2021年6期)2021-09-10意外夺冠娃娃乐园·综合智能(2020年5期)2020-06-07算距离小学生导刊(2018年34期)2018-12-18三 人 行连环画报(2016年10期)2016-12-16每次失败都会距离成功更近一步山东青年(2016年3期)2016-02-28爱的距离母子健康(2015年1期)2015-02-28距离有多远延河(下半月)(2014年3期)2014-02-28高台居民读者(乡土人文版)(2013年12期)2013-05-03曹 操连环画报(2010年2期)2010-10-26

推荐访问:同名 匹配 识别