基于地标的行人导航路径引导方法

陈 玥 璐，武 刚，陈 飞 翔

(北京林业大学信息学院，北京 100083)



基于地标的行人导航路径引导方法

陈 玥 璐，武 刚*，陈 飞 翔

(北京林业大学信息学院，北京 100083)

为了生成符合行人认知习惯的路径引导信息，以降低其在寻路过程中的认知压力并减少错误的寻路决策，提出一种基于地标的行人导航路径引导方法。该方法引入地标信息并建立空间对象间的可视关系，在此基础上使用方向模型和描述句法生成描述词和描述短语。随后提出了基于NLRP的全局路径描述算法和局部路径引导算法。前者提取中继目的地和途经地标，使用句法模式生成全局路径描述，为行人提供先验路径知识；后者判断行人当前位置，提取相关地标并结合句法生成对应位置的引导信息，辅助行人的寻路行为。最后，以北京林业大学校园为实验区域，验证了方法的可用性。

地标；行人导航；路径引导；NLRP

0 引言

随着智能移动设备的普及，行人导航(Pedestrian Navigation)成为近年来空间信息服务的研究热点。由电子地图、空间定位、路径规划和路径引导等模块组成的行人导航系统(Pedestrian Navigation System)辅助用户沿预先规划的路径迅速、准确地抵达目的地。路径引导(Route Directions)按照预定路径，提供一系列抵达目的地需采取的行动描述信息，辅助人们的寻路(Way-finding)行为[1]，是行人导航中的重要环节。目前，行人导航软件仍采用由车载导航继承而来的“到转向距离”(Distance-to-Turn)的引导方法[2]，不考虑用户空间知识，在路径中的决策点(Decision Points)处生成行动指令，组织成符号、文字或语音等形式的引导信息并展示给用户，辅助其寻路决策。此方法生成的信息虽然有效但不够自然，不符合行人的寻路习惯[1]。

地标(Landmark)是固定的、清晰的、独特的对象或区域，通常以兴趣点的形式存在，具有可见性和可辨识性[3]。作为人们惯用的寻路线索，可以降低行人的认知压力，提高寻路效率[2]。目前，已有学者引入结构化的地标作为路径元素并采用“到转向距离”的方法生成引导信息[4-6]。但当路径决策点较多时，该方法输出的引导信息将会非常冗长复杂，增加人们的记忆和认知压力[7]。另有学者直接利用地标生成路径描述[1,7]，但省略了路径细节，不适于处理复杂的路径[1]。行人通常活动于楼宇、街区间，决策点密度较大，路径复杂度较高，因此以上方法造成用户认知压力大，引导效率低。另外，行人行走不受规则道路限制，除不可达区域外皆可通行，且常见动作(如转身、调头等)易造成行进方向改变，导致偏离路径。上述方法在寻路前生成引导信息，无法根据行人位置实时引导，更无法在其偏离路径时进行纠偏，不能满足行人导航中的路径引导需求。

本文引入地标信息并提出了基于地标的空间位置描述方法，对空间对象进行位置描述。在此基础上，提出了基于GIS路径的自然语言表述(Natural Language Representation of Path,NLRP)方法[8]的全局路径描述算法和局部路径引导算法，将路径输出为由连续地标间的次序信息和与其配套的行为要求构成的引导信息[9]。两类符合认知习惯的引导信息分别在寻路前为行人形成先验路径知识[8,9]，在寻路中进行实时引导。

1 地标选取与可视关系构建

1.1 地标的选取和表示

地标按影响范围可分为局部地标和全局地标，在选取时需要考虑其视觉特征(如大小、颜色、结构等)、语义特征(特殊的文化或社会内涵)[6,10]。另外，行人活动于小尺度空间且运动速度较慢，视线容易被附近的地物遮挡，因此，为保证地标的可见性和可辨识性，应着重考虑其高度属性。局部地标用于定位和路径确认，应选取靠近路径同时具有较强语义特征的空间对象；全局地标用于形成空间知识，应选择具有较强视觉特征且影响范围较广的空间对象。靠近路径的全局地标也可替代局部地标的作用。两类地标都以空间点要素的形式存储在数据库中,并加入“名称”等属性字段。

1.2 可视关系构建

