空间关系推理方法分类体系，本文主要内容关键词为：体系论文,关系论文,方法论文,空间论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：P208 文献标识码：A 文章编号：1672—0504（2009）03—0001—07
0 引言
空间关系及其推理广泛用于空间数据查询[1]、空间数据挖掘[2]、基于内容的图像检索[3]、空间关系的等价性和相似性[4]以及空间数据库的一致性维护[5—7]等。在上述应用中，有关矢量对象或图像对象的知识用少量符号组成的空间关系描述，如inside、overlap、contain、north和south等。定性空间推理利用符号空间关系的常识性知识，自动从已知空间关系的符号描述中推导出新的空间关系信息。这种推理是在蕴涵的知识和规则的基础上经过符号运算而完成的，无需几何计算。空间关系推理在以下领域发挥作用：1）检查现实世界中是否存在一些空间对象，其空间关系可以满足查询语句或空间关系的符号描述，基于空间关系推理，可发现符号描述中与实际情况不相符的空间关系；2）检测多源、多尺度空间数据的不一致性，以维护空间数据的逻辑一致性；3）评价多源、多尺度空间数据的等价性或相似性；4）确定一个空间关系符号集能否充分且唯一地描述一个空间场景[6]；5）提高多种空间关系约束的空间数据查询或结构检索的效率。
目前空间关系推理研究主要集中在单类型空间关系推理上，即根据拓扑关系推理拓扑关系、根据方向关系推理方向关系，而较少研究多种类型空间关系的混合推理。现有的各种空间关系描述模型相互独立，不能统一描述，因而较难进行多种空间关系的混合推理。空间关系推理是地理信息科学、人工智能、计算机科学等领域研究的热点，已提出了许多推理方法。为对这些推理方法进行分析和评价，需建立一套分类体系，并按照分类体系对已有方法的适用条件及解决的问题进行对比分析，了解各种方法的针对性和特殊性，不仅有利于正确理解和使用已有推理方法，更有助于研究和提出新的空间关系推理方法。但目前缺乏相关的分类体系，本文拟建立空间关系推理方法的分类体系，并在此体系内对已有方法进行对比分析。
1 空间关系推理分类体系
在实际应用中，使用哪种空间关系推理取决于已知的空间信息及待推理的空间关系。Sharma进一步指出，集成空间关系推理所得结果与其它3种推理方法组合推理所得结果相同[8]。
Sharma在上述分类的基础上，对方向关系采用投影模型，拓扑关系采用九交模型，定性距离采用间隔表示，实现了上述4种推理方法。由于用投影方法描述简单面对象的方向关系，因而不能正确推理方向关系；尤其是他仅关注简单方向关系推理，而没有涉及复杂方向关系推理，推理的效率和准确性受到限制。若用方向关系矩阵建模面对象的方向关系，推理结果会更精确，因此探讨方向关系矩阵和拓扑关系组合推理方法非常必要。
1.2 基于空间关系描述模型的分类
当采用不同的模型对同一对象的空间关系建模时，往往会有不同的结果。同样，采用不同的模型，也会导致不同的推理方法和结果。根据空间关系推理方法所采用的模型，可将空间关系推理分为基于同种模型及组合多种模型的推理。其中，基于同种模型的推理指已知和需要推理的空间关系均由相同的模型描述，包括基于RCC模型的拓扑关系推理[9]、基于九交模型的面对象拓扑推理[10]、基于投影方法的方向关系推理[11]、基于方向关系矩阵的方向关系推理[12]等。组合多种模型的推理指已知的空间关系采用不同的模型描述，需要推理的空间关系可为两个模型中的任一个，其典型例子为组合内部方向关系和外部方向关系推理内部或外部方向关系[13]、组合多种方向关系的拓扑关系推理[14,15]、组合九交模型和通用交模型推理线／面拓扑关系[16]等。
需要指出的是，不是任意的两种模型组合都有意义，如组合RCC模型和九交模型没有意义，组合关系矩阵和锥形模型也没有意义。只有两个模型描述的空间关系概念不同，确实能提供互补信息时，组合才有意义。如方向关系矩阵和内部方向关系互补，因而可以组合推理；而方向关系矩阵和投影方法都描述外部方向关系，它们是竞争关系，因而其组合没有意义。
1.3 基于参照系统的分类
空间关系推理本质是一种符号运算，因而在运算中，须考虑符号的含义及其参照系统。这里的参照系主要针对方向关系而言，因为拓扑关系和距离关系没有参照系，但方向关系的定义和描述却离不开参照系。已有方向关系推理主要针对两个参照系，即两个已知方向关系的参照对象不相同：如从A与B及B与C间的方向关系推理A与C的方向关系或拓扑关系；在该例中，两个已知方向关系的参照对象分别是A和B。在实际应用中，由于已知方向关系和未知空间关系的条件限制，可能需要另一种推理机制：已知A与B及A与C间的方向关系，推理B与C的方向或拓扑关系；在这种推理中，两个方向关系共用1个参照对象A，因而为基于1个参照系的空间关系推理[14,15]。基于1个参照系的推理是对基于2个参照系推理方法的有益补充。
1.4 基于空间对象动态变化的分类
根据推理方法所针对的空间对象是否随时间发生形状改变或移动，可将空间关系推理分为静态空间关系推理和动态空间关系推理。空间对象的时变特征导致空间关系是动态变化的。动态空间关系推理的一个关注点是根据两个已知时间点的空间关系推理中间状态的空间关系。由于空间对象的动态变化可分为连续（如污染区扩散）和离散（地块的合并与分裂）变化两种类型，且这两种变化往往采用不同的建模方法，因而导致其空间推理方法也不一致。
1.5 基于空间对象类型的分类
空间对象类型也会影响空间关系推理方法，如对象类型不同，导致基本空间关系的个数不同或采用的模型也不同。对于拓扑关系而言，面／面有8个基本拓扑关系，线／面有19个基本拓扑关系，线／线有33个基本拓扑关系，点／线、点／面有3个基本拓扑关系，而点／点有2个基本拓扑关系。由于基本拓扑关系的个数、含义和名称不同，导致不同类型对象组合推理时，会有不同的方法和结果。对于方向关系而言，对象类型会影响方向关系描述模型的选择。例如，若点为参照对象，则基于锥形的模型比较适合；若参照对象为面对象，则方向关系矩阵可能较好。目前，尚未出现一个能兼容点、线、面的方向关系模型。由于上述原因，很多空间关系推理方法都适合于某一类型对象，适用于多种对象类型的空间关系推理方法较少；或者一些通用的方法对于某些对象类型（如线对象）推理结果可能不够精确。
1.6 基于空间对象复杂程度的分类
根据空间对象复杂程度，空间关系推理方法可分为简单对象空间关系推理和复杂对象空间关系推理。已有的大多数空间关系推理方法都针对简单对象，实际应用往往需要处理各种复杂对象，如确定复杂对象（对象边界和范围能明确定义、几何结构复杂，如带洞的面对象、由多个子区域组成的复合面对象甚至更复杂的对象）及宽边界区域（边界和范围不能明确定义，用一个宽边界来概略描述对象的不确定部分）。简单对象空间关系推理是目前研究最广泛的，如基于九交模型的面对象拓扑关系推理[10]、基于方向关系矩阵的面对象方向关系推理[12]等。由于简单对象不可再分，且结构简单，因而推理方法简单且具有代表性。复杂对象可由相同空间维或不同维简单空间对象组成，结构复杂，如同质或异质网络。复杂对象空间关系推理不仅能在复杂对象层面上进行，还能在简单对象及不同层次对象间进行，典型例子为多尺度数据库中同质或异质网络拓扑结构一致性推理及检测[17]。
1.7 基于对象尺度特征的分类
根据空间尺度可将空间关系推理方法分为单一尺度推理和多尺度推理：单一尺度空间关系推理未对空间尺度建模，只能处理单一尺度的对象，大多数空间关系推理都属于该类别；多尺度空间关系推理直接对空间尺度特性建模，可在多个尺度上进行空间关系推理。对象的粗略尺度表示往往比详细尺度表示具有更简单的结构、形状和较低的空间维。多尺度推理主要从已知的详细尺度的空间关系和空间结构推理粗略尺度的空间关系，需统一考虑对象结构、形状和空间关系多种因素的影响，其典型例子是多尺度数据库中空间关系一致性的评价和检测[18,19]。目前的多尺度空间关系推理主要集中在由详细尺度、复杂结构、高空间维对象空间关系推理粗略尺度、简单结构、低空间维对象的空间关系。
1.8 基于对象层次特征的分类
根据对象层次特征可将空间关系推理方法分为单层次和多层次空间关系推理。单层次空间关系推理在单一层次上进行，主要针对简单、没有层次结构的空间对象，大多数空间关系推理都属于该类别。多层次空间关系推理利用不同层次对象的空间关系约束进行，如根据高层次对象空间关系推理低层次和同层次对象空间关系，利用同层次对象空间关系推理低层次和高层次对象空间关系，利用低层次对象间空间关系推理高层次对象空间关系，典型例子为复杂宽边界区域子区域间拓扑关系的层次依赖推理[20]、层次方向关系推理[21]。
2 已有空间关系推理方法分类评述
图1表示由8个指标组成的空间推理方法分类体系，某个空间关系推理方法可以同时属于其中的多个分类。因此，按照上述分类体系，可把已有空间关系描述模型与推理方法进行归类对比，有利于正确理解和使用已有模型和方法。单种空间关系推理中可进一步根据空间关系模型进行区分，如基于投影模型的方向关系推理、基于方向关系矩阵的方向关系推理；而拓扑关系推理可分为基于九交模型的拓扑关系推理、基于RCC模型的拓扑关系推理等。由于空间关系描述模型不同，可能导致不同的推理方法和推理结果，这对于方向关系尤为重要。
2.1 拓扑关系推理方法分类评述
拓扑关系模型主要有两大类：基于点集拓扑的模型和基于描述逻辑的模型。Egenhofer等提出的九交模型[22]是典型的基于点集的模型，它能统一描述点、线、面拓扑关系。在此基础上，Abdelmoty等扩展了拓扑九交[23]，提出了广义拓扑关系模型，以描述和推理形状复杂的对象拓扑关系；Chen等用空间对象Voronoi区域代替九交中外部集合，以区分分离和邻近拓扑关系[24]；Schneider等进一步扩展了九交模型，定义和区分了复杂点、线、面对象的拓扑关系[25]。基于描述逻辑的拓扑关系模型以RCC理论为代表[9]，它仅描述面对象拓扑关系，不能描述不同空间维拓扑关系。尽管九交模型和RCC理论采用了不同的方法描述拓扑关系，但它们在描述和推理简单面对象拓扑关系时具有相同的结果。表1对代表性的拓扑关系描述模型和推理方法进行分类对比与评述，得出以下结论：1）在拓扑关系描述方面，基本可处理简单和复杂点、线、面拓扑关系；而在拓扑关系推理、方面，仅集中在简单点、线、面拓扑关系推理，缺乏复杂对象拓扑关系推理方法。2）移动对象、多尺度、多层次拓扑关系推理研究仍需加强，尤其是顾及复杂对象层次结构的多尺度、多层次拓扑关系推理方法。
图1 空间关系推理方法分类体系
Fig.1 The classification system for spatial reasoning methods
2.2 方向关系推理方法分类评述
方向关系用于描述两个空间对象的相对位置关系，主要分为外方向关系模型和内方向关系模型[13]。外方向关系模型描述与参照区域外部有关的方向概念，有锥形模型、三角模型、间隔关系模型、2-DString串模型、符号阵列、MBR模型、方向关系矩阵模型和基于Voronoi图的模型等；这些模型采用不同的方式来近似空间对象，从不同的角度描述外部方向关系，因而具有不同的适应性特点，是竞争关系。内方向关系模型描述与参照区域内部或边界有关的方向概念，主要有基于投影和基于锥形的两种。
内方向关系模型与外方向关系模型是互补的，可组合使用，具有以下特点：1）内方向关系模型和外方向关系模型分别是为描述空间对象内部和外部的方向概念而设计的，因此内方向关系是对外方向关系的有益补充；2）内方向关系所描述的概念与外方向关系模型互相补充，同时对空间对象形状的描述能力也是互相补充的，组合内方向关系模型和外方向关系模型既能弥补已有方向关系模型不能描述的方向概念，也能处理空间对象形状复杂时的方向关系；3）目前描述外方向关系的不同模型的组合较少，因为它们描述相同的方向概念，是竞争关系。
表2对不同方向关系模型所采用的近似方式、描述的概念类型以及方向关系推理方法所依据的方向关系模型进行了分类对比和评述，得出以下结论：1）从研究文献看，方向关系矩阵模型受到重视；2）移动对象方向关系和多尺度方向关系推理方法尚有欠缺，需研究时空连续变化对象方向关系的演化规律及其查询实现；3）针对不同的外方向关系模型，有不同的推理方法和推理结果，目前尚无结论表明哪个模型更适合描述外方向关系，应在分析比较已有外方向关系模型的基础上，提出可行的解决方案。
2.3 多种空间关系组合推理方法分类评述
从表3可看出，已有空间关系推理方法具有以下特点：1）在组合多种空间关系推理方面，对方向关系和拓扑关系采用了不同的模型。例如，方向关系矩阵与拓扑关系九交模型的组合，而方向和拓扑关系的其它模型组合推理方法较少（注：RCC方法与拓扑九交基本等价，因此RCC与方向关系矩阵组合和九交模型与方向关系矩阵组合类似）。2）已有的方向关系推理方法都采用了外部方向关系模型，由于该模型采用近似形状计算方向关系，对空间对象形状不敏感，因而不能有效完成相交、包含等复杂情况下的空间关系推理；而内方向关系对空间对象形状敏感，与外方向关系组合，能处理相交、包含等复杂情况下的空间关系推理。3）拓扑和方向关系组合推理方法研究不充分，Sharm提出的4种推理方法采用间隔模型描述方向关系，推理结果不够准确；若采用更准确的方向关系模型，如方向关系矩阵，则它与拓扑关系的组合推理体系尚不完善。4）针对简单对象的空间关系推理较多，而复杂对象拓扑和方向关系推理问题较少，尤其是复杂对象间多种类型空间关系组合推理更少。复杂对象存在固有的层次结构，已有方法在描述和推理过程中较少涉及复杂对象的内在层次结构，即多层次的描述与推理模型不够。采用多层次的描述与推理方法，研究和发展顾及层次结构的复杂对象拓扑、方向关系组合描述模型与组合推理方法，不仅能在高层上描述复杂对象总体空间关系，适用于查询等面向用户的高级应用；同时在低层上描述复杂对象中子对象之间的空间关系，适用于一致性检测等面向几何处理的应用，能满足多种应用需求。
3 结论
本文将空间关系类型、空间关系描述模型、推理参照系统、空间对象动态变化、空间对象类型、空间对象的复杂程度、对象尺度特征、对象层次特征8个因素作为指标，建立了空间关系推理方法分类体系；并以此体系为标准，对比和分析了已有空间关系推理方法。上述分类体系是针对确定空间关系推理的，并未考虑空间对象的不确定性。这是因为不确定空间关系与确定空间关系是并列的，因而本文分类体系也适用于不确定空间关系（不确定对象也有复杂简单之分，不确定空间关系也有单尺度与多尺度之分等）。从空间关系推理发展趋势看，不确定区域的空间关系描述与推理已成为研究的重点领域，不确定区域的拓扑和方向关系描述、计算取得了一定的进展，但不确定区域空间关系推理尤其是不确定区域拓扑和方向的组合推理正在发展中。
收稿日期：2008—12—01；
修订日期：2009—02—28