基于OTSU和轮廓追踪的地图线条识别方法

冉文静 王加胜 饶 珣 赵 喆 陈鑫亚 徐春晓

(1.云南师范大学信息学院，云南 昆明 650500；2.云南师范大学地理学部，云南 昆明 650500)

1 引言

纸质地图是重要的地理数据来源之一。为了充分利用纸质地图数据，需要通过扫描成栅格地图后，再将其转化为计算机方便查询和拓扑分析的矢量数据。地图矢量化即为将栅格地图转换为矢量地图的处理过程，是地理信息科学（Geographic Information Science，GIS）数据获取的重要途径。传统的地图矢量化方法采用人机交互方式完成，需要用鼠标对照栅格地图新建图层，描绘点、线、面，添加属性。当需矢量化的地图数量较大时，这种方式需要花费大量的人力物力。如何改进自动化程度，提高矢量化速度成为目前快速获取地理空间数据亟需解决的问题。线条识别是地图自动矢量化的关键步骤，线条识别后可通过栅格转矢量方法方便地转化为线和面。

现有的地图线条识别算法主要分为三类：一是基于边界特征的线条算法[1]。该算法由Capson提出[3]，利用多边形边界的连贯性研究的一种扫描栅格图多边形边界链接序列化算法，但是该算法需要占用大量的内存资源。二是基于边界搜索的线条查找算法[4-7]，该算法由Nichols[2]提出，该算法首先确定来自四个相邻像素交点的类型，然后用连接信息跟踪弧，用弧线构造多边形，但是该算法也仍然存在占用大量内存资源的缺点。三是基于边界跟踪的线条查找算法[8-13]。在目前线要素提取的研究中：赵雪松[14]将地图进行二值化后，结合Arcscan的DRG进行自动的矢量化。但经过此方法提取线要素的过程中还需要进行人工修测、删减、增补等处理，才能得到较好的结果。董敏等[15]用ArcGIS自动矢量化提取线要素，薛滨瑞[16]用CorelDraw和ArcGIS制作地形等高线，但这两种方案易导致矢量化线条变形。Naccache等[17]提出细化算法来提取等高线，虽然速度快、效果好，但算法对于扫描地形图的质量要求较高，且实现方式成本较大，不利于普及。邓凯、朱世权等[18]在地图线条质量优化过程中，阈值的调整可能额外生成杂点。在这些方法中存在需要人工修改，或实现效果不好等缺陷。

本文提出了一种基于最大类间方差法（OTSU）和边界追踪的地图线条自动识别方法。该方法根据光栅图像的连通性提取多边形边界，从上到下和从左到右扫描图像，将地图中线条所形成的轮廓全部检测提取。相比较于其它的矢量化算法，该算法记录了所有轮廓之间的联系信息，并运用这些信息有效解决了地图的图文分离问题。

2 地图线条识别方法

基本思路为：首先，对图像进行预处理，对于含噪声比较高的地图图像，进行去噪、滤波等处理；然后，基于OTSU阈值分割算法对处理好的图像进行二值化处理；然后，运用边界追踪算法识别轮廓；最后，通过计算所有轮廓的面积将面积小的进行剔除，实现地图的图文分离，即将线条和文字分离出来。

2.1 地图灰度化与二值化

（1）地图的灰度化。就是将每个像素点的RGB值转换为一个灰度值。首先，读取彩色的栅格地图，用矩阵存储其数值。参考文献[19]运用公式（1）将RGB图像转换为灰度图像。

其中，R、G、B分别代表彩色图像中的红色、绿色、蓝色三个通道的对应像素值，Gray为最终计算出的灰度值。

（2）图像的二值化。二值化的目的是排除干扰，区分出地图中的目标（线条）和背景（其它）。通过设定阈值，将大于阈值的像素灰度值设为1，把小于这个值的像素灰度值设为0。在图像二值化的过程中，阈值对线条识别结果有很大的影响。传统的二值化方法主要根据人工的经验设定一个阈值。本文运用OTSU算法实现灰度图像自动二值化。OTSU算法由日本学者大津在1979年提出，是一种图像灰度自适应的阈值分割算法，其在图像亮度和对比度较低的情况下也能较好地选取合适的分割阈值。OTSU要求选择最佳阈值，使图像前景和背景间的灰度值差距较大，衡量灰度差异的标准定义为类间方差，即当前景和背景间的类间方差取最大值时，获取最佳阈值。假设图像的像素总数为N，L个灰度级[1,2,…,L]，灰度值为i的像素总数为ni出现概率：

