旅游地图的自动绘制.doc

个人收集整理 勿做商业用途自动生成旅游地图摘要：旅游地图对旅游者到一个不熟悉的城市来说是很必要的，因为地图对路标和其它感兴趣的点都加亮使其可视化。然而，手工绘制地图是一种静态的表现手法，不足以适应个人旅游的需要和品味。在这篇论文里，我们提出了一种设计旅游地图的自动系统，可以选择并加亮对旅游者来说很重要的信息.我们的系统使用了自上而下基于视觉的图像分析和自顶向下基于网络信息提取的技术，来决定地图元素的显著程度。然后着重对最重要的元素生成地图,用多视角渲染的一个组合来加强街道和路标的可视化，制图的一般技术如使用简化、变形和平移来加强路标和降低相对不重要的建筑物。我们展示了若干自动产生的旧金山旅游地图并将它们与手工方法作对比。1 引言旅游地图对旅游者到一个不熟悉城市是必要的资源，因为地图对路标和其它点如博物馆、饭店、公园、购物街加亮使其在地图上可见。最有效的旅游地图是能展现出当前的信息，这样旅游者就能很容易找到他们感兴趣的地方.然而，设计和渲染这样的旅游地图是一个耗时的过程，因为需要熟练的地图设计技巧.而且，手工绘制的地图是静态的表现手法，不足以适应个人旅游者的需要和品味。兴趣点对每个人来说较好区分。独特的建筑物和环境特征可作为通用的路标来显示，一个旅游者可能对商店最感兴趣，而另一个旅游者可能想找最近的餐馆。在设计一幅地图时,对地图绘制者来说第一个改变是，对旅游者即将使用的地图决定地图上的元素的重要程度。旅游者通常采用步行和公共交通的组合方式从一个地方到另一个地方。所以，一个有效的旅游地图必须能提供充足的可视化路标和兴趣点，从而帮助旅游者快速识别他们当前的位置并决定到目标的最好路径。例如：地图绘制者利用多视角渲染来增强街道和路标的可见性。同样，他们用各种各样制图的一般方法来增强识别路标和重点突出地图上最重要的元素。所以,对制图者来说第二个改变是，选择渲染和制图一般方法的一个集合,增强最重要的路标和兴趣点同时降低或消除不相关的元素。在最近十年，数字地图很流行，比如有Microsoft Live（)、Google Maps()和Yahoo Maps（),城市通常是一个建筑物的永久状态，街道和建筑物可能被修整、创建、毁掉。这种数字地图和手工绘制地图相比，一个优势是对城市街道和建筑物的几何模型是连续更新的,所以通常反映的是最新的信息。然而，这些数字地图不足以说明生成旅游地图的两个主要改变并且还存在很多问题,包括：路标的低识别。数字地图通常省略建筑物或仅仅显示一部分。当用户选择路标的位置能用图钉加亮时，在没有进一步可视化信息的情况下对一个用户识别路标还是不可能的。没有背景信息.数字地图不提供背景信息，因为它们不加亮显示，而这些背景信息可以帮助用户在一个城市旅游时确定方位。低通用性。数字地图不产生一个城市中相对不重要的建筑物。所有的建筑物在细节上是处于同一水平，对旅游者过滤出他们需要的信息带来了困难，所以,这地图显示的过度复杂。在这篇论文里,我们提出了一个自动生成旅游地图的系统，并提前高亮显示两种主要变化，显著减少从目前数字地图继承的问题。我们系统的输入是一个城市的几何模型,包括街道、水池、公园和建筑物（带方本说明）。用户能最优化说明他们感兴趣地方的类别（如:餐馆、商店).我们的系统使用自上而下基于图像分析的方法和自顶向下信息抽取的技术来决定地图元素的重要程度。然后使用多视角渲染的一个组合方法来加强街道和路标的可视化，使用制图的一般方法如简化、变形和平移来突出路标的显示而弱化相对不重要的建筑物，生成一幅对最重要元素突出显示的地图。2。旅游地图设计为了设计更有效的旅游地图，我们使用了Agrawala和Stolte August2001的方法，从分析城市纹理特征的先前工作开始Lynch 1960；Sorrows and Hirtle 1999，同时收集了最好的手工设计地图Southworth and Southworth 1982；Tufte 1990；Holmes 1991和制图本Kraak and Ormeling 1996。从这些分析中,我们提取出一幅旅游地图最重要的元素，并识别出一组有效渲染旅游地图的原理.2。1重要信息在城市图像（Kevin Lynch1960)这本经典书里，定义了五个元素来代表城市的纹理特征：路标、路径、分区、节点和边界。事实上,这些元素有大量的属性使其在导航任务和对一个新环境的总体认识上很有必要。路标：大的实物在环境中通常作为参考点。而我们关注的焦点是建筑物，其它的对象如桥和山也能作为路标。路标的特征原理是在周围环境背景中是唯一的并且是容易记住的。Sorrows and Hirtle1999 记为路标还可以分为三个子类:认知路标是语义上的，因为文化和个人的意义不一样。例如，一个著名作家的一套公寓是文化意义，而一个特别的餐馆可能就是个人意义。视觉路标是通过外表特征如颜色或形状可区分的建筑物结构路标因空间位置是容易让人记住的，例如在决定街道交叉点、汽车站点或城镇广场位置在设计旅游地图时应包含建筑物的这三个子集.认知路标表示了一个地方的特征或反映了观光者的个人兴趣，而视觉路标和结构路标对导航是很有必要的.路标为不熟悉的地方导航提供了额外的背景,能使用户通过周围的环境定位自己Deakin 1996；Michon and Denis 2001。路径。道路,人行道，运输线，运河，铁路等都是人们通过环境自由聚集、交互和移动的路径。在这个工作里，我们关注道路，因为它在城市导航中占主导地位。分区。一个城市的有些地区通过建筑类型、建筑用处、居民类型有共同的可识别特征，就像唐人街、意大利区、大使馆区就是分区的例子。节点。在很多城市，公园、城镇广场、海滩和繁忙的十字路口点是人们趋向聚集的地方.这些节点对旅游者来说特别有用，是和本地居民联合在一起的好地方。边界.很多城市包含像河、城墙、道路等元素，它们可作为连续地区的中断点.例如边界可作为一个地方到另一个地方的边线或两个连在一起的地方分隔线。边界通常被定义为城市元素的第四个要点.例如一条高速公路可以作为一个界线，也可以作为一个重要的路径。我们的系统对边界不明确定义，但作为城市的第四个要素。2。2绘制多视角地图绘图通常使用多观测点和透视的方法来加强地图上重要元素的可视化。通常采用对街道和地面正面图、俯视图结合的方法，对建筑物采用斜投影视图。用自顶向下的观点对地面透视图绘制缩小、变形、消除有助于用户理解道路网的布局。制图者对路标选择偏透影或透视图投影的方法可以使建筑物的正面清晰显示。偏投影和视图(或远景)投影有互补的优势。偏投影出建筑物的大小和形状不依赖于视点的距离。Agrawalw etalJune 2000指出对图像平面作水平方向的偏投影可以保证建筑物的真实形状和有助于比较大小和面积。但是，缺少远景的线索将使建筑物表现的不真实。对建筑物用远景投影避免了这个问题，但在比较建筑物大小和面积时却带来了问题.一般化地图绘制者采用多种绘制地图的一般方法包括简化、平移、变形和选择来增强地图的清晰度并突出显示地图上最重要的信息，并在地图的各物体间保留空间的位置关系Monmonier 1993；MacEachren 1995；DiBiase et al.1992.在这个工作里，我们考虑将这些一般化方法应用于手工绘制地图上的建筑物并展示这些技术是怎样加强地图可用性的。简化.地图绘制者用简化将相对不重要的建筑物弱化或者说是减少建筑物规模的复杂度，从而避免渲染人工制品。平移。艺术家通常加宽道路来显示一个未知区域的路径.结果是建筑物可利用的空间被限制。常用的技术是平移建筑物以避免和邻近的街道和建筑物重叠。变形.地图绘制者通常要增加重要路标的和减少不相关建筑物的大小。移除。手工地图通常移除了不太相关的建筑物来减少地图的复杂度，并获得较重要建筑物的空间。3。系统概况我们开发出一套自动生成旅游地图的系统,并基于第二部分设计原理。在图2中,我们的系统的输入数据组成了一个城市的完整几何模型，包括带纹理的3D建筑物和路的几何模型，并且每条路被分类为一条街道，主干道、坡或高速公路。一幅交通图将街道分成四个离散的水平.平面图将城市分割成水路、停车场和地面.最后，在4.1部分会作解释,我们的系统会从提取关于建筑物分类（博物馆、餐馆等）的分割信息的大量网页中作解析，用户可以对每一个建筑物作排列。从这些数据中,我们的系统可以预处理建筑物的轮廓和街区边界,通过道路将街区划界。我们对建筑物的轮廓是通过作三角形面片作投影和描出像素空间外轮廓来决定的。我们计算街区边界也是通过对路网作三角形面片和应用街区分割的方法。在预处理后,我们就能识别出路标、道路、区域、节点和每个元素的重要程度(第4部分）。为了生成旅游地图,用户指定城市、城市的地区、个人兴趣的路标类别(如餐馆、商店等)。然后系统设计并渲染出一个含盖指定区域并加亮显示个人兴趣点的旅游地图。(第5部分)。4。计算重要性我们的系统能从城市基本数据中构造一组特征,并自动提取路标、道路、区域、节点和他们相关的重要性。按照Sorrows and Hirtle1999的方法,我们将特征划分成三个类别:语义、可视化、结构化。语义特征通过基于网络信息提取技术的方法来计算，可视化和结构化特征通过分析城市的地理、纹理和图像的地平面来计算。每个特征和一个分数关联，分数高表明重要性高。我们计算出每幅地图元素特征分数的加权和来衡量重要性。用户必须选择他们感兴趣的路标分类，他们也能手动设置每个特征的权重.我们提供一组默认权重的实验选择。Raubal and Winter2002 and Klippel and Winter2005提出一种基于特征识别路标重要程度的相似方法，他们假设语义特征是给定的输入部分。而我们是提取网页中的语义信息。我们也可以考虑地图的五个元素(路标、路径等)互相影响的重要性和独立计算每个元素的重要性有什么样的关系。4.1路标路标特征工作是基于Appleyard1969上的,他作了一份调查，问人们一条路旁记住的建筑物是什么。通过这份调查，他得出的结论是一组凸路标特征正是我们用到系统中的。语义特征识别语义特征要求有文化和路标对个人意义的知识。当这样的语义不仅仅来自城市数据将不能决定它的含义，因特网提供了大量语义结构化数据的收集，从这里我们可以提取出正确的特征.最近大量的技术利用网络提取图片处理中的背景语义Snavely et al.2006;Hays and Efros 2007.同样Tezuka and Tanaka2005运用文本挖掘技术从未组织的网络文档中去提取路标信息。我们扩展了这个思想从三个旅游相关的网站上解析路标信息.正如图3中显示的，我们提取出下面的属性：名字,纬度/经度位置,地址，区域，类别(旅游吸引力，博物馆,商业设施，商店，餐馆等)让用户排序（0-5个等级)。当旅游地图不包含路标位置时，我们的系统调用Google Map的接口来定位。我们使用纬度/经度位置和每一个路标关联并和城市数据集中的建筑几何模型保持一致。最后,我们利用用户通过三个网站对路标进行排序得到语义分数.图6显示出一个地区最重要的语义路标。可视化特征构建唯一的可视化特征(颜色、形状等）可以和一个局部地区出现的其它建筑物区分开来并容易被当作路标来记住。我们区分三种对建筑物有显著影响的可视化特征的类型：外表颜色、形状复杂度和建筑物高度。我们首先定义一组在建筑物中量化当前这些特征的特征，然后解释怎样将这些特征关联到分数。外表颜色。很多建筑物容易让人记住是因为它们的颜色和周围的建筑物不同。正如图4显示,为了提取一个建筑物中墙的颜色，我们首先将建筑物的几何模型分成屋顶和墙三角形面.一个建筑物三角形片面i和标准的ni被标记为一面墙，如果ni0。5或其它则表示的是屋顶。下面，对所有的墙的三角形面在纹理地图上应用Felzenszwalb2004的基于颜色的分割算法。在纹理中分割出的每段我们通过平滑误差和噪声得到的平均颜色来作为近似颜色.最后,为了避免纹理中的黑影，我们将每段纹理的外表颜色设置为最亮的颜色，只能在段的面积比整个墙的面积大5时才这样考虑。颜色值是由LAB颜色空间中的L部分组成。形状复杂度.很多建筑物是简单规则的长方形，也有很多不是这样的标准形状，越突出越能作为路标。我们用两个特征来测试形状的复杂度。第一个特征是测试建筑物休积界限可能是真建筑物休积的比率Mirtich 2005。第二个特征是测试角度差异。图5描述了这两种形状复杂特征的差异。建筑物高度.高建筑物从远处就很容易看见.所以我们使用建筑物高度作为可视化特征。在可视化特征的环境中，建筑物仅仅变成了个和周围建筑物区分的路标。为了计算每个可视化特征的分数，我们用一种由Nothegger et al2004提出的方法来估计偏差:Score=，其中x是个体测试，med(x)表示的是中间值。为了计算中间值,我们定义局部邻近的建筑物包括50米以内所有的建筑物。图6给出了一个区域最重要的可视化路标。结构体特征很多认知心理学的学习表明，旅游者极易在路的交汇点和城镇广场来定位一个新城市Denis et al。1999；Lovelace et at。1999；Michon and Denis 2001.这些建筑物的空间位置和导航很相关，因此可以通过结构体路标的类型来识别.交汇点的建筑物.建立一个重要的交汇点比其它的都重要。我们对每一个交汇点计算所有道路在那个交汇点重要程度的分数，然后求和（可以参见4.2计算路的重要程度)。这样，我们就知道了哪些道路和地方是重要的交汇点。最后，我们在交汇点和建筑物之间用高斯分布来得到它们之间的重要程度。对于每一个建筑物，我们从附近的交汇点累积权重。广场周围的建筑物.为了能识别在城镇广场周围的建筑物，我们首先提取出广场的重要程度，这个会在4.4部分作解释.用广场的重要程度来衡量建筑物的重要程度和用交汇点一样.图6显示出了一个地区最重要的结构体路标。4。2道路我们用语义和结构特征来定义道路的重要程度。当对于所有地图语义特征都是一样时，结构特征就取决于用户选择的感兴趣点。语义特征以前在选择道路的重要程度上,关注的是从拓扑学和几何学间接推导出语义的重要性Mackaness and Reard 1993；Thomson and Richardson 1995；Thomson and Richardson 1999；Jiang and Claramunt 2004.相比而言，我们的系统是直接从输入数据和网络上得到语义信息.分类。道路通常根据它们的用处被分成离散的类。例如,在我们的输入数据里，每一条道路被分为街道、主干道、动脉道、陡坡和高速公路这几类。每一类的各自分数分别为0.25,0。5,0。75，1。0,1.0。交通流量.频繁移动对一条道路的重要程度有很大的影响Lynch 1960。主要的线路如在旧金山的Bay Bridge or the Presidio ParkWay是智能地图的关键。我们通过交通地图获得关于路的信息（），通过路的使用小时数将路分成四个离散水平.一条路段的交通分数被归范化成交通水平。结构特征我们特别设计结构特征去选择道路，这样更容易导航，同时让旅游者选择到感兴趣的地方去。我们的道路被表示成多叉线，这样我们计算每一线段的重要分数。段的重要程度暗示了它对附近路标的影响程度,在4.1部分有说明。路标的邻近性.作为旅游者，他们感兴趣的最近的道路是很重要的，因为可以帮助导航.为了计算这个特征，我们首先估计出用户选择的路标作为感兴趣点(餐馆、商店）的语义重要性，这个在4。1部分有描述。然后通过用高斯函数算出路的样本和路标位置的距离,再得到每条两米之内的路段语义的重要程度。对每一条路的样本点，我们累积附近路标对它的影响。最后，对每条路的每个线段，我们计算出子样品的平均分数。连接路标的道路。旅游者通常都会到城市的不同景点看看,这对加强路之间的连接是有帮助的。我们通过控制API从虚拟地球地图（http:/dev。4。3划区语义特征为了识别每个路标的语义特征，我们提取出路标附近的区域(可以参见4.1)。分区通常没有精确的边界，所以我们就简单的去识别区域中心，通过搜索附近高密度路标的位置。我们通过迭代计算路标点的平均位置，在每次迭代中,必要的时候,我们可以不使用极端值。4.4节点语义特征有些节点,如广场、公园和湖也可以考虑作为路标,我们通过解析旅游网站提取出它们来识别路标语义(参见4.1).然而这个提取过程只提供节点的一个坐标位置。为了计算出广场的2D范围，我们扩展周围空白区的位置。同样我们在背景纹理中使用基于颜色的种子填充来记定2D范围.节点的分数,作为路标语义的特征，从输入站点显示来看符合一般用户等级。5。绘制5.1多视角地图多视角地图在描述道路和描述一个单视角建筑物的正面部分突出可见时有很大优势.为了创建多视角地图，我们对路标用正交投影和透视投影来绘制地平面。正交投影如图7所示，正交投影用指定投影线的两个参数和来定义。在我们的应用中，图像平面和水平面平行，控制用透视法缩小绘制建筑物正面的数量,而控制建筑物正面是否可见。因为图像平面相对水平面来说是正交的，建筑物可以通过街道正确定位-正交投影不会改变建筑物的定位。我们对每个建筑物建立了不同的正交投影，这样建筑物的正面对附近的路面是可见的。当建筑物正面面向多条街道时，我们将建筑物正面面向最重要的街道。更具体地来说，我们计算每个建筑物d向量的偏角来表示最邻近道路的方向。如图7所示，我们从建筑物足迹的坐标fi(i=1M）抽样，去掉边界组成分割片sj（j=1N)和标准化的nj.然后d=，这是分割片标准化的权重和。权重用下面的公式来表示：W(fi,sj)=kj(1)，kj是路段sj（参见4.2路的重要性)的重要性分数，D(fi,sj)是建筑物足迹fi到sj边界的距离，maxD（f，s)是计算所有的足迹点到边界段.所以，邻近足迹点的边界段有最高的权重。最后我们用d来计算投影参数=arctan and =-c我们用来定位街边的建筑物正面的可见性，用在度量d的距离，用规模因子c来控制透视法缩小绘制的数量。5。3非真实感图形绘制地图绘制者通常通过轮廓线和减弱建筑物的颜色的方法来加强路标。轮廓线含盖了形状信息，并可以帮助观测者更好识别建筑物的几何模型。在两个邻近的平面角大于/4的三角形中可以通过轮廓线识别边缘。建筑物纹理中的人工制品如阴影部分会对观测者视角引起歧义并使建筑物很难识别。为了消除这个影响,我们的系统用一致的颜色来绘制墙和屋顶。在提取出墙和屋顶的颜色后，正如4.1中提到,我们将墙的颜色变深让它更容易区分，加亮屋顶的颜色来使建筑物显得更亮。而绘制非路标建筑物时由让它显得暗一些。5。4标注为了使旅游地图可用并可以导航，我们必须标注出地图中重要的元素包括路标、道路、节点（湖、公园、广场)和小区.自动标注方位和线的特征在自动地图设计中是个学习问题Lmhof 1975；Edmondson et al。1996;Agrawala and Stolte August 2001;Vollick et al。2007。通常的方法是寻找地图中可能要标注的空间并找到最优的布局。我们使用的是Agrawala and Stolte的模拟退火算法August 2001。我们标注地图元素经历四个步骤，从节点开始，然后是路标、街道和分区，这是一个连续的顺序。用这种搜索方式减少搜索空间的维度并显著提高收敛.我们的系统扩展以前的标注技术，包括地图元素重要价值的布局得分函数。这种方法保证最重要元素以最优化的方式被标记，而相对不重要的元可能被远处的取代或移除.6。结论许多用我们的系统生成的旅游地图例子在图1、16和17中给出显示.输入数据由旧金山的6227个建筑物组成。在左边的图中加利福尼亚和Clay St是不可见的.在扩宽道路和产生建筑物后，这两条街变得可见，而且所有的街区结构是被保留的。图17是超市周围建筑物的特写图,我们对建筑物用正交投影来加强对着街道的那一面。在这个例子中，超市街在那个区域重要程度最高所以总是可见。我们标注出路标的语义，使其它建筑物半透明。和存在的地图作比较。在图1、14和16中,我们将已存在的数字地图和旧金山手工绘制的旅游地图和用我们方法生成的地图作比较。不像数字地图直接通过卫星图显示出3D建筑物的几何模型，我们选出和旅游相关的信息再绘图，这样更容易识别路标的3D视图。另外，我们使用通用的制图和多视角制图方法来减少地图的复杂性，加强重要路标的显示有助于导航。我们的地图不用和专家手工绘制的地图匹配质量，我们的地图有适应城市变动和用户兴趣的优势。手工图必须给出所有观光者感兴趣的路标，这样通常会造成建筑物混乱.混乱也会使标注很难读.相比而言，我们的地图只加强用户感兴趣路标的显示，因此更清晰。时间信息我们的旅游地图生成系统包含了很多处理过程，最后是基于用户的兴趣而产生的。在处理过程中，我们计算建筑物、道路、分区和节点的语义、可视化和结构特征。我们对建筑物采用了部分预处理、修正、分解，同时对道路正交投影得到独立的权重。因为这些计算在我们的数据集里只执行一次,所以我们的焦点不是优化它们，它们都可以在Matlab中实现。很多预处理过程是需要花几分钟，有的会更长.最慢的是计算语义路标间的路线，花24小时。查询这些路线是取决于虚拟地球服务的。我们的地图创作接口导入这些预处理数据并允许用户修改权重、设置视角参数和路标的兴趣类别。为了显示地图,我们生成建筑物,多视角绘图，然后标注地图。当街区包含很少的路标建筑时将花费几秒的时间,当包含多路标时将花费几分钟。多视角制图是实时时间.标注相对的慢，是跟标记的数量成比例的。图16包含了成百上千个标记需花40分钟，而图15仅花几秒钟。然而，我们相信使用特定的数据结构可以加快重叠计算的空间，GPU加速可以显著减少标记时间Hartmann et al.2005；Ali et al。2005。7。总结和展望我们介绍了一个自动生成旅游地图的综合系统。我们的系统通过举例说明网络数据挖掘、感知导航的几何模型、图像分析和提前可视化技术是怎样组合的，最后得到了一个每天可以使用的自动生成旅游地图的有效工具。我们的方法最大的的亮点是用户自定义性。用户可以根据他们对一个城市观光的偏爱和意向构建他们自己的地图。和手工地图相比,我们的系统利用实时更新的信息，这样能动态适应，例如道路关闭的时间和博物馆或餐馆开放的时间。在这篇论文里,我们是打印地图，未来的一个直接工作就是在移动设备上产生交互作用的地图。如Zipf2002建议在用户偏爱、文化不同和GPS定位的个人地图更具交互性。自动生成旅游地图对这样的交互性和个人化可以提升效力。8.致谢我们感谢Eyal Ofek对我们的这个工作提出的建议方向。我们同时也感谢Bill Chen和微软虚拟地球对城市几何模型数据提供的方法。多视角循环的闭合解决方案是来自于James Obrien的谈话。这个工作被微软虚拟地球部分支持。Alfred P.Sloan基金会和自然科学基金会授权CCF-0643552。