面向行人空间认知的路径描述自动生成算法与模拟实验

周 沙,甄 文 杰,王 润,方 芳

(中国地质大学(武汉)信息工程学院，湖北 武汉 430074)

面向行人空间认知的路径描述自动生成算法与模拟实验

周 沙,甄 文 杰,王 润*,方 芳

(中国地质大学(武汉)信息工程学院，湖北 武汉 430074)

路径描述是人类心理空间表征外化的方式之一，与人们的日常生活息息相关。针对目前行人导航无法满足行人空间认知偏好多样性的问题，首先通过认知实验验证了参与者在确定自身位置时选取地标所考虑的主要因素为可视性和距离；然后结合行人的步行方向发展了一种基于地标可视性、地标与行人之间的距离以及步行方向的地标选取模型，并以该模型为基础提出一种以行人为中心的定性路径描述自动生成算法；最后，采用C++编程语言实现了基于路径描述自动生成算法的模拟程序。模拟实验表明，该算法能根据行人步行方向和位置的变化，实时调整相应的路径指示信息。因此，该文提出的算法可提供以行人为中心的路径描述动态生成服务，以满足行人空间认知偏好多样性的需求。

地标；行人导航；路径描述；空间认知；算法

0 引言

随着城市交通的发展，人们对出行信息的需求越来越高[1]。面向行人的路径描述是空间认知学科和导航技术领域研究的热点问题之一，受到了国内外相关学者的广泛关注[2-7]。实际上，比起几何描述，几乎绝大部分的路径描述倾向于采用地标[8,9]。目前，基于地标的路径指示中，地标影像及地标相对于观察者的方向关系的表达是固定不变的[10]，这导致行人需要通过主观判断确定真实地标的方位。地标判断时间受到行人实际视角的影响，且判断时间较长容易造成认知压力[11]。另外，地标的选取方法主要采用Klipple等提出的地标显著性计算模型[12]，这种方法以地标为主要研究对象，忽略了路径描述面向的是行人这一客观事实，未顾及行人空间认知规律的影响；且该方法依赖不切实际的数据集[13]，即无法直接获取与地标显著性相关的数据源(视觉特征、结构特征、语义特征等)。

典型的GIS提供了附加的数据源，如与实体相关的信息：建筑名、建筑物的边界坐标、兴趣点等。Dale等结合真实的GIS数据与自然语言生成方法，提出了基于地标的路径指示自动生成方法[7]，但是该方法面向的是车载导航。相比汽车的行驶，行人的步行具有更大的灵活性，不受马路约束且方向变化较大(步行过程中可以任意改变方向)。另外，随着移动GIS的发展，行人经常要查询自己所处的位置[14]并与所处真实环境做比较。因此，设计符合行人空间认知的路径描述并通过现有GIS数据源自动获取地标信息是实现以行人为中心的导航服务的关键。

本文设计了一种以行人为中心的路径描述自动生成算法，主要聚焦于辅助行人确定自身的位置；最后根据设计的算法实现了路径描述自动生成模拟程序。

1 基于地标的路径指示与认知实验

1.1 基于地标的路径指示

目前，行人导航系统中路径指示的形式包括语言指示、图形指示[15]、图像指示和混合指示等，混合指示较为常见。其中语言指示首先提示行人当前的行走方向，且该方向与图形指示(方向箭头)相对应，然后提醒行人沿此方向行走会观察到某地标，行人需要判断路径指示信息中显示的地标是否与真实地标相匹配。

在智能导航终端普及的情况下，行人的位置可实时获得并能够与地图进行比对，从而找到行人所处位置附近的地标。现有的路径描述方法虽然给出了与地标相关的信息(如名称、距离等)，但是没有考虑给出的地标对于行人是否有意义(如由于角度和距离的原因，行人可能无法识别路径指示中的地标)，为行人认知环境带来了障碍。具体存在的问题有：1)图像中显示的地标影像角度是固定的，当行人视角与该影像提供的视角不一致时，行人无法迅速确定自身所处位置，容易产生认知压力；2)由于认知偏好的多样性，行人是否会使用现有路径指示的地标确定自身所处的位置是不确定的。因此，本文从空间认知的角度入手解决这两个问题。

1.2 空间认知实验

地标在路径描述中的主要作用是辅助行人确定自身所处位置和前进方向，本研究聚焦于前者。因此，本文设计了位置描述实验，来确定参与者利用地标描述自身所处位置时的一般规律，从而将其运用到路径指示的地标选择中。

召集15名中国地质大学信息工程学院的学生进行现场空间位置描述实验，实验区域为中国地质大学图书馆周围3条人行道(AB、BC和CD)，边长分别为65 m、85 m和65 m，每条人行道包含6个测试点(如图书馆北侧的A、①、②、③、④ 和B)(图1)。实验过程中，15名参与者随机被分成3组，每组(5人)分别被分配到3条不同的人行道上，每位参与者都被引导到相应的人行道上，描述该人行道上5个不重复的抽样点，且描述顺序由实验者随机选取，最后，位置描述结果由参与者自己记录。

图1 现场调查区域Fig.1 In situ survey area

