本章首先介绍GPS全球卫星定位系统、GIS地理信息系统的基本概念，以及当前国内外发展的现状和它们在城市交通GIS的应用，并由此指出研究城市栅格地图道路识别系统的重大意义。由此构成本论文选题的时代背景与技术背景。
§1.1 GPS、GIS系统简介
§1.1.1 GPS（全球定位系统）简介
GPS是英文Navigation Satellite Timing and Ranging/Global Position System的字头缩写词NAVSTAR/GPS的简称。它的含义是，利用导航卫星进行测时和测距，构成全球定位系统。[1]人们将这一全球卫星定位系统简称为GPS。GPS全球卫星定位系统从提出到建成，经历了20年，到1994年24颗工作卫星进入预定轨道，系统全面投入运行。GPS系统因其应用价值极高，所以得到美国政府和军队的重视，不惜投资300亿美元来建立这一工程，成为继阿波罗登月计划和航天飞机计划之后的第三大空间计划。
GPS系统的空间部分由24颗卫星组成，均匀分布在6个仰角为55度的轨道面上。GPS系统的利用者接收卫星发送的扩频信号，测量电波传播时间求出卫星到接收机天线的距离，利用空间三球相交一点的原理，解算以接收机位置为未知数的方程，从而确切知道接收机的位置，也就是说，只需接收到3颗卫星的信号，就能确定用户的二维（经度、纬度）位置。GPS系统从根本上解决了人类在地球上的导航和定位问题，它可以为全球用户提供连续、实时、高精度的三维位置、速度和时间信息，可以满足各种不同用户的需要。在海洋上，它可用于舰船海上协同作战，在海洋交通管制、海洋测量、石油探测、海轮进出港管理等领域提供定位服务；在陆地上，可用于各种车辆、坦克和陆军等的定位；它还可以广泛应用于人们的日常生活和科学研究中，如汽车驾驶、旅游、探险、测绘、勘探考古等方面。GPS定位系统的建立，给导航和定位技术带来了巨大的变革。
美国政府在进行GPS系统设计时，计划提供两种服务。一种为标准定位服务—SPS，利用粗测/捕获码（C/A码）定位，预计精度约为400m，提供民间用户使用。另一种为精密定位服务——PPS，利用精密码（P码）定位，精度达到10m，提供给军方和得到特许的用户使用。但在GPS实验卫星应用阶段，多次实验表明，实际定位精度远高于此值，利用C/A码定位精度可达到15~40m，利用P码定位精度可达3m。为了维护美国自身利益，美国国防部在GPS系统中加入了SA（Selective Availability）政策——选择可用性政策，人为地将误差引入卫星时钟和卫星数据中，降低GPS的定位精度，以防止未经许可的用户把GPS用于军事目的。采用SA政策后的GPS系统C/A码定位，水平定位精度为100米，垂直测量精度为157米。美国国防部常年对SA政策进行测量，并根据形势和要求对部分和全部卫星取消SA政策。SA政策的引入，在一定程度上限制了GPS的应用，为了提高定位精度，人们研究和发展出差分GPS技术——DGPS（Differential GPS）。但是，DGPS系统需要建立相应的差分基准站和监测站，造价昂贵。随着GPS应用的不断发展，GPS广大用户要求取消SA政策的呼声越来越高，考虑到庞大的GPS应用市场，美国政府最终于2000年5月1日取消了SA政策，这必将促进GPS定位和导航的应用的进一步发展。
2000年以后，以波音公司为首，休斯空间和通信公司、计算机科学公司(CSC)、洛克西德马丁管理与数据系统(M&DS)和雷声公司开始研究开发新一代的全球定位系统——GPS III。GPS III的结构将基于现有的卫星导航系统，并将开发出具有创新结构的新的GPS系统。
§1.1.2 GIS（地理信息系统）简介
GIS地理信息系统（Geographical Information System）是集计算机科学、地理地质学、测绘科学、环境科学、空间科学、信息科学和管理科学等为一体的多学科结合的新兴边缘科学。[2]它是在计算机硬件、软件系统的支持下，采集、存储、管理、分析和描述整个或部分地球表面（包括大气层在内）与空间和地理分布有关的数据的空间信息系统。它是融合计算机图形和数据库与一体，用来存储和处理空间信息的高新技术，它把地理位置和相关属性有关地结合起来，根据用户地需要将空间信息及其属性信息准确真实、图文并茂地输出给用户，满足城市建设、企业管理、居民生活对空间信息的变化，借助其独有的空间分析功能和可视化表达功能，进行各种辅助决策。
地理信息系统具有一下三个方面的特征：
1)具有采集、管理、分析和输出多种地理空间信息的能力，具有空间性和动态性；
2)以地理研究和地理决策为目的，以地理模型方法为手段，具有区域空间分析、多要素综合分析和动态预测能力，产生高层次的地理信息；
3)由计算机系统支持进行空间地理数据管理，并由计算机程序模拟常规的或专门的地理分析方法，作用于空间数据，产生有用信息，完成人类难以完成的任务。
地理信息系统是从20世纪60年代开始逐渐发展起来的新技术。由于地球是人们赖以生存和发展的基础，所以GIS是与人类的生存、发展和进步密切关联的一门信息科学技术，受到人们愈来愈多的重视，其应用已涉及到各行各业。特别是近几年来，由于全球信息化的飞速发展、信息高速公路、“数字地球”、[3]“数字城市”、“虚拟社区”理论的提出，GIS产业受到了空前的关注，越来越多的人投身到GIS的学习浪潮中。
20世纪80年代是GIS普及和推广应用的阶段。由于计算机的发展，推出了图形工作站和PC微机等 性价比大为提高的新一代计算机，计算机和空间信息系统在许多部门广泛应用。计算机网络技术的应用，使地理信息数据的长距离传输时效得到极大的提高。GIS系统软件和应用软件的发展，使得GIS的应用从解决基础设施的规划（如道路、输电线）转向更复杂的区域开发和规划，例如土地的农业利用、城市化发展、人口规划与布局等，地理因素成为投资决策中不可缺少的依据。许多国家把GIS作为有关部门的必备工具投入日常运转。与卫星遥感技术想结合，GIS开始用于全球性问题研究，例如全球沙漠化、全球可居住区的评价、厄尔尼诺现象及酸雨、核扩散及核废料以及全球变化与全球监测。美国军方制作了全球1:100万空间数据库DCW，原苏联制作了全球数字调和模型和数字正摄影像。20世纪80年代，GIS软件的研制和开发也取得了很大的成绩，仅1989年市场上有报价的软件就达70多个，并且涌现出了一些具有代表性的GIS商用软件，如Arc/Info, MicroStation, MGE Intergraph, Auto CAD/Arc CAD等。
我国GIS的发展虽然较晚，但发展势头迅猛，大体上经历了4个阶段，即起步（1970－1980年）、准备（1980－1985年）、发展（1985－1995年）、产业化（1996年以后）阶段。GIS已在很多部门和领域得到应用，并引起了政府部门的高度重视。从应用方面看，地理信息系统已在资源开发、环境保护、城市规划建设、土地管理、农作物调查、交通、能源、地图测量、林业、房地产开发、自然灾害的监测和评估、金融、保险、石油与天然气、军事、犯罪分析、运输与导航、110报警系统、公共汽车调度等方面得到了具体应用。国内已有城市测绘地理信息系统或测绘数据库正在运行或建设中。一批地理信息系统软件已研制开发成功（如GeoSTAR, CityStar, MapGis等），一批高等院校已设立了一些与GIS有关的专业或学科，一批专门从事GIS产业活动的高新技术企业相继成立。此外，还成立了“中国GIS协会”和“中国GPS技术应用协会”等组织。
进入21世纪，随着地理信息产业的建立和数字化产品的普及，GIS技术已深入到各行各业，成为政府部门进行科学管理、快速决策及人们生活、生产、学习和工作中不可缺少的工具。朱鎔基总理在中共十五界二中全会报告中明确指出地理信息将作为一个产业来加以发展，我国的GIS正迎来一个阳光明媚的春天。
§1.2 城市栅格地图道路识别研究的意义和现状
§1.2.1 城市交通GIS研究的意义
GIS的概念地理信息系统(Geographic Information System 简称GIS)是一项以计算机为基础的新兴技术，围绕着这项技术的研究、开发和应用形成了一门交叉性、边缘性的学科，是管理和研究空间数据的技术系统，在计算机软硬件支持下，它可以对空间数据按地理坐标或空间位置进行各种处理、对数据的有效管理、研究各种空间实体及相互关系。通过对多因素的综合分析，它可以迅速地获取满足应用需要的信息，并能以地图、图形或数据的形式表示处理的结果。
交通是国民经济发展的两大支柱之一。交通问题具有明显的地域特征，是地理信息科学的一个主要研究发展。此外，交通技术的发展与电子技术、通讯技术、计算机技术等高新技术的发展息息相关，而这些高新技术同时也是实施“数字地球”战略必须着重发展的技术。可以毫不夸张的说，交通将是“数字地球”战略发展的最大受益者之一，同时也是实施“数字地球”战略的一个重要组成部分。
城市交通网络在城市发展中占有至关重要的地位。它不仅是城市的一个重要组成部分，同时也决定了城市中居民的生活方式。长期以来，交通问题已成为困扰城市发展的重要问题。世界各国都面临这日益严重的城市交通问题，如交通拥挤、车辆行驶缓慢、交通事故频繁及其由于交通堵塞造成的大量空气污染等问题。很多发达国家逐渐认识到，欲有效解决这些问题，仅仅依靠道路建设，扩大路网规模是远远不够的，交通问题的解决必须依赖现代信息技术与管理技术的有机结合。他们纷纷呼吁对现代交通问题给予新的认识，建立卓有成效的、对环境危害低的交通系统，更方便地进行客货运输，促进经济发展，减少交通事故。
20世纪90年代初，美国、日本和西欧等竞相投入大量资金和人力，开始大规模地进行道路交通运输智能化的研究和实验，开始时称之为“智能车辆道路系统”（Intelligent Vehicle and Highway Systems,IVHS）,进行道路功能和车辆智能化的研究。随着研究的不断深入，系统功能扩展到道路交通运输全过程及其有关服务部门，发展成为带动整个公路交通运输现代化的“智能交通系统”（Intelligent Transportation Systems，ITS）。目前，ITS的发展已经使高科技研究人员与产品成为现代交通工业的重要的新生力量与组成部分。
ITS是将先进的信息技术、数据通讯传输技术、电子传感技术、电子控制技术以及计算机处理技术等有效地集成，运用于整个地面运输管理体系，而建立起的一种在大范围内、全方位发挥作用的，实时、准确、高效的综合运输和管理系统。[4]具体在公路运输及城市交通领域，该系统将汽车、司机、道路及相关的服务部门相互联接起来，并使汽车在道路的运行功能智能化。ITS主要由6个高级交通系统构成，分别为：高级交通管理系统、高级出行信息系统、高级车辆控制系统、商业车辆运行系统、车辆自动定位系统及车辆自动识别系统。ITS通过公共服务系统完成公路与街道的交通监控，为出行者提供交通信息，对可能出现的险情及延误预先提出警告，帮助交通管理部门对车辆进行有效的实时疏导、控制和事故处理，减少交通堵塞和延误，辅助车辆的自动导航，进行公共交通的实时调度和行驶路线的调整，帮助运输部门增加运客率，降低运营成本，提高商业运输效率等。ITS这些辅助功能使路网上的交通流运行处于最佳状态，改善交通拥挤状况、减少交通阻塞，最大限度的提高路网的通行能力，提高整个公路运输系统的机动性、安全性和生产效率、使公众能够高效的使用公路交通设施和能源。
§1.2.2 城市栅格地图道路识别研究现状
在过去，从地图中获取地理信息是非常昂贵的并且是高时耗的一项工作，因为整幅地图的信息输入借助于数字化仪由人工手动操作，虽然它具有很高的数字压缩比以及较低的硬件损耗而且操作比较简单，但是在当今这个信息爆炸对更新要求较快的时代，它的制图周期太长，更新太慢，信息更换不及时的缺点暴露无疑，所以极为需要一个地图自动输入系统。近些年来，已经出现从纸质地图中提取地理信息的自动或是半自动的系统。
文献[5]依据中心线作为道路网络中最重要的信息这一特性提出一个道路自动提取的算法。作者在先前已经做的边界跟踪算法，名为PVT（parallel vector tracer）[6]，目的在于提取矢量地图。但是只要原始地图中出现路为文字或是路标等个体切断，那么跟踪器会在割断处停下，上述算法就完全失效。文献[5]针对这个问题做了详细研究并提出解决的办法。文中选取的是二值图像，首先使用设定阈值T1消除孤立的黑像素连接区域，再消除字符，主要满足轮廓线长度在T2和T3之间、水平垂直方向的长度小于T4并且转折点数大于T5，那么这个字符即被消除。对上面进行预处理过的图像进行特征点提取，处理交点处的向量，删除前面所选出的重复向量，判断交点处的向量如何连接，消除选出的噪声向量，最后连接与道路或是桥梁交叉向量。当然地图经过这样的处理后，依旧会产生错误，文中最后也做了后续处理，其一是校正交叉路口的扭曲形状，其二是对由字符割断的向量连接中有误判的情况进行纠正。行文中对N×N的图像分别做水平方向和垂直方向的扫描线，设定规则函数来连接出现在扫描线上的相邻点，由此构成水平向量和垂直向量；再根据所设定的连接条件来合并细小向量，最后形成矢量地图。
文献[7]中介绍了一个从纸质地图中自动提取道路网络的方法，强调于从地区纸质地图中提取拓扑道路网络。该文的理论依据是依靠提取和连接到路的中心线从而形成道路网络。在道路网络构建的过程中，重点是要解决合并和连接问题，因为地图中不可避免的出现粘连字符、分裂道路段等问题。主要方案是用扫描仪将纸质地图转换为灰度图像，经滤波去除噪声像素得到的灰度图用二值化的方法得到主处理过程的输入图像；再使用分离字符的方法解决中心线连接时会出现的字符割断中心线的问题；将这样处理过的图像转换成矢量图，利用感知器分类算法解决大量分裂道路段的问题；最后进行中心线提取，解决前面没有完全处理的粘连字符的难题。该文的实验结果良好并且给出修正过的示例，但是这篇文章的图源中所包含的字符为英文字符，道路线宽度一致，还有很重要的一点文中道路和文字非常清晰，区域块形状明显。如图1-1（该图取自文献[7]）。该文所提及的分离字符的算法相当新颖，使用CCA(Connected component analysis)算法[8]提取粘连字符，使每个粘连部分都被一个矩形包围；用尺寸过滤的方法，选出尺寸出现频率较高的矩形，并将这样的矩形框去除，也即去掉了大量的字符，因为在该图源中字符大小一致，所以字符大小的矩形出现频率最高。因而可以滤出大部分字符。此外，还有一点，它避开了彩色地图的颜色问题，只是针对二值图像进行处理。
图1-1 二值化后的新加坡街道图
在文献[9]中，作者提出一种从彩色地图中的提取道路的方法。这是所查文献中为数不多的提及图源是彩色地图的提取算法。在大多例子中，由多层图像来构建地图，每一层都是用一种颜色表示，代表地图信息的一个子集。该文使用了颜色分割，道路图像修复和提取骨架的算法。关键是提出一个基于条件膨胀的道路恢复算法确保道路信息的精度，消除和减少了图像中的道路变形。它的图源是Korea地形图（见图1-2）。该文指出了人眼看来无变化的颜色块而实际上是多种颜色的混合体，从而对于图源中不同类点分别选取了它们的聚类中心点，计算同一类的像素点。将原图像分成多层，其中红色聚类的上图像的道路层。如果仅仅是不断重复膨胀算法，那么整个图像中的道路将无限制的增长，故必须限制其不断增长的趋势。鉴于切断道路的都是黑色字符层，故将其设为约束性条件。上面我们已经得到分层的二值图像集，定义A={A0，A1，⋯⋯An},A0为黑色字符层，其他A1，⋯⋯An分别作为从原图中分离出来的区域。那么只要当A0不为空集，那么就对Ai进行膨胀运算，直至A0被膨胀完毕。经过开运算消除轮廓线，用闭运算消除内部噪声，最后得到较好矢量化结果。
图1-2 左为Korea的地形图，右为左图的部分放大
以上是目前国外相关研究状况中比较有代表性的三类，文献[5]是根据数字化仪原理来提取道路的一类，文献[7]依据道路中心线来判断道路的一类，文献[9]将图像分层后进行道路提取的一类，当然还有一些其他的对于地图中道路网络的提取做了大量的工作如文献[10－13]等，在此就不一一罗列。
鉴于地图中道路识别一直都是栅格地图中识别的重点和难点。在国内，这方面的研究也已经成为一个活跃的研究领域,到目前为止已经提出了不少方法。主要问题还是集中在有关中文字符形成噪声的处理上，这些处理方法可以归纳为两大类：(1)第一类方法[文献14,15]：根据文字要素在栅格图象上的孤立性、连通性及尺寸大小特征，采用8邻域方法计算所有连通成分，求得每个连通成分的外接矩形框的大小，采用面积、宽高比和密度等数字特征进行滤波实现图文分离。但是由于栅格地图上线划要素的比例较大，线划要素本身多数都是连通的，因此这类方法计算量大、处理时间长、效率低；同时这类方法对文字的尺寸比较敏感，特别是多尺寸文字混排的情况；它识别英文的效果比较好，由于汉字的复杂性造成单个汉字并不一定连通，因此误判率较高。(2)第二类方法[文献16,17]：对于栅格地图，不管图象上的要素类别，都一起进行细化、跟踪矢量化处理，在矢量图形上依据线划的长短提取和分离文字要素。这种方法对细化和矢量化算法的要求很高，细化、矢量化过程中文字和线划会发生畸变，尤其是文字和线划要素本身模糊不清时，这种畸变更为严重，使得分离出来的文字和线划有变形，给下一步的识别和理解带来了困难。
通过对国内外现状的研究，我们研究一种忽略中文字符本身的方法来提取道路，但是并不是对地图直接进行细化，矢量化。在后面的文章中我们将重点叙述。
§1.3 本文的研究对象及其特点
§1.3.1 栅格地图中道路识别的难点
GIS系统的难点集中在纸质地图数据的自动输入部分。纸质地图的印刷特点决定了它的自动输入具有以下技术难点：
1）图颜色分布范围不均，同一种颜色在地图不同位置的色度、饱和度和亮度的范围大小不一致。因而必须综合考虑全图不同位置的颜色样本，选取最佳分色阈值或最佳分色判决函数。
2）地图区域内图像失真。地图印刷的套色不佳，使得分色后的图像区域之间容易被噪声点或是噪声区域“粘连”。
3）地图图像中，区域表现为多种形状交织的复杂结构。图中的文字、图标等信息，由于与区域颜色不同，在分色后区域图像的完整性遭到一定程度的破坏，这给道路的正确提取造成很多困难。
4）相对于区域图像来说，街道完整性的破坏程度过大，直接从原地图中获得完整的道路图像十分困难。产生该情况的原因：道路中间印刷街道名称，将街道图像分成若干段，造成“断路”。
5）字符种类多，大小不一，方向任意，位置随机，颜色深浅不一。
§1.3.2 本文的研究对象及其特点
本文采用的图源是地质出版社地图编辑室所编制的中国公路交通图册[18]。
所选图源的颜色特征如下：河流，湖泊以及护城河等是用深浅不一的蓝色表示的，与绿地有关的，如公园，绿化带等是用绿色表示的；城市区域是用颜色一致的棕色表示，城市道路根据路的性质不同分别用绿色，粉色，橙色等几种颜色表示；但是在道路和区域中存在一些类似于噪声的杂色点，还搀杂大量用黑色表示的文字及少量的表示特殊含义的标志，如医院的标号“
”，学校的图标“
”，及交警大队的图标“
”等等。
针对本文采用的图源，地图特征归纳如下：
1）地图是由道路、区域和噪声构成，地图中的噪声主要包括：字符、符号（如“红十字”符号用来标示该地方是医院）以及河流线，公园区等。
2）道路和区域的颜色分布很均衡，区域的颜色只有一种，其中道路的颜色有五种，分别代表不同功能的道路，大部分以白色（高亮度）标示。
图1-3a 原图 图1-3b 原图的灰度直方图
3）灰度直方图的分段特征,参见图1-3b。地图的道路、区域和噪声三层在灰度分布上有比较明显的界限，噪声主要位于低灰度区（灰度级范围：0～100），区域主要位于中等灰度区（灰度级范围：101～200），道路主要位于高灰度区（灰度级范围：201～255）。0对应的灰度最小，也就是最黑，255对应的灰度最大，也就是最亮。纵坐标表示具有某一灰度级的像素数目占总的像素数的比例，也就是该灰度级出现的频率。图中的最长的一条线所在的灰度级就是区域的灰度，因为在地图中，区域总是拥有最多的像素数。
4）地图中的文字笔划的宽度远远小于道路的宽度，而文字方块占用的面积也远远小于区域的面积，这使我们能够用某种方法（如灰度形态学）来去除道路上和区域里的文字。
5）地图中的某些符号所围成的方块内部的颜色与道路的颜色相同。如不事先消除这些符号，会形成道路识别中强干扰信号。
6）有些结构稍复杂的方块字落在道路上，其围成的方块的宽度或高度有的会超过路的宽度。
7）地图中有的地方会出现两条路离得很近的现象，这样在道路在识别之后会出现路的粘连。
此外，其道路自身还具有以下特点：
1)道路宽度变化比较小,并且变化很慢；2)道路方向变化比较慢；3)道路总是具有一定的长度。
§1.4 本文的内容及安排
§1.4.1 研究方案
1）采用的研究方法
采用理论推导、算法选取与实验验证相结合的方法。
2）技术路线
在Microsoft Visual C++ 6.0开发平台下，利用实验室现有的软件包，根据国内外较成熟的地图背景特征抽取与识别特定信息的思想，结合算法实现与改进，最终实现输出优化，得到较高的道路信息识别率。
3）实验方案的可行性分析
中国科学技术大学GPS实验室已完成了自主知识产权软件包“GPS监控导航GIS开发平台”已用来成功解决合肥、厦门等6个城市的向量地图。本研究是建立在实验室研究成果之上，提出较好的道路区域识别阀值调整策略构建完整的闭环系统，提高道路信息识别率。
§1.4.2 解决的问题
1）构建出本论文提出的地图道路信息识别闭环系统,利用算法实现论文提出的思想，客观评价道路信息识别率，撰写相关学术论文。
2）解决当前图象处理领域中，提高交通地图背景下的道路信息识别率的问题。§1.4.3 本文的内容安排
本文内容安排如下：
城市栅格地图道路识别研究的意义和现状以及本文研究对象的特点和研究方案。
第二章 从栅格地图和矢量地图的基本概念出发，介绍了矢量地图同栅格地图相比具有的一些优势，矢量地图的生成，矢量地图的编辑等。同时，对矢量地图中道路的拓扑结构和矢量地图库的组成给出了清晰的阐述。
城市地图道路识别系统构建及实现，包括其基本思想和具体实现，给出了程序实现界面。
