贾 雨， 王 莹， 姚兴苗

（1. 成都理工大学核技术与自动化工程学院，四川 成都 610059；2.电子科技大学通信与信息工程学院，四川 成都 611731）

等值线图纸矢量化是指将等值线图纸扫描获得相应的图像，通过计算机自动识别图像中的等值线，提取矢量的几何属性与拓扑关系，将处理对象由像素点阵图像转换为矢量图形。该项工作是等值线图纸数字化录入的一种常用技术，在地质、地球物理、地理信息系统等方面有广泛的应用，受到相关领域科技工作者的广泛关注，提出了许多有用的算法[1-4]，促进了该项技术的发展。

现有研究均在不同的方面促进了等值线图纸矢量化技术的发展，但尚没有一种方法能解决等值线图纸矢量化的所有问题，在实际应用中还存在不能完全采用计算机自动识别的情况。为此，本文通过改进基于圆跟踪[3]的等值线矢量化算法，提出了一种交互式的等值线的矢量化方法——等值线间隔追踪算法，通过人工干预弥补计算机自动识别存在的缺陷，保证追踪的正确性，适用于灰度等值线图像的矢量化，具有实用性和高效性。

1 等值线间隔追踪算法

1.1 算法原理

等值线间隔追踪算法采用非细化的方法，对等值线图纸直接进行像素级的追踪，以人工拾取的等值线上的某一点为起点，沿头尾两个方法进行追踪，若找不到符合条件的点，则暂停追踪，等待人工干预后继续追踪，直到整条等值线追踪完毕。等值线间隔追踪算法有3个关键的门限参数作为追踪的约束条件，RGB门限值对选取的点进行初步判断，通过颜色排除背景像素点；夹角门限利用等值线光滑的性质，排除等值线以外的干扰点；最小搜索半径门限控制搜索的范围并且可以作为搜索结束的标识。

对于实线上的某一点Pi开始按照搜索半径R进行搜索，可能找到多个符合灰度门限的点，计算这些点与Pi点所确定的直线与点Pi和它前面的相邻点Pi-1所构成的直线的夹角，取夹角最小的点为搜索到的等值线上的点，如图1(a)所示。

对于虚线上的某一点Pi开始按照搜索半径R进行搜索，若没有符合灰度门限和夹角门限的点，则缩小搜索半径继续搜索，直到找到符合条件的点。通过设置最小搜索半径门限为VALUEr小于虚线段的半长，可实现虚线绘制的等值线的追踪。如图1(b)所示。

图1 等值线间隔追踪算法原理示意图

等值线间隔追踪算法相较于基于圆跟踪的等值线图矢量化算法，主要进行了以下两个方面的改进：

1）基于圆跟踪的等值线图矢量化算法只能处理黑白二值图像，等值线间隔追踪算法通过灰度门限的设置可以处理灰度图像。

2）基于圆跟踪的等值线图矢量化算法适用于实线绘制的等值线的追踪，而当绘图区域存在逆断层（多值面）时，下盘的等值线是由虚线绘制的，本文提出的等值线间隔追踪算法可以通过设置最小搜索半径来实现虚线绘制的等值线图像的追踪。

1.2 算法描述

设Pi为等值线的控制点，则所有等值线控制点集合为为等值线的控制点个数。设追踪算法的灰度门限为VALUErgb，最小搜索半径门限为VALUEr，搜索半径为R。

第1步：在图像中的等值线上任取一点放入集合U，该点即作为头点，又作为尾点，向两个方向追踪等值线。

第2步：以头点为搜索起点搜索。

1）置集合V为空集，用于临时存放追踪找到的点。在头点方向上，以头点为圆心，R为半径搜索圆上的像素点，逐个比较这些点与头点的灰度差是否超过灰度门限VALUErgb。若灰度差小于灰度门限VALUErgb，则将该点放入集合V。

2）若集合V不为空，分2种情况考虑：

第1种情况，所有等值线控制点集合为U只有一个控制点P1，则取等临时集合V中与控制点P1灰度差最小的一个点为第二个控制点P2，放入集合U。

第2种情况，所有等值线控制点集合为U有2个或2个以上的控制点，当前头点记为Pi，逐个判断集合V中点与头点Pi所确定的直线与头点Pi和它前面的相邻点Pi-1所构成的直线的夹角，取夹角最小的点为控制点，将这个点放入集合U中，记此点为头点，并将当前搜索半径置为R，重新执行第2步。

3）若集合V为空，则跳至第4步。

第3步：以尾点为搜索起点搜索。以尾点为搜索起点搜索方法与第2步相同。若找到符合条件的点，放入集合U，并将该点设置为尾点，作为下次尾点方向追踪的起点。若没有找到符合条件的点，跳至第4步。

第4步：若R≥VALUEr，则缩小搜索半径，以当前的头点或尾点按第2、3步进行搜索。若R

等值线间隔追踪算法步骤如图2所示：

图2 等值线间隔追踪算法原理

1.3 等值线的光滑处理

在追踪出所有的等值点后，如果仅仅将等值点依次连接起来，那么生成的等值线图是由折线构成，而等值线通常要求是一条光滑连续的曲线。因此，需要对等值线进行光滑处理。常见的曲线光滑算法主要可分为插值算法和拟合算法两类。常见的插值算法有抛物线加权算法、分段三次多项式插值的方法，三次样条函数法等；常见的拟合算法有线形迭代法、Bezier曲线函数法等。