本文以节点、弧段为路径元素表示道路网络，使用改进的缓冲区分析算法构造空间对象可视关系[2,11]。模拟行人视野范围，构建局部地标与路径元素间的可视关系，表示路径上的行人可观察到该局部地标；模拟全局地标可视范围，构建全局地标与路径节点和局部地标间的可视关系，表示位于路径节点或局部地标附近的行人可观察到该全局地标。设V、E、L、P分别为数据库中的节点、弧段、局部地标和全局地标集合，sVi和eVi为组成弧段Ei的起始和结束节点。

1.2.1 局部地标可视关系 按顺序分别构建节点和弧段处的局部地标可视关系。对每个节点Vi，以其坐标为中心按一定的阈值dv为半径建立圆形的缓冲区，将其中与Vi间距离最小的局部地标Lj作为Vi的可视地标。如图1a，L1为V1的可视地标。距离设为d(Vi，Lj)，计算公式如下：

(1)

式中：(xv,yv)和 (xl,yl)分别为Vi和Lj的坐标。将Lj编号储存于Vi的可视局部地标编号字段中。

图1 可视关系构建

Fig.1Structureofvisualrelationship

构造弧段处的可视关系，本文将地标与弧段的位置关系分为弧段内和弧段外，如图1a中，对于弧段E1，L1为弧段外地标，L2为弧段内地标。具体构造方法如下：

(1)对每个弧段Ei，取出sVi、eVi，利用式(1)求得d(sVi,eVi)、d(sVi,Lj)、d(eVi,Lj)。

(2)若满足当d(sVi,Lj)>d(eVi,Lj)时d2(sVi,eVi)≥d2(sVi,Lj)-d2(eVi,Lj)或当d(sVi,Lj)

(3)计算由sVi、eVi和Lj构成的三角形的半周长p(Ei,Lj)，并用海伦公式和三角形面积公式求得地标距弧段距离h(Ei,Lj)。计算公式如下：

(2)

h(Ei,Lj)=

(3)

(4)若h小于一定的阈值he，则Lj为Ei的可视地标，将Lj地标编号储存于Ei的可视局部地标编号字段中，否则继续判断其他地标。如图1a，L2为E1的可视地标。

(5)若Ei内无可视地标，则认为sVi、eVi中距离节点最近的可视地标为Ei的可视地标。

1.2.2 全局地标可视关系 构造全局地标可视域需考虑全局地标的位置、角度和距离等属性。具体方法为：1)对全局地标Pi以坐标为极点，x正半轴为极轴，逆时针方向为正建立极坐标系。2)为Pi添加可视距离Sp、起始可视角度α、结束可视角度β，可视角度范围为[0°,360°]，此时可视域为扇形区域，若无可视角度限制，则可视域为圆形区域。3)判断Vj或Lk位置，若可视域为圆形区域，则算法与局部地标对节点可视关系的判断方法相同，若为扇形区域，则满足极径d(Pi,Vj)β)或γ∈[α,β](α<β)时，Pi为Vj或Lk的可视全局地标。如图1b，全局地标P1为节点V3和局部地标L3的可视地标。将Pi编号储存于Vj或Lk的可视全局地标编号字段中。

2 基于地标的空间位置描述方法

在地标可视关系的基础上，以路径元素和局部地标为描述对象，局部地标和全局地标为参考对象对其进行空间位置描述。行人对定量的距离难以有直观、准确的认识[1]，因此仅用方位关系表示描述对象位置。该方法具体步骤为：对空间方位关系进行定性描述，结合自然语言描述方法，生成描述词并组成描述短语。

2.1 方位关系定性描述

定性描述方位关系时需要考虑3个因素：参考框架、方向模型和方位词。绝对参考框架适合描述陌生环境中的方向，相对参考框架适合描述主体所感知到的方向[12]，因此分别用以上两类描述框架描述空间方向和行进方向。常用的方向模型有圆锥模型、投影模型和双十字模型等，本文采用金鑫等[13]提出的八方向模糊不均匀划分模型，该模型不是空间方向的硬性划分，符合人们的认知习惯[14]。在两种参考框架下描述八方向模糊区间时需要采用不同的方位词(表1)。绝对参考框架下的方位词记为方向描述词，相对参考框架下的方位词记为转向描述词。

表1 八方向模糊区间在不同参考框架下的方位词选取

