空间关系建模主要研究空间对象的表示方法、对象间空间关系的表示方法与推理方法. 不确定性是现实世界的一种重要属性，在地质勘探、机器人导航、智能交通、图像处理等领域中都存在着具有不确定边界的空间对象，此类对象间的空间关系建模已引起广泛关注^{[1, 2]}. 目前相关研究主要针对区域对象，且多针对空间拓扑关系，方向关系研究较少.

现有不确定区域间方向关系表示模型多是基于粗集和模糊集理论或是对已有精确模型(锥形模型、方向关系矩阵模型)的简单扩展. 在推理方面，目前多基于确定区域间的主方向关系^{[3, 4, 5, 6]}，不确定区域间方向关系推理研究尚处于起步阶段.

笔者针对具有不确定边界的区域对象，研究此类区域间的方向关系建模. 首先简要介绍主方向关系模型的相关定义；然后利用宽边界对不确定区域进行表示；基于确定区域间的主方向关系模型，采用组合方法描述不确定区域间的方向关系；在此基础上定义不确定区域间方向关系与约束，并研究不确定区域间方向关系约束规则；最后采用约束满足问题求解技术对不确定区域间方向关系进行推理.

现有方向关系建模主要针对确定区域对象. 所有确定区域的集合用 $\Re $ ^[3]表示. 在描述确定区域a相对于b的方向关系时，称a为主区域，b为参照区域. 通过b的最小边界矩形(MBR，minimum bounding rectangle)为G(b)，将平面空间划分成9个方向片，即B_(b)、N_(b)、NE_(b)、E_(b)、SE_(b)、S_(b)、SW_(b)、W_(b)、NW_(b)，分别表示b的中心、北、东北、东、东南、南、西南、西和西北方向，进而构成由区域b确定的参照系统π(b).

定义1 R=R₁:…:R_k是一个基本主方向关系，如图 1所示. 其中：1) 1≤k≤9; 2) R₁,…,R_k∈{B,S,SW,W,NW,N,NE,E,SE}; 3) 对每个i和j，若1≤i,j≤k,i≠j，则R_i≠R_j; 4)对任意一个参照区域b∈ $\Re $ ，存在区域a₁,…,a_k∈ $\Re $ ，其中a₁∈R₁(b),a_k∈R_k(b)且a₁∪…∪a_k∈ $\Re $ ^[3].

Figure 1

		Figure Option ViewDownloadNew Window
		图1 基本主方向关系模型

基本主方向关系是由若干个方向片构成的表达式，表达式中方向片之间无顺序要求，例如B:E与E:B表示同一基本主方向关系. 特殊地，当k=1时，R₁:…:R_k称为单片关系. 主方向关系模型共包含218个基本主方向关系，记为 U .

例如，图 1中的区域a位于b的东北和东方向，记为a NE:E b.

定义2 若一个基本主方向关系R为矩形关系，当且仅当存在2个矩形区域a和b，使得a R b^[3].

定义3 R₁=R₁₁:…:R_1n与R₂=R₂₁:…:R_2m是2个基本主方向关系，若有{R₂₁,…,R_2m}⊆{R₁₁,…,R_1n}，则称R₁包含R₂，记为R₂⊆R₁^[3].

类似地，R₁=R₁₁:…:R_1n是基本主方向关系，R₂为方向片，若R₂∈{R₁₁,…,R_1n}，则称R₁包含方向片R₂，记为R₂∈R₁.

定义4 R为一个基本主方向关系，包含R的最小矩形关系(方向片数目最少)称为R的边界关系(BR，bounding relation)，记为r(R)^[3].

定义5 R为一个矩形关系，由R的最左方向片构成的矩形关系记为M(W,R). 类似地，可定义M(S,R)、M(N,R)、M(E,R)、M(NE,R)、M(NW,R)、M(SE,R)和M(SW,R). 特殊地，定义M(B,R)=R^[3].

主方向关系模型的相关定义详见文献^{[3, 4]}.

导致空间关系具有不确定性的原因很多，例如人们认知的不确定性、空间对象属性(位置、边界等)的不确定性、信息采集和分析过程中的不确定性等. 笔者研究具有不确定边界的区域对象间的方向关系.

定义6 1个宽边界区域a由2个区域a₁和a₂组成，其中a₁、 a₂∈ $\Re $ ，a₁∈a₂. 将a₁,a₂分别称为a的内区域和外区域，a₁、 a₂的边界分别用 $\partial $ a₁和 $\partial $ a₂表示^[7].

