第三章 数字道路地图(1).ppt

1、车载GPS定位技术与应用,第三章数字道路地图, 3.1 导航电子地图概述 3.2 节点-路段数据模型 3.3 适合车辆导航的路段链数据模型 3.4 数字地图的分层组织 3.5 导航数据的组织方法,3.1 导航电子地图概述,导航电子地图概述,城市地图,导航用电子地图实例,导航电子地图概述,导航系统组成,导航电子地图地位及与导航功能的对应关系,地位：导航电子地图在整个车辆导航应用体系中起到核心的作用，针对不同导航应用往往会采用不同规格的电子地图。 通常电子地图由记录实际地物的地理数据和与实际地物相关的标识、修饰信息以及各类附加信息组成。根据应用场合的不同，电子地图的选用也不同。 电子地图数据与导航

2、应用功能之间的关系如下图所示：,导航电子地图概述,地图显示、地址匹配、地图匹配、路径规划、路径引导与数字地图的关系,地图显示是车辆导航系统的重要组成部分，它构成了人机接口的基础，地图显示的成功与否直接影响到用户对产品的印象。地图显示需要依赖数字地图中的道路位置、宽度、级别等属性以及道路附近的各种设施。 地址匹配又称为地理编码，即通过给定的经纬度坐标确定地图上街道的地址，或者相反的过程。需要数字地图的基本属性是道路的名称和地址范围。 地图匹配是利用数字地图的路网信息修正车辆定位模块的位置输出，位置修正的前提是车辆在道路上行驶。 路线规划和路线引导更是与数字地图密切相关，它的几乎所有数据如路网的空

3、间分布、几何坐标、拓扑连接、道路平均时速、转向限制等等来源都是数字地图中的道路信息，,车辆导航系统的功能与数字道路地图特征的关系,车辆导航系统的数字地图和通用数字地图侧重点不同： 首先，地图要素种类不同。 导航图重点要素：道路 每条路的地理坐标、道路之间的拓扑关系、道路交叉口的交通限制情况等。因此设计导航数字地图数据库时，需要着重考虑道路的表达与组织，同时要有一个高效的访问道路信息的机制，以便可以高效率的进行诸如路线规划，路线引导等功能。对于车辆导航系统来说，应该根据功能需要选择合适的信息进行表达和存储。数字道路地图是导航数字地图数据库的重点和基础，是数字地图的核心内容。 其次，数据层次划分不

4、同。 地图数据层次划分应该强调道路的分层，同时要求能够方便扩展，便于地图的升级维护。,车辆导航系统的功能与数字道路地图特征的关系,3.2节点一路段数据模型,3.2.1图论基本概念 图(Graph)图表示的是定义在顶点集上的二元关系。图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集，V(G)中所含元素的个数即顶点数，称为图的阶，记为|V(G)|或n E(G)是边的有限集合，边是顶点的无序对或有序对，E(G)中所含元素的个数称为边数或弧数，记为m 有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也

5、称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头(终端点) 无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v),邻接 与 关 联 对于无向图G= (V ,E) ，若有边(u,v) E，则称u和v互为邻接点或相邻接，且边(u,v) 依附于顶点u和v，或称边(u,v) 与顶点u和v相关联。对于有向图G=(V,A)，若有弧 A，则称顶点v邻接到顶点v，顶点v邻接自顶点v，且弧 与顶点v和v，相关联，它从顶点v发出，也称为顶点v的前向关联边，顶点

6、v的后向关联边。 顶点的度:无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 某个顶点的度=此顶点的入度+此顶点的出度,带权 图（网络(Network) ）: 图的边或弧可具有与之相关的量化信息，表示从一个顶点到另一个顶点的距离、费用等等。这种与图的边或弧相关的量化信息叫做边或弧的权(Weight)，其中的顶点称为节点(Node)。 路径 从顶点v到顶点w的一条路径是由一个不同顶点组成的序列V=Vi,0，Vi,1，Vi,n，满足(Vi,j-1，Vi,j)E 或 E,(1jn)且其中Vi,0=v， Vi,n=w

7、。 路径长度 沿路径边的数目。 连通：从顶点V到顶点W有一条路径，则V和W是连通的 连通图：图中任意两个顶点都是连通的无向图叫,图G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , 顶点2入度：1 出度：3,图G2中：V(G2)=1,2,3,4,5,6,7 E(G2)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7) 顶点2的度：4,带权图,3.2.2节点一路段数据模型的形式化定义,目前的车辆导航系统中，道路网用图的形式来表示，而且大多使用基于节点路段的数字道路地图数据模型。 道路网 带权有向图，道路以线或折线对象的方式存

