基于OPRAm 的三维相对方位关系模型

欧阳继红，祝东红，，富 倩，杨 帅，陈 思

（1.吉林大学 计算机科学与技术学院，长春130012；2.吉林大学 符号计算与知识工程教育部重点实验室，长春130012）

0 引 言

空间推理是人工智能、地理信息系统、机器人、计算视觉、图像检索、自然语言处理等领域的重要内容［1］。空间推理主要研究拓扑和方位关系，王生生等［2］给出了有向线对象细节拓扑关系模型；Moratz［3］提出了具有可扩展粒度方位点关系代数OPRAm模型，用于描述方位点的相对方位关系。Dylla等［4］给出OPRAm模型的概念邻域图。Moratz等［5］给出了其复合算法。

近年来，随着空间推理应用研究的不断深入，三维空间的应用研究越来越多，因此需要研究适用于三维空间的方位关系表达和推理模型［6］。关于三维空间方位关系的研究主要分为两方面：点对象间相对方位关系和区域对象间的方位关系，如Pacheco等［7］提出的三维点对象间的相对方位关系模型和Chen等［6］提出的基于MBR 的三维区域对象间的主方位模型。然而Pacheco提出的模型是基于双十字模型的，对空间关系划分不够细致，表达相对方位关系较弱。Chen等提出的模型是针对区域的，区域对象间的方向关系比点对象之间的方向关系较为复杂。然而在实际应用中当对象间距离比较大时，通常将对象抽象为点更为合适，同时也降低了方位关系的复杂度。因此，需要研究适用于三维空间点对象间的相对方位关系表达和推理模型。

本文基于二维OPRAm模型，通过引入新的三维空间的两个相对角来表达三维相对方位信息，得到三维点对象间的相对方位关系模型3DOPRAm。在此基础上，给出了3DOPRAm模型的概念邻域及导航问题的形式化表示。最后，采用新模型基于动作的邻域关系描述了汽车导航问题。

1 相关理论

1.1 方位点关系代数OPRAm

Moratz［3］在直线段模型的基础上提出了一种具有可扩展粒度的相对方位关系模型OPRAm，使用一个方位点（有方向的点）表示空间对象。粒度参数m ＞0∈n决定方位点的区分粒度，m 条线将二维平面划分为2m 个线性区域和2m 个平面区域。区域按逆时针方向从0到（4m－1）进行编号，区域0和方位点的本质方向重合。图1给出了m＝2（见图1（a））和m＝4（见图1（b））时，平面上不同位置方位点A 和B 的相对方位关系；图1（c）给出了平面上两个相同位置方位点的相对方位关系。

图1 两个方位点之间的相对方位关系Fig.1 Relative directions between two oriented point

1.2 邻域划分图

Freksa［8］首次定义了概念邻域图（Conceptual neighborhoods graph，CNG），并将概念邻域结构用于处理时间区间代数中时间区间连续变化的问题。宋小华等［9］指出概念邻域图只给出了空间关系变化的结果，没有给出空间关系变化的原因，不知道是什么引起空间关系发生变化。宋小华在概念邻域图的基础上，引入“动作”的概念，他认为空间关系的变化是因为在对象上施加了动作。

如果有动作关系集合A，能够使互斥完备的基本关系集合B 概念邻域图CNG（B）中的邻域关系相互转换，则称集合A 为完备动作关系集合。由完备动作关系集合A、基本关系集合B 和B通过A 转变的邻域关系集合≈，构造一个能表示基本关系随动作变化的图，则称此图为邻域划分图（Neighborhood partition graph，NPG），其形式表示如下：

对任意原子关系b ∈B，其基于动作的邻域关系表示为np（b），其形式表示如下：

2 三维相对方位关系3DOPRAm

2.1 三维空间中粗粒度方位点模型

三维空间中，以点为空间变量，方位点使用有序对S＝（PS，δS）表示，其中PS是方位点S 的笛卡尔坐标PS＝（xS，yS，zS）；δS表示方位点的本质方向。δS平行于地面，它所在的平面为xoy 面，垂直于xoy 面的方向为z 轴，图2 为3DOPRAm模型参照系。