参与者选取地标时主要考虑地标是否可见以及地标与自身的距离。实验结果中一共收集了75条位置描述，提到的地标个数为131个(包含相同的地标)，其中：1)有31(41.3%)条位置描述中只包含1个地标，且一条描述中最多包含3个地标；2)所有地标对于参与者均可见；3)130个地标(99.2%)与参与者之间的距离小于50 m。另外，不同的参与者在描述相同的测试点时会采用相同或不同的地标。这说明由于认知偏好的多样性，人们对相同位置的描述具有不确定性。

2 路径指示的自动生成算法

2.1 地标选取规则及模型

为了生成对于行人有意义的路径指示信息，即行人容易感知到的地标信息。根据位置描述认知实验结果以及行人步行的方向，本文制定了地标选取规则及其实现过程：

规则1：地标对于行人可见。在没有遮挡物的情况下，以寻路者为中心、r为半径的圆形缓冲区内的地标对于寻路者而言均为可见地标。如图2所示，OA间没有遮挡物，且A点(地标的边界点)在观察者(位于O点)的可见区域内，故包含A点的地标对于观察者可见；而B点被遮挡物遮挡，C点虽未被遮挡但其不在可见区域内，故该地标上的其他点均对O点不可见，因此包含B点和C点的地标对于行人不可见。

图2 可见地标Fig.2 Visible landmark

图3 行人与地标之间的距离和方位角Fig.3 Distance and azimuth between pedestrian and landmark

规则2：地标与行人之间距离较近。计算行人与可见地标的所有可见边界点的距离，选择其中最短的距离作为行人与地标之间的距离。图3中，距行人所处位置O点距离最近的地标边界点为A点，因此行人与地标之间的最短距离则为D。另外，图3中的θ为行人与地标之间的方位角，由行人的步行方向与OA(行人当前位置和距行人最近的可见地标边界点之间的连线)之间的夹角组成。行人的步行方向为行人当前位置O与前一个GPS点P之间的连线。

根据以上规则本文将地标的显著性作为地标的选取标准：

(1)

其中:S表示地标的显著性；V=1表示地标对于行人可见，V=0表示不可见；WD(式(2))和Wθ(图4)[16]分别为地标与行人间的距离权重和相对方向权重。

(2)

由于行人所处的环境中可能不只存在一个地标，故本文选取最显著的地标作为路径描述中的地标，如式(3)所示：

Smax=max(S1,S2,…,Sn)

(3)

路径指示中地标选取的流程如图5所示：

图5 地标选取流程Fig.5 Flow chart of landmark selection

2.2 面向行人空间感知的路径描述

指向手势是行人较容易感知的方向指引，可以有效地引导行人到达目的地，故为了符合行人的空间感知，并降低行人寻路时的认知压力，本文生成的路径描述算法给出了地标相对于寻路者的实时相对方向。日常生活中的路径描述是通过自然语言表达的，这种方式对于行人更容易接受。因此本文参考文献[16]将不同的角度归类为不同的定性方向描述(图6)，从而实现了方向的定性表达。

图6 方向的定性描述Fig.6 Qualitative descriptions of direction

另外，距离是路径描述中需要考虑的重要因素。目前的路径指示在行人距离地标较远时就提示距地标的距离，行人需要分散注意力去思考地标的方位、距离等因素，这将导致行人产生认知压力[13]。故本文给出的路径描述中，用于行人确定自身位置的形式为{地标名，“位于”，相对方向，距离}(如图书馆位于右前方30 m)，其中地标必须对于行人可见，且两者之间的距离小于50 m(根据1.2节的实验结果设定)。由于本研究主要聚焦于利用地标辅助行人确定自身所处位置，故在本节和算法实现部分不涉及与前进方向指示相关的知识。

3 算法实现及模拟实验

本文利用C++编程语言实现了面向行人空间认知的路径描述模拟程序，以中国地质大学西区的部分区域作为实验区域，程序运行结果如图7所示。图中的箭头表示行人的步行方向，箭头右上方的信息为提示行人当前位置的路径指示，如“物探楼位于右前方7 m”。虽然图7a和图7b 中行人的步行方向相同，但由于位置不同，故生成的路径描述有所不同。

现实生活中，因为视角、个人偏好等原因，依据此方法选择的地标对行人而言不一定显著；而且由认知实验可知，行人不只采用一个地标描述自身所处位置，这种情况下，行人可以通过当前局部环境中对于其更有吸引力的(一个或多个)地标实现自身定位。但是，如果同时显示多个地标信息，容易出现信息冗余的情况，不符合路径描述的简洁性原则。因此，本模拟程序只在路径指示上显示最显著的地标信息(也可以采用语音提示的方式)，可见区域内的其他地标信息作为辅助信息，为行人提供位置判断的依据。图7右上角的列表(刷新按钮的上方)为行人当前位置周围所有可见且与该位置距离小于50 m的地标，以及这些地标与行人之间的方位和距离信息，该列表中的地标信息可以提示行人路径指示信息中地标附近的其他地标。例如，当路径指示中提到图书馆西北角处的交叉路口时，行人也可以通过该交叉口附近的地标信息(足球场、图书馆等)确定自身当前所处的位置。