定义7 若a是1个宽边界区域，则a的宽边界记为Δa，其中Δa= $\partial $ a₁∪ $\partial $ a₂∪(a₂-a₁)^[7].

例1 图 2(a)和图 2(b)分别表示确定区域a₁和a₂，图 2(c)表示分别以a₁、 a₂为内、外区域构成的宽边界区域，2条边界和其间的深色部分表示区域的宽边界.

Figure 2

		Figure Option ViewDownloadNew Window
		图2 确定区域与宽边界区域

可用宽边界区域表示具有不确定边界的区域. 宽边界区域的外区域表示不确定区域的最大空间范围；内区域表示不确定区域的确定空间范围；外、内2个区域的差集和二者的边界表示不确定边界.

宽边界区域的内、外区域均为确定区域，因此可利用确定区域间的方向关系研究宽边界区域间的方向关系. 下面以218个基本主方向关系表示内、外区域间的方向信息，通过组合表示方法定义宽边界区域间的方向关系.

定义8 D=〈D₁,D₂,D₃,D₄〉为1个宽边界方向关系，当且仅当存在2个宽边界区域a和b，其中a₁、 b₁分别为a、 b的内区域；a₂、 b₂分别为a、 b的外区域，使得a₁ D₁ b₁、 a₁ D₂ b₂、 a₂ D₃ b₁、 a₂ D₄ b₂、 D_i∈ U ，1≤i≤4.

例2 如图 3所示，宽边界区域a(a₁为内区域，a₂为外区域)相对于宽边界区域b(b₁为内区域，b₂为外区域)的宽边界方向关系为〈NW,NW,NW:N,NW:N〉，记为a 〈NW,NW,NW:N,NW:N〉 b.

Figure 3

		Figure Option ViewDownloadNew Window
		图3 a 〈NW,NW,NW:N,NW:N〉 b

当a₁=a₂或b₁=b₂，即主区域或参照区域为确定区域时，a与b之间的方向关系可视为宽边界方向关系模型的特例，同样可用宽边界方向关系进行表示.

对于218个基本主方向关系，并非任意4个基本主方向关系的组合都可表示宽边界区域间的方向关系. 例如〈NW,NW,N:NW,NW:N:NE〉，不存在a₁、 a₂、 b₁、 b₂∈ R ，使得a₁∈a₂、 b₁∈b₂、 a₂ N:NW b₁、 a₂ NW:N:NEb₂同时成立，因此不是宽边界方向关系. 可见，若D=〈D₁,D₂,D₃,D₄〉为1个宽边界方向关系，则D₁,D₂,D₃,D₄彼此间存在约束. 对于任意一个宽边界方向关系，下面通过命题1~6给出其自身蕴涵的约束.

命题1 对于任一宽边界方向关系D=〈D₁,D₂,D₃,D₄〉，其中D_i∈{D₁,D₃}，方向片R_j∈{B,N,E,S,W}，若R_j∈D_i，则表达式(R_j∈D_i+1)∨(B∈ D_i+1)成立.

证明 对于满足关系D的任意2个宽边界区域a、b，分别设a₁、b₁为内区域，a₂、b₂为外区域. 当 D_i=D₁，方向片R_j=N且R_j∈D₁时，得证(N∈D₂)∨ (B∈D₂).

由定义6和定义8可知，b₁∈b₂∧a₁ D₁ b₁∧a₁ D₂ b₂，根据基本主方向关系的形式化定义^[3]，有I_x(b₁)≥ I_x(b₂)∧P_x(b₁)≤P_x(b₂)∧I_y(b₁)≥I_y(b₂)∧P_y(b₁)≤P_y(b₂). 其中：I为函数值的下界(infimum)；P为函数值的上界(supremum).

N∈D₁，因此存在区域a′ ₁∈ R ，a′ ₁∈a₁，使得a′ ₁ N b₁. 因此I_x(a′ ₁)≥I_x(b₁)∧P_x(a′ ₁)≤P_x(b₁)∧I_y(a′ ₁)≥ P_y(b₁). 进而有I_x(a′ ₁)≥I_x(b₂)∧P_x(a′ ₁)≤P_x(b₂). 若P_y(b₂)≤I_y(a′ ₁)，则a′ ₁ N b₂，即有N∈D₂；若I_y(a′ ₁)≤P_y(b₂)≤P_y(a′ ₁)，则a′ ₁ B:N b₂，即有N∈D₂∧B∈D₂；若P_y(b₂)≥P_y(a′ ₁)，则a′ ₁ B b₂，即有B∈D₂. 因此当D_i=D₁,N∈D₁时，(N∈D₂)∨(B∈D₂)成立.