使用xoy 面的相对方位和z 轴的相对方位组合表示三维空间的相对方位关系。其中xoy 面的方位划分如图3所示，使用字母f、b、l、r、lf、rf、lb、rb 代 表 front、back、left、right、leftfront、rightfront、leftback、rightback；z 轴方位划分如图4所示，使用字母U（up）、D（down）分别表示位于xoy 面的上方和下方；E（equal）表示恰好在xoy 平面上；前两个“＊”表示xoy 面上的方位关系，第3个字母表示z轴方位关系。

图2 3DOPRAm 模型参照系Fig.2 Reference system of the 3DOPRAm model

图3 xoy面方位划分Fig.3 Directions in the xoyplane

图4 z轴方位划分Fig.4 Directions of the z－axis

为了区分三维空间中的两个方位点A 和B，令A ＝（PA，δA），其中PA＝（xA，yA，zA），令B ＝（PB，δB），其 中PB＝ （xB，yB，zB）。对 二 维OPRAm模型相对角进行扩展，引入两个相对角φAB和θAB，如图5所示，其定义如下：

式中：φAB 为方位点B 在方位点A 所确定的xoy面投影后，两个方位点之间的反正切值。

式中：θAB为方位点B 和方位点A 之间连线与xoy面所成的角。

图5 三维空间中方位点A 和B 之间的相对角φAB 和θABFig.5 Relative anglesφAB andθAB of two oriented points in the three dimensions

在三维空间中，φAB－δA表示方位点B 在方位点A 所确定的xoy 面方位；φBA－δB表示方位点A在方位点B 所确定的xoy面的方位。相对角θAB表示方位点B 在方位点A 的z 轴方位。其中φAB－δA和θAB对应角度的变化构成方位点A 所在的欧几里得空间的完备划分，其所对应的方位和角度变化如表1所示，方位点B 所在欧几里得空间的划分和方位点A 类似。

2.2 三维空间中粗粒度方位点相对方位关系

三维空间中，使用三元组（QAB、QBA、ZAB）表示空间中的两个方位点之间的方位关系。QAB表示xoy 面上方位点A 相对于方位点B 的方位关系；QBA表示xoy 面上方位点B 相对于方位点A的方位关系；ZAB表示方位点B 相对于方位点A的z 轴方位关系。

xoy 面上，两个方位点在不同位置时，总共有8×8＝64种基本关系。当两个方位点在同一位置时，有8种方位关系；故xoy 平面上共有72种原子方位关系。z 轴有以下5种方位关系ZAB＝｛U1、U2、D1、D2、E｝。可得出三维空间中总共有360种方位关系。

表1 方位点A 所在三维欧几里得空间划分Table 1 Apartition of oriented point A on the Euclidean plane

2.3 可扩展粒度3DOPRAm 模型

空间演算的粒度和空间结果的数学特性是解决定性空间任务的主要问题［10］。在实际应用中（如复杂导航任务），依据所处的环境、机器人的处理能力、任务的要求，需要不同粒度下的方位关系，因此引入了可扩展粒度。选择合适的粒度参数可以忽略一些不能引起变化的推理步骤，加快计算速度。

将上述粗粒度相对方位关系的设计准则扩展到多粒度的情况，得到3DOPRAm，其中m 为粒度参数，m ＞0∈n将二维平面划分为2m 个线性区域和2m 个平面区域。区域按逆时针方向从0到（4m－1）编号，区域0和方位点的本质方向重合。m 条线将z 轴正半轴划分成m 个方位，从xoy 面按逆时针编号；将z轴负半轴划分成m 个方位，从xoy 面按顺时针编号。

xoy 面上，可扩展粒度方位关系中每一个方向片i满足如下角度范围：

方向片j的角度范围和方向片i 相同。当PAPB时，使用关系A∠ijB 表示如下含义：给定粒度m，以B 为参照对象，A 相对于B 的位置用j描述，以A为参照对象，B相对于A 的位置用i描述。其中方向片i，j满足如下几何结构：

