地标分层多粒度路径导引描述方法

李 霖，毛 凯，谭永滨

武汉大学 资源与环境科学学院，湖北 武汉 430079

1 引 言

路径导引是导航与位置服务领域重要研究内容，是人类活动和日常生活的一个基本组成部分。路径导引是一个空间认知过程，也是建立在空间认知基础之上的空间关系推理过程。文献［1］将路径导引过程分为3个认知阶段，依次是当前环境认知、最优路径选择和概念转换结果（语言或图像）输出。路径导引描述通常由一系列连续的连接点（junction）组成。连接点被定义为一个二元组〈description，instruction〉，其中description是对空间位置的描述（如前方100m、环岛第3出口等），instruction表示在该空间位置采取的行动（如右转、转出等）［2］。依次转弯 （turn－by－turn）路径导引方式就是对路径计算结果中的每一个连接点依次输出，而对于一条复杂的路径结果，输出全部的路径导引描述会非常冗长复杂，增加人在寻路过程中的认知负荷和记忆负荷。文献［3］对区域环境的熟悉程度不同提出了4种寻路模式：熟知者、半熟知者、探索者、辅助寻路，讨论了寻路决策与地标之间的关系。地理信息的语言文字描述，在一定程度上对地理，概念的理解总存在一定语言上的模糊性［4］，对熟悉周边环境的本地人而言，基于地标的描述方式更加符合人们的认知习惯，地标作为位置信息的载体，对于安抚情感和保证寻路决策的正确性有很大作用［5］。基于地标的路径导引描述成为当前导航技术领域研究热点之一。

基于地标的路径导引描述的关键在于研究基于导航语义的地标参考空间位置描述方法。文献［6］认为定性位置（qualitative location，QL）是目标对象与其他特征的相对参照位置，正是通过未知特征与已知特征之间的空间关系来描述或者获得关于目标对象的空间位置。文献［7］提出一种基于地标的定性参考（landmark based qualitative reference，LBQR）系统，通过将Voronoi图与地标相结合，实现定性空间的位置描述，但该方法的应用依赖一个假定：各地标显著度是等价的，这与实际情况有一定差距。文献［8］对LBQR进行了改进，考虑到地标显著度对定性空间范围的影响，提出加权Voronoi图与地标的空间位置描述，但该方法仅以校区为范围在单一的尺度下进行研究，并未考虑知识是有粒度的［9］，对空间现象的认知表现为从总体到局部、从概略到细微、从重要到次要的层次顺序［10］，并且不同的任务对数据尺度的要求不同［11－12］，多粒度的描述方法则能更好地处理路径表达的不确定性。总体上，上述研究局限于空间中各自孤立、离散的位置的描述，而并未考虑在驾驶导航环境下，位置描述有序性的特点。基于此，本文试图针对不同尺度的地标认知空间完成基于导航语义的多粒度的形式化建模，设计更符合人们认知习惯的路径导引描述方法。

2 多粒度路径导引描述

2.1 候选地标数据集

文献［5］从景观的角度提出构成城市的5个基本要素：道路、边界、区域、节点、标志物。文献［23］将地标定义为环境中唯一的或者与邻近相比具备显著性的特征体。文献［13］根据功能性将地标分为两类：定向地标和定位地标。定向地标具有相当的知名度，主要应用于空间知识的表达和共享，承担定向的作用，其不一定分布于规划的路径附近；定位地标主要应用于寻路过程中的位置指引或反馈，承担定位的作用，通常沿着规划的路径周边分布。文献［14］根据对人们寻路决策的影响将地标分为决策地标、潜在决策地标和沿途地标3类。在导航语义下，独立于寻路者之外的地理参考元素都可能因为视觉外观、位置分布或功能特征而作为获选地标，如道路及其附属设施同样具备定位或定向功能，亦可作为候选地标对象，又如交叉口、立交桥等在路径导引过程中影响到决策结果。

综上考虑本文候选地标数据集构建步骤如下：① 选择导航数据库中的POI数据集和道路附属物为数据源；② 对路径规划的结果进行分析，确定路径规划的节点和主要形点，并以此作为输入，对数据源进行缓冲区分析；③ 将分析的结果即作为候选地标数据集。

2.2 导航地标显著度

文献［15］以建筑物为研究对象，从视觉、语义和结构3个方面研究对地标的显著度影响。文献［24］在此基础上进行了改进，引入了可视性参数，认为对于特定路径上下文来说，如果地标无法或难以通视（如遮挡情形），那么显著度也势必受到影响。导航地标显著度（Sf）可由以下公式计算

式中，ωv，ωs，ωt＞0且Σω＝1；Sv表示视觉特征；Ss表示语义特征；St表示结构特征，Sa表示通视程度；ωv、ωs、ωt分别表示视觉、语义、结构的权重系数。

视觉特征Sv定义为大小、形状、颜色等外部特征的度量，主要反映视觉上与周围环境的差异程度。在驾驶导航环境下，视觉特征对于使用者来说更为重要，因此也是本文研究的重点。本文中视觉特征值是通过模拟驾驶试验获取，该试验是建立在两点假设基础上：① 视觉特征的地标在视域范围内是可见的；② 地标的视觉特征值与其在视域范围内出现频次相关，可认为出现频率越高视觉特征值越大，反之亦然。建立视觉特征值Sv与地标出现频次f（x）函数关系如下式

式中，xmin、xmax分别为样本中地标出现频次的最小值与最大值。

结构特征St定义为空间布局等效用特征的度量，主要反映个体对整体贡献的差异程度。对于车载导航而言，地标的结构特征主要表现为定向作用，距离道路越近的地标结构特征越高，反之，距离道路越远结构特征越低。为了计算的方便，本文建立结构特征值St与地标到道路中心线投影距离dprj的映射关系，如下表所示。

表1 投影距离dprj与结构特征值St映射Tab.1 Mapping of dprjand St

语义特征Ss定义为文化、历史、特色等内部特征的度量，主要反映属性上与周围环境的差异程度。但是在导航过程中，由于使用者在短时间内中难以迅速判别地标的语义特征，因此语义特征对导航地标显著度的影响在这里本文不作进一步讨论。

基于上述分析，导航地标显著度的计算公式为

式中，ωv，ωt＞0且Σω＝1。

2.3 多层加权Voronoi图

从理论角度来讲，多粒度分析提倡通过不同的分辨率或尺度，对地理数据中出现的知识进行认知以及探索。在日常生活实践中，人们的空间认知和空间行为大多与尺度相关的。有研究表明，地标作为空间认知过程中的重要参照物，也往往表现为分层的空间认知结构［10，16］。文献［17］根据影响范围的不同，将地标分为局部地标和全局地标，并提出了视域空间的概念，本文借鉴这种思想，并进一步细化将城市地标由大到小划分为5个级别：城市级、区域级、街区级、街道级、视域级，具体描述如表2所示。

表2 城市地标分级Tab.2 Levels of city landmarks

另一方面，地标对城市空间的影响符合空间相互作用理论，即地标对周围空间的影响力与地标的显著度成正比。本文将地标显著度定义为权重，引入加权 Voronoi（weighted Voronoi，WV）来解决这一问题。位于加权Voronoi图多边形中的每个点到该多边形地标点的距离与该点到相邻多边形地标点的距离之比小于两地标点的权重之比（如图1所示）［18］。

图1 常规Voronoi图与加权Voronoi图Fig.1 Voronoi and WV

综合以上因素可知多层加权Voronoi图是建立分层地标参考系的基础之上，故本文采用多层加权Voronoi图实现空间剖分，具体实现方法如下：

（1）按照文献［19］中提出的迭代法，对候选地标数据集L进行分层处理，可得到每一层地标集合记作Li，i∈N。

加权Voronoi图的算法实现有栅格法和矢量法，出于模型表达及计算效率等因素考虑本文采用矢量法［20］构造加权Voronoi图。

2.4 基于分层地标的路径导引描述

路径计算的结果通常是以首尾相接、连续的弧段来描述，记作

为了描述的方便，将Rs称作弧段路径。对于第i层，将加权Voronoi图Vi与弧段路径Rs求交，根据公式（4）即可得到第i层地标路径

式中，T（）表示以地标为中心的泰森多边形。