同理可证，对于D_i∈{D₁,D₃}，方向片R_j∈{B,N,E,S,W}的其他情况，相应的表达式(R_j∈D_i+1)∨ (B∈D_i+1)均成立. 综上，命题1成立.

命题2 对于任一宽边界方向关系D=〈D₁,D₂,D₃,D₄〉，有D₁⊆D₃,D₂⊆D₄成立.

证明 对于满足关系D的任意2个宽边界区域a、b，分别设a₁、b₁为内区域，a₂、b₂为外区域. 由定义8可知，a₁ D₁ b₁∧a₂ D₃ b₁. 设D₁=R₁:…:R_k，由基本主方向关系的定义，存在k个区域a₁₁,a₁₂,…,a_1k，使得 a₁₁∈a₁,a₁₂∈a₁,…,a_1k∈a₁ a₁₁∪a₁₂∪…∪a_1k=a₁ 且这k个区域分别位于方向片R₁(b₁),…,R_k(b₁)中. a₁∈a₂，因此a₁₁∈a₂,a₁₂∈a₂,…,a_1k∈a₂，即a₂存在k个子区域分别位于方向片R₁(b₁),…,R_k(b₁)中，进而可知{R₁,…,R_k}⊆D₃，即有D₁⊆D₃.

同理可证，若D=〈D₁,D₂,D₃,D₄〉为1个宽边界方向关系，则有D₂⊆D₄. 综上，命题2成立.

定义9 R₁=R₁₁:…:R_1n与R₂=R₂₁:…:R_2m为2个基本主方向关系，R₁∩R₂={R₁₁,…,R_1n}∩{R₂₁,…,R_2m}.

命题3 对于任一宽边界方向关系D=〈D₁,D₂,D₃,D₄〉，其中D_i∈{D₁,D₃}，若{NE,E,SE}∩ M(E,r(D_i))=∅，则{NE,E,SE}∩D_i+1=∅.

证明 对于满足关系D的任意2个宽边界区域a、 b，分别设a₁、 b₁为内区域，a₂、 b₂为外区域. 当D_i=D₁，{NE,E,SE}∩M(E,r(D₁))=∅时，得证{NE,E,SE}∩D₂=∅.

由定义6和定义8可知，b₁∈b₂∧a₁ D₁ b₁∧a₁ D₂ b₂，因此有I_x(b₁)≥I_x(b₂)∧P_x(b₁)≤P_x(b₂)∧I_y(b₁)≥I_y(b₂)∧P_y(b₁)≤P_y(b₂). 若{NE,E,SE}∩M(E,r(D₁))=∅，则NE(b₁),E(b₁),SE(b₁)中不存在G(a₁)的子区域，进而由基本主方向关系的形式化定义，可知P_x(a₁)≤P_x(b₁). P_x(b₁)≤P_x(b₂)，因此P_x(a₁)≤P_x(b₂). 进而可知，NE(b₂),E(b₂),SE(b₂)中不存在G(a₁)的子区域，因此有NE$\notin $D₂∧E$\notin $D₂∧SE$\notin $D₂，即有{NE,E,SE}∩D₂=∅.

同理可证，当D_i=D₃，{NE,E,SE}∩M(E,r(D₃))=∅时，有{NE,E,SE}∩D₄=∅成立. 综上，命题3成立.

命题4 对于任一宽边界方向关系D=〈D₁,D₂,D₃,D₄〉，其中D_i∈{D₁,D₃}，若{NW,W,SW}∩ M(W,r(D_i))=∅，则{NW,W,SW}∩D_i+1=∅.

命题5 对于任一宽边界方向关系D=〈D₁,D₂,D₃,D₄〉，其中D_i∈{D₁,D₃}，若{NW,N,NE}∩ M(N,r(D_i))=∅，则{NW,N,NE}∩D_i+1=∅.

命题6 对于任一宽边界方向关系D=〈D₁,D₂,D₃,D₄〉，其中D_i∈{D₁,D₃}，若{SW,S,SE}∩ M(S,r(D_i))=∅，则{SW,S,SE}∩D_i+1=∅.

命题4~6成立，证明过程与命题3证明过程类似.

在定性空间关系建模中，可将定性空间关系推理问题转换为定性空间约束满足问题(QS-CSPs，qualitative spatial constraint satisfaction problems). 1个 QS-CSPs通常抽象为值域 D 上的1组变量 V 和其上的1个约束集合 C ，因此形式化记为〈 V ,D ,C 〉. 目前，定性空间关系建模研究多基于平面空间. Allen利用路径相容算法(path-consistency)提出了一种区间对象间拓扑关系约束的相容性检测方法. 下面对Allen的方法进行扩展，研究不确定区域对象间方向关系约束的相容性检测问题.

