一种基于形状特征的地理实体相似性查询方法

2015-06-07夏宇，朱欣焰

地理与地理信息科学 2015年1期

夏宇，朱欣焰

(1.江西师范大学地理与环境学院，鄱阳湖湿地与流域研究教育部重点实验室，江西南昌 330022;2.武汉大学测绘遥感信息工程国家重点实验室，湖北武汉 430079)

夏宇1，朱欣焰2

为适应矢量空间数据库的相似性查询的应用需求，提出一种融合区域和边界的形状特征提取算法。通过地理实体的坐标，求解地理实体的质心及离散的旋转角度和质心距离序列，然后等角度间隔重采样，通过线性内插求出所得系列边界点的质心距离，建立质心距离直方图，构造以质心距离直方图、紧凑度和面积的三元组构成的形状特征描述。在此基础上，提出针对矢量空间数据的地理实体相似性查询算法。通过自主开发的GIS空间智能查询与分析平台，以全国1∶25万县市级行政区划矢量数据为数据源，实现了地理实体的相似性查询。实验结果表明,改进图像分析领域的形状分析方法并应用到矢量数据相似性查询领域是可行的，提出的方法可以满足地理实体的相似性查询应用需求。

空间数据；地理实体；形状特征；相似性查询

0 引言

相似性查询是从数据库中找到与给定查询对象相似的对象，近年来相似性查询应用已成为信息检索、数据挖掘等诸多领域的研究热点问题。随着地理空间信息技术的迅速发展，为发现和利用更深层次的地学规律，空间数据的相似性查询成为地学领域迫切的需求，近年来逐渐得到更多重视[1-4]。目前，空间数据相似性查询的研究集中在两方面：一是对遥感影像数据的相似性查询，主要为利用纹理特征[1,2,4]及利用形状特征[3-6]的检索等；二是对矢量空间数据的相似性查询，主要为空间结构相似等方面的研究，文献[7]给出了异构数据集间进行空间场景相似性的特征描述和评价方法；文献[8]综合考虑空间对象的面积、属性及其相互间的拓扑、方向关系等特征，给出了空间场景相似性匹配模型；从空间拓扑相似方面的研究，文献[9]提出在不同尺度上拓扑等同一致性和基于拓扑距离的一致性特征的判断方法；文献[10]给出了判断多重表达地理空间数据库中的拓扑相等和相似的方法；从方向关系相似方面进行研究，文献[11]总结了地理空间方向关系的形式化描述模型，文献[12]探讨了主方向之间的相似性的特征描述和评价方法。

综上可见，目前对矢量空间数据相似性查询的研究主要是从空间结构的角度，多关注于空间场景的相似性，而从几何形态的角度对地理实体的相似性查询则较为少见，目前相关研究见于同名实体匹配及基于形状模板的空间查询等方面[13-17]。针对用户给定的地理实体查询相似的对象，对于地理空间信息应用逐步走向智能化具有重要的现实意义。例如，在全国范围内查询与给定城市地理形状相似的县市，查询结果所揭示的地学规律可为行政区的经济规划提供借鉴，为行政区的调整和完善提供辅助决策的理论依据。另外，目前的形状分析方法多是图像分析和模式识别领域针对栅格数据设计的，形状特征的表达一般有两类[18-21]：一类是基于区域的方法，如紧凑度、拓扑描述符等；另一类是基于边界的方法，如链码、边界矩、质心距离曲线等。这些形状特征一般是通过组成图像中的区域边界的像素集合来表达[18-20]，难以适应于矢量数据的地理实体的形状特征提取。鉴于此，为适应矢量空间数据库的相似性查询的应用需求，本文改进图像分析领域的形状分析方法，并应用到矢量空间数据的相似性查询领域，提出一种针对矢量空间数据的融合区域和边界的形状特征提取算法，在此基础上，提出一种针对矢量空间数据的地理实体的相似性查询方法。

1 融合区域和边界的形状特征提取

1.1 基本思想

质心距离曲线和紧凑度分别是图像分析领域中基于边界和基于区域的一种重要形状特征描述方法[19,20]，本文将两者结合并应用到矢量数据的相似性查询领域，通过融合区域和边界的方法来表达地理实体的形状特征，以实现地理实体的相似性查询。基本思想：通过地理实体的坐标，求解地理实体的质心和离散的旋转角度和质心距离序列，然后等角度间隔重采样，通过线性内插求出所得系列边界点的质心距离，建立质心距离直方图，构造以质心距离直方图、紧凑度和面积的三元组构成的形状特征描述，如图1所示。

