交通矢量地图自动生成平台的算法研究与实现改进

交通矢量地图自动生成平台的算法研究与实现改进专业自动化作者徐浩学号PB00010060导师鲍远律教授20045完成于GPS实验室中国科学技术大学自动化系致谢首先，我要感谢的是我的父母，没有他们的辛苦劳作，没有他们在物质精神上的支持，我不可能有机会在中国科学技术大学接受教育并顺利完成学业，更谈不上完成这篇论文，在此向你们致以最真挚的感谢，也将这篇论文作为献给你们的一份礼物。我要感谢我的导师鲍远律教授。从本科三年级开始，鲍老师接收我进实验室学习，在这里我学到了鲍老师治学的严谨和求实，思路的宽广和创新。鲍老师的博学让我敬佩，他的平易近人更让我感动。正是在鲍老师无私的帮助下，在他耐心的指导和帮助下，我才能够学到许多的专业知识，才能完成这篇论文。在此，我也要向鲍老师表达我最诚挚的感谢。感谢我的室友钟捷飞，在调试论文相关程序的时候，你给了我巨大的帮助，在此向你表示衷心感谢。感谢大学期间给我授课讲学的老师们，正是从你们那里我的知识得到了丰富。我受益更大的是受到你们对学术专注精神的影响，知道了做学问做事都要实事求是、乐观勤奋。感谢实验室的师兄师姐，你们给我的热情帮助，使我感受到了一种团结进取的实验室氛围，你们的帮助对我完成这篇论文起到了重要作用。感谢我的室友、朋友们，和你们的愉快相处使我能在一个和谐的环境中进行学习研究。和你们在一起的日日夜夜，和你们的真挚友情，是我生命中的最重要财富之一。徐浩200451中国科学技术大学本科毕业论文目录致谢1目录2摘要1ABSTRACT2第一章绪论411GPS、GIS系统简介4111GPS（全球定位系统）简介4111GIS（地理信息系统）简介412交通矢量地图自动校正的意义513论文安排6第二章矢量地图综述821矢量地图的基本概念822GPS实验室交通矢量地图自动生成平台介绍9221系统组成9222地图矢量库10223地图数据库1123地图数据的结构1224矢量库的组织1225交通矢量地图的生成13第三章交通矢量地图的传统校正算法1531交通矢量地图的误差分析1532矢量地图的线性定标16321线性定标的原理17322线性定标的缺陷1833矢量地图的整体校正算法18331整体校正算法的基本原理18332整体校正算法的局限性20第四章矢量地图的离散非线性校正2241算法的思路2242离散块的选择2343算法的具体实现2444校正算法实例28441合肥市矢量地图校正实例28452算法分析30第五章离散非线性校正算法实现的改进研究3251算法实现程序的结构分析32511对ADJUSTPOINT方法进行分析研究33512对NEWCHANGEPOINT函数进行分析研究3752离散非线性校正算法实现的截断修正3853算法实现改进总结43结束语442中国科学技术大学本科毕业论文参考文献453摘要GPS全球卫星定位技术在车辆导航领域有着广泛的应用。随着我国道路建设的发展和数字地球、数字城市的提出，车辆导航的需求越来越大。车辆导航离不开精确、完整的交通矢量地图，在这样的背景下，开发、发展、改进矢量地图的生成工具就非常重要。本论文是以中国科学技术大学GPS实验室的交通矢量地图自动生成平台为背景、基础和研究对象。详细研究了其中的交通矢量地图自动校正部分，仔细分析几种校正算法，并对算法的实现进行了改进，使其能在校正矢量地图的同时更好的保持地图的网络拓扑关系。该平台的地图校正功能是根据GPS记录仪记下的实际轨迹，对由栅格地图生成的矢量地图进行校正的。传统校正算法主要是针对矢量地图中的旋转和放缩误差，采用全局一次性变化的方法对地图进行校正。这类算法存在着明显的不足即无法校正地图中的非线性误差，无法达到局部最优的校正效果。针对这些不足，科大GPS实验室从交通矢量地图的基本特征出发，深入分析矢量地图的网络拓扑结构，提出并使用了离散非线性的校正算法，取得了良好的效果。在作者分析该算法时发现，由于实现时引入了计算误差，现有的对该算法的实现有可能威胁到矢量地图的网络拓扑结构，于是作者在深入研究该算法之后，采用了截断修正思想，对该算法的实现进行了修改，使其更好的保持矢量地图网络拓扑结构的稳定，并且在实际应用中，得到了较好的结果。关键字GPS（全球卫星定位系统），GIS（地理信息系统），车辆导航，矢量地图，网络拓扑，离散块，映像，截断修正。1中国科学技术大学本科毕业论文ABSTRACTGPSGLOBALPOSITIONINGSYSTEMTECHNOLOGIESAREWIDELYUSEDINTHEFIELDOFVEHICLENAVIGATINGALONGWITHTHEROADDEVELOPMENTOFOURCOUNTRYANDTHEBROUGHTFORWARDOFDIGITALEARTHANDDIGITALCITY,THEMARKETOFVEHICLENAVIGATINGISGROWINGFASTTHEVEHICLENAVIGATINGCANNOTWORKWELLWITHOUTAPRECISEVECTORMAPINTHISBACKGROUND,ITISVERYIMPORTANTTOEXPLOIT,DEVELOPANDIMPROVETHETOOLOFBUILDINGVECTORMAPINTHISPAPER,WESELECTTHETRAFFICVECTORMAPSAUTOMAKEPLATFORMOFUSTCGPSLABASBACKGROUND,BASEANDRESEARCHOBJECTWEGODEEPINTORESEARCHINGTHEPARTOFPROOFREADINGOFTHISPLATFORM,ANALYZEDIFFERENTPROOFREADINGALGORITHMS,ANDIMPROVETHEREALIZATIONSOFTHEMWEDOALLTHESETOBETTERKEEPVECTORMAPSNETWORKINGTOPOLOGYWHENWEPROOFREADAVECTORMAPTHISSYSTEMPROVIDESTHEFUNCTIONOFPROOFREADINGMAPITCANPROOFREADTHEVECTORMAPFROMGRIPMAPACCORDINGTOTHEGPSVEHICLETRACK,WHICHISRECORDEDBYGPSRECORDERTHETRADITIONPROOFREADINGALGORITHMADOPTSTHEOVERALLONETIMETRANSFERRINGMETHODTOADJUSTTHEMAP,AIMEDATTHEROTATEANDEXPANSIONERRORSEXITINGINTHEVECTORMAPITHASANOBVIOUSDISADVANTAGETHATTHISALGORITHMCANTPROOFREADTHENONLINEARERRORSANDPROVIDETHELOCALAREATOGETTHEBESTPROOFREADINGRESULTSOBASEDONTRAFFICVECTORMAPSBASICCHARACTER,THEUSTCGPSLABGIVESANINDEPTHSTUDYTOTHEVECTORMAPSNETWORKINGTOPOLOGYSTRUCTUREANDBRINGSFORWARDTHEDISCRETENONLINEARPROOFREADINGALGORITHMALSOTHISALGORITHMISAPPLIEDTOTHEPROOFREADINGMAPS,ANDGETSGOODRESULTSWHENANALYZINGTHISALGORITHM,THEAUTHORFOUNDTHATTHECURRENTREALIZATIONTOTHISALGORITHMMAYTHREATENTHEVECTORMAPSNETWORKINGTOPOLOGY,BECAUSEOFCALCULATEERRORSAFTERDEEPLYRESEARCHINGTHISALGORITHM,THEAUTHORAMENDCURRENTREALIZATION,WITHANOTIONOFTRUNCATIONCORRECT,INORDERTOBETTERKEEPVECTORMAPSNETWORKINGTOPOLOGYSTABILIZATIONTHEAUTHORAPPLIESITTOTHEPROOFREADINGMAPS,ANDGETSBETTERRESULTSTHENPRIMARYREALIZATION2中国科学技术大学本科毕业论文KEYWORDSGPS,GIS,VEHICLENAVIGATING,VECTORMAP,NETWORKINGTOPOLOGY,DISCRETEAREA,MAPPING,TRUNCATIONCORRECT3中国科学技术大学本科毕业论文第一章绪论本章首先介绍GPS全球卫星定位系统、GIS地理信息系统的基本概念，以及当前国内外发展的现状和它们在车辆导航方面的应用，并由此指出对交通矢量地图进行自动校正的重大意义。由此构成本论文选题的时代背景与技术背景。11GPS、GIS系统简介111GPS（全球定位系统）简介GPS是英文NAVIGATIONSATELLITETIMINGANDRANGING/GLOBALPOSITIONSYSTEM的字头缩写词NAVSTAR/GPS的简称。它的含义是，利用导航卫星进行测时和测距，构成全球定位系统。人们将这一全球卫星定位系统简称为GPS。GPS全球卫星定位系统从提出到建成，经历了20年，到1994年24颗工作卫星进入预定轨道，系统全面投入运行。GPS系统因其应用价值极高，所以得到美国政府和军队的重视，不惜投资300亿美元来建立这一工程，成为继阿波罗登月计划和航天飞机计划之后的第三大空间计划。GPS系统的空间部分由24颗卫星组成，均匀分布在6个仰角为55度的轨道面上。GPS系统的利用者接收卫星发送的扩频信号，测量电波传播时间求出卫星到接收机天线的距离，利用空间三球相交一点的原理，解算以接收机位置为未知数的方程，从而确切知道接收机的位置，也就是说，只需接收到3颗卫星的信号，就能确定用户的二维（经度、纬度）位置。GPS系统从根本上解决了人类在地球上的导航和定位问题，它可以为全球用户提供连续、实时、高精度的三维位置、速度和时间信息，可以满足各种不同用户的需要。GPS定位系统的建立，给导航和定位技术带来了巨大的变革。111GIS（地理信息系统）简介GIS地理信息系统（GEOGRAPHICALINFORMATIONSYSTEM）是集计算机科学、地理地质学、测绘科学、环境科学、空间科学、信息科学和管理科学等为一体的多学科结合的新兴边缘科学。它是在计算机硬件、软件系统的支持下，采集、存储、管理、分析和描述整个或部分地球表面（包括大气层在内）与空间和地理分布有关的数据的空间信息系统。它是融合计算机图形和数据库与一体，用来存储和处理空间信息的高新技术，它把地理位置和相关属性有关地结合起来，根据用户地4中国科学技术大学本科毕业论文需要将空间信息及其属性信息准确真实、图文并茂地输出给用户，满足城市建设、企业管理、居民生活对空间信息的变化，借助其独有的空间分析功能和可视化表达功能，进行各种辅助决策。地理信息系统具有以下三个方面的特征具有采集、管理、分析和输出多种地理空间信息的能力，具有空间性和动态性；以地理研究和地理决策为目的，以地理模型方法为手段，具有区域空间分析、多要素综合分析和动态预测能力，产生高层次的地理信息；由计算机系统支持进行空间地理数据管理，并由计算机程序模拟常规的或专门的地理分析方法，作用于空间数据，产生有用信息，完成人类难以完成的任务。地理信息系统是从20世纪60年代开始逐渐发展起来的新技术。由于地球是人们赖以生存和发展的基础，所以GIS是与人类的生存、发展和进步密切关联的一门信息科学技术，受到人们愈来愈多的重视，其应用已涉及到各行各业。特别是近几年来，由于全球信息化的飞速发展、信息高速公路、“数字地球”、“数字城市”、“虚拟社区”理论的提出，GIS产业受到了空前的关注，越来越多的人投身到GIS的学习浪潮中。20世纪80年代是GIS普及和推广应用的阶段。由于计算机的发展，推出了图形工作站和PC微机等性价比大为提高的新一代计算机，计算机和空间信息系统在许多部门广泛应用。计算机网络技术的应用，使地理信息数据的长距离传输时效得到极大的提高。GIS系统软件和应用软件的发展，使得GIS的应用从解决基础设施的规划（如道路、输电线）转向更复杂的区域开发和规划，例如土地的农业利用、城市化发展、人口规划与布局等，地理因素成为投资决策中不可缺少的依据。许多国家把GIS作为有关部门的必备工具投入日常运转。与卫星遥感技术想结合，GIS开始用于全球性问题研究，例如全球沙漠化、全球可居住区的评价、厄尔尼诺现象及酸雨、核扩散及核废料以及全球变化与全球监测。12交通矢量地图自动校正的意义GPS技术的广泛应用，既依赖于地理信息系统GIS，又促进了地理信息系统GIS的蓬勃发展。交通矢量地图是为道路交通管理、车辆安全监控等目的而使用的建立在准确地理位置坐标数据模型的地理信息系统。交通矢量地图是完善GPS5中国科学技术大学本科毕业论文应用技术的基石，这在我国目前更显得重要。矢量地图的准确性直接关系到系统提供的资料的准确度以及由此做出的决策的效能。实际上在目前的数字化时代，提出数字地球、数字城市、数字交通，只要涉及到地理位置，就需要矢量地图。矢量地图的生成过程，目前主要使用数字化仪，如果要求直接获得精确的矢量化地图，不仅需要小比例尺的精确的测绘地图，整个矢量化过程也变成一件极为繁琐的过程。反过来，我们使用大比例尺的甚至只是市面上可以买到的交通旅游地图，矢量地图的生成过程，就会成为极为简单的事情。不过矢量地图的地理位置定标与校正，则成为矢量地图成功实现的关键环节。目前对矢量地图的地理位置定标与校正除了整体线性校正外，就是人工逐节点校正，前者并不能改进原始矢量地图的非线性误差，后者则成为极为繁琐的手工逐点定标过程，其工作量不亚于重新独立测绘制图。文1中我们曾介绍“中国GPS应用系统迅速增长的障碍不是硬件而是软件。只有大力发展中国交通矢量地图GIS软件产品，才能使目前的GPS应用系统成为实用高效，从而迅速形成中国GPS应用产品的规模化生产与市场”。中国交通矢量地图GIS自动生成与校正技术及在这一技术基础上的平台软件，及其规模化的中国交通矢量地图GIS产品，将是GPS应用产业唯一的最高风险最高回报的双刃剑。13论文安排第一章绪论，简要介绍了GPS、GIS的基本概念，当前国内外发展现状，及其在车辆导航系统中的应用；结合当前数字化地球、数字化城市的实际需要，分析了交通矢量地图校正的重大意义。第二章矢量地图综述，从矢量地图的基本概念出发，介绍了矢量地图同栅格地图相比具有的一些优势，矢量地图的生成，矢量地图的编辑等。同时，对矢量地图中道路的拓扑结构和矢量地图库的组成给出了清晰的阐述。第三章交通矢量地图的传统校正算法，本章从交通矢量地图的误差分析出发，研究了交通矢量地图传统的自动校正算法及最小化多点最小二乘误差的整体线性校正算法，同时分别分析了这种算法的优点和不足。6中国科学技术大学本科毕业论文第四章矢量地图的离散非线性校正算法研究，研究分析交通矢量地图自动生成平台中提出并应用的与传统整体线性校正算法有本质上不同的新的自动校正算法离散非线性校正算法。给出了对合肥市矢量地图的校正实例，从实际校正效果上验证算法的可行性与先进性，并分析其不足之处。第五章离散非线性校正算法实现的改进研究，分析在实际进行矢量地图校正时影响地图拓扑结构的原因，从保护地图拓扑结构的目标出发，在离散非线性校正算法实现中加入截断修正方法，产生新的实现算法，使实际系统在校正矢量地图的同时不会改变系统的拓扑结构。并给出对合肥市矢量地图的校正实例，与原来的算法实现进行效果比较。7中国科学技术大学本科毕业论文第二章矢量地图综述无论是城市规划管理，还是车辆监控导航，都需要准确的矢量地图。导航电子地图是整个导航系统的基础，导航系统的定位、路径寻优、轨迹校正等功能都不开导航电子地图的支持。对于建设数字化地球、数字化城市，矢量地图具有重要的意义。21矢量地图的基本概念随着计算机的出现和信息论的发展，地图制图逐步由手工绘制过渡到电子化、自动化的阶段，从数字资料自动制图、图形资料自动制图到航空遥感和航天遥感图像的自动制图，电子地图的技术发展非常迅速。电子地图的应用非常广泛，海洋、气象、水文、地质、土地利用、地球物理、宇航、测绘、勘探等领域都需要电子地图。20世纪60年代，地理信息系统（GEOGRAPHICINFORMATIONSYSTEM，简称GIS）14的兴起和迅猛发展更推动了电子地图制图的发展。GIS是一种专门用于管理地理空间分布数据的计算机信息系统，所以其中的数字电子地图是一个必不可少的部分，它在很大程度上决定了GIS的命运。电子地图按照其数据结构的不同，又主要分为矢量电子地图和栅格电子地图两种，栅格电子地图也就是我们平时常见的位图。矢量地图是指对点阵数据数字地图图像进行跟踪识别得到的矢量数据以后的地图，然后对地图中线状地物如河流、等高线、铁路、公路、等进行恢复，恢复的结果就是一幅矢量地图。在矢量地图上可以方便的进行放大和缩小变换。电子地图的这两种实现，各有优缺点。栅格电子地图，主要是生成比较方便，图像比较细致，和人们日常使用的地图类似，容易被用户接受，但是，栅格电子地图数据量比较大，存储不方便，放大过程中会产生失真，数据不是很准确，很难进行全局或者局部校正，更新起来也比较费事。矢量电子地图生成相对费事，但是数据经过压缩，数据量小，地图可以随意缩放，缩放过程中不会失真，可以进行全局或者局部校正，更新起来也很方便。例如成都市地图，按照比例尺1200000（约），转化为24位位图，大约15M，而我们生成的矢量地图数据库，只有137K，近3000条道路（矢量边）的矢量文件大小只有约61K。可见矢量电子地图的优越性。8中国科学技术大学本科毕业论文22GPS实验室交通矢量地图自动生成平台介绍绝大多数GIS系统中使用的地图是以矢量地图作为其表现形式的。国内目前矢量地图常用的生成方式有两种，一种是用数字化仪从纸质地图中提取，另一种是从点位图中利用模式识别的有关理论进行识别和提取。用第一种方法生成一个准确而完备的矢量地图要花费大量的人力和财力，一个中等规模的城市用数字化仪生成矢量地图，大约需要一个月的时间。所以我们采用的是第二种方法。221系统组成我们所说的GIS往往是一个比较庞大的系统，而且包含了很多各类数据管理、决策的模块，它是一种针对性比较强的系统，对于不同的用户，往往对数据有不同的操作、管理、决策。但是它毕竟是一个以地理空间分布数据为基础的系统，所以有一个因素不能少，那就是电子地图，它为系统提供最基本的地理信息。我们如何来组织一份矢量地图呢数据是矢量地图的核心，电子地图可以看作由点、线、面这三种几何对象以及它们的属性数据构成的数据的集合，所以我们引入了地图矢量库和地图数据库这两个概念。矢量库是一组图形描述数据，保存了地图的几何数据；数据库则是一组描述数据，保存地图各种几何对象的属性数据，二者之间通过地物对象的序号建立索引关系。如下图矢量地图地图矢量库地图数据库图形数据组描述数据组序号图221矢量地图的组成一副地图可以看成是由点、线、面三种几何图形构成的。点指的是单位之类的地物实体，线则是道路、铁路之类的实体，而区划这类的实体就可以用面来表征。依照传统的习惯，把点、线、面这三类地物按照从上到下的顺序排列。生成、编辑电子地图的过程就是生成、编辑地图矢量库和数据库的过程，下面我们来介9中国科学技术大学本科毕业论文绍一下这两个最重要的库。222地图矢量库矢量库定义出几何结构的位置形状信息。点标志比较简单，只是一个点；面标志对应的几何结构就是一个多边形，也比较简单；而线标志则包含较多的内容，要相对复杂一些。我们下面主要介绍一下与线标志有关的一些定义，也就是道路的有关定义定义0矢量边。是一些点的坐标的集合，表征着一条连续的折线。它有以下的性质A点的排列顺序决定了折线的行进方向，决定了折线的形状和位置；B只有两个端点可以属于别的矢量边。定义1大节点、小节点、节点。大节点是矢量边的端点；小节点是指矢量边除端点之外的内部点；大节点和小节点统称节点。定义2弧。一条弧就是一条矢量边，是若干个节点的集合。组成弧的节点是顺序排列的。定义3路。路是若干条弧的集合。如图所示1234568小节点2、3、5、6大节点1、4、7、8弧1，2，3，4、4，5，6，7、4，8路以上的弧的任意组合均可能构成路。7图222几种拓扑结构的定义10中国科学技术大学本科毕业论文223地图数据库地图数据库中包含了各种地物的属性数据。对于面地物，需要知道的属性有类型、位置、形状、名称、颜色等；对于点地物，需要知道的属性有类型、位置、名称、显示图标、显示级别等；对于线地物，需要知道的属性有类型、位置、形状、名称、颜色、显示宽度、显示级别等；上面提到的各种地物的属性数据中都有一项类型，也就是它所属的组（GROUP）。组，定义出了某一批地物的缺省属性，是一些具有相同或相近属性的同类地物的集合。整个数据库的层次如下所示地图数据库点状地物组线状地物组面状地物组点状类地物线状类地物面状类地物点状地物线状地物面状地物DIVISIONGROUPENTITY图223地图数据库的层次地图的数据库有四个层次，最上层当然是地图数据库，它由三个部分（DIVISION）构成的，也就是点、面、线三大类地物；每个部分又由若干个组（GROUP）构成；每个组又由若干个地物实体（ENTITY）构成，实体，就是点、面、线这类的地物个体。这种分层结构使得配置地图数据库时显得特别的方便。11中国科学技术大学本科毕业论文23地图数据的结构数据是地图的核心。一副完备的电子地图的数据量是很大的，我们采用了分层的数据结构来组织这些数据，最大限度的考虑和满足用户的需要。地理数据的分层结构电子地图点状地物线状地物面状地物基本地理对象点节点弧路多边形几何对象几何数据点状地物群线状地物群面状地物群基本地理对象集图252地理数据的分层组织电子地图由基本地理对象集（点、线、面状地物集）组成；基本地理对象由几何对象（点、线、面）加上其属性数据组成，几何对象包含地理对象的几何数据，并维护对象间的拓扑关系。24矢量库的组织地图矢量库保存了组成地图的线状元素的几何数据，也就是包含了节点、弧和路的信息。它是整个电子地图和GIS系统的根本，也是我们后面实现路径寻优、动态轨迹校正等智能决策功能的基础。下面我们就来看看在这个矢量库中是如何组织这些数据的。像我们在最前面提到的，弧是节点的集合，路是弧的集合。我们可以把矢量12中国科学技术大学本科毕业论文库看成由三个表构成，一个节点的表，每一行表示一个节点，X、Y坐标组成这个表的两个列；一个弧的表，它的每一行表示一条弧，它的列是构成这条弧的点；还有一个路的表，它的每一行表示一条路，构成这条路的所有的弧是各个列。如图253所示。另外，对于一个GIS系统，不可或缺的功能就是根据地理空间信息进行一些决策，例如搜索两个给定点之间的最优路径。在前面的讨论中，我们可以看到节点、弧、路之间的关系是很密切的，因此我们提供充分的机制，使得它们之间能够顺利的相互访问。如图253所示。第1个点第2个点第N个点弧1弧2弧NA弧的表第1条弧第2条弧第N条弧路1路2路NR路的表弧到路的索引弧所包含的点包含这点的弧所包含的弧某一条弧某一个点某一条路XY点1点2点NC节点的表图253地图矢量库的组织25交通矢量地图的生成要生成一副交通矢量地图，首先是生成地图的矢量文件，生成矢量地图的拓扑结构矢量库。我们采用的是从点位图中识别、生成矢量地图的方式。我们将从纸制地图扫描得到的点位图进行识别，提取出其中的道路信息，然后将这些道路信息矢量化得到一副只包含道路信息的矢量文件，将这作为一副矢量地图的基础。然后，在这个基础上进行编辑、校正，并输入各种地图上的有关数据，生13中国科学技术大学本科毕业论文成电子地图的数据库，最终生成一个完整而准确的矢量地图。如下图所示彩色地图识别地图矢量化软件MAPHANDLE矢量地图编辑软件MAPEDITOR彩色地图线状的黑白位图矢量文件GPS或GIS应用系统完整而准确的矢量地图矢量库和数据库图231交通矢量地图的生成从上面的框图中我们可以看出生成一副较完备矢量交通地图，主要包括以下三个步骤彩色地图的道路识别；地图矢量化；矢量地图的校正和地图信息的添加；彩色地图的道路识别，就是根据一幅彩色交通地图，利用一定的算法，提取出其中的道路、区域信息，形成一幅黑白位图。地图矢量化则是根据得到的线状的黑白位图抽取出有意义的模式特征。矢量化后的地图经过校正和添加地图信息就可以很好的应用于我们的监控和导航系统了。在这篇文章中我们主要研究一下平台的校正功能部分。1514中国科学技术大学本科毕业论文第三章交通矢量地图的传统校正算法在智能车辆监控、导航系统中，我们要随时跟踪并准确地显示车辆的位置，因此我们必须给GPS智能车辆监控、导航系统提供一幅良好的矢量地图。从GPS卫星收到的信号是车辆当前的经纬度，我们要把车辆的位置准确的显示在地图上，有两个要求其一要求道路之间的相对位置是准确的；其二就是在地图坐标和地理坐标之间建立一种准确的映射关系。我们采用的交通矢量地图的图源是规范化的城市公路交通图。它的一个基本特点是可能局部或大面积变形，但其上面的有限个关键点（道路的交叉点、道路在边界上的终端点以及弯曲道路的拐弯点）之间的相对方位（不是相对距离）应是正确的。意思是城市公路交通图不可能把交叉路口A的东北处的交叉路口B错印到交叉路口A的西南，上面（右边）一条路不可能错印成下面（左边）一条路。这样，就保证了第一个要求，即道路之间的相对位置是准确的。本章我们主要介绍如何在地图坐标和地理坐标之间建立一种准确映射关系的传统方法，即如何对一幅矢量化后的地图进行有效的校正。31交通矢量地图的误差分析一般来说，矢量化后的交通地图一般都和实际的车辆轨迹存在着一定的偏差，导致这一现象的原因主要有三点矢量地图的数据是通过对栅格地图矢量化而得到的，因此就存在地图比例尺问题；矢量化过程中的局部偶然误差也是误差的一个来源；当然栅格地图（图源）本身的误差更是误差的主要来源，它将完全带入矢量化后的矢量地图中。下面我们给出两个示例15中国科学技术大学本科毕业论文图311校正前的合肥市矢量地图和实际的车辆轨迹图312校正前的上海市矢量地图和车辆轨迹从图311中我们可以明显看出矢量地图和实际的车辆轨迹之间存在着一个放缩和平移的关系，而在图312中，矢量地图和实际的车辆轨迹之间有旋转，当然在这两幅地图中都存在局部的误差。32矢量地图的线性定标在进行校正算法的分析与设计之前，我们必须首先了解两种坐标系统地图坐标和地理坐标。地图坐标是指地图上某一个点在地图上显示的坐标位置，我们用来表示；地理坐标是指这个点的经纬度坐标，我们用YX，LATLON，来表示。下16中国科学技术大学本科毕业论文面我们将介绍一下传统的矢量地图线性定标方法以及整体校正算法。321线性定标的原理传统的矢量地图地理位置定标只要使用不在同一经度或同一纬度上的两个点的精确位置的经纬度数据，就可以唯一地确定地图上所有节点的坐标，方法如下矢量地图某一点的精确地理坐标记为，地图坐标到地理坐标的放大倍数记为，设地图坐标系和地理坐标系之间的夹角,YXPSCALEX,LATLONG,YL,YX,LATLONSCALEY，XL，顺时针方向为正，地图上的某点对应的实际的经纬度为。如下图所示,00YXP,00LATLONGLONLATYXPX0,Y0GLON0,LAT0PX0,Y0GLON0,LAT0图321两种坐标体系示意图显然有0000COSSINSINCOSYXLATLATLLONLONLYXYX212211CCLATLONBABA系数向量的关系式为YXLLBABA00COSSINSINCOS2211000021COSSINSINCOSYXLATLLONLCCYX实际上，即使我们不知道的地理坐标、与,00YXP,00LATLONG，由于地图坐标系YX，,11LAT是整数定标的矢量地图节点的位置点阵坐标，只要我们设定出相应的地图放大比例尺,并已知地图任意两点与精确的经纬度与，上述公式已经唯一地确定出矢量地图任一点与其精确地理坐标的一一对应关系。上式的算法也说明，只要通过全局一次性旋转与放缩变换算法，我们就完成了总体校正。新的矢量地图以新的点阵分布，直接显示成地理坐标系。,YXLL,22LATLON,LATLONG1Y,2YXP,1XP2LONGGG,YXPLAT,LON17中国科学技术大学本科毕业论文322线性定标的缺陷矢量地图地理位置定标的结果，地图的精度完全取决于图源的精度，即要求原始未定标的矢量地图不存在全平面上的非线性误差。并且由于矢量地图的线性定标只用两个点的精确位置数据，当所取的两个校正点的位置存在一点点误差，就可能产生整幅地图的较大误差。克服两点精度误差影响的办法是采用多个校正点的整体校正算法，如最小二乘法、DFP变尺度法等。33矢量地图的整体校正算法331整体校正算法的基本原理矢量地图是由一系列节点以及它们之间的拓扑关系组成的，节点之间的拓扑关系唯一地决定了一幅矢量地图。矢量地图的节点数目是有限的，任意两个节点之间总是分开（有距离）的，并且只存在孤立节点与非孤立节点两类。矢量地图上的线（交通路线与区域边界线）由连接非孤立节点的线段构成。表示某一地理单位的孤立节点则总是包围在某个闭合的区域或闭合路线范围内。对地理信息系统GIS，节点之间的拓扑关系简言之，就是矢量地图上非孤立节点在其构成的线上的相邻序号关系总是不变的，孤立节点位于其所在的闭合区域范围内的规则总是不变的，但节点之间的相对距离关系可以存在误差。我们对矢量地图的校正就是在不改变节点之间拓扑关系的前提下，使用尽可能少的已知校正点的矢量地图位置与地理经纬度之间的对应位置关系信息，获得所有节点位置尽可能精确的调整。取待校正矢量地图上已知精确位置信息的N个点作为校正点。这N个点在矢量地图节点坐标数据库中的位置矢量记为,22211121NNNNNYXPYXPYXPPPPPLL其中校正点,IIIIYXPPNI,2,1在当前矢量地图节点坐标数据库的点位置坐标为。而这N个点在显示的矢量地理地图（已确定比例系数，坐标对应原点经纬度及方向角，参见前节）上的位置经纬度表示为IY,IXNP,000YXP,YXLL18中国科学技术大学本科毕业论文NNGGGG,21,111NNNLATLONGLATLONGL其中校正点在显示的矢量地理地图上的位置经纬度表示为IP,IIIILATLONGGNI,2,1类似地，我们把矢量地图节点坐标数据库中所有节点（设共有为个）记为L,22211121LLLLALLYXNYXNYXNNNNNL而所有节点在显示的矢量地理地图上（加进节点之间的拓扑关系，可视为矢量地图图廓）表示为ALLN,22211121LLLLALLYXMYXMYXMMMMML现在已知这N个校正点的地理经纬度的精确位置是NP,11NNNLATLONLATLONGL也就是说对应在矢量地图节点坐标数据库中准确的位置矢量是已知的，记为NG,2211NNNYXYXYXPL矢量地图的完全校正，就是要找到线性映射关系M，把映射成NPNP,2211NNNNYXYXYXPPML但对线性变换，这通常是不能实现的。通常所说的矢量地图校正，就要找出线性映射关系，把映射成，即MMNPNP,2211NNNNYXYXYXPMPL等价于把映射成GNGN,11NNNNLATLONLATLONGMGL使得与之间偏差最小，等价于与偏差E最小。偏差的误差函数取为NPNPNGNG11NNNIINIINNPPKEKEGGE式中K为常数不影响优化过程，距离函数22IIIIIIILATLATLONLONGGE22IIIIIIIYYXXPPE19中国科学技术大学本科毕业论文获得线性映射关系后，对矢量地图所有节点（对应地图图廓）执行同样的变换。可以预期变换后的矢量地图所有节点（对应校正后的地理地图图廓）与准确的矢量地图所有节点（构成准确的地理地图图廓M）的偏差也会达到最小。从而完成矢量地图校正的过程。MALLNNALLMALLALLALLMALLN直观地说，矢量地图校正的过程，本质上就是改变矢量地图节点坐标数据库的所有节点数据，尽可能地用接近于其准确位置的新数据来替代。值得特别说明的是虽然我们用到的只是N个点的精确数据，但只要这N个点是分散在地图平面上，由于矢量GIS地图保持所有节点之间拓扑关系这一基础特性，由这N个点的校正数据完全可能推算出其它节点的校正规则，且这种校正规则至少对位于这N个点的N个邻域上的所有节点的修正是足够有效的。ALLNALLNALLN332整体校正算法的局限性所有的矢量地图整体线性校正算法的一个明显的局限性是不能校正原矢量地图存在的非线性误差。上节所给出的矢量地图线性校正算法只是均匀地（即使改变最优指标为加权最小二乘，也是本质均匀地）使用已知的N个点的精确数据信息，一个明显的结果就是，这N个点校正的结果一定不会在这N个点的准确位置上，除非原图完全不存在非线性误差。地图存在的非线性误差，形象化地说，就好比地图的幅面遭受过揉捏，平面有些变形，其上有些块面积变大，同时有些块面积变小，虽然这些变形块的出现不足以破坏到整幅矢量地图节点之间的拓扑关系，但这些变形块的分布与局部面积的变形则是毫无规则而言。很明显，即使可以用来校正的精确点数目很多，这种计算机自动进行的矢量地图整体线性校正过程也无法克服这一局限性。目前实际解决这一问题的办法就是手动逐点校正，也就是人工移动节点至其精确位置，其耗时耗力，不亚于重绘地图。在原矢量地图不存在非线性误差时，线性整体校正算法看起来已经尽善尽美，但我们注意到，就校正后的矢量地图整体位置误差，不可能低于矢量化前的纸质栅格地图图源的整体位置误差。纸质地图本身的误差在地图矢量化后转变成矢量地图基于节点的拓扑结构的误差（实际上也构成了矢量地图的非线性误差）。纸质地图图源的比例关系限定了其允许的整体位置误差。例如110万比例尺地图，以02MM的点、线可视分辨率栅格图形计算，其固有的整体位置误差为100M。由于你选取N个校正点的过程中已经包含了02MM位置传感（或100米地理坐标）的固有误差，线性校正的结果，当然不可保证获得更高的精度。这点可20中国科学技术大学本科毕业论文算是线性校正算法存在的另一个局限性，至少和手动逐点校正方法相比如此。手动逐点校正方法虽然原始，但具有修正非线性误差的功能，只要不怕耗时耗力，人工移动所有节点至其精确位置，校正后的地图的位置精度当然可以不受原矢量地图整体位置误差的限制。21中国科学技术大学本科毕业论文第四章矢量地图的离散非线性校正在第三章，我们介绍了经过一次性全局变换来校正地图的整体校正算法。无论从理论上，还是实际的校正效果来看，整体校正算法（最小二乘法，变尺度法等）只能达到全局的最优，而无法使得局部也达到最优的效果。尤其，对于矢量地图中存在的非线性误差，使用这种方法，无法进行有效的校正。由此，我们有必要采用一种新的校正方法，来弥补这方面的缺陷。这就是我们要研究的离散非线性校正算法。该算法是由中国科学技术大学自动化系00届研究生王国江首先提出，并进行了程序实现，用于交通矢量地图自动生成平台的自动校正部分。矢量地图离散非线性校正算法的“离散”，或者说“分块”，它是同时针对矢量地图整体线性校正算法的“整体”和手动逐点校正过程的“逐点”而提出的。针对矢量地图整体线性校正算法只能获得全局最优，新算法企图进一步达到任意“分块”的局部区域最优校正。针对手动逐点校正过程每次一个矫正只能校正一个节点位置，新算法企图“以点带面”，达到整个“分块”内的局部区域优化校正。41算法的思路离散非线性校正算法的整个思路描述如下1整个校正过程由N个已知精确位置的校正样本点的累加校正过程组成。每个校正样本点及其邻近区域组成了一个分块区域，我们称之为一个离散块。每个校正过程只进行这个离散块内的所有矢量节点的位置校正。这里用到了“离散”的概念及使用线性系统离散建模与遵循离散线性系统理论。2离散块中的校正算法选择，首先是基于该校正样本点校正前后的两个坐标数据的差值，即位置的移动，以及矢量地图节点网络拓扑关系不变原理下由校正样本点移动可以获得的该离散块中所有其它节点的相应移动数据。另外，要遵循整幅地图离散建模或保证所有离散块之间的无缝衔接，离散块中的校正算法必须保证块边缘上的节点位置不变。所以离散块中的校正算法不可能是简单的线性变换，一定是某类非线性校正算法。新算法引入“非线性”的概念及满足该变换的边界条件，即保证22中国科学技术大学本科毕业论文任何时刻全平面的无缝连接。3校正过的样本点在以后的校正过程中位置保持不变。这也是该算法确定离散或“分块”的唯一原则。因此，算法中的“离散”概念不是一个对地图平面上的静态离散（对比离散线性系统理论中离散概念仅是时间上的静态离散）,而是基于地图平面上随时刻（已校正点数）而不同的动态离散概念。算法确定的“分块”原则是在每一新校正样本点校正前，在该时刻的校正结果形成的整体地图平面上进行，以保证校正过的样本点不动，不仅不要考虑历次分块的状况，而且应该选择以校正样本点为核心（不是中心）尽可能大的分块区域。可以推知，随K增大，不动点的增多，则新的非线性校正的离散块必将越来越小。形象地说，以时间回顾，K层离散块是重重叠叠又交错的分布在时间轴上；以地图平面回顾，一张遭受过揉捏过的矢量地图幅面，如同平面保持但又挤压变形的柔性铁丝网经历多次的单点牵拉定位。42离散块的选择首先，这里把离散非线性校正算法中涉及当前一步的校正样本点，离散块等的定义与表达符号再明确如下。按照上节“动态离散”概念的分析，这里的定义均强调是基于“当前”状态，即校正过程已完成了第1,2,K个校正样本点，当前准备使用第K1校正样本点,在第K1“离散块”中进行该块中所有节点位置的调整。记第K1校正样本点为或，它在当前矢量地图节点坐标数据库的数据为；它当前显示在矢量地理地图上的经纬度为，它在矢量地图节点坐标数据库的数据（准确位置）将要修改为，因为它的精确的地理经纬度是。注意，我们把正待确定的第K1离散块记为，该块中所有节点记为（节点数据库值）或地图显示值。本节主要讨论当前如何定义第K1个离散块。KP11KG1KS1K1KN1KPG1KPKS1KP1KG1KS1KN1KM1既然校正过程已进行到完成了K个校正样本点，确定唯一的限制条件就是确保校正过的样本点1KS,211KKGGGG不再移动位置。或者从相应的矢量地图节点坐标数据库方面说，这K个校正样本点的当前数据1KGKP123中国科学技术大学本科毕业论文,2111KKKPPPPP不再改变,保持其精确值。1KP考虑到已校正的这K个样本点已被固定在它们精确的位置上，它们七零八落地分布在地图平面上，对以后的校正，它们的总体布局是确定边界的决定因素。所以我们分析每个已校正样本点1KG1KSIIPPKI,2,1对的限制。由上节单点牵拉定位的思路，单个已校正点I（显示为）对选择范围的限制。图2中，位于过的的垂线将平面分成两个半平面，记第K1校正点所在的那一半平面为。1KSPIG1KSIGIKGG1IH1KG图42离散块的选取综合已完成的K个校正点对的限制，我们得到1KSIKIIKHS1143算法的具体实现下面的叙述涉及视觉效果的内容是以计算机屏幕上所显示出的矢量地图为准的。矢量地图的显示必须先确定矢量地图定标比例系数SCALEYSCALEX，坐标对应原点经纬度及方向角。我们的矢量地图自动生成平台采用的是GPS道路轨迹自动完成矢量地图初始定标过程。在这个轨迹自动定标之后，才开始校正算法的步骤。下面说明中涉及每一新校正样本点的数据输入操作，并不需要键盘输入数字，而是直接在屏幕矢量地图上用鼠标点取该点在校正前和校正后的位置完成的。点取该点校正后的精确位置，实际上就是获取位于该点的GPS轨迹记录，自动完成该点精确位置经纬度数据的输入。下面是离散非线性校正算法的具体实现步骤,00YXP24中国科学技术大学本科毕业论文步骤1,2两点定标矢量地图最小校正系统步骤1选取第1校正点1G,11111111YXPPLATLONGG，本文中符号表示对应或等价关系，是通过鼠标点取获得的，实际的操作是修改存取数据库中的。IGIP离散块为全平面，点取矢量地图上该点指向其精确的轨迹点1S1G1G,11111111YXPPYXGG。实际显示变化为平移地图平面，G移位于。内部的操作是矢量地图节点坐标数据库的所有节点数据均已作了相应的平移修改校正。11G,YXNALL步骤2选取第2校正点，离散块为除固定点外的全平面，点取矢量地图上该点指向其精确的轨迹点。实际显示变化为地图平面绕作了一次旋转与放缩变化。内部的操作是矢量地图节点坐标数据库的所有节点数据均已作了相应的旋转与放缩修改校正。2G2S1G2G2G1G,YXNALL说明矢量地图校正全过程至少需要使用不在同一经度或同一纬度上的两个点的精确位置的经纬度数据。不论用何种校正算法，在仅能使用两个校正点的情况下，均自动蜕化成为计算过程完全等价的矢量地图两点定标过程。从这个意义上，我们把仅使用两个校正点的矢量地图离散非线性校正过程定义为最小校正系统。本质上的矢量地图离散非线性校正过程，是从第三校正点开始。步骤K（K3）离散块中所有节点的非线性校正过程KS情况1为有限区域KSKS为有限区域的情况可由图332说明，这里仅给出了三角形的情况，KS其它情况可以此类推。这种情况的等价描述为为一凸M多边形,与位于凸M多边形内。I11KIIKHSKGKG25中国科学技术大学本科毕业论文图431离散块内部的映射关系示意图KS图中，已经完成的校正点，G，G，G所产生的分别垂直于，G，的4条直线靠侧的4个半平面，的交集构成的三角形ABC形成离散块。点取矢量地图上该点指向其精确的轨迹点。本次变换的核心，也是移动距离最大的点就是变换成。从而内非线性变换关系可分解成M3对三角形的非线性映射，记为IGKMNLIKGGKSMKGKGNKGGLKGGMGKIHKGMHKGNHKGLHSM。就本例即ABGMABGKKBCGMACGKKCAGMCAGKK。下面我们用图例来说明映射关系M图432三角形之间的映射关系在上图中，G变换到，G是三角形内部的任一点。假设经过KKGIABGKIGM映射