考察公式（5）的几何意义，对于中每一个地标，与其邻近地标li（li∉）相比，与弧段路径Rs距离最近，这一结果符合认知习惯，即在显著度相似的条件下，距离人越近的地标越容易被关注。在建立分层地标参考系之后，本文以简化的方式生成多粒度路径导引描述，即在对应层级下将集合中的地标顺序输出，形如

在实际应用中，在获得各层级地标路径之后，通过进一步定性和定量的空间方位计算，可转换为更容易接受的多尺度自然语言描述［21］，因为不是本文讨论重点，这里不作进一步展开。归纳起来，算法描述如下

图2 算法流程图Fig.2 The flow of the algorithm

3 试验设计及结果

城市街景是以影像的方式对城市道路及其周边环境的真实记录与再现，包含了传统地图所不能表现的空间语义，代表着地球实际的物理状况，是带有与人们生活环境相关的社会、经济和人文知识的 地 球 全 息 图 （knowledge based GIS）［22］。本文在武汉公益地图网站（2010年3月更新）上进行模拟驾驶试验，以间隔15～20m的步距进行地标采样，记录每个全景影像采样点视距内可辨识的地标对象，累计采集可视POI 717个。从公信度较高的谷歌地图数据源（2011年更新）上采集地标及POI共计1442个，以此作为试验样本数据。

试验选取了武汉市洪山区珞瑜路鲁巷至武汉天河机场路段，横跨武昌、汉阳、汉口三镇，全长约43.5km。通过试验计算得出 “中南大酒店”、“黄鹤楼”、“武汉长江大桥”等地标从街景上可辨认次数均超过20次，视觉特征值Sv均大于0.8，也就是说在视觉特征更为明显，其中，“卓刀泉立交桥”、“武汉长江大桥”、“江汉桥”等地标由于其附着于道路上，相较于“黄鹤楼”、“群光广场”、“中国电信湖北公司”等地标距离道路更近，与道路的结构关系更显著，结构特征值St均为1。将导航地标的视觉特征值Sv和结构特征值St代入公式（3）计算显著度Sf。

接着试验按照上文所述步骤，分别以地标的经纬度和显著度作为加权Voronoi图的发生点的坐标和权重构造多层加权Voronoi图，计算结果如图3所示。其中图3（a）表示大尺度下加权Voronoi图，沿途经过卓刀泉立交桥、黄鹤楼、武汉长江大桥等城市级地标；图3（b）和图3（c）分别表示区域级和街区级中等尺度下计算结果，为了方便对比表示，图3（c）是图3（b）的局部放大；图3（d）表示街道级小尺度下计算结果，与图3（c）相比可以看到街道级地标个数明显增多，剖分图形更加细化。

最后试验将导航规划的路径与各级加权Voronoi图空间求交，以得到相交的加权泰森多边形，相交加权泰森多边形的发生点即是所求的结果地标。如此逐级计算进而得到各级路径导引地标集合。再根据实际应用需要，将集合中的地标按照行进方向顺序输出，即可生成由小到大不同粒度的路径导引描述信息。

以楚天卢酒店到群光广场路段为例，大尺度描述为“楚天卢酒店（经过）卓刀泉立交桥（到达）群光广场”，通过“卓刀泉立交桥”（Sf：0.631 1）这一地标的引入，形成路径导引的整体态势；在小尺度下，补充表达了“鲁广人行天桥”（Sf：0.438 8）、“武体人行天桥”（Sf：0.563 1）、“卓刀泉立交桥”（Sf：0.631 1）、“测绘科技大厦”（Sf：0.565）、“君宜王朝大饭店”（Sf：0.594 2）等地标，路径导引信息得到进一步细化。在长距离（如从“鲁巷广场”至“天河机场”）路径导引的描述亦可采用此方法。试验表明，导航地标显著度一定程度上决定了导航语义下地标多尺度分布特征，而多粒度的描述方式符合从粗到细的空间认知规律，能够满足不同详细程度信息的应用需求。大尺度的导航地标序列能够以简洁的方式快速表达导航路径概况，中小尺度能够表达更为详细的途经信息，使得寻路过程更为明确。

图3 试验区分级加权Voronoi图Fig.3 Hierarchy weighted－Voronoi maps in experimental area

