-
空间推理是地球空间信息、人工智能、自然语言处理等相关领域的热点研究方向[1]。主方向关系作为空间推理的重要组成部分，方向关系模型的有效表达与方向关系推理的形式化描述是实现空间主方向关系认知的关键[2]。研究表明，基于坐标的GIS (coordinate-based GIS，CB-GIS)[3]并不符合大众对空间方向关系的认知，而基于地标的定性参照系(landmark-based qualitative reference system，LBQRS)[4]在空间目标的方向关系描述上更贴切人们的日常生活与实际需求。对空间方向关系的形式化描述与推理，学术界已有许多相关研究。在模型表达上，有最小外接矩形(minimum bounding rectangle，MBR)模型[5]、二维字符模型[6]、Voronoi图模型[7]、直方图模型[8]、改进型锥形模型[9]等。经文献[10]分析，矩形模型虽能简化空间方向计算，但未顾及图形的形状特征，导致矩形模型对方向关系表达的准确性不足，锥形模型则受制于图形的形状大小。为了更准确地表达方向关系，Goyal[11]提出了方向关系矩阵模型，并且以线要素、面要素、目标对象所占参照物的九方向区域面积比例，改进了方向关系矩阵模型, 验证了方向关系矩阵模型对方向关系表达完备性、严密性、唯一性和通用性。在图形形状上，方向关系的研究对象主要为凸边形，而对凹边形的研究相对不足[12]; 在图形方向关系表达尺度上，未顾及方向关系中本身方向关系的细化表达。在方向关系的合成运算上，传统合成推理使用的方向关系组合表推理方法着重于1个参照的合成计算[13-14]，往往不适用于2个参照系的方向关系合成。在对已有基于1个参照系、2个参照系的方向关系推理研究[15-16]中发现，方向关系合成的逻辑谓词因参照系的不同而不同，缺乏统一形式化的逻辑推演。
故本文基于方向关系矩阵模型，以凹边形地标为研究案例，提出了凹边形地标参照的主方向关系推理方法。从方向关系表达的整体性与局部性角度，利用三等分仿射变换(trisection affine transformation，TAT)实现凹边形地标的外部性参照对象表达；通过凹边形顶点的凹凸性判断，利用连接凹拐点与凸拐点的有向边自适应分割(adaptive concave segmentation，ACS)实现凹边形地标的内部性参照对象表达。在主方向关系推理上，基于向量三角形法则与方向关系谓词，以方向关系的逻辑和合成代数运算(logicalintegration composing，LIC)、逻辑差合成代数运算(logicaldifference composing，LDC)分别推理2个地标参照、1个地标参照下目标对象与参照对象的主方向关系。
HTML
-
自Allen提出区间代数(interval algebra，IA)概念以来，IA对方向关系的表达产生了重要作用，如图 1所示的正向、反向方向关系示例。虽然方向关系的IA表达与推理研究取得一定进展，但仍有一定局限。如图 2所示，根据Balbianip[17]建立的IA二维拓展矩形代数(rectangle algebra，RA)，如表 1所示，可知A与B的方向关系为本身关系。受IA方向关系表达的图形大小影响，当pB2 → 0+，如图 2虚线矩形表示，方向关系的判定仍为本身方向关系。实践表明，此时相对A，B与A的方向关系为南向关系更合理，而此时的本身方向关系不足以准确地表达B与A的方向关系。
Figure 1. Directional Relations in IA
Figure 2. Limitation for Self-direction in IA
dirt(X，Y) {p，m} {o，fi} {di} {eq，s，d，f} {si，oi} {pi，mi} {p，m} SW SW：S SW：S：E S S：SE SE {o，fi} W：SW W：I：SW：S W：I：E：SW：S：SE I：S I：E：S：SE E：SE {di} NW：W：SW NW：N：W：I：SW：S All N：I：W N：NE：I：E：S：SE NE：E：SE {eq，s，d，f} W W：I W：I：E I I：E E {si，oi} NW：W NW：N：W：I NW：N：NE：W：I：E N：I N：NE：I：E NE：E {pi，mi} NW NW：N NW：N：NE N N：NE NE Table 1. Directional Relations Mapping in RA
Freeman[18]指出, 由于空间模糊关系的存在，一般的数学关系明显不适用于空间关系模型，当目标对象处于凹边形凹槽中时，根据方向关系矩阵模型，目标对象与参照对象之间的方向关系为模糊性本身方向关系。为实现本身方向关系的细化表达，本文以图 3所示的对象三等分仿射变换，将本身方向关系转化为空间8方向关系。
Figure 3. Trisection Affine Transformation
算法1 三等分仿射变换
输入：面状要素Ply。
输出：Ply的三等分仿射变换Ply′。
1) 空间面状要素Ply，通过最小外接矩形算子MBR(·)构建Ply的最小外接矩形区域MO，MO←MBR(Ply)，并获取MO四个边界角点坐标值MOx max、MOx min、MOy max、MOy min、图形Ply与MO交点zj (j = 1，2，…，n)。
2) 笛卡尔坐标系下，结合三等分仿射变换矩阵$\mathit{\boldsymbol{tpc}}{\rm{ = }}\left[\begin{array}{l} 2\;\;\;\;\;\;1\\ 1{\rm{/}}3\;\;2{\rm{/}}3 \end{array} \right]$，将MO的横坐标、纵坐标区间三等分仿射变换于相应的空间坐标区间，形成MO′，即
3) 经MO′←MO的比例约束，实现z′j←zj，Ply′←Ply。
4) 算法结束。
-
凹边形的顶点凹凸性、方向判别是计算机图形学的基本问题，在模式识别、数字图像处理、地理信息等众多领域已具广泛应用[19]。参照凹边形局部位置的不同，目标对象与其主方向关系亦不同。如图 4(a)所示，由表 1可知，相对与A，目标T与A的方向关系为E，而T与B的方向关系则为N。为了实现本身方向关系的内部性参照对象表达，利用算法2实现连接凹凸拐点的有向边延长线自适应分割凹边形，如图 4中虚线分割结果所示。
Figure 4. Adaptive Tessellations of Concaves
算法2 凹边形自适应分割
输入：凹边形Conc。
输出：局部性凸边形LConv。
1) 若凹边形Conc，定义Conc顶点排列方向的逆时针方向d+为多边形的正方向。
2) 由右手定则，确定Conc的法向量$\overrightarrow n $，记顶点数、边数分别为pcont、econt。
3) 对连接同一顶点的两个向量边做向量叉积运算$\overrightarrow m \leftarrow {\overrightarrow e _1} \times {\overrightarrow e _2}$，如果$\overrightarrow m \cdot \overrightarrow n $＜0，则证明该顶点为凹拐点，该点属性赋值vertex.cc_attrib ←0；否则，该点为凸拐点，赋值vertex.cc_attrib ←1，pcont ←pcont-1；until pcont ==0。
4) 有向边$\overrightarrow e $的两端点pi、pj异或运算pi⊕pj，如果pi. cc_attrib⊕pj.cc_attrib ==1，则以此边为基准实现图形分割，LConv←clip($\overrightarrow e $，Conc)，econt ←(econt-1)；否则continue，until econt==0。
5) 算法结束。
1.1. 外部性参照对象
1.2. 内部性参照对象
-
在地球空间信息学领域，主方向关系推理是构建GIS空间方向关系认知的重要方式。在MBR矩形代数产生的九方向：东(E)、南(S)、西(W)、北(N)、东北(NE)、东南(SE)、西北(NW)、西南(SW)和本身方向(I)中，因本文对I细化表达，所以构成本文主方向关系谓词集合为S_Dir={E，S，W，N，NE，SE，NW，SW}，存在的方向关系为：
式中，~为反方向关系；∞为方向关系合成运算；d∈S_Dir。
实践表明，不管是2个参照对象的方向关系合成计算，还是1个参照对象的方向关系合成计算，NE∞NW方向的结果均应为N。尽管个体间存在文化和语言差异，但并不影响对方向关系的理解[20]。例如，汉语中的西北向与英语中的Northwest因语言的不同而描述不同，汉语先东西、后南北，而英语则是先南北、再东西，在方向关系语义表达上实则为同一方向，为NW = N∞W = W∞N = WN。根据式(1)、式(2)、式(3)，方向NE∞NW合成运算过程：
式中，E∞W = 0，对任一方向d，有d∞0 = d。结合式(1)、式(2)与式(3)的形式化描述，S_Dir条件下方向关系的定性表达完备。
-
根据参照对象的相对性，方向关系推理主要有2个参照对象、1个参照对象两种形式。如图 5(a)所示的2个参照对象，基于向量三角形法则，由参照对象T1和目标对象O1、以及目标对象O1与参照对象T2的方向关系，可推知参照对象T2和参照对象T1的方向关系。图 5(b)所示的1个参照对象，由参照对象T3和目标对象O2、参照对象T3和目标对象O3的方向关系，可推知目标对象O2和目标对象O3的方向关系。据此，在统一逻辑谓词与方向谓词条件下，研究提出了基于LIC和LDC的方向关系推理。
Figure 5. Triangle Rules in Vector
推论1 基于LIC的方向关系推理
式中，dir2(·)为LIC表达式，且i，j∈N*; ⊕为LIC运算符；∪为并集运算；
推论2 基于LDC的方向关系推理
式中，dir1(·)为LDC表达式，且i，j∈N*；
2个参照对象下，以图 6为例，A参照下，根据表 1，得A与B的RA方向关系dirt(A，B)= D1={NE，E}；B参照下，得B与C的RA方向关系dirt(B，C)=D2={N}，则A与C的方向关系dir2(A，C)可由式(5), 得：dir2(A，C)=N∞NE=N∞N∞E=N∞E=NE，N∞E=NE，即D1∞D2={NE}。
Figure 6. Reasoning for Cardinal Directions
1个参照对象下，当参照对象A与B之间的方向关系为R1，A与C的方向关系为R2时，相对于B，B与C之间的方向关系dir1(B，C)可由式(6)得出。以图 6参照对象A为例，据表 1，有dirt(A，B)=R1 = {NE，E}，dirt(A，C)=R2 ={N}，那么dir1(B，C)=(N-NE∩N)∞~(NE-NE∩N) ∪ (N-E∩N)∞~(N-E∩N)，即dir1(B，C)={W，NW}=W：NW，表明C在B的西方和西北方向的主方向线上，如图 6带箭头虚线R3所示；同理可得，dir1(C，B) =(NE-NE∩N)∞~(N-NE∩N) ∪ (E-E∩N)∞~(N-E∩N)={E，SE}，即dir1(C，B)={E，SE}，表明B在C的东方和东南方的主方向线上，且dir1(B，C)∞dir1(C，B)=0，表明两方向关系为反方向关系，验证了基于LDC的方向关系推理有效性；当R1与R2同方向时，如R1 = R2={S}，那么1个参照对象下LDC的方向关系推理结果或为S，或为N，即主方向位于南北向延长线上。
2.1. 主方向关系谓词
2.2. 主方向关系推理过程
-
本文以矩形代数表达的八方向关系，在WGS84坐标系下以比例尺1：10 000云南省昆明市五华区部分建成区为研究案例。由图 7所示建筑多为不规则的凹边形结构，首先，利用ArcGIS 10.0简化面制图工具实现图形简化，在方向关系推理验证上，对比方向关系的矩形代数，如表 1所示，佐证本文方法对凹边形地标参照的主方向关系表达与推理的可行性。
Figure 7. Landmarks and Urban Buildings
-
以图 8规则化典型图形为研究对象，定义逆时针方向$\overrightarrow p $为图形的正方向。由图 8(a)中图形D的MBR包含图形E的MBR，从表 1可知，D与E的方向关系为本身方向关系I，由三等分仿射变换，凹边形D映射为图 8(b)中的D′。结合表 1方向关系映射，得dirt(E，F)={si}×{pi}=N：NE，实现凹边形的外部性主方向参照对象表达。
Figure 8. Affine Transformation and Segmentation for Concaves
法向量$\overrightarrow p $、凹边形的自适应分割方法如图 8(c)所示，点1和点2构成的向量边$\overrightarrow a $、点2和点3构成的向量边$\overrightarrow b $计算得，$\left( {\overrightarrow a \times \overrightarrow b } \right) \cdot \overrightarrow p < 0$，由此判定点2为凹拐点；同理，判定点1、点3为凸拐点。根据凹拐点转凸拐点或凸拐点转凹拐点的向量边反向延长线分割凹边形，如图 8(c)中的点2至点3、点5至点6、点1至点2、点4至点5，该转点有向边的延长线将图形A分割为A1、A2、A3和A4，如图 8(c)中虚线所示。同理，凹边形B分割为B1、B2、B3，凹边形C分割为C1、C2、C3，以及图 8(d)中所示的凹边形F分割为F1、F2、F3、F4，凹边形D分割为D1、D2、D3，凹边形E分割为E1、E2、E3，结合表 1方向关系映射，得dirt(D1，F) = {N，NE}，实现凹边形的内部性主方向参照对象表达。
-
就2个参照对象而言，以图 8(c)为例，结合表 1，相对于参照物A，B与A之间的方向关系为dirt(A，B)=I：S⇒{S}，方向关系I未列入八方向关系，舍去；相对于B，C与B方向关系为dirt(B，C)=NE：E，根据式(5)，得A与C的外部性主方向关系为dir2 (A，C)=dirt(A，B) ⊕dirt(B，C)=S∞NE：E=(S∞NE) ∪ (S∞E=E：SE；由表 1的矩形关系{pi}×{fi}，可知dirt(A，C)=E：SE，dir2(A，C)=dirt(A，C)。对特殊的本身方向关系I。以图 8(a)、8(b)为例，D与E为本身方向关系，根据凹边形D的三等分仿射变换D′，由表 1，得dirt(D′，E)={o} × {pi} = NW：N；dirt(E，F)={si}×{pi}=N：NE，dirt(D′，F)={N}；根据式(5)，得dir2(D′，F)={NW，N} ⊕{N，NE}=N：NE，此与表 1得出方向关系不相等的主要原因是图形大小对方向关系表达具有相对不变性。例如，当凹边形F相对于E的主方向关系不变时，凹边形F可向东方延伸且超过凹边形D的x轴投影极大值，dir2(D′，F)的方向关系推理结果N：NE包含了N，证明了基于LIC的方向关系推理可行性。
-
就1个参照对象而言，如图 8(c)，dirt(A，B)=B：S⇒{S}，dirt(A，C)=E：SE，由式(6)推出B与C的外部性主方向关系dir1(B，C)=dirt(A，C)
3.1. 内部性与外部性参照对象表达
3.2. 基于2个参照对象的方向关系推理
3.3. 基于1个参照对象的方向关系推理
-
鉴于方向关系矩阵对凹边形本身方向关系表达的模糊性，本文从方向关系的外部性参照和内部性参照出发，利用三等分仿射变换方法将对象间的模糊性本身方向关系细化为外部性参照的八方向关系；根据凹边形顶点的凹凸性，采用凹凸点的反向延长线分割凹边形方法实现了方向关系的内部性参照对象表达；在方向关系推理上，方向关系的逻辑和、逻辑差合成代数方法分别实现了1个参照对象、2个参照对象的主方向关系推理。经矩形代数空间方向关系验证，验证了1个参照对象、2个参照对象下基于LIC、LDC的方向关系推理有效性。针对研究中存在的1个参照对象中两个相同方向关系推理的不确定性，如何有效地对方向关系进行量化表达，实现方向关系推理的刚性判定，是主方向关系推理后续工作中需要进一步研究和解决的问题。
DownLoad:
