留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

凹边形地标参照的主方向关系推理方法

康顺 李佳田 瞿珊珊

康顺, 李佳田, 瞿珊珊. 凹边形地标参照的主方向关系推理方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021
引用本文: 康顺, 李佳田, 瞿珊珊. 凹边形地标参照的主方向关系推理方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021
KANG Shun, LI Jiatian, QU Shanshan. A Qualitative Reasoning Method for Cardinal Directional Relations Under Concave Landmark Referencing[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021
Citation: KANG Shun, LI Jiatian, QU Shanshan. A Qualitative Reasoning Method for Cardinal Directional Relations Under Concave Landmark Referencing[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021

凹边形地标参照的主方向关系推理方法

doi: 10.13203/j.whugis20160021
基金项目: 

国家自然科学基金 41561082

国家自然科学基金 41161061

详细信息
    作者简介:

    康顺, 博士生, 主要研究方向为空间关系定性表达与推理。kangshun_cumt@126.com

  • 中图分类号: P208

A Qualitative Reasoning Method for Cardinal Directional Relations Under Concave Landmark Referencing

Funds: 

The National Natural Science Foundation of China 41561082

The National Natural Science Foundation of China 41161061

More Information
    Author Bio:

    KANG Shun, PhD candidate, specializes in representing and reasoning with spatial relations. E-mail: kangshun_cumt@126.com

图(8) / 表(1)
计量
  • 文章访问数:  926
  • HTML全文浏览量:  47
  • PDF下载量:  416
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-12-25
  • 刊出日期:  2018-01-05

凹边形地标参照的主方向关系推理方法

doi: 10.13203/j.whugis20160021
    基金项目:

    国家自然科学基金 41561082

    国家自然科学基金 41161061

    作者简介:

    康顺, 博士生, 主要研究方向为空间关系定性表达与推理。kangshun_cumt@126.com

  • 中图分类号: P208

摘要: 空间推理是地球空间信息、人工智能、自然语言处理等相关领域的热点研究内容。主方向关系的表达与推理是空间推理的重要组成部分。针对空间方向关系矩阵对凹边形对象方向关系表达、推理的不足,研究依据目标对象与凹边形地标方向关系表达的不确定性,提出了凹边形地标参照的外部性主方向关系与内部性主方向关系推理方法。利用凹边形三等分仿射变换矩阵、自适应分割算法实现凹边形地标外部性、内部性参照对象表达;基于向量三角形法则与方向关系谓词,以方向关系的逻辑和、逻辑差合成代数运算推理2个地标、1个地标参照下目标对象与参照对象之间的主方向关系。通过实验与算例验证,证明凹边形地标参照下目标对象与参照对象的主方向关系推理可行性。

English Abstract

康顺, 李佳田, 瞿珊珊. 凹边形地标参照的主方向关系推理方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021
引用本文: 康顺, 李佳田, 瞿珊珊. 凹边形地标参照的主方向关系推理方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021
KANG Shun, LI Jiatian, QU Shanshan. A Qualitative Reasoning Method for Cardinal Directional Relations Under Concave Landmark Referencing[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021
Citation: KANG Shun, LI Jiatian, QU Shanshan. A Qualitative Reasoning Method for Cardinal Directional Relations Under Concave Landmark Referencing[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 24-30. doi: 10.13203/j.whugis20160021
  • 空间推理是地球空间信息、人工智能、自然语言处理等相关领域的热点研究方向[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个地标参照下目标对象与参照对象的主方向关系。

    • 自Allen提出区间代数(interval algebra,IA)概念以来,IA对方向关系的表达产生了重要作用,如图 1所示的正向、反向方向关系示例。虽然方向关系的IA表达与推理研究取得一定进展,但仍有一定局限。如图 2所示,根据Balbianip[17]建立的IA二维拓展矩形代数(rectangle algebra,RA),如表 1所示,可知AB的方向关系为本身关系。受IA方向关系表达的图形大小影响,当pB2 → 0+,如图 2虚线矩形表示,方向关系的判定仍为本身方向关系。实践表明,此时相对ABA的方向关系为南向关系更合理,而此时的本身方向关系不足以准确地表达BA的方向关系。

      图  1  IA方向关系表达

      Figure 1.  Directional Relations in IA

      图  2  区间代数本身方向关系表达的局限性

      Figure 2.  Limitation for Self-direction in IA

      表 1  矩形代数方向关系映射

      Table 1.  Directional Relations Mapping in RA

      dirt(XY) {pm} {ofi} {di} {eqsdf} {sioi} {pimi}
      {pm} SW SWS SWSE S SSE SE
      {ofi} WSW WISWS WIESWSSE IS IESSE ESE
      {di} NWWSW NWNWISWS All NIW NNEIESSE NEESE
      {eqsdf} W WI WIE I IE E
      {sioi} NWW NWNWI NWNNEWIE NI NNEIE NEE
      {pimi} NW NWN NWNNE N NNE NE

      Freeman[18]指出, 由于空间模糊关系的存在,一般的数学关系明显不适用于空间关系模型,当目标对象处于凹边形凹槽中时,根据方向关系矩阵模型,目标对象与参照对象之间的方向关系为模糊性本身方向关系。为实现本身方向关系的细化表达,本文以图 3所示的对象三等分仿射变换,将本身方向关系转化为空间8方向关系。

      图  3  三等分仿射变换

      Figure 3.  Trisection Affine Transformation

      算法1  三等分仿射变换

            输入:面状要素Ply

            输出:Ply的三等分仿射变换Ply′。

      1) 空间面状要素Ply,通过最小外接矩形算子MBR(·)构建Ply的最小外接矩形区域MOMO←MBR(Ply),并获取MO四个边界角点坐标值MOx maxMOx minMOy maxMOy min、图形PlyMO交点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′,即

      $$ \left[\begin{array}{l} M{{O'}_{x\;\max }}\;\;M{{O'}_{x\;\min }}\\ M{{O'}_{y\;\max }}\;\;M{{O'}_{y\;\min }} \end{array} \right]\left[\begin{array}{l} M{O_{x\;\max }}\;\;M{O_{x\;\min }}\\ M{O_{y\;\max }}\;\;M{O_{y\;\min }} \end{array} \right] \cdot \mathit{\boldsymbol{tpc}}。 $$

      3) 经MO′←MO的比例约束,实现zjzjPly′←Ply

      4) 算法结束。

    • 凹边形的顶点凹凸性、方向判别是计算机图形学的基本问题,在模式识别、数字图像处理、地理信息等众多领域已具广泛应用[19]。参照凹边形局部位置的不同,目标对象与其主方向关系亦不同。如图 4(a)所示,由表 1可知,相对与A,目标TA的方向关系为E,而TB的方向关系则为N。为了实现本身方向关系的内部性参照对象表达,利用算法2实现连接凹凸拐点的有向边延长线自适应分割凹边形,如图 4中虚线分割结果所示。

      图  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 $的两端点pipj异或运算pipj,如果pi. cc_attrib⊕pj.cc_attrib ==1,则以此边为基准实现图形分割,LConv←clip($\overrightarrow e $,Conc),econt ←(econt-1);否则continue,until econt==0。

      5) 算法结束。

    • 在地球空间信息学领域,主方向关系推理是构建GIS空间方向关系认知的重要方式。在MBR矩形代数产生的九方向:东(E)、南(S)、西(W)、北(N)、东北(NE)、东南(SE)、西北(NW)、西南(SW)和本身方向(I)中,因本文对I细化表达,所以构成本文主方向关系谓词集合为S_Dir={ESWNNESENWSW},存在的方向关系为:

      $$ \begin{array}{l} \;\; \sim E = W, \sim N = S, \\ \sim NE = SW, \sim NW = SE \end{array} $$ (1)
      $$ E\infty E = E, NE\infty NE = NE$$ (2)
      $$ d\infty \left( {d\infty d} \right) = \left( {d\infty d} \right)\infty d $$ (3)

      式中,~为反方向关系;∞为方向关系合成运算;d∈S_Dir。

      实践表明,不管是2个参照对象的方向关系合成计算,还是1个参照对象的方向关系合成计算,NENW方向的结果均应为N。尽管个体间存在文化和语言差异,但并不影响对方向关系的理解[20]。例如,汉语中的西北向与英语中的Northwest因语言的不同而描述不同,汉语先东西、后南北,而英语则是先南北、再东西,在方向关系语义表达上实则为同一方向,为NW = NW = WN = WN。根据式(1)、式(2)、式(3),方向NENW合成运算过程:

      $$ \begin{array}{l} NE\infty NW = \left( {N\infty E} \right)\infty \left( {N\infty W} \right) = \left( {N\infty } \right.\\ \left. E \right)\infty \left( {W\infty N} \right) = N\infty \left( {E\infty W} \right)\infty N = N \end{array} $$ (4)

      式中,EW = 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的方向关系推理。

      图  5  向量三角形法则

      Figure 5.  Triangle Rules in Vector  

      推论1  基于LIC的方向关系推理

      $$ {\rm{di}}{{\rm{r}}^{\rm{2}}}\left( \cdot \right) = {D_1} \oplus {D_2} = \mathop \cup \limits_{i = j = 1}^n \left( {D_1^i\infty D_2^j} \right) $$ (5)

      式中,dir2(·)为LIC表达式,且ijN*; ⊕为LIC运算符;∪为并集运算;

      推论2  基于LDC的方向关系推理

      (6)

      式中,dir1(·)为LDC表达式,且ijN*为LDC运算符;-为差集运算;∩为交集运算;|为集合或运算;

      2个参照对象下,以图 6为例,A参照下,根据表 1,得ABRA方向关系dirt(AB)= D1={NEE};B参照下,得BCRA方向关系dirt(BC)=D2={N},则AC的方向关系dir2(AC)可由式(5), 得:dir2(AC)=NNE=NNE=NE=NENE=NE,即D1D2={NE}。

      图  6  主方向关系推理

      Figure 6.  Reasoning for Cardinal Directions

      1个参照对象下,当参照对象AB之间的方向关系为R1AC的方向关系为R2时,相对于BBC之间的方向关系dir1(BC)可由式(6)得出。以图 6参照对象A为例,据表 1,有dirt(AB)=R1 = {NEE},dirt(AC)=R2 ={N},那么dir1(BC)=(N-NEN)∞~(NE-NEN) ∪ (N-EN)∞~(N-EN),即dir1(BC)={WNW}=WNW,表明CB的西方和西北方向的主方向线上,如图 6带箭头虚线R3所示;同理可得,dir1(CB) =(NE-NEN)∞~(N-NEN) ∪ (E-EN)∞~(N-EN)={ESE},即dir1(CB)={ESE},表明BC的东方和东南方的主方向线上,且dir1(BC)∞dir1(CB)=0,表明两方向关系为反方向关系,验证了基于LDC的方向关系推理有效性;当R1R2同方向时,如R1 = R2={S},那么1个参照对象下LDC的方向关系推理结果或为S,或为N,即主方向位于南北向延长线上。

    • 本文以矩形代数表达的八方向关系,在WGS84坐标系下以比例尺1:10 000云南省昆明市五华区部分建成区为研究案例。由图 7所示建筑多为不规则的凹边形结构,首先,利用ArcGIS 10.0简化面制图工具实现图形简化,在方向关系推理验证上,对比方向关系的矩形代数,如表 1所示,佐证本文方法对凹边形地标参照的主方向关系表达与推理的可行性。

      图  7  地标与城区建筑

      Figure 7.  Landmarks and Urban Buildings

    • 图 8规则化典型图形为研究对象,定义逆时针方向$\overrightarrow p $为图形的正方向。由图 8(a)中图形D的MBR包含图形E的MBR,从表 1可知,DE的方向关系为本身方向关系I,由三等分仿射变换,凹边形D映射为图 8(b)中的D′。结合表 1方向关系映射,得dirt(EF)={si}×{pi}=NNE,实现凹边形的外部性主方向参照对象表达。

      图  8  凹边形仿射变换与分割

      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分割为A1A2A3A4,如图 8(c)中虚线所示。同理,凹边形B分割为B1B2B3,凹边形C分割为C1C2C3,以及图 8(d)中所示的凹边形F分割为F1F2F3F4,凹边形D分割为D1D2D3,凹边形E分割为E1E2E3,结合表 1方向关系映射,得dirt(D1F) = {NNE},实现凹边形的内部性主方向参照对象表达。

    • 就2个参照对象而言,以图 8(c)为例,结合表 1,相对于参照物ABA之间的方向关系为dirt(AB)=IS⇒{S},方向关系I未列入八方向关系,舍去;相对于BCB方向关系为dirt(BC)=NEE,根据式(5),得AC的外部性主方向关系为dir2 (AC)=dirt(AB) ⊕dirt(BC)=SNEE=(SNE) ∪ (SE=ESE;由表 1的矩形关系{pi}×{fi},可知dirt(AC)=ESE,dir2(AC)=dirt(AC)。对特殊的本身方向关系I。以图 8(a)8(b)为例,DE为本身方向关系,根据凹边形D的三等分仿射变换D′,由表 1,得dirt(D′,E)={o} × {pi} = NWN;dirt(EF)={si}×{pi}=NNE,dirt(D′,F)={N};根据式(5),得dir2(D′,F)={NWN} ⊕{NNE}=NNE,此与表 1得出方向关系不相等的主要原因是图形大小对方向关系表达具有相对不变性。例如,当凹边形F相对于E的主方向关系不变时,凹边形F可向东方延伸且超过凹边形Dx轴投影极大值,dir2(D′,F)的方向关系推理结果NNE包含了N,证明了基于LIC的方向关系推理可行性。

    • 就1个参照对象而言,如图 8(c),dirt(AB)=BS⇒{S},dirt(AC)=ESE,由式(6)推出BC的外部性主方向关系dir1(BC)=dirt(AC) dirt(AB)={ESE} {S}=NEE,即CB的西和西南方向,由表 1得dirt(BC)=NEE=dir1(BC),证明dir1(BC)的方向关系推理与表 1判定结果一致。从图形局部与整体关系推理上, 以图 8(d)凹边形分割的D1为例,其与凹边形E的方向关系dirt(D1E)={NNEBE} ⇒ {NNEE};dirt(D1F)={NNE},根据式(6),得dir1(EF)={NNE} {NNEE}=NWNE,表明FE的主方向关系为东北、西北;由表 1得出的空间方向关系为dirt(EF)=NNE,两者关系不相等的主要原因是图形局部形状大小对方向关系表达具有相对性,但由dir1(EF)推理得出的NWNE在方向关系的表达上包含NNE,验证了LDC对内部性、外部性方向关系推理的可行性。当基于1个参照对象的两个方向关系相同时,如dirt(FE)={N},dirt(FD1)={N},则dir1(ED1)= dirt(FE) | dirt(FD1)={N} | {S},dir1(ED1)的方向关系推理包含了dirt(ED1)={N}。经矩形代数方向关系对LDC的交叉验证,验证了同向条件下基于LDC的方向关系推理可行性。同方向关系推理的不确定性原因是两个目标对象与参照对象的距离不同。如若E置于D的下方,距离的改变并未影响DEF的方向关系,但方向关系推理结果却变为S。因此,空间对象间距离的改变虽未影响方向关系的表达,但改变了方向推理结果。

    • 鉴于方向关系矩阵对凹边形本身方向关系表达的模糊性,本文从方向关系的外部性参照和内部性参照出发,利用三等分仿射变换方法将对象间的模糊性本身方向关系细化为外部性参照的八方向关系;根据凹边形顶点的凹凸性,采用凹凸点的反向延长线分割凹边形方法实现了方向关系的内部性参照对象表达;在方向关系推理上,方向关系的逻辑和、逻辑差合成代数方法分别实现了1个参照对象、2个参照对象的主方向关系推理。经矩形代数空间方向关系验证,验证了1个参照对象、2个参照对象下基于LIC、LDC的方向关系推理有效性。针对研究中存在的1个参照对象中两个相同方向关系推理的不确定性,如何有效地对方向关系进行量化表达,实现方向关系推理的刚性判定,是主方向关系推理后续工作中需要进一步研究和解决的问题。

参考文献 (20)

目录

    /

    返回文章
    返回