定义10 X_u D X_v为1个宽边界方向关系约束，其中D=〈D₁,D₂,D₃,D₄〉为宽边界方向关系，X_u、 X_v为宽边界区域变量，D_i∈ U ，1≤i≤4.

为方便说明，简记宽边界方向关系(BBDR，broad boundary direction relation)和基本主方向关系(BCDR，basic cardinal direction relation).

定义11 宽边界区域间方向关系的约束满足问题记为〈 V,D,C 〉_BBDR，它是一类特殊的空间约束满足问题，其中 V 为一个有限变量集； D为V 中变量对应的值域，是2维平面空间中宽边界区域的无限集合； C 为宽边界方向关系约束集合. 若 C 是相容的，当且仅当存在对 V 的1组实例化X₁=a₁,…,X_n=a_n，其中a_i为宽边界区域，a_i以a_i(2i-1)为内区域，a_i(2i)为外区域，a_i(2i-1),a_i(2i)∈ R ，1≤i≤n，使得 C 是可满足的，称a₁,…,a_n是 C 的1个解. C 的所有解的集合记为s( C ).

类似地，对于确定区域间基本主方向关系的约束满足问题，笔者形式化记为〈 V ,D ,C 〉_BCDR.

约束转换规则1 对于宽边界方向关系约束满足问题中的任意一个变量X_i，1≤i≤n，对应2个确定区域变量x_2i-1,x_2i，使得x_2i-1 B x_2i成立.

对于任意一个宽边界区域，其均由外、内2个确定的区域构成，若以外区域为参照区域，内区域为主区域，则内区域与外区域间满足基本主方向关系B. 如图 2(a)所示，宽边界区域a对应2个确定区域a₁,a₂，其中a₂为a的外区域，a₁为a的内区域，并有a₁ B a₂. 其对应的约束转换图如图 4所示.

Figure 4

		Figure Option ViewDownloadNew Window
		图4 约束转换规则1实例图

约束转换规则2 对于任意一个宽边界方向关系约束X_i 〈D₁,D₂,D₃,D₄〉 X_j，宽边界区域变量X_i对应2个确定区域变量x_2i-1,x_2i，X_j对应2个确定区域变量x_2j-1,x_2j，使得x_2i-1 D₁ x_2j-1,x_2i-1 D₂ x_2j,x_2i D₃ x_2j-1,x_2i D₄ x_2j成立.

例3 宽边界方向关系约束X_i 〈NW,NW:N,NW:N,NW:N〉 X_j，执行约束转换规则2后得到1组确定区域间方向关系约束x_2i-1 NW x_2j-1,x_2i-1 NW:N x_2j,x_2i NW:N x_2j-1,x_2i NW:N x_2j.

转换后对应的约束转换图如图 5所示.

Figure 5

		Figure Option ViewDownloadNew Window
		图5 约束转换规则2实例图

由约束转换规则1和2，可将1个〈 V,D,C 〉_BBDR转换为1个〈 V,D,C 〉_BCDR. 下面通过例4说明具体转换过程. 在此基础上，可通过扩展现有确定区域间方向关系的推理方法对不确定区域间方向关系进行推理.

例4 设宽边界方向关系约束集合

对宽边界方向关系约束X₁ 〈N,N,N:NE,N〉 X₂中的2个宽边界区域变量X₁、 X₂分别执行约束转换规则1，得到

对宽边界方向关系约束X₂ 〈NW,NW,NW,N:NW〉 X₃中的2个宽边界区域变量X₁、 X₂分别执行约束转换规则1，得到

对宽边界方向关系约束X₁ 〈N,N,N:NE,N〉 X₂执行约束转换规则2，得到

对宽边界方向关系约束X₂ 〈NW,NW,NW,N:NW〉 X₃执行约束转换规则2，得到

对约束集合 C 进行转换后得到新的确定区域间方向关系约束集合 C ′和相应的变量集合 V ′.

Figure 6

		Figure Option ViewDownloadNew Window
		图6 基于约束转换规则1和2得到的约束网络

对于一个宽边界方向关系约束满足问题〈 V,D,C 〉_BBDR，判定其相容性的步骤如下.

步骤1 基于约束转换规则1，将宽边界区域变量集合 V 转换为确定区域变量集合 V ′，并将推导出的基本主方向关系约束放入 C ′中.

