（模式识别与智能系统专业论文）矢量地图拓扑校正及其在gis系统中的应用.pdf

摘要 摘要 数字时代需要数字地图 我国目前数字地图生成依赖于国外技术 其中对矢 量地图的位置校正仅提供基于仿射变换 平移 旋转和放缩 的整体线性校正功 能 实现矢量地图的离散非线性校正 是基于平面点集拓扑及误差校正理论探索 与应用研究的重大课题 不仅可以填补数字地图生成平台的这一技术空白 并将 极大地降低数字地图生成成本 基于上述背景 本论文对实验室已经完成的矢量 地图校正软件平台上的离散非线性校正算法进行完善与改进 使之严格满足拓扑 变换的要求 具有重要的理论意义与实用价值 矢量埘图校正的本质 就是在不改变节点之间拓扑关系的前提下 使用尽可 能少的样本点对的地图位置信息与对应的精确地理位置信息 通过样本点对校正 前后的位置变化 获得矢量地图平面内所有节点位置尽可能的精确调整 论文简单介绍了实验室已经完成的离散非线性校正算法 在肯定它是矢量地 图校正理论与实践上一个本质性的重大进步的同时 依据平面点集拓扑结构理 论 深入分析了其在理论上的缺陷和在算法与软件实现上的三点基础性不足 结 合拓扑学的有关知识 给出了有理有据的改进方案 形成了比较完善的更有效实 用的矢量地图拓扑校正算法 论文同时将校正后的矢量地图用于实际 设计和完 成了基于w e b g i s 与g p r s 的 个人g i s 助理系统 包括软硬件设计与实现 论文的创新之处在于对原算法及其软件实现上的三处改进 1 将原算法在数字地图整数域空间上的变换过程修正改进为实数平面上的 严格意义上的拓扑变换过程 同时也解决了积累误差问题 2 通过增加离散块边界节点的手段实现了拓扑变换过程中的离散块边界的 无缝连接 3 依据校正点信息 自动修正矢量显示地图的原点经纬度坐标 实现了拓扑 变换过程中地图幅面的自动平移 保证了矢量地图所有节点变换前后的完整性 关键字 地理信息系统 智能交通 矢量地图 拓扑变换 离散非线性校正 a b s t r a c t a b s t r a c t t h ed i g i t a la g en e e dd i g i t a lm a p c h i n a sc u r r e n tg e n e r a t i o no f d i g i t a lm a p sr e l y o nt h ef o r e i g nt e c h n o l o g i e s a n dd u r i n gt h e s et e c h n o l o g i e s t h et e c h n o l o g yu s e df o r l o c a t i o nc o r r e c t i o n so ft h ev e c t o rm a po n l yp r o v i d ea f f i n et r a n s f o r m a t i o n t r a n s l a t i o n r o t a t i o na n ds h r i n k a n dt h eo v e r a l ll i n e a rc o r r e c t i o n t h ef u l f i l l so ft h ed i s c r e t e n o n l i n e a rc o r r e c t i o ni sav e r yi m p o r t a n tp r o b l e mb a s e do nt h ep l a n ep o i n ts e t t o p o l o g ya n dt h ee x p l o r a t i o na n da p p l i e dr e s e a r c ho fe r r o rc o r r e c t i o nt h e o r y i tc a nn o t o n l yb r i d g et h ed i g i t a lm a pg e n e r a t i o np l a t f o r mf o rt h i st e c h n o l o g yg a p a n dg r e a t l y r e d u c et h ec o s to fg e n e r a t i o no f d i g i t a lm a p s a g a i n s tt h ea b o v eb a c k g r o u n d t h i s p a p e ri m p r o v eo nt h ev e c t o rm a pc o r r e c t i o ns o f t w a r ep l a t f o r mw h i c ht h el a bh a sb e e n c o m p l e t e dt om a k ei tm e e tt h en e e do ft h et o p o l o g yt r a n s f o r ms t r i c t l ya n dh a v et h e t h e o r ys i g n i f i c a n c ea n dp r a c t i c a lv a l u e t h en a t u r eo ft h ec o r r e c t i o no ft h ed i g i t a lv e c t o rm a pi su s i n gt h el o w e s tn u m b e r o fs a m p l ep o i n t so nt h em a pl o c a t i o ni n f o r m a t i o na n dt h ec o r r e s p o n d i n g p r e c i s e l o c a t i o ni n f o r m a t i o nt og e tt h ee x a c tl o c a t i o no fa l lt h en o d e sa sf a ra sp o s s i b l eu n d e r t h ep r e m i s eo fn o tc h a n g i n gt h et o p o l o g i c a lr e l a t i o n sb e t w e e nt h en o d e s t h ep a p e rs i m p l yi n t r o d u c et h ed i s c r e t en o n l i n e a rc o r r e c t i o na l g o r i t h m sw h i c h t h eg p sl a bh a sb e e nc o m p l e t e da n d a n a l y z et h ei m p e r f e c t i o no f i t st h e o r ya n dt h r e e s h o r t a g e so ft h es o f t w a r eo nt h eb a s eo ft h ep l a n ep o i n ts e tt o p o l o g ym a dt h e a f f i r m a t i o nt h a tt h ea l g o r i t h m sm a k e sg r e a tp r o g r e s si nt h ec o r r e c t i o no ft h ed i g i t a l m a pb o t ht h e o r e t i c a l l ya n dp r a c t i c a l l y c o m b i n e dw i t ht h er e l e v a n tk n o w l e d g eo f t o p o l o g y g i v e saw e l l f o u n d e d s c h e m ea n df o r m sam o r ee f f e c t i v ea n dp r a c t i c a la l g o r i t h mo ft h ev e c t o rm a p g r a p h i c s t o p o l o g yc o r r e c t i o n t h ep a p e rm a k e st h ed i g i t a lm a p su s e di nt h ea c t u a ld e s i g na n d c o m p l e t e st h ew e b g i sa n dg p r s b a s e d p e r s o n a lg i sa s s i s t a n ts y s t e m i n c l u d i n g h a r d w a r ea n ds o f t w a r ed e s i g na n di m p l e m e n t a t i o n t h ep a p e ri m p r o v e st h eo r i g i n a la l g o r i t h ma n ds o f t w a r ei nt h r e ea r e a sa sf o l l o w s 1 a m e n d m e n ta n di m p r o v et h ep r o c e s so ft r a n s f o r m a t i o nb yu s i n go r i g i n a la l g o r i t h m o nt h ed i g i t a lm a pt ot h es t r i c ts e n s eo ft o p o l o g yt r a n s f o r m a t i o np r o c e s so fr e a lp l a n e a n ds o l v i n gt h ep r o b l e mo fa c c u m u l a t e de r r o r 2 r e a l i z et h ed i s c r e t eb l o c k s s e a m l e s sl i n k so ft h et o p o l o g yt r a n s f o r m a t i o np r o c e s s b ya d d i n gt h eb o r d e rn o d e so fd i s c r e t eb l o c k 3 b a s e do nt h ei n f o r m a t i o no fa d ju s t e dp o i n t s a d j u s t i n gt h el a t i t u d ea n dl o n g i t u d e i i a b s t r a c t c o o r d i n a t e so nt h ev e c t o rm a pa u t o m a t i c a l l y i m p l e m e n t i n gt h em a pa u t o m a t i c a l l y t r a n s l a t ei nat o p o l o g yt r a n s f o r m a t i o np r o c e s st oe n s u r et h ei n t e g r i t yt h a ta l lt h en o d e s o ft h ev e c t o rm a pb e f o r ea n da f t e rt h et r a n s f o r m a t i o n k e yw o r d s g i s i t s d i g i t a lv e c t o rm a p t o p o l o g y d i s c r e t en o n l i n e a rc o r r e c t i o n 1 1 1 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文 是本人在导师指导下进行研究工作 所取得的成果 除已特别加以标注和致谢的地方外 论文中不包含任 何他人已经发表或撰写过的研究成果 与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明 本人授权中国科学技术大学拥有学位论文的部分使用权 即 学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版 允许论文被查阅和借阅 可以将学位论文编入有关数据库进行检 索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后也遵守此规定 作者签名 玛扔昏 肘弋 户 y 多h y 年乜 彬纠杪 第1 章绪论 第1 章绪论 全球卫星定位系统 g p s 与地理信息系统 g i s 是智能交通系统 i t s 中的两个重要的理论支柱 本章首先从它们的基本概念入手 分析它们之间的相 互关系 并介绍一种矢量地图自动生成校正平台 它使用较低精度的图源同样能 获得满足智能交通系统应用要求的矢量地图 由此指出矢量地图自动校正的重大 意义以及它在地理信息系统和智能交通系统应用中的重要地位 1 1g p s gis 与智能交通 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 的简称 它的含义是 利用导航卫星进行测时和测距 为人类在全球范围内提供定位服务 李天文 2 0 0 3 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 是集计算机科学 地 理地质学 测绘科学 环境科学 空间科学 信息科学和管理科学等为一体的多 学科结合的新兴边缘科学 邬伦 张晶 赵伟 2 0 0 2 也是一种同时管理地理 空间信息和数据库属性数据的信息系统 首先 g i s 是一种计算机系统 它具备 一般计算机系统所具有的功能 如采集 管理 分析和表达数据等功能 其次 g i s 处理的数据都和地理信息有着直接或间接的关系 地理信息是有关地理实体 的性质 特征 运动状态的表征和一切有用的知识 而地理数据则是各种地理特 征和现象间关系的符号化表示 包括空间位置 属性特征及时域特征三部分 空 间位置数据描述地物或现象所在位置 属性数据有时又称作非空间数据 是属于 一定地物或现象 描述其特征的定性或定量指标 时域特征是指地理数据采集或 地理现象发生的时刻或时段 另外 从地理信息系统在实际应用中的作用与地位来看 目前对地理信息系 统的认识可归纳为三个相互独立又相互关联的观点 一是地图观点 强调地理信 息系统作为信息载体与传播媒介的地图功能 认为地理信息系统是一种地图数据 处理与显示系统 每个地理数据集可看成是一张地图 通过地图代数实现数据的 操作与运算 其结果仍然表现为一张具有新内容的地图 测绘及各种专题地图部 门非常重视地理信息系统的快速生产高质量地图的能力 第二种观点称为数据库 观点 多为具有计算机科学背景的用户所接纳 强调数据库系统在地理信息系统 中的重要地位 认为一个完整的数据库管理系统是任何一个成功的地理信息系统 不可缺少的部分 第三种观点则是分析工具观点 强调地理信息系统的空间分析 第1 章绪论 与模型分析功能 认为地理信息系统是 n 空间信息科学 第三种观点普遍地为 地理信息系统界所接受 并认为这是区分地理信息系统与其它地理数据自动化处 理系统的唯一特征 陈述彭 1 9 9 9 智能交通系统 i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m 简称i t s 是将先进的信 息技术 数据通讯传输技术 电子传感技术及计算机软件处理技术等有效的集成 运用整个地面交通管理系统而建立的一种在大范围内 全方位发挥作用的高效 便捷 安全 环保 舒适 实时 准确的综合交通运输管理系统 是一种提高交 通系统的运行效率 减少交通事故 降低环境污染 信息化 智能化 社会化 人性化的新型交通运输系统 孙文彬 岑敏仪 郭淳 2 0 0 2 它将有助于最大 程度的发挥交通基础设施的效能 提高交通运输系统的运行效率和服务水平 为 公众提供高效 安全 便捷 舒适的出行服务 i t s 涵盖了所有的运输方式 并 考虑运输系统动态的 相互作用的所有要素 人 车 路以及环境 i t s 的总 体功能是通过改进 通常是实时地 交通网络的管理者和其他用户的决策 从而 改善整个运输系统的运行 目前 世界发达国家都在投入巨资进行大规模的i t s 建设 美国是应用i t s 较为成功的国家之一 1 9 9 5 年3 月 美国交通部出版了 国家智能交通系统项 目规划 明确规定了智能交通系统的7 大领域和2 9 个用户服务功能 并确定了 到2 0 0 5 年的年度开发计划 7 大领域包括出行和交通管理系统 出行需求管理 系统 公共交通运营系统 商用车辆运营系统 电子收费系统 应急管理系统 先进的车辆控制和安全系统 另外日本也早在1 9 7 3 年就开始了对智能交通系统 的研究 它的i t 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 格式的地图及信息数据库结合在一起 并 能接收调频无线电广播发送的交通流量信息 另外 许多大公司 如奔驰日本公 司 丰田 本田等 都在积极开发自己的导航信息系统 拓展导航信息服务市场 在美国 有多个公司已研制或正在研制轿车导航系统 克莱斯勒公司研制了一种 2 第1 章绪论 基于g p s 的车辆导航系统 该系统在失去卫星信号后 可用计程器工作 保持 车辆继续导航 威斯汀豪斯公司研制了自动车辆定位系统 安装在城市公共汽车 和轻轨火车上 在欧洲 1 9 9 5 年 法国巴黎的公共汽车率先使用车辆调度和导 航系统 可以看到 相对于车辆导航和监控而言 专注于个人用户的导航产品就显得 稀少很多 本文的第四章将介绍一种个人g i s 助理系统 它专门针对老人和儿童 这些相对弱势群体开发 为他们提供导航 监控和报警等服务 解决用户的实际 困难 交通技术的发展与电子技术 通讯技术 计算机技术等高新技术的发展息息 相关 而这些高新技术同时也是实施 数字地球 战略必须着重发展的技术 仝 培杰 1 9 9 8 可以毫不夸张的说 智能交通将是 数字地球 战略发展的最大 受益者之一 同时也是实施 数字地球 战略的一个重要组成部分 1 2 矢量地图自动生成校正平台简介 如何以较小的代价生成一幅精确实用的矢量地图 如何以最快的速度实现 矢量地图的自动化生产 则是一项具有重大实践意义的挑战 g p s 实验室自成 立以来 一直致力于数字地图 智能交通方面的研究 并在上述领域取得了突 破性的进展 形成了一套具有自主知识产权的矢量地图自动生成校正平台 本 平台中使用交通印刷地图作为图源 数据使用现场采集的g p s 道路轨迹 通过 矢量地图自动生成校正平台的道路自动提取 矢量格式转换 位置自动校正三 大环节 获得一幅基本可用的矢量交通地图 它的结构方框图如图1 1 1 所示 其中的矢量交通地图自动生成校正平台包括3 个功能模块 用双线方框表 示 1 栅格地图道路网络自动提取 2 交通地图道路网络矢量化 3 矢量地图位置精度自动校正 完成的矢量地图 再由生产者或用户添加地理属性数据及单位信息内容 构成数字交通地图 方框图中最下面的两个单线方框表达的就是数字交通地图 的用户使用过程包括信息更新过程 直接在数字交通地图用户界面上进行 第1 章绪论 道路网络提取软件r o a d e t r a c t 道路网络黑白位图 a d j u s t 数字地图再校正 数字交通地图用户界面 信息添加 i i数字交通地图 已定标校正后的矢量地图 g p s 或g i s 应用系统 监控 导航 交通管理 物流运输 用户 图1 1 1 数字交通地图的自动生成校正平台 1 3 矢量地图自动校正的意义和研究现状 上述矢量地图的自动生成平台使用较低精度的图源 彩色印刷地图 通过 各种处理获得能够满足g i s 应用要求的矢量地图 由于图源的精度问题和处理过 程中的误差 势必造成初步得到的矢量地图存在大量随机误差和系统误差 所 以校正的环节必不可少 其意义主要表现为以下两点 1 大幅度减小地图扫描与矢量化的工作量 地图图层提取是地图矢量化的基础 通过图层提取可去除遥感图像或栅格地 图中的9 9 以上的冗余信息 并同时获得数字交通地图所需要的涉及地物位置 与地理单元之间的全部空间拓扑关系 建立矢量数据库 矢量数据库是数字地图 的灵魂 是数字地图区别于一般测绘地图的本质所在 矢量数据库存储文件的大 小可能只是产生它的遥感图像或栅格地图的几百分之一 使用目前流行的商用数字地图生成平台软件 生成矢量地图的位置精度取决 于扫描地图图源的分辨率与精度 由于商用数字地图平台软件所生成矢量地图的 位置精确度取决于其用于图层提取的测绘地图的标定精度 为了保证地图精度 必须使用大比例尺幅面的遥感图像或测绘地图来扫描 导致制作一个中等城市的 矢量地图动辄需要投入数百万的资金及大量的人力 即使是专用的交通矢量地图 的生成成本也是价格不菲 据统计 其中用于地图图层提取环节 基本采用的是 交互式矢量化手段 一般占整个系统建设成本的5 0 8 0 2 大为降低数据采集与手动校正的工作量 使用g p s 轨迹实现自动校正的矢量交通地图生成平台 并不要求现场采集 4 第l 章绪论 所有的g p s 道路轨迹 只需要少量的框架式的道路或位置轨迹数据 自动校正 过程中对每一采样点的位置校正能够实现该点所在局部区域的自动矫正 因此 只要所采集g p s 道路或位置轨迹 能够较均匀地分散在地图上 即使数据很有 限 也能获得很好的校正效果 目前对矢量地图的校正大概有四种方法 即 人工逐节点校正 三角网分块 校正 韩晶等 1 9 9 9 整体线性校正和离散非线性校正 人工逐节点校正 顾 名思义 就是人为的将待校正地图上的所有节点调整的其准确的位置上 这样做 能够最大化校正精度 但缺点也显而易见 费时费力 且制作成本高 三角网分 块校正是在全图大部分误差较小的区域不增大误差的同时 减小误差较大区域的 误差 达到数据校正的目的 其主导思想在于对目标图中的采样点进行分块 然 后针对每一个分块分别计算其校正系数进行校正 后面的两种方法 整体线性校 正和离散非线性校正都属于自动校正方法的范畴 他们可以利用选取样本点的方 法 根据样本点校正前后位置的变化 获得一定的校正规则 自动把地图上的节 点校正到其准确位置上 本文所重点介绍的拓扑校正算法就是吸取了这两种方法 的长处 并结合本人的研究工作 所提出的一种新型矢量地图校正算法 1 4 论文安排 论文首先简单介绍了实验室已经完成的离散非线性校正算法 在肯定它是矢 量地图校正理论与实践上一个本质性的重大进步的同时 依据平面点集拓扑结构 理论 深入分析了其在理论上的缺陷和在算法与软件实现上的三点基础性不足 结合拓扑学的有关知识 给出了有理有据的改进方案 形成了比较完善的更有效 实用的数字地图矢量图形拓扑校正算法 论文同时将校正后的矢量地图用于实 际 设计和完成了基于w e b g i s 与g p r s 的 个人g i s 助理系统 包括软硬件 设计与实现 具体安排如下 第一章首先对一些基本概念进行了简单的介绍j 包括矢量地图校正的重大意 义 矢量地图自动生成校正平台简介 自动校正算法的研究现状以及矢量地图在 地理信息系统中的应用情况 第二章是拓扑校正算法综述 从矢量地图的误差分析出发 详细阐述了矢量 地图的校正本质和要求 并对已有的整体线性校正和离散非线性校正的原理进行 了简要的介绍 提出了算法中存在的问题 第三章涉及算法拓扑不变性的研究 针对应用中出现的三类主要缺陷 如何 在实数平面上的实现拓扑变换 离散块边界无缝链接问题和如何实现地图幅面自 动平移等问题分别给出了原因分析 改进思路和改进方法 这些改进措施在理论 第1 章绪论 上给予了拓扑校正算法强有力的支持 并为算法校正前后矢量地图拓扑不变性的 证明提供了途径 第四章给出了一个工程应用实例 它是一种基于嵌入式设备的个人g i s 助理 系统 分为用户手持终端和监控中心两大部分 文章分别从硬件组成到软件设计 详细介绍了它的实现过程 本系统利用经过拓扑校正算法校正过的矢量地图 在 实际应用中取得了良好的使用效果 第五章总结与展望 6 第2 章拓扑校正算法综述 第2 章拓扑校正算法综述 在车辆监控 导航等一系列g i s 典型应用中 都离不开一幅精确的矢量地图 从g p s 卫星收到的信号是用户当前的经纬度信息 要把用户的位置准确地显示 在地图上 对矢量地图就必然有两方面的要求 第一是要求点与点之间 点与路 之间 路与路之间的相对位置关系是准确的 即拓扑关系确定 第二就是在地图 坐标和地理坐标之间建立一种准确的映射关系 本章将从矢量地图的误差分析入手 剖析矢量地图自动校正的本质 指出规 范校正结果的要求 并对已有校正算法进行了简单的介绍 指出其中的不足 2 1 矢量地图的误差分析与自动校正 2 1 1 矢量地图的误差分析 矢量地图数据的误差包括很多种 首先是数据来源带来的误差 手扶跟踪数 字化或扫描纸质地图图像矢量化作为矢量地图录入的主要手段 由于湿度 温度 保存时间等环境因素引起的图纸变形 采用数字化仪录入时 录入人员的工作经 验和水平 地图扫描输入时 由于机械等原因产生的微小拉伸 压缩及旋转变形 卫片 航片数据本身的误差及坐标变化等都将影响制图的精度 其次 在对不同 来源的不同图层进行编辑整饰的过程中 也有可能发生平移 旋转或拉伸等变化 带来数据误差 韩晶等 1 9 9 9 另外 地图图源本身的误差也是误差的一个主 要来源 它将从测绘过程完全带入矢量化后的矢量地图中 李君轶 2 0 0 2 下面给出两个存在误差的地图示例 其中的深色虚线线条是真实的车辆行驶 轨迹 它通过g p s 卫星定位实际测量得到 反映了车辆所在的相应道路在当前 显示的地图平面中的位置 从图2 1 1 中可以明显看出 在地图平面中 矢量地图中的道路和实际的车 辆轨迹之间存在着一个放缩和平移的关系 而在图2 1 2 中 矢量地图中的道路 和实际的车辆轨迹之间存在着某种程度的旋转 另外 两幅地图中都存在一些局 部的不均匀的误差 仅仅对地图进行放缩 平移和旋转变换是不能消除的 由此得出待校正地图中存在的误差分为两类 线性误差和非线性误差 线性 误差指的是可以通过放缩 平移 旋转变换消除的误差 通过矢量地图的整体线 性校正 可以非常有效地消除这种误差 非线性误差指那些无法通过放缩 平移 旋转有效消除的误差 这种误差仅仅利用线性校正方法 不能有效消除 只有通 7 第2 章拓扑校正算法综述 过人工校正或非线性离散校正来消除 8 图2 1 1 矢量地图的线性误差 放缩 平移 示例 图2 1 2 矢量地图的线性误差 旋转 示例 第2 章拓扑校正算法综述 2 1 2 矢量地图的自动校正 矢量地图具有保持其节点拓扑关系不变的性质 是指矢量地图上非孤立节点 在其构成的线上的相邻连接关系总是不变的 孤立节点位于其所在的闭合区域范 围内的规则总是不变的 但节点之间的相对距离关系可以存在误差 对矢量地图 的校正就是在不改变节点之间拓扑关系的前提下 通过对若干校正点的原位置向 其精确地理位置的调整 获得相应的全平面上的映射规则 将规则作用于矢量地 图的所有节点 获得矢量地图所有节点位置尽可能精确的调整 选取待校正矢量地图上已知精确位置信息的玎个点作为待校正点集 记为 g h g k l 9 2 g k 1 石l y 1 g 矗 y f 91 1 其中g g 儿 y 1 2 刀 表示第i i k 待校正点吕在大地坐标系上的不 准确的位置经纬度为 t 只 如图2 1 3 中打上符号 x 的点 而g 在大地坐标系上的精确的经纬度为西 g i w 订 所以待校准点集g 的精确位置集合应为g 如图2 1 3 中打上符号 的点 g g 9 2 g g x y g 万 y 2 2 图2 1 3 输入g p s 道路轨迹数据的合肥市矢量地图 9 第2 章拓扑校正算法综述 矢量地图的自动校正就是在保持矢量拓扑结构不变的前提下 利用已知精 确经纬度的校正点对 通过校准校正点对获得矢量地图节点调整的映射规则 调 整矢量地图中所有节点的位置 直观地说 矢量地图校正的过程 本质上就是改变矢量地图节点坐标数据库 的所有节点数据d 尽可能地用接近于其准确位置的新数据矾来替代 由于待校正地图中存在的误差分为两类 线性误差和非线性误差 所以矢量 地图的自动校正总体上也分成两大类 整体线性校正与离散非线性校正 整体线性校正的定义如下 矢量地图的整体线性变换丁 通常是不能实现完全的节点移动 但可以把 q 映射成g g r a g x 0j a g 石 y 2 3 使得q 与q 之间的距离偏差e 最小 偏差e 定义为 e 兰帜一g l 乞 k g i i 2 4 校准样本点对的距离函数e f 1 2 玎 的定义为 e i i g 一g i x 一x 2 少 一少 2 2 5 获得线性映射关系丁 后 对矢量地图所有节点d 执行同样的变换 r p t n l n 2 n p 0 以 2 知 厅0 2 6 可以预期变换后的矢量地图所有节点p 0 与准确的矢量地图所有节点d 二的 偏差 或 i i o 一d 卅 p 卜以1 2 7 也会达到最小 从而完成整体线性校正的过程 通过对矢量地图的误差分析可以看到 整体线性校正是针对矢量地图线性误 差的自动校正 因为线性误差 平移 放缩和旋转 可以利用坐标变换加以校正 值得注意的是 整体线性校正的过程可以保证校正前后地图结构的拓扑不变性 离散非线性校正的定义如下 离散非线性校正 就是要找到一种拓扑映射丁 把待校准点集g 一全部映 射到其精确位置g 鹅 q 即 g m 茁 y i f 1 2 刀 2 8 l o 第2 章拓扑校正算法综述 直观地说 就是把在图2 1 3 中打上符号 的点移动到打上符号 的点的位置上去 同时保持矢量地图的拓扑关系不变 获得线性映射关系丁 后 对矢量地图所有节点巩执行同样的变换 及d 双 托 或 西 戊 商 2 9 完成矢量地图校正的全过程 也就是说 拓扑校正对我们有两个要求 一是获得正确的校正规则 二是保 证校正前后地图的拓扑结构不变 2 2 整体线性校正 2 2 1 整体线性校正的原理及实现 矢量地图整体线性校正算法很多 包括等距变换 仿射变换与射影变换等 目前数字地图的自动生成校正平台校正使用的整体线性校正算法原理如下 直角坐标下的线性变换瓦 校正地图平面水平方向的拉伸误差4 x 与竖直 方向上的拉伸误差a y 瓦 2 1 0 i y 分别为两轴的放大倍数 0 分别为两轴的平移量 直角坐标上的拉 伸误差校正变换瓦 把矢量地图的任一点g 如力映射为 g g x y 瓦 g x j g7 p 07 2 1 1 极坐标下的线性变换 校正地图方位角的旋转误差a o 与极轴方向上的 拉伸误差和 吼 黪麓 泣蚴 k p k 分别为两轴的放大倍数 0 r o 分别为两轴的平移量 极坐标上的旋转 拉伸误差校正变换 把矢量地图的任一点g 如力映射为 雪 季 曼 夕 疋 g x 夕 瓦 g p 臼 季 声 0 2 z 3 将整体线性校正算法定义为尺度误差校正变换瓦 与旋转误差校正变换 砭 的综合变换 0 0 x y 以以 i l i x y j 第2 章拓扑校正算法综述 丁 瓦靠 瓦 砭 2 1 4 如图2 2 1 所示 精确位置为f g f 的待调整的点g 如力 由瓦 首 先调整到喜 舅 力 再由瓦 调整季 毫歹 到g7 0 y 即 g x y t g x y 瓦 喜 毛夕 瓦 瓦眩 p d 2 1 5 图2 2 1 坐标变换将g x y 的调整到9 7 z 7 y 示意图 矢量地图整体线性校正r 的结果为 x k f i 伊 r 铲 k a sc osy k y ss i n 曼o 籀k y z p u r p s i n 义 k 乏0 秒 糍亿旧 7 尼y 歹 o o 尼p 口 o 7 校正后的误差为 p l g 一g l 血 2 缈 2 x 一石 2 一y 2 2 1 7 显然 只要确定了参数v k k yok 口r a k p j 2 1 8 就可以得到映射r 而参数y 可以通过最小化目标函数得到 最小化目标函 数通常使用的迭代搜索算法为变尺度d f p 法和最4 乘法 目标函数定义为 m nj p g 7 g j 2 x x i 2 y 一少j 2 矿 2 1 9 对目标函数 的最优化采取变尺度d f p 法 具体迭代步骤就不在此赘述 直观地说 矢量地图校正的过程 本质上就是改变矢量地图节点坐标数据库 中所有节点的数据d 尽可能地用接近于其准确位置d 的新数据d 来替代 值得特别说明的是 放缩和平移变换都不会破坏矢量地图的拓扑结构 所以 整体线性校正综合利用了刀个节点的信息 并且始终保持了同样的拓扑关系 同 第2 章拓扑校正算法综述 时 虽然校正用的只是有限的n 个点的精确数据 但只要这n 个点在地图平面上 合理地分散开来 那么由矢量地图保持了所有节点之间的拓扑关系这一基础特 性 由这 1 个点的校正数据就完全可能推算出其它节点的校正规则 且这种校正 规则至少对位于这 z 个点附近的玎个邻域内的所有节点的校正是足够有效的 2 2 2 整体线性校正的局限性 矢量地图整体线性校正算法的一个明显的局限性是不能校正原矢量地图存 在的非线性误差 本节给出的矢量地图线性校正算法只是均匀地同时使用己知的 n 个参考点对的精确数据信息 这样做的后果就是 这n 个待校正样本点的校正 结果一般不可能同时达到这聆个点的准确位置上 除非原图完全不存在非线性误 差 地图存在的非线性误差 形象化地说 就好比地图的幅面遭受过揉捏 平面 有些变形 其上有些块面积变大 同时有些块面积变小 虽然这些变形块的出现 不足以破坏到整幅矢量地图节点之间的拓扑关系 但这些变形块的分布与局部面 积的变形则是毫无规则而言的 很明显 即使可以用来校正的精确点数目很多 矢量地图整体线性校正过程也无法克服这一局限性 目前实际解决这一问题的最 有效办法就是手动逐点校正 也就是人工移动节点至其精确位置 其耗时耗力 不亚于重绘地图 矢量地图整体线性校正算法的另一局限性是对矢量地图校正效果有限 最高 精度受限于栅格地图图源的点阵分辨率 纸质地图图源的比例尺幅度决定了栅格 地图及由其生成的矢量地图的最高精度 线性校正的结果 不可能获得更高的精 度 2 3 离散非线性校正 上面介绍的整体线性校正算法 无论从理论 还是实际的效果来看 只能达 到全局最优 而无法使局部也达到最优的效果 尤其是对于矢量地图中存在的非 线性误差 更不能使用线性校正的方法消除 因此 如何消除非线性误差就成为 提高矢量地图校正精度的瓶颈 而离散非线性校正就是g p s 实验室针对消除非线 性误差所提出的解决方案 目前数字交通地图的自动生成校正平台校正使用的离 散非线性校正算法介绍如下 2 3 1 离散非线性校正的本质 离散非线性校正的思路描述如下 第2 章拓扑校正算法综述 1 测量出n 个已知精确位置的校正点对 校正过程由这n 个校正点对对应的 子校正过程累加组成 每个校正点对及其邻近区域组成了一个称为离散块的分块 区域 校正分为门步进行 每个校正过程只对这个离散块内的所有矢量节点的位 置进行校正 因此新算法要引入 离散 的概念及使用线性系统离散建模并遵循 离散线性系统理论 2 对于每个离散块中校正算法的选择 首先要遵循整幅地图离散建模的理论 且保证所有离散块之间的无缝衔接 也就是说必须确保离散块边缘上的节点位置 不变 其次是要考虑基于该校正点对校正前后的两个坐标数据的差值 即位置的 移动 以及矢量地图节点网络拓扑关系不变原理下由校正点对的移动可以获得的 该离散块中所有其它节点的相应移动数据 因此 离散块中的校正算法不可能是简单的线性变换 一定是某类非线性校 正算法 因此新算法要引入 非线性 的概念及满足该变换的边界条件 即保证 任何时刻全平面的无缝连接 3 校正过的点在后续的校正过程中必须保持位置不变 是该算法确定离散块 或 分块 的重要原则 因此 该算法中的 离散 概念不是一个对地图平面上 的静态离散 对比离散线性系统理论中离散概念仅是时间上的静态离散 而是 基于地图平面上随时刻 已校正点数 而不同的动态离散概念 该算法确定的 分 块 原则是在每一对新校正点校正前 在该时刻以前校正的结果形成的整体地图 平面上进行 只要保证校正过的点不动 不仅不要考虑历次分块的状况 而且应 选择以校正点为核心 不是中心 尽可能大的分块区域 可以推知 随校正过的点 数足的增大 不动点k 的增多 新的离散块必将越来越小 形象地说 以时间回 顾 k 层离散块是重重叠叠又交错的分布在时间轴上 以地图平面回顾 一张经 过揉捏的矢量地图幅面 就像在平面内挤压变形的柔性铁丝网 橡皮变形 经 历k 次的单点牵拉定位 会一块块地被拉平 离散非线性校正的实现 1 动态离散块与子拓扑变换 按照上节 动态离散 概念的分析 对刀个已知精确位置校正点对的校正信 息是逐点使用而逐块进行的 所以矢量地图离散非线性拓扑变换丁 可以分解为 玎个子拓扑变换瓦 如下 丁 l 瓦一l 疋正 瓦 l 一 疋 疋 正 2 2 0 子拓扑变换瓦 只以第k 校正点对为依据求解 同时只作用于第后个离散块 瓯 包括s 内的所有矢量节点 瓦 定义为保证动态离散块 的边界曲线映射 1 4 第2 章拓扑校正算法综述 为自己 动态离散块瓯内部各节点能够得到最恰当校正的拓扑变换 疋 g g 疋 s 女 s l 2 2 1 疋 s s 式中s 的补集 表示矢量地图非离散块瓯的平面空间 按瓦 的定义可知第k 步可以完成第l 2 k 个校正点q 4 留 的 精确校正 即 疋疋一1 t 2 t g l t 疋 g 二 g 七 g 七 g i i 9 2 g k 2 2 2 最后一步即第1 1 步完成离散非线性拓扑变换r 全过程 达到 l g t g l 一 g 月 g g l g g t g 月 2 2 3 2 动态离散块与已校正点对 已校正点对g 州是子拓扑变换瓦 中的不动点集 那么如何在第k 步校正 过程中确定第k 个离散块 如何具体选定离散块 也就是如何确定离散块的边界 既然校正过程已进行 到完成了k 一1 个校正点 按照动态离散的思路 确定瓯唯一的限制条件就是确 保校正过的点集 g 二 g l g g 一1 2 2 4 不再移动其精确位置g 二 离散分块可以有多种选择 考虑到已校正的这k 一1 个点已被固定在它们的精 确位置 七零八落地分布在地图平面上 对以后的校正 g 七一l 的总体布局是确 定s 边界的决定因素 分析每个已校正点 g fj 1 2 k 一1 2 25 gi i 1 2 k 2 5 g fj 2 一 2 s k 的限制 参见图2 3 1 连接已校正的不动点g i 与待校正点对繇与g 取匀女g 名 的角平分线 过g i 做角平分线的垂线记为厶g 把地图平面划分 为两个半平面 其中g 与g j 所在的那个半平面记为仇 g 考虑不动点g 对 待校正点对g 与g 作用范围的限制 依照单点牵拉定位的观点 将瓯限制于 g 之内应该是合理的 从处理的角度看也将会较为简单 即 c 吼 g f 1 2 k 1 2 2 6 综合已完成的k 一1 个校正点对瓯的限制 我们得到离散非线性校正过程中 t 七c 七 g s s 哼 丁r 露 凰 j r 瓦 第2 章拓扑校正算法综述 第七个离散块的选取规则为 s 七 n 硝k 1 日七 g n 2 2 7 图2 3 1 已校正点g f 尼 对 范围的限制 3 离散块内部节点的校正 离散块s 七为一凸m 多边形仰 k g 七与g 位于s t 内 如图2 3 2 所示 将m 多边形s t 记为a b c 一f 其m 条边a a b g 肌分别记为己l 三2 三州 连接第j j 校正点g 女至瓯各顶点 将 分解成m 个三角形 a g t l l 2 m 在图中为带虚线边的4 个三角形 s u a g 七三七g 三 连接第七个精确点g 至s 各顶点 将s k 分解成所个三角形 歹 1 2 聊 在图中为实线边构成的4 个三角形 s 七 n 2 么g 三 1 6 图2 3 2 离散块 内部的映射关系示意图 2 2 8 g l j 2 2 9 第2 章拓扑校正算法综述 这样一来 瓦 对瓯自身映射可以转化为m 个相邻三角形的映射之和 兀 瓯 疋u 闰m4 9 l j u 三瓦 4 瓯三 u 二4 9 l j s 2 3 0 下面定义五 对三角形的非自身映射 除了应满足对三角形中 含边界 所有 节点修正规则的要求外 还要保证所有相邻三角形共同边映射的象空问的无缝衔 接 r 七 a g j l a g k l l j 1 2 m 2 3 1 不失一般性 考虑底边为a b 的三角形a g l j 及其象空间a g l j 对应三角 形内部的映射关系参见图2 3 3 黧 慕譬 钐 in i 图2 3 3 对应三角形内部的映射关系 记么反三 为4 9 a b a g k l j 为 g 女a b 定义对三角形的映射变换瓦 瓦 4gta b ag a b 2 3 2 如f 瓦 g 季 季萝 g 或 g 虿 g 磊 2 3 3 式中 露 表示线段露的长度 余类推 g 是三角形a g k a b 中 含三角形 三条边 的任意一点 g 经过瓦 映射到a g a b 内部的点为垂 季位于线段 盛g 上 a a b 么反么b 中 g k 瓦 或或 垂直于底边彳b 交么b 于磊 或 g 季 露 垂直于底边彳b 交彳召于吾 矿 延长g g 交底边彳b 于g 基于矢量地图及其节点网络拓扑特性 不会出现g 七与g 分别位于多边形内 外两