留言板

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

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

面向关键点的轨迹-有向线移动过程建模

向隆刚 王星星 吴涛 陶强强

向隆刚, 王星星, 吴涛, 陶强强. 面向关键点的轨迹-有向线移动过程建模[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
引用本文: 向隆刚, 王星星, 吴涛, 陶强强. 面向关键点的轨迹-有向线移动过程建模[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
XIANG Longgang, WANG Xingxing, WU Tao, TAO Qiangqiang. Key Point-Oriented Modeling of Trajectory-Directed Line Movement[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
Citation: XIANG Longgang, WANG Xingxing, WU Tao, TAO Qiangqiang. Key Point-Oriented Modeling of Trajectory-Directed Line Movement[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731

面向关键点的轨迹-有向线移动过程建模

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

基金项目 Nos. 41471374, 41001296

详细信息

Key Point-Oriented Modeling of Trajectory-Directed Line Movement

Funds: 

The National Natural Science Foundation of China Nos. 41471374, 41001296

More Information
图(6) / 表(4)
计量
  • 文章访问数:  1302
  • HTML全文浏览量:  51
  • PDF下载量:  440
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-10-15
  • 刊出日期:  2016-10-05

面向关键点的轨迹-有向线移动过程建模

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

    基金项目 Nos. 41471374, 41001296

    作者简介:

    向隆刚,博士,副教授,主要从事轨迹数据处理与分析研究。geoxlg@whu.edu.cn

    通讯作者: 王星星,硕士生,Email:2013206190002@whu.edu.cn
  • 中图分类号: P208

摘要: 轨迹数据处理与分析是目前数据库和空间信息等相关领域的研究热点之一。针对轨迹在地理空间中相对于有向线的移动过程发生多次相交、相切、重叠、折返且存在停留的复杂情况,提出一种面向关键点的轨迹-有向线语义拓扑移动过程模型,表达轨迹相对于有向线的随时间演变的语义拓扑关系,包括方向关系、位置关系及语义信息。该模型从方向关系的局部有效特征出发,基于缓冲区建立平面空间参考框架;在此基础上,从拓扑角度对轨迹-有向线的起止点、交点、折返点和停留点等关键点进行分析,得到172种语义拓扑关系,将其划分为14种拓扑关系类;最后,模型以语义明确的字符编码表达关键点的语义拓扑关系,并以关键点编码序列刻画轨迹相对于有向线的复杂移动过程。

English Abstract

向隆刚, 王星星, 吴涛, 陶强强. 面向关键点的轨迹-有向线移动过程建模[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
引用本文: 向隆刚, 王星星, 吴涛, 陶强强. 面向关键点的轨迹-有向线移动过程建模[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
XIANG Longgang, WANG Xingxing, WU Tao, TAO Qiangqiang. Key Point-Oriented Modeling of Trajectory-Directed Line Movement[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
Citation: XIANG Longgang, WANG Xingxing, WU Tao, TAO Qiangqiang. Key Point-Oriented Modeling of Trajectory-Directed Line Movement[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1292-1298. doi: 10.13203/j.whugis20140731
  • 近年来,轨迹数据处理与分析受到国内外很多科研人员、科研机构及企业单位的高度重视。数据模型[1]、语义注解[2]、查询分析[3, 4]、数据挖掘[5]等成为轨迹数据研究的热点方向。

    轨迹投影到地理空间并插值之后,可将其看作一种复杂的有向线(即轨迹线,下同),通常表现为曲线,可以自交、闭合、折返,甚至包括多个分支。此外,移动对象可能出于某种目的在某地停留[1],且一条轨迹中可能存在多个这样的停留。

    轨迹在地理空间中相对于有向线的移动过程可能非常复杂。如图 1所示,红色箭头表示某人一天出行的轨迹线,黑色箭头表示某公路单向路段,作为轨迹线的参考有向线。不难看出轨迹线与参考有向线存在多次相交(点2、8、9、10、11) 、相切(点3) 、重叠(点4、6) 及折返(点5) 等复杂关联关系。下文统一采用黑色实线表示参考有向线A,红色实线表示轨迹线B,箭头表示轨迹线/参考有向线的方向,△、∇分别表示起点和终点,•表示交点(或折返点),○表示停留点。

    图  1  轨迹-有向线移动过程示例

    Figure 1.  An Example about the Movement of a Trajectory-Directed Line

    针对轨迹在地理空间中相对于有向线的复杂移动过程,本文提出一种面向关键点的轨迹-有向线语义拓扑移动过程模型。该模型从拓扑角度,表达轨迹线起点、终点、折返点、交点及停留点等关键点相对于有向线的随时间演变的方向关系、位置关系及语义信息,不仅可以区分相交、相切和重叠(含同向、反向关系)等拓扑细节,而且能够表达起始、终至、折返和停留等语义信息。

    • 本文将轨迹看作一种复杂的有向线,探讨其相对于有向线的移动过程。

      线空间关系模型的研究始于上世纪九十年代,4交模型[6]、9交模型[7]是早期的线拓扑关系模型,为后来提出的V9I模型[8]、RCC(Randell,Cui and Cohn)模型[9]、空间代数模型[10]等奠定了基础。早期线方向关系模型有double-cross[11]、dipole calculus[12]、direction-relation matrix[13]等。

      在有向线的空间关系方面,Clementini等[14]提出用四种拓扑不变量进行描述,但交点类型的判断比较复杂,且需要结合图例来判别。Kurata等[15]提出的HBT(head-body-tail)模型定义了10类基本拓扑关系,但模型忽略了有向线内部存在的相交、相切、重叠等拓扑细节。王生生等[16]提出的DDLO(detail of directed line object)模型可以精确描述多次相交的细节,但需要结合图例来区分。Moratz等[17]提出了DRA(dipole relation algebra)模型,描述有向线起点、终点相对于另一有向线的空间关系,但不适用于轨迹—有向线的移动过程建模。吴静等[18]提出了三元组DLR(directed line relation)模型,改进了有向线空间关系的区分能力,但仍存在以下几点不足:当参考有向线为曲线时,建立这种平面划分较为困难,甚至是不可能的;不能区分同向、反向关系;也不能区分交点拓扑位置。

    • 轨迹作为一种复杂的有向线,在地理空间中相对于有向线的移动过程可能发生多次相交、相切、重叠、折返且存在停留。本文将起点、终点、折返点、交点及停留点作为轨迹-有向线移动过程的关键点,构建面向关键点的轨迹-有向线语义拓扑移动过程模型。

    • Moratz等[17]在提出DRA模型时,将有向线的平面空间划分为左侧(l)、右侧(r)、正前方(f)、正后方(b)四个区域。吴静等[18]提出的DLR模型在此基础上添加了左前(fl)、右前(fr)、左后(bl)、右后(br)等区域的划分。有向线通常表现为曲线,其方向关系仅在局部范围内成立。本文引入缓冲区概念,并据此建立平面空间参考框架,如图 2所示,图中闭合虚线表示有向线的缓冲区范围。在缓冲区中,整个平面空间被划分为有向线的起点(s)、内部(i)、终点(e)、前方(f)、后方(b)、左侧(l)、右侧(r)和外部(u)共8个部分。

      图  2  平面空间参考框架

      Figure 2.  A Reference Framework of Planar Space

      本文在探讨轨迹相对于有向线的移动过程时,主要针对缓冲区内部的关键点,发生在外部(即u)的关键点相对于有向线的意义不大,本文将不做讨论。

      考虑轨迹线上的任意关键点,以该点为圆心、无穷小正数ε为半径画一个圆。在圆内,关键点将轨迹线分为l1l2两部分,沿轨迹线的前进方向,l1由圆周指向圆心,称为入边,l2由圆心指向圆周,称为出边。关键点的入边、出边概念是基于局部范围定义的,其方向关系在缓冲区内总是成立的。

      起点没有入边,终点没有出边。交点是发生在有向线上的关键点,其入边、出边同时存在,且入边、出边至少有一个不在有向线上。折返点是移动对象在有向线上折返时产生的关键点,其入边、出边均在有向线上或其两端延长线上,且两者方向相反。

    • 在本文提出的平面空间参考框架之下,对于任意关键点P,其编码

      (1)

      称为关键点的语义拓扑编码。式中,x表示入边的方向关系,且x∈{Ф,f,b,l,r}(Ф表示该关系不存在,下同);y表示出边的方向关系,且y∈{Ф,f,b,l,r};ⓜ表示关键点的语义指示符,且ⓜ∈{ⓘ,ⓢ,ⓑ,ⓔ,ⓡ},其中,ⓘ表示相交,ⓢ表示停留,ⓑ表示始于,ⓔ表示终于,ⓡ表示折返;z表示关键点的拓扑位置,且z∈{s,e,i,f,b,l,r}。对于发生在参考有向线上或有向线前方、后方的任意关键点,以有向线的箭头方向为前方:如果入边(或出边)位于关键点前方,则x(或y)等于f;如果入边(或出边)位于关键点后方,则x(或y)等于b

      从关键点的语义拓扑编码可以看出,该编码同时包含方向关系(x、y)、位置关系(z)以及语义信息(ⓜ)。本文将方向关系与位置关系合称为拓扑关系,将这三种关系统称为语义拓扑关系。下文将从有向线外和有向线上两方面对关键点语义拓扑关系进行讨论。

    • 考虑有向线外关键点编码,通过排列组合出编码xyⓜz的所有可能性,见表 1,得到54种语义拓扑编码。显然,对于有向线外的关键点编码xyⓜz,满足z∈{f,b,l,r},ⓜ∈{ⓢ,ⓑ,ⓔ}

      表 1  有向线外关键点编码的54种可能情况

      Table 1.  54 Encoding Possibilities for Key Points Lying off a Directed Line

    • 考虑有向线上关键点编码,通过排列组合出编码xyⓜz的所有可能,见表 2,得到118种语义拓扑编码。显然,对于有向线外的关键点编码xyⓜz,满足z∈{s,e,i}

      表 2  有向线上关键点编码的118种可能情况

      Table 2.  118 Encoding Possibilities for Key Points Lying on a Directed Line

    • Kurata等[15]在HBT模型中将有向线之间(A相对于B)的拓扑关系总结为10类,即disjoint(相离)、split(分离)、follow(A在B后)、precede(A在B前)、meet(相遇)、diverge(A是B的分支)、divergedBy(B是A的分支)、merge(A融入B)、mergedBy(B融入A)、cross(相交)。本文在此基础上,考虑轨迹线的特殊性,增加4种拓扑关系类,即touch(相切)、return(折返)、forward overlap(同向重叠)、backward overlap(反向重叠)。表 3即对14种拓扑关系类与关键点语义拓扑编码xyⓜz之间的对应关系进行了总结。需要指出的是,disjoint是相离关系,对应所有发生在有向线外的关键点编码,故表 1中54种编码的拓扑关系类均为disjoint。而对于其它13种拓扑关系类,图 3图 4列出了它们与表 2中118种编码之间的映射关系,同时给出了这118种编码的图例表达。

      表 3  轨迹-有向线拓扑关系类

      Table 3.  Topological Relation Classes for Trajectory-Directed Line

      图  3  有向线上关键点拓扑关系类之非重叠关系

      Figure 3.  Non-Overlapping Topological Relations for Key Points Lying on a Directed Line

      图  4  有向线上关键点拓扑关系类之重叠关系

      Figure 4.  Overlapping Topological Relations for Key Points Lying on a Directed Line

    • 首先从轨迹线的起点开始跟踪,将起点、终点、交点、折返点及停留点等关键点顺序编号,然后逐一编码,所有关键点编码依次顺序排列,即可得到语义拓扑编码序列表达的轨迹-有向线移动过程模型:

      (2)

      式中,TL表示轨迹T相对于有向线L的关键点编码序列,Фy1z1xnФzn分别是轨迹线起点、终点编码,xiyimizi是轨迹-有向线移动过程的第i个关键点编码,且

      在关键点编码序列中,单个关键点编码xyⓜz存在一定的约束,见表 1表 2表 3,从中不难发现单个关键点编码存在如下约束:

      1) zx、y编码具有3种约束:

      ① 若x=l(或r),或y=l(或r),则z≠r(或l);

      ② 若x=ly=r,或x=ry=l,则z∉{l,r }

      ③ 对于有向线外的关键点,即z∉{ s,i,e },若x∈{f,b},或y∈{f,b},则z∈{f,b}

      2) ⓜ与x、y、z编码具有4种约束:

      ① 若x=Ф,则ⓜ=ⓑ;

      ② 若y=Ф,则ⓜ=ⓔ;

      ③ 若x=y=fb,则ⓜ=ⓡ或ⓢ;

      ④ 若z∈{ f,,l,r}x、y≠Ф,则ⓜ=ⓢ。

      此外,相邻关键点编码之间也存在一定的约束。发生重叠关系时,重叠关键点个数至少为2个,相邻的重叠关键点编码之间存在如下约束:

      1) 设某关键点编码为lfⓘi,拓扑关系类为同向重叠关系,下一个关键点(交点、折返点或停留点)的入边必然与有向线同向重叠,且该关键点只可能发生在有向线的内部或终点处,即x=bz=ie

      2) 设某关键点编码为lbⓘi,拓扑关系类为反向重叠关系,下一个关键点(交点、折返点或停留点)的入边必然与有向线反向重叠,且该关键点只可能发生在有向线的内部或起点处,即x=fz=is

      需要指出的是,当轨迹在交点(或折返点)处有停留时,由于相交(或折返)语义隐含在关键点编码中,此时只需用ⓢ作为语义提示符,同时表达停留和相交(或折返)两层含义。例如,lfⓢi表示从左向右穿过有向线,且在交点处有停留。

      图 1所示轨迹-有向线共有11个关键点,对其进行语义拓扑过程建模,结果见表 4所示。表 4同时列出了所有关键点的语义拓扑编码所属的基本拓扑关系类。

      表 4  轨迹-有向线移动过程(图 1)建模结果

      Table 4.  Modeling Result for the Movement (Fig. 1) of Trajectory-Directed Line

    • 每年在非洲都会上演壮观的动物大迁徙场面,角马、斑马、羚羊等组成声势浩大的队伍,从坦桑尼亚(TANZANIA)的塞伦盖蒂保护区前往肯尼亚(KENYA)的马赛马拉国家公园,如图 5所示,沿途跨越马拉河(Mara river)、塔雷克河(Talek river)和格鲁米提河(Grumeti river)等多条河流。以河流为参考有向线(方向为河流流向),动物在迁徙过程时:会在岸边饮水或探查渡河点(停留),沿着河流移动(同向或反向重叠),或直接渡河(相交)。基于轨迹-有向线语义拓扑移动过程模型,可对动物相对于河流移动的复杂语义拓扑过程进行建模。图 6在较大比例尺下给出了五条典型的动物迁徙轨迹。

      图  5  非洲角马迁徙图[19]

      Figure 5.  A Migration Map about African Wildebeests

      图  6  相对于格鲁米提河的角马轨迹

      Figure 6.  Wildebeest Trajectories with Respect to Grumeti River

      从语义解析和查询分析两方面的应用进行说明:

      1) 语义解析

      在本文提出的轨迹-有向线语义拓扑移动过程模型中,关键点编码同时包含方向关系、位置关系和语义信息。针对关键点编码序列的语义解析可从拓扑角度还原移动对象相对于有向线的移动过程。例如,轨迹Ⅰ编码的解读如下:动物一路北迁,在抵达河岸后停留(饮水休息),接着在河流右侧移动,一段时间后再次靠近河岸(探查渡河点),接着继续在河流右侧移动,最终从合适地点渡过河流,到达水草茂盛的北岸。

      2) 查询分析

      本文提出的轨迹-有向线移动过程模型还可应用于查询分析。将多个轨迹-有向线移动过程编码存储于数据库中,即可通过字符串扫描的简单方式来查询分析轨迹-有向线移动过程。

      ① 查询未到达河流北岸的动物:动物没有成功渡河(溺毙或被其它动物猎杀),则轨迹不在有向线左侧移动,说明所有关键点的方向关系和位置关系均不在有向线左侧,扫描所有关键点编码序列,过滤掉关键点编码满足x=ly=l的轨迹,即可得到检索结果,故返回轨迹Ⅳ。

      ② 查询徘徊多次后渡河的动物:动物没有直接渡河,说明轨迹与有向线存在相切关系,根据相切关系的特点,存在关键点编码满足x=y=lr,且z∈{s,i,e},即将其所属轨迹列入结果集中,故返回轨迹Ⅰ和Ⅴ。

    • 本文将轨迹看作一种复杂的有向线,提出一种面向关键点的轨迹-有向线语义拓扑移动过程模型。该模型可以表达轨迹线起点、终点、折返点、交点及停留点等关键点相对于有向线的位置关系和方向关系,并含语义信息。与其他研究相比,本文模型具有以下4个特点。

      1) 对于曲线形式的有向线对象,其方向关系仅在局部范围内成立。从这一认识出发,我们引入缓冲区概念,并基于缓冲区建立平面空间参考框架。

      2) 将起点、终点、折返点、交点以及停留点等作为轨迹-有向线移动过程的关键点,从拓扑角度对其进行语义编码,以表达轨迹相对于有向线的随时间演变的语义拓扑关系。

      3) 关键点的编码方式简单直观,易于理解。例如,lfⓘs,表示从左方进入有向线起点,且往终点方向移动。

      4) 在关键点编码的基础上,提出了轨迹-有向线语义拓扑移动过程模型,不仅可以有效区分相交、相切和重叠(含同向和反向关系)等拓扑细节,能够表达始于、终于停留和折返等语义信息。

      在后续工作中,将依据Clementini[14]关于线-线拓扑不变量的研究成果,进一步考虑相邻关键点的连接方向问题。

参考文献 (19)

目录

    /

    返回文章
    返回