Table 1 Choosing method of orientation words in eight-directions fuzzy intervals

[0，π6]，[116π，2π][π6，π3][π3，23π][23π，56π][56π，76π][76π，43π][43π，53π][53π，116π]绝对参考框架北东北东东南南西南西西北相对参考框架前右前右右后后左后左左前夹角(°)6030603060306030

2.2 空间方位的自然语言描述方法

采用绝对参考框架描述空间实体位置,根据描述对象和参考对象生成名称描述词，提取位置信息参数并通过计算确定方向描述词，按描述句法组成位置描述短语。具体步骤如下：

(1)以OT、OR表示描述对象和参考对象，名称描述词Name(O)表示空间对象O的名称。若O为地标，则Name(O)表示地标名称；若O为节点或弧段，则表示“路口”或“道路”。

(2)OT、OR均为空间点要素，若OT为弧段，则由其可视地标在弧段上的投影点表示。取出OT、OR坐标(xt,yt)、(xr,yr)，以OR为极点，正北方向为极轴，顺时针方向为正建立极坐标系，计算方向角θ，根据表1确定方向描述词，记为Dir(OT,OR)，表示OT相对于OR的方位。θ计算公式如下：

(4)

(3)Position(OT,OR)表示一个位置描述短语，{}表示描述范围，引入U表示方向描述词词缀，如“边”、“面”、“侧”等，I表示助词，如“的”。采用句法{Name(OR)+Dir(OT,OR)+U+I+Name(OT)}生成位置描述短语，实例：“图书馆西南侧的路口”、“校医院西北边的标本馆”。

3 引导算法

3.1 全局路径描述算法

算法在寻路过程开始前生成全局路径描述，帮助行人形成整体的路径概观。为使描述符合行人的路径表述习惯，引入目的地描述机制[15]，即提取路径的中继目的地，省略具体的引导过程[1]。为减少冗余的引导信息，按“绕过”和“经过”的途经方式将局部地标分类，对其进行途经地标描述。算法流程：将路径抽象为路径节点的可视局部地标序列，利用节点的可视全局地标对序列进行分割。提取中继目的地地标并使用途经方式判别算法判断其余地标途经方式。提取名称描述词和位置描述短语，结合相应句法模式生成途经地标描述和中继目的地描述两类NLRP动作单元，并组合为分段路径描述。最后将多个分段路径描述整合成为全局路径描述。

设V为路径节点序列，L、vP分别为V的可视局部、全局地标序列，lP为L的可视全局地标序列，SL为分割出的局部地标段，Dcp为全局路径描述，subDcp为分段路径描述,表2列出了相关句法模式和对应描述实例。算法具体步骤如下：

(1)输入V、L、vP、lP，初始化Dcp。

(2)利用节点可视全局地标对路径进行分割。标记Vi，初始化SL并将Li加入到SL中，随后搜索vP，若vPi+1=vPi，则认为Vi+1与Vi属于同一路径分段，将Li+1加入到SL中，否则分割结束。

(3)用判别算法判断地标的途经方式。设T为绕过的地标集合，BP为经过的地标集合，T和BP都采用哈希表存储，以保证元素唯一。算法步骤：初始化T，默认为经过的地标，将SL的值添加到BP中。对由Vi-1、Vi和Vi+1组成的路段使用Douglas-Peucker算法判断Vi是否为转向点，若Vi距Vi-1、Vi+1相连直线距离大于一定阈值d，则认为Vi为转向点。随后运用式(5)判断地标与路径位置关系[16]，若Li位于转向前后两条弧段的同侧，即T(Vi,Li)×T(Vi+1,Li)>0，则认为其为“绕过”的地标。如图2所示，L4为路段V0、V1、V2绕过的地标，其余为经过的地标。判断完成后，将Li添加到T中并从BP中删除。

T(Vi,Li)=(xl-xi)(yi-yi-1)-(xi-xi-1)(yl-yi)

(5)

图2 地标途经方式

Fig.2Passingwaysoflandmarks

(4)对SL进行途经地标描述。遍历T、BP，取出绕过和经过地标的名称描述词序列nName(T)和nName(BP)，并以顿号分隔。引入核心动词“绕过”和“经过”并使用表2中句法M1进行途经地标描述，随后将其附加到subDcp。

