留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用松弛标记法进行空间场景匹配

张丁文 陈占龙 谢忠

张丁文, 陈占龙, 谢忠. 利用松弛标记法进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
引用本文: 张丁文, 陈占龙, 谢忠. 利用松弛标记法进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Spatial Scenes Matching with on Relaxation Labeling Approach[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
Citation: ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Spatial Scenes Matching with on Relaxation Labeling Approach[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719

利用松弛标记法进行空间场景匹配

doi: 10.13203/j.whugis20150719
基金项目: 

国家重点研发计划 2017YFC0602204

中央高校基本科研业务费专项资金 CUG160226

地理信息工程国家重点实验室开放基金 SKLGIE2013-Z-4-1

测绘遥感信息工程国家重点实验室资助项目 13I02

国家自然科学基金 41401443

国家自然科学基金 41671400

湖北省自然科学基金重点项目 2015CFA012

详细信息

Spatial Scenes Matching with on Relaxation Labeling Approach

Funds: 

The National Key R & D Program of China 2017YFC0602204

the Fundamental Research Funds for the Central Universities, China University of Geosciences (Wuhan) CUG160226

Open Research Fund of State Key Laboratory of Geography Information Engineering SKLGIE2013-Z-4-1

Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing 13I02

the National Natural Science Foundation of China 41401443

the National Natural Science Foundation of China 41671400

the Natural Science Foundation of Hubei Province of China 2015CFA012

More Information
  • 摘要: 相似性度量是地理学中的关键组成部分,被广泛应用于空间检索、空间信息整合及空间数据挖掘中。因为空间场景中实体个数的差异及空间对象间的关系难以精确相等,若执行空间场景的完全精确匹配,可能会使得检索结果为空。顾及尺度差异,从空间场景中进行空间语义理解,建立了多尺度空间场景的形式化描述模型,并提取场景中稳定的特征构建空间场景特征矩阵。建立场景间的初始匹配概率矩阵后,基于松弛标记法迭代更新概率矩阵,直到矩阵收敛于一全局最小值并确定匹配的实体对,从而进行空间场景相似性评估。采用武汉居民地域数据进行场景匹配实验,并对不同邻域搜索半径下的匹配时间及精确度进行对比与分析,实验结果表明,基于松弛标记法的空间场景匹配方法具有较高的精确度。
  • 图  1  空间查询场景与数据库场景

    Figure  1.  Spatial Query Scene and Database Scene

    图  2  检索场景A和候选场景B

    Figure  2.  Query Scene A and Candidate Scene B

    图  3  从武汉居民地域数据中搜索出与场景A匹配的空间范围

    Figure  3.  Search the Matched Scene of Scene A from Wuhan Residential Region Data

    图  4  实体a1在5次迭代中与不同实体匹配的概率及概率曲线的变化过程

    Figure  4.  Matching Probabilities and Curves of a1 in the Five Iterations

    图  5  不同邻域范围半径所搜索到的邻域实体数量

    Figure  5.  Object Quantities in Neighborhood for Different Neighborhood Searching Radius

    表  1  场景AB间实体对的匹配概率

    Table  1.   Matching Probabilities of Object Pairs Between Scenes A and B

    实体对 匹配率
    A0 B0 A0 B1 A0 B2 A1 B0 A1 B1 A1 B2 A2 B0 A2 B1 A2 B2
    p0 0.173 0.089 6 0.060 7 0.099 5 0.158 6 0.088 5 0.079 3 0.105 1 0.145 6
    s0 0.132 3 0.106 7 0.089 1 0.069 8 0.138 6 0.102 3 0.121 0.095 4 0.144 3
    p1 0.196 3 0.081 9 0.03 0.062 7 0.188 5 0.056 4 0.091 7 0.064 9 0.18
    p3 0.3 0.034 8 0.006 9 0.002 3 0.3 0.034 8 0.004 6 0.186 0.297 6
    下载: 导出CSV

    表  2  实验数据基本情况

    Table  2.   Introduction of Experiment Data

    数据集 点数量 区数量 总面积/km2
    武汉市居民地域数据 47 112 1 576 146.05
    空间场景A 292 5 3.63
    下载: 导出CSV

    表  3  不同邻域范围半径下的匹配正确度

    Table  3.   Matching Accuracy Under Different Neighborhood Searching Radius

    半径 半径1 半径2 半径3 半径4
    正确度 100% 100% 0 0
    下载: 导出CSV
  • [1] Mark D M, Comas D, Egenhofer M J, et al. Evaluating and Refining Computational Models of Spatial Relations Through Cross-Linguistic Human-Subjects Testing[C]. International Conference on Spatial Information Theory, Vienna, Austria, 1995
    [2] Unwin D J, Doornkamp J C. Introductory Spatial Analysis[J]. Parallel Problem Solving from Nature, 2010, 36(10):1307-1319
    [3] Rodríguez M A, Egenhofer M J. Determining Semantic Similarity Among Entity Classes from Different Ontologies[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(2):442-456 doi:  10.1109/TKDE.2003.1185844
    [4] Andrea M, Egenhofer M J. Comparing Geospatial Entity Classes:An Asymmetric and Context-dependent Similarity Measure[J]. International Journal of Geographical Information Science, 2004, 18(3):229-256 doi:  10.1080/13658810310001629592
    [5] Nabil M, Ngu A H H, Shepherd J. Picture Similarity Retrieval Using the 2D Projection Interval Representation[J]. IEEE Transactions on Knowledge & Data Engineering, 1996(4):533-539
    [6] Petrakis E G M, Faloutsos C. Similarity Searching in Medical Image Databases[J]. IEEE Transactions on Knowledge and Data Engineering, 1997, 9(3):435-447 doi:  10.1109/69.599932
    [7] Li Bonan, Fonseca F. TDD:A Comprehensive Model for Qualitative Spatial Similarity Assessment[J]. Spatial Cognition & Computation, 2006, 6(1):31-62
    [8] Papadias D, Delis V. Relation-Based Similarity[C]. ACM Workshop on GIS, Las Vegas, USA, 1997
    [9] Bruns T, Egenhofer M. Similarity of Spatial Scenes[C]. The 7th International Symposium on Spatial Data Handling. Delft, the Netherlands, 1996
    [10] Frank A U. Qualitative Spatial Reasoning:Cardinal Directions as an Example[J]. International Journal of Geographical Information Science, 1996, 10(3):269-290 doi:  10.1080/02693799608902079
    [11] 陈占龙, 周林, 龚希, 等.基于方向关系矩阵的空间方向相似性定量计算方法[J].测绘学报, 2015, 44(7):813-821 doi:  10.11947/j.AGCS.2015.20140198

    Chen Zhanlong, Zhou Lin, Gong Xi, et al. A Quantitative Calculation Method of Spatial Direction Similarity Based on Direction Relation Matrix[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(7):813-821 doi:  10.11947/j.AGCS.2015.20140198
    [12] 刘涛, 杜清运, 毛海辰.空间线群目标相似度计算模型研究[J].武汉大学学报·信息科学版, 2012, 37(8):992-995 http://ch.whu.edu.cn/CN/Y2012/V37/I8/992

    Liu Tao, Du Qingyun, Mao Haichen. Spatial Similarity Assessment Model and its Application in Line Groups[J]. Geomatics and Information Science of Wuhan University, 2012, 37(8):992-995 http://ch.whu.edu.cn/CN/Y2012/V37/I8/992
    [13] Bruns H T, Egenhofer M J. Similarity of Spatial Scenes[J]. Spatial Data Handling, 1996(8):31-42
    [14] Christmas W J, Kittler J, Petrou M. Structural Matching in Computer Vision Using Probabilistic Relaxation[M]. New York:IEEE Computer Society, 1995
    [15] Lee J H, Won C H. Topology Preserving Relaxation Labeling for Nonrigid Point Matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(2):427-432 doi:  10.1109/TPAMI.2010.179
    [16] 岳春宇, 江万寿.一种利用级联滤波和松弛法的SAR图像配准方法[J].武汉大学学报·信息科学版, 2012, 37(1):43-45 http://ch.whu.edu.cn/CN/Y2012/V37/I1/43

    Yue Chunyu, Jiang Wanshou. Registration Method for SAR Image Based on Cascade Filter and Relaxation Optimization Algorithm[J]. Geomatics and Information Science of Wuhan University, 2012, 37(1):43-45 http://ch.whu.edu.cn/CN/Y2012/V37/I1/43
  • [1] 张嘉琪, 杜开虎, 任书良, 王瑞凡, 关庆锋, 陈文辉, 姚尧.  多源空间大数据场景下的家装品牌线下广告选址 . 武汉大学学报 ● 信息科学版, 2022, 47(9): 1406-1415. doi: 10.13203/j.whugis20190468
    [2] 李维炼, 朱军, 张昀昊, 付林, 胡亚, 尹灵芝, 戴义.  空间语义约束的泥石流灾害VR场景融合建模及交互方法 . 武汉大学学报 ● 信息科学版, 2020, 45(7): 1073-1081. doi: 10.13203/j.whugis20180329
    [3] 刘英, 吴立新, 岳辉.  基于梯度结构相似度的矿区土壤湿度空间分析 . 武汉大学学报 ● 信息科学版, 2018, 43(1): 87-93. doi: 10.13203/j.whugis20160216
    [4] 陈占龙, 张丁文, 谢忠, 吴亮.  利用多等级相关性反馈进行空间场景匹配 . 武汉大学学报 ● 信息科学版, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
    [5] 陈占龙, 吕梦楼, 吴亮, 徐永洋.  基于特征矩阵和关联图的空间场景相似性度量方法 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
    [6] 杨静, 程昌秀, 李晓岚, 陈驰.  网络结构空间格局相似度分析——以1938~2014年北京市骨干交通网络为例 . 武汉大学学报 ● 信息科学版, 2016, 41(12): 1593-1598. doi: 10.13203/j.whugis20140569
    [7] 路志越, F.Benjamin Zhan, 鄂栋臣.  PSHA模型的算法改进与中国地区未来地震概率评估 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 349-352.
    [8] 许俊奎, 武芳, 钱海忠, 马芳博.  一种空间关系相似性约束的居民地匹配算法 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 484-485.
    [9] 刘涛, 杜清运, 毛海辰.  空间线群目标相似度计算模型研究 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 992-995.
    [10] 刘涛, 杜清运, 闫浩文.  空间点群目标相似度计算 . 武汉大学学报 ● 信息科学版, 2011, 36(10): 1149-1153.
    [11] 王培超, 朱欣焰, 苏科华, 陈静.  分布式空间数据标记语言的研究与实现 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 659-662.
    [12] 洪梓璇, 边馥苓.  基于支持度矩阵的Apriori改进算法 . 武汉大学学报 ● 信息科学版, 2008, 33(12): 1246-1249.
    [13] 一种基于空间虚拟场景的森林冠层雷达相干散射模型 . 武汉大学学报 ● 信息科学版, 2008, 33(2): 120-123.
    [14] 张煜, 孙家, 张晓东.  一种基于距离变换与标记图的边缘匹配方法 . 武汉大学学报 ● 信息科学版, 2006, 31(8): 675-678.
    [15] 刘耀林, 傅佩红.  Kriging空间分析法及其在地价评估中的应用 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 471-474.
    [16] 仇彤.  基于小波变换的松弛法影像匹配 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 145-148.
    [17] 潘励, 张剑清.  道路断线自动连接的概率松弛方法 . 武汉大学学报 ● 信息科学版, 1997, 22(4): 318-321.
    [18] 沈未名, 张祖勋, 张剑清.  基于神经网络的影像匹配概率松弛算法 . 武汉大学学报 ● 信息科学版, 1996, 21(3): 247-251.
    [19] 仇彤, 张祖勋.  基于松弛法的影像边缘提取 . 武汉大学学报 ● 信息科学版, 1994, 19(4): 322-327.
    [20] 于晓江, 栾胜奎, 朱光世.  测量球面无标记物体定轴转动角位移的客观散斑法 . 武汉大学学报 ● 信息科学版, 1993, 18(4): 88-93.
  • 加载中
图(5) / 表(3)
计量
  • 文章访问数:  959
  • HTML全文浏览量:  60
  • PDF下载量:  295
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-08-25
  • 刊出日期:  2018-05-05

利用松弛标记法进行空间场景匹配

doi: 10.13203/j.whugis20150719
    基金项目:

    国家重点研发计划 2017YFC0602204

    中央高校基本科研业务费专项资金 CUG160226

    地理信息工程国家重点实验室开放基金 SKLGIE2013-Z-4-1

    测绘遥感信息工程国家重点实验室资助项目 13I02

    国家自然科学基金 41401443

    国家自然科学基金 41671400

    湖北省自然科学基金重点项目 2015CFA012

    作者简介:

    张丁文, 博士, 主要研究方向为空间分析基础算法、空间场景相似性等。dingwenzhang@yahoo.com

    通讯作者: 陈占龙, 博士, 副教授。Chenzhanlong2005@126.com
  • 中图分类号: P208

摘要: 相似性度量是地理学中的关键组成部分,被广泛应用于空间检索、空间信息整合及空间数据挖掘中。因为空间场景中实体个数的差异及空间对象间的关系难以精确相等,若执行空间场景的完全精确匹配,可能会使得检索结果为空。顾及尺度差异,从空间场景中进行空间语义理解,建立了多尺度空间场景的形式化描述模型,并提取场景中稳定的特征构建空间场景特征矩阵。建立场景间的初始匹配概率矩阵后,基于松弛标记法迭代更新概率矩阵,直到矩阵收敛于一全局最小值并确定匹配的实体对,从而进行空间场景相似性评估。采用武汉居民地域数据进行场景匹配实验,并对不同邻域搜索半径下的匹配时间及精确度进行对比与分析,实验结果表明,基于松弛标记法的空间场景匹配方法具有较高的精确度。

English Abstract

张丁文, 陈占龙, 谢忠. 利用松弛标记法进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
引用本文: 张丁文, 陈占龙, 谢忠. 利用松弛标记法进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Spatial Scenes Matching with on Relaxation Labeling Approach[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
Citation: ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Spatial Scenes Matching with on Relaxation Labeling Approach[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
  • 相似性度量是地理学中的关键组成部分[1],是设计像人一样反应和行动的智能地理信息系统的基础,使用机器执行相似性度量的难点在于将定性的相似性描述转换为范围在0(最差匹配)和1(最佳匹配)之间的定量相似度。在过去的几十年中,空间相似性研究逐渐从基于性质如模式、密度和分布等[2]转向基于内容的图像检索和地理数据库中基于草图的空间检索上[3-4]

    空间场景匹配的核心问题在于将一个场景的对象和关系与另一个场景的对象和关系联系起来,因此场景间的匹配识别原则尤为重要。在大部分的空间场景相似度量研究中,常假设两个场景具有相等的对象数量[5]或对象数量相对较少(如小于10)[6-7],或过于关注空间关系而忽略对象本身,如基于关系相似度计算场景相似度的概念邻域方法[8-9]和基于投影方法[10-11],或选择具有最高相似度的对象互相匹配而忽略空间关系[12],又或者假设事先知道场景对象间的对应关系[13],并计算从一个场景转换为另一个场景所需的离散渐变数量,从而衡量场景间的相异度。

    在地理数据库中,只有少数空间场景可以进行精确匹配,因为空间对象间的关系会稍有不同,方向和距离难以精确相等,而且形状间的差别会相当大,因此严格执行精确匹配会使得检索结果几乎为空。本文基于松弛标记法[14-15]提出了一种结合空间实体几何特征及空间关系进行场景相似性评估的方法,基于邻域对象支持度迭代更新匹配概率矩阵直到收敛于某一全局极小值,并选择具有最高匹配概率的实体对,以实现对匹配场景的搜索。由于空间关系及几何描述都不涉及度量单位,因此该方法能满足具有不同比例尺及投影坐标系(即多尺度)的空间场景间的相似性计算。

    • 松弛标记法[15]是采用符号来描述图像特征的识别方法,其中,处理对象称为目标,描述目标的符号称为标记,先给定目标一组初始标记,通过迭代运算逐次更新标记,最后求得这组目标的确切标记集。采用松弛标记法能将多种约束有效结合且不受实体数目的影响,目前其在空间场景中的主要应用为城市道路网匹配及遥感影像匹配[16]等。

      松弛标记法中存在一个结点集合和一个标记集合,其中每个结点与一组标记相关联,标记与结点的匹配情况称为匹配度。设当前有n个结点,每个结点关联着同样的标记集Λ={λ| λ =1…m},pi(λ)为标记λ与结点i的匹配度,且满足式(1):

      $$ \sum\limits_{\lambda = 1}^m {{p_i}\left( \lambda \right)} = 1,i = 1,2 \cdots n $$ (1)

      标记与其邻域间的一致度可通过标记支持度进行度量,描述为邻域中其他标记的最佳结点匹配度及邻域对此标记匹配情况兼容度的函数。标记间的约束表示为兼容系数rij(λ, λ′),指的是与结点j相关联标记λ′及与结点i相关联标记λ间的兼容度。根据邻域标记的匹配度及兼容系数,标记λ在结点i处的邻域支持si(λ)度被定义为:

      $$ {s_i}\left( \lambda \right) = \sum\limits_{j = 1}^n {\sum\limits_{\lambda ' = 1}^m {{r_{ij}}\left( {\lambda ,\lambda '} \right){p_j}\left( {\lambda '} \right)} } $$ (2)

      若标记网络中每个结点都满足匹配度向量与邻域支持度向量一致,此标记过程满足一致性[15],即:

      $$ {\mathit{\boldsymbol{p}}_i} = \frac{{{\mathit{\boldsymbol{s}}_i}}}{{\left( {{\mathit{\boldsymbol{s}}_i} \cdot \mathit{\boldsymbol{1}}} \right)}} $$ (3)

      若尚未满足一致性,在随后的迭代中,需将标准化的邻域支持度向量直接分配给匹配度向量,并继续进行迭代。

      $$ \mathit{\boldsymbol{p}}_i^{k + 1} = \mathit{\boldsymbol{s}}_i^k $$ (4)
    • 图 1为例,检索场景中有xyz三个空间实体,现需从数据库场景(包含实体abcd)中找出对应实体。基于描述场景的特征向量集,可初步计算出检索对象与数据库对象的空间关系相似度矩阵(见式(5)),如Pxy, abv1指的是空间实体对(x, y)和(a, b)在空间关系特征向量v1上的相似度。

      $$ \left[ {\begin{array}{*{20}{c}} {P_{xy,ab}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{xy,ac}^{{\mathit{\boldsymbol{v}}_1}}}& \cdots &{P_{xy,cd}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{xz,ab}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{xz,ac}^{{\mathit{\boldsymbol{v}}_1}}}& \cdots &{P_{xz,cd}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{yz,ab}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{yz,ac}^{{\mathit{\boldsymbol{v}}_1}}}& \cdots &{P_{yz,cd}^{{\mathit{\boldsymbol{v}}_1}}}\\ {P_{xy,ab}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{xy,ac}^{{\mathit{\boldsymbol{v}}_2}}}& \cdots &{P_{xy,cd}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{xz,ab}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{xz,ac}^{{\mathit{\boldsymbol{v}}_2}}}& \cdots &{P_{xz,cd}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{yz,ab}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{yz,ac}^{{\mathit{\boldsymbol{v}}_2}}}& \cdots &{P_{yz,cd}^{{\mathit{\boldsymbol{v}}_2}}}\\ \vdots &{}&{}&{}&{}&{}&{}&{}&{}&{}&{}& \vdots \\ {P_{xy,ab}^{{\mathit{\boldsymbol{v}}_N}}}&{P_{xy,ac}^{{\mathit{\boldsymbol{v}}_N}}}& \cdots &{P_{xy,cd}^{{\mathit{\boldsymbol{v}}_N}}}&{P_{xz,ab}^{{\mathit{\boldsymbol{v}}_N}}}&{P_{xz,ac}^{{\mathit{\boldsymbol{v}}_N}}}& \cdots &{P_{xz,cd}^{{\mathit{\boldsymbol{v}}_N}}}&{P_{yz,ab}^{{\mathit{\boldsymbol{v}}_N}}}&{P_{yz,ac}^{{\mathit{\boldsymbol{v}}_N}}}& \cdots &{P_{yz,cd}^{{\mathit{\boldsymbol{v}}_N}}} \end{array}} \right] $$ (5)

      图  1  空间查询场景与数据库场景

      Figure 1.  Spatial Query Scene and Database Scene

      建立空间实体匹配概率矩阵需要考虑实体对的几何相似度。由于每对空间关系(aibs, ajbt)存在着两种可能的匹配形式(aibs, ajbt)或(aibt, ajbs),因此需要分别计算实体对(ai, bs)、(ai, bt)、(aj, bs)和(aj, bt)的几何相似度,并选择相似度最高的两对匹配形式,这个过程以g(aiaj, btbs)表示。对实体间的匹配概率p进行如式(6)所定义的计算,g(aibj, btbs)的结果为两对几何相似度最高的实体,因此可得到两对实体的匹配概率p1p2

      $$ \begin{array}{l} p\left( {{a_i}{a_j},{b_t}{b_s}} \right) = \left( {{p_1},{p_2}} \right) = \\ L\left( {{a_i}{a_j},{b_t}{b_s}} \right) \times g\left( {{a_i}{a_j},{b_t}{b_s}} \right) \end{array} $$ (6)

      式中,L为空间关系度。实际运算中,某一实体对的匹配概率会被重复计算,但由于存在于不同的空间关系中,其概率会受到不同程度的影响,本文取所有概率的平均值作为初始匹配概率(式(7)),l为实体对可能概率值的个数。

      $$ p_{\left( {x,a} \right)}^{{v_i}} = \frac{{p_{\left( {x,a} \right)1}^{{v_i}} + p_{\left( {x,a} \right)2}^{{v_i}} + \cdots + p_{\left( {x,a} \right)l}^{{v_i}}}}{l} $$ (7)

      最后得到场景间的初始概率矩阵P,并在迭代更新前对P进行标准化操作。

      $$ \mathit{\boldsymbol{P}} = \left[ {\begin{array}{*{20}{c}} {{p_{\left( {x,a} \right)}}}&{{p_{\left( {x,b} \right)}}}&{{p_{\left( {x,c} \right)}}}&{{p_{\left( {x,d} \right)}}}\\ {{p_{\left( {y,a} \right)}}}&{{p_{\left( {y,b} \right)}}}&{{p_{\left( {y,c} \right)}}}&{{p_{\left( {y,d} \right)}}}\\ {{p_{\left( {z,a} \right)}}}&{{p_{\left( {z,b} \right)}}}&{{p_{\left( {z,c} \right)}}}&{{p_{\left( {z,d} \right)}}} \end{array}} \right] $$ (8)
    • 实体aibj配对时,应存在bj的邻域对象btai的邻域对象as,使得(bj, bt)与(ai, as)一致。设ahbk是不同于aibj的任意实体,并设δaibj(ah, bk)为aibj匹配时对象ahbk间的相似度(也称兼容系数)。(ah, bk)对(ai, bj)的兼容系数主要包括匹配概率p(ah, bk)及实体对{(ai, ah), (bk, bj)}的空间关系度L(aiah, bjbk)两部分(式(9))。

      $$ {\delta _{{a_i}{b_j}}} = \left( {{a_h},{b_k}} \right) = L\left( {{a_i}{a_h},{b_j}{b_k}} \right) \times p\left( {{a_h},{b_k}} \right) $$ (9)

      δaibj(ah, bk)为1,则(ah, ai)与(bk, bj)相对应,此时(ah, bk)给予(ai, bj)最大的匹配支持,反之亦然。aibj匹配时,对于ai邻域实体ahbj邻域中的若干邻近对象都有匹配的可能,只需选择与ah具有最大相似度的bk,从而ah对(ai, bj)的支持度为:

      $$ \mathop {\max }\limits_{k \ne j} \left( {\left| {{\delta _{{a_i}{b_j}}}\left( {{a_h},{b_k}} \right)} \right|} \right) $$ (10)

      同理可计算ai每个邻域实体对于(ai, bj)的支持度,为获取ai邻域的总支持度,本文取ai所有邻域实体支持度的平均值:

      $$ {s^{\left( 1 \right)}}\left( {{a_i},{b_j}} \right) = \frac{{\sum\limits_{h \ne i} {\left[ {\mathop {\max }\limits_{k \ne j} \left( {\min \left( {\left| {{\delta _{{a_i}{b_j}}}\left( {{a_h},{b_k}} \right)} \right|,{s^{\left( 0 \right)}}\left( {{a_h},{b_k}} \right)} \right)} \right)} \right]} }}{{\left( {m - 1} \right)}} $$ (11)

      对此过程进行迭代,第r次迭代时有:

      $$ {s^{\left( r \right)}}\left( {{a_i},{b_j}} \right) = \frac{{\sum\limits_{h \ne i} {\left[ {\mathop {\max }\limits_{k \ne j} \left( {\min \left( {\left| {{\delta _{{a_i}{b_j}}}\left( {{a_h},{b_k}} \right)} \right|,{s^{\left( {r - 1} \right)}}\left( {{a_h},{b_k}} \right)} \right)} \right)} \right]} }}{{\left( {m - 1} \right)}} $$ (12)

      由于相似概率总是小于或等于1,s(1)内的每个值必然小于或等于s(0)中的相应值;依次类推,s(r)(ai, bj)为单调不自增的非负序列。对于n个待匹配的空间实体,场景间实体初始匹配概率计算的复杂度为O(n2),而概率松弛标记法中单次迭代的时间复杂度为O(n2),因此基于松弛标记法的空间场景匹配运算计算复杂度为O(n2)。

    • 图 2中场景AB间的匹配过程进行分析,AB间共存在6种可能的匹配形式。表 1p0描述了标准化后实体对的初始匹配概率,s0为实体对的邻域支持度。

      图  2  检索场景A和候选场景B

      Figure 2.  Query Scene A and Candidate Scene B

      表 1  场景AB间实体对的匹配概率

      Table 1.  Matching Probabilities of Object Pairs Between Scenes A and B

      实体对 匹配率
      A0 B0 A0 B1 A0 B2 A1 B0 A1 B1 A1 B2 A2 B0 A2 B1 A2 B2
      p0 0.173 0.089 6 0.060 7 0.099 5 0.158 6 0.088 5 0.079 3 0.105 1 0.145 6
      s0 0.132 3 0.106 7 0.089 1 0.069 8 0.138 6 0.102 3 0.121 0.095 4 0.144 3
      p1 0.196 3 0.081 9 0.03 0.062 7 0.188 5 0.056 4 0.091 7 0.064 9 0.18
      p3 0.3 0.034 8 0.006 9 0.002 3 0.3 0.034 8 0.004 6 0.186 0.297 6

      邻域支持度对实体对的相似度产生直接影响,在第r次迭代时,bjai的概率如式13所示。

      $$ \begin{array}{l} {p^{\left( {r + 1} \right)}}\left( {{a_i},{b_j}} \right) = \\ {p^{\left( r \right)}}\left( {{a_i},{b_j}} \right) \times {s^{\left( r \right)}}\left( {{a_i},{b_j}} \right),r = 1,2,3 \cdots n \end{array} $$ (13)

      p1是第一次迭代后的匹配概率,p3则是3次迭代后的结果,观察到(A0, B0)、(A1, B1)和(A2, B2)的匹配概率相对p1产生了持续增长,而其他实体对则明显收敛,因为在矩阵的迭代过程中,正确匹配对的概率增长是以不正确匹配对的概率削减为前提的。若采用实体相似度之和作为场景匹配值,按匹配度从高到低对场景排序为:{(A0, B0), (A1, B1), (A2, B2)}→{(A0, B0), (A1, B2), (A2, B1)}→{(A0, B1), (A1, B2), (A2, B0)}→{(A0, B1), (A1, B0), (A2, B2)}→{(A0, B2), (A1, B1), (A2, B0)}→{(A0, B2), (A1, B0), (A2, B1)}。

    • 采用本文方法,从武汉居民地域数据中检索出与场景A一致的空间场景(见图 3)。武汉居民地域数据从武汉数据集中获取,场景A数据则由国家GIS工程技术研究中心提供,相关属性如表 2所示。场景A的点、区数量和空间范围都远小于居民地域数据,从1 576个区中检索出场景A中5个区的可能性约为8.050 8×1013种。

      图  3  从武汉居民地域数据中搜索出与场景A匹配的空间范围

      Figure 3.  Search the Matched Scene of Scene A from Wuhan Residential Region Data

      表 2  实验数据基本情况

      Table 2.  Introduction of Experiment Data

      数据集 点数量 区数量 总面积/km2
      武汉市居民地域数据 47 112 1 576 146.05
      空间场景A 292 5 3.63

      居民地域数据中,对象间的拓扑关系构成单一(相离关系),对象形状较为规范(四边形),因此选择方向关系和对象几何形状作为参照场景的描述参数,计算出每对空间对象的初始匹配概率后,再根据其邻域对象群的支持度对其进行迭代调整,可得出较为精确的匹配结果。本文使用笛卡尔方向关系描述空间对象间的方向关系,空间对象的几何特征可通过傅里叶算子进行分析。

    • 首先计算两个场景间空间对象的初始匹配概率,ai(0≤i < 5)表示场景A中的对象,bj(0≤j < 1 576)表示地域数据中的对象,可得初始匹配概率矩阵:

      $$ \begin{array}{l} \;\;\;\;\;\;\;\;\;{b_0}\;\;\;\;\;\;\;\;\;\;{b_1}\;\;\;\;\;\;\; \cdots \;\;\;\;\;\;{b_{430}}\;\;\;\;\;{b_{431}}\;\;\;\;\;\;\;\;{b_{432}}\;\;\;\;\;\;\;{b_{433}}\;\;\;\;\;\; \cdots \;\;\;\;\;\;{b_{437}}\;\;\;\;\; \cdots \\ \begin{array}{*{20}{c}} {{a_0}}\\ {{a_1}}\\ {{a_2}}\\ {{a_3}}\\ {{a_4}} \end{array}\left[ {\begin{array}{*{20}{c}} {0.9876}&{0.6047}& \cdots &{0.9869}&{0.9844}&{0.9969}&{0.9938}& \cdots &{1.0000}& \cdots \\ {0.9898}&{0.4768}&{}&{0.9979}&{1.0000}&{0.9847}&{0.9664}&{}&{0.9844}&{}\\ {0.9738}&{0.6254}&{}&{0.9721}&{0.9664}&{0.9933}&{1.0000}&{}&{0.9938}&{}\\ {0.9888}&{0.5801}&{}&{0.9848}&{0.9847}&{1.0000}&{0.9933}&{}&{0.9969}&{}\\ {0.9906}&{0.4837}& \cdots &{1.0000}&{0.9979}&{0.9894}&{0.9721}& \cdots &{0.9869}& \cdots \end{array}} \right] \end{array} $$

      分别计算每一匹配对的邻域支持度,以(a0, b0)为例,a0邻域对象为a1a2a3a4,为a1选择匹配对象时要将b0排除在外,并比较所有实体对(a1, bj)(1≤j≤1 575)的匹配概率,从中选择概率最大的对象,对每一邻域对象重复此过程。计算a0的邻域支持度,并更新(a0, b0)的匹配概率, 若干次迭代更新后,概率值为:

      $$ \begin{array}{l} \;\;\;\;\;\;\;\;\;{b_0}\;\;\;\;\;\;\;\;\;\;{b_1}\;\;\;\;\;\;\; \cdots \;\;\;\;\;\;{b_{430}}\;\;\;\;\;{b_{431}}\;\;\;\;\;\;\;\;{b_{432}}\;\;\;\;\;\;\;{b_{433}}\;\;\;\;\;\; \cdots \;\;\;\;\;\;{b_{437}}\;\;\;\;\; \cdots \\ \begin{array}{*{20}{c}} {{a_0}}\\ {{a_1}}\\ {{a_2}}\\ {{a_3}}\\ {{a_4}} \end{array}\left[ {\begin{array}{*{20}{c}} {0.0002}&{0.0001}& \cdots &{0.9765}&{0.9667}&{0.9873}&{0.8994}& \cdots &{1.0000}& \cdots \\ {0.0002}&{0.0001}&{}&{0.9875}&{1.0000}&{0.9753}&{0.8504}&{}&{0.8821}&{}\\ {0.0001}&{0.0001}&{}&{0.9619}&{0.9491}&{0.9838}&{1.0000}&{}&{0.8960}&{}\\ {0.0002}&{0.0001}&{}&{0.9790}&{0.9671}&{1.0000}&{0.9423}&{}&{0.9631}&{}\\ {0.0002}&{0.0001}& \cdots &{1.0000}&{0.9821}&{0.9799}&{0.8608}& \cdots &{0.8899}& \cdots \end{array}} \right] \end{array} $$ (14)
    • 图 4展示了实体a1在5次迭代中与不同实体匹配的概率及概率曲线的变化过程。对于实体a1,在匹配过程中,a1和实体b438的匹配概率一直保持在较高的水平且在5次迭代后停留在一个稳定的值。同理,实体a2与实体b432存在一对一的匹配关系,实体a3的对应实体是b435a4b433相匹配,而a5则与实体b431相对应。

      图  4  实体a1在5次迭代中与不同实体匹配的概率及概率曲线的变化过程

      Figure 4.  Matching Probabilities and Curves of a1 in the Five Iterations

      邻域搜索半径对匹配运算的效率及准确度存在影响,半径过大会使邻域范围增大,增加计算时间;半径过小会使应有的邻域对象没被选中而影响准确度。本文采用4组不同的邻域半径进行匹配运算并对比计算时间和结果,分别为实体外包矩形的对角线长度(半径1)、中心到对角长度(半径2)、中心到长边距离(半径3)、中心到短边距离(半径4)。

      4个半径对应的邻域实体数量相差较大(见图 5),表 3是不同半径对应的运算准确度,其中半径1、2的匹配正确度为100%,而半径3、4却为0。由于半径3、4的邻域范围较小,无法将足够对象纳入邻域范围,导致正确匹配对的邻域支持度较小,该硬性误差在迭代运算中影响了全局正确性。

      图  5  不同邻域范围半径所搜索到的邻域实体数量

      Figure 5.  Object Quantities in Neighborhood for Different Neighborhood Searching Radius

      表 3  不同邻域范围半径下的匹配正确度

      Table 3.  Matching Accuracy Under Different Neighborhood Searching Radius

      半径 半径1 半径2 半径3 半径4
      正确度 100% 100% 0 0
    • 本文提出了一种基于松弛标记法的场景相似性评估方法,通过邻域支持度迭代更新匹配概率矩阵直到收敛于某一极小值,从而得到实体间的最终相似度。本文方法包括概率矩阵初始化、概率矩阵迭代更新和相似场景确定3个步骤。本文选取了武汉居民地域数据进行空间场景的匹配实验,尝试从地域数据中搜索出与某空间场景匹配的空间范围,并对算法的迭代更新过程进行了分析,对不同邻域搜索半径范围下的实验结果及时间进行了对比。实验数据表明,在合适的邻域范围下进行场景匹配计算可得到精确性较高的匹配结果,且在平衡计算精确性与运算时间之间的关系时需按照实际情况决定。

      由于空间数据的多样性及运算中存在各种难以预料的误差,且使用机器进行匹配难以根据不同情况及时进行运算策略的调整,因此下一步的工作将是:(1)将松弛标记法应用到存在点、线等空间类型实体的空间场景匹配中; (2)将用户反馈阶段加入空间场景匹配运算过程中。

参考文献 (16)

目录

    /

    返回文章
    返回