一种基于空间关系的空间场景数据检索方法

摘要

本发明公开了一种基于空间关系的空间场景数据检索方法。步骤一：将手绘检索场景作为检索输入；步骤二：对数据库场景和检索场景提取改进9-交模型语义网络；步骤三：提取基本方向关系语义网络；步骤四：创建改进9-交模型语义网络的关联图，得到预处理结果集；步骤五：针对预处理结果集创建基本方向关系语义网络的关联图，得到检索结果集；步骤六：计算检索结果集中检索结果的相似性分值；步骤七：如果当前检索结果集为空或者结果集中的检索结果数目小于阈值，对空间关系进行约束放松，扩充检索结果集，返回步骤四，否则进行下一步；步骤八：按相似性分值的高低将检索结果显示在输出设备上。本发明具有提高检索效率和用户体验的优点。

说明书

技术领域

本发明属于空间检索领域，尤其涉及一种可以提高检索效率的，基于空间关系的空间场 景数据检索方法。

背景技术

随着“数字中国”的逐步实现，空间信息应用面越来越广泛。数字矢量地图具有精度高、 支持高质量缩放、定位准确、操作方便、更新便捷等多种优势，已成为地理信息系统、智能 交通运输系统、数字化城市和数字化国防建设等方面必需的保障资源，它克服了纸质地图查 询速度慢、存储不方便、绘图精度低等缺点，是整个系统的基石。但是，矢量地图的检索仍 然停留在以数据库查询语言为基础的机械化检索阶段，未能充分发挥矢量数据的空间特征。 这种传统的检索方式不仅刻板，而且用户在使用时十分不便并且极易出错。造成这些问题的 主要原因是空间检索具有输入模糊、不精确、难于理解和不规范等特点，这些都制约了传统 空间检索语言的检索效率和命中率。

为了突破传统空间检索语言在面对空间检索输入模糊、不精确、难于理解和不规范等特 点的限制，基于手绘草图的检索打开了用户和空间数据交互的新领域，这种检索方式允许用 户方便的手绘出思维简图来代替传统检索方式中复杂、刻板的检索语言，更加符合用户对空 间数据的理解方式，更加贴近用户的使用习惯。

发明内容

本发明的目的是提供一种可以提高检索效率和用户体验的，基于空间关系的空间场景数 据检索方法。

本发明是通过以下技术方案实现的：

一种基于空间关系的空间场景数据检索方法，包括以下几个步骤，

步骤一：将手绘检索场景作为检索输入；

步骤二：对数据库场景和检索场景提取改进9-交模型语义网络；

步骤三：对数据库场景和检索场景提取基本方向关系语义网络；

步骤四：创建改进9-交模型语义网络的关联图，得到预处理结果集；

步骤五：针对预处理结果集创建基本方向关系语义网络的关联图，得到检索结果集；

步骤六：利用相似性定量计算模型计算检索结果集中检索结果的相似性分值，按相似性分值 对检索结果进行由高到低的排序；

步骤七：如果当前检索结果集为空或者结果集中的检索结果数目小于阈值，对空间关系进行 约束放松，扩充检索结果集，返回步骤四，否则进行下一步；

步骤八：按相似性分值的高低将检索结果显示在输出设备上。

本发明一种基于空间关系的空间场景数据检索方法，还可以包括：

1、改进9-交模型，在9-交模型的基础上对9-交模型矩阵中的每一个元素进行扩展，使每个 元素的取值范围扩展到{-1,0,1,2}。

2、创建改进9-交模型语义网络的关联图的方法为：

步骤一：检索场景G的点集为(v₁,...，v_n)，数据库场景H的点集为(u₁,...,u_N)，如果数据 库场景H中的点u_j满足检索场景G中点v_i的约束，则在改进9-交模型的语义网络的关联图中 创建一个点a_ij表示数据库场景H中第j个点满足检索场景G中第i个点的约束；

步骤二：如果数据库场景H中存在点u_j到点u_l的空间关系满足检索场景G中点v_i到点v_k的空间关系约束，则在改进9-交模型语义网络的关联图中点a_ij和a_kl之间建立边；

步骤三：重复步骤一～步骤三，直到没有满足约束的点和边为止。

3、针对预处理结果集创建基本方向关系语义网络的关联图的方法为：

步骤一：检索场景G的点集为(v₁,...,v_n)，预处理结果集场景H'的点集为(u′₁,...,u'_N)，如果 预处理结果集场景H'中点u'_j满足检索场景G中点v_i的约束，则在基本方向关系语义网络的关 联图中创建一个点a′_ij表示预处理结果集场景H'中第j个点满足检索场景G中第i个点的约 束；

