基于改进种子填充算法的地物快速填充应用研究

宋华平，郭鑫，李晋川

(1.重庆数字城市科技有限公司，重庆 400020； 2.重庆邮电大学光纤通信重点实验室，重庆 400065)

基于改进种子填充算法的地物快速填充应用研究

宋华平1∗，郭鑫2，李晋川1

(1.重庆数字城市科技有限公司，重庆 400020； 2.重庆邮电大学光纤通信重点实验室，重庆 400065)

地形图向GIS数据转换工作量巨大，在建筑物面状化处理过程中尤为突出。本文通过对此类工作特点的总结，以传统的种子填充法和扫描线种子填充法为理论基础，提出一种边搜索边填充、先填充再根据方向满行入栈的改进种子填充算法。通过仿真实验，对比传统种子填充算法，得出该算法具有解决重复出入栈问题、降低使用堆栈大小，

改进种子填充算法；区域填充；二次开发

1 引 言

建筑物面填充是GIS数据建库很重要的步骤，其所运用的给定区域快速填充算法是计算机图形处理中的一个重要课题。在进行图形处理时，不仅要画出图形的边界，常常还需要将边界范围内的所有像素单元都修改为指定的颜色。它在真实图形生成、计算机艺术、图像处理、高精度字体显示等多个领域中有着重要的应用[1]。因此，区域填充算法在计算机图形学领域地位举足轻重。

目前，最常用的区域填充是多边形填色，传统的区域填充算法有两种:一种是采用邻接链表的数据结构，通过确定区域边界的扫描线覆盖间隔来填充的扫描线(Scan Line)算法；另一种是采用递归方法，从给定的位置开始填充，到指定边界为止的种子填充(Seed Filling)算法。文献[2]提到的扫描线算法主要用于填充由简单边组成的规则区域，比如圆、椭圆以及其他一些标准的多边形，它在填充时对轮廓线的形状有一定的要求，需要预先知道区域的边界。在很多实际应用中，一个需要填充的复杂区域的边界事先并不知道，因此扫描线算法在处理带水平边的凹拐点时不能正确填充，但其利用了扫描线上像素之间的连贯性，因此具有较高的效率。胡云等[3]提出的种子填充算法不要求事先知道待填充区域的边界，就可解决边界比较复杂的和填充带有内孔的多边形区域填充问题。其原理是只要在某个区域(边界)内已知一个像素，并赋予填充色，以该点为起点，用4向连通方法或8向连通方法，就能从此像素出发找到区域内的所有像素点进行填充。简单直观的种子填充算法，由于进行大量的出入栈操作，因此效率很低，在特殊应用中填充速度就满足不了要求。在填充较大的区域时，要求分配较大的堆栈空间，不仅浪费了内存，还会出现堆栈溢出现象[4]。

鉴于以上的问题，本文吸取了种子填充算法的某些思想，提出一种边搜索边填充、先填充再根据方向满行入栈的改进种子填充算法，算法避免了堆栈大小的问题，将填充的点包括边界轮廓都存放在Filled队列链表中，用于下一步的轮廓识别。该算法通过VC++ 6.0平台的仿真验证，得出其进出堆栈次数远远低于经典的种子填充算法。在执行效率和占有栈空间大小方面也得到很好的改进。最后，利用Bentley MicroStation软件平台的二次开发工具，在某市勘测院GIS建库项目中实施该改进算法，发现填充速度很快，填充效果也能满足实际空间数据编辑管理的应用需求。

2 种子填充法及其改进思想

种子填充算法是从填充区域内部一点开始，并由此出发找到区域内的所有像素。算法从给定种子(X，Y)开始，先检测该点的颜色，如果它与边界色和填充色都不相同，就用填充色来填充该点，然后检测相邻位置，以确定它们是否是边界色和填充色，若不是，就采用递归算法填充该相邻点，直到此过程检测完整区域边界范围内的所有像素为止[5]。

2.1 种子填充算法

根据填充区域的特性，种子填充法可分为4向连通和8向连通两种。4向连通区域是指从区域中任意一点出发，在不越出区域边界的前提下，通过上、下、左、右4个方向的移动组合，搜索到达区域内的任意像素，这种填充方法就称为“4-连通算法”。8向连通区域是指从区域中某一点出发，在不越出区域边界的前提下，通过上、下、左、右、左上、左下、右上和右下全部8个方向到达区域内的任意像素，这种填充方法就称为“8-连通算法”。基于应用需要，本文只分析“4-连通算法”。

图1 连通方向示意图