当PA＝PB时，使用关系A∠iB 表示如下含义：给定粒度m，以A 为参照对象，B 位于A 的方位。方向片i满足如下几何结构：

在z轴上的方位，可扩展粒度方位关系中方向片h满足如下角度范围：

A∠hB 表示以A 为参照对象，B 相对于A 的高度范围。方向片h满足如下几何结构：

三维空间中的相对方位关系用xoy 面和z 轴相对方位关系组合表示，对三维空间中的方位点A 和B，当A 和B 的位置不同时，使用表示，含义为：xoy 面上，对于B而言，B在A 的方位用i表示。对于A 而言，A 在B 的方位用j 表示；z轴上，h表示以A 为参照对象，B相对于A 的高度。当A 和B 的位置相同时，使用A∠ihB 表示，含义为：对于B而言，B在A 的xoy 面的方位用i表示，z轴的方位用h 表示。图6和图7为粒度m ＝2的三维空间中方位点的相对方位关系：表示角度范围为：φAB－δA＝3π／2，φBA－δB＝π／4，θAB∈（π／4，π／2］。A2∠40B 表示角度范围为δBδA＝π，θAB＝0。

图6 不同位置两个方位点的相对方位关系Fig.6 Two o－point in relation relation at different position

2.4 3DOPRAm 相对方位关系的逆

方向关系取逆操作是方向关系的基本运算之一，对于空间中的两个点对象A 和B，已知它们的关系为R ＝（A，B），通过求逆操作可以得到R ＝（B，A）。在3DOPRAm模型中，通过简单的符号操作，即可求得3DOPRAm模型的逆操作。

当三维空间中方位点A 和B 在不同位置时，方位点的逆为：

当方位点A 和B 在相同位置时，方位点的逆为：

图7 相同位置方位点的相对方位关系A2∠40BFig.7 Two o－point in A2∠40Bat the same position

3 3DOPRAm 概念邻域及定性空间导航问题

为了将3DOPRAm模型用于描述定性空间导航问题，本文给出了基于3DOPRAm模型的概念邻域及导航问题形式化的表示。通过设定规则，将动作引起邻域关系变化用于求解导航问题。

3.1 3DOPRAm 概念邻域

基于二维空间中OPRAm模型的概念邻域，给出了3DOPRAm模型的概念邻域。由于在实际应用中，不同空间对象所施加的动作是不同的，或者是在研究空间关系时，因为参照对象是较少发生变化或基本不发生变化，只需要研究目标对象的动作即可，因此针对3DOPRAm模型，需要根据实际应用场景和特定相对方位关系，给出其引起关系变化的动作。

当三维空间中相对方位关系为Am∠jihB 时，对A 和B 施加任意动作可得到如下概念邻域：

当三维空间中相对方位关系为Am∠shB 时，对A 和B 施加任意动作可得到如下概念邻域：

3.2 定性空间导航问题

宋小华等［9］提出了定性空间关系自动规划的形式化表示和推理算法，并证明此算法的可靠性，同时指出其方法在处理单方面空间关系规划中具有通用性。基于此思想，本文给出了定性空间导航问题的形式化表示和基本求解思路。

定性空间导航问题描述：直观上，定性空间关系的导航就是给定初始状态对象间的空间关系和目标状态对象间的空间关系的表示，求解从初始状态到目标状态的动作序列。

定义1 定性空间关系导航是一个动作序列π＝〈a1，a2，…，ak〉，其 中k ≥0，导 航 的 长 度 是｜π｜＝k，即动作数目。

定义2 称N ＝（s，g）是一个定性空间关系导航问题，其中s为定性空间关系初始状态；g 为定性空间关系目标状态，从s经过动作序列π到达目标状态g，则π是N 的一个解。

定性空间关系导航问题求解：

求解定性空间关系导航问题，就是以N ＝（s，g）作为输入，求解动作序列π的过程。

使用递归回溯方法求解此类问题，其基本思路为：对初始邻域状态分别按顺序施加动作，到达下一个动作邻域状态。删除掉规则不允许和产生循环的动作邻域状态后，对产生的动作邻域状态进行递归求解，直至转换到目标状态。如果找不到目标状态，返回失败。

