§4.1 概述
随着计算机技术的发展，GIS（地理信息系统）发挥着越来越重要的作用，这对矢量地图的需求也大大增加了。传统的方法就是对地图依次进行描图、扫描、细化和矢量化。描图的过程就是用一张和源地图一样大小的透明纸蒙在地图上，然后用铅笔沿路的中心线进行描迹，最终得到一幅黑白纸质图。然后用数字化仪逐点进行数字化后扫描进计算机，得到黑白BMP 位图。然后在此基础上对其进行细化和矢量化操作。这种方法虽然简单，但是速度很慢，而且会容易带来噪声，随着人们对地理信息需求量的增加以及地理信息处理的批量化，人工识别愈来愈被看成是一项既费时又费力的工作，地理信息的识别也越来越成为地理信息系统发展的瓶颈。
当前，地图中道路信息的自动提取已经成为计算机模式识别领域中的一个重点、难点，许多学者在这方面做了大量的研究工作[43-54] ，取得了很多有效的方法，有着很强的现实意义，它将极大地提高GIS 数据的更新速度。这些文献的研究对象大多是卫星航拍图片，这增加了矢量地图的生成成本，不过其中的一些方法在处理栅格交通地图时也可以借鉴。专门用于城市栅格地图道路图层识别的方法[36-39]取得了很有效的结果，但是这些方法都是针对城市交通地图中道路、噪声的特征，基于道路颜色信息的聚类而进行的，对于扫描质量比较好的地图能够取得比较好的效果，而对那些颜色混杂或非城市地图，实验证明这些方法并不能得到满意的效果，而且也没有考虑那些宽度较小的低等级道路。本文试图对此加以研究。
§4.2 图源分析
本文使用的图源如图4.1，来源于安徽交通地图册，是一幅县市级地图，经扫描得到：
图 4.1 安徽全椒县地图(部分)
从上面的图像可以看到：
- 区域面积比较大，一般都是地图中面积所占比例最大的，颜色分布的相对较为均匀；
- 不同等级的道路是用不同的颜色标示的，高等级的道路具有一定的宽度，路的颜色与背景对比较为明显，但是由于印刷、扫描的误差，路和区域间存在过渡色；其他要素，诸如河流、文字等也有类似的情况；低等级道路比较细，而且颜色也与一些文字噪声相近；
- 为了制图需要，地图中有一些具有特殊意义的标识符号，如城镇中心、乡村等，这些符号有些作为噪声干扰了道路信息的提取，而一些较为特别的标识符号则与道路有着很大的关系，为道路的提取提供了一定的参考价值；
- 道路都是相连的；存在的一些道路端点一般都对应一些标识符号，如乡村、城镇等。
另外，这种图像由于地图本身的原因以及扫描过程中的误差，颜色信息很不规范，也就是说，即使对于同一种要素，它里面也含有许多其他要素的颜色信息，这样的话，如果一开始就用颜色聚类的方法来进行信息提取，将会产生很多误差，不利于后面的处理，因此，除了颜色信息以外，我们还要利用其他的特征，如道路的宽度、道路网络的特点、地图中其他地图要素的作用等。结合这些特征以及具体的这一类图像，本章得到了下面的道路自动提取算法。
§4.3 地图的预处理
4.3.1 模板匹配提取标识符号
前面提到，有些道路上出现了许多标识符号，因此，如果能够将他们先提取出来，则对后面的道路提取具有很大的参考作用，而且这些标识符号也是制图者有意识地添加上去的，它们也是一种很有用的信息，因此，将它们提取出来也可以丰富信息的提取。对于点状符号的提取，模式识别中模板匹配的方法[57] 是很有效的，算法也比较简单，其不足之处主要就是运算量很大，较耗时间。模板匹配（template atching method），它基本上是一种统计识别方法。利用模板匹配可以在一幅图像中找到已知的物体，拿已知的模板和原图像中同样大小的一块区域去进行对比，如果不相匹配，然后平移到下一个像素，仍然进行同样的操作。如果在原图像的某一位置，对在模板中所有像素都进行了比较之后，出现差别最小，，或局部相似度达到一个较大的值，那么该位置对应的与模板同样大小的一块区域就是我们要找的物体。
采用以下的四个公式来计算原图像当前搜索位置处的像素块同模板之间的相似度：
公式(4.3.1)用来计算整个模板的能量，并存储在变量SigmaT 中，th 和tw 代表模板的高度和宽度，T(i, j) 表示(i, j) 处的像素的颜色值，对于一个模板，SigmaT 是一个常量，不随在原图像中的搜索位置的变化而变化。公式(4.3.2)计算(x, y) 处与模板同样尺寸的像素块（以下简称搜索块）的能量，(x, y) 是搜索块左上角的坐标。公式(4.3.3)计算(x, y) 处搜索块同模板之间的互相关能量。公式(4.3.4)利用式(4.3.1)、式(4.3.2)和式(4.3.3)的结果计算原图像(x, y) 处的搜索块同模板之间的相似度，并将结果保存在变量R(x, y) 中。如果R(x, y) > T （T 为设定的阈值），我们就认为原图像(x, y) 处的像素块同模板能很好的进行匹配，说明该位置处就存在一个地图符号。找到了符号之后，我们就以特定的颜色填充符号加以标记。提取的结果如图4.2 所示：.
图4.2 标识符号提取结果
4.3.2 区域规范化
前面已经提到，区域的面积最大，而且颜色分布的也较为均匀，为了去除其中一些孤立的噪声点，先用3
3 的模板进行平滑滤波处理；然后扫描图像，设图像大小为M N ,统计各个灰度值的像素点个数Ni ，i =0,1,2…,254,（区域设置为白色，所以灰度值为255 的就不予考虑了），如果Ni /(M N ) = K1大于一个阈值K ，就认为它是区域像素，以该点为参考点，扫描整幅图像，对所有与该点灰度值（该点的灰度值也就是i ）相差在一个较小的范围T 时，就将它们变为白色（区域颜色）。这样就完成了区域规范化。这里除了阈值T 的设置以外，基本上都是自动进行的，不需要人工干预；使用K1作为一个比较参数，可以使得K1的设置更加简单。
需要说明的就是，这种方法，一般只适用于地图中只含有少数几种（通常就是中心的那部分区域）区域的情况，这样才能保证区域的面积较大；如果还有边界，则必然包含有边界外的其他区域，为了区别，这时边界以外的区域颜色一般和边界里面的颜色是不一样的，且其面积
不是很大，则这些区域部分将不会被规范化。所以，对这一部分的区域需要采用其他的方法进行规范化处理。比如说，区域的宽度一般要比道路的宽度大，可以根据这一特点识别出区域的颜色：采用一个大小合适的模板在图像上平移，如果模板内的象素都是同种颜色（或颜色距离相近），则认为里面是区域部分。不过该算法运算量比较大，花费时间长。
4.3.3 锐化处理
由于地图本身质量以及扫描过程中误差的引入，地图中不同要素间存在过渡色，因此，这里的锐化处理就是为了尽可能多地去除这些过渡色，以突出目标要素的颜色信息。由于图像中红色道路已经很细小，因此为了避免他们信息被减少过多，对红色分量大于一定的阈值T 的象素点不作锐化处理。具体算法如下：对于图像中的任一个非区域像素点P(i, j)（不包括边界点），考虑与他相邻的两个点P(i +1, j) 和P(i, j +1) ，如果满足条件
并且P(i, j,1) < T (不对红色像素处理)，则将点P(i, j) 转变为区域点，这里的th 是我们设置的一个阈值参数，这个参数的设置对于锐化的结果有着很大的影响，过渡色的去除的多少很大程度上取决于这个参数，th 越小，被去除杂色的就越多。经过这样处理以后，突出了道路信息，大部分文字噪声的笔画都变得非常细，尤其是那些和道路的颜色比较相近的噪声，经过这一步的处理后，对道路的干扰变小了，在后面就很容易去除。而那些较宽的道路的中心颜色还是比较均匀的，因此锐化处理对这一部分的影响很小，边缘差别较大的成分则被滤除了。
§4.4 道路提取
4.4.1 高等级道路提取
经过前面的锐化处理以后，颜色分布较为均匀的要素，如那些较宽的道路，都被保留下来，文字等要素由于存在太多的杂色，保留下来的较少，从而减少了对道路提取所造成的干扰。但是那些较粗的红色大字以及铁路等噪声由于都具有一定的宽度，前面的锐化处理并没有对它们造成很大的影响，而且红色大字（包括那些细小的红色道路）由于和国道（较粗的红色道路）的颜色相近，而且有和他们粘在一起的情况，因此，在对这些高等级道路进行提取时，不能单纯的依靠颜色信息来进行聚类处理，而需要结合其他的特征，否则就会引起过识别，产生太多的噪声。
通过对图源的分析，可以采用这样的一个方法来提取较宽的高等级道路：设置一个模板（模板大小跟路的宽度有关，这里使用的是99）在图像中平移，统计模板内非区域像素点的个数M ，并求出这M 个像素的平均灰度值ave ，设置一个计数器t =0,考察这M 个像素，若某个像素的灰度值与ave 的差值小于某个阈值，并且该点的灰度值在道路颜色范围内，则令t =t +1。统计完毕后,若t/M 大于某个阈值，则认为该模板内存在有道路象素，将上面满足条件的点以黑色（0,0,0）标注。
实验证明，采用上面的这种结合颜色和道路宽度信息的方法可以较好地避免其他噪声像素，尤其是与一些道路颜色相近的象素（如字、红色细小道路（县乡级道路））的干扰。也有一些少部分的由于笔画较粗（因而在前面受到的锐化处理影响较小）且颜色与道路相近的文字也会被误识别为道路，实际上也就是噪声，不过他们一般都是不太大的孤立块，可以利用此类噪声的这一特点采用“自适应模板”的方法进行去除，这个方法在给定模板的最大值（包括长和宽）MN时，能够去除所有外接矩形小于这个值的孤立噪声块，这在后面会介绍。经过这一步处理，就将较宽的高等级道路大致辨识了出来。道路上存在有其他的噪声点，如文字、标识符号等，他们覆盖或者隔断了道路，由于这里的道路都是具有一定的宽度（一般来说，这个宽度要大于文字噪声的笔画宽度），可以采用八方向法[38] 进行去除，而对后面将要提取的低等级道路，由于其宽度太小，这个方法不再适用。
4.4.2 低等级道路提取
在前面提取的基础上，低等级道路的提取就比较简单了，在结构上它没有高等级道路的宽度，基本上就是线条，只能利用它的颜色信息。从图中看出这些道路的红色分量很大，因此，我们只要设置一个阈值th _ r 作为比较参数，对所有红色分量大于该阈值的非区域像素都将其置为红色( RGB (255,0,0)),作为提取出来的低等级道路。这种道路本身比较细，被其他颜色的象素覆盖的比较多，断开的很厉害，形成了一段一段的比较短的道路线段，为了便于后面的处理，在进行这一步的颜色规范化后，接着进行下面的处理：对任意两个红色象素（也就是该等级的道路），如果它们之间的距离在一定阈值范围之内，且它们之间没有区域象素（因为道路不会被区域隔开）和其他已经提取出来的道路象素，则将它们之间的所有其他象素用红色象素代替。
§4.5 噪声去除
不过，从前面的地图图像中我们已经可以看到，由于各种要素间的颜色是互相混杂的，而且前面在进行锐化处理时，红色分量较大的那些象素点没有受到影响而被保留了下来，因此，单纯根据颜色进行提取时，就会将这些满足条件的噪声点也误识别为道路，主要有两种情况：红色大字和高等级道路的边缘象素。下面结合图示来进行说明和处理：
图4.3 道路边缘噪声的去除
从图4.3(a)中可以看出，高等级道路的边缘部分存在着很多满足上面条件的低等级红色道路象素，在提取出高等级道路的基础上，如图4.3(b)所示，接下来根据上面的条件提取低等级道路，结果如图4.3(c)，从中可以看出，高等级道路的边上存在着很多红色的象素点，而且正好是在道路的边缘，顺着道路的方向，如果不将它们去除，就会被误认为成一条实际的低等级道路，给提取结果带来很大的误差。观察这些噪声象素我们可以看到，它们都是出现在高等级道路的附近，因此，可以采用一个很简单的方法将他们去除：扫描整幅图像，如果扫到红色象
素点，则以该点为中心，在距离其一定长度R 的范围内，如果有高等级道路象素点，就将该红色像素去除。这里的参数R 的值不能设置得太大，这样真正的道路也就不会删除很多。这样处理会使得那些与高等级道路相连的实际低等级道路被误删除一部分，但是考虑到道路的实际长度和被删除的长度，这并不会对道路的最终提取结果产生太大的影响。噪声去除的结果如图4.3(d)所示，道路边缘的红色像素已经被完全去除了。
还有一个就是红色大字的去除。根据图像的颜色分析，红色大字与红色细小道路的颜色非常接近，仅仅使用上面的限制条件，则这些字也会被当成道路识别进来，他们实际上也是一种噪声。这些字的一个主要特点就是笔画很粗（相对于县乡级道路而言），相应的就使得它上面的 红色象素点比较集中，为此，根据这一特征，可以使用下面的方法进行去除红色字体：扫描图像，如果扫描到一个红色象素，则以该点为中心，向外扩张形成一个矩形模板，模板的大小可以大一些，根据红字的笔画宽度而定，统计该模板内的红色（ RGB 值为（255，0，0））和黄色（ RGB 值为（255，255，0），这种象素由本步骤处理转换得到）象素的总数量，如果大于某个阈值，则将该模板里面的红色象素都转变为黄色象素；以此方法处理整幅图像。最后，将图像中的黄色象素（其实就是前面提取出来的红色大字转换而来的）都转化为区域，也就最终实现了红色大字的去除。
这里尽管有些红色大字也是孤立的，但是并不适合用自适应模板来去除这些噪声，因为这些字体太大，这样需要的模板也就会很大，而红色道路因为被隔断的情况非常多，那么就会有许多道路段也被去除，不利于后面的进一步处理。
具体的实例如下，图（a）是选取的一小块原图像，图（b）是已经提取出高等级道路和标识符号的图像，按照上面提取红色细小道路的条件，处理后得到图（c），可以看到里面的噪声——红色大字，采用上面的方法去除红色大字后的结果如图（d），还有一小块的红色噪声象素，此时就可以用后面的自适应模板去除之。
图4.4 红色大字的去除
在这两种道路的信息都初步提取出来以后，还应该进行下面的处理：
孤立噪声点的去除，这里的噪声主要是指前面被误识别为道路的一些象素点，由于印刷、扫描的原因，他们与道路的颜色相近而被认为是道路，主要是一些文字。这些噪声点的大小不一，单纯使用面积阈值的方法来去除它们有时难以奏效，因为还有一些断开的道路，它们的连通象素数目并不是很大。不过，对于大部分的这一类噪声点，根据它们的形成原因，它们一般都有这样一个特点：对于某一个噪声块，总可以找到一个一定大小的矩形框将其包围，而且这个矩形框的四个边界上没有道路象素。在前面已经提取出来了标识符号，而且这些符号与道路 之间有着很大的关系。于是，我们可以这样进行，具体的除噪方法如下：扫描整幅图像，如果遇到道路像素，则以该像素为中心，向外围逐渐扩张，形成矩形，如果扩张到某个范围，使得矩形四个边界上都是非道路和标识符号象素，则可认为矩形内部是孤立噪声点，将他们转化为区域即可。
道路空洞的填补：在前面提取的结果上，高等级道路内部存在着许多的区域象素点，主要是由于地图的印刷质量及前面的锐化处理所造成的，这不利于后面对道路的细化处理，对于那些小的空洞，可以采用中值滤波的方法来填补，这里使用的是3
3的模板；而对于较大的空洞，可采用改进的八方向法进行处理，具体如下：扫描整幅图像，对某个非道路点，将其沿该点八邻域象素的八个方向向外扫描，在一定距离范围内，若到达道路点的方向数大于或等于阈值R ，则认为该点是存在与道路内部的噪声点，将其转化为道路点。为了保证该点只存在于道路内部而不是其他的情况，这里的R ＝8。经过这一步后，不仅填补了空洞，而且也滤去了大量的细小噪声。同样，因为红色道路比较细小，所以这里的中值滤波没有对红色像素进行处理。
§4.6 道路的后续处理
经过上面几步的处理以后，道路的主要信息已经得到，但还存在一些道路被断开等不完整的情况，这里所要做的就是对已经得到的结果进行细化[55] [57] 、连接的后续处理，所谓细化，也就是提取道路的中心，细化处理能够更好地突出道路的结构特征，以便于后面的进一步处理
以及最终的道路矢量化。细化的结果使得各类要素都向中间收缩，对于同一种要素，其原来的连通性不会发生改变，但是对非同种要素，若是原来两种道路相交叉，则在细化后仍会保持连通，这种情况可以不予考虑；还有一种情况就是，一条道路的端点落在其他道路上，这时，在细化后，他们就不再连通，还需要对结果进行处理。
在进行细化处理时，由于噪声的干扰，比如说，利用模板去除孤立噪声时，那些与道路粘在一起的噪声就无法去除，成为道路的一部分，在细化后形成了道路上的一个分叉，作为噪声，在进行后面的处理之前，必须将他们去掉，方法如下：对图像中的任一个道路端点，在其附近 进行扫描，如果遇到一个道路交叉点（也就是衍生出该毛刺分支的那个端点），且端点和道路交叉点之间的位置距离小于某个阈值R ,根据上面所说的道路的特点，即道路一般很长而且没有明显的转向，则可认为它是多出来的一个分支，将该分支删除即可。示例结果如下图4.5 所示：
图4.5 毛刺去除
在细化的基础上就可以进行道路的连接处理。连接中，主要根据道路的结构特征以及道路与其它要素的相互关系来进行。具体来讲，地图上的道路主要有以下特点：
1）道路一般都很直，不会有明显的转向，因此可以将其看作由一段一段的线段组成；
2）道路的断点都是成对出现的,在细化的基础上，如果存在两个同等级的道路端点,并且他们之间的距离小于某个设定的值,就用直线段将这两点连接起来；
3）对于一些存在道路相交的情况，一般都会在交叉处有前面提取出来的标识符号。
在进行道路连接处理时，（尤其是红色细小道路，它的连接关系比较复杂，不如高等级道路那样规则。）遵循以下的准则：按照两点之间的距离从近到远的顺序；按照两点之间有无标识符号的先后顺序；按照两点的性质（端点――端点或者端点――非端点）顺序进行。这些准则的建立也是基于道路结构的特点以及道路与标识符号的关系所得到的。依据以上准则，我们对提取的结果进行了如下的完善：填补空洞，道路细化处理，毛刺去除，断点连接。对于其他不满足上述特点的断点（如孤立端点，即附近没有与其对应的端点），若在该端点附近存在道路，结合该端点所在的道路方向，将端点沿着此方向延长至其他道路以实现道路的连通，否则，不予处理（这种情况一般存在于县乡级道路上，而且在道路的端点多数会有标识符号）。最终的道路提取结果如下图所示。
图4.6 道路提取结果图
§4.7 结论
可以看到，这里使用了基于道路的结构特征提取算法，利用了道路的宽度信息和道路与其它要素的位置关系进行后续处理，并没有单纯地对道路颜色进行归一化处理，使得提取的自动化程度进一步提高，并且减少了误识别。当道路种类较多且颜色噪声较大时，这种方法的效果还是能令人满意的，可以有效避免相似颜色的噪声影响。关于区域的规范化，我们在前面已经看到，这种方法还是有一定的局限性，对于某些地图它可能不会有很好的规范效果。可以考虑用交互式界面来人为指定区域或其他要素，以更好地实现地图规范化，实验证明这种方法的效 果比较好，后面会对此加以介绍。