如图1所示，假设中心的黄色点是当前处理的点，如果是“4-联通算法”，则只搜索处理周围红色标识的4个点，如果是“8-联通算法”则除了处理上、下、左、右4个红色标识的点，还搜索处理4个蓝色标识的点，但有时会出现越出边界的问题。

2.2 改进种子填充算法思想

为了使算法适用于任意复杂图形，并且具有较快的填充速度，本文采用边搜索边填充、先填充再满行入栈的方法。在入栈之前要判断行像素点是否已被填充，若已被填充才入栈，否则不予考虑。这样将会减少入栈的冗余像素，即每一个像素行只入栈一次。为此，种子填充算法改进如下:建立一个队列Filled和一个标志数组Flag来实现区域填充。

为了存储对每个新的子区域进行搜索填充的起始位置以及搜索填充的方向，定义一个堆栈，其存储结构体如下:

struct node{

int Xl；//当前扫描行填充区间的左边界X坐标intXr；//当前扫描行填充区间的右边界X坐标int Y；//当前扫描行Y

int Direction_4；//搜索填充的方向{-1，0}向左搜索，{1，0}向右搜索，{0，1}向上搜索，{0，-1}向下搜索

}

Link_Stack；

在算法的实现过程中我们可用for循环遍历定义好的方向即可实现递归搜索。

Direction_8[]={{-1，0}，{-1，1}，{0，1}，{1，1}，{1，0}，{1，-1}，{0，-1}，{-1，-1}}；//8个连通方向

Direction_4[]={{-1，0}，{0，1}，{1，0}，{0，-1}}；//4个连通方向

算法步骤如下:

①找出该区域内部任意一点，作为填充种子。Flag[Y]标志扫描第Y行是否全部填充过，若是，则Flag[Y]=true，否则Flag[Y]=false。对Y行进行扫描时，先检查Flag[Y]，当Flag[Y]=false时才填充该点。

②对Y行进行左、右方向搜索，并把填充后种子点存入队列Filled。Xl[Y]和Xr[Y]分别表示Y行最左端点和最右端点，这样扫描的种子像素时范围仅限于Xl[Y]≤x≤Xr[Y](x∈Filled)，此时满足Flag[Y] =true。

③将{{Xl[Y]，Xr[Y]}，Y，{0，1}}和{{Xl[Y]，Xr[Y]}，Y，{0，-1}}分别压入堆栈，作为向上搜索填充和向下搜索填充的起始信息。其中{Xl[Y]，Xr [Y]}为搜索区间，Y为搜索指定行，{0，1}和{0，-1}分别表示向上、向下的搜索方向。

④若堆栈为空，则填充过程完成，程序结束。否则继续执行以下步骤:

⑤栈顶元素出栈，将出栈信息作为新区域搜索和填充的起始信息。保留起始信息的左右端点至Xpl和Xpr中，根据起始信息中记录的方向在区间[Xpl，Xpr]内搜索下一条扫描行，若搜索到未填充点，则以其为种子点，重复②步骤。若在区间[Xpl，Xpr]内所有点都为边界像素或已填充像素，则说明当前连续区域已填充完毕，转步骤③。

图2 改进种子填充算法流程图

改进的扫描行种子填充算法如图2所示，对上述搜索上方扫描行未填充的像素作为种子像素点入栈的操作进行细化，算法描述如下:

InitStack()//初始化栈，并使它为空；

Setpixel()//给指定像素点赋色

Filledpoint()//存储已填充点

StackEmpty()//栈的判空函数

//算法开始:

while(!StackEmpty())

point=Pop()；

if(Flag[Y]==false)

if(point的最左点不为填充色也不为边界色)

{Setpixel(point的最左点)；Filledpoint(point的最左点)；}

if(point的最右点不为填充色也不为边界色)

{Setpixel(point的最右点)；Filledpoint(point的最右点)；}

else

Push({{Xl[Y]，Xr[Y]}，Y，{0，1}})；

Push({{Xl[Y]，Xr[Y]}，Y，{0，-1}})；

该算法中，对种子所在扫描行分上下两个方向进行分别逐行扫描，取标志数组和左右端点的数组.增加一个全局的结构体用以区分扫描方向，如此又可以减少对每条扫描行判定是否扫描过的步骤，提高效率。

上述算法的难点在于找到扫描行Y的未被填色的最左端点Xl和最右端点Xr后对其填色。可以分析的情形有三种，如图3所示:包括行单区间连续(图3之a)；行多区间连续(图3之b)；行多区间不连续(图3之c)。采用两端逼近的算法来解决，最终解决的时间复杂度都为O(n)。

图3 扫描行端点区间分类情况

3 算法比较