图1 地理实体形状特征提取

Fig.1 Shape feature extraction of geographic entities

1.2 特征提取

算法1 地理实体形状特征提取算法

(1)

式中:n是地理实体的顶点数，(xi,yi)是顶点坐标。

步骤2:以O为原点，水平右方向为x正轴，垂直上方向为y正轴，遍历坐标序列，计算第一象限y值最小的点坐标A(xa,ya),第四象限y值最大的点坐标B(xb,yb)。

步骤3:根据式(2)，求多边形与x正轴的交点E(xe,ye)：

xe=xa+(y0-ya)(xb-xa)/(yb-ya),ye=y0

(2)

(3)

(4)

步骤5:等角度间隔重采样边界，令m等分可得到与多边形的交点序列(E,I1,I2,…，Im-1)。

步骤7:根据式(5)，通过线性内插计算该交点序列(E,I1,I2,…，Im-1)的坐标，求得极角序列θ1，θ2，…，θm和质心距l1,l2,…，lm：

θi=(i-1)*M/2π,li=dk+(dr-dk)(θi-αk)/(αr-αk)

(5)

(6)

2 地理实体的相似性查询

2.1 基本思想

针对融合区域和边界的形状特征描述，地理实体的相似性查询基本思想：通过用户给定查询对象，以区域大小约束对候选集进行初级过滤，然后以质心距离直方图计算边界相似度，以紧凑度计算区域相似度，基于相似度的近邻个数阈值，通过逆向距离综合加权，综合计算形状相似度(图2)。

图2 地理实体相似性查询

Fig.2Similarityqueryofgeographicentities

2.2 相似性查询

算法2 地理实体的相似性查询算法

步骤3:根据式(7)，计算满足ds3，i≥σ的候选集合，实现对候选集的初次过滤：

(7)

式中:σ为针对D3的相似度阈值。

(8)

式中：i∈I1={1，2，…，t}⊆I。

步骤5:根据公式(9)，计算归一化区域相似度ds2，i：

(9)

式中：i∈I1={1，2，…，t}⊆I。

步骤6：据式(10)求解k个最近邻对象，即为查询对象Q的相似性查询结果集R。

ds，i=Ds1，i*w1i+ds2,i*w2i

(10)

其中，w1i、w2i由式(11)确定：

(11)

式中：xji是基于相似度dsj,i降序排列的序数，tj是基于相似度dsj,i的近邻个数阈值。

3 应用实例与分析

3.1 应用实例

以全国1∶25万县市级行政区划矢量数据为数据源，设计和开发了GIS空间智能查询与分析实验系统，实现了地理实体的相似性查询应用。系统采用C编程语言；二次开发环境采用ArcEngine和OracleObjectsforOLE；系统支持以下3种类型矢量数据的相似性查询：Shape文件数据、OracleSpatial对象关系模型数据、ArcSDEforOracleSpatial数据。用户通过空间位置或属性信息给定感兴趣行政区划，设置Top-kNN最近邻阈值、等间隔重采样阈值及相似权重的近邻阈值(或由系统缺省指定阈值)，选择相似性查询算法(系统提供的3种相似性查询算法可选，缺省为基于融合区域和边界的算法)，系统提供相似性查询结果的属性描述、图形可视化及地图高亮显示等，图3是以江西省范围为例进行县市级行政区划地理实体相似性查询的应用实例。

该系统实现了地理实体的相似性查询，表1是设置相似性查询的Top-kNN最近邻阈值k=6，等间隔重采样阈值m=512,区域及边界相似的近邻阈值tj=10，基于融合区域和边界的算法，在江西省范围内选择查询对象进行相似性查询的结果。

从图3和表1可见，引入和改进图像分析领域的形状分析方法到矢量数据的相似性查询领域，通过融合区域和边界的形状特征，进行地理实体的相似性查询，从功能上是可行的，能够实现相似性查询的功能性需求。

图3 县市级行政区划地理实体相似性查询应用实例

Fig.3Theapplicationinstanceofsimilarityqueryforgeographicentitiesofadministrativeregions

表1 江西省范围内对给定行政区划的相似性查询结果

Table 1 The result of similarity query for given administrative region in Jiangxi Province(k=6,m=512,tj=10)