8、储，表示为一系列带坐标点的有序集。 包含交叉点的道路被拆分成最基本的路段，使其只在端点处与其他路段相交。拆分后的基本路段对应于路网中的弧，其端点就是图中的顶点。 用图的形式可以表示为:,其中 ， NR :代表道路网络；Ns为道路的节点集，对应图的顶点集;Rs为道路的有向路段集，对应图的弧集，可以用道路网络中两个节点的拓扑关系表示，u和v分别是起点和终点，Quv路段的属性集，可表示长度、平均时速、通过时间、是否收费等。,道路在数字地图中作用： 1、道路描述主要是现实道路的显示，要求数据比较细致和详细; 2、计算主要是指配合车辆导航的地图匹配、路线规划和引导等内容，要求道路具有明确的综合性，以利于

9、道路计算的速度和算法的实现。 对道路数据的空间描述：一般采用三个层次，即数据层、描述层，综合层，它们的内容见下表,3.2.3路网的基本要素,路网的基本要素为：点实体(节点)和线实体(路段),1、路段 路段一般作为道路的最小空间描述单元。即路段是具有同一属性在路网中相互独立且最小的道路图形特征。每一条道路，有对应的一些属性信息，例如道路的交通限制、道路名称、道路宽度等，所以需要根据属性信息的变化把一些道路拆分为更小的路段。 2、节点 节点并不是一个实际意义上的点，它是一个抽象的概念，即可能使车辆行驶路线发生改变的控制点。 （1）道路的交叉口或者路的终点。 （2）道路特性发生改变的点，如在该点道路

10、的宽度显著增加或者减少，或者从该点开始道路需要收费行驶等。 （3）可能进行转向操作的点，如进行物理分隔的道路中间将隔离栏(带)打开，专供车辆掉头的点， （4）快速路的出入口等。直接影响车辆导航系统路线计算的结果的点。,（2.1）几种典型的道路交叉口,(1)多道交叉口 三条或者三条以上的单车道或多车道相交的平面交叉口形成一个节点，如:T型交叉口、Y型交叉口、十字交叉口、多路交叉口等，如图 (a)所示。有时多条道路的中心线在交叉口没有交叉成为一个点时，但如果起到了交叉口的作用，仍然可以把它作为一个节点处理，如图 (b),路网基本要素节点 路段,(2 )环岛型交叉口 环岛 型 交 叉口是一种特殊的交

11、叉口，在该交叉口内部，车辆必须单向行驶，绕环岛逆时针旋转行驶，如图3.2 (c). (3 )快速路的出入口 快速 路 (含高速路、高架桥等)的出入口包含了交叉信息和出入口，它既要描述正常快速路的行驶路线，也要确定道路出入口位置，如图3.2 (d). (4) U 型转弯口，如图3.2(e)。,路网基本要素节点 路段,（2.2）道路连接点,道路连接点，用于标定道路方向的改变以及同一道路发生属性描述变化的转折点，复杂道路通过增加道路连接点来进行分段。例如在C, F, G使道路属性发生改变影响车辆导航功能实现的点，它们是道路连接点。 （2.3）各种复杂的立交桥，应将各个匝道的出入口定义为节点，使得计算

12、的行车路线能清楚的表达桥内的行驶，使出行者了解各种转向操作的具体行走方法。,路网基本要素节点 路段,图3.3,3、典型示例,如图3.4所示是城市快速路中主、辅路并行，且存在非互通式立交桥的情形。 这种情况下，主、辅路用两条平行的路段表示，快速路的出口P和入口Q、W为下层交叉点辅路与相交道路EF的平面交叉口都形成节点，而主路在立交处则没有形成节点。,图3.4实际道路网络及对应的节点一路段模型,路网基本要素节点 路段,4、组成要素的属性,4.1 节点的属性数据应包括: （1）节点编号、（2）节点坐标、（3）灯控路口的时间配时、 （4）节点的车辆行驶平均时间延误、（5）交叉口转向限制等。 4.2车辆

13、导航系统路段属性数据应该至少包含以下内容: (1)路段编号; (2 )起点、终点编号；(3)路段名称; (4)路段长度; (5)路段宽度; (6)道路等级(高速路，国道，省道，县道，城市一级路，二级路，三级路); (7)车辆平均时速: (8)路面建筑状况(好、一般、差); (9)最高速度限制; (10)是否收费与收费标准 (11)实时路况信息(交通事故、堵塞程度等); (12)允许车辆类型,路网基本要素节点 路段,导航数据库中节点要素说明实例,导航数据库中路段要素说明,3.2.4 路网连通性表达,路段之间的连接关系的表达即路段通过节点建立拓扑关系，建立拓扑关系的路网可以方便的执行地图匹配、路线