步骤二：如果预处理结果集场景H'中存在点u'_j到点u′_l的方向关系满足检索场景G中点v_i到点v_k的方向关系约束，则在基本方向关系语义网络的关联图中点a′_ij和a′_kl之间建立边；

步骤三：重复步骤一～步骤三，直到没有满足约束的点和边为止。

4、相似性定量计算模型为：

S_{Scene(db,qry)}＝S'_{Scene(db,qry)}·(w_Comp·(S_Comp-1)+1)

其中，S_{Scene(db,qry)}为空间场景的相似性，w_Comp为空间场景完整性在空间场景检索中所占的权重， S_Comp(db,qry)为空间场景完整性，

$S_{\mathrm{Scene}(\mathrm{db},\mathrm{qry})}^{\prime }=\frac{(w_{\mathrm{Obj}}·S_{\mathrm{Obj}}+w_{\mathrm{Rel}}·S_{\mathrm{Rel}})}{w_{\mathrm{Obj}}+w_{\mathrm{Rel}}}$

其中，w_Obj为在基本方向关系语义网络的关联图中空间对象所占的权重，w_Rel表示在基本方向 关系语义网络的关联图中空间关系所占的权重，S_Obj为基本方向关系语义网络的关联图整体 的空间对象的相似度，S_Rel为基本方向关系语义网络的关联图整体的空间关系的相似度。

有益效果：

本发明提出一种基于空间关系的矢量数据检索方法，针对传统空间检索语言在面对空间 检索输入模糊、不精确、难于理解和不规范等特点的限制，本方案的系统原型采用手绘草图 作为输入，更加符合人类对空间数据的认知过程，方便用户的使用。对比传统矢量数据检索 方法，本发明具有以下优点：

第一，更加符合人类对空间数据的认知过程，深入利用了矢量数据的空间特征。传统矢 量数据检索是基于数据库查询语言，需要用户精准的输入。然而，多数情况下用户只会记忆 明显的空间特征，例如两个物体的空间相对位置、相对大小等，在这些情况下传统数据库语 言几乎无法进行检索。本发明利用9-交模型、定量改进9-交模型、基本方向关系和细方向关 系，从拓扑和方向两个空间特征对矢量空间数据进行形式化描述，以此作为检索的基本元素， 实现了基于空间关系的矢量数据检索。

第二，提出一种定量计算相似性的模型，用于综合评价检索结果，为排序提供依据。依 据空间关系进行矢量数据的检索，属于定性检索，很难精确地描述出具体的数量关系，大多 数情况下检索结果并不唯一。本发明提出一个定量计算相似性的模型计算检索结果的相似性 ，为排序提供依据。本发明提出的相似性定量计算模型，从矢量数据中的基本组件开始计算 相似性，即计算矢量数据中对象间空间关系的相似性，再通过基本组件的相似性计算整个矢 量数据的相似性。

通过对比国内外关于给予空间关系的图像检索解决方案，充分分析传统检索方案，本课 题主要研究内容包括以下几部分：第一，对空间关系进行形式化描述，用数学模型描述矢量 地图的空间特征，形式化描述的结果是基于空间关系检索的基础；第二，针对检索结果进行 排序，由于每个检索结果的匹配程度不同，应根据匹配程度的高低进行排序，匹配程度应该 有统一的计算模型进行量化，方便检索结果排序。本方案从拓扑关系和方向关系两个角度对 空间关系进行描述为检索提供基础，同时制定了一套相似度的计算模型来定量计算检索的匹 配程度用于检索结果排序。本发明是一种利用空间关系进行图像检索的方法，可以提升检索 效率和用户体验。

附图说明

图1为技术方案流程图；

图2为提取关联图流程图；

图3为8种面-面关系的9-交集模型示意图；

图4为两个几何对象相交示意图；

图5为基本方向关系的九宫格示意图；

图6为基于9-交模型面-面关系的拓扑相邻图；

图7为空间场景中拓扑关系约束放松示意图；

图8为几何对象的维度定义表；

图9为几何对象DE-9IM表；

图10为基于维扩展9-交集矩阵表。

具体实施方式

下面将结合附图对本发明做进一步详细说明。

基于空间关系的矢量地图检索方案，主要分为提取场景空间关系阶段、提取关联图阶段、 检索阶段、排序阶段和约束放松阶段，流程如图1所示，具体技术方案如下：

