留言板

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

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

基于特征矩阵和关联图的空间场景相似性度量方法

陈占龙 吕梦楼 吴亮 徐永洋

陈占龙, 吕梦楼, 吴亮, 徐永洋. 基于特征矩阵和关联图的空间场景相似性度量方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
引用本文: 陈占龙, 吕梦楼, 吴亮, 徐永洋. 基于特征矩阵和关联图的空间场景相似性度量方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
CHEN Zhanlong, LV Menglou, WU Liang, XU Yongyang. Space Scene Similarity Metrics Based on Feature Matrix and Associated Graph[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
Citation: CHEN Zhanlong, LV Menglou, WU Liang, XU Yongyang. Space Scene Similarity Metrics Based on Feature Matrix and Associated Graph[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450

基于特征矩阵和关联图的空间场景相似性度量方法

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

国家自然科学基金 41401443

国家科技支撑计划 2011BAH06B04

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

武汉大学测绘遥感信息工程国家重点实验室开放研究基金 13I02

中央高校基本科研业务费专项 CUG16022

详细信息
    作者简介:

    陈占龙, 博士, 副教授, 研究方向为空间分析算法、空间推理、地理信息系统软件开发与应用。chenzhanlong2005@126.com

    通讯作者: 吴亮, 博士, 副教授。wuliang133@189.cn
  • 中图分类号: P208

Space Scene Similarity Metrics Based on Feature Matrix and Associated Graph

Funds: 

The National Natural Science Foundation of China 41401443

the National Science and Technology Support Program of China 2011BAH06B04

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

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

the Research Funds for the Central Universities Basic Special Projects CUG16022

More Information
    Author Bio:

    CHEN Zhanlong, associate professor, PhD, specializes in spatial analysis algorithms, spatial reasoning, GIS, etc. E-mail:chenzhanlong2005@126.com

    Corresponding author: WU Liang, PhD, associate professor. E-mail:wuliang133@189.cn
图(6) / 表(4)
计量
  • 文章访问数:  1301
  • HTML全文浏览量:  77
  • PDF下载量:  448
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-03-30
  • 刊出日期:  2017-07-05

基于特征矩阵和关联图的空间场景相似性度量方法

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

    国家自然科学基金 41401443

    国家科技支撑计划 2011BAH06B04

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

    武汉大学测绘遥感信息工程国家重点实验室开放研究基金 13I02

    中央高校基本科研业务费专项 CUG16022

    作者简介:

    陈占龙, 博士, 副教授, 研究方向为空间分析算法、空间推理、地理信息系统软件开发与应用。chenzhanlong2005@126.com

    通讯作者: 吴亮, 博士, 副教授。wuliang133@189.cn
  • 中图分类号: P208

摘要: 为了解决包含不同实体数目的空间场景相似性度量问题,本文利用特征矩阵对空间场景进行描述,根据查询场景和数据库场景的特征矩阵生成场景关联图,利用关联图中的各种匹配圈获取空间场景集合,然后根据场景完整度和相似性度量模型计算场景集合中每个场景的匹配度,最后计算出最佳匹配场景,并对匹配结果进行分析评价。实验表明,该方法能够较好地度量不同实体数目的空间场景的相似性。

English Abstract

陈占龙, 吕梦楼, 吴亮, 徐永洋. 基于特征矩阵和关联图的空间场景相似性度量方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
引用本文: 陈占龙, 吕梦楼, 吴亮, 徐永洋. 基于特征矩阵和关联图的空间场景相似性度量方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
CHEN Zhanlong, LV Menglou, WU Liang, XU Yongyang. Space Scene Similarity Metrics Based on Feature Matrix and Associated Graph[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
Citation: CHEN Zhanlong, LV Menglou, WU Liang, XU Yongyang. Space Scene Similarity Metrics Based on Feature Matrix and Associated Graph[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
  • 空间场景相似性度量是根据空间场景中实体的几何特征[1-3]、空间关系[4-6]和语义特征[7-8]等对不同空间场景的相似程度进行度量的一种方法,研究空间场景相似性度量方法对未来智能化的地理信息检索模式具有重要意义。

    Egenhofer[9]首次利用草图进行空间数据的查询,提出一种运用拓扑关系概念邻域图和方向关系概念邻域图的描述方法。文献[10]在基于Egenhofer的基础上将模糊技术引入到概念邻域图中,利用拓扑关系对不同空间场景进行相似性度量。Papadias[11]定义了实体间方位、距离、拓扑关系的相似程度,提出了一种空间场景相似性的计算方法。文献[12]利用实体间的空间关系构建特征矩阵,采用独立成分分析和模糊支持向量机方法对空间场景进行了检索。文献[13]加入了空间场景的目标层次关系,提出了基于元空间关系的拓扑相似性度量方法。文献[14]基于方向关系矩阵对实体间的方向关系相似性进行了深入研究。文献[15]通过空间关系对居民地匹配进行了相关研究。现有的空间场景相似性度量,大都仅能对相同实体数目的空间场景进行度量,针对这一问题,本文试图从实体的几何特征和空间关系出发研究任意实体数目的空间场景相似性度量方法,该方法自动提取空间场景,并实现对不同实体数目的空间场景的相似性度量。

    • 几何特征通过Freeman链码[16]或傅里叶算子[17-18]来获取, 空间关系特征通过实体间的方位、距离、拓扑关系来获取,其中方位关系特征向量可以通过方位关系矩阵[19]获取,距离关系特征向量通过距离关系矩阵获取,拓扑关系特征向量通过9-交集矩阵[20]获取,以方向关系特征向量的提取为例,根据方向关系的9种方向,可以从包含两个实体AB的空间场景S中获取方向关系特征向量PAB = {PAB1, PAB2, …, PAB9}。

      图 1所示,图 1(a)中的空间场景S有4个实体ABCD,以方向关系特征向量为例,可以获取空间场景的特征向量PAB = {PAB1, PAB2, …, PAB9},根据两两配对原则,再加上实体本身,可以得到场景S的特征向量PABPACPADPBCPBDPCDPAAPBBPCCPDD,即可得到空间场景特征矩阵S(图 1(b)),其中PABPACPADPBCPBDPCD描述两实体之间的空间关系,PAAPBBPCCPDD描述空间实体几何特征。通过包含N个实体的场景可以得到N(N-1)/2个9-交集矩阵,加上实体本身N个特征向量,可以构建一个行×列= 9×[N(N-1)/2 + N]的空间场景特征矩阵。

      图  1  空间场景的描述

      Figure 1.  Space Scene Description

    • 场景关联图是建立查询场景特征矩阵和数据库场景特征矩阵之间的关联匹配关系图,其目的是为了将检索问题转化为图的搜索问题。在空间场景特征矩阵S中,其列向量可分为两大类:第一类为PAAPBBPCCPDD,即几何特征向量;第二类为PABPACPADPBCPBDPCD,即空间关系特征向量。

      场景关联图的生成过程如下。

      1) 根据查询场景和数据库场景中几何特征向量的匹配度生成场景关联图的结点(是否匹配由几何松弛化决定),每个结点代表查询场景实体与数据库场景实体的匹配关系。

      2) 根据两场景空间关系特征向量的匹配度生成结点与结点之间的边,边指结点中两对实体之间相似的空间关系(是否匹配由空间关系松弛化条件决定)。

      现以图 2中的查询场景和数据库场景为例,当查询场景中的实体X与数据库场景中的实体A匹配时,即可生成场景关联图结点,记作(X, A),同理,可生成场景关联图结点(Y, B),当两场景的空间关系特征向量PXYPAB匹配时,即可生成场景关联图中两结点间的边,记作(XA, YB)。通过不断地匹配,即可生成相应的场景关联图(图 2)。

      图  2  空间场景的获取

      Figure 2.  Obtain Space Scene

      生成场景关联图后,可在图中搜索各种匹配圈,其匹配圈可分为完全匹配圈、不完全匹配圈和完全不匹配圈等3类。“完全匹配圈”指能够将查询场景中的实体全部包含,且图的边能围成一个闭合回路的搜索结果;“不完全匹配圈”指能够部分包含查询场景中的实体,或者能够全部包含查询场景中的实体,但边不能围成一个闭合回路的搜索结果;“完全不匹配圈”是指通过空间关系特征向量匹配的单个实体对,且不能够成为“完全匹配圈”或“不完全匹配圈”中结点的搜索结果。通过获取场景关联图中的“完全匹配圈”和“不完全匹配圈”,来获取初始的空间场景集合。

    • 对于空间场景S′的几何特征向量PAA= {PAA1, PAA2, …, PAAi},根据查询场景S中与之对应的向量PA′A′= {PA′A1′, PA′A2′, …, PA′Ai′},利用向量间的余弦公式可计算出两向量PAAPA′A′的匹配度LAA,同理可计算其他向量的匹配度Ni(0 < i < MM为场景S中匹配的几何实体的数目),然后根据每个匹配度的相对权重WNi,计算出实体几何特征向量的平均匹配度Nave

      $$ {N_{{\rm{ave}}}} = \frac{{\sum\limits_{i = 1}^M {{N_i}} \times w{N_i}}}{{\sum\limits_{i = 1}^M {w{N_i}} }} $$ (1s)

      对于向量PAB= {PAB1, PAB2, …, PABi},根据查询场景S中与之对应的向量PA′B′= {PA′B1′, PA′B2′, …, PA′Bi′},计算向量PABPA′B′的匹配度LAA:

      $$ {L_{AA}} = \frac{{{\mathit{\boldsymbol{P}}_{AA}} \times {\mathit{\boldsymbol{P}}_{A^{\prime} }}A^{\prime} }}{{|{\mathit{\boldsymbol{P}}_{AA}}| \times |{\mathit{\boldsymbol{P}}_{A^{\prime} A^{\prime} }}|}} = \frac{{\sum\limits_{i = 1}^n {{\mathit{\boldsymbol{P}}_{ABi}}} \times \sum\limits_{i = 1}^n {{\mathit{\boldsymbol{P}}_{A^{\prime} B}}_{^{\prime} i}} }}{{\sqrt {{\mathit{\boldsymbol{P}}_{AB{i_2}}}} \times \sqrt {{\mathit{\boldsymbol{P}}_{A^{\prime} B^{\prime} i{^{\prime} _2}}}} }} $$ (2)

      同理,可以计算出其他向量的匹配度Li,0 < i < M×(M-1)/2,其中M为场景S中匹配的几何实体的数目,然后根据每个匹配度的相对权重WLi,利用式(3) 计算空间关系特征向量的平均匹配度Lave:

      $$ {L_{{\rm{ave}}}} = \frac{{\sum\limits_{i = 1}^{M \times \left( {M-1} \right)/2} {{L_i} \times w{L_i}} }}{{\sum\limits_{i = 1}^{M \times \left( {M-1} \right)/2} {w{L_i}} }} $$ (3)
    • 当提取的空间场景S′与查询场景S中包含的实体数目不相同时,通过空间场景完整度C来表示S′在S中的完整性:

      $$ C = \frac{{\sum\limits_{i = 1}^M {w{N_i}} }}{{\sum\limits_{i = 1}^n {w{N_i}} }} $$ (4)

      式中,n表示查询场景S所包含实体的个数; MSS′匹配实体的个数; WNiS中的实体NiS中的权重。

    • 场景的近似匹配度Sscene为:

      $$ S{^{\prime} _{{\rm{scene}}}} = \frac{{\left( {wL \times {L_{{\rm{ave}}}}} \right) + \left( {wN \times {N_{{\rm{ave}}}}} \right)}}{{wL + wN}} $$ (5)

      式中,NaveLave为空间场景矩阵中两类向量的平均匹配度;WNwLNaveLave的权重。结合场景完整度C和它的权重Wc,场景完整匹配度Sscene为:

      $$ {S_{{\rm{scene}}}} = S{^{\prime} _{{\rm{scene}}}} \times \left( {wc \times \left( {C-1} \right) + 1} \right) $$ (6)

      当计算出空间场景集合中所有空间场景的匹配度后,即可计算出最佳的匹配场景。

    • 本文采用武汉某高校局部地区的矢量化数据进行实验,通过GIS软件提取场景中实体轮廓点和空间关系特征向量。几何关系特征向量根据实体轮廓点的分布情况,通过傅里叶变换获得,计算方法参考文献[18]。空间关系特征向量的提取以区A和区B为例,利用区A的外包矩形将平面画分成9个区域,计算出区B在9个区域中各部分的面积与区B总面积的比值,获取方位关系特征向量,距离关系特征向量通过区A的面积与区AB总外包矩形面积的比值来度量,拓扑关系特征向量,由于该场景中不存在相交和包含的关系,仅通过相邻和相离两种拓扑关系表示,对于相邻的情况,通过相邻两区公共边的长度与区A周长的比值进行量化。

      表 1为部分实验数据,列项XXZZYY为几何特征向量,列项XYXZYZ为空间关系特征向量,对于后者,第1~9行为方向关系特征向量,第10行为距离关系特征向量,第11行为量化后的拓扑关系特征向量。

      表 1  空间关系特征向量和实体几何特征向量

      Table 1.  Spatial Relationship Feature Vectors and Solid Geometry Feature Vector

      TD XY XZ YZ XX YY ZZ AB AD
      1 0 0 0 1 1 1 0 0
      2 0 0 0.567 5 0.004 8 0.024 2 0.476 0 0.050 9
      3 0 0.630 9 0.386 7 0.276 1 0.248 3 0.776 8 0 0.785 1
      4 0 0 0 0.069 0 0.894 0 0
      5 0.027 0 0.011 0 0 0 0.026 2 0.009 2
      6 0.868 2 0.369 1 0.035 0.865 0.154 8
      7 0 0 0 0 0
      8 0 0 0 0 0
      9 0.104 6 0 0 0.108 8 0
      10 0.354 3 0.186 7 0.219 6 0.332 8 0.203 6
      11 0.155 2 0 0.097 2 0.159 5 0
    • 在计算空间关系特征向量的匹配度时,分别计算方向、距离、拓扑关系的匹配度,对三者分配相同的权重,并利用式(3) 计算出每对空间关系特征向量的匹配度,而几何特征向量的匹配度可以利用式(1) 直接计算。为了最大限度地提取空间场景,该实验分别选取0.75、0.65作为几何特征向量和空间关系特征向量的最小匹配度,以此生成匹配关联图,并选取0.65作为场景完整度的最小值,提取空间场景。

      其中,XACEFGIJ的匹配度分别为0.979、0.965 5、0.964 2、0.874 8、0.985 4、0.965、0.984 8;YABCEFGI的匹配度分别为0.979 1、0.862、0.876、0.986 3、0.853 8、0.983 7、0.983 1;ZBDFGHJK的匹配度分别为0.868 8、0.832 5、0.966 1、0.768 7、0.830 4、0.772 5、0.874 5。部分空间关系特征向量匹配度为:XYABADFGFHKJQPQO的匹配度分别为0.999 6、0.683 3、0.999 7、0.788 1、0.999 7、0.653、0.747 2;XZABADFGFHKJQPPO的匹配度分别为0.706、0.999 9、0.700 2、0.997 2、0.707 6、0.707 1、0.719 8;YZBDGHFEKIJIPQPO的匹配度分别为0.812 9、0.999 6、0.614 3、0.753 1、0.596 7、0.577 3、0.814 1。最后从上述场景关联图中提取4个空间场景,如图 3所示。

      图  3  空间场景集合

      Figure 3.  Space Scene Collection

    • 根据式(1) 计算出上述4个场景的几何特征向量平均匹配度:Nave1=0.891 1,Nave2=0.896 3,Nave3=0.960 2,Nave4=0.960 6。为了更好地分析方向、距离、拓扑关系对空间关系特征向量平均匹配度Lave的影响,本文分别对三者分配不同的权重(表 2),然后利用式(3) 计算出在不同权重下不同场景的Lave表 3中的列项“匹配度1”表示在方向、距离、拓扑关系的权重为“0.33-0.33-0.33”时计算而得的Lave,以此类推,行项Lave1Lave2Lave3Lave4分别对应场景集合中4个空间场景的Lave

      表 2  权重分配

      Table 2.  Weight Distribution

      方向关系 距离关系 拓扑关系
      权重1 0.333 3 0.333 3 0.333 3
      权重2 0.5 0.25 0.25
      权重3 0.25 0.5 0.25
      权重4 0.25 0.25 0.5

      表 3  空间关系特征向量平均匹配度

      Table 3.  Average Match of Spatial Relationship Feature Vectors

      匹配度1 匹配度2 匹配度3 匹配度4
      Lave1 0.937 4 0.97 0.969 8 0.858 2
      Lave2 0.998 8 0.999 2 0.999 1 0.998 9
      Lave3 0.999 7 0.999 7 0.999 7 0.999 8
      Lave4 0.819 4 0.841 4 0.915 9 0.676 3

      本文分别对实体的几何特征和空间关系特征分配不同的权重(表 4),利用式(5) 计算出在不同权重下不同场景的近似匹配度S′,同时可根据NaveLave的不同权重分配可以计算出4个场景的近似匹配度。由于场景3的实体数目为2,其他3个场景的实体数目都为3,根据式(4) 可计算出4个场景的场景完整度C,分别为C1=C2=1,C3=2/3,C4=1,根据场景完整度C和4个场景的近似匹配度S′,取场景完整度权重Wc=1/3,利用式(5) 可计算出4个场景的完整匹配度S。具体的评估分析如图 4~图 6所示。

      表 4  权重分配表

      Table 4.  Weight Distribution

      权重1 权重2 权重3 权重4 权重5 权重6 权重7
      Nave 0.2 0.3 0.4 0.5 0.6 0.7 0.8
      Lave 0.8 0.7 0.6 0.5 0.4 0.3 0.2

      图  4  空间关系特征向量平均匹配度

      Figure 4.  Matching Degree of Spatial Relationship Feature Vectors Graph

      图  5  场景近似匹配度曲线图

      Figure 5.  Scene Approximate Similarity Graph

      图  6  场景完整匹配度曲线图

      Figure 6.  Scene Complete Similarity Graph

    • 图 4中,横坐标轴表示方向、距离、拓扑关系的权重分配,纵坐标轴表示空间关系特征向量平均匹配度,Lave1~Lave4分别对应4个场景的Lave,通过分析曲线图和具体的实验数据,当权重发生变化时,4个场景与查询场景的匹配度有较大波动,根据不同权重下的曲线变化趋势可知,场景2、场景3与查询场景的方向、距离、拓扑关系都保持很高的匹配度;场景1与查询场景的方向、距离关系的匹配度较高,但拓扑关系匹配度较低;场景4与查询场景的距离关系匹配度很高,但拓扑关系匹配度非常低。综合分析,当三者权重分配为“0.50-0.25-0.25”时匹配效果最佳。

      图 5中,横坐标轴表示几何特征、空间关系的权重分配,纵坐标轴表示场景近似匹配度,S1~S4分别对应4个空间场景的近似匹配度,当Nave的权重增加时,场景1、场景2和场景3的匹配度会逐渐降低,但场景4的匹配度会逐渐升高,当Nave的权重增加到0.7时,其匹配度有反超的趋势,由此可知,场景1、场景2和场景3的LaveNave的匹配度要高,而场景4则刚好相反。

      图 6中,横坐标轴表示几何特征、空间关系的权重分配,纵坐标轴表示场景完整匹配度,S1~S4分别对应4个空间场景的完整匹配度,通过4幅曲线图的对比,可以明显看出不同权重分配对场景完整匹配度的影响。从图 6(b)中可以看出,当NaveLave的权重分配为“0.2-0.8”,即方向、距离、拓扑、几何特征的权重分配为“0.40-0.20-0.20-0.20”时,完整匹配度如下:场景2>场景1>场景3>场景4;当权重为“0.3-0.7”,即权重分配为“0.35-0.175-0.175-0.30”时,场景2>场景1>场景3=场景4;当权重为“0.4-0.6”,即权重分配为“0.30-0.15-0.15-0.40”时,场景2>场景1>场景4>场景3,至于NaveLave其他的权重分配,即Nave的权重大于0.4,场景4的完整匹配度几乎接近或超过场景1和场景2,其研究意义不大,在此不作分析。综上所述,最佳匹配场景是场景2,其次是场景1,而场景3和场景4会随着NaveLave的权重分配而发生相应变化。

    • 本研究利用空间场景特征矩阵来描述空间场景,在不依赖实体属性的条件下通过场景关联图实现了空间场景的提取,由于引入了空间场景完整度,实现了对包含不同数目实体的空间场景的相似性度量,讨论了不同权重的方位、距离、拓扑关系对Lave的影响,同时分析了NaveLave对场景匹配度的影响,最后得出方位、距离、拓扑、几何特征在不同权重分配下各场景完整匹配度的比较结果,并给出了最佳匹配场景。

      在建立空间场景特征矩阵的过程中,由于方位关系不支持旋转操作,其描述的空间场景也不支持场景旋转,因此,在后续的研究过程中,将重新定位空间场景的主方向,以获取能够支持旋转的方位关系特征向量,实现空间场景的旋转,同时引入空间场景权重自适应融合方法,如人工神经网络、遗传算法、粒子群算法等对本文的权重分配进行自适应融合改进。

参考文献 (20)

目录

    /

    返回文章
    返回