经过实地行走测试，试验结果中单个地标在视域范围内可辨认度、持续性以及各地标之间承接的连贯性等方面与实地行走体验基本一致。为了对试验结果进行进一步验证，随机调查了6位武汉本地出租车司机，其中武昌出租车（鄂A XL1＊8、鄂A XP1＊9、鄂A XX0＊2）司机3位，汉口出租车（鄂A XR0＊9、鄂A XH5＊5、鄂A XL9＊9）司机3位。调查问题“请问鲁巷广场到天河机场会经过哪些地方”、“还能再详细一点么”。在6位司机的答复中 “卓刀泉立交桥”、“中南大酒店”、“黄鹤楼”、“武汉长江大桥”、“江汉桥”、“青年路”、“天河机场”等地标出现率均超过83.3%；“湖滨花园酒店”、“广埠屯电脑城”、“街道口”、“大东门”、“古琴台”、“武胜路家乐福”、“长江大酒店”、“金盾大酒店”、“航空路”、“省电信”、“机场路立交”出现率在50%～83.3%之间；其余地标出现率均低于50%。除个别地标因本地俗称或个人偏好引起差异外（如有两位司机认为“古琴台”和“江汉桥”在方位表达上是一致的，“广埠屯电脑城”比“君宜王朝大饭店”在方位表达上更符合本地习惯），调查结果与试验结果基本一致。

4 结 论

基于分层地标的多粒度路径导引描述方法，对导航语义下不同尺度的地标认知空间进行划分，通过将地标显著度与多层加权Voronoi图的空间剖分相结合，实现多粒度的路径导引描述。该方法可以根据周边环境、沟通对象和实际场景提供不同粒度的、符合人们认知习惯的描述结果，能有效地增强导航寻路知识的传递和共享能力，对于导航与位置服务应用具有实际意义。本文主要研究对象是基于点状地标的计算和建模，线状和面状地标可在此基础上进一步扩展。此外，地标的语义特征、方位朝向等其他因素对地标显著度评价的影响还有待进一步的研究。

［1］ DANIEL M P，DENIS M.Spatial Descriptions as Navigational Aids：A Cognitive Analysis of Route Directions［J］.Kognitionswissenschaft，1998，7（1）：45－52.

［2］ TVERSKY B，LEE P.Pictorial and Verbal Tools for Conveying Routes in Spatial Information Theory：Cognitive and Computational Foundations of Geographic Information Science［M］.Berlin：Springer Verlag，1999：51－64.

［3］ XIA J C，ARROWSMITH C，JACKSON M，et al.The Wayfinding Process Relationships between Decision－making and Landmark Utility［J］.Tourism Management，2008，29（3）：445－457.

［4］ LI Lin，ZHU Haihong，WANG Hong，et al.Semantic Analyses of the Fundamental Geographic Information Based on Formal Ontology：Exemplifying Hydrological Category［J］.Acta Geodaetica et Cartographical Sinica，2008，37（2）：230－235.（李霖，朱海红，王红，等.基于形式本体的基础地理信息语义分析［J］.测绘学报，2008，37（2）：230－235.）

［5］ KEVIN L.The Image of the City［M］.Beijing：Huaxia Publishing House，2003：150－151.（凯文·林奇.城市意象［M］.北京：华夏出版社，2003：150－151.）

［6］ YAO X，THILL J C.Spatial Queries with Qualitative Locations in Spatial Information Systems［J］.Computers，Environment and Urban Systems，2006，30（4）：485－502.

［7］ WANG X，LIU Y，GAO Z，et al.Landmark－based Qualitative Reference System［C］∥25th IEEE International Geoscience and Remote Sensing Symposium （IGARSS 2005）.Seoul：IEEE，2005：932－935.

［8］ GONG Yongxi，LIU Yu，WU Lun，et al.Locality Description Based on Multiplicatively Weighted Voronoi Diagram and Landmarks［J］.Geography and Geoinformation Science，2010，26（4）：21－26.（龚咏喜，刘瑜，邬伦，等.基于带权Voronoi图与地标的空间位置描［J］.地理与地理信息科学，2010，26（4）：21－26.）