1、手绘检索场景作为检索输入。

2、提取拓扑空间关系阶段。对数据库场景和检索场景提取基于改进9-交模型的语义网络， 9-交语义网络是描述空间场景中任何两个对象间9-交关系的矩阵，是利用拓扑空间关系进行 检索的基础。

3、提取方向空间关系阶段。对数据库场景和检索场景提取基于基本方向关系的语义网络， 基本方向语义网络是描述空间场景中任何两个对象间相对方向的矩阵，是利用方向关系进行 检索的基础。

4、提取关联图阶段。创建基于检索场景和数据库空间场景之间改进9-交语义网络的关联 图。创建关联图的具体过程如下：

设检索场景G的点集为(v₁,...,v_n)、数据库场景H的点集为(u₁,...,u_N)，创建关联图分 为以下三个步骤：

(1)如果H中的一个点u_j满足检索场景G中某一个点v_i的约束，则在关联图中创建一 个点a_ij表示H中第j个点满足G中第i个点的约束；

(2)在关联图中存在点a_ij和a_kl，表示u_j满足v_i约束，u_l满足v_k约束。如果H中存在u_j到 u_l的空间关系满足G中v_i到v_k的空间关系约束，则关联图中点a_ij和a_kl之间存在边，表示 u_j到u_l的空间关系满足v_i到v_k空间关系的约束；

(3)重复(1)、(2)至无满足约束的点和边为止。

提取关联图步骤如图2所示，按上述步骤创建基于改进9-交语义网络的关联图，产生预 处理结果集(预处理结果集中的场景满足检索场景的拓扑关系，是一个粗略的结果集)。

5、检索阶段。利用步骤3中提取的基本方向关系语义网络，对预处理结果集提取基于基 本方向关系语义网络的关联图，提取基于基本方向关系语义网络的关联图可以消除预处理结 果集中方向空间关系不满足检索场景约束的检索结果，形成最终的检索结果集，提取基于基 本方向关系语义网络关联图的具体过程如下：

设检索场景G的点集为(v₁,...,v_n)、预处理结果集场景H'的点集为(u'₁,...,u'_N)，创建关联图 分为以下三个步骤：

(1)如果H'中的一个点u'_j满足预处理结果集场景G中某一个点v_i的约束，则在关联图中 创建一个点a′_ij表示H'中第j个点满足G中第i个点的约束；

(2)在关联图中存在点a′_ij和a′_kl，表示u'_j满足v_i约束，u′_l满足v_k约束。如果H'中存在u'_j到 u′_l的方向关系满足G中v_i到v_k的方向关系约束，则关联图中点a′_ij和a′_kl之间存在边，表示 u'_j到u′_l的方向关系满足v_i到v_k方向关系的约束；

(3)重复(1)、(2)至无满足约束的点和边为止。

6、排序阶段。利用本方案提出的相似性定量计算模型计算检索结果集中检索结果的相似 性分值。根据分值对检索结果中的检索结果进行排序，分值高的场景排序靠前，分值低的场 景排序靠后。

7、约束放松阶段。在检索结果集为空或结果集中的检索结果数目小于规定的检索数目时， 对空间关系进行约束放松，扩充检索结果集，增加命中检索目标可能性。对检索场景约束放 松之后，重新回到步骤4进行检索。

8、按相似性分值的高低在显示设备上输出检索结果。

本发明的检索方案主要包括提取场景空间关系阶段、提取关联图阶段、检索阶段、排序 阶段和约束放松阶段。涉及的主要模型和技术包括：1、改进的9-交模型；2、基本方向关系 模型；3、相似性定量计算模型；4、约束放松。

1、改进的9-交模型

(1)经典9-交模型

经典9-交模型是利用被描述的两个空间对象的内部、外部和边界是否相交来描述两个空 间对象的拓扑关系，故称9-交模型。利用9-交模型定义了面-面关系8种、线-线关系33种、 线-面关系19种，其中8种面面关系分别用符号Disjoint、Meet、Overlap、Cotains、Covers、 Inside、CoveredBy和Equal表示，如图3所示。

(2)改进9-交模型

改进9-交模型对经典9-交模型在维度上进行了扩展，更加具体的细化了对象间的空间关 系，可以更准确的反应对象间空间关系的细节。约定dim(a)表示几何对象的维度，在二维空 间中的取值为{-1,0,1,2}即记录两个几何对象交集的维度，其中-1代表交集为空。如图8所 示。