步骤2 基于约束转换规则2，将宽边界方向关系约束集合C转换为基本主方向关系约束集合C′.

步骤3 基于步骤1和步骤2，将〈 V,D,C 〉_BBDR转换为〈 V′,D,C ′〉_BCDR. 作为路径相容算法的关键技术，基本主方向关系间的相容性复合运算(记为“$\circ $”)已在很多文献中详细讨论[3,9]. 借助于这些运算性质，笔者给出针对〈 V,D,C 〉_BCDR的路径相容性算法，从而间接实现对〈 V,D,C 〉_BBDR相容性的判定.

算法具体描述如下.

宽边界方向关系相容性算法(BBDR-CON，consistency algorithm for BBDRs)

输入：〈 V,D,C 〉_BBDR.

输出：s( C )非空输出“consistent”，否则输出“unconsistent”.

/*约束转换，V′,C ′分别表示执行约束转换后得到的确定区域变量集合和确定区域间方向关系约束集合*/

For all X_i in V o

V ′←{x_2i-1,x_2i}

C ′←{x_2i-1 B x_2i}

EndFor

For all X_i D_t X_j in C Do

C ′←{x_2i-1 D_t1 x_2j-1,x_2i-1 D_t2 x_2j,x_2i D_t3 x_2j-1,x_2i D_t4 x_2j}

EndFor

/*标记约束，u标记区域x_u，C_uv标记x_u,x_v间的约束，1≤u,v≤2n*/

Q ←{〈u,v〉|u D v∈ C ′}

/*约束传播，T 为临时约束集合*/

While Q ≠∅ Do

Select and delete a 〈u,v〉 from Q

For all k (k≠u,k≠v,1≤k≤2n) Do

T ←C_uv∩(C_uk$\circ $ C _kv)

 If T =∅ Then return “unconsistent”

 Else

   If T ≠C_uv

   C_uv← T

   Add 〈u,v〉 to Q

  EndIf

   T ←∅

 EndIf

EndFor

EndWhile

return“consistent”

BBDR-CON算法是正确的. 第一，Skiadopoulos等^[3]证明了算法中复合运算的正确性；基于宽边界模型和主方向关系的形式化定义可知，算法中的约束转换规则是正确的. 第二，While循环是算法的主体部分，当约束集合 Q 不为空时，选择C_uv，然后选择与u,v能构成三角形的变量k，对边〈u,k〉,〈k,v〉标注的关系进行复合运算，并将C_uv与C_uk$\circ $ C_kv相交的结果存入临时约束集合 T 中. 若 T 为空，说明关系集合C_uv中没有属于关系集合C_uk$\circ $ C_kv的元素，这与路径相容的定义相冲突，则返回“unconsistent”；若 T 不为空，则用新约束集合 T 替换原有关系C_uv. 此时约束网络中的关系已被改动，重新将边〈u,v〉加入 Q 中，继续循环，直到当所有约束对应的边均被检测(即 Q 为空)，若此时再无可能产生冲突的约束，则可判定约束集合是相容的.

BBDR-CON算法是对Allen的路径相容算法的扩展. 对于含有n个变量的宽边界方向关系约束满足问题，可转换为包含2n个变量的确定区域间方向关系的约束满足问题，对应于约束网络中的2n个结点，最多包含2n(2n-1)(2n-2)/6个三角形. 对这些三角形进行路径相容性检测所需的时间为O(n³)，所以BBDR-CON算法的时间复杂度为O(n³).

笔者采用定性方法，基于宽边界模型和基本主方向关系模型，研究了不确定区域间方向关系的表示和推理方法. 提出了宽边界区域间方向关系表示方法，并在此基础上提出一种基于宽边界方向关系约束的复杂度为O(n³)的相容性算法BBDR-CON. 与以往确定区域间方向关系模型相比较，笔者的工作能形式化表示和推理不确定区域间的空间关系，不仅进一步深化了空间关系建模理论研究，同时更有利于解决复杂实际问题.

理论研究方面，对于笔者提出的宽边界方向关系，其运算性质(逆运算、复合运算等)仍有待于深入研究. 现实世界中的空间对象更加复杂，导致不确定性的因素很多，不仅局限于带有不确定边界的区域对象，因此更接近人们空间认知的不确定空间对象的新表示方法是未来该领域中的一个研究热点. 应用研究方面，在城市交通、地理信息系统(GIS，geographic information system)、机器人导航和计算机辅助设计中，基于线性物体的方向关系推理也具有极高的应用价值，因此将笔者提出的方法应用于线性物体推理，是未来值得开展的一项应用研究工作.