栅格地图道路的快速矢量化方法研究与实现

寇曼曼，王勤忠，万 娜

(河南省地震局，河南 郑州 450018)

0 引言

GIS数据主要有栅格地图和矢量地图2类。栅格电子地图也就是通常所说的Bitmap位图。获取栅格数据的成本低、速度快、自动化程度高，但是数据量大，存储不方便，缩放过程中会产生失真，数据不是很准确。矢量电子地图，数据结构紧凑，数据量小，冗余度低，有利于网络和检索分析，精度高，图形显示质量好，可以随意缩放，缩放过程中不会失真。由于矢量电子地图的这些特点，使它在地理信息系统中应用很广。因此如何将栅格数据转换为矢量数据是GIS技术研究的重点之一［1-4］。

通常制作矢量图要先用扫描仪把纸质地图扫描成数字栅格图像，然后再转换成所需要的矢量图。目前，在实际生产中是借助现有的工具软件(如国外的MapInfo及国内的MapGIS等)进行逐点矢量化，工作量大而且繁琐。本文采用从互联网获取得数字栅格地图为处理对象，通过识别地图标注的方法来实现道路提取，在此基础上提出一种基于可变矩形跟踪框技术实现栅格地图道路快速矢量化的方法。

1 分类道路提取与细化

1.1 数据来源

通常制作矢量图要先用扫描仪把纸质地图扫描成数字栅格图像，然后再转换成所需要的矢量图。本文采用从互联网获取得数字栅格地图为处理对象。

1.2 分类道路提取

Google Map是由分辨率大小为256×256的图片无缝拼接而成的。每个地图瓦片均由独立的URL地址唯一确定，有了完整的 URL在 C#中利用 Http-WebRequest类可实现瓦片地图的下载［5-7］。在获取瓦片地图的基础上，应用图像拼接得到原始数字栅格地图。通过基于视觉一致性的聚类分析，可以基本分离出所需要的道路，但存在分离出的要素被各种标注覆盖或中断的现象。通过结合模式识别与基于视觉一致性的色彩聚类分析精确识别出各类标注体。在成功提取标注区和道路信息的基础上，通过分析不同标注对道路的覆盖形式，实现间断道路的自动连接［8-10］。

1.3 道路细化

通过前面的标注区识别及基于视觉效果的色彩聚类分析和中断道路的连接，已经提取出了道路信息，将道路的颜色置为黑色(取值为1)，其他为白色(取值为0)。设待细化的图像有任意点P，如果等于0，即认为此点是背景点，跳过不予处理，继续下一点，如果等于1，认为是道路上的点，接着判断此点是否保留。通常使用3×3的结构元素对点P的去留进行判断［11-12］，但是对于是否是连接点的判断，需要进一步向外延考察，所以本文采用5×5的结构元素，选取点P周围对称的24个点，结构如图1所示。

图1 5×5结构元素

同时满足以下4个条件的点P将被删除:

1)2≤A(P)≤6;

2)B(P)=1;

3)P(1，2)*P(2，1)*P(2，3)=0 或者 P(1，2)*P(2，1)*P(2，3)=1＆＆B(P(1，2))≠1;

4)P(1，2)*P(2，1)*P(3，2)=0 或者 P(1，2)*P(2，1)*P(3，2)=1＆＆B(P(2，1))≠1。

其中A(P)表示点P八邻域中值为1的点的个数，B(P)表示点P八邻域中从0→1变化的个数。

2 栅格地图道路矢量化规则

要矢量化的栅格数据主要有以下特点:

1)从道路数据的空间特征上来看，道路分不同等级，道路之间有交点。

2)从单条道路的角度看，道路有一定的方向性，且具有分段特性。

依据GIS系统线性对象的一般性拓扑规则，在跟踪矢量化过程中，应满足以下2个条件:

1)在同一层要素类中，线与线不能相互重叠，相交处打断，以弧段形式表达线状要素;

2)2个线层不能相交。

3 矢量化追踪方法

3.1 可变矩形追踪框

正方形追踪框数据为一栅格点集，左上角为起始点，顺时针排列。以矢量化线要素上一点为中心，以2S+1为边长的正方形追踪框(追踪步长S，S取正整数)，记录追踪框与线要素的交点，并根据不同情况调节追踪框大小来获得唯一的追踪目标点。

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换方法。其原理是:过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近的像素［13］。当追踪框与矢量化线要素有2个交点时，采用Bresenham算法返回由这2点所确定直线中的一系列点集M，假设点集中有S点在矢量化图像上，点拟合比例为P=S/M，选取合适的阈值P1(0＜P1＜1)，若实际情况大于P1，认为2交点之间的点近似在一条直线上，以末端点为下一追踪点，若小于P1，则认为2交点之间的点基本不在一条直线上，缩短追踪步长，缩小跟踪框。

3.2 端点(交点)判断

3.2.1 追踪框与被矢量化对象交点

根据矩形中点及边框大小确定边框上各点的坐标，然后从追踪框左上角开始，逐点判断是否存在与被矢量化对象颜色一致的点并记录下这些交点。当交点为连续点时，合并首尾点只记录第一个点。

判断追踪框与被矢量化对象的交点数，如果只有一个交点，则缩小追踪框找到末端点;如果存在2个交点，则通过判断追踪框中点和追踪框与被矢量化对象交点间是否为近似的直线确定追踪步长是否合适;如果存在多于2个交点，则跟踪框内可能存在多个线段的交汇点。

3.2.2 追踪框内矢量化线段交汇点