因此，在经典9-交模型的基础上，对9-交模型矩阵进行改进，对矩阵中每一个元素的值 进行了扩展，取值范围由原来的{0,1}扩展到{-1,0,1,2}，例如两个面区域相交得到的交集是 面，则dim(面)是2，该元素记为2。

如图4所示的两个几何对象，应用改进9-交模型，可以得到如图9所示的矩阵关系。最 终得到如图10所示的矩阵形式。

2、基本方向关系模型

基本方向关系采用的是九宫格形式描述两个空间对象的方向关系，即以一个空间对象的 外接矩形为基准，四条边向外延伸形成9个区域，形成九宫格。正中间的外接矩形标记为0， 以它为方向中心，从左上方开始顺时针方向依次标记为NW、N、NE、W、E、SW、S、SE， 如图5所示，相交部分对应的变量为1，不相交部分对应的变量为0。9个变量按NW、N、 NE、W、0、E、SW、S、SE顺序组成基本方向关系模型的字符串，作为检索的基础。

3、提取关联图

关联图是在检索场景和数据库场景之间空间对象及其相应的空间关系匹配时，由空间对 象和其相应的空间关系构成的图。关联图中的点表示数据库场景中存在一个点满足检索场景 中某一个点的约束，关联图中的边表示该边的两个点在数据库场景中对应点的空间关系满足 该边的两个点在检索场景中对应的空间关系约束。

设检索场景G的点集为(v₁,...,v_n)、数据场景H的点集为(u₁,...,u_N)，创建关联图分为 以下三个步骤：

(1)如果H中的一个点u_j满足检索场景G中某一个点v_i的约束，则在关联图中创建一 个点a_ij表示H中第j个点满足G中第i个点的约束；

(2)在关联图中存在点a_ij和a_kl，表示u_j满足v_i约束，u_l满足v_k约束。如果H中存在u_j到 u_l的空间关系满足G中v_i到v_k的空间关系约束，则关联图中点a_ij和a_kl之间存在边，表示 u_j到u_l的空间关系满足v_i到v_k空间关系的约束；

(3)重复(1)、(2)至无满足约束的点和边为止。

显然，关联图中的点和边一定在检索场景中有对应，并且一个关联图一定不会是另一个 关联图的子集，所以关联图一定是检索场景语义网络的极大团。当检索场景在数据库场景中 被完全检索时，关联图中点和边会对应检索场景中所有的点和边，关联图是检索场景的最大 团。

4、检索阶段

利用基本方向关系模型提取预处理结果集中场景和检索场景的语义网络关联图，消除预 处理结果集中方向空间关系不满足检索场景约束的检索结果，形成最终的检索结果集。

提取检索场景和预处理结果集场景的基本方向语义网络关联图的具体步骤如下：

设检索场景G的点集为(v₁,...,v_n)、预处理结果集场景H'的点集为(u′₁,...,u'_N)，创建关联图 分为以下三个步骤：

(1)如果H'中的一个点u'_j满足预处理结果集场景G中某一个点v_i的约束，则在关联图中 创建一个点a′_ij表示H'中第j个点满足G中第i个点的约束；

(2)在关联图中存在点a′_ij和a′_kl，表示u'_j满足v_i约束，u′_l满足v_k约束。如果H'中存在u'_j到 u′_l的方向关系满足G中v_i到v_k的方向关系约束，则关联图中点a′_ij和a′_kl之间存在边，表示 u'_j到u′_l的方向关系满足v_i到v_k方向关系的约束；

(3)重复(1)、(2)至无满足约束的点和边为止。

经过检索阶段处理得到最终的检索结果集，检索结果集中的场景经过9-交模型预处理排 除拓扑关系不一致的场景，然后经过基本方向关系模型检索消除方向关系不一致的场景。

5、相似性定量计算模型

相似性计算模型分为以下三步：

本发明的设计方案适用于所有的矢量空间场景，没有针对特定场景，如海图、气象等， 本方案认为所有的对象、关系都是平等的，故以下步骤中所有的权重值都为1。

(1)计算组件相似性

根据公式(1)计算关联图整体的空间关系的相似度S_Rel：

$S_{\mathrm{Rel}}=\frac{\underset{i=1}{\overset{M/(M-1)/2}{\Sigma }}{w}_{R_i}·s_{R_i}}{\underset{i=1}{\overset{M(M-1)/2}{\Sigma }}{w}_{R_i}}---\left(1\right)$