下面以正轴抛物线加权平均算法为例，介绍等值线的光滑算法。

正轴抛物线加权平均法的基本思想是根据给定的曲线特征点顺序，每相邻3点作1条抛物线，而每相邻两点之间前后两条抛物线弧的重合部分用加权平均曲线作为最终的插值光滑曲线[6]。

正轴抛物线加权平均法的实现方法是：对给定的n个曲线特征点序列，从首点开始，顺序取4点，过4点中的前3点可作一正轴抛物线，过4点中的后3点又可作一正轴抛物线，对过中间2点的2条正轴抛物线取加权平均，作为过中间2点的最终曲线。由于权函数是一个三次多项式，所以最终的曲线方程是五次多项式。

正轴抛物线加权平均法在数学上是严密的，计算过程也较为简单，能保证光滑曲线严格通过每个特征点，并且在整条线上具有一阶连续导数，其缺点是曲线的拐点不一定正好在特征点上，也即曲线的最大曲率点有可能偏离节点。

2 应用实例

等值线间隔追踪算法的核心思想是以像素点的灰度值和相邻点连线的夹角为约束条件，在满足最小搜索半径的门限的前提下寻找合适的像素的点作为等值线的控制点。在算法实现过程中，可以通过调整各门限值来适应不同等值线的追踪，并且采用人工干预的交互式操作来保证追踪结果的正确性。等值线间隔追踪算法中门限参数的设置对于等值线的追踪效果有明显的影响，适用于不同情况下的等值线图纸追踪。

1）灰度门限

一般情况下，等值线图纸中同一条等值线的颜色是相同的，可以通过设置灰度门限将等值线上的像素点和等值线上其他图像信息区分开来。当图纸上干扰信息与等值线灰度值相近时，可以设置较小的灰度门限，减少误判的情况；当图纸上干扰信息与等值线灰度值相差较大时，可以设置较大的灰度门限，以保证追踪过程中不因门限过小而丢失等值线上的点。

2）最小搜索半径门限

通过设置最小搜索半径的门限可以矢量化虚线绘制的等值线，并且在绝大多数情况下追踪过程不会因为等值线的标注而中断。该算法采用头尾点同时追踪的方式，能够克服扫描图片上出现的线交叉的问题，确保追踪出的等值线分岔。

3）夹角门限

合理的设置算法中相邻点连线的夹角门限，可实现不同情况下的等值线追踪。对于等值线密集区域，设置较小的夹角门限，以确保不会追踪到相邻等值线上的点；对于曲率较大的等值线，则设置较大的的夹角门限，使追踪过程不会出现过多的等待人机交互的中断。

图3为灰度化以后的等值线图纸，图4为对等值线图纸中几条等值线采用等值线间隔追踪算法进行追踪的效果图，图中彩色等值线为追踪所得等值线，当等值线追踪到逆断层边界时，由于夹角门限的限制，可以有效的选取等值线上的点，并且在上盘线或下盘线处停止追踪。从实验结果中可以看出追踪所得的等值线与等值线图纸中等值线基本吻合。

图3 预处理后的等值线图纸

图4 等值线间隔追踪算法效果图

3 结 论

本文在基于圆追踪的非细化等值线矢量化基础上，改进并实现了等值线间隔追踪算法。该算法基于稀疏轮廓跟踪图像矢量化识别模型，采用非细化的方法直接对等值线进行追踪，通过人工干预保证追踪的正确性，适用于灰度等值线图像的矢量化。实验结果表明，本文的算法适用于灰度图像的等值线追踪，可以直接追踪粗细不同的等值线，且能适用于含有逆断层的等值线图的矢量化，最大优点是追踪出的线是没有分岔的线，能够克服扫描图片上出现的线交叉的问题，实现简单且具有高效性。

[1]刘修国, 谢 忠. MAPGIS 中扫描矢量化及其相关技术[J]. 地球科学, 1998, 23(7): 341.

[2]Khotanzad A, Zink E. Contour line and geographic feature extraction from USGS color topographical paper maps [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(1): 18-31.

[3]陈争光, 吴裕树, 王玉芳.一种新型的地形等高线矢量化方法[J]. 计算机工程与应用, 2004, 3: 84-86.

[4]赵国成, 孙 群, 安晓亚, 等. 一种从彩色扫描图像上提取等高线的方法[J]. 测绘通报, 2011, (4): 35-37.

[5]张志军, 孙志辉. 基于VC 平台的彩色图像的灰度化技术[J]. 计算机应用, 2005, 24(1): 61-67.

[6]艾自兴, 龙 毅. 计算机地图制图[M]. 武汉: 武汉大学出版社, 2005, 85-87.

[7]张鹏强, 翟 翊, 林群超. 大比例尺地形图扫描数字化影像变形纠正方法与实践[J]. 测绘学院学报,2001, 18(4): 280-283.

[8]杨 云, 朱长青, 孙 群. 彩色扫描地图中线目标的矢量化方法[J]. 计算机辅助设计与图形学学报,2009, 21(4): 533-541.

[9]黄本宇. 等值线图绘制算法研究及实现[D]. 西安:西安石油大学, 2007: 22-23.

[10]谭建荣, 彭群生. 基于图形约束的工程图纸扫描图像直线整体识别方法[J]. 计算机学报, 1994, 17(8):561-569.

[11]成 彬, 张树生, 石云飞. 工程图矢量化识别技术研究综述[J]. 工程图学学报, 2008, 29(6): 7-12.