空间相似性和旋转不变性的空间场景匹配研究

房家伟 凌云

摘 要：空间场景与人类生活密切联系，无处不在，是人们生活发生的真实空间。本文针对矢量空间场景匹配过程中的旋转问题，引入位置图的概念，分析待匹配场景的内部结构之间的关系，如图元间的最近点、最远点、质心点，而这种关系不随场景的旋转而变化。突破以往从图元个体角度描述草图特征的方法，转换思路为将空间场景作为群组对象，从整体上刻画草图特征。本文以郑州市局部区域为实验数据，利用该区的矢量化数据进行验证，并分析评价匹配结果。实验结果表明基于位置图和空间相似性的方法能很好地实现空间场景匹配，并能解决场景旋转等问题。

关键词：空间相似性;旋转不变性;位置图;波形图;空间场景匹配

中图分类号：TP391  文献标识码：A  文章编号：1673-260X（2020）09-0040-05

1 引言

在GIS研究方面，针对空间相似性很多学者一般都用空间几何关系中的图元形状特征、图元的相对大小特征、两图元的相对方向特征、空间关系中的图元间的拓扑关联、图元间的距离远近、图元间的相对方向等来表现[1]。空间相似性关系计算性不高，且空间关系相对复杂，因此在计算空间图元相似性时要同时考虑空间几何关系中的形状特性、大小特性、方向特性;空间关系中的拓扑关系、距离关系、方向关系等多个因子[2]。通过对空间相似性的度量，可以用来揭示空间场景匹配，也对世界的认知提供更多的理论价值和应用价值，因此受到国内外很多学者的研究和关注[1～4]。

探究空间场景匹配问题其实就是计算空间图元目标实体的相像程度[5]。通常空间场景相似性是将单个图元的相似关系，以及每个图元之间的空间关联相似性用来建立关联图，计算出相似性[6]。但是此类方法难以解决场景的旋转问题，从而导致漏查，错查等结果[7]。因此提出位置图的计算方法，把输入数据（草图）看成一个整体，分析其整体关系，包括各图元间的类空间关系。从而解决匹配过程中输入数据与参考数据的旋转问题。结合草图数据融合的优势，探索面向地理场景的匹配方法，将会进一步提高空间匹配的可用性;进一步揭示地理场景的认知、描述和应用机理;促进地理信息科学和技术的智能化、大众化、社会化发展。

2 解决方案

为了提高场景相似性检索的精度，使用草图整体特征相似性度量方法，本文首先通过草图的重心点、最近点、最远点绘制出几何位置图。然后，利用折线相似性计算算法计算出相似性，从而完成粗匹配。最后，结合空间场景的集合相似性和空间关系相似性完成精匹配。

本文选取郑州市部分地区的矢量数据作为匹配场景进行实验。图1中A为匹配场景，图B1，B2，B3，B4，B5中为数据库。

3 基于位置图的草图场景粗匹配

3.1 空间几何坐标的获取

每个面状图元都可以用一个形状中心点来表示。通过该点可以从整体的角度来研究旋转不变性、平移不变性等特征[7]。对于矢量数据，大多数都是用几何坐标中心点，但是基于本文场景匹配的条件下，需要考虑可能两个相似度较高的形状可能几何坐标点不一致[8]。考虑到几何目标的面积特征，本文采用重心作为目标的形狀中心点。

但是针对多图元群组来说，很多学者采用最小外包矩形（MBR）和最小面积外接矩形来描述群组目标。因为相比较于MBR来说，最小面积外接矩形更接近原目标的形状[6，7]。故本文采用最小面积外接矩形来描述群组。根据公式（1）求得群组的最小面积外包矩形的质心。

上式中的n为图元的每条边与原点组成三角形的面积，Xi，Yi分别表示第i个点在X和Y轴的坐标。基于上述方法得到了空间几何坐标以及群组目标的最小面积外接矩形质心：