14、规划等道路计算。 车辆导航系统中连通性与实际道路网络中的有所不同： 数字道路地图可以用带权有向图的形式来描述，图论意义上的连通性描述了节点之间的邻接关系，这种节点之间的连通性具有传递性，即节点n1与n2连通，n2与n3连通，那么n1一定与n3连通。 但在实际的道路网络中，交通管理部门经常会采取一些交通管理措施，如单向交通、转向限制等，这种情况下，节点之间的连通性不再具有传递性，从而那些直观上连通的路线在实际交通行为中是不可达的。,例如，从花园北路到北航东南门路口，从图中直观地看是连通的，但由于北航路口的东进口禁止左转，使得在实际交通行为中不能由花园北路左转到学知路口，因此这条路线不可达。,解决

15、方法一：增加虚边法,基本思想：在具有转向限制的节点处增加多个虚拟节点和虚拟边，将每一种允许的转向行为表示出来。 设在路网Nr中，节点vi，具有n(i)个后继和n (i) 个前驱，那么必须将该节点拆分为n(i)十n (i) 个虚节点，分别代表该交叉口处的n(i)个出口和n (i) 个入口，对于允许的转向行为，在虚节点之间构造虚有向边，一个具有转向限制的T型交叉口(图3.5所示)可以用增加虚节点的方法表示出来，如图3.6,增加虚边的方法优点：非常直观，简单 缺点：1、增大了存储量，从而增加了计算时间，加大了路网编码的工作量。2、大量虚节点和虚边，与原有路网中的弧和节点混杂在一起，输出结果的可读性较

16、差。,图3.6增加虚边法表示转向限制,3.3 适合车辆导航的路段链数据模型,即解决方法二 3.3.1车辆导航系统对数字道路地图数据模型的要求 1) 能够表达路网要素及拓扑结构; 2) 能够表达单向交通、交叉口转向限制等交通管制措施; 3) 能够表达具体实际中各种特殊的路网结构; 4) 能够表达路口的时间延迟，即道路网络的节点权值; 5) 便于地图匹配算法对路网的操作; 6) 便于路线规划算法对路网的操作;,3.3.2路段一链的数据模型1、形式化定义,基本思想：将路网的基本单元“路段”作为图的顶点，而将路段之间的允许转向行为(这种转向行为称作“链”)作为图的弧。 它的形式化定义为: 其中，NR为

17、一个图，代表道路网络; Rs为图的顶点集，代表道路网络的有向路段集; Ls为图的弧集，代表道路网络的链集。 P代表对应道路网络NR的路段集。,2、链的形成,路 段 链数据模型与节点一路段数据模型之间存在紧密的关系 设节点路段的道路网络为N=(V,E), V是顶点集，E是弧集； 对应的基于路段一链的道路网络定义如下:N=( V ,L )， 其中 V = E ，即网络N中的的顶点集V就是网络N中的弧集，L表示链集，它可以定义如下： x,yV表示N中的顶点，对应网络N中的弧， x=(u,v,Quv )表示N中弧的起点是网络N中的起始弧， y= ( v,w, Qvw)表示N中弧的终点是网络N中的x的后

18、继弧, (u,v,w) P 表示网络N中有转向限制的弧，在N中不再存在。,3-7链的生成图,假设存在如图 ( a)所示由南向西的禁止左转限制，同时该路口不允许车辆掉头， 图 (b)是该道路的节点一路段表示， 那么可以生成路段一链的道路网络模型，如图 (c)所示。,3、“路段一链”数据模型具有特点:,(1 )很好解决了交通实际中的单行线问题; 由于该数据模型以“路段”为网络节点，它继承了有向路段的属性信息，任何个双向道路都对应于两个有向路段，当某条道路为单向时，该地理实体仅对应一有向路段，也就是对应该模型中的一个节点。 (2)很自然的表达了路网中的转向限制 由于该数据模型以“链”为网络弧段，假如