其中表示关联图中第i个空间关系在检索场景中的权重，代表第i个空间关系的相 似性分值。本发明中只有经过改进9-交模型和基本方向关系模型处理后得到的检索结果集中 的场景才计算相似性，即在拓扑关系和方向关系都满足的情况下相离关系与对象间距离成 正比，其它关系均为1；计算公式如式(2)：

$S_{R_i}=\frac{d_{r_i}}{D_{R_i}}---\left(2\right)$

其中，表示检索场景中第i个空间关系的距离，表示数据库场景中第i个空间关系 的距离。

(2)计算空间场景完整性

对于每个检索生成的非最大团的极大团的关联图都对应着一个不完全解，完全解的空间 场景相似性分值应该比不完全解的空间场景相似性分值要高一些，因此在不完全解中未匹配 的空间对象对最终的空间场景相似性分值应该有一个减少的影响。衡量检索场景和数据库场 景中未匹配的空间对象对空间相似性影响的量，称作空间场景完整性S_Comp(db,qry)，其计算公式 为：

$S_{\mathrm{Comp}(\mathrm{db},\mathrm{qry})}=\frac{M}{M+\alpha ·(n-M)+\beta ·(N-M)}---\left(3\right)$

其中，M代表关联图中匹配的对象数，N代表数据库场景中的对象数，n代表检索场景 中的空间对象数量，α代表检索场景中未匹配的空间对象的权重，β代表数据库场景中未匹 配的空间对象的权重。

上述公式粗略的刻画出了空间场景完整性S_Comp(db,qry)的性质，匹配的对象越多越接近1， 匹配的越少越接近0，其中α和β两个权重值可以更加灵活的控制空间完整性S_Comp(db,qry)的计 算结果。

a.如果α＝β＝1，表示匹配对象和不匹配对象对于空间场景完整性的影响是平等的，主要 应用在两个空间场景中的空间数量差不多需要比较细微不同的情况下，例如，在航拍中 区分拍摄日期；

b.如果α＝β＝0，表示有匹配的对象存在，则S_Comp(db,qry)为1，否则为0，使得空间场景相 似性仅仅依靠匹配的空间对象，忽略所有未匹配对象对空间场景相似性的影响。

c.如果α＝1,β＝0，表示只考虑检索场景中未匹配的空间对象对空间完整性的影响，主要 应用在局部检索中，可以对局部匹配出来的所有结果进行排序，反映出匹配的程度，应 用十分广泛。

本发明应用于局部场景检索，设置α＝1,β＝0，更加适合局部检索的特点。

(3)计算空间场景相似性

空间场景相似性的计算正是用到上述介绍的组件相似性和空间场景完整性的计算结果， 空间场景相似性是根据空间对象整体相似性和空间关系整体相似性在关联图中所占的权重进 行整体考虑的结果，其计算公式为：

$S_{\mathrm{Scene}(\mathrm{db},\mathrm{qry})}^{\prime }=\frac{(w_{\mathrm{Obj}}·S_{\mathrm{Obj}}+w_{\mathrm{Rel}}·S_{\mathrm{Rel}})}{w_{\mathrm{Obj}}+w_{\mathrm{Rel}}}---\left(4\right)$

其中，w_Obj表示在关联图中空间对象所占的权重，w_Rel表示在关联图中空间关系所占的权 重。

由关联图的相似性计算空间场景的相似性不仅要在考虑空间对象相似性和空间关系相似 性所占权重的基础上，还要考虑未匹配对象对相似性结果的影响，即引入空间场景完整性， 最终空间场景的相似性计算公式为：

S_{Scene(db,qry)}＝S'_{Scene(db,qry)}·(w_Comp·(S_Comp-1)+1)   (5)

其中，w_Comp表示在场景完整在空间场景检索中所占的权重。未匹配的对象越少，空间场 景完整性S_Comp(db,qry)越大，最终的空间相似性S_{Scene(db,qry)}越大，匹配程度越高。

6、约束放松

空间关系的约束放松是就临近概念而言的，临近概念是指把不同的空间关系按着一定的 规范组织在一起，相邻的两个空间拓扑关系称为临近。空间拓扑关系临近概念的具体化形式 是拓扑关系相邻图和方向关系相邻图。基于改进9-交模型面-面关系的拓扑相邻图，如图6所 示，描述了基于改进9-交模型的拓扑关系按空间对象相对位置远近原则组织在一起的相邻关 系，例如，disjoint与meet是相邻的、covers与overlap、contains和equal是相邻的。基于基 本方向模型的相邻图，如图7所示，有线连接的两个方向关系可以放松。