查询对象查询结果永丰县永丰县、会昌县、于都县、吉水县、赣县、乐安县安远县安远县、余干县、宜黄县、寻乌县、信丰县、高安县铅山县铅山县、乐平市、都昌县、崇义县、南丰县、进贤县广昌县广昌县、崇仁县、南丰县、乐平市、广丰县、彭泽县临川市临川市、余干县、万安县、乐安县、德兴市、瑞金县峡江县峡江县、樟树市、靖安县、上犹县、万年县、新干县吉水县吉水县、余干县、贵溪县、乐安县、永丰县、泰和县石城县石城县、南昌县、奉新县、宜黄县、分宜县、彭泽县上高县上高县、瑞昌县、大余县、石城县、靖安县、东乡县…………

3.2 实验分析

由于目前矢量数据的相似性查询研究很少从几何形态的角度关注地理实体的相似性，因而基于区域的方法和基于边界的方法在矢量数据的相似性查询领域鲜有涉及。本文尝试将基于区域的方法和基于边界的方法应用到矢量数据的相似性查询领域，进而提出一种针对矢量数据的基于融合区域和边界的相似性查询算法，记为M3。

图4 不同算法地理实体的相似性查询结果(Ⅰ)

Fig.4 The result of similarity query for different algorithms(Ⅰ)

图5 不同算法地理实体的相似性查询结果(Ⅱ)

Fig.5 The result of similarity query for different algorithms(Ⅱ)

表2 不同算法地理实体相似性查询结果

Table 2 The result of similarity query for different algorithms

查询SQ对象算法查询结果可视化结果Q1：江西省范围内与“临川市”形状相似的县市？临川市Q2：安徽省范围内与“舒城县”形状相似的县市？舒城县M1临川市、德兴市、永修县、南昌县、会昌县M2临川市、余干县、万安县、乐安县、玉山县M3临川市、余干县、万安县、乐安县、德兴市M1舒城县、阜阳市、祁门县、贵池市、凤阳县M2舒城县、泗县、霍山县、涡阳县、全椒县M3舒城县、霍山县、泗县、阜阳市、涡阳县

为验证本文方法的有效性，分别对以下3种相似性查询算法(M1-基于区域的算法、M2-基于边界的算法、M3-基于融合区域和边界的算法)进行相似性查询实验。设置Top-kNN查询阈值k=5，等间隔重采样阈值m=512,区域和边界相似的近邻阈值tj=10，实验结果如图4、图5和表2所示。

从表2可见，对于Q1：在江西省范围内查询与“临川市”形状特征相似的县市,M1的查询结果为临川市、德兴市、永修县、南昌县、会昌县，M2的结果为临川市、余干县、万安县、乐安县、玉山县，M3的结果为临川市、余干县、万安县、乐安县、德兴市。从图4和表2可见，M1的最相似的对象为德兴市，M2的最相似的对象为余干县，M3的最相似的对象和M2一致，而德兴市在M3的检索结果中排名第4，从表2可视化结果中可以看出，M3的相似性查询结果与实际情况更加一致。对于Q2：在安徽省范围内查询与“舒城县”形状特征相似的县市,M1的查询结果为舒城县、阜阳市、祁门县、贵池市、凤阳县，M2的结果为舒城县、泗县、霍山县、涡阳县、全椒县，M3的结果为舒城县、霍山县、泗县、阜阳市、涡阳市。从图5和表2可见，M1的最相似的对象为阜阳市，M2的最相似的对象为泗县，M3的最相似的对象是霍山县，M1、M2和M3最相似的对象各不相同，但M3的最相似的对象是M2的次相似对象，而阜阳市在M3的检索结果中排名第3，从表2可视化结果中可以看出，M3的相似性查询结果更符合人们的空间认知。事实上，M3在Q1中的最相似对象与M2一致，而在Q2中的最相似对象与M2不一致，这是由于M3综合了对区域和边界特征的表达能力，一定程度上克服了M2从边界特征进行形状描述的缺陷——由于地理实体边界的复杂性，存在着不同的形状对应于边界特征相似度相等的情况。因而，M3的相似性查询结果与人们的空间认知也更加一致。

表3为重采样阈值对地理实体相似性查询结果的影响(最近邻阈值k=6及区域和边界相似的最近邻阈值tj=10)。

表3 重采样阈值对地理实体相似性查询结果的影响