追踪框与被矢量化对象存在多于2个交点时，采用逐点跟踪确定可能的交汇点。从追踪框中心点开始，以1个像素宽为跟踪步长，在该点的八邻域中搜索线要素上的点，并统计其个数n(相邻的点合并为一个点)，如图2所示。若n=1，则该点为线条的端点，结束此线的跟踪;若n=2，则该点为线条的中间点，根据追踪方向选择曲线上的点作为下一追踪点;若n＞2，则该点为曲线的交汇点，相邻多点合并为一个点，归并3交叉、4交叉后，具体形式如图1所示，“0”为背景，着色部分为曲线上的点，7种形式分别旋转90°、180°、270°，共计有 22 种情况。应用 Bresenham算法判断交汇点与上一矢量化点之间是否为近似的直线，如果是则记录交汇点，然后选择在道路惯性延伸方向的交点做为下一跟踪点，在道路的惯性延伸方向上没有交点，那么将曲线的交汇点做为端点，此条道路矢量化结束。

图2 逐点追踪确定交叉点

3.2.3 道路交点惯性延伸方向

在道路交汇点的位置会有多条道路相交，如何选择下一步的跟踪方向将是继续矢量化的关键，用道路惯性延伸方向来帮助选择。如图3所示，追踪框尺寸size=7，道路与追踪框入方向的交点ap，相对于中心点P在追踪框上的对称点cp，左右移动［size/2］向下取整即3个点，从lp到rp这个范围内都属于道路的惯性延伸方向。落在lp到rp之间的交点将是一个跟踪点。

图3 道路的惯性延伸方向

4 矢量化实现

道路矢量化的算法流程如图4所示，采用自适应可变矩形跟踪框，计算矢量化对象与跟踪框交点;判断交点数，如果只有2个交点则采用逆Bresenham算法判断交点之间的线段是否为近似直线，不满足则缩小跟踪框返回上一步，满足近似直线条件则把追踪方向的交点作为下一追踪框中心点继续;如果只有一个交点则通过缩小追踪框找到端点;如果交汇点多于2个则采用逐点跟踪方式判断追踪框内有无交汇点，如果无交汇点则同存在2个交汇点一样处理，如果存在交汇点则判断交汇点与上一矢量化中间点之间是否满足近似直线标准，不满足则缩小跟踪框，满足则取交汇点为矢量化线段的交点，线段惯性延伸方向的交点为下一跟踪框的中心点，若为丁字路口无惯性延伸方向交点，则结束追踪。

图4 单条道路矢量化算法流程

5 试验结果

图5 栅格地图道路矢量化效果

图5展示了不同道路状况下的矢量化效果。图5(a)、图5(b)这2个例子可以看出被矢量化对象以可变步长沿道路自然延伸方向跟踪，并终止于同类道路的丁字型交汇点;图5(c)、图5(d)这2个例子显示矢量化算法自动在道路交汇处设置交点并沿道路惯性延伸方向延续矢量化;当遇到立交点，系统默认设置为采用交互式人工确定下一步跟踪方向及交点性质，如图5(d)中显示低等级公路被高等级公路中断，停止矢量化等待交互处理。

6 结束语

本文以数字栅格地图为处理对象，提出一种基于可变矩形跟踪框技术快速矢量化线状要素的方法。根据栅格地图特征，采用自适应跟踪步长的可变矩形跟踪框技术，加快了矢量化的速度，同时又结合逐点跟踪、端点判断、道路惯性延伸点判断方法，提高了矢量化的精准度，最终达到对栅格地图道路快速、精确地矢量化的目的。实验结果表明该方法的矢量化效果十分理想。

［1］钱静，陈洋，王润生.彩色扫描地形图中等高线提取方法的研究［J］.中国图象图形学报，2006，11(10):1443-1449.

［2］张玉芳，熊忠阳，陈铭灏，等.彩色栅格地图矢量化方法研究［J］.计算机应用研究，2008，25(10):85-87.

［3］王勇，李朝奎.线性要素栅格数据矢量化快速简便算法设计与实现［J］.测绘工程，2009，18(5):44-46，50.

［4］邹修明，张岳新.栅格地图矢量化关键技术研究与实现［J］.计算机工程与应用，2003，39(19):102-103，138.

［5］张东辉，何政伟，杨斌.栅格图像自动矢量化系统的研究与实现［J］.计算机工程与应用，2010，46(10):171-174.

［6］李少梅，阚映红，王颖，等.Google Earth影像变换与应用研究［J］.测绘科学与工程，2010，30(2):11-14，43.

［7］寇曼曼，王勤忠，谭同德.Google Map数字栅格地图算法及应用［J］.计算机技术与发展，2012，22(4):204-206.

［8］寇曼曼，王勤忠，谭同德.彩色数字栅格地图中道路的识别与提取［J］.计算机工程，2012，38(13):276-279.

［9］詹曦.彩色城市交通地图的道路识别与提取［J］.计算机仿真，2010，27(2):242-246.

［10］Hai T，Bao Y L.Road extraction based on image features of raster urban traffic map［C］//International Conference on Transportation Engineering 2007.2007:594-599.

［11］Chin R T，Wan H K，Stover D L，et al.A one-pass thinning algorithm and its parallel implementation［J］.Computer Vision Graphics Image Processing，1987，40(10):30-40.

［12］牟少敏，杜海洋，苏平，等.一种改进的快速并行细化算法［J］.微电子学与计算机，2013，30(1):53-55，60.

［13］Freeman H.Computer processing of line-drawing image［J］.Compute Surveys，1974，6(1):57-97.