一种不同比例尺面状居民地的概率松弛匹配算法_刘洁.pdf
《一种不同比例尺面状居民地的概率松弛匹配算法_刘洁.pdf》由会员分享,可在线阅读,更多相关《一种不同比例尺面状居民地的概率松弛匹配算法_刘洁.pdf(5页珍藏版)》请在咨信网上搜索。
1、第 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 Resource
2、s and Environment Science,Wuhan University,Wuhan 430079,China2 Chinese Academy of Surveying and Mapping,Beijing 100830,China摘要:为了提高居民地面实体匹配的准确度,提出一种基于概率松弛模型的不同比例尺面状居民地匹配算法。首先,依据道路信息划分面状居民地数据,每次运行算法只处理一个道路网眼内的面状居民地;然后,扩展初始匹配模式,正反向计算居民地面实体之间和居民地面实体匹配到空两种匹配概率,并根据邻近匹配对的兼容性不断更新初始概率矩阵,直至相邻两次迭代矩阵内匹配概率变化量均小
3、于某一阈值;最后,根据设定的选取规则选出 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 mod
4、el.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
5、 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,f
6、our 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 p
7、airs.Key words:areal settlement;entity matching;road mesh;probabilistic relaxation不同尺度同名实体匹配技术能够用于保证同一空间场景在不同尺度数据库之间的一致性,从而实现多尺度地理空间数据库的增量更新。然而由于制图综合或地理空间目标变化,不同尺度同名实体匹配面临着一些复杂情况,例如:聚合操作将多个居民地面实体聚合为一个面实体;典型化和移位操作会使居民地面实体的位置发生明显偏移。面对这些复杂情况,研究匹配效果更好的算法是非常必要的。国内外很多学者从不同角度对实体匹配做了很多研究工作,基于地理实体几何相似性的同名实体匹
8、配常用的相似性度量因子包括:位置、形状、大小、重叠区域和方向等1-4。还有些算法在局部几何相似性的基础上顾及了邻近结构相似性5,根据邻近关系信息降低目标匹配对的模糊性;也有学者采用增量式凸壳匹配、群对象探测等方法来识别不同比例尺的居民地匹配关系6,7,或者采用道路外包矩形的自适应算法、模拟退火算法提高道路匹配效率8,9。近年来,概率松弛算法已经应用到了点要素10,11、道路网12-16和面实体匹配17-20的研究中。实际上,在一些模糊性较大的情况下,匹配更大程度上依赖上下文信息,在不同的上下文环境中匹配结果也可能不DOI:10.14188/j.2095-6045.2021102文章编号:209
9、5-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 期刘洁等:一种不同
10、比例尺面状居民地的概率松弛匹配算法同17,概率松弛算法就是在迭代过程中尝试结合上下文信息,最终得到全局一致性的匹配结果。文献 17 将概率松弛模型拓展到了多尺度面实体匹配的研究中,尤其是在模糊性较大的情况下获得了较好的匹配效果,但其还存在改进的空间,如匹配过程中缺少对面实体匹配到空实体情况的研究。因此,本文在此基础上扩展初始匹配模式,正反向计算居民地面实体之间和居民地面实体匹配到空两种匹配概率,并根据邻近匹配对的兼容性不断更新初始概率矩阵,直至相邻两次迭代矩阵内匹配概率变化量均小于某一阈值,最终根据设定的选取规则选出 1 0、1 1、1 M和 M N等 4种匹配对。1 面状居民地匹配的概率松弛
11、改进算法1.1面状居民地分区按照制图综合的规则,各个道路网眼内的居民地面实体应该是独立综合的。此外,在地图综合过程中,道路两侧的面实体可能发生不同方向的移位,将其他道路网眼内的面实体纳入候选匹配集可能会造成邻近候选匹配对之间的相对关系出现偏差。因此,本文采用文献 21 提出的一种改进的多边形自动生成算法提取道路网眼,利用小比例尺地图上的道路网眼对匹配区域进化划分,同时通过匹配的方法概略地找到大比例尺地图上对应道路网眼内的居民地面实体群17,每次只处理一个道路网眼内的面状居民地数据,减少无效遍历,提高匹配效率。1.2概率矩阵初始化假设两个待匹配的居民地面实体数据集:setA和 setB。对于 s
12、etA中的每个居民地面实体 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-
13、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、
14、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=ma
15、xo(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概率矩阵的迭代更新兼容系数则反映了目标匹配对和邻近候选匹配对
16、之间的相对关系,而通常邻近候选匹配对不止一个,需要综合考虑全部邻近候选匹配对的兼容系数及其匹配概率值,得到目标匹配对(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+n
17、2+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的匹配关系对应空间变化或地图综合中消失或出现的面实体;1 1的匹配关系对应空间变化中偏移、扩张、收缩和旋转等情况,或者地图综合过程中的移位、夸大、简化等操作;1 M 的匹配关系对应空间变化或地图综合过程中分割或合并的情
18、况,是同名实体匹配算法的重点和难点,比例尺跨度越大,受地图综合的影响就越大,匹配关系就越复杂;M N的匹配关系是同名实体匹配的重要组成部分,也是模糊性最大的部分。例如,在地图综合过程中,对不同比例尺的数据实施典型化操作,在保持初始空间分布的同时,使用小比例尺的较少对象替换大比例尺的对象。基于上述 1 0、1 1、1 M 和 M N 等 4 种匹配关系的理论基础,具体匹配对选取流程如下:1)获取最终概率矩阵每行、每列概率值最大以及概率值大于阈值 1的候选匹配对。若最大值对应匹配到空的情况,且没有其他候选匹配对的概率值大于阈值 1,则选取为 1 0的匹配关系;否则加入队列 Mqueue待进一步检查
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 不同 比例尺 居民地 概率 松弛 匹配 算法 刘洁
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。