随着国内城市化的迅速发展,各省市、地区都在进行旧城改造、城市建设,城区面貌变化日新月异,国际、省际、城际间的交流日益加深,人口流动增多,因此出现“寻址”困难的问题。目前,文本作为最常见的输入语言,广泛应用在百度地图、谷歌地图等主流地图中,实现地图寻址过程。但是在寻址过程中,人们利用文本表述不明时,常常通过绘制简单草图的方式进行辅助表达,这一过程有助于人们在大脑中形成简单的空间场景,将大脑中的空间场景与实际场景进行一一对应,最终对目标地址进行定位和找寻。因此,手绘草图作为一种直观的用户交互“语言”,利用其空间关系相对不变性,将手绘草图中的空间对象与矢量地图中相应的空间对象进行一一映射,这种映射关系的建立就是地图匹配的过程,也是实现地图寻址和定位的核心步骤。目前,地图匹配的主要过程是通过对空间对象的空间相似度进行度量,从而判断两空间对象是否匹配。常见的空间相似性度量包括距离、面积、形状、位置、语义、拓扑和方向等,其中拓扑相似性常作为粗匹配的度量用在地图匹配的过程中,目的是减少匹配候选集、提高匹配效率,然后利用距离、面积、形状、位置等几何相似性特征实现地图的精确匹配。由于手绘草图不具有标准的地理参考坐标,因此无法获取空间对象的准确的空间地理信息。由于人们对空间认知会产生不同程度的畸变使得绘制的空间对象的形状和位置都是模糊的,因此,只能利用以拓扑关系为主的空间关系作为约束条件,实现手绘草图与矢量地图的匹配。论文的主要工作概括为以下几点:(1)总结了矢量地图匹配和手绘草图匹配的国内外研究现状,提出了基于拓扑特征的手绘草图与矢量地图匹配的研究思路;(2)分析了手绘草图认知畸变的特征,得出手绘草图具有空间关系不变的结论,基于这个特征可以实现手绘草图与矢量地图的匹配。将手绘草图中提取的空间对象进行归纳,可分为点、线、面三种类型,详细阐述了基于这三种类型间的空间关系及其对应的不同粒度的表达模型,为匹配过程奠定了基础;(3)详细阐述了图的两种存储方式:邻接表和邻接矩阵,概括分析了它们的优缺点后,从而得到邻接矩阵能够提高图搜索效率的结论。因此手绘草图和矢量地图利用邻接矩阵进行原始空间关系存储,将所有潜在匹配点对构建全局空间关系矩阵和某一匹配点对对应的局部空间关系矩阵。其中,对局部空间关系矩阵进行详细的分析后,进行了量化计算,并将计算结果用于矩阵质量评价中;(4)本文将局部空间关系矩阵的量化计算结果作为禁忌搜索过程中适应度函数计算,取适应度函数计算后值最高的对应匹配点对作为下一步的匹配方向,并添加到匹配序列中,然后进行迭代计算,直至将所有匹配点对搜索完成。本文从单一约束关系和多约束关系两方面进行了匹配算法和空间关系质量的评价,验证了将空间关系矩阵矩阵与改进禁忌搜索算法相结合的匹配算法在手绘草图与矢量地图匹配过程中的可行性与有效性。