一种不同比例尺面状居民地的概率松弛匹配算法_刘洁.pdf

第 48 卷第 2 期2023 年 4 月Vol.48 No.2Apr.2023测绘地理信息Journal of Geomatics一种不同比例尺面状居民地的概率松弛匹配算法刘洁1 郭庆胜1 王勇2 陈恒11 武汉大学资源与环境科学学院，湖北 武汉，4300792 中国测绘科学研究院，北京，100830A Probabilistic Relaxation Matching Algorithm for Areal Settlements at Different ScalesLIUJie1 GUOQingsheng1 WANGYong2 CHENHeng11 School of Resources and Environment Science，Wuhan University，Wuhan 430079，China2 Chinese Academy of Surveying and Mapping，Beijing 100830，China摘要：为了提高居民地面实体匹配的准确度，提出一种基于概率松弛模型的不同比例尺面状居民地匹配算法。首先，依据道路信息划分面状居民地数据，每次运行算法只处理一个道路网眼内的面状居民地；然后，扩展初始匹配模式，正反向计算居民地面实体之间和居民地面实体匹配到空两种匹配概率，并根据邻近匹配对的兼容性不断更新初始概率矩阵，直至相邻两次迭代矩阵内匹配概率变化量均小于某一阈值；最后，根据设定的选取规则选出 1 0、1 1、1 M 和 MN等4种匹配对。实验结果表明，本文所提方法可以有效准确地识别出 4种匹配关系，明显减少了误匹配和漏匹配。关键词：面状居民地；实体匹配；道路网眼；概率松弛中图分类号：P208文献标志码：AAbstract：In order to improve the matching accuracy，this paper proposes a matching algorithm for areal settlements at different scales based on probabilistic relaxation model.The proposed method first partitions two areal settlements datasets into subsets using road information，so that at each run the algorithm deals only with the areal settlements in one road mesh.After that，the initial matching mode is extended to calculate bidirectional matching probability between areal settlements and between areal settlement to null.And then，continuously updates the initial probability matrix according to the compatibility of adjacent matching pairs until the matching probability variations in matrix of two consecutive iterations are less than a certain threshold.Finally，four matching pairs of 1 0，1 1，1 M and MN are selected according to the selection rule we set.The results indicate that the algorithm proposed in this paper can effectively and accurately identify four matching relationships and significantly reduce the number of mismatched pairs and missed matched pairs.Key words：areal settlement；entity matching；road mesh；probabilistic relaxation不同尺度同名实体匹配技术能够用于保证同一空间场景在不同尺度数据库之间的一致性，从而实现多尺度地理空间数据库的增量更新。然而由于制图综合或地理空间目标变化，不同尺度同名实体匹配面临着一些复杂情况，例如：聚合操作将多个居民地面实体聚合为一个面实体；典型化和移位操作会使居民地面实体的位置发生明显偏移。面对这些复杂情况，研究匹配效果更好的算法是非常必要的。国内外很多学者从不同角度对实体匹配做了很多研究工作，基于地理实体几何相似性的同名实体匹配常用的相似性度量因子包括：位置、形状、大小、重叠区域和方向等1-4。还有些算法在局部几何相似性的基础上顾及了邻近结构相似性5，根据邻近关系信息降低目标匹配对的模糊性；也有学者采用增量式凸壳匹配、群对象探测等方法来识别不同比例尺的居民地匹配关系6，7，或者采用道路外包矩形的自适应算法、模拟退火算法提高道路匹配效率8，9。近年来，概率松弛算法已经应用到了点要素10，11、道路网12-16和面实体匹配17-20的研究中。实际上，在一些模糊性较大的情况下，匹配更大程度上依赖上下文信息，在不同的上下文环境中匹配结果也可能不DOI：10.14188/j.2095-6045.2021102文章编号：2095-6045（2023）02-0138-05引用格式：刘洁，郭庆胜，王勇，等.一种不同比例尺面状居民地的概率松弛匹配算法 J.测绘地理信息，2023，48（2）：138-142（LIU Jie，GUO Qingsheng，WANG Yong，et al.A Probabilistic Relaxation Matching Algorithm for Areal Settlements at Different Scales J.Journal of Geomatics，2023，48（2）：138-142）基金项目：国家自然科学基金（41871378）。第 48 卷第 2 期刘洁等：一种不同比例尺面状居民地的概率松弛匹配算法同17，概率松弛算法就是在迭代过程中尝试结合上下文信息，最终得到全局一致性的匹配结果。文献 17 将概率松弛模型拓展到了多尺度面实体匹配的研究中，尤其是在模糊性较大的情况下获得了较好的匹配效果，但其还存在改进的空间，如匹配过程中缺少对面实体匹配到空实体情况的研究。因此，本文在此基础上扩展初始匹配模式，正反向计算居民地面实体之间和居民地面实体匹配到空两种匹配概率，并根据邻近匹配对的兼容性不断更新初始概率矩阵，直至相邻两次迭代矩阵内匹配概率变化量均小于某一阈值，最终根据设定的选取规则选出 1 0、1 1、1 M和 M N等 4种匹配对。1 面状居民地匹配的概率松弛改进算法1.1面状居民地分区按照制图综合的规则，各个道路网眼内的居民地面实体应该是独立综合的。此外，在地图综合过程中，道路两侧的面实体可能发生不同方向的移位，将其他道路网眼内的面实体纳入候选匹配集可能会造成邻近候选匹配对之间的相对关系出现偏差。因此，本文采用文献 21 提出的一种改进的多边形自动生成算法提取道路网眼，利用小比例尺地图上的道路网眼对匹配区域进化划分，同时通过匹配的方法概略地找到大比例尺地图上对应道路网眼内的居民地面实体群17，每次只处理一个道路网眼内的面状居民地数据，减少无效遍历，提高匹配效率。1.2概率矩阵初始化假设两个待匹配的居民地面实体数据集：setA和 setB。对于 setA中的每个居民地面实体 i，在 setB中搜索与其距离小于距离阈值 d的面实体 j作为候选匹配集 CSi。同样获取 setB中每个居民地面实体 j的候选匹配集 CSj。不属于 CSi或 CSj的居民地面实体，单向初始匹配概率直接赋值为 0。本文在相似性度量因子的选择和计算上参考了文献 19 和文献22 的研究成果，并综合考虑了位置相似度、形状相似度、大小相似度、方向相似度和叠置率。概率矩阵初始化完成后，形成一个（m+1）（n+1）的矩阵，m 和 n 分别是 setA 和 setB 中居民地面实体的数目，如式（1）所示。P=|P1，1P1，2P1，-1P2，1P2，2P2，-1P-1，1P-1，20（1）式中，P（i，j）为面实体 i匹配到面实体 j的概率。1.3顾及上下文信息的概率矩阵迭代更新1.3.1兼容系数的计算概率松弛算法中某一候选匹配对的匹配概率除了与自身相似性有关外，还与邻近候选匹配对的匹配概率和相对关系有关13。兼容系数正反应了邻近匹配对（h，k）对目标匹配对（i，j）的兼容程度，即相对关系，计算见式（2）。如果 setA 中面实体 i 和 h 与setB 中面实体 j和 k的相对关系比较相似，则兼容系数 C（ij，hk）会得到一个较高的值。例如，图 1中对于目标匹配对（i，j），邻近候选匹配对（h，k）的兼容程度高于邻近候选匹配对（h，k，），因为 i、h与 j、k的相对关系（相对方向关系、相对位置关系和相对叠置关系）更相似。C(ij，hk)=w1 simol(i，j)relol(ij，hk)+w2 q=14simq(i，j)relq(ij，hk)（2）式中，w1、w2为权重值；simol（i，j）表示叠置率；simq（i，j）表示相似度，q=p，sp，s，o，分别表示位置、形状、大小、方向；考虑上下文信息的相对位置、相对形状、相对大小和相对方向关系的计算见参考文献 19，相对叠置关系的计算见式（3）。relol(ij，hk)=11+(ratio1-ratio2)2其中，|ratio1=maxo(i，j)a(i)，o(i，j)a(j)ratio2=maxo(h，k)a(h)，o(h，k)a(k)（3）式中，relol代表面实体 i、h和面实体 j、k的相对叠置关系；a（i）为面实体 i的面积，a（h）、a（j）和 a（k）的含义类似；o（i，j）为面实体 i和 j相交部分的面积，o（h，k）的含义类似。图 1邻近候选匹配对（h，k）对目标匹配对（i，j）的兼容程度Fig.1Compatibility of Adjacent Candidate Matching Pair（h，k）to Target Matching Pair（i，j）139测绘地理信息2023 年 4 月1.3.2概率矩阵的迭代更新兼容系数则反映了目标匹配对和邻近候选匹配对之间的相对关系，而通常邻近候选匹配对不止一个，需要综合考虑全部邻近候选匹配对的兼容系数及其匹配概率值，得到目标匹配对（i，j）第 r 次迭代时的支持系数 qr（i，j）23。根据第 r次迭代的匹配概率和支持系数，可以计算第 r+1次的匹配概率17，其表达式为：pr+1(i，j)=p2(i，j)+q2(i，j)1+j=1J(q2(i，j)2（4）式中，r为迭代次数；Pr（i，j）为第 r次迭代时的匹配概率；Pr+1（i，j）为第 r次迭代时的匹配概率。如此迭代，直到概率矩阵的变化量小于某一给定阈值。每次运行算法仅处理一个道路网眼内的面状居民地数据，其迭代过程的语句频度为 f（n）=n4+n2+n2+n+n+n=n4+2n2+3n，时 间 复 杂 度 为T（n）=O（f（n）=O（n4）。1.4匹配对选取一般来说，面实体的匹配关系可以分为 6 种类型，分别是 1 0、0 1、1 1、M 1、1 M 和 M N，如图 2所示。其中，0 1和 M 1的匹配关系可以转化为 1 0和 1 M 的匹配关系。因此，本文只需讨论 1 0、1 1、1 M和 M N等 4种匹配关系。1 0的匹配关系对应空间