19、相邻的路段可以通行的话，该数据模型就建立了以节点为连接的联系，也就是该模型中的一条“链”;,(3 )对于路网中交叉口处的不同转向行为的交叉口延迟，它们可以转化到“链”的属性中，用网络弧段的权值表达。 对应的弧的权值由下式确定: d(Li，Lj)= d( Li) +dp(Li,Lj) 其中 :d(Li,Lj)为路段-链模型中弧(链)的权值，d(Li)为节点一路段模型中弧(路段)的权值，dp(Li,Lj)为路段Li转向Lj的延迟所对应的权值。 (4) 这种数据模型也增大了网络的规模 这是由于在城市道路网路中，路段的数目大于节点的数目，同时路段连接关系的数目也大于路段数目。,3.4 数字道路地图的分

20、层组织,3.4.1普通的地图分层方法 最初传统的数字地图，没有分层组织，一幅图包含有各类不同的信息，如边界、城市、村镇、河流、注记、道路等，在进行某一专题或地理分析时，只注重对某一单项同类对象进行显示和分析，而其他内容不作为分析对象，从直观上给人杂乱的感觉，处理也不方便。,目前的GIS软件都采用分层结构组织地图数据。一般地，分层结构采用按图层组织的方法，即把同一类或几类地理要素的信息放在同一个图层，每一个图层存储为一个或一组独立的文件，如图3.9所示，在这组文件中进行叠加显示操作。,图3.9,3.4.2数字道路地图的单图集分层结构,由于车载导航设备的计算能力和存储资源的限制，需要设计专门的分层

21、结构来组织道路数据。 目前国际上主流的导航地图数据（如Kiwi, SDAL等标准)的分层组织结构就是针对车载设备的特点设计的。 其特点：是将主地图数据依比例尺组织成“比例尺层 图幅”结构。一个主地图称作图集，在1:500至1:4000万比例尺的范围内将图集分成若干比例尺层，也称存储层，所有存储层覆盖同一地理区域，但每个存储层信息的详细程度不同。存储层内依一定规则划分成等距或不等距的矩形区域，称作图幅，也可以在存储层内按“块 基准图幅 图幅”的多级结构划分地理空间。 优点：充分考虑了车载设备对大容量地图数据的操作能力，能缓解强势数据与弱势资源之间的矛盾。,分层、分块数目的大小,可以根据硬件软件条

22、件综合考虑。 将第1层地图数据根据屏幕显示范围大小,按横方向分为m份,纵向分为n份,这样一屏幕数据由mn份矢量数据组成。第2层 (mn)2 份矢量数据组成。依此类推，第I层由(mn)i 份矢量数据组成。 分割的数据采用树结构索引存储。 如图3-10所示。,3-10 单图集分层组织结构 “比例尺层图幅”分层结构,单图集分层组织的缺点：,不利于后续数据的添加和现有数据的局部更新 由于它把整个地理空间的数据资料集合到一个主地图上，我国现在正处于经济和城市建设的高速发展时期，地图数据的添加和更新要求能够快速及时，这种单图集分层组织形式不适用我国车辆导航地图数据生产的现状。,3.4.3 数字道路地图的多

23、图集分层结构,多图集分层组织结构可以通过一个图幅树的多叉树结构将所有主地图连接在一起。如图3-11所示。,311多图集分层组织结构,每个图集按显示比例尺分成多个存储层； 层与层之间的比例尺可以是整数倍的关系； 相邻层的图幅是包含关系； 一个子图幅只能有一个父图层； 一个父图层具有的子图幅数量不能超过其区域所能容纳的子图幅数量，但允许子图幅的数量小于最大数，甚至允许没有子图幅的情况下有孙图幅、重孙图幅等。,图3-12,1、多图集分层组织结构:,2、存储结构图幅树,便于车辆导航系统对不同地图进行访问和操作。 图幅树中的每个图幅是图幅树中的一个节点，存储顺序如下： 根节点在首位，最高存储层的所有图幅

24、节点记录在后面，次高层的所有图幅节点记录在最高存储层的后面，依次类推。,313多图集分层组织的图幅树结构,例 地图数据的管理,整个地图数据的组织是按照图层-地图-地图集一体化的电子地图数据组织方法（见下图），每个图层存贮管理用户感兴趣的对象(同类地图元素)。,图层-地图-地图集组织,地图集：地图集包含了导航软件所能加载的所有地图数据，它是一个存放地图的容器，其中地图的检索方法类似于针对数组的使用方法。 地图：地图是通过地图集检索得到一个对象，它包含的是一个行政区划的地图数据。同时地图也是存放图层的一个容器，其中对图层的检索方法类似于针对数组的使用方法。 图层：一个图层代表的是一种地图数据元素的集合。,3、地图数据库和地图元素的分类,整个地图数据库按照功能用途可以分为三种数据库类型： 分析数据库