(5)对SL进行中继地标描述。取SL后的第一个地标Lj为中继目的地，以Position(Lj,lPj)表示中继目的地位置，并引入“沿”、“朝”、“向”等介词和“转”、“行走”等核心动词，分别用Prep和Verb表示[17]。利用句法M2进行中继目的地描述并附加到subDcp。若Lj、lPj地标名相同，则用Name(lPj)替代Position(Lj,lPj)。为避免下标溢出，结束路段的中继目的地为终点可视局部地标。

(6)将subDcp附加到Dcp。为保证描述语句符合自然语言习惯，在多个subDcp间加入“随后”、“然后”、“再”等连接词。若路径分段为全局路径的起始或结束则加入修饰起始或结束的非持续性动作单元，如“从Position(L0,lP0)出发”和“抵达终点”等，以保证Dcp的NLRP完整性[8]。

表2 引导信息的句法模式与描述实例

Table 2 Syntactic patterns and describable instances of guidance information

所属算法句法符号动作单元句法模式描述实例全局路径描述局部路径引导M1途经地标描述“绕过”+nName(T)+“，经过”+nName(BP)绕过食堂、体育馆，经过操场M2中继地标描述Prep+Position(Lj，lPj)+Verb向主楼西北侧的校医院行走N1节点定位VnP+Position(Vi，vLi)位于校医院西边的路口N2节点重定向Prep+Turn(Vi)+Verb向右转N3节点定向Prep+Position(Ei，eLi)+Prep+Name(vLi+1)+Verb沿校医院北边的路向标本馆行走N4弧段定位VnP+Position(Ei，eLi)位于篮球场东边的路上N5弧段定向Prep+Name(vLi+1)+Verb向体育馆行走N6弧段重定向“抵达/经过”+Name(vLi+1)+“前/后”，Prep+Turn(Vi+1)+Verb抵达体育馆前向右转经过体育馆后向左转N7纠偏Prep+Position(Vi/Ei，vLi/eLi)+Verb向学研大厦东边的路口行走

3.2 局部路径引导算法

算法在寻路过程中生成局部路径描述,为行人提供实时的引导。算法原理：使用缓冲区表示路径，如图1a中，设dv为圆形路口半径，he为路宽的一半。实时判断行人位置，若位于路径上，则提取对应名称、转向描述词和位置描述短语，结合相应句法模式生成由定位、定向、重定向三类动作单元组成的节点或弧段处的引导信息；若偏离路径，则搜索路径中距离行人最近的节点或弧段，当距离小于一定阈值时生成纠偏信息，否则视作彻底偏离路径并结束引导。寻路为动态的过程，因此局部路径引导的NLRP允许以持续性动作结束。本算法在位置更新时执行。

设V、E为路径节点和弧段序列，vL、eL为V、E的可视局部地标序列，d、h为当前位置与节点和弧段间的最短距离，di、hi为路径缓冲区参数，s为偏离后距路径元素的最近距离，w为偏离阈值，所用句法模式及描述实例见表2。具体步骤：1)输入V、E，获取当前位置。2)倒序搜索V，运用式(1)计算d。若d0则向右，反之向左，并使用向量夹角公式计算转角，根据表1相对参考框架下对应的方位词提取转向描述词Turn(Vi)，结合句法N2生成重定向动作单元。根据Vi后的弧段Ei和节点Vi+1及其可视地标eLi、vLi+1，提取转向点后一弧段的位置描述短语Position(Ei,eLi)和行走目的地的名称描述词Name(vLi+1)，结合句法N3生成定向动作单元。将以上生成的三类动作单元组合成为节点引导信息。调整V、E，删除Vi之前的节点和Ei之前的弧段。3)若当前位置不在任何节点中，倒序搜索E，运用点到直线距离公式计算h，若h

4 实验与结果分析

以北京林业大学校园为实验区域，在自主移动GIS平台AoGIS下，对本文所述方法进行编程实现。使用节点-弧段法表示道路，选取了18个全局地标和75个局部地标并构造可视关系。引导前采用Dijkstra算法规划路径。通过描述实验和行走实验验证方法的有效性和可靠性。

4.1 描述实验

