寻路是人们日常生活中频繁遭遇的现实问题,与民众的生活息息相关。作为基于位置的信息服务的特殊形式,导航服务为用户规划最优路径并生成与这些路径相对应的路径指示。本研究中,路径指示的跟随者是行人。地标作为现有导航系统中最重要的导航信息,起到显著的方位标识和路径引导作用。基于地标的行人导航服务的首要任务是引导用户在寻路过程中以最低的实际消耗和认知消耗到达目的地。地标是面向人类心理空间模型的外部参考点。行人导航系统中,地标的重要性主要体现在以下几个方面:1)通常人们利用地标描述位置和路径,基于地标的位置表达和路径引导方式显得更为自然;2)陌生环境中,人们是通过显著地标来确定方向的,在路径指示中融入地标不仅可以支持空间定向,而且还能减少不确定性和降低寻路决策错误的概率;3)识别显著的地标可以确保行人跟随的路径的正确性和导航系统工作的正常性,路径上的地标越多,其质量越高。近年来,车载导航已较为成熟,相比之下面向行人的导航问题则日益突出:(1)缺少符合空间认知的位置概念的数字化表达技术通常导航系统将用户的空间位置信息映射到电子地图上,来描述用户在现实环境中的地理位置。然而,实际上人们通常是基于地标描述一个位置,而不是利用导航地图上显示的当前位置来描述。目前位置表达相关的研究中缺乏一种将人类认知的位置语义进行数字化表达的技术。(2)忽略了行人的空间认知对路径指示中地标选择的影响,而且无法有效捕捉行人的注视点以预测实际朝向用户在利用地标作为寻路过程中的空间参考点之前,正确识别环境中的地标是导航任务能否成功的关键。在现实环境中,行人通常需要依赖视觉搜索寻找导航系统预先指定的地标。然而,现有面向行人导航的路径指示中的地标数据主要通过地标的显著性计算模型和在线地标资源获得,这些方法忽略了行人的空间认知对于地标选择的影响。此外,现有行人导航主要采用电子罗盘、磁力计、手机内置相机等确定行人的实际朝向。事实上,行人的实际朝向取决于注视点。然而,现有方法无法有效捕捉注视点以预测行人的实际朝向。(3)路径指示中提供的地标图像和方向指示无法适应行人位置和朝向变化相比汽车的行驶,行人的步行具有更大的灵活性,这种灵活性主要体现在:1)不受马路约束;2)朝向变化较大(步行过程中可以任意改变朝向)。而现有路径引导信息中地标方位和导航方向的指示无法适应行人位置和朝向的变化,这将导致路径选择错误的概率增加。(4)缺少规避复杂决策点的路径规划方法现有研究提出了在路径计算问题中使实际消耗和认知消耗最小化,例如:1)面向车载和行人导航的最少转弯路径和最简单路径等;2)面向车载导航的规避复杂决策点(其复杂度由节点个数衡量)的路径计算方法。然而,很少有研究针对基于地标的行人导航服务发展一种规避复杂决策点(其复杂度是通过现实场景中的地标数据定量表达)的方法。本文针对上述问题提出了相应的解决方案,并通过实验研究进行了相关验证:(1)本文提出并测试了一种形式模型以捕捉人类认知的位置概念,该模型借鉴机器人学的指纹概念,即一个位置可用其周围的地标进行描述。为了真实的测试面向人类认知的位置也可以用指纹描述,本文提出了一种基于指纹计算位置的算法,并设计了现场实验捕捉这些位置和这些位置对应的指纹。结果表明,具有相同指纹的所有空间位置的组合可以用于描述人类认知的位置。(2)首先以位置描述认知实验结果和前人的研究为基础,提出了一种顾及可视性、接近性和离心率的地标数据选择规则,并给出了具体的选择算法流程。然后,提出了一种基于启发式图像插值法的行人朝向预测模型。该模型利用了图像的匹配程度以及行人和全景图之间的位置关系进行预测。其中,图像的匹配程度是在统计意义上根据匹配的SIFT(scale-invariant feature transform:尺度不变特征变换)特征的百分比求得。朝向预测模拟实验结果表明,本文提出的方法显著优于忽略了行人与全景图之间的位置关系的朝向预测方法。(3)本文以位置描述认知实验结果和前人的研究为基础,利用街景视图服务商提供的全景数据,提出了一种适应行人位置和朝向变化的地标图像提取方法。然后,实现了地标方位和导航方向的定性表达。最后,采用C++编程语言实现了基于地标的自适应路径指示自动生成模拟程序。模拟实验表明,本文提出的算法可以提供以行人为中心、适应行人位置和朝向变化的动态路径指示生成服务。(4)本文提出了一种规避包含难以识别的地标的复杂决策点的方法。具体而言,本文首先发展了一种基于街景视图服务商提供的全景图中提取的地标的尺寸和文本的复杂决策点确认模型。然后设计了一种遗传算法,并利用该算法实现了规避复杂决策点的路径规划。在该遗传算法中,距离也是计算目标之一。案例研究的结果表明,本文设计的遗传算法具有一定的灵活性,而且该算法规划的最优路径在规避复杂决策点的同时,还能保证路径行程距离最短。本文提出的路径规划方法对于构建一个包含其它用户群体偏好(如规避分支数量较多的决策点)的完整行人导航系统至关重要。