3.2 几何与力的位置图绘制与计算

通过群组目标的最小面积外接矩形质心与各图元间的重心点、最近点、最远点的关系特征，且这种关系特征特别的灵活，在群组整体发生旋转，偏移的时候，能够很好地度量群组的相似性[9，11]。本文采用位置图来反映这种图元间的关系。

由力的位置图分析可得投影比为一个常量[1]，但是由于用户输入等问题，匹配图形可能会存在旋转问题，需要再对每个群组做旋转分析。本文以群组最小MBR的质心为旋转中心，为？琢°为旋转角度（0°<？琢<360°）进行旋转。用相同算法求出投影比。为了直观方便的反映图元间的投影比关系，采用波形图的形式进行展示。

3.3 波形图相似性的计算

波形图的X轴坐标的跨度比较大，为0-360;而Y轴的坐标却是0-20之间[12，13]。针对这个问题，提出了对波形图进行归一化得做法：

（1）遍历所有数据，找出X，Y的最大值和最小值;

（2）X，Y的所有值分别减去最小值，然后除以最大值和最小值的差。

根据上述算法[12-17]，得到波形图的相似度如下，进行相似程度排序如表2：

通过绘制波形图可以看出B1和B2、B3具有较高的相似性。但是并不能确定它们就是用户所要匹配的场景，还可能存在如下可能，因此要做精匹配。

情况一：MBR相同，重心相同，但是图元不同。见图2（a）：群组MBR和重心相同。

情况二：群组相同（包括各图元相同），但是群组整体变大。见图2（b）：群组等比放大。

情况三：部分图元确定，部分只是位置稍微偏离。见图2（c）：部分图元偏离。

4 基于空间相似性的精匹配

针对粗匹配中出现的问题，本章通过精匹配从粗匹配结果排序中筛选出最可能的空间场景。首先，群组的几何相似性通过图元的形状，大小，方向等几何特征来描述[18，19];然后，空间场景的空间关系相似度用图元间的拓扑关系、距离关系、方向关系的相似度来度量[20-25];最后本文用层次分析法，分别对空间场景的几何相似度及空间关系相似度附以不同的权重，来表示空间场景的总相似性。而相似性是定量衡量空间场景的接近程度，因此可以完成空间场景的匹配[18，19，24]。

4.1 空间场景几何相似性的计算

空间场景几何相似性的计算包含了形状相似性[25]、大小相似度[21]和方向相似度[15]，计算方法见参考文献，由此计算出本文研究区的形状、大小，方向相似度，见表3：

如此，很容易得到A1，B17两图元之间的形状相似程度SimF（A1，B17）、A1，B17之间的大小相似程度SimS（A1，B17）和它们之间的方向相似程度Sim？兹（A，B）。结合层次分析模型，分别对空间几何关系中的形状、大小和方向相似度赋予不同的权重因子，即得到两空间图元的几何度SimG（A，B）：

simG（A，B）=kF×simF（A，B）+kS×simS（A，B）

+k？兹×sim？兹（A，B）  （2）

其中，式（2）中的KS、K？兹、KF分别代表空间图元几何特征的大小，方向和形状被赋予的比重因子。它们的和为1，且每个值的大小都在0到1的范围内。

因为一个群组中有多个图元，考虑到单图元的相似性、整体的几何相似性，本文采用均值的方法，见表4。

4.2 空间场景空间关系相似性的计算

空间关系是研究GIS重要理论之一，目前国内外学者一般从空间图元间的拓扑关系、距离关系、方向关系等方面来度量空间关系的相似性[26，27]。

4.2.1 拓扑关系

本文数据匹配场景中只涉及面与面的相邻及面与面的相离这两种空间拓扑关系，研究群组的空间关系时，以群组为单位分析其内部图元间的空间关系。