从上述模拟结果可以看出，本文提出的算法可以根据行人步行方向和位置的变化调整相应的路径指示信息。因此，该算法可以实时地为行人提供位置信息，具有一定的灵活性。

图7 路径描述模拟结果Fig.7 Simulation results of route descriptions

4 结语

本文面向行人空间认知，通过认知实验验证了行人在确定自身位置时，选取地标所考虑的主要因素，据此提出了地标选取的规则，设计了以行人为中心的路径描述自动生成算法。模拟实验表明，本文提出的算法不仅可以实现传统的路径描述方法(在固定的位置提供路径描述)，而且还能提供以行人为中心的动态路径描述生成服务，以满足行人认知偏好多样性的需求。以行人为中心，基于行人的实际位置和步行方向，描述行人视野范围内的地标，是减轻行人认知压力、提高导航效率的有效途径。但是，本文没有通过志愿者测试实际生成的路径描述是否比传统的更加有效，这将是下一步的工作。

[1] 李清泉,萧世伦,方志祥,等.交通地理信息系统技术与前沿发展[M].北京：科学出版社,2012.

[2] 陈玥璐,武刚,陈飞翔.基于地标的行人导航路径引导方法[J].地理与地理信息科学,2015,31(1):17-22.

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

[4] 王剑,龙毅,颜言,等.基于自然语言路径描述的地图空间认知研究[J].测绘科学,2012,37(3):38-40.

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

[6] FANG Z X,LI Q,ZHANG X,et al.A GIS data model for Landmark-based pedestrian navigation[J].International Journal of Geographical Information Science,2012,26(5):817-838.

[7] DALE R,GELDOF S,PROST J P.Using natural language generation in automatic route description[J].Journal of Research and Practice in Information Technology,2005,37(1):89-105.

[8] DENIS M,PAZZAGLIA F,CORNOLDI C,et al.Spatial discourse and navigation:An analysis of route directions in the city of Venice[J].Applied Cognitive Psychology,1999,13(2):145-174.

[9] MICHON P E,DENIS M.When and Why are visual landmarks used in giving directions?[A].Spatial Information Theory[C].Springer Berlin Heidelberg， 2001.292-305.

[10] DUCKHAM M,WINTER S,ROBINSON M.Including landmarks in routing instructions[J].Journal of Location Based Services,2010,4(1):28-52.

[11] ZHANG X,LI Q,FANG Z,et al.An assessment method for landmark recognition time in real scenes[J].Journal of Environmental Psychology,2014,40:206-217.

[12] KLIPPEL A,WINTER S.Structural salience of landmarks for route directions[A].Spatial Information Theory[C].Springer Berlin Heidelberg,2005.347-362.

[13] RICHTER K F,WINTER S.Landmarks:GIScience for Intelligent Services[M].Cham,Switzerland:Springer,2014.

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

[15] DIZAJI R N.Towards More Adaptive Pedestrian Navigation Systems[D].International Institute for Geo-information Science and Earth Observation,2009.

[16] BARTIE P J,MACKANESS W A.Development of a speech-based augmented reality system to support exploration of cityscape[J].Transactions in GIS,2006,10(1):63-86.

An Automatic Generation Algorithm of Route Description for Pedestrian Spatial Cognition and Simulation Experiment

ZHOU Sha,ZENG Wen-jie,WANG Run,FANG Fang

(CollegeofInformationEngineering,ChinaUniversityofGeosciences,Wuhan430074,China)

Route descriptions are the externalization of human mental spatial representation,and are so common in our daily life.However,the existing route descriptions are insufficient to satisfy the diversity of pedestrians′ cognitive preferences,such as generate route descriptions based on properties of landmark but not on pedestrians′ cognition.Several studies show that landmarks play an important role in route descriptions,hence,landmark selection is a key element for automatic generation algorithm of route description.In this paper,the main factors (i.e.,the visibility of landmarks and distances between landmarks and test positions) that effecting landmark selection are firstly verified through an in-situ cognitive experiment,then the landmark selection model,considering these two factors and the heading directions of pedestrians,is proposed.Based on the model,an automatically generated algorithm of pedestrian-centered qualitative route descriptions is devised.For the purpose of implementing the automatic generation algorithm for route descriptions,a simulation program is developed by Clanguage.The simulation results indicate that the proposed algorithm can adjust route instructions in real time,as the heading directions and the locations of pedestrians change.Traditional navigation systems provide route descriptions at pre-set locations.In contrast,the algorithm proposed in this paper could provide a dynamic generating service of pedestrian-centered route descriptions,which compliances the diversity of spatial cognition preferences of pedestrians.

landmarks;pedestrian navigation;route description;spatial cognition;algorithm

2015-12-13；

2016-03-11

国家自然科学基金项目(41371422、41201385、41301426、41301427、41501433)

周沙(1985-)，男，硕士，主要研究方向为行人导航理论与应用。*通讯作者E-mail：runwang_cug@163.com

10.3969/j.issn.1672-0504.2016.03.004

P208

A

1672-0504(2016)03-0019-04