为了验证上述改进算法栈空间大小、进出栈次数、算法执行时间方面的改进，我们在计算机上进行了实验，该实验是在配置为Pentium4 1.4GHz/512MB/Windows XP/VC++6.0的虚拟机环境下完成的。具体实验数据如表1所示。

运行结果对比表 表1

由表1可以看出:①在栈所用空间大小方面，改进算法的栈空间大小大概是传统种子填充算法的栈空间大小的20%左右；②从进出栈的次数来看，传统种子填充算法的进出栈次数是改进算法的2.5倍；③利用改进算法对区域进行填充，可以大大加快填充速度，提高效率。

4 示范应用

随着GIS应用领域的不断扩大，应用功能的不断增强，系统对空间数据的要求也越来越高。在GIS数据建库的过程中，必须充分考虑成果的低成本、数据的真实性、建库的高效性等特点。本文算法在某市勘测院的地图整理编制应用过程中，利用Bentley MicroStation软件平台的二次开发功能[6]，很好地解决了建筑轮廓查找与构面的问题。其基本思想为:首先查找到建筑物结构的关键字(如“砖”、“砼”等)，然后以关键字为基础，搜索包含此文字的最小外接多边形，应用改进种子填充算法，将建筑物轮廓围合而成区域构成建筑物的面。如图4所示，填充粉色为一般建筑物，填充浅绿色为棚屋建筑物。

图4 算法实例效果图

利用查找建筑物结构关键字和改进的种子填充算法的建筑物构面过程，验证了改进种子填充算法的完整性和高效性，此方法大大地提高了大比例尺地形图建筑物构面的工作效率，也为大比例尺地形图中建筑物建库工作提供另一种可行技术手段。

5 结 论

市场经济的发展和行业的激烈竞争要求我们以“服务”的理念和姿态做事，这种服务也必须与时俱进、动态变化。这使得地理信息数据建库的方式、管理的过程都亟待变革，基于改进种子填充算法的GIS数据建筑物构面建库处理方式具有高效率、高精度、低成本等优点，弥补了传统AutoCAD建库方面的不足，大大减少了人机交互工作，所得成果令人满意。但我们在建库过程中也发现了一些不足，如程序处理对原始测绘数据要求较高，成果中有漏填充或错误填充现象。未来，我们将进一步优化该建筑物填充方法，以便将该方法更好的应用于GIS建库。

[1] Chang Fu，Chen Chunjen，Lu Chijen.A linear time component labehng algorithm using contour tracing technique[J]. Computer Vision and Image Understanding，2004，93(2): 206～220.

[2] 施一军.基于GIS技术建立地图数据库的构想和实现[J].测绘通报，2011(11):71～73.

[3] 胡云，李盘荣.一种改进的种子填充算法[J].无锡市广播电视大学学报，2008(2)；31～34.

[4] 孙家广，杨长贵.计算机图形学[M].北京:清华大学出版社，2003:234～247.

[5] 秦晓薇.区域填充算法的研究[J].赤峰学院学报:自然科学版，2011(6):47～49.

[6] Winters.学习MicroStation VBA[M].北京:中国水利水电出版社，2007:194～231.

App lication research ofmodified Seed Filling Algorithm in the Fast Filling Process for Ground Object Data

Song Huaping1，Guo Xin2，Li Jinchuan1
(1.Chongqing Cybercity Sci-tech Co.，Ltd.Chongqing 400020，China； 2.Key Laboratory of Optical Fiber Communication Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China)

The data conversion from topographicmaps to GIShas a hugeworkload，especially in the process of building Poindirtize.According to a summary of the characteristics of this type ofworks and the theoretical basis of traditional Seed Filling Algorithm and Scan-Line Seed Filling Algorithm，this paper proposes a modified Seed Filling Algorithm which can realize searching and filling simultaneously and firstly filling then full row accessing the stack according to the direction.By comparing with traditional Seed Filling Algorithm，simulation results show that the new algorithm has the ability to solve the problem of repeated accessing stack.What’smore，new algorithm can reduce the number of requiring stacks，and speed up the building(ground object filling)process.Finally，this paper uses Bentley MicroStation software platform secondary development tool to realize the fast library setting bymodified Seed Filling Algorithm.

modified seed filling algorithm；region filling；secondary development

1672-8262(2013)04-49-04

P208.2，P209

B

2012—10—07

宋华平(1979—)，男，助理工程师，主要从事地理信息系统开发及数据处理等工作。

加快地物building填充速度等优点。最后，利用Bentley MicroStation软件平台二次开发工具，实现了改进种子填充算法对建筑物的快速建库处理。