通过粗匹配的匹配结果排序，排除SimT（A（），B（））=0的情况。因此以下实验只需考虑匹配场景与数据库中待匹配场景的第二种情况。但是针对匹配场景有4个图元目标，首先要选取其中一个单图元为参考目标，从而以它为参考点来计算最短距离。本实验是以A1，B1，B5，B9，B13，B17为参考目标得到的是群组整体的数据平均距离。计算拓扑相似度[26，27]可得表5。

4.2.2 方向关系

方向Voronoi图模型和方向关系矩阵模型能够通过数值来反映空间方向相似性。实验考虑数据计算的复杂性和考虑图元的整体性，选用改进的方向关系矩阵模型来描述空间方向相似度。在以A1，B1，B5，B9，B13，B17为参考目标时，根据方向关系[26，27]公式计算出匹配场景和数据库待匹配各场景的特征向量。

在上述公式计算得到的空间图元特征向量基础上，根据相关系数法来度量两个场景的空间关系相似度[26，27]SimD（AB，EF），见表6。

4.2.3 距离关系

为了准确地计算距离关系的相似程度的大小，需选用图元的重心点表示质心距离中的质心点。在粗匹配中第一步已经获取各图元的重心坐标。且粗匹配已经考虑了图元的形状、大小和方向的相似度，所以在计算空间场景A的距离关系[26，27]时，可以用每个图元与参考图元的距离总和作为匹配场景和数据库待匹配各场景的距离（见表7）;

4.3 空間场景相似性的计算

为了提高匹配的准确性和充分利用匹配的约束特征，采用层次分析法同时度量空间几何关系和空间关系，并赋予不同的权重因子。

本文参考文献[22]的权重赋值如下：

SIM=0.8×[0.6×[0.4×simT+（simd+simD）×0.3]

+0.4×（simF+simS+sim？兹）]+0.2×simCU  （3）

匹配结果排序，见表8。

5 总结

早就有“一图胜千言”的说法，人们可以简单便捷地通过感知将大量的数据融合用草图表示出来，通过对草图的分析，可以高效地整合信息，节约信息化成本和精确地获取地理空间位置。由此可见草图在描述空间场景方面的优势。

本文是以空间场景匹配为突破口，旨在解决在场景匹配中存在的场景旋转问题。充分利用矢量数据的可视化及空间图元间的空间几何和空间关系特征。从人们对空间的定性思考的思维方式来说，空间场景匹配可以通过空间相似性进行度量。通过对空间相似性的研究，也为多源数据的融合和空间场景查询提供了强有力的理论基础，对将来智能化GIS的发展也有深远的影响。

论文通过在前人相关知识研究的基础上，进行了图像场景匹配的分析列举与汇总。从空间场景的中图元的几何特征（形状、大小等）来计算图元的几何特征相似度，并对拓扑关系、方向关系、距离关系进行了深度的描述，并最终找出最合适的方法来度量空间关系的相似性;对提出的位置图方法也进行了深度的解读，清晰地表述粗匹配的各步骤及计算波形图的相似度算法的介绍。最后取郑州市某局部地区的矢量数据为实验数据，对上述的方法进行了验证，并对实验的结果进行了多角度的分析评价。最终从实验结果发现，基于空间相似性和旋转不变性的方法能够匹配到更为相似的空间场景，匹配的结果也更符合用户的空间认知观念。

——————————

参考文献：

〔1〕潘柔.矢量面状地物的空间场景相似性计算方法研究[D].长安大学，2015.

〔2〕Xu Y ， Xie Z ， Chen Z ， et al. Shape similarity measurement model for holed polygons based on position graphs and Fourier  descriptors[J]. International Journal of Geographical Information Science， 2017， 31（1-2）：253-279.

〔3〕郝燕玲，唐文静，赵玉新，等.基于空间相似性的面实体匹配算法研究[J].测绘学报，2008，37（04）：501-506.

〔4〕郑宇志，张青年.基于拓扑及空间相似性的面实体匹配方法研究[J].测绘科学技术学报，2013，30（05）：106-111.