4 应用举例

基于3DOPRAm动作邻域关系对立交桥上的汽车进行导航。以粒度m ＝2为例，粒度m ＝2将xoy 面的方位分为0、1、2、3、4、5、6共七个方向片，将z轴方位分为0，1，2，－1，－2共五个方向片。

如图8所示，立交桥的入口处有个汽车，其运动状态如方位点A所示。分别设置如图8所示的3个目标状态，如方位点B、C、D 所示，3个方位点的方向为箭头的方向。汽车可操作的动作分别为向前、向后（倒车操作）、向左（即车头转向左行驶）、向右（即车头转向右行驶）、向上（沿坡道向上行驶）、向下（沿坡道向下行驶）共6个动作，在立交桥一些位置制定一些交通规则，对汽车进行导航，求解出汽车从方位点A 所示状态变化到方位点B、C、D 所示状态的动作序列。

以汽车从方位点A 所示状态变化到方位点C所示状态为例说明基于动作邻域关系变化的导航问题的求解过程。

图8 立交桥汽车导航场景Fig.8 Spatial scenario about Car Navigation on the flyover

方位点A 和方位点C 的最终相对方位关系为：A2∠00C

对汽车施加如下动作序列：向前、向前、向右、向右、向右、向下、向前、向右、向右、向下、向右、向前，得到状态变化如下：

同样，得到方位点A 到达方位点B 和D 的动作序列分别为：向右、向上、向前、向前，它们的状态变化如下：

5 结束语

在OPRAm模型的基础上，提出了点对象间的相对方位模型3DOPRAm，此模型不仅能够表示平面上的前后左右等方位关系，而且能够表示高度的上中下等方位关系，具有更强的表达能力。与已有三维点对象间相对方位模型——双十字模型相比，此模型具有可扩展粒度m，能表达更细致的方位关系。在此基础上，给出了3DOPRAm模型的概念邻域。最后基于其动作的邻域关系，将新模型应用于描述基于约束规则的汽车导航空间场景中。

［1］Cohn A G.Qualiative spatial representation and reasoning techniques［J］.LNCS，1997，1303：1－30.

［2］王生生，王兆丹，刘大有，等.有向线对象细节拓扑关系模型［J］.吉林大学学报：工学版，2009，39（5）：1292－1296.Wang Sheng－sheng，Wang Zhao－dan，Liu Da－you，et al.Detailed topological relation model of directed line objects［J］.Journal of Jilin University（Engineering and Technology Edition），2009，39（5）：1292－1296.

［3］Moratz R.Qualiative spatial reasoning about oriented points［R］.SFB／TR8Spatial Cognition，2004.

［4］Dylla F，Wallgrün J O.Qualitative spatial reasoning with conceptual neighborhoods for agent control［J］.Journal of Intelligent and Robotic Systems，2007，48（1）：55－78.

［5］Mossakowski T，Moratz R.Qualitative reasoning about relative direction of oriented points［J］.Artificial Intelligence，2012，180－181（2）：34－45.

［6］Chen J，Liu D，Jia H，et al.Cardinal Direction Relations in 3DSpace［M］.Berlin Heidelber：Springer，2007：623－629.

［7］Pacheco J，Escrig M T，Toledo F.Integrating 3D orientation models［C］∥5th Catalonian Conference on Artificial Intelligence，Lecture Notes in Artificial Intelligence，Springer Berlin Heidelberg，2002，2504：88－100.

［8］Freksa C.Temporal reasoning based on semi－intervals［J］.Artificial Intelligence，1992，54（1－2）：199－227.

［9］宋小华，欧阳丹彤.一种动态定性空间关系自动规划方法［J］.软件学报，2012，23（10）：2564－2571.Song Xiao－hua，Ouyang Dan－tong.Automated planning method for dealing with dynamic qualitative spatial relations［J］.Journal of Software，2012，23（10）：2564－2571.

［10］Moratz R，Dylla F，Frommberger L.A relative orientation algebra with adjustable granularity［C］∥Proceedings of the Workshop on Agents in Real－time and Dynamic Environments，2005：61－70.