Table 3 The influence of resampling threshold value on similarity query results

查询重采样阈值算法相似性查询结果Q1：江西省范围内与“临川市”形状相似的县市？m=8m=16m=32m=64m=128m=256m=512M2临川市瑞金县乐安县广昌县玉山县M3临川市瑞金县乐安县万安县德兴市M2临川市乐安县崇仁县万安县广昌县M3临川市乐安县万安县铅山县瑞金县M2临川市乐安县万安县余干县玉山县M3临川市乐安县万安县余干县德兴市M2临川市乐安县万安县余干县玉山县M3临川市乐安县万安县余干县德兴市M2临川市万安县余干县乐安县玉山县M3临川市万安县余干县乐安县德兴市M2临川市万安县余干县乐安县玉山县M3临川市万安县余干县乐安县德兴市M2临川市余干县万安县乐安县玉山县M3临川市余干县万安县乐安县德兴市

从表3可见，当m=8时，查询到的最相似对象是瑞金县，检索结果与实际情况存在差距。随着m增加，相似性查询结果集渐趋于稳定，只是由于重采样精度的提高，相似程度的判断更加准确，相似性检索结果与人们的空间认知也更加相符。综上可见，最近邻阈值只与查询结果个数有关，不影响查询质量，可根据实际查询需求设定；重采样阈值m越大，相似性查询精度越高，同时查询效率下降，理想情况是查询结果趋于稳定的重采样阈值，一般与地理实体形状的复杂度相关，可根据经验值设定；最近邻阈值对相似性查询精度有不显著的影响，理想情况是相似与不相似的分界点，可按照经验值设定。

M1和M2都是图像分析领域中的经典方法，本文探索性地将其引入到矢量数据的相似性查询领域，进而提出针对矢量数据相似性查询的算法M3，由实验分析可见， M3在相似性查询的质量方面，优于M1和M2。

4 讨论与结论

矢量数据相似性查询是空间数据相似性查询的重要内容，对于促进地理信息的智能化应用具有重要的现实意义。由于目前矢量数据的相似性查询研究多是从空间结构的角度关注地理场景的相似性，很少从几何形态的角度关注地理实体的相似性，因而传统的图像分析领域的经典形状分析方法虽已被用到矢量数据的地图更新、地图综合等方面，但在矢量数据的相似性查询领域却鲜有涉及。本文探索性地将图像分析领域的经典形状分析方法应用到矢量数据的相似性查询领域，拓展了经典形状分析方法的应用范围。

由于图像分析领域的经典形状分析方法并不能直接适应矢量空间数据库的相似性查询，本文改进了图像分析领域的经典形状分析方法，提出一种针对矢量空间数据的融合区域和边界的形状特征提取算法，在此基础上，提出了一种针对矢量空间数据的地理实体的相似性查询算法。相似性查询功能实验、引入到相似性查询领域的不同算法的比较实验及重采样阈值对地理实体相似性查询结果的影响实验表明，本文提出的融合区域和边界的形状特征提取算法及以此为基础的地理实体相似性查询算法，可以实现地理实体的相似性查询应用需求。由于地理信息相似性查询是涉及空间认知、信息挖掘、人工智能等诸多领域的复杂问题，因而结合这些领域的最新研究成果，建立地理信息相似性查询的评价和更新模型，以提高相似性查询质量，是有待下一步深入研究的课题。

[1] XIE Z X,ROBERTS C,JOHNSON B.Object-based target search using remotely sensed data:A case study in detecting invasive exotic Australian Pine in south Florida[J].ISPRS Journal of Photogrammetry & Remote Sensing,2008,63:647-660.

[2] 许锐，曾艳芳.基于Contourlet变换的高空间分辨率遥感影像检索研究[J].测绘科学，2013，38(4)：116-118.

[3] 朱佳丽，李士进，万定生，等.基于特征选择和半监督学习的遥感图像检索[J].中国图象图形学报，2011,16(8)：1474-1482.

[4] 朱先强，黄金才，邵振峰，等.一种定义感兴趣局部显著特征的新方法及其在遥感影像检索中的应用[J].武汉大学学报(信息科学版)，2013,38(6)：652-655.

[5] 王仁礼，郝玉保，顾立娟.改进的边缘角度直方图在遥感图像检索中的应用[J].测绘科学，2008,33(6)：70-72.

