（模式识别与智能系统专业论文）交通矢量地图自动生成平台的研究和发展.pdf

中闭科学技术人学顺l ：论艾 摘要 g p s 全球卫星定位技术在车辆导航领域有着广泛的应用，作者所在的科大 g p s 实验室一直关注该领域的发展。随着我国道路建设的发展和数字地球、数字 城市的提出，车辆导航市场的需求越来越大。车辆导航离不丌精确、完整的交通 矢量地图，在这样的背景下，作者于读研期间，致力于交通矢量地图的自动生成 平台的研究和发展工作。 本论文以该平台的研究为背景，详细论述了交通矢量地图的生成过程。对于 其中的关键技术，如栅格地图的矢量化，地理数据库的规划，地理信息的涂加等 等，本文均给出了详细的解决方案。 该平台提供了地图校正功能：即我们可以根据g p s 车辆轨迹对矢量地图进 行校f 。因此我们可以利用此系统，快速( 中等城市只需3 天) 、准确的生成矢 量地图。相比国内外通用的矢量地图生成平台，它具有成本低、效率高的优点。 现有的校f 算法主要是针对矢量地图中的旋转和放缩误差，采用仝川次性 变化的方法，对地图进行校正。这一算法存在着明显的不足：即无法校f | i 地图中 的非线性误差，无法达到局部最优的校证效果。针对这些不足，作者从交通矢量 地图的基本特征出发，深入分析矢量地图的刚络拓扑结构，提出了离散非线性的 校f 算法，并应用于合肥、成都等城市的地图校正中，取得了良好的效果。 关键字：g p s ( 全球卫星定位系统) ，g i s ( 地理信息系统) ，乍辆导肌，欠 量地图，网络拓扑，离散块，映像。 i i ! 塑型兰丝查生兰堡：! 堡兰垒! 璺! 坠 a b s t r a c t g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) t e c h n o l o g i e sa r ew i d e l yu s e di n t h ef i e l do f v e h i c l en a v i g a t i n ga n du s t c ( u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g yo fc h i n a ) g p s l a b h a sk e p te y e so nt h ed e v e l o p m e n to ft h i sf i e l df o ry e a r s a l o n gw i t ht h er o a d d e v e l o p m e n to fo u rc o u n t r ya n dt h eb r o u g h tf o r w a r do fd i g i t a le a r t ha n dd i g i t a lc i t y ， t h em a r k e to fv e h i c l en a v i g a t i n gi sg r o w i n gf a s t t h ev e h i c l en a v i g a t i n gc a l ln o tw o r k w e l lw i t h o u tap r e c i s ev e c t o rm a p i nt h i sb a c k g r o u n d ，t h ea u t h o rh a sb e e nd e d i c a t e d t ot h er e s e a r c ha n dd e v e l o p m e n tw o r ko ft h et r a m c v e c t o r - m a p sa u t o m a k ep l a t f o r m d u r i n gh i sg r a d u a t es t u d y b a s e do nt h er e s e a r c ho ft h i sp l a t f o r m ，t h i sp a p e rd i s c u s s e st h ep r o c e d u r et o m a k et r a f f i c v e c t o r - m a pi nd e t a i l a i m e da ts o m ek e yt e c h n i q u e s ，s u c ha st h e v e c t o r i n g t o g r i dm a p ，t h el a y o u t t o g e o g r a p h i c a ld a t a b a s e ，t h ea d d i n go f g e o g r a p h i c a li n f o r m a t i o n ，t h i sp a p e rg i v e st h es o l u t i o n si nd e t a i l t h i ss y s t e mp r o v i d e st h ef u n c t i o no fp r o o f r e a d i n gm a p w ec a np r o o f r e a dt h e v e c t o rm a pa c c o r d i n gt ot h eg p sv e h i c l et r a c k s ow ec a ng e tap r e c i s ev e c t o rm a p r a p i d l yu s i n gt h i ss y s t e m c o m p a r e dw i t h o t h e rd o m e s t i ca n da b r o a dt m i v e r s a l p l a t f o r m st h a t a r ed e v e l o p e dt om a k ev e c t o rm a p s ，t h i ss y s t e mh a st h ea d v a n t a g eo f l o wc o s ta n dh i g he f f i c i e n c y t h ec u r r e n tp r o o f r e a d i n ga l g o r i t h ma d o p t st h eo v e r a l 【o n et i m et r a n s f e r r i n g m e t h o dt oa d j u s tt h em a p ，a i m e da tt h er o t a t ea n de x p a n s i o ne r r o r se x i t i n gi nt h e v e c t o rm a pi th a sa no b v i o u sd i s a d v a n t a g et h a t t h i sa l g o r i t h mc a n tp r o o f r e a dt h e n o n 1 i n e a re r r o r sa n dp r o v i d et h el o c a la r e at og e tt h eb e s tp r o o f r e a d i n gr e s u l t s o b a s e do nt r a f f i c v e c t o r m a p sb a s i cc h a r a c t e r t h ea u t h o rg i v e sa ni n - d e p t hs t u d yt ot h e v e c t o r m a p sn e t w o r k i n gt o p o l o g y s t r u c t u r ea n db r i n g sf o r w a r dt h ed i s c r e t e n o n 。l i n e a rp r o o f r e a d i n ga l g o r i t h m a l s ot h ea u t h o ra p p l i e st h i sa l g o r i t h mt o t h e p r o o f r e a d i n go f h e f e ia n dc h e n g d uc i t i y sm a p s ，a n dg e t sg o o dr e s u l t s k e yw o r d s ：g p s ，g i s ，v e h i c l en a v i g a t i n g ，v e c t o rm a p ，n e t w o r k i n gt o p o l o g y d i s c r e t ea r e a ，m a p p i n g 1 1 1 中因科学技术人学坝i ：论义 致谢 致谢 首先，我要感谢我的导师鲍远律教授。本篇论文完全是在鲍老师的指导 和激励下完成的 在g p s 实验室三年多的学习生活过程中，鲍老师给予我无微不至的关怀和 细心的教导。鲍老师严谨的治学态度、实事求是的科研精神、乐观勤奋的工作作 风和扎实丰富的实践经验给我留下了深刻的印象。在进行g p s 车辆导航系统、 g i s 矢量地图生成平台等领域的研发以及相关问题的研究和探索过程中，我始终 得到鲍老师的支持、鼓励和指导，在实际参与工程项目的过程中，鲍老师更给予 戎很多帮助和指导，毫无保留地护向产一的绎喻传授铃载，使书受矗雕汽，寻h 得 到很多有益的启示，也培养了我对待科研认真负责的态度。在此，我谨向鲍老师 表示最诚挚的感谢。 感谢刘振安教授，在论文写作期间，您给予我很多关心和指导。感谢系里所 有的老师和领导以及曾经教过我的老师们，感谢你们的谆谆教导，把我培养成才。 感谢叶家明、刘丽萍、阎庆、章守信，那些一起编写、调试程序和讨论问题 的f i 干旱非带皇的讯h 抽 乒学习；i l 了很名车西存它耠审t 作莹习拍t 程中，你们给予我的关怀和帮助让我永远难忘，这份友情将陪伴我走过今后的每 一天。感谢所有g p s 实验室的成员，和我分享学习和生活中的苦与乐。 感谢我的室友高旭东、陈志福、王文辉，5 3 9 的日日夜夜我都不会忘记。感 谢9 5 l o 和0 0 1 0 研所有的同学，五年本科、三年研究生一起学习、生活的时光将 成为我终生难忘的记忆，感谢你们陪伴我走过人生最灿烂的- 段旅程。 感谢我的父母、姐妹，是你们一直在背后支持我，鼓励我，鞭策我，在我跌 倒的时候扶助我，在我成长的每一个日日夜夜，是你们给予了我这世界上最温暖 无私的亲情和爱。这篇论文，是我学习生活的总结，也是我对你们最衷心的报答。 王国江 2 0 0 3 5 中困科学技术人学硕l 论文绪论 第一章绪论 本章首先介绍g p s 全球卫星定位系统、g i s 地理信息系统的基本概念，以 及当前国内外发展的现状和它们在车辆导航方面的应用，并由此指出对交通矢量 地图进行自动校f 的重大意义。由此构成本论文选题的时代背景与技术背景。 1 1 g p s 、g i s 系统简介 1 1 1g p s ( 全球定位系统) 简介 g p s 是英文n a v i g a t i o ns a t e l l i t et i m i n ga n dr a n g i n g g l o b a lp o s i t i o ns y s t e m 的 字头缩写词n a v s t a r g p s 的简称。它的含义是，利用导航卫星进行测时和测 距，构成全球定位系统。人们将这一全球卫星定位系统简称为g p s 。g p s 全球 卫星定位系统从提出到建成，经历了2 0 年，到1 9 9 4 年2 4 颗工作卫星进入预定 轨道，系统全面投入运行。g p s 系统因其应用价值极高，所以得到美国政府和军 队的重视，不惜投资3 0 0 亿美元来建立这一工程，成为继阿波罗登月计划和航天 飞机计划之后的第三大空l 训计划。 g p s 系统的空间部分由2 4 颗卫星组成，均匀分布在6 个仰角为5 5 度的轨道 面上。g p s 系统的利用者接收卫星发送的扩频信号，测量电波传播时问求出：卫星 到接收机天线的距离，利用空f 日j 三球相交一点的原理，解算以接收机位置为未知 数的方程，从而确切知道接收机的位置，也就是说，只需接收到3 颗卫星的信号， 就能确定用户的二维( 经度、纬度) 位置。g p s 系统从根本上解决了人类在地球 上的导航和定位问题，它可以为全球用户提供连续、实时、高精度的三维位餐、 速度和时间信息，可以满足各种不同用户的需要。在海洋上，它可用于舰船海上 协同作战，在海洋交通管制、海洋测量、石油探测、海轮进出港管理等领域提供 定位服务；在陆地上，可用于各种车辆、坦克和陆军等的定位：它还可以广泛应 用于人们的同常生活和科学研究中，如汽车驾驶、旅游、探险、测绘、勘探考古 等方面。g p s 定位系统的建立，给导航和定位技术带来了巨大的变革。 美国政府在进行g p s 系统设计时，计划提供两种服务。一种为标准定位服 务一s p s ，利用t h o u 捕获码( c a 码) 定位，预计精度约为4 0 0 m ，提供民问用 户使用。另一种为精密定位服务p p s ，利用精密码( p 码) 定位，精度达到 1 0 m ，提供给军方和得到特许的用户使用。但在g p s 实验卫星应用阶段，多次 实验表明，实际定位精度远高于此值，利用c a 码定位精度可达到1 5 4 0 m ，利 用p 码定位精度可达3 m 。为了维护美国自身利益，美国国防部在g p s 系统中加 入了s a ( s e l e c t i v e a v a i l a b i l i t y ) 政策选择可用性政策，人为地将误差引入卫 星时钟和卫星数掘中，降低g p s 的定位精度，以防止未经许可的用户把g p s 用 于军事目的。采用s a 政策后的g p s 系统c a 码定位，水平定位精度为1 0 0 米， 垂直测量精度为1 5 7 米。美国国防部常年对s a 政策进行测量，并根据形势和要 求对部分和全部卫星取消s a 政策。s a 政策的引入，在一定程度上限制了g p s 的应用，为了提高定位精度，人们研究和发展出差分g p s 技术一一d g p s ( d i f f e r e n t i a lg p s ) 。但是，d g p s 系统需要建立相应的差分基准站和监测站，造 价昂贵。随着g p s 应用的不断发展，g p s 广大用户要求取消s a 政策的呼声越 来越高，考虑到庞大的g p s 应用市场，美国政府最终于2 0 0 0 年5 月lr 取消了 中周科学技术人学7 0 i | i ：论史 绪论 s a 政策，这必将促进g p s 定位和导航的应用的进一步发展。 2 0 0 0 年以后，以波音公司为首，休斯空问和通信公司、计算机科学公司 ( c s c ) 、洛克西德马丁管理与数据系统( m & d s ) 和雷声公司丌始研究丌发新一代 的全球定位系统g p si i i 。g p si i i 的结构将基于现有的卫星导航系统，并将 丌发出具有创新结构的新的g p s 系统。 1 1 1g i g ( 地理信息系统) 简介 g i s 地理信息系统( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ) 是集计算机科学、地 理地质学、测绘科学、环境科学、空问科学、信息科学和管理科学等为一体的多 学科结合的新兴边缘科学。它是在计算机硬件、软件系统的支持下，采集、存储、 管理、分析和描述整个或部分地球表面( 包括大气层在内) 与空间和地理分稚有 关的数据的空间信息系统。它是融合计算机图形和数据库与一体，用来存储和处 理空间信息的高新技术，它把地理位置和相关属性有关地结合起来，根据用户地 需要将空间信息及其属性信息准确真实、图文并茂地输出给用户，满足城市建设、 企业管理、居民生活对空间信息的变化，借助其独有的空问分析功能和可视化表 达功能，进行各种辅助决策。 地理信息系统具有一下三个方面的特征： 具有采集、管理、分析和输出多种地理空l b j 信息的能力，具有空间性和动 态性： 以地理研究和地理决策为目的，以地理模型方法为手段，具有区域空间分 析、多要素综合分析和动念预测能力，产生高层次的地理信息； 由计算机系统支持进行空问地理数据管理，并由计算机程序模拟常规的或 专门的地理分析方法，作用于空间数掘，产生有用信息，完成人类难以完成的任 务。 地理信息系统是从2 0 世纪6 0 年代丌始逐渐发展起来的新技术。由于地球是 人们赖以生存和发展的基础，所以g i s 是与人类的生存、发展和进步密切关联 的一门信息科学技术，受到人们愈来愈多的重视，其应用已涉及到各行各业。特 别是近几年来，由于全球信息化的飞速发展、信息高速公路、“数字地球”、“数 字城市”、“虚拟社区”理论的提出，g i s 产业受到了空前的关注，越来越多的人 投身到g i s 的学习浪潮中。 2 0 世纪8 0 年代是g s 普及和推广应用的阶段。由于计算机的发展，推出了 图形工作站和p c 微机等性价比大为提高的新一代计算机，计算机和空间信息 系统在许多部门广泛应用。计算机网络技术的应用，使地理信息数据的长距离传 输时效得到极大的提高。g i s 系统软件和应用软件的发展，使得( 3 i s 的应用从解 决基础设施的规划( 如道路、输电线) 转向更复杂的区域丌发和规划，例如二 ：地 的农业利用、城市化发展、人口规划与布局等，地理因素成为投资决策中不可缺 少的依据。许多国家把gj s 作为有关部门的必备工具投入同常运转。与卫星遥 感技术想结合，g i s 丌始用于全球性问题研究，例如全球沙漠化、全球可居住区 的评价、厄尔尼诺现象及酸阿、核扩散及核废料以及全球变化与全球监测。美国 军方制作了全球1 ：1 0 0 万空间数据库d c w ，原苏联制作了全球数字调和模型和 数字j 下摄影像。2 0 世纪8 0 年代，g i s 软件的研制和丌发也取得了很大的成绩， 仅1 9 8 9 年市场上有报价的软件就达7 0 多个，并且涌现出了一些具有代表性的 g i s 商用软件，如a r c d n t f o ，m i c m s t a t i o n ，m g ei n t e 唱r a p h ，a u t oc a , d a r cc a d 等。 我国c i s 的发展虽然较晚，但发展势头迅猛，大体上经历了4 个阶段，即起 2 中周科学技术人学坝l ：论史 绪论 步( 1 9 7 0 一1 9 8 0 年) 、准备( 1 9 8 0 一1 9 8 5 年) 、发展( 1 9 8 5 1 9 9 5 年) 、产业化 ( 1 9 9 6 年以后) 阶段。g i s 已在很多部门和领域得到应用，并引起了政府部门 的高度重视。从应用方面看，地理信息系统已在资源丌发、环境保护、城市规划 建设、土地管理、农作物调查、交通、能源、地图测量、林业、房地产开发、自 然灾害的监测和评估、金融、保险、石油与天然气、军事、犯罪分析、运输与导 航、1 1 0 报警系统、公共汽车调度等方面得到了具体应用。国内已有城市测绘地 理信息系统或测绘数据库e 在运行或建设中。一批地理信息系统软件已研制丌发 成功( 如g e o s t a r ，c i t y s t a r , m a p g i s 等) ，一批高等院校已设立了一些与g i s 有 关的专业或学科，一批专门从事g i s 产业活动的高新技术企业相继成立。此外， 还成立了“中国g i s 协会”和“中国g p s 技术应用协会”等组织。 进入2 l 世纪，随着地理信息产业的建立和数字化产品的普及，g i s 技术已 深入到各行各业，成为政府部门进行科学管理、快速决策及人们生活、生产、学 习和工作中不可缺少的工具。朱镕基总理在中共十五界二中全会报告中明确指出 地理信息将作为一个产业来加以发展，我国的g i s 正迎来一个阳光明媚的春天。 1 2g p s 、g i s 在车辆导航系统中的应用。 g p s 全球定位系统自9 0 年代全面运行投入运营以来，以其全天候、精度高、 体积小、时实性等特点，广泛应用于各个方面。短短的几年间，g p s 技术和相关 应用得到了极大的发展，在海陆空天等领域发挥着越来越大的作用。尤其在车辆 导航方面，显示出强大的生命力和广阔的应用前景，己成为当今国际社会一个新 的技术产业和经济增长点。以2 0 0 0 年为例，车辆导航产品的产值为2 9 亿美元， 约占g p s 产品总值的3 5 左右，由此可见，这将是一个极具潜力的市场。 2 i 世纪是数字信息的时代，包括无线通讯、g p s 全球定位系统、g i s 地理 信息系统、遥感等技术的“数字地球”成为研究的热点。其中，g p s 和车辆导航 技术更得到了广泛的关注。中固科学报( 9 6 9 1 3 ) 载文引用美未来学家预测 “今后十年十大产品将改变人们的工作和生活方式”，其中第七项就是利用g p s 技术并带有智能地图的导航跟踪设备。 车辆监控和导航的研究工作丌始于本世纪7 0 年代，近年来，许多汽车生产 公司为了提高本公司产品在市场的竞争能力，投资研究和丌发车辆导航设备，极 大推进了g p s 在车辆导航领域的应用和发展。丰阳、东芝、索尼等很多大公司 与导航系统供应商协作，使得日本在轿车导航系统方面的研究处于世界领先地 位。1 9 9 1 年，东芝公司轿车导航系统，采用一种可操作的电视g p s 接收机，可 显示沿途饭店、旅馆和商店等信息。1 9 9 4 年，索尼公司推出一种带电子地图的 汽车导航系统，将一个8 通道的g p s 接收机与c d r o m 格式的地图及信息数据 库结合在一起，并能接收调频无线电广播发送的交通流量信息。另外，许多大公 司，如奔驰r 本公司、丰阳、本f 只等，都在积极丌发自己的导航信息系统，拓展 导航信息服务市场。在美国，有多个公司已研制或正在研制轿车导航系统。克莱 斯勒公司研制了一种基于g p s 的车辆导航系统，该系统在失去卫星信号后，可 用罗经和记程计来工作，保持车辆继续导航。威斯汀豪斯公司研制了自动车辆定 位系统，安装在城市公共汽车和轻轨火车上。在欧洲，1 9 9 5 年，法国巴黎的公 共汽车率先使用车辆调度和导航系统。 相比许多发达国家在g p s 应用领域的研究和发展，我国还处于起步阶段， 但近年来发展迅速。我国不少城市引进国外先进设备，装备在公安、军队、盒融、 消防等部门，发挥了一定的效益。另外，考虑到卫星定位导航在军事和国家安全 3 中网科学技术人学预l ：论义 等方面的战略地位，我国也丌始研发自己的卫星定位系统北斗导航系统。 2 0 0 0 年1 0 月3 l 同，我国自行研制的第一颗“北斗导航试验卫星”在西昌卫星 发射中心发射升空；1 2 月2 1 日，第二颗“北斗导航试验卫星”发射升空。标志 着我国将拥有自主研制的第一代卫星导航定位系统，也预示着我国导航定位技术 将发展到了一个新的阶段。但是，目前我国g p s 车辆导航和定位系统的研究和 应用还处于初级阶段，还没有与g i s 地理信息系统等其他系统有效结合形成一 个强大的应用系统。 1 3 交通矢量地图自动校正的意义 g p s 技术的广泛应用，既依赖于地理信息系统g i s ，又促进了地理信息系统 g i s 的蓬勃发展。交通矢量地图是为道路交通管理、车辆安全监控等目的而使用 的建立在准确地理位置坐标数据模型的地理信息系统。交通矢量地图是完善g p s 应用技术的基石，这在我国目前更显得重要。矢量地图的准确性直接关系到系统 提供的资料的准确度以及由此做出的决策的效能。 实际上在目前的数字化时代，提出数字地球、数字城市、数字交通，只要涉 及到地理位置，就需要矢量地图。矢量地图的生成过程，目前主要使用数字化仪， 如果要求直接获得精确的矢量化地图，不仅需要小比例尺的精确的测绘地图，整 个矢量化过程也变成一件极为繁琐的过程。反过来，我们使用大比例尺的甚至只 是市面上可以买到的交通旅游地图，矢量地图的生成过程，就会成为极为简单的 事情。不过矢量地图的地理位置定标与校正，则成为矢量地图成功实现的关键环 节。目前对矢量地图的地理位置定标与校f 除了整体线性校j 下外，就是人工逐节 点校f ，前者并不能改进原始矢量地图的非线性误差，后者则成为极为繁琐的手 工逐点定标过程，其工作量不亚于重新独立测绘制图。 文 1 】中我们曾介绍：“中国g p s 应用系统迅速增长的障碍不是硬件而是软 件。只有大力发展中国交通矢量地图g i s 软件产品，才能使目前的g p s 应用系 统成为实用高效，从而迅速形成中国g p s 应用产品的规模化生产与市场”。中 国交通矢量地图g i s 自动生成与校f 技术及在这一技术基础上的平台软件，及 其规模化的中国交通矢量地图q i s 产品，将是g p s 应用产业唯一的最高风险最 高回报的双刃箭。 本论文将着眼于城市交通管理、车辆导航对交通矢量地图的迫切需要，介绍 g p s 实验室在交通矢量地图g i s 自动生成与校正技术研究工作中所取得的一系 列研究成果，并结合个人在交通矢量地图自动校正算法方面的学习、总结和思考， 针对交通矢量地图中的非线性误差，提出了一种按g p s 位置轨迹对矢量地图予以 自动定标与精度校币的新型算法：离散非线性校正算法。 1 4 论文安排 第一章绪论，简要介绍了g p s 、g i s 的基本概念，当前国内外发展现 状，及其在车辆导航系统中的应用：结合当前数字化地球、数字化 城市的实际需要，分析了交通矢量地图校正的重大意义。 第二章矢量地图综述，从矢量地图的基本概念出发，介绍了矢量地图 同栅格地图相比具有的一些优势，矢量地图的生成，矢量地图的编 辑等。同时，对矢量地图中道路的拓扑结构和矢量地图库的组成给 出了清晰的阐述。 4 中困科学技术人学f 0 ； i j 论义 绪论 第三章交通矢量地图的自动校正，本章从交通矢量地图的误差分析出 发，详细阐述了交通矢量地图传统的自动校正算法及最小化多点最 小二乘误差的整体线性校f 算法，给出了校正实例，同时分别分析 了这种算法的优点和不足。在比较线性校正算法与手动( 非自动) 非线性校正过程的基础上，产生出本文新算法的动机。 第四章矢量地图的离散非线性校正，本章是全文的重点，全面叙述作 者在交通矢量地图自动生成平台的研究中提出的与传统整体线性 校正算法有本质上不同的新的自动校正算法：离散非线性校正算 法。给出了对合肥市与成都市的多种校正实例，从实际校正效果上 验证了算法的可行性与先进性。最后比较分析了整体线性校正算法 与离散非线性校正算法各自的优点和不足。 第五章矢量地图在车辆导航系统中的应用，本章首先介绍了以准确的 交通矢量地图为基础的车辆导航系统，接着介绍了两种导航系统中 的智能决策：最短路径寻优算法和车辆轨迹实时修正算法，并在矢 量地图上加以实现。 5 中冈科学技术人学倾j ：论义矢量地 e i 综述 第二章矢量地图综述 从第一章，我们看出无论是城市规划管理，还是车辆监控导航，都需要准确 的矢量地图。导航电子地图是楚个导航系统的基础，导航系统的定位、路径计优、 轨迹校正等功能都不丌导航电子地图的支持。对于建设数字化地球、数字化蚍市， 矢量地图具有重要的意义 那么什么是矢量地图? 它具有那些优点和属性? 如何来生成矢量地图 呢? g p s 实验室在这一方面做了那些工作? 这正是本章所要讲述的内容。 2 1 矢量地图的基本概念 随着计算机的出现和信息论的发展，地图制图逐步由手：c 绘制过渡到巳子 化、自动化的阶段，从数字资料自动制图、图形资料自动制图到航空遥感用i 航天 遥感图像的自动制图，电子地图的技术发展非常迅速。如前一段，美困还利j f 】卫 星扫描生成全球的三维电子地图。电子地图的应用非常广泛，海洋、气象、水文、 地质、土地利用、地球物理、宇航、测绘、勘探等领域都需要电子地图。2 0 世 纪6 0 年代，地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，简称g i s ) i l 卅的兴 起和迅猛发展更推动了电子地图制图的发展。g i s 是一种专门用于管理地圳空间 分布数据的计算机信息系统，所以其中的数字电子地图是一个必不可少的部分， 在很大程度上决定了g i s 的命运。我国对制图自动化和g i s 的研究起步较晚， 近几年，形成一股关于电子地图的研究热湖。 电子地图按照其数据结构的不同，又主要分为矢量电子地图和栅格电了地图 两种，栅格电子地图也就是我们平时常见的位图。 矢量地图是指对点阵数据数 字地图图像进行跟踪识别得到的矢量数据以后的地图，然后对地图巾线状地物如 河流、等高线、铁路、公路、等进行恢复，恢复的结果就是一l 隔矢量地图。在矢 量地图上可以方便的进行放大和缩小变换。 电子地图的这两种实现，各有优缺点。栅格电子地图，主要赴生成比较力便， 图像比较细致，和人们同常使用的地图类似，容易被用户接受，但是，栅格r 小f 地图数据量比较大，存储不方便，放大过程中会产生失真，数据不是很准确，很 难进行全局或者局部校正，更新起来也比较费事。矢量电子地图生成相对费事， 但是数据经过压缩，数据量小，地图可以随意缩放，缩放过程中不会失真，可以 进行全局或者局部校f ，更新起来也很方便。例如成都市地刚，按j 比例j t1 ： 2 0 0 0 0 0 ( 约) ，转化为2 4 位位图，大约1 5 m ，而我们生成的矢量地图数损；， 只有1 3 7 k ，近3 0 0 0 条道路( 矢量边) 的矢量文件大小只有约6 1 k 。可见欠l j l l 子地图的优越性。 2 2g p s 实验室开发的矢量地图与g i s 系统 绝大多数g i s 系统中使用的地图是以矢量地图作为其表现形式的。嗣内目 前矢量地图常用的生成方式有两种，- - , p 是用数字化仪从纸质地图中捉取，儿一 种是从点位图中利用模式识别的有关理论进行识别和提取。生成一个准确而完备 的矢量地图要花费大量的人力和财力，一个中等规模的城市用数字化仪生成矢量 地图，大约需要一个月的时间。如何以较小的代价生成一副实用的矢量地图，并 6 中冈科学技术人学顶i ：论义矢地i 璺i 综述 在此基础上构造一个实用的g i s 系统，是g p s 实验室一直在研究的一个课题。 g p s 实验室从1 9 9 3 年以来，一直在从事g p s 定位、监控与导航和g i s 系统 的研究。无论是g p s 定位、监控、导航，都离不- 丌g i s 系统的支持。在g i s 系 统方面，已经有过多个版本，分别是在d o s 、w i n d 3 l 和w i n 9 5 下丌发的。经 过许多人多年的努力g p s 实验室形成了一套有实验室特色的，而且比较成熟的 g i s 软件和g i s 环境矢量地图尘成平台。下面，我们就介绍一下g p s 实验室丌 发的矢量电子地图生成平台和g i s 系统。 2 2 1 系统组成 我们所说的g i s 往往是一个比较庞大的系统，而且包含了很多各类数据管 理、决策的模块，它是一种针对性比较强的系统，对于不同的用户，往往对数据 有不同的操作、管理、决策。但是它毕竟是一个以地理空间分柿数据为基础的系 统，所以有一个因素不能少，那就是电子地图，它为系统提供最基本的地理信息。 作 们 保 性 图形数据组描述数据小 图2 2 1 矢量地图的组成 - n 地图可以看成是由点、线、而i 种几何图形构成的。点指的是单位之类 的地物实体，线则是道路、铁路之类的实体，而区划这类的实体就可以用面来表 征。依照传统的习惯，把点、线、面这三类地物按照从上到下的顺序排列。生成、 编辑电子地图的过程就是生成、编辑地图矢量库和数据库的过程，下而我们米详 细介绍一下这两个最重要的库。 2 2 2 地图矢量库 矢量库定义出几何结构的位置形状信息。点标志比较简单，只是一个点：面 标志对应的几何结构就是一个多边形，也比较简单：而线标志则包含较多的内容， 要相对复杂一些。我们下面主要介绍一f - j 线标志有关的一些定义，也就是道路 的有关定义： 定义0 ：矢量边。是一些点的坐标的集合，表征着一条连续的折线。它，f r 以 下的性质： a 点的排列顺序决定了折线的行进方向，决定了折线的形状和位置： 7 中困科学技术人学倒1 ：论义 矢量地| 茔综述 b 只有两个端点可以属于别的矢量边。 定义l ：大节点、小节点、节点。大节点是矢量边的端点；小节点是指矢量 边除端点之外的内部点；大节点和小节点统称节点。 定义2 ：弧。一条弧就是一条矢量边，是若干个节点的集合。组成弧的节点 是顺序排列的。 定义3 ：路。路是若干条弧的集合。 如图所示： 小1 y 点：2 、3 、5 、6 人。1 y 点：1 、4 、7 、8 弧： 1 ，2 ，3 ，4 、 4 ，5 t6 ，7 】、【4 ，8 】 路：以上的弧的任意组合均可能构成路。 7 图2 2 2 几种拓扑结构的定义 我们以后所有的工作都要针对以上定义的几种结构来展朋均。 2 2 3 地图数据库 地图数据库中包含了各种地物的属性数据。 对于面地物，需要知道的属性有：类型、位筠：、形状、名称、颜色等； 对于点地物，需要知道的属性有：类型、位置、名称、显示图标、显示级别 等： 对于线地物，需要知道的属性有：类型、位置、形状、名称、颜色、娃示宽 度、显示级别等； 上面提到的各种地物的属性数据中都有一项类型，也就是它所心的组 ( g r o u p ) 。组，定义出了某一批地物的缺省属性，是一些具有相同或相近心性的 同类地物的集合。 整个数据库的层次如下所示： 8 厂 中田科学技术人学顾：j 论史矢量地l 鳘| 综述 d i v i s i o n 图2 2 3 地图数据库的层次 地图的数据库有四个层次，最上层当然是地图数据库，它由三个部分 ( d i v i s i o n ) 构成的，也就是点、面、线三大类地物；每个部分又由若干个组( o r o u p ) 构成；每个组又由若干个地物实体( e n t i t y ) 构成，实体，就是点、面、线这类 的地物个体。这种分层结构使得配置地图数据库时显得特别的方便。 2 2 4 面向对象的数据模型 采用面向对象的数据模型可以最自然地描述现实世界，将实体抽象为对象， 用对象中的数据成员和成员函数模拟客观世界及其运动。面向对象的数据模型有 很强的扩充性。根据面向对象的数据组织方式，用面向对象的方法设计了一个稳 健的，易于扩充和修改的数据库模型。如图2 2 4 所示： 地图对琢类( m a p ) 包含 地图数揩厚( d 日)l篁垒 j 地图欠量陴( t 0 p 0 ) 包含 地物类( d i v i s i o n ) 聚合 地物纽( gr o u p ) 聚台 地物丈体( e n l j t y 】kf 儿何对象类 腻忭 图2 2 4 地图对象间的关系 地图对象类包含地图的属性和组成成分，属性表示地图的基本特征：地图名、 9 中周科学技术人学坝j ? 论义 矢量地蚓综述 比例尺等等，在这个类的层次上我们可以定义地图的基本操作，例如放大、缩小、 漫游等。从这个对象的关系图来看，在实现的时候，地图的数据库与矢量库并不 是完全独立的，相反，数据库实际上包含了矢量库。也可以这么看，矢量库实际 上是一个几何对象集，提供某些e n t i y 的几何数据。 e n t i t y 包含了基本地理对象的属性和空间几何信息，指明了基本地理对象的 基本特征和组成的几何对象，几何对象包含几何对象的地理位置和相互关系的信 息，可以分为纯几何对象类( 如点、多边形等) 和拓扑几何对象类( 如节点、弧 等) ，后者是由地图矢量库来提供的。 2 3 交通矢量地图的生成 要生成一副交通矢量地图，首先是生成地图的矢量文件，生成矢量地图的拓 扑结构矢量库。我们采用的是从点位图中识别、生成矢量地图的方式。我们 将从纸制地图扫描得到的点位图进行识别，提取出其中的道路信息，然后将这些 道路信息矢量化得到一副只包含道路信息的矢量文件，将这作为一副矢量地图的 基础。然后，在这个基础上进行编辑、校正，并输入各种地图上的有关数拱- ：，生 成电子地图的数据库，最终生成一个完整而准确的矢量地图。如下图所示： 图2 3 1 交通矢量地图的生成 下面我们给出合肥市地图生成的实例，来演示地图生成的全过程。 1 0 中冈科学技术人学坝i j 论义矢量地i 笙i 综迷 例2 3 2 合肥币彩色变通地图( 部分) 图2 3 3 提取出道路和区域信息后的黑白地图 图2 3 4 矢量化后的合肥市地图 中周科学技术人学1 0 i i j 论义矢量地图综述 图2 3 5 信息添加后的合肥市矢量交通地图( 部分) 从上面的框图和实例中我们可以看出生成一副较完备矢量交通地图，主要包 括以下三个步骤： 彩色地图的道路识别； 地图矢量化； 矢量地图的校f 和地图信息的添加； 彩色地图的道路识别，就是根据一j 嚆彩色交通地图，利用一定的算法，提取 出其中的道路、区域信息，形成一幅黑白位图0 5 1 。地图矢量化则是根据得到的 线状的黑白位图抽取出有意义的模式特征。矢量化后的地图经过校正和添加地图 信息就可以很好的应用于我们的监控和导航系统了。下面我们将简要介绍一下地 图矢量化和地理信息添加这两方面的内容。 2 4 地图矢量化 在矢量化之间一般要先作一些预处理工作，以减少噪声的干扰，保证数据 的质量。预处理过程主要包括以下几个方面： 平滑： 所谓的平滑处理是将图象上由于噪声引入的孤立点去掉，将孔洞、缺口、间 隙填补上，将小突起删除。平滑处理是预处理的第一步，平滑的结果将影响细化 的结果，最终影响矢量化。 细化： 所谓的细化是将图象上的线条细化成一个象素宽的线条的处理过程，细化的 结果使得线条所在的地方总保持一个象素宽。对细化的一般要求是：保证细化后 曲线的连通性，细化结果是原曲线的中心线，细化处理速度快，保留细线端点。 矢量化结果的好坏，很大程度上取决于细化算法。 连接断点： 计算断点之间的距离，如果之间的距离小于给定的误差，则在断点之问画一 条直线。 删除毛刺：主要是删除图像点外细小的分杈。 1 2 中囝科学技术人学坝i ：论义矢量地幽综述 在最终的细化位图上就可以完成图形的矢量化过程。我们给出地图矢量化的 基本流程如下： 图2 4 2 地图矢量化的流程 2 5 矢量地图的编辑 地图矢量化完成以后，我们可以得到一个包含了所有道路拓扑信息的基本的 矢量文件，它只是矢量地图库的一个雏形。在此基础上，我们要对矢量地图进行 编辑，将地图上地物的属性信息输入地图属性数据库中，并确定地图的地理参数， 从而生成一个完整而又准确的交通矢量地图。 矢量地图的编辑主要完成以下的几个方面的工作： 编辑g i s 地图数据库；编辑地图的拓扑结构；利用已有的轨迹记录确定地 图的地理参数。 一副地图编辑过程可以用如下的流程图来表示： 1 3 中阖科学技术人学坝i ? 论史 矢量地幽综述 2 5 1 地图数据的结构 数据是地图的核心。- - n 完备的电子地图的数据量是很大的，我们采用了分 层的数据结构来组织这些数据，最大限度的考虑和满足用户的需要。 地理数据的分层结构： 图2 5 ，2 地理数据的分层组织 电子地图出基本地理对象集( 点、线、面状地物集) 组成；基本地理对象由 几何对象( 点、线、面) 加上其属性数据组成，几何对象包含地理对象的几何数 据，并维护对象阳j 的拓扑关系。 2 5 2 矢量库的组织 地图矢量库保存了组成地图的线状元素的几何数据，也就是包含了节点、弧 和路的信息。它是整个电子地图和g i s 系统的根本，也是我们后面实现路径寻 优、动态轨迹校正等智能决策功能的基础。下面我们就来看看在这个矢量库中是 如何组织这些数据的。 像我们在最前面提到的，弧是节点的集合，路是弧的集合。我们可以把矢量 库看成由三个表构成，一个节点的表，每一行表示一个节点，x 、y 坐标组成这 个表的两个列：一个弧的表，它的每一行表示一条弧，它的列是构成这条弧的点； 还有一个路的表，它的每一行表示一条路，构成这条路的所有的弧是各个列。如 图2 5 3 所示。 另外，对于一个g i s 系统，不可或缺的功能就是根据地理空问信息进行 些决策，例如搜索两个给定点之间的最优路径。在前面的讨论中，我们可以看到 节点、弧、路之问的关系是很密切的，因此我们提供充分的机制，使得它们之问 能够顺利的相互访问。如图2 5 3 所示。 1 4 中周科学技术人学坝i ? 论义 矢盘地l 星i 综述 i 第1 个点f 第2 个点 弧1 弧2 弧n a 弧的表 第1 条弧第2 条弧 路1 路2 矢量地图的完全校正，就是要找到线性映射关系掰，把只映射成巧： 以) = 巧= 隶耳i ，i ) ( 善；，) ，+ o ，) 但对线性变换 ， 一) ，这通常是不能实现的。通常所况的矢量地图校正，就要 找出线性映射关系村( ) ，把只映射成一，即： 只t i ，只) = # 。i ，y i i “2 ，y 2 j ，f j 。，y 。) 等价于把g 。映射成g ： a 。= m ( g 。) ；g l o n l + 埘j ) ，( i o n ：、t a t ) 使得巧与露之间偏差最小，等价于g ：与g ：偏差e 最小。偏差的误差函数取为： e ；怫一g _ ：| = 量e ? = 畦铲女慷一删 式中k 为常数不影响优化过程，距离函数： 。? ；j k j g 刈= i j _ 二i i i 产j i 石孑研q = l p ：一p 训= i i ：j i i 芦j i ；丽。 获得线性映射关系m ( 一) 后，对矢量地图所有节点n 。( 对应地图图廓m 。) 执行 同样的变换。可以预期变换后的矢量地图所有节点| ：。( 对应校正后的地理地图 图廓m 0 ) 与准确的矢量地图所有节点二( 构成准确的地理地图图廓二) 的偏 差也会达到最小。从而完成矢量地图校正的过程。 直观地说，矢量地图校正的过程，本质上就是改变矢量地图节点坐标数据库 的所有节点数据a 。，尽可能地用接近于其准确位最二的新