通过描述实验验证全局路径描述信息的有效性。以北京林业大学1号楼为起点，11号楼为终点进行路径规划。由“Distance-to-Turn”算法(DTTA)生成的引导信息为:“从起点向正东方向出发，走30m，左转，走140m，右转，走250m，左转，……，走60m，到达终点”。由全局路径描述算法(GRDA)生成的引导信息为：“从银杏大道西边的1号楼出发，绕过1号楼，经过2号楼、3号楼，向田家炳体育馆南侧的绿缘公寓行走；随后绕过生物楼，向主楼西北侧的校医院行走；再绕过校医院、标本馆、加热站，向图书馆行走；……，向11号楼行走抵达终点”。通过对比发现，融合了地标的全局路径描述包含更多环境信息，其描述路径的方式更符合行人习惯。

如上文所述，引导信息中引导次数过多会对行人造成认知压力[11]。表3给出了在实验区域内选取的5组平均长度分别为198m、348m、600m、900m和1 150m的路径(每组5条)及其相关参数。DTTA的引导信息在转向点和终点处产生，因此随着路径长度的增加和决策点个数的增多，该方法的引导次数较多；GRDA算法利用全局地标分割路径，每个路径分段生成一次引导信息，因此路径长度和转向点个数对引导次数影响较小。上述结果表明，GRDA能在路径长度较长、转向点个数较多时，仍保持较低的引导次数，不会增加行人的认知压力。

表3 不同长度路径下的平均引导次数对比

Table 3 Comparison of average guidance time in different route length

平均长度(m)平均转向点数平均全局地标数算法平均引导次数1981．81．8DTTAGRDA2．81．83485．82．4DTTAGRDA6．82．46008．84DTTAGRDA9．84900105DTTAGRDA1151150126DTTAGRDA136

4.2 行走实验

采用行走实验验证局部路径引导的可靠性。通过GPS获取当前位置的WGS-84坐标数据，并将其转换为投影坐标用于计算。如图3，箭头表示路径方向。位于位置A时，引导信息为：“位于加热站北边的路上，向图书馆行走，抵达图书馆前左转”；从A步行至B，引导信息变为：“位于图书馆西南面的路口，向左转，随后沿图书馆西边的路向19号楼行走”；返回A，引导信息为：“偏离路径，向图书馆西南面的路口行走”；行走到位置C，提示“彻底偏离路径”，引导结束。实验结果显示，局部路径引导算法可以在路径中生成节点或弧段处的引导信息，在偏离路径或沿路径逆向行走时生成纠偏信息，距路径距离大于w(实验中设定为50 m)时结束引导。另外，每次位置更新时只生成单次引导信息，不会对行人造成认知负担。

图3 行走实验

Fig.3Walkingexperimentation

5 结语

本文提出的行人导航路径引导方法以地标为引导线索，通过构造地标可视域建立空间对象间的参考关系，并使用空间位置描述方法生成描述词和描述短语。在此基础上，使用全局路径描述算法生成全局路径描述，帮助行人形成整体的路径概观；使用局部路径引导算法生成局部路径引导信息，另外，还充分考虑到了行走方向的不确定性，进行偏离路径判断和纠偏引导。实验证明：1)全局路径描述信息符合行人寻路习惯并且不会增加额外的认知压力；2)局部路径引导信息可在寻路过程中实时为行人引路，并避免其偏离路径；3)两类基于NLRP的路径引导信息便于用户理解。综上所述，本文提出的方法能够生成符合行人认知习惯的路径引导信息，满足其寻路过程中的引导需求，具有一定应用价值。但全局路径描述的引导次数由途经全局地标个数决定。因此，如何在环境中选取数量、影响范围合理的全局地标，以达到最优引导效果，是今后需解决的问题。另外，不同地域、生活习性、文化背景下行人的空间认知习惯存在一定差异[12]，因此，探寻面向不同认知习惯人群的句法模式和信息展示方式，也是未来的研究方向。

[1] 赵卫锋,李清泉,李必军.空间认知驱动的自适应路径引导[J].遥感学报,2011,15(6):1180-1187.

[2] 张星,李清泉,方志祥.面向行人导航的地标链生成方法[J].武汉大学学报(信息科学版),2010,35(10):1240-1244.

[3]FURUKAWAH,NAKAMURAY.Apedestriannavigationmethodforuser′ssafeandeasywayfinding[C].Heidelberg:SpringerVerlag,2013.156-165.