[6] ZHANG D S.Image Retrieval Based on Shape[D]. Melboume:Monash University,2002.

[7] WANG C X,STEFANIDIS A,AGOURIS P.Spatial content-based scene similarity assessment[J].ISPRS Journal of Photogrammetry and Remote Sensing,2013,69:103-120.

[8] 宋腾义，汪闽.多要素空间场景相似性匹配模型及应用[J].中国图象图形学报，2012,17(20)：1274-1283.

[9] BELUSSI A,CATANIA B,PODESTA P.Towards topological consistency and similarity of multiresolution geographical maps[A].LI K J.Proceedings of the ACM International Symposium on Advances in Geographic Information Systems[C].Michigan:Association for Computing Machinery,2005.220-229.

[10] ARGEMIRO J,PAIVA C,PAIVA A C,et al.Topological Equivalence and Similarity in Multi-representation Geographic Databases[D].Maine:University of Maine,1998.

[11] 夏宇，朱欣焰，李德仁.GIS空间方向关系形式化描述模型分析[J].测绘科学，2007,32(5)：94-98.

[12] GOYAL R K,EGENHOFER M J.Similarity of cardinal directions[J].Lecture Notes in Computer Science,2001,2121:36-55.

[13] 安晓亚，孙群，肖强，等.一种形状多级描述方法及在多尺度空间数据几何相似性度量中的应用[J].测绘学报， 2011,40(4)：495-501,508.

[14] 付仲良，逯跃锋.利用弯曲度半径复函数构建综合面实体相似度模型[J].测绘学报，2013,42(1)：145-151.

[15] 帅赟，艾延华，帅海燕，等.基于形状模板匹配的多边形查询[J].武汉大学学报(信息科学版)，2008,33(12)：1267-1270.

[16] 艾延华，帅赟，李精忠.基于形状相似性识别的空间查询[J].测绘学报，2009,38(4)：356-362

[17] 童小华，邓愫愫.基于概率的地图实体匹配方法[J].测绘学报，2007,36(2)：210-217.

[18] LONCARIC S.A Survey of shape analysis techniques[J].Pattern Recognition,1998,31(8):983-1001.

[19] 章毓晋.图像处理和分析教程[M].北京:人民邮电出版社,2009.

[20] 章毓晋.图像分析[M].北京：清华大学出版社，2005.

[21] 王斌.形状分析的新方法及其应用[D].上海:复旦大学,2006.

[22] BATTY M.Exploring isovist fields:Space and shape in architectural and urban morphology[J].Environment and Planning B:Planning and Design,2001,28(1):123-150.

A Method on Similarity Query of Geographic Entities Based on Shape Feature

XIA Yu1,ZHU Xin-yan2

(1.SchoolofGeographyandEnvironment,KeyLaboratoryofPoyangLakeWetlandandWatershedResearch,MinistryofEducation,JiangxiNormalUniversity,Nanchang330022;2.StateKeyLaboratoryofInformationEngineeringinSurveying,MappingandRemoteSensing,WuhanUniversity,Wuhan430079,China)

To meet similarity query requirements for vector spatial database,this paper presents a shape feature descriptor with the fusion of regional and boundary features with its extraction algorithm.First,discrete rotation angles and a sequence of centroid-distances by the coordinates of the geometry are solved.Then,a centroid-distance sequence for series boundary points by equal interval resampling angle are determined by a linear interpolation technique.Thereupon,the centroid-distance histogram is set.Accordingly,the descriptor with the triple of centroid-distance histogram,compactness and area is achieved.Then,an algorithm for geographic entities similarity query is proposed based on the descriptor,and the similarity queries for geographic entities are achieved through the self-developed intelligent vector geospatial database query platform with 1∶250 000 nationwide county/city level administrative division vector data as experiment data set.Experimental results show that it is feasible to introduce shape analysis method in the filed of image analysis into the filed of geographic entities similarity query,and the proposed method can achieve geographic entity similarity query application requirements.

spatial data;geographic entity;shape feature;similarity query

2014-04-14；

2014-05-19

国家自然科学基金项目(41101369);江西省教育厅科技计划项目(GJJ12189);江西师范大学青年英才培育计划项目

夏宇(1981-)，男，博士，副教授，硕士生导师，主要研究方向为空间信息服务。E-mail:geoxy@126.com

10.3969/j.issn.1672-0504.2015.01.002

P208

1672-0504(2015)01-0006-06