在车辆监控导航和智能交通系统中，都需要准确的矢量地图。导航电子地图是整个导航系统的基础，导航系统的定位、路径的寻优、轨迹的校正等功能都离不开导航电子地图的支持。对于建设数字化地球、数字化城市，矢量地图具有重要的意义。
首先来了解一下电子地图的概念以及目前GPS实验室做过的交通矢量地图生成平台相关的工作 。
2.1 栅格地图和矢量地图的基本概念
随着计算机的出现和信息论的发展，地图制图逐步由手工绘制过渡到电子化、自动化的阶段，从数字资料自动制图、图形资料自动制图到航空遥感和航天遥感图像的自动制图，电子地图的技术发展非常迅速。电子地图的应用非常广泛，海洋、气象、水文、地质、土地利用、地球物理、宇航、测绘、勘探等领域都需要电子地图。20世纪60年代，地理信息系统（Geographic Information System，简称GIS）[12-14]的兴起和迅猛发展更推动了电子地图制图的发展。GIS是一种专门用于管理地理空间分布数据的计算机信息系统，所以其中的数字电子地图是一个必不可少的部分，它在很大程度上决定了GIS的命运。
电子地图[15]按照其数据结构的不同，又主要分为矢量电子地图和栅格电子地图两种。栅格电子地图也就是我们平时常见的位图，是各种比例尺的纸介质地形图和各种专业使用的彩图的数字化产品，就是每幅图经扫描、几何纠正及色彩校正后，形成在内容、几何精度和色彩上与地形图保持一致的栅格数据文件。栅格数据为按给定间距排列的阵列数据,基本信息单元由数据点的空间位置和数据信息构成,数据信息可以是高程、遥感图象的RGB值或其它信息。数据按图幅或按区域存放,文件结构包括文件头和数据体,文件头包括对数据的各种描述信息(如行数、列数、格网间距、坐标等),数据体依次记录基本单元信息。一般为节省存储空间,栅格数据需进行压缩或以其它形式进行重新组织。
矢量地图是每幅经扫描、几何纠正后的影像图，是对一种或多种地图要素进行矢量化形成的一种矢量化数据文件，是一种更为方便的放大、漫游、查询、检查、量测、叠加地图。其数据量小，便于分层，能快速的生成专题地图，所以也称作矢量专题信息DTI（Digital Thematic Information）。此数据能满足地理信息系统进行各种空间分析要求，视为带有智能的数据。可随机地进行数据选取和显示，与其他几种产品叠加，便于分析、决策。通常矢量数据的基本单元定义为点、线、面3种目标形式。基本信息单元由反映其分类体系及位置的基本数据组成。同一类基本空间信息单元具有类似的质量、数量特征,构成一个要素层;多个图形要素层构成一个图幅,数据按图幅存放;同一比例尺的多个图幅构成一个区域。 矢量地图是对点阵数据数字地图图像进行跟踪识别得到的矢量数据以后的地图，然后对地图中线状地物如河流、等高线、铁路、公路、等进行恢复，恢复的结果就是一幅矢量地图。
电子地图的这两种实现，各有优缺点。栅格电子地图，主要是生成比较方便，图像比较细致，和人们日常使用的地图类似，容易被用户接受，但是，栅格电子地图数据量比较大，存储不方便，放大过程中会产生失真，数据不是很准确，很难进行全局或者局部校正，更新起来也比较费事。矢量电子地图生成相对费事，但是数据经过压缩，结构紧凑，数据量小，冗余度低；有利于网络和检索分析；图形显示质量好，精度高；但是数据结构复杂，多边形叠加分析比较困难。矢量电子地图可以随意缩放，缩放过程中不会失真，可以进行全局或者局部校正，更新起来也很方便。
例如成都市地图，按照比例尺1：200000（约），转化为24位位图，大约15M，而利用GPS实验室交通矢量地图自动生成平台生成的矢量地图数据库，只有137K，近3000条道路（矢量边）的矢量文件大小只有约61K。可见矢量电子地图的优越性。
2.2 GPS实验室交通矢量地图自动生成平台介绍
绝大多数GIS系统中使用的地图是以矢量地图作为其表现形式的。国内目前矢量地图常用的生成方式有两种，一种是用数字化仪从纸质地图中提取，另一种是从点位图中利用模式识别的有关理论进行识别和提取。生成一个准确而完备的矢量地图需要花费量的人力和财力，一个中等规模的城市用数字化仪生成矢量地图，大约需要一个月的时间。因此，如何以较小的代价和成本来生成一副实用的矢量地图，并在此基础上构造一个实用的GIS系统，是GPS实验室一直在研究的一个课题。
GPS实验室自1993年创建以来，一直在从事GPS定位、监控、导航和GIS系统的研究[16,17]。无论是GPS定位、监控或是导航，都离不开GIS系统的支持。经过多人多年的努力，GPS实验室已经形成了一套具有实验室特色的，而且比较成熟的GIS软件和GIS交通矢量地图生成平台。下面，我们就介绍一下GPS实验室开发的交通矢量电子地图生成平台[18-22]和GIS系统。
2.2.1 系统组成
我们所说的GIS往往是一个比较庞大的系统，而且包含了很多各类数据管理、决策的模块，它是一种针对性比较强的系统，对于不同的用户，往往对数据有不同的操作、管理、决策。但是它毕竟是一个以地理空间分布数据为基础的系统，所以有一个因素不能少，那就是电子地图，它为系统提供最基本的地理信息。
我们如何来组织一份矢量地图呢？数据是矢量地图的核心，电子地图可以看作由点、线、面这三种几何对象以及它们的属性数据构成的数据的集合，所以我们引入了图矢量库和地图数据库这两个概念。矢量库是一组图形描述数据，保存了地图的几何数据；数据库则是一组描述数据，保存地图各种几何对象的属性数据，二者之间通过地物对象的序号建立索引关系。如下图：
一副地图可以看成是由点、线、面三种几何图形构成的。点指的是单位之类的地物实体，线则是道路、铁路之类的实体，而区划这类的实体就可以用面来表征。依照传统的习惯，把点、线、面这三类地物按照从上到下的顺序排列。生成、编辑电子地图的过程就是生成、编辑地图矢量库和数据库的过程，下面我们来介绍一下这两个最重要的库。
2.2.2 地图矢量库
矢量库定义出几何结构的位置形状信息。点标志比较简单，只是一个点；面标志对应的几何结构就是一个多边形，也比较简单；而线标志则包含较多的内容，要相对复杂一些。我们下面主要介绍一下与线标志有关的一些定义，也就是道路的有关定义：
定义0：矢量边。是一些点的坐标的集合，表征着一条连续的折线。它有以下的性质：
a．点的排列顺序决定了折线的行进方向，决定了折线的形状和位置；
b．只有两个端点可以属于别的矢量边。
定义1：大节点、小节点、节点。大节点是矢量边的端点；小节点是指矢量边除端点之外的内部点；大节点和小节点统称节点。
定义2：弧。一条弧就是一条矢量边，是若干个节点的集合。组成弧的节点是顺序排列的。
定义3：路。路是若干条弧的集合。
2.2.3 地图数据库
地图数据库中包含了各种地物的属性数据。
对于面地物，需要知道的属性有：类型、位置、形状、名称、颜色等；
对于点地物，需要知道的属性有：类型、位置、名称、显示图标、显示级别等；
对于线地物，需要知道的属性有：类型、位置、形状、名称、颜色、显示宽度、显示级别等；
上面提到的各种地物的属性数据中都有一项——类型，也就是它所属的组（Group）。组，定义出了某一批地物的缺省属性，是一些具有相同或相近属性的同类地物的集合。整个数据库的层次如下所示：
地图的数据库有四个层次，最上层当然是地图数据库，它由三个部分（Division）构成的，也就是点、面、线三大类地物；每个部分又由若干个组（Group）构成；每个组又由若干个地物实体（Entity）构成，实体，就是点、面、线这类的地物个体。这种分层结构使得配置地图数据库时显得特别的方便。
2.2.4 面向对象的数据模型
采用面向对象的数据模型可以最自然地描述现实世界，将实体抽象为对象，用对象中的数据成员和成员函数模拟客观世界及其运动。面向对象的数据模型有很强的扩充性。根据面向对象的数据组织方式，用面向对象的方法设计了一个稳健的，易于扩充和修改的数据库模型。如图2.4所示：
地图对象类包含地图的属性和组成成分，属性表示地图的基本特征：地图名比例尺等等，在这个类的层次上我们可以定义地图的基本操作，例如放大、缩小漫游等。从这个对象的关系图来看，在实现的时候，地图的数据库与矢量库并不是完全独立的，相反，数据库实际上包含了矢量库。也可以这么看，矢量库实际上是一个几何对象集，提供某些Entity的几何数据。
Entity包含了基本地理对象的属性和空间几何信息，指明了基本地理对象的基本特征和组成的几何对象，几何对象包含几何对象的地理位置和相互关系的信息，可以分为纯几何对象类（如点、多边形等）和拓扑几何对象类（如节点、弧等），后者是由地图矢量库来提供的。
2.3 交通矢量地图的生成
GIS使用直观的地理图形方式来录入、管理、显示和分析与地理空间相应的各种数据，因此系统要同时具备图形处理功能和数据处理功能。为了给更上层的GPS或GIS应用系统提供一个准确、完备而且美观的矢量电子地图，首先要生成地图的矢量文件，生成矢量地图的拓扑结构——矢量库。我们采用的是从点位图中识别、生成矢量地图的方式。我们将从纸制地图扫描得到的点位图进行识别，提取出其中的道路信息[23-29]，然后将这些道路信息矢量化得到一副只包含道路信息的矢量文件，将这作为一副矢量地图的基础。然后，在这个基础上进行编辑、校正，并输入各种地图上的有关数据，生成电子地图的数据库，最终生成一个完整而准确的矢量地图。如下图所示：
从上面的框图中可以看出生成一副较完备矢量交通地图，主要包括以下三个步骤：
①彩色地图的道路识别；
②地图矢量化；
③矢量地图的校正和地图信息的添加；
彩色地图的道路识别，就是根据一幅彩色交通地图，利用一定的算法，提取出其中的道路、区域信息，形成一幅黑白位图。地图矢量化则是根据得到的线状的黑白位图抽取出有意义的模式特征。矢量化后的地图经过校正和添加地图信息就可以很好的应用于我们的监控和导航系统了。下面将简要介绍一下地图矢量化和地理信息添加两方面的内容，在这篇文章中我们主要研究由该平台自动生成的矢量文件
下面将以合肥旅游地图光盘地图为例，来演示地图的整个生成过程
图源是光盘地图地质出版社地图编辑室所编制的中国公路交通图册[30]
图2.6经过道路识别提取，二值化操作之后得到一副黑白点位图，如下图所示：
图2.7通过MapVectorTry地图矢量化软件完成预处理（平滑、去除毛刺）、细化、矢量化之后得到下图：
在图2.8的基础上，经过地图的编辑操作，加入地图属性信息，就可以得到一副完整的矢量地图。
2.4 地图矢量化
在这之前我们已经得到了由彩色地图得到的粗略的信息——线状的黑白位图，从这样细节背景中抽取出模式有意义的特征就是矢量化。在矢量化之前，一般要先作一些预处理工作， 以减少噪声的干扰，提高数据的质量，保证后续的细化处理和矢量化工作。
2.4.1 要用到的一些基本的参数
在处理时从左到右，从上到下对图象的每一个点进行判断处理。如上图所示，我们对每一个象素点用3×3的模板进行处理。用到以下几个函数
其中F的值成为P-1 的连接数，根据连接数，可以判断P点的性质：
I. F=0 表示这点为孤立点或是内部点；
II. F=1 表示这点为端点或拐点或是边界点；
III. F=2 表示这点为连接点；
IV. F=3，4 表示这点为分支点、交叉点。
见下图中的几个例子：
2.4.2 几种预处理操作
预处理操作主要包括以下几个方面：
2.4.2.1 平滑
平滑处理是将图象上由于噪声引入的孤立点去掉，将孔洞、缺口、间隙填补上，将小突起删除。平滑处理是预处理的第一步，平滑的结果将影响细化的结果，最终影响矢量化。
【处理1】
删除所有的孤立点。
【处理2】
利用下图的几种模板判断：
以上三种处理类型，每种类型包括：旋转n×90o 的情况，所以每种类型对应于四种情况。
【处理3】
判断每个点的交叉数，如果大于2，这个中心象素置成1。这样的处理可以将图中的细小的断点连接上。
【处理4】
在将前两步处理完成之后，将已置成-1的象素点全部置0。如此反复前两步处理，直到已经没有可以处理的象素点。
2.4.2.2 细化
细化处理是将图象上的线条细化成一个象素宽的线条的处理过程，细化的结果使得线条所在的地方总保持一个象素宽。对细化的一般要求是：保证细化后曲线的连通性，细化结果是原曲线的中心线，细化处理速度快，保留细线端点。矢量化结果的好坏，很大程度上取决于细化算法。这里所使用的是经典Hilditch法。
【处理1】
将模板沿扫描方向移动，当同时满足以下的六个条件时，将中心象素点置为-1，否则不作任何改变。
条件1：A(k)=1 中心象素为图形部分；
条件2：SB(2i) = 1 (i∈N2) , N2={0, 1, 2, 3} 中心象素为背景与图形的边界；
条件3：S|A(i)| =2 ( i∈N3) , N3={0, 1, ..., 7} 不删除端点；
条件4：SC(i) = 1 (i∈N3) , 保留孤立点；
条件5：F = 1 保持连接性；
条件6：A(i) ? -1 , 或 G(i) = 1 , i∈N3 , 线宽为2的部分只消除其一侧；
【处理2】
在【处理1】结束后，将已置成-1的象素全部置0，再次进行【处理1】，如此反复，直到【处理1】的结果不再有-1的象素点出现。
2.4.4.3 连接断点
【处理1】
寻找断点：将同时满足以下两个条件的点，
条件1：A(-1) = 1 中心象素为目标象素；
条件2：SA(i) = 1 (i∈N3) , 8邻域中只有一个目标象素。
【处理2】
判断连接：将端点之间两两计算距离，如果之间的距离小于给定的误差。则在这两点之间画一条直线。
2.4.4.4 删除毛刺
【处理1】
寻找毛刺：毛刺有两类端点，
A类端点：和连接断点处理中的端点一样；
B类端点：同时满足以下两个条件：
条件1：A(-1) = 1 中心象素为目标象素；
条件2：SA(i) = 3 (i∈N3) , 交点或分支点。
【处理2】
删除第一类毛刺：计算每个A类端点与B类端点之间的距离，如果小于给定的误差，则以背景色在二者之间画一条直线。
【处理3】
删除第二类毛刺：计算A类端点两两之间的距离，如果小于给定的误差，则在二者之间以背景色画一条直线。主要是删除图像点外细小的分杈，而且弯弯曲曲的毛刺必须经过多次处理才能够删除干净。
2.4.3 跟踪矢量化
【处理1】
沿扫描方向寻找节点。所谓的节点满足：
条件一：A(-1) = 1, 中心象素为目标象素；
条件二：SA(i) ? 2， 端点或者是交点或是分支点。
【处理2】
以该点为出发点，在3×3的模板中以0~7的方向搜索该点的8邻域，找到第一个未被矢量化过的象素，记录这个点。然后一这点为出发点，再搜索，如此反复，直到找到另外一个节点，这样就将连接在这两个节点之间的所有象素记录到一个数组中。
【处理3】
将上一步得到的象素数组矢量化：将两个端点分别设成起点S、终点E，在S、E之间找到一个与SE连线偏移最大的点M；如果误差小于要求的误差，就可以用S、E两点表征出这条矢量，如果误差大于要求的误差，则M是一个矢量边内的小节点，然后矢量化S— M、M— E，如此反复，直到找不到大于要求误差的点。
【处理4】
重复以上的跟踪和矢量化，直到所有满足节点要求的点的所有分支均被找完。
【处理5】
寻找循环链（岛屿链）：经过以上的步骤所有不属于循环链的象素点均已被标志。只要找到某一个未被标志的象素点，即可以找到它所在的循环链，以这点为起点，进行跟踪，终点仍是这点，记录之间的所有象素。将获得的象素数组矢量化（【处理3】）。如此反复，直到找不到被标志的点。
根据上述的各种处理，在程序中的矢量化流程如下图所示：
2.5 矢量地图的编辑
地图矢量化完成以后，我们可以得到一个包含了所有道路拓扑信息的基本的矢量文件，它只是矢量地图库的一个雏形。在此基础上，我们要对矢量地图进行编辑，将地图上地物的属性信息输入地图属性数据库中，并确定地图的地理参数，从而生成一个完整而又准确的交通矢量地图。
矢量地图的编辑主要完成以下的几个方面的工作：
编辑GIS地图数据库；编辑地图的拓扑结构；利用已有的轨迹记录确定地图的地理参数。
一副地图编辑过程可以用如下的流程图来表示：
2.5.1 地图数据的结构
数据是地图的核心。一副完备的电子地图的数据量是很大的，我们采用了分层的数据结构来组织这些数据，最大限度的考虑和满足用户的需要。地理数据的分层结构：
电子地图由基本地理对象集（点、线、面状地物集）组成；基本地理对象由几何对象（点、线、面）加上其属性数据组成，几何对象包含地理对象的几何数据，并维护对象间的拓扑关系。
2.5.2 矢量库的组织
地图矢量库保存了组成地图的线状元素的几何数据，也就是包含了节点、弧和路的信息。它是整个电子地图和GIS系统的根本，也是后面实现路径寻优、动态轨迹校正等智能决策功能的基础。下面我们就来看看在这个矢量库中是如何组织这些数据的。像我们在最前面提到的，弧是节点的集合，路是弧的集合。
我们可以把矢量库看成由三个表构成，一个节点的表，每一行表示一个节点，X、Y坐标组成这个表的两个列；一个弧的表，它的每一行表示一条弧，它的列是构成这条弧的点；还有一个路的表，它的每一行表示一条路，构成这条路的所有的弧是各个列。如图2.15所示。
另外，对于一个GIS系统，不可或缺的功能就是根据地理空间信息进行一些决策，例如搜索两个给定点之间的最优路径。在前面的讨论中，我们可以看到节点、弧、路之间的关系是很密切的，因此我们提供充分的机制，使得它们之间能够顺利的相互访问。如图2.15所示
2.5.3 矢量地图的编辑
主要包括地图的整体操作和地图上地物信息的编辑。
地图的整体操作包括：地图的拼接和地图的平移。这两个功能是整个GIS和地图平台中非常重要的功能。因为一幅纸制地图往往是很大的，由于条件的限制，很难把地图全部一次扫描、处理完成，一般是将地图分成几个部分，分块扫描处理，得到这几块小图的矢量文件，然后再将这几块矢量文件合并起来；地图拼接完成的就是这个功能。之后要将拼接图调整到合适的位置，然后将其中有用的信息加到目标图上，这就需要对地图进行整体的平移。
地图上地物信息的编辑包括：路的操作（定义，删除）、矢量边的操作（添加、删除、弧的整体调整）、节点的操作（节点的添加、删除、合并、拆分）、区域的操作（定义、调整、删除）。这些都涉及地图矢量数据库中各种拓扑结构的调整和它们之间的相互关系，对于整个矢量地图具有重要的意义，也是整个GIS系统和地图平台最重要的功能。