[4]GOODMANJ,BREWSTERSA,GRAYP.Howcanwebestuselandmarkstosupportolderpeopleinnavigation[J].BehaviourandInformationTechnology,2005,24(1):3-20.

[5]KLIPPELA,TAPPEH,KULIKL,etal.Wayfindingchoremes——Alanguageformodelingconceptualrouteknowledge[J].JournalofVisualLanguagesandComputing,2005,16(4):311-329.

[6]KLIPPELA,WINTERS.Structuralsalienceoflandmarksforroutedirections[A].SpatialInformationTheory[C].Berlin:SpringerVerlag,2005.347-362.

[7] 李霖,毛凯,谭永滨.地标分层多粒度路径导引描述方法[J].测绘学报,2014(1):105-110.

[8] 刘瑜,高勇,林报嘉,等.基于受限汉语的GIS路径重建研究[J].遥感学报,2004,8(4):323-330.

[9] 王晓明,刘瑜,张晶.地理空间认知综述[J].地理与地理信息科学,2005,21(6):1-10.

[10] 龚咏喜,刘瑜,邬伦,等.基于带权Voronoi图与地标的空间位置描述[J].地理与地理信息科学,2010,26(4):21-26.

[11] 张星,李清泉,方志祥,等.顾及地标与道路分支的行人导航路径选择算法[J].武汉大学学报(信息科学版),2013,38(10):1239-1242.

[12] 余建伟,李清泉.位置感知计算中定位信息的自然语言描述[J].地理与地理信息科学,2009,25(1):10-13.

[13] 金鑫,耿海燕,高勇,等.空间方位关系在不同认知场境下的模糊性探讨[J].北京大学学报(自然科学版),2009,45(6):1025-1032.

[14] 郭继发,崔伟宏.八方向模糊不均匀划分及参考点位误差所致不确定性分析[J].遥感学报,2010,14(5):879-892.

[15] TOMKO M,WINTER S.Pragmatic construction of destination descriptions for urban environments[J].Spatial Cognition and Computation,2009,9(1):1-29.

[16] 张宏,温永宁,刘爱利.地理信息系统算法基础[M].北京:科学出版社,2006.22-23.

[17] 张雪英,闾国年,宦建.面向汉语的自然语言路径描述方法[J].地球信息科学学报,2008,10(6):757-762.

[18] 郑玥,龙毅,明小娜,等.多种空间关系组合的地理位置自然语言描述方法[J].地球信息科学学报,2011,13(4):465-471.

Route Directions Method of Pedestrian Navigation Based on Landmark

CHEN Yue-lu,WU Gang,CHEN Fei-xiang

(SchoolofInformationScience&Technology,BeijingForestryUniversity,Beijing100083,China)

In order to generate the route direction information that conforms to pedestrian cognitive habits,reducing the cognitive stress and inaccurate decision in process of way-finding,a route directions method of pedestrian navigation based on landmark is put forward by the article.Local landmarks and global landmarks are introduced and visual relationship among spatial objects is set up by the method.On this basis,descriptive words and descriptive phrases are generated by direction model and descriptive syntax.Before the start of way-finding,route was divided into segments by global landmarks,descriptive words and descriptive phrases were extracted from segments and NLRP action units were generated by connecting syntax patterns and then multiple action units were combined together as global route description.In the process of way-finding,extracting descriptive words and descriptive phrases in the basis of current position,guide information which was composed of location,orientation and redirect action units were generated by syntax patterns.When deviating from the path,the correction guide information would be generated.Experimental results showed that the route direction information generated by the method can meet user demand for route direction;in the meanwhile,any extra burden of cognitive would not be increased.It can accurately guide the pedestrian to reach the destination in real-time.The method has certain application value.

landmark;pedestrian navigation;route directions;NLRP

2014-05-27；

2014-07-12

地质矿产调查评价项目(1212011120436)；中央高校基本科研业务费专项基金项目(TD2014-02)

陈玥璐(1990-)，男，硕士研究生，主要研究方向为移动GIS应用、行人导航系统。*通讯作者E-mail：wugang@bjfu.edu.cn

10.3969/j.issn.1672-0504.2015.01.004

P208

A

1672-0504(2015)01-0017-06