留言板

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

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

矩形方向约束的邻域空间推理

张丁文 陈占龙 谢忠

张丁文, 陈占龙, 谢忠. 矩形方向约束的邻域空间推理[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165
引用本文: 张丁文, 陈占龙, 谢忠. 矩形方向约束的邻域空间推理[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165
ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Neighborhood Reasoning of Rectangular Direction Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165
Citation: ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Neighborhood Reasoning of Rectangular Direction Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165

矩形方向约束的邻域空间推理

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

国家重点研发计划 2017YFC0602204

国家自然科学基金 41401443

国家自然科学基金 41671400

湖北省自然科学基金 2015CFA012

中央高校基本科研业务费专项资金优秀青-基金 CUG160226

详细信息

Neighborhood Reasoning of Rectangular Direction Constraints

Funds: 

The National Key Research & Development Program of China 2017YFC0602204

the National Natural Science Foundation of China 41401443

the National Natural Science Foundation of China 41671400

the Natural Science Foundation of Hubei Province 2015CFA012

the Research Funds for the Central Universities Basic Special Projects CUG160226

More Information
    Author Bio:

    ZHANG Dingwen, PhD, specializes in spatial reasoning, spatial analysis and geo-computation. E-mail:dingwenzhang@yahoo.com

    Corresponding author: CHEN Zhanlong, PhD, associate professor. E-mail:Chenzhanlong2005@126.com
  • 摘要: 在空间计算过程中,空间物体常被描述为其最小外包矩形,因此矩形间的方向约束是空间关系的一个关键子集。在矩形代数基础上,使用一个2×2的特征矩阵来描述矩形间的169种方向约束关系,并构建矩形方向约束邻域网格,以邻域网格上对应顶点间的最短网格路径分析矩形方向约束关系间的距离。进而,分析当两个矩形的其中一个发生缩放和平移等渐变时,一种矩形方向约束关系转变为其邻近约束关系的过程,并使用特征值元组区间的笛卡尔乘积来表示矩形变形过程中所形成矩形约束的特征矩阵,最后分析总结了矩形变形时对应特征矩阵的变化特点。
  • 图  1  矩形AB的两种矩形约束

    Figure  1.  Two Directional Constraints Between A and B

    图  2  RCD关系中北的4种可能的反方向

    Figure  2.  Opposite Direction of North in RCD Relations

    图  3  FM构建示例分析

    Figure  3.  Construction of F-Matrix

    图  4  ab间空间约束及对应FM

    Figure  4.  Spatial Constraints and F-Matrix of a, b

    图  5  关系“起始于”的邻近关系

    Figure  5.  Neighbor Relations of Start

    图  6  区间ab的13种区间关系及对应的邻域网格

    Figure  6.  13 Interval Relations Between Interval a, b and the Neighborhood Lattice of IA

    图  7  矩形方向关系FM的邻域网格

    Figure  7.  Neighborhood Lattice of F-Matrix

    图  8  o(-2, 0)和f(0, 1)间的连通路径

    Figure  8.  Path Between o(-2, 0) and f(0, 1)

    图  9  FM对应的邻域网格节点及距离

    Figure  9.  Vertex and Distances in Neighborhood Lattice for F-Matrices

    图  10  方向关系为A西北BA的扩展渐变

    Figure  10.  Gradual Changes of A when A NW B

    图  11  AB间可能矩形约束的邻域空间

    Figure  11.  Constraint Neighborhood Between A and B

    图  12  矩形A的水平平移

    Figure  12.  Horizontal Translation of A

    图  13  A水平平移过程所对应的多种邻域遍历路径

    Figure  13.  Travelling Paths in Neighborhood Lattice During Horizontal Translation of A

    表  1  区间代数关系及符号表示

    Table  1.   Interval Algebra Relations and Symbolic Representations

    区间代数关系 符号 逆关系符号
    在…之前(before) b bi
    重叠(overlay) o oi
    在…之间(during) d di
    相接(meet) m mi
    起始于(start) s si
    终止于(finish) f fi
    相等(equal) e e
    下载: 导出CSV
  • [1] Allen J F. Maintaining Knowledge About Temporal Intervals[J]. Readings in Qualitative Reasoning About Physical Systems, 1990, 26(11):361-372 http://dblp.uni-trier.de/db/journals/cacm/cacm26.html#Allen83
    [2] Freksa C. Temporal Reasoning Based on Semi-intervals[J]. Artificial Intelligence, 1992, 54(1-2):199-227 doi:  10.1016/0004-3702(92)90090-K
    [3] Güsgen H W. Spatial Reasoning Based on Allen's Temporal Logic[OL]. http://www.icsi.berkeley.edu/pubs/techreports/tr-89-049.pdf, 1989
    [4] Ligozat G É. Reasoning About Cardinal Directions[J]. Journal of Visual Languages & Computing, 1998, 9(1):23-44
    [5] Gerevini A, Renz J. Combining Topological and Size Information for Spatial Reasoning[J]. Artificial Intelligence, 2002, 137(1-2):1-42 doi:  10.1016/S0004-3702(02)00193-5
    [6] Balbiani P, Condotta J F, Ligozat G. Reasoning About Generalized Intervals: Horn Representability and Tractability[C]. International Workshop on Temporal Representation and Reasoning, Cape Breton, 2000
    [7] Vilain M, Kautz H, van Beek P. Constraint Propagation Algorithms for Temporal Reasoning: A Revised Report[M]//Readings in Qualitative Reaso-ning About Physical Systems. San Francisco: Morgan Kaufmann Publishers Inc, 1989
    [8] Wood J. Minimum Bounding Rectangle[M]. Berlin:Springer, 2008
    [9] Navarrete I, Sciavicco G. Spatial Reasoning with Rectangular Cardinal Direction Relations[C]. ECAI 2006, 17th European Conference on Artificial Intelligence, Workshop on Spatial and Temporal Reasoning, Riva del Garda, 2006
    [10] Navarrete I, Sciavicco G. Spatial Reasoning with Rectangular Cardinal Direction Relations-The Convex Tractable Subalgebra[J]. Annals of Mathema-tics and Artificial Intelligence, 2013, 67(1):31-70 doi:  10.1007/s10472-012-9327-5
    [11] Randell D A, Cui Z, Cohn A G. A Spatial Logic Based on Regions and Connection[C]. 3rd International Conference on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, 1996
    [12] 周涛, 陆惠玲, 杨德仁, 等. "蛋-黄"模型的拓展研究[J].武汉大学学报·信息科学版, 2012, 37(2):242-246 http://ch.whu.edu.cn/CN/abstract/abstract130.shtml

    Zhou Tao, Lu Huiling, Yang Deren, et al. Popula-rized "Egg-Folk" Model[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2):242-246 http://ch.whu.edu.cn/CN/abstract/abstract130.shtml
    [13] Schneider M, Chen T, Viswanathan G, et al. Cardinal Directions Between Complex Regions[J].ACM Transactions on Database Systems, 2012, 37(2):1-40 doi:  10.1007%2Fs10639-006-9016-2
  • [1] 王彦平, 白泽朝, 林赟, 李洋.  InSAR双向矩形角反射器阵列形变监测精度评估与验证 . 武汉大学学报 ● 信息科学版, 2021, 46(10): 1471-1477, 1488. doi: 10.13203/j.whugis20210101
    [2] 李欣, 杨宇辉, 杨博, 尹峰.  利用方向相位特征进行多源遥感影像匹配 . 武汉大学学报 ● 信息科学版, 2020, 45(4): 488-494. doi: 10.13203/j.whugis20180445
    [3] 李邵波, 周丰年, 赵建虎, 冯杰.  联合灰度突变和方向约束的浅剖层位自动拾取 . 武汉大学学报 ● 信息科学版, 2019, 44(4): 532-538. doi: 10.13203/j.whugis20170131
    [4] 解愉嘉, 刘学军.  顾及轨迹地理方向的监控视频浓缩方法 . 武汉大学学报 ● 信息科学版, 2017, 42(1): 70-76. doi: 10.13203/j.whugis20160080
    [5] 陈占龙, 吕梦楼, 吴亮, 徐永洋.  基于特征矩阵和关联图的空间场景相似性度量方法 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
    [6] 王中辉, 闫浩文.  一种改进的锥形方向关系模型 . 武汉大学学报 ● 信息科学版, 2014, 39(2): 186-190. doi: 10.13203/j.whugis20120688
    [7] 郭庆胜, 冯代鹏, 刘远刚, 陈勇.  一种解算空间几何对象的最小外接矩形算法 . 武汉大学学报 ● 信息科学版, 2014, 39(2): 177-180. doi: 10.13203/j.whugis20120676
    [8] 王中辉, 闫浩文.  基于方向Voronoi图模型的群组目空间方向关系计算 . 武汉大学学报 ● 信息科学版, 2013, 38(5): 584-588.
    [9] 杨曦光, 黄海军, 刘艳霞, 严立文.  水-气界面辐射能量的方向性特征及水体透射特征研究 . 武汉大学学报 ● 信息科学版, 2013, 38(8): 1003-1008.
    [10] 陈晖, 舒欣, 殷建平.  利用方向场进行指纹图像快速分区 . 武汉大学学报 ● 信息科学版, 2012, 37(2): 165-169.
    [11] 郭继发.  高阶模糊地理对象的方向关系研究 . 武汉大学学报 ● 信息科学版, 2011, 36(12): 1414-1417.
    [12] 沈敬伟, 闾国年, 温永宁, 吴明光.  拓扑和方向空间关系组合描述及其相互约束 . 武汉大学学报 ● 信息科学版, 2011, 36(11): 1305-1308.
    [13] 杜世宏, 郭泺.  基于拓扑关系的不确定区域方向关系推理 . 武汉大学学报 ● 信息科学版, 2010, 35(4): 388-393.
    [14] 何建华, 刘耀林, 俞艳.  不确定方向关系的模糊描述模型 . 武汉大学学报 ● 信息科学版, 2008, 33(3): 257-260.
    [15] 郭庆胜, 郑春燕.  锥形空间方向关系模型的改进 . 武汉大学学报 ● 信息科学版, 2007, 32(1): 81-84.
    [16] 毛建华, 王涛, 郭庆胜.  邻接凸多边形方向关系计算及其推理 . 武汉大学学报 ● 信息科学版, 2001, 26(4): 364-368.
    [17] 王永宁, 刘明亮, 朱海红.  彩色CRT显示器描述颜色特性的数学模型 . 武汉大学学报 ● 信息科学版, 1996, 21(1): 73-76.
    [18] 李以赫, 文剑光.  重力方向传感器 . 武汉大学学报 ● 信息科学版, 1995, 20(3): 263-268.
    [19] 顾旦生.  单三角锁按方向观测平差 . 武汉大学学报 ● 信息科学版, 1959, 3(3): 39-49.
    [20] 钱冰.  科学研究的方向和道路 . 武汉大学学报 ● 信息科学版, 1958, 2(0): 8-10.
  • 加载中
图(13) / 表(1)
计量
  • 文章访问数:  1116
  • HTML全文浏览量:  85
  • PDF下载量:  292
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-09-13
  • 刊出日期:  2018-08-05

矩形方向约束的邻域空间推理

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

    国家重点研发计划 2017YFC0602204

    国家自然科学基金 41401443

    国家自然科学基金 41671400

    湖北省自然科学基金 2015CFA012

    中央高校基本科研业务费专项资金优秀青-基金 CUG160226

    作者简介:

    张丁文, 博士, 主要研究方向为空间分析基础算法、空间场景相似性等。dingwenzhang@yahoo.com

    通讯作者: 陈占龙, 博士, 副教授。Chenzhanlong2005@126.com
  • 中图分类号: P208

摘要: 在空间计算过程中,空间物体常被描述为其最小外包矩形,因此矩形间的方向约束是空间关系的一个关键子集。在矩形代数基础上,使用一个2×2的特征矩阵来描述矩形间的169种方向约束关系,并构建矩形方向约束邻域网格,以邻域网格上对应顶点间的最短网格路径分析矩形方向约束关系间的距离。进而,分析当两个矩形的其中一个发生缩放和平移等渐变时,一种矩形方向约束关系转变为其邻近约束关系的过程,并使用特征值元组区间的笛卡尔乘积来表示矩形变形过程中所形成矩形约束的特征矩阵,最后分析总结了矩形变形时对应特征矩阵的变化特点。

English Abstract

张丁文, 陈占龙, 谢忠. 矩形方向约束的邻域空间推理[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165
引用本文: 张丁文, 陈占龙, 谢忠. 矩形方向约束的邻域空间推理[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165
ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Neighborhood Reasoning of Rectangular Direction Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165
Citation: ZHANG Dingwen, CHEN Zhanlong, XIE Zhong. Neighborhood Reasoning of Rectangular Direction Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1185-1192. doi: 10.13203/j.whugis20160165
  • 在GIS、人工智能(artificial intelligence, AI)、图像检索等研究领域中,为了识别时空推理中不同对象间的关系,研究人员针对空间对象间的方向关系提出了许多模型及架构,较常用的有区间代数演算[1](interval algebra calculus, IA)(线形区域间的方向演算)、空间点对象间的方向演算[2-3]、空间面对象间的方向演算(cardinal direction calculus, CDC)[4]、区域连接演算(region connection calculus-8, RCC-8)[5]、矩形代数演算(rectangle algebra calculus, RA)[6]和对象关系矩阵(object interaction matrix, OIM)[7]等。

    在实际应用中,为了优化空间分析计算过程,空间物体常用其最小外包矩形描述[8],因此矩形间的空间方向约束是空间关系的一个关键子集。在CDC中,参照对象的最小外包矩形的延伸边界将其外部空间划分为9个分区,并分析被比较对象在这9个分区中的占据情况,从而得出两个对象间的方向关系。与CDC类似,OIM同时使用参照对象和被比较对象的边界进行空间划分。矩形方向演算[9-10](rectangular cardinal direction calculus, RCD)定义了矩形间的36种方向关系。RA[8]使用基本区间关系对来描述169种矩形空间约束关系。RCC-8[5]基于RCC-理论[11]中的8种基本关系来定义两个区的空间约束关系。但二者都缺乏定量分析的准确性和完整性。

    为了高效地分析矩形间的方向约束,本文提出描述矩形方向关系的特征矩阵(F-matrix, FM),实现了与矩形代数关系及矩形方向关系之间的对应,并讨论如何基于FM的数学性质度量矩形方向关系间的距离。使用整数集合{-2, -1, 0, 1, 2}中的元素构建FM,169个矩阵分别映射两个矩形间的169种方向约束关系,能满足矩形方向求反运算的唯一性,且矩阵所固有的数学性质使矩形间的方向推理更简单,空间关系间的推理研究见文献[5, 12]。

    • 图 1中描述的是矩形AB的两种矩形约束,两者不同之处在于图 1(a)AB的边相离,而图 1(b)AB的边相接。在CDC中,矩形A相对于B的两种矩形约束都被描述为:

      $$ {\rm{dir}}\left( {A, B} \right) = \left[{\begin{array}{*{20}{c}} 1&0&0\\ 0&0&0\\ 0&0&0 \end{array}} \right] $$ (1)

      图  1  矩形AB的两种矩形约束

      Figure 1.  Two Directional Constraints Between A and B

      即CDC对于矩形边界相接的情况,容易出现描述混淆。

      使用OIM描述图 1, 两种矩形约束可表示为:

      $$ {\rm{OIM}}\left( {A, B} \right) = \left[{\begin{array}{*{20}{c}} 2&0&0\\ 0&0&1 \end{array}} \right] $$ (2)
      $$ {\rm{OIM}}\left( {A, B} \right) = \left[{\begin{array}{*{20}{c}} 2&0\\ 0&1 \end{array}} \right] $$ (3)

      从式(2)和(3)可知,OIM能分辨出矩形边界相接的情况,但由于空间划分依赖双方矩形的边界(具体可参考文献[13]),导致其矩阵大小无法统一(式(2)的3×2矩阵和式(3)的2×2矩阵),难以直接计算。

      RCD在对矩形方向关系求反时无法保持唯一性,即已知矩形A相对B的方向,却无法确定B相对A的方向。如图 2所示,A相对B的RCD关系为北,而B相对A的方向则可能为南、南:西南、南:东南和南:东南:西南。尽管RCD明确定义了每个方向的弱反方向集,但在空间方向分析中,难以对组合方向关系(包含两个以上基本方向)进行高效推理。

      图  2  RCD关系中北的4种可能的反方向

      Figure 2.  Opposite Direction of North in RCD Relations

      为了有效描述矩形约束关系及度量关系间的距离,本文使用FM来描述矩形方向约束。将参照矩形B和目标矩形A分别表示为投影区间端点(Ax-, Ay-, Ax+, Ay+)和(Bx-, By-, Bx+, By+),可将矩形约束转换为一维区间约束。根据点代数演算[10],平面R2上的点p1(目标端点)和p2(参照端点)间存在大于、等于和小于(>, < ,=)3种顺序关系;用函数C为端点间的顺序关系分配数值(式(4)),显然,“>”和“ < ”是一对互逆约束,0表示“=”。

      $$ C\left( {{p_1}, {p_2}} \right) = \left\{ \begin{array}{l} -1 \Leftrightarrow {p_1} < {p_2}\\ 0 \Leftrightarrow {p_1}{\rm{ = }}{p_{\rm{2}}}\\ 1 \Leftrightarrow {p_1} > {p_2} \end{array} \right. $$ (4)

      基于函数C可分析端点p与一维区间I间的关系。先分别计算p和区间端点I-I+间顺序关系的表示值,两值之和称为特征值(定义1),特征值描述了端点与一维区间的约束关系。该方法能在计算中较好地保持端点间的顺序关系。

      定义1  特征值。计算端点对(I*, J-)和(I*, J+)的顺序关系表示值并求和,所得值称为描述端点I*与区间J[J-, J+]间约束关系的特征值v(I*, J)

      $$ {v_{\left( {{I^*}, J} \right)}} = C\left( {{I^*}, {J^-}} \right) + C\left( {{I^*}, {J^ + }} \right) $$ (5)

      在端点与一维区间约束关系的特征值基础上,本文使用特征值元组来描述两个一维区间对象间的约束关系。

      定义2  特征值元组。特征值元组t(I, J)描述了目标区间I与参照区间J的约束关系,包含端点I-I+与区间J的约束关系特征值v-v+, 即:

      $$ \left\{ \begin{array}{l} {t_{\left( {I, J} \right)}} = \left( {{v^-}, {v^ + }} \right)\\ {v^-} = C\left( {{I^-}, {J^ - }} \right) + C\left( {{I^ - }, {J^ + }} \right)\\ {v^ + } = C\left( {{I^ + }, {J^ - }} \right) + C\left( {{I^ + }, {J^ + }} \right) \end{array} \right. $$ (6)

      AB投影区间之间存在8个有意义的端点对,即8个非空的顺序关系值。本文使用一个顺序关系矩阵对这8个关系值进行组织,即:

      $$ \left[\begin{array}{l} C({A_{{x^-}}}, {B_{{x^-}}})\;C({A_{{x^ + }}}, {B_{{x^-}}})\;C({A_{{x^ - }}}, {B_{{x^ + }}})\;C({A_{{x^ + }}}, {\rm{ }}{B_{{x^ + }}})\\ C({A_{{y^ - }}}, {B_{{y^ - }}})\;C({A_{{y^ + }}}, {B_{{y^ - }}})\;C({A_{{y^ - }}}, {B_{{y^ + }}})\;C({A_{{y^ + }}}, {\rm{ }}{B_{{y^ + }}}) \end{array} \right] $$ (7)

      式(7)中,第一行描述了x轴投影区间[Ax-, Ax+]和[Bx-, Bx+]间的端点顺序关系, 第二行与y轴投影区间[Ay-, Ay+]、[By-, By+]相对应。将顺序关系矩阵转换为FM,首先将矩阵划分为4部分,分别与A投影区间端点对应,然后对每部分求和以计算单个区间对参照区间端点的约束特征值。

      定义3  特征矩阵(FM)。特征矩阵FMA, B定量描述了矩形AB间的空间约束,并基于ABxy轴投影区间端点间的顺序关系进行构建,使用特征值元组ftxftyFM进行化简,则可分别描述ABxy轴投影区间之间的约束。即:

      $$ \begin{array}{l} \left[\begin{array}{l} C\left( {{A_{{x^-}}}, \;{B_{{x^-}}}} \right) + C\left( {{A_{{x^ + }}}, {B_{{x^-}}}} \right)\;C\left( {{A_{{x^ - }}}, {B_{{x^ + }}}} \right) + C\left( {{A_{{x^ + }}}, {B_{{x^ + }}}} \right)\\ C\left( {{A_{{y^ - }}}, {B_{{y^ - }}}} \right) + C\left( {{A_{{y^ + }}}, {B_{{y^ - }}}} \right)C\left( {{A_{{y^ - }}}, {B_{{y^ + }}}} \right) + C\left( {{A_{y + }}, {B_{y + }}} \right) \end{array} \right]\\ = \left[{\begin{array}{*{20}{c}} {fv_x^1}&{fv_x^2}\\ {{\rm{ }}fv_y^1}&{fv_y^2} \end{array}} \right] = {\rm{ }}\left[{f{t_x}f{t_y}} \right]{^{\rm{T}}} \end{array} $$ (8)

      图 3中,ABxy轴上的投影区间分别是AxBxAyBy,区间端点间的顺序关系为Ax-Bx-Ax+Bx+Ay-By-Ay+By+。应用函数C(p1, p2)可得其顺序关系矩阵,再按照转换规则变换为描述矩形约束的FM,即:

      $$ \begin{array}{l} \mathit{\boldsymbol{F}}{\mathit{\boldsymbol{M}}_{A, B}} = \left[{\begin{array}{*{20}{c}} {-1}&{-1}&1&{-1}\\ 1&{ - 1}&1&1 \end{array}} \right] = \left[{\begin{array}{*{20}{c}} {-2}&0\\ 0&2 \end{array}} \right] = \\ \;\;\;\;\;\;\;\;\;\;\;{\left[{\left( {-2\;0} \right)\;\left( {0\;2} \right)} \right]^{\rm{T}}} \end{array} $$ (9)

      图  3  FM构建示例分析

      Figure 3.  Construction of F-Matrix

    • 图 4中,通过ab方向关系FM在时间点txtz处的变化,可推测abty处的方向关系,而使用RCD关系则无法预见这一变化(RCD关系在txty处保持一致)。由于FM集在描述矩形方向约束时是闭合的,且169个FM分别对应169种矩形方向约束,当两个矩形中的一个变形或移动时,如何识别最可能发生的矩形方向约束,因此,本文提出矩形约束关系的邻域空间概念。

      图  4  ab间空间约束及对应FM

      Figure 4.  Spatial Constraints and F-Matrix of a, b

    • 若通过连续改变,方向r1可直接转变为r2,则认为r1r2邻近。例如,区间a起始于(s)区间b,一个微小的改变会直接引发关系“ab中间(d)”或“ab重叠(o)”(图 5),因此dos邻近。本文在x-y平面基于特征值元组重新定义了区间关系的邻域网格。如图 6所示,xy轴分别指示区间关系对应特征值元组中的左、右特征值,平面上的13个顶点分别与13个特征值元组对应。用与轴平行的弧段连接每对邻近的顶点,可得区间关系的邻域网格。每个顶点在xy轴上的坐标形成了其对应的特征值元组,如关系bi的特征值元组是(2,2)。图 4中的关系列表见表 1

      图  5  关系“起始于”的邻近关系

      Figure 5.  Neighbor Relations of Start

      图  6  区间ab的13种区间关系及对应的邻域网格

      Figure 6.  13 Interval Relations Between Interval a, b and the Neighborhood Lattice of IA

      表 1  区间代数关系及符号表示

      Table 1.  Interval Algebra Relations and Symbolic Representations

      区间代数关系 符号 逆关系符号
      在…之前(before) b bi
      重叠(overlay) o oi
      在…之间(during) d di
      相接(meet) m mi
      起始于(start) s si
      终止于(finish) f fi
      相等(equal) e e

      定义4  特征值元组区间。特征值元组区间[(vi-vi+), (vj-vj+)]对应于由特征值元组(vi-vi+)和(vj-vj+)在其邻域空间中形成的封闭区域。对于任意特征值元组(vk-vk+) [(vi-vi+), (vj-vj+)],特征值vk-vk+满足顺序关系vi-vk-vj-vi+vk+vj+

      例如,特征值元组区间[(-1,0), (0,1)]的邻域空间范围如图 6中虚线围绕的矩形所示,(-1,0)为矩形左下角,(0,1)为右上角,区间中的特征值元组分别为(-1, 0)、(-1, 1)、(0, 0)和(0, 1),描述了4个基本的区间关系sefd

    • 本文使用邻域网格描述矩形约束的邻域空间。图 7中,两个垂直平面的轴分别为x1x2y1y2,分别与FM中的4个元素对应。x1-x2平面上的13个顶点分别对应13个特征值元组,每个顶点(x1i, x2i)有一个y1-y2平面,其中(x1i, x2i)作为y1-y2平面的原点,描述了当x轴区间约束特征值元组为(x1i, x2i)时,y轴上所有可能区间约束的特征值元组。因此,矩形约束邻域空间中的169个顶点分别代表 169个FM,通过使用与xy轴平行的弧段连接任意两个最近顶点,可得矩形方向约束的邻域网格。

      图  7  矩形方向关系FM的邻域网格

      Figure 7.  Neighborhood Lattice of F-Matrix

    • FM由描述了矩形投影区间约束的特征值元组对构建,通过挖掘特征值元组的数学性质可计算两种矩形方向约束间的邻域距离。在区间关系邻域网格中(图 8),从o(-2, 0)出发到达f(0, 1)的可能路径为ofidisioifofiesioif, osesioifofiefosefosdf。设每对近邻特征值元组间的距离为1,则上述路径距离分别为5、5、5、3、3和3。邻域空间距离指的是空间中连接两点的最短距离,因此区间关系邻域距离对应特征值元组在网格中的最短路径距离,即o(-2, 0)和f(0, 1)间的邻域距离应为3。

      图  8  o(-2, 0)和f(0, 1)间的连通路径

      Figure 8.  Path Between o(-2, 0) and f(0, 1)

      定义5  特征值元组距离。特征值元组f1(v1-, v1+)和f2(v2-, v2+)间的距离为特征值元组中对应元素绝对值之差的和,即

      $$ {d_{{f_1}, {f_2}}} = \left| {v_1^--v_2^-} \right| + \left| {v_1^ + -v_2^ + } \right| $$ (10)

      由于特征值元组abc在邻域网格中的位置有两种情况,三者形成直线段或三角形。直线段中有da, b+ db, c = da, cda, c+dc, bda, bdb, a+da, cdb, cdb, c+dc, adb, adc, a+ da, bdc, bdc, b+ db, a=dc, a几种可能的距离关系,根据三角形两边之和大于第三边原理,必然有dft1, ft2+ dft2, ft3dft1, ft3。因此,得出如下两条性质。

      性质1  特征值元组间邻域距离的取值范围为[0, 8]。

      性质2  特征值元组对(f1, f2)和(f2, f3)间的邻域距离之和必然大于或等于特征值元组对(f1, f3)的邻域距离。

    • 矩形方向约束距离为对应FM的邻域网格最短路径距离,且近邻距离为1。图 9中,FM[(-2,-1) (-2,2)]T与[(-2,-2) (-1,2)]T邻近,距离为1,[(-2,-1) (-1,2)]T与[(-2,0) (0,2)]T,[(-2,-2) (-2,2)]T和[(-2,-1) (-1,2)]T间的最短路径如图 9中粗线所示,分别为2和3。

      图  9  FM对应的邻域网格节点及距离

      Figure 9.  Vertex and Distances in Neighborhood Lattice for F-Matrices

      定义6  特征矩阵邻域距离。特征矩阵FM1(f1-, f1+)和FM2(f2-, f2+)间的距离为对应特征值元组的邻域距离之和。

      矩形约束邻域网格中的顶点代表FM,顶点间的弧段则描述了FM间的邻域距离,通过邻域网格可以确定每个FM的近邻,从而推测矩形渐变时最可能发生的矩形方向约束。

    • 缩放是指对矩形扩大或缩小以改变矩形间的方向约束,以下渐变分析只针对矩形A,参照矩形B的渐变可根据关系对称性进行推导。

      A扩展渐变的典型例子是A相对B的初始方向关系分别为西北、西南、东南、西南。图 10描述了A西北B时(初始FM为[(-2,-2) (2,2)]T)A的渐变。A同时存在水平和垂直方向渐变,若对A进行水平扩展,会演变5种不同的矩形方向约束,AB间方向关系依次转变为A西北BA西北:北BA西北:北:东北B,同时水平方向约束对应的特征值元组依次为(-2,-2)→(-2,-1)→(-2,0)→(-2,1)→(-2,2)。

      图  10  方向关系为A西北BA的扩展渐变

      Figure 10.  Gradual Changes of A when A NW B

      性质3  已知初始矩形方向约束的FM,在矩形渐变过程中产生的矩形方向约束,可使用初始特征值元组与结束特征值元组所组成区间的笛卡尔乘积进行推理。

      图 11中,AB间初始水平和垂直方向约束的特征值元组分别为(-2,-2)和(2,2),对A进行扩展渐变产生的FM可表示为区间[(-2,-2), (-2,2)]和[(2,2), (2,-2)]的笛卡尔乘积,25个结果FM(图 9中加粗线上顶点)分别与图 11的25种矩形约束对应,并可根据最短路径计算渐变方向间的距离。

      图  11  AB间可能矩形约束的邻域空间

      Figure 11.  Constraint Neighborhood Between A and B

    • 平移描述的是矩形在平面上移动使得矩形方向约束发生变化,有水平平移、垂直平移及水平和垂直方向平移3种情况。图 12为水平平移的例子,AB间的初始方向关系为A西北B,对应FM为[(-2,-2) (2,2)]TA进行水平移动时,从A西北B转变为A东北B的过程中共经历5种方向关系,对应9种矩形方向约束,FM可表示为特征值元组区间的笛卡尔积[(-2,-2), (2,2)]×[(2,2)]。

      图  12  矩形A的水平平移

      Figure 12.  Horizontal Translation of A

      两个FM间的邻域网格遍历路径的选择原则是:路径中的任意相邻节点必须在同一平面上,且出于效率优化的考虑,遍历路径的水平或垂直方向应保持一致,从而实现以最短路径访问到结束FM的目的。

      若知道起始和结束方向约束,通过对FM邻域网格进行分析,可得若干种矩形移动路径,从FM [(-2,-2),(1,2)]T演变为[(-2,-2),(-2,-2)]T的过程中,有图 13的6种连通遍历路径。从对矩形缩放和平移所引起的矩形方向关系变化情况分析可知,使用FM对矩形方向关系进行推理和预测时,数字特有的性质可保证分析结果的准确、完全,且根据FM邻域网格可计算出矩形方向约束之间的距离,并分析出在矩形平移过程中,从起始方向关系到终止方向关系间所有可能的遍历路径,在实际情况中可利用这一性质制定解决方案和策略。

      图  13  与A水平平移过程所对应的多种邻域遍历路径

      Figure 13.  Travelling Paths in Neighborhood Lattice During Horizontal Translation of A

    • 本文使用FM来描述矩形之间的方向约束关系,并分析了矩形方向关系邻域空间及如何基于 FM计算两个矩形方向间的距离,这对计算矩形方向相似度具有非常大的帮助。本文根据矩形变形过程中的初始矩形约束和终止矩形约束,使用特征值元组区间的笛卡尔乘积,推算出衍变过程中生成的新矩形约束,并通过矩形约束推断出矩形间的几何约束。同时还可预测矩形变形所引起的矩形约束变化。若当前矩形约束为相接,则下一个矩形约束必定是分离或重叠,因此根据当前矩形约束和即将发生的变形,可以进行更多详细的预测。下一步的工作是将其应用到空间场景的相似性识别中。

参考文献 (13)

目录

    /

    返回文章
    返回