设图像的初始阈值为t，若像素的灰度值小于t，则属于C0，否则属于C1，C0、C1别代表图像的背景类和前景类。图像背景类和前景类像素出现的概率和灰度均值分别用ω0、ω1、u0、u1表示，有：

其中，σ2表示类间方差，当σ2取得最大值时，获取最佳阈值。

2.2 线条轮廓追踪

线条轮廓追踪主要是基于边界追踪对二值图像进行拓扑结构分析。把一个二值图像转换成边界表示，以此来实现地图的线条识别。边界追踪是数字化二值图像处理的基本技术之一，它从1像素的连接分量和0像素的连接分量之间的边界导出坐标或链码序列[20]。因为二进制图像在外边界和1分量以及孔边界和0分量之间存在一一对应，所以可以确定给定二进制图像的拓扑结构。要提取的信息是两种边界：外边界和孔边界。

如果像素点（i,j）满足外边界和孔边界的起始条件时，则像素点（i，j）被视为外边界或孔边界的起点。算法从左到右扫描像素点直到找到目标像素点，图1显示了判断是外边界还是孔边界的标准。其中图1a表示外边界，图1b表示孔边界。在扫描时，首先分辨一个像元是外部边界还是孔边界；然后，为发现的边框分配一个可识别的数字，即边界序号，用NBD来表示。初始时NBD=1，每次发现一个新的边界NBD+1。在这个过程中，遇到（i,j）=1，(i,j+1)=0时，则将像素（i,j）的值更改为-NBD。否则，将像素（i,j）的值设为NBD。除非（i,j）在已经跟随的边界上跟随并标记整个边界，否则继续扫描图片，当扫描到图片右下角时，算法停止。

图1 外边界和孔边界判断标准

2.3 文字的去除

由于运用目标追踪的矢量化算法，会将地图上的文字的轮廓一并查找，因此在绘制轮廓时，选择绘制所有的轮廓，会将地图上的文字也进行绘制出来，这样就对地图线条的提取造成了干扰，对于这个问题，本文利用轮廓的面积实现图文分离。由于文字的轮廓面积较小，因此，可设定面积阈值筛选出字体的轮廓。其中轮廓面积的计算原理是计算整个或者部分轮廓的面积，计算部分轮廓面积时，由轮廓弧线和连接两端点的弦围成的区域总面积计算。

3 实验和结果

3.1 实验数据

本文所用的数据是从天地图以及百度网页下载的RGB的彩色电子地图图像。为对比分析本文提出方法的效果，选取四类较为典型的电子地图图像进行实验：一是线条较少文字较少的地图，为最简单的地图图像，如图2a所示；二是线条较多文字较少的地图图像，如图2b所示；三是线条少文字较多的地图图像，如图2c所示，四是线条多文字也多的地图图像，也是最为复杂的地图，如图2d所示。

图2 原始彩色地图

3.2 实验结果

实验的结果如图3所示，第一步为将图像二值化的结果。在将地图进行二值化的过程中，发现会有少量的地图线条和文字有孔洞的效果，因此少量的图像信息有所损失。在经过轮廓追踪后进行文字和线条的分离过程中，由于在进行轮廓追踪算法时，对于有些文字本身就在地图的线条上，查找轮廓时，将文字与线条计算在同一轮廓内，因此通过轮廓面积方法进行图文分离的时候，会存在部分的文字没有办法进行去除。从最后的实验结果中可以看到：在第一幅最为简单的地图中通过计算轮廓面积的方法能够将地图线条和文字进行很好的分离，线条提取的结果几乎没有损失；在第二幅地图中，结果有少量的线条和文字未进行分离，如图中用红色框标识的部分；在第三幅地图中图文分离的效果相较于第二幅地图来说更多一点；在第四幅地图中的实验结果较差，不仅有线条的损失，而且线条中夹杂文字的地方也最多。

图3 实验结果

4 结语

针对地图线条自动识别问题，本文提出了一种基于OTSU和轮廓追踪的地图线条识别方法。通过不同复杂程度的电子地图实验，结果表明，本文方法实现了地图线条自动识别，为地图自动矢量化提供了重要支撑。然而，通过实验发现，本文的方法对于线条少，文字少且未附着于线条上的地图来说有很好的适用性，但对于线条多，文字与线条混杂的复杂地图来说，实验的结果仍有提升的空间。尤其是对于文字附着在线条上，与线条混在一起的情况，通过轮廓追踪的算法会将文字与线条计算在同一轮廓内，因此对于这样的情况就不能将文字和线条进行有效分离，在今后的工作中将进一步研究优化。