§5.1 通用的地图道路识别与提取方法
下面的方框图示出用传统的方法来提取地图道路的过程。描图的过程就是用一张和源地图一样大小的透明纸蒙在地图上，然后用铅笔沿路的中心线进行描迹，最终得到一幅黑白纸质图。然后用数字化仪逐点进行数字化后扫描进计算机，得到黑白BMP位图。然后在此基础上对其进行细化和矢量化操作。这种方法虽然简单，但是速度很慢，而且会容易带来噪声，随着人们对地理信息需求量的增加，随着地理信息处理的批量化，随着高性能计算机的制造使得处理海量地理信息越来越快，人工识别愈来愈被看成是一项既费时又费力的工作，地理信息的识别也越来越成为地理信息系统发展的瓶颈。基于此，我们必须建立一个计算机提取城市地图道路的自动识别系统以取代目前的人工识别系统。
图5.1 传统的方法来提取地图中的道路
§5.2 现有文献中关于道路提取的理论和方法
文后的参考文献中有一些是关于地图道路的提取与识别的。综合这些文献的内容来看主要有以下一些特点：
1、地图图源多种多样。有的是选取航空遥感图像；有的是选取纸质地图，然后用扫描仪扫描进计算机的，正如5.1节所叙述的那样。
2、提取地图道路所选用的方法依所选取的图源不同而不同。可以分为三类：基于图像的颜色特征的方法、基于地图的拓扑特征的方法和两种方法的结合。
3、从识别效果的角度看，并没有一种方法使对目标的识别达到完全自动化，往往需要人工的干预，如人的先验知识。
§5.3 本论文的工作
本论文的工作主要有以下两个方面：
1、构建了基于灰度分割的彩色栅格城市交通地图道路信息的识别与提取系统RoadExtractor。撰写的论文已收入ICCA’02（国际控制及自动化2002学术年会，于2002年6月16日-19日在厦门大学召开）会议论文集（ISBN:0-7803-7413-4; IEEE Catalog Number: 02EX560C; Page:260-264）。
2、提出了基于人工神经网络的道路提取与识别闭环反馈控制系统，为以后的研究奠定了基础。
§5.4 本论文中所研究的对象——地图的特征分析
本论文所研究的地图是来自《中国公路交通图册》（光盘版），同一图层的颜色分布是很均衡的，而由纸质地图经扫描进计算机，其颜色分布却受到了很大的破坏。本论文选取该地图册中的合肥市城市交通地图的一部分（图5.4）来进行研究，对该地图进行分析之后发现它有以下一些比较明显的特征：
1、地图是由道路、区域和噪声构成，地图中的噪声主要包括：字符、符号（如“红十字”符号用来标示该地方是医院）以及河流线，公园区等。
2、道路和区域的颜色分布很均衡，区域的颜色只有一种，其中道路的颜色有五种，分别代表不同功能的道路，大部分以白色（高亮度）标示。
3、灰度直方图的分段特征 从地图的灰度直方图（图5.2(b)）中可以看出，地图的道路、区域和噪声三层在灰度分布上有比较明显的界限，噪声主要位于低灰度区（灰度级范围：0～100），区域主要位于中等灰度区（灰度级范围：101～200），道路主要位于高灰度区（灰度级范围：201～255）。图5.2(b)的横坐标为灰度数值，范围为0～255，从左到右逐渐增大，0对应的灰度最小，也就是最黑，255对应的灰度最大，也就是最亮。纵坐标表示具有某一灰度级的像素数目占总的像素数的比例，也就是该灰度级出现的频率。图中的最长的一条线所在的灰度级就是区域的灰度，因为在地图中，区域总是拥有最多的像素数。
4、地图中的文字笔划的宽度远远小于道路的宽度，而文字方块占用的面积也远远小于区域的面积，这使我们能够用某种方法（如灰度形态学）来去除道路上和区域里的文字。
5、地图中的某些符号对道路的提取有很大的影响，因其所围成的方块内部的颜色与道路的颜色相同，这样如不事先除掉，道路就会产生过识别。
6、有些结构稍复杂的方块字，如果落在道路上，其围成的方块的宽度或高度有的会超过路的宽度，这样路在此处会形成断点，造成道路的欠识别。
7、地图中有的地方会出现两条路离得很近的现象，这样在道路在识别之后会出现路的粘连，造成道路的过识别。
图5.2 地图及其灰度直方图
以上的7个特点中最后两点是影响道路识别率的主要因素，所以在识别与提取地图道路的过程中要采取比较有效的方法尽量减少误识别。
§5.5 基于灰度分割的彩色城市交通地图道路的识别与提取
根据5.4节的分析，我们提出基于灰度分割道路提取与识别算法。图5.3是该算法的流程图。下面对该流程图作详细的介绍：
图5.3 流程图
5.5.1 去除地图中的符号
地图中的符号，如“
”（红十字，表示该位置是医院的所在地）对道路信息的识别与提取有比较大的影响，所以在提取道路之前，必须采用有效的方法来去除这些符号，在这里模板匹配是一种很有效的方法（第三章介绍了用聚类分析的方法也可以去除地图中的符号）。利用模板匹配可以在一幅图像中找到已知的物体，拿已知的模板(在本例中为“”符号所形成的图像)，和原图像中同样大小的一块区域去进行对比，如果不相匹配，然后平移到下一个像素，仍然进行同样的操作。如果在原图像的某一位置，对在模板中所有像素都进行了比较之后，出现差别最小，那么该位置对应的与模板同样大小的一块区域就是我们要找的物体。
我们采用以下的四个公式来计算原图像当前搜索位置处的像素块同模板之间的相似度：
公式(5.5.1)用来计算整个模板的能量，并存储在变量SigmaT中，th和tw代表模板的高度和宽度，T(i,j)表示(i,j)处的像素的颜色值，对于一个模板，SigmaT是一个常量，不随在原图像中的搜索位置的变化而变化。公式(5.5.2)计算(x,y)处与模板同样尺寸的像素块（以下简称搜索块）的能量，(x,y)是搜索块左上角的坐标。公式(5.5.3)计算(x,y)处搜索块同模板之间的互相关系数。公式(5.5.4)利用式(5.5.1)、式(5.5.2)和式(5.5.3)的结果计算原图像(x,y)处的搜索块同模板之间的相似度，并将结果保存在变量R(x,y)中。如果R(x,y)>T（T为事先设定的阈值），我们就认为原图像(x,y)处的像素块同模板能很好的进行匹配，说明该位置处就存在一个地图符号。找到了符号之后，如果符号落在区域里，我们就以区域的颜色填充符号所围成的区域，否则我们就以道路的颜色填充。
本论文利用这一算法，提取地图中的符号，取得了比较好的效果。在图5.4中，我们可以看到，“”（红十字，表示此处是医院）等符号，对地图的道路的识别有很大的影响，因此在提取与识别地图道路之前我们必须把这些符号去掉。
图5.5所示为去掉符号后的结果，图5.4中的“”符号被图5.5中的黑色小方块所代替。由于这些符号落在了地图的区域里，故我们以区域的颜色填充这些黑色的小方块，如图5.6所示。
图5.4 原图
图5.5 图5.4中的地图符号被黑色的小方块代替 59
图5.6 黑色小方块用区域的颜色代替
5.5.2 归一化道路的颜色
因为在地图中不同用途的道路以不同的颜色标示（见图5.4），为了顺利提取出道路，还必须统一道路的颜色，使得所有的道路以一种颜色（白色）标示。在这一步我们利用了地图的图例（见图5.7），因为每一类地图集都有自己的图例。图例中标示道路的颜色很容易提取，在提取了图例中的道路颜色之后，我们扫描整幅图像来计算图例中的道路颜色和地图中各种颜色之间的距离，如果距离小于一个比较小的阈值的话，我们就认为在地图中该颜色标示的是道路，并且把该颜色替换为白色（高亮度）。颜色距离的计算公式如下所示：
这里R1，G1，B1分别代表地图中颜色的红色，绿色和蓝色分量；R2，G2，B2分别代表图例中道路颜色的红色，绿色和蓝色分量。D代表这两种颜色之间的距离。
图5.7 图例
图5.8示出归一化地图道路颜色之后的结果，从图中可以看出，地图道路都以白色来表示，这有利于下面对地图的操作。
图5.8 归一化道路的颜色
5.5.3 腐蚀文字
文字的笔画因其宽度与路的宽度相去甚远；文字方块所围成的面积也远远小于地图区域的面积；也因文字噪声的所形成的图像的灰度均小于路和区域的灰度，我们可以利用数学形态学的理论来去除文字。文字的笔画看成是结构单元，地图是目标图像。利用灰度形态学的腐蚀和膨胀操作来消除文字的算法如下（每次扫描3×3像素块）。
图5.9(a)示出原图，其中的黑色的文字被看成是结构元素；图5.9(b)示出利用数学形态学的腐蚀和膨胀操作后的结果。
仅仅扫描一次原图像道路网络是不能完全提取出来的，它可能扫描数次，直到噪声完全从地图中去除为止。
5.5.4平滑道路
图5.10示出腐蚀文字后的结果，从图中可以看出，腐蚀文字后的道路仍然有许多密密麻麻的小黑点，我们必须平滑之。
下面介绍一下平滑的算法。根据我们的先验知识：一幅地图，无论它多复杂，区域的像素数总是多于道路的像素数，在图5.10的黑白地图中，我们通过统计黑白像素的比例，得到白色像素集合为道路，黑色像素表示区域。
先逐行扫描图5.10，如果两个白色像素之间连续黑色像素点的个数小于一个比较小的阈值话，我们就认为这些黑色像素点应该被替换为白色像素点。阈值一般选为3，因为太大了，会把两条靠得很近的路之间的区域像素错误的替换为路上像素点。这样有些比较大断点的路就无法连接，我们可以在后续的步骤中予以修复。行扫描如果结束了，再逐列扫描，进行同样的操作。这样就可以去除图5.10中所有的黑色的小点。图5.11示出了平滑及反色后的结果。
5.5.5 细化和矢量化
道路网络提取出来之后，路还是有一定的宽度，这不仅需要占用大的存储容量，而且仍然不能用计算机来进行诸如缩放等处理，所以必须进行细化和矢量化操作。道路网络细化之后，只有一个像素的宽度，这就很容易对其进行矢量化操作。我们应用实验室里已经有的软件来进行细化和矢量化的操作。图5.12显示出细化的结果，图5.13显示出矢量化的结果。道路网络矢量化之后，只占用了比较小的存储空间，并且可以对其无限次的放大或缩小操作。我们可以在矢量地图的基础上添加GIS信息，用于城市的智能交通，城市规划等领域。
图5.12 细化后的结果
图5.13矢量化后的结果
§5.6 RoadExtractor简介
5.6.1系统开发信息
本论文综合运用了前面叙述的图像处理、图像识别等理论构建了彩色城市交通地图道路识别与提取系统RoadExtrator。该系统采用Microsoft Visual C++作为开发工具，以Windows 2000作为开发平台。图5.14是该系统的界面。
5.6.2系统界面
1、标题栏
标题栏显示的是当前打开的位图文件路径名，以及该系统的名称“彩色城市交通地图道路识别与提取系统【中国科学技术大学GPS实验室】”。当前打开的是成都市的地图（D:\MyPictures\chengdu.bmp）。
2、状态栏
状态栏显示的是：（1）当前鼠标的位置；（2）鼠标位置处像素颜色的R、G、B、Y值，其中Y是该像素的亮度，亮度的计算式为：
，为了避免浮点数运算，本系统的Y的计算式改为：
, “>>” 为右移位运算；（3）图像的大小（宽度×高度×每像素的位数），当前地图的大小为2852×2014×8，宽度为2852像素，高度为2014像素，每像素为8位；（3）当前的日期和时间。
3、菜单栏
①【文件】该菜单负责位图文件的打开和保存，打开和保存的文件类型包括BMP格式和JPG格式，BMPFile和JpegFile类具体实现BMP文件和JPG文件的读写工作。
②【分步】和【自动】菜单具体实现地图道路提取的工作。【分步】菜单一步一步地实现道路提取工作，具体步骤在5.5节中已介绍，主要包括：去除地图中的符号，归一化道路的颜色，腐蚀文字和平滑道路等。而【自动】菜单一次性完成道路的提取工作，最终结果黑白二值图。
③【提取】为了能够提取其他地图册中地图道路，设计了该菜单，在提取道路之前，手动选择所有道路的颜色，并且设定归一化后的道路的颜色。
④【图像处理】实现对图像进行各种处理操作，包括：边缘提取，灰度化，反色，直方图均衡化，二值化和伪彩色等。
⑤【霍夫变换】利用Hough变换理论提取图像中的直线和平行直线。不过输入的图像必须是二值黑白图，且黑色的像素数少于白色的像素数。
⑥【灰度形态学】实现对灰度图像或彩色图像（先转化成灰度图）进行各种形态学操作，包括：腐蚀，膨胀，开启，闭合，平滑和梯度等。
⑦【原图像】显示原来的图像。
⑧【视图】该菜单的主要功能有：关闭或打开工具栏、状态栏，关闭或打开全屏显示，显示图例，显示流程图，显示当前运行程序的路径等。
⑨【帮助】该系统的一些信息，以及中国科学技术大学GPS实验室的链接等。
图5.14 系统界面
5.6.3运行结果界面
图5.15所示为系统的运行结果界面，以上面的成都市的地图为例，该界面显示出对该地图提取道路的结果。
图5.15 系统的运行结果界面
§5.7进一步的研究
5.7.1 基于灰度分割方法的不足之处分析
图5.11是用基于灰度分割方法论述的提取彩色城市交通地图道路的结果，把它同原图对照发现，识别出的道路有的发生了偏差，有出现了过识别，而有的出现了欠识别，出现这种情况的一方面是地图的原因，这在在前面已经分析过了，就是：（1）有些结构稍复杂的方块字，如果落在道路上，其围成的方块的宽度或高度有的会超过路的宽度，这样路在此处会形成断点，造成道路的欠识别。（2）地图中有的地方会出现两条路的离得很近，这样在道路在识别之后会出现路的粘连，造成道路的过识别。
另一方面就是这种方法是工作在开环状态下，其中的阈值、参数的调整并不是自适应，需要人工的干预，因而鲁棒性并不好，造成道路的识别率并不是太高。现在提出通过构建一个闭环反馈控制系统，把栅格地图中道路和非道路两种不同的识别过程作为地图道路信息综合识别系统中两个并联的子系统，通过对两个子系统输出区域进行比较，使闭环系统的输出成为可观变量，并分别对每个识别子系统进行反馈优化调节，以获得道路信息识别的自适应优化。
5.7.2 新提出的基于闭环反馈方案
图5.16是该系统的方框图。
图5.16 系统方框图
下面对系统的各部分进行解释。
1、 输入 系统的输入仍然是彩色地图。
2、 图像的预处理 这一部分就是前面介绍的基于灰度分割的地图道路提取过程。经过这一步，地图的初步的道路网络已经形成（如图5.11所示），是一幅黑白两色图，其中白色为背景，即地图的区域（为了不引起混淆，我们把道路以外的部分即白色像素围成的部分称为背景）；黑色为道路网络。
3、 道路识别图像预处理 这一步的主要工作是消除道路的边缘毛刺，连接道路的断点等。
4、 区域识别图像的预处理 这一步的主要工作是消除背景里的孤立点。这一步和上一步可以在道路和区域的识别中进行。
5、 道路网络图层的模式识别过程和非路区域图层的模式识别过程 虽然经过上述几步处理之后的地图图像中道路网络基本形成，但是处在道路和区域的交界处仍然存在一定的误识别。我们可以把现在的这幅图中的像素进行分类：道路，背景，道路的过识别区域（即背景的欠识别区域），道路的欠识别区域（即背景的过识别区域）。然后根据道路和背景的特征分别对道路和背景进行识别，去掉道路的过识别区域，以背景的颜色代替之；去掉背景的过识别区域，以道路的颜色代替之。
6、综合误差判别 把上述的两个识别结果的图像进行相交，构造一个评价函数，对相交的结果进行评价，如果这个结果不理想，再分别反馈回道路和区域识别的输入端，并分别调整各自的阈值，重新进行识别，直到结果满意为止，即达到评价函数所规定的标准。
7、输出结果 此时的结果虽然也是黑白二值图，但道路的识别率同图5.11相比有了一个质的飞跃，从视觉效果来看道路更平直了。在此基础上，可以对其细化和矢量化操作，得到更为准确的矢量图。
5.7.3 道路和区域的特征分析
道路的特征：（1）同一条道路的宽度基本上没有太大的突变，也就是说路的边缘是平滑的；（2）路的边缘在其局部上是由一对平行的线段组成；（2）路是连续的。
区域的特征：（1）区域是由道路围成的封闭的多边形，因为道路在局部上是由一条条的短的折线组成；（2）区域也是平滑的，也就是说区域里没有孤立点（孤岛）。
我们可以利用这些特征在前面基于灰度分割的道路提取的基础上构建一个人工神经网络图像识别的系统。
5.7.4 评价函数的确定
归一化道路颜色（见5.5.2节的叙述）后的地图图像（见图5.8）往下有两条处理路径：
1、图5.8的图像数据先转化为灰度图，然后选定一个阈值进行二值化处理，阈值的选取与图像的灰度分布有关，这里选取的阈值比较接近路的灰度值，取245，灰度低于245的像素，其灰度值直接用0代替；高于或等于245的用255代替（如图5.17所示）。这样得到的黑白二值图，然后用灰度形态学算子（先进行灰度形态学的腐蚀操作，再用原图像的灰度值减去腐蚀操作结果的灰度值）进行边缘提取并保存（如图5.18所示）；
图5.17 图5.8图像的二值化
图5.18 图5.17提取边缘后的结果
2、腐蚀文字，边缘提取（图5.19）；
图5.19 图5.8图像边缘提取后的结果
图5.20 图5.18和图5.19相与的结果
图5.21 图5.18和图5.20相与的结果
把上述两步得到的图像逐像素进行相与操作，相与的结果仍然是二值图像（图5.20），并且路的边缘变得不连续，但是路的边缘位置是准确的，在此基础上，对其中的黑色像素点进行Hough变换提取其中的直线段，每次提取其中的一条直线段，记下该线段的位置信息后，把该线段位置处的黑色像素替换为背景的白色像素，然后再对剩下的图像实行Hough变换，提取下一条直线，然后替换该位置处的直线像素为背景像素；然后继续实行Hough变换，替换像素，直到所有的黑色像素全部为背景的白色像素替换完为止。这样地图中的道路边缘都提取出来了。
为了更好的提取道路的边缘，此时还需要把上面相与操作的结果（图5.20）同图5.18再次进行相与操作，结果见图5.21，从该图可以看出，图中的白色像素点主要有以下两个特征：（1）短的笔划和一些孤立点是由原图中的文字组成，这些像素的位置也同样是准确的，可以根据这些位置信息去除地图中的字符噪声。（2）长的线段组成道路的边缘线段，我们可以先采用Hough变换的理论提取这些长的直线段，来弥补图5.20中缺失的道路边缘。
因为这些边缘的位置是准确的，所以可以把边缘的位置信息作为评价函数。如果一次道路和区域识别过程结束，综合它们的结果测得道路的位置与这个评价函数有偏差的话，我们在返回到系统的输入端，重新调整阈值，再进行道路和区域的识别，直到道路的位置与评价函数相吻合。
5.7.5 基于神经网络的道路识别闭环反馈系统
1、网络结构的确定
具体来说，图5.16的系统可以由基于神经网络图像识别系统来实现，图5.22是一种前向神经网络图像分类器，由输入层，隐层和输出层构成。现在能确定的就是网络输出节点数，因为系统的最终输出结果只有两类：道路和区域，所以输出节点数为2。隐层节点数与网络输出逼近期望值所要求的精度和学习系统的复杂程度有密切关系，网络的隐层节点数可按照下式计算：
隐层节点数＝
在该式中特征向量维数值的就是输入节点的特征向量维数。分类数就是指输出节点的数目，这里分类数就是2。
网络节点的激发函数采用Sigmoid 型，Sigmoid函数详细的内容见第四章。
图5.22 前向神经网络图像分类器
2、输入节点特征向量及维数的确定
根据5.7.3节对道路和区域特征的描述，我们可以采用一个或几个计算机能够识别的量化的指标来表示。这就是所谓的图像特征提取和特征数据的规格化。
由于图像颜色进行了二值化，仅仅利用图像的颜色信息是不能够描述这4类像素（道路、区域、道路的过识别区域和道路的欠识别区）的特征的。我们转而利用图像的拓扑特征来对它们进行描述。
参照图5.11，根据我们的先验知识：一幅地图，无论它多复杂，区域的像素数总是多于道路的像素数，在该黑白地图中，我们通过统计黑白像素的比例，得到黑色像素集合为道路，白色像素表示区域。
考虑(i,j)处的像素，其中i为该像素所在的列，j为该像素所在的行。设图像中的道路的宽度为w，对于每一条路，w是一个常数，以该像素为中心，我们选取
的方块，则方块内像素的个数为
。我们设方块内黑色像素的个数为n。如果该方块内的所有点的颜色值都为0（黑色），即
，则该像素属于道路；如果该方块内所有点的颜色值都为1（白色），即
，则该像素属于区域（背景）；如果该方块内黑色像素点的个数
，则该像素处在道路和区域的交界处，至于它到底属于道路的过识别区（背景的欠识别区），还是属于道路的欠识别区（背景的过识别区），我们暂时无法判断，我们可以把n作为输入节点特征向量的一个分量。
我们再根据另外的信息来确定输入节点特征向量的别的分量。
5.7.6值得商榷的地方
以上的内容只是理论分析，由于时间的关系，并没有做实际的试验来验证其正确性。因此有不少值得商榷的地方：（1）闭环反馈系统评价函数的确定，（2）输入节点特征向量及维数的确定。有的地方很可能经过研究之后发现它是完全错误的。
但是这至少会给后续的研究工作提供了一个思路，搭建了一个框架。相信随着对这类图像识别问题的认识的进一步加深，彩色城市交通地图道路识别与提取系统一定会得到很好的完善。
