对遥感影像进行分割得到大量的面状对象即图斑，对图斑进行边界矢量化以得到矢量数据是常用的处理。本文提出了图斑边界矢量化的一种简便算法，该算法基于真实待选像素角点集和待选点优先原则来跟踪边界多边形的顶点，通过排除内像素角点及伪相邻的像素角点确定出真实待选像素角点集，而待选点优先原则具有逻辑严密、原理简单的特点。本算法易于实现且执行效率高，可用于图斑的快速矢量化，算法通过VC++编程得以实现。
一、引言
栅格数据和矢量数据是GIS的2种基本数据类型，二者间的互相转换是常见的操作。栅格数据转换为矢量数据，比较常见的是遥感影像分割图或其分类图斑的边界矢量化，常用的方法有边缘跟踪法、有向边界法、散列线段聚合法、游程编码追踪边界法、基于四叉树结构的压缩编码追踪弧段法等。很多GIS软件、遥感图像处理软件具有相应的栅格数据矢量化的功能模块，但具体运用时有时会遇到一些问题，甚至转换失败。
笔者在进行遥感影像分割结果应用软件开发过程中，需对影像分割结果进行矢量化处理，提取各图斑的边界并形成矢量格式的shapefile文件，这需要开发栅格数据矢量化模块。本文提出了一种沿图斑边界跟踪提取真实角点的方法，该方法首先通过排除图斑包含的内角点、伪相邻角点两类干扰性角点得到候选角点的真实集合，再依据逻辑严密的候选角点优先原则判定出正确的待定角点，按此方法逐个搜索出图斑边界的顶点，跟踪并连接图斑边界顶点以构成封闭多边形。该方法的原理简洁易懂，算法易于实现，执行效率高，对于遥感影像分割后的图斑矢量化具有良好的效果。
二、算法介绍
对多光谱遥感影像进行分割，得到分割图，在此基础上提取出各图斑，现需对图斑逐个进行边界矢量化，以得到边界线矢量文件。如图1所示，图斑的边界线是一封闭多边形，多边形顶点的准确位置应是图斑边界像素的像素角点而非中心点，只有这样边界多边形的周长和面积才准确。分析可知，矢量化处理的关键是计算边界多边形全部顶点的坐标，而边界多边形的顶点全部来自于图斑边界像素的像素角点。
图1：边界矢量化示意图 图2：像素与像素4角点的坐标关系
本文算法以单个图斑为对象，算法思路为：
1) 以图斑为单元提取其包含的全部像素，对每个像素P，记录其坐标(row, col)和像素4角点C1、C2、C3、C4的坐标[(row-1, col-1), (row-1, col), (row, col), (row, col-1)]，如图2所示，易知像素坐标与像素4角点坐标的数量对应关系。可知任一像素角点为4个相邻像素所共有，而4个像素有的在图斑内有的则在图斑外，对照图1及图2，可知图2中像素角点C3对应的4个像素P、P2、P3、P4均在图斑内，而像素角点C1、C2、C4对应的4个像素中均有处于图斑外的。本文称图斑包含的像素为有效像素。
对整个图斑，经提取可得到像素4角点坐标集合A = {(x0, y0),(x1, y1), …, (xm, ym)},像素坐标集合B = {(X0, Y0), (X1, Y1), …, (Xn, Yn)}。
2) 分析知集合A包含了2种像素角点的坐标，一种像素角点为边界多边形的顶点，比如图2中的像素角点C1、C2、C4，另一种像素角点处于边界多边形的内部，比如图2中的像素角点C3，这些内部的像素角点并非边界多边形的顶点，因而须被剔除。此处定义内像素角点，指位于边界多边形内部的像素角点，从图1及图2观察易知内像素角点对应的4个像素均在图斑内，因而内像素角点的判定规则为：其对应的4个像素坐标均在图斑像素坐标集合B内。
从集合B中提取出这样的相邻4像素组合，再依据像素坐标与像素角点坐标的数量关系推算像素角点坐标，该点即为内像素角点，以此构成内像素角点坐标集合E。集合A减去集合E形成新的集合C，集合C中的元素全为边界多边形的顶点坐标，集合C的求解过程如图3所示。
图3：边界多边形顶点坐标推算
3) 定义伪相邻的像素角点对概念，伪相邻的像素角点对是指同为边界多边形的顶点、位置上相邻（即距离为一个像素尺寸）但不隶属同一有效像素的像素角点对，如图4中像素角点Pi、点Pj即是伪相邻的像素角点对。在代表边界多边形顶点的集合C内，逐一判定出伪相邻的像素角点对并将其存入到集合D = {[(xi, yj), (xs, yt)], [(xa, yb), (xc, yd)], …}中。伪相邻的像素角点对集合D与边界多边形顶点集合C相结合，用于确定出真实的待选像素角点集合，该集合将在下文的顶点搜索规则中加以运用。
4) 依据像素坐标值找出图斑顶行的第一个有效像素，将该像素的左上角点C1设定为边界多边形跟踪的起始顶点，该像素的右上角点C2作为边界多边形的第二个顶点。
5) 按照顶点搜索规则沿图斑边界跟踪搜索余下的边界顶点，下文将对顶点搜索规则进行详细阐述。
6) 按顺序依次连接搜索到的顶点，形成所求的边界多边形并封闭。
本文算法的原理如图5所示。该算法的核心是顶点搜索规则，而该规则是基于真实待选像素角点集合和候选点优先原则2项内容的，关于候选点优先原则，下文将予以阐述。本算法处理的数据为边界多边形顶点坐标集合C和伪相邻的像素角点坐标集合D，集合C的数据量为图斑的顶点数量，而集合D的数据量则取决于图斑的复杂度。由此可知，该算法的复杂度主要取决于边界多边形的顶点总数，因而运算量较小。
图4：伪相邻的像素角点对 图5：算法原理图
确定了边界多边形的起始顶点及第二个顶点后，多边形其它顶点的搜索是一个迭代过程，其本质是按顶点搜索规则进行边界跟踪。本方法的顶点搜索规则为：
1) 设当前顶点为Pi，上一顶点为Pi-1，Pi、Pi-1均已知，待求顶点为Pi+1。本文定义“方向线”这一概念，其涵义是从点Pi-1指向点Pi的有向连线Di。方向线Di值设定如下：从左指向右时为0，从上指向下时为1，从右指向左时为2，从下指向上时为3，如图6所示。
2) 求下一顶点Pi+1等价于确定下一方向线Di+1（从当前点Pi指向待求点Pi+1的有向连线），易知理论上待定方向线Di+1有三候选值，相应的待求点Pi+1有三候选点。本搜索规则规定待定方向线Di+1的三候选值须遵循优先原则，以当前方向线Di值为0为例，Di+1的优先顺序为：Ⅰ>Ⅱ>Ⅲ, 即按优先原则Di+1值顺次为：3 > 0 > 1，如图6所示。完整的待定方向线优先原则见表1。
3) 按照优先原则，从边界多边形顶点坐标集合C中挑选出第一候选点，参考伪相邻的像素角点对集合D判定其是否为伪相邻的像素角点，若非则该候选点即为待定点Pi+1，该步骤结束进入步骤4)；若为伪相邻的像素角点，则按优先原则挑选下一候选点进行是否为伪相邻的像素角点的判断，依此类推，直至挑选出正确的待定点。
4) 确定的待定点Pi+1成为新的搜索的当前点，待定方向线Di+1也成为新的搜索的当前方向线，重复步骤2)-3)进行迭代运算，这样顺序搜索得到边界多边形的所有顶点。
5) 当待定点是边界多边形的起始顶点时，搜索过程完成，同时也实现了边界多边形的闭合。将得到的所有方向线依次连接起来，就形成了所求的边界多边形。
易知，该搜索规则的主要部分是步骤2)和步骤3)，而这两步的处理过程均十分简单，运算量小，因而顶点的搜索过程速度较快，运算执行效率高。此过程中，将图斑边界多边形的顶点搜索过程转换成了方向线的构造及连接过程，在边界矢量化过程中同时实现了顶点的搜索与弧段的构建，具有快速、简便的特点。
图6：方向线值定义 图7：方向线优先原则示意图
表1：方向线优先原则表
三、试验
试验所用数据为某地区的SPOT 5多光谱影像，影像尺寸为2000×2000。采用均值漂移法（Mean Shift）对影像进行分割，分割结果如图8所示。利用VC++编程实现了本文的算法，对分割结果中的图斑逐个进行边界矢量化，得到了相应的shapefile矢量文件，其结果如图9所示。从图9可见图斑的边界矢量化取得了良好的效果，所有图斑不论大小均得到了正确的矢量边界，没有信息的丢失。为充分验证本算法的效率，选用不同尺寸的SPOT 5多光谱影像进行了测试，测试所用机器环境为：Intel Core2 Duo P9600 CPU，主频为2.66GHz,内存为3GB RAM，Window XP操作系统，同时将本文算法与常用的遥感影像处理软件Erdas Imagine 9.1的栅格数据矢量化的效率进行对比，Erdas软件的矢量化耗时通过人工计时得到，测试结果如表2所示，表2中图斑总数、图斑顶点总数是通过将生成的shapefile矢量文件加载到GIS软件ArcMap中并通过相应处理得到的。由表2可见，相对于Erdas软件，本算法的运算速度较有优势，处理非大尺寸（超过1万像素级尺寸）的影像的矢量化可满足要求。
依据本文算法原理，本算法的复杂度与边界多边形的顶点总数存在直接关系，依据表2结果制作了影像图斑边界矢量化耗时与边界顶点总数的关系曲线图（图10），从中可知影像的图斑边界矢量化耗时与其边界顶点总数呈近似的线性关系。本算法的复杂度还与图斑的伪相邻的像素角点对存在情况有关，但伪相邻的像素角点对存在数量较少，只有在少量的边界顶点判定时须结合伪相邻的像素角点对的判断，因而关系曲线图呈近似线性。
图8：遥感影像分割图 图9：图斑边界矢量化结果
表2：算法效率测试结果
图10：耗时统计曲线图
四、结束语
本文提出的边界矢量化算法的实质是以边界像素为着眼点，依据边界上相邻像素角点的空间关系建立一种简便的顶点搜索规则来逐个确定真实的边界多边形的顶点，从而实现边界顶点的跟踪，算法原理简单且易于实现。边界顶点跟踪的过程中每次仅操作当前顶点的待定方向线，因此整个矢量化用时仅与边界顶点个数有关。
不仅如此，在边界跟踪过程中将边界顶点的待定转换为相邻像素角点连接向量（即方向线）的待定，这样在跟踪边界顶点的同时动态构造边界多边形的每个单元弧段，从而快速的将栅格图斑转换成矢量面域。
本文算法充分利用了栅格数据边界像素角点间的几何及拓扑关系，因此避免了复杂的弧段追踪和拓扑构建过程，大幅提高了栅格数据边界矢量化的效率。
参考文献
[1]陈述彭,鲁学军,周成虎等.地理信息系统导论[M].北京:科学出版社,1999.
[2]苏程,周祖煜,倪广翼,俞伟斌,黄智才,章孝灿.基于像元有向边的栅格数据扫描线矢量化方法[J].计算机辅助设计与图形学学报,2011,7(23):1139-1146.
[3] Yang B,Purves R,Weibel R.Efficient transmission of vector data over the internet[J].
International Journal of Geographical Information Science,2007,21(2):215-237.
[4]Rafael C.Gonzalez Richard E.Woods著.阮秋琦,阮宇智等译.数字图像处理(第二版)[M].北京:电子工业出版社,2005.
[5]李占才,刘春燕.点阵图形矢量化的高效方法——有向边界法[J].计算机应用与软件,1997,(3):48-51.
[6]黄波,陈勇.矢量、栅格相互转换的新方法[J].遥感技术与应用,1995,10(3):61-65.
[7]谢顺平,都金康,王腊春,顾国琴.基于游程编码的GIS栅格数据矢量化方法[J].测绘学报,2004,33(4)
:323-327.
[8]吴华意,龚健雅,李德仁.无边界游程编码及其矢栅直接相互转换算法[J].测绘学报,1998,27(1):63-68.
[9]唐宏,盛业华.一种新的矢量化方法[J].北京测绘,1999,(3):13-15.
作者：徐莹1，王涛1，崔晨风2
(1.天津市测绘院,天津 300381；2.西北农林科技大学水利与建筑工程学院）
声明：中国勘测联合网登载此文出于传递更多信息之目的，并不意味着赞同其观点或证实其描述，文章内容仅供参考。