〔5〕翟仁健.基于全局一致性评价的多尺度矢量空间数据匹配方法研究[D].解放军信息工程大学，2011.

〔6〕赵彬彬.多尺度矢量地图空间目标匹配方法及其应用研究[D].中南大学，2011.

〔7〕郭黎，郑海鹰，王豪.面状矢量空间数据匹配技术研究[J].海洋测绘，2009，29（03）：12-15.

〔8〕黄智深，钱海忠，王骁，金永岗，张强.基于降维技术的面状居民地匹配方法[J].测绘科学技术学报，2012，29（01）：103-109.

〔9〕Zhang J R， Zhang J， Lok T M， et al. A hybrid particle swarm optimization-back-propagation algorithm for feedforward neural network training[J]. Applied Mathematics & Computation， 2007， 185（02）：1026-1037.

〔10〕Papadias D， Egenhofer M J， Sharma J. Hierarchical reasoning about direction relations  in： Proc. 4th ACM Workshop on GIS [C]. 1996：105-112.

〔11〕Papadias D， Delis V. Relation-based similarity[C]. Fifth ACM International Workshop on Advances in Geographic Information Systems. ACM， 1997：1-4.

〔12〕Ai T， van Oosterom P. A displacement method based on field analysis[C].In：SymPosium on Integrated Systems for Spatial Data Production，Custodian and Decision Support. Xi'an，2002：1-8.

〔13〕WANG Zeshen， DanLee. Buliding Simplification Based on Pattern Recognition and Shape Analysis[C].SDH 2000-Conference  Proceedings.2000，58-72.

〔14〕張桥平，李德仁，龚健雅.城市地图数据库面实体匹配技术[J].遥感学报，2004，8（02）：107-112.

〔15〕郭黎，崔铁军，郑海鹰.基于空间方向相似性的面状矢量空间数据匹配算法[J].测绘科学技术学报，2008，25（05）：115-121.

〔16〕Nedas K A， Egenhofer M J. Spatial-Scene Similarity Queries[J]. Transactions in Gis， 2008， 12（6）：661-681.

〔17〕Jun Chen， Chengming Li， Zhilin Li， et al. A Voronoi-based 9-intersection model for spatial relations[J]. International Journal of Geographical Information Science， 2001， 15（3）：201-220.

〔18〕童小华，邓愫愫，史文中.基于概率的地图实体匹配方法[J].测绘学报，2007，36（02）：210-217.

〔19〕邵世维.基于几何特征的多尺度矢量面状实体匹配方法研究与应用[D].武汉大学，2011.

〔20〕Rylov M A， Reimer A W. Improving label placement quality by considering basemap detail with a raster-based approach[J]. GeoInformatica， 2015， 19（3）：463-486.

〔21〕章莉萍，郭庆胜，等.相邻比例尺地形图之间居民地要素匹配方法研究[J].武汉大学学报信息科学版，2008，33（06）：255-260.

〔22〕刘涛，闫浩文.空间面群目标几何相似度计算模型[J].地理信息科学学报，2013，15（05）：356-361.

〔23〕吴静，尹涛.多尺度空间关系相似性研究[J].测绘科学，2011，36（04）：59-63.

〔24〕Deng M， Li Z L，Chen X Y. Extended  Hausdorff distance for spatial objects in GIS[J].International Journal of Geographical Information Science，2007，21（04）：459-475.

〔25〕艾廷华，帅赟，李精忠.基于形状相似性识别的空间匹配[J].测绘学报，2009，38（04）：306-310.

〔26〕Frontiera， P.， R. Larson and J. Radke， A comparison of geometric approaches to assessing spatial similarity for GIR[J]. International Journal of Geographical Information Science， 2008. 22（03）： p. 337-360.

〔27〕Yan H，Chu Y，Li Z，et al.A quantitative description model for directional relations based on direction groups[J].Geoinformatica，2006，10（02）：177-195.