［9］ DENG Min，LI Zhilin，CHENG Tao，et al.Rough－set Representation of GIS Data Uncertainties with Multiple Granularities［J］.Acta Geodaetica et Cartographica Sinica，2006，35（2）：64－70.（邓敏，李志林，程涛，等.多粒度的GIS数据不确定性粗集表达［J］.测绘学报，2006，35（2）：64－70.）

［10］ AI Tinghua，CHENG Jianguo.Key Issues of Multi－scale Representation of Spatial Data［J］.Geomatics and Information Science of Wuhan University，2005，30（5）：377－382.（艾廷华，成建国.对空间数据多尺度表达有关问题的思考［J］.武汉大学学报：信息科学版，2005，30（5）：377－382.）

［11］ TIMPF S，VOLTA G S，POLLOCK D W，et al.A Conceptual Model of Wayfinding Using Multiple Levels of Abstraction［J］.Lecture Notes in Computer Science，1992，639：348－367.

［12］ ZHENG Nianbo，LU Feng，LI Qingquan.Dynamic Multi－scale Road Network Data Model for Navigation［J］.Acta Geodaetica et Cartographica Sinica，2010，39（8）：428－434.（郑年波，陆锋，李清泉.面向导航的动态多尺度路网数据模型［J］.测绘学报，2010，39（8）：428－434.）

［13］ PRESSON C C，MONTELLO D R.Points of Reference in Spatial Cognition：Stalking the Elusive Landmark［J］.British Journal of Developmental Psychology，1988，6：378－381.

［14］ LOVELACE K L，HEGARTY M，MONTELLO D R.Elements of Good Route Directions in Familiar and Unfamiliar Environments.in Spatial Information Theory：Cognitive and Computational Foundations of Geographic Information Science［M］.Berlin：Springer Verlag，1999：65－82.

［15］ SORROWS M E，HIRDE S C.The Nature of Landmarks for Real and Electronic Spaces.in Spatial Information Theory：Cognitive and Computational Foundations of Geographic Information Science［M］.Berlin：Springer Verlag，1999：37－50.

［16］ TOMKO M，WINTER S，CLARAMUNT C.Experiential Hierarchies of Streets［J］.Computers，Environment and Urban Systems，2008，32（1）：41－52.

［17］ MONTELLO D R.Scale and Multiple Psychologies of Space［M］∥Spatial Information Theory：A Theoretical Basis for GIS.Berlin：Springer Verlag，2009：312－321.

［18］ LI Shengquan，HU Peng，YAN Weiyang.Delimitation of Central Cities Influenced Regions Based on Weighted－Voronoi Diagram ［J］.Engineering Journal of Wuhan University，2004，37（1）：94－97.（李圣权，胡鹏，闫卫阳.基于加权Voronoi图的城市影响范围划分［J］.武汉大学学报：工学版，2004，37（1）：94－97.）

［19］ WINTER S，TOMKO M，ELIAS B，et al.Landmark Hierarchies in Context［J］.Environment and Planning B：Planning and Design，2008，35（3）：381－398.

［20］ GAHEGAN M，LEE I.Data Structures and Algorithms to Support Interactive Spatial Analysis Using Dynamic Voronoi Diagrams［J］.Computers，Environment and Urban Systems，2000，24（6）：509－537.

［21］ YING Shen，LI Lin，GAO Yurong，et al.Natural Language Description of Multi－scale Spatial Orientation in LBS［J］.Geomatics World，2008（1）：28－33.（应申，李霖，高玉荣，等.LBS中多尺度空间方位的自然语言描述［J］.地理信息世界，2008（1）：28－33.）

［22］ LI Deren，HU Qingwu.Digital Measurable Image Based Geo－spatial Information Service［J］.Geomatics and Information Science of Wuhan University，2007，32（5）：377－380.（李德仁，胡庆武.基于可量测实景影像的空间信息服务［J］.武汉大学学报：信息科学版，2007，32（5）：377－380.）

［23］ SIEGEL A W，WHITE S H.The Development of Spatial Representations of Large－scale Environments ［J］.Advances in Child Development and Behavior，1975（10）：9－55.

［24］ KLIPPEL A，WINTER S.Structural Salience of Landmarks for Route Directions［C］∥Proceedings of International Conference on Spatial Informational Theory.Elliottville：COSIT，2005：347－362.