扫描线种子区域填充算法的研究与实现

王利祥

（河南护理职业学院 河南 安阳 455000）

1 引言

随着社会科学技术的飞速发展，数字图像处理技术也得到了很快的发展，尤其是计算机和网络技术出现以后，数字图像处理技术渐渐的占据了图像处理技术领域的整个区域。随着数字图像在社会生活和工作中扮演的角色越来越重要，图像处理理论和技术研究也越来越受到了各个领域的广泛关注。与此同时，伴随着4G+以及互联网+时代的到来，移动终端设备比如手机、pad、笔记本电脑等的高速发展，特别是手机的功能逐渐强大，人们对图形图像处理的实时性和智能化提出了更高的要求。因此研究和完善并且使用更加高效的区域填充算法[1]仍然具有很高的研究价值和应用市场。

2 研究背景及意义

在计算机对现实中的图形图像进行存储时，只是对图形图像的边缘以及内部填充的颜色进行存储，当计算机对这些数据处理时，需要对存储的这些数据进行复原。在复原的过程中，首先要判断出图形图像元素的边界线或简单的特定区域，然后对边界线内部进行渲染，整个过程我们称之为区域填充。

区域填充算法属于计算机图形学应用和研究中的基本算法之一，属于计算机图形学与图像处理两大学科领域交叉的基本问题之一，它在实际应用广泛应用图像处理、目标分析以及计算机图形学中的其他领域。

3 区域填充算法的研究

传统的区域填充算法主要有边界标志区域填充算法、种子区域填充算法、边界区域填充算法和扫描线区域填充算法。

3.1 边界标志填充算法

该算法又称为边标志算法，其大致思想为：首先使用直线光栅化算法绘制出图形图像的边界线，在此过程中会得到扫描区域中横纵坐标的最大值和最小值，即扫描线的方形扫描区域，然后对扫描区域进行扫描填充，即可得到复原的图形图像。该算法的优点在于：

（1）不需要对像素点进行求交集运算以及对每个边界线的交点也不需要进行排序；

（2）对扫描区域中的每个像素点只访问一次，因此计算效率高、时间复杂度小。

3.2 种子填充算法

传统的种子填充算法，无论是基本的简单种子填充算法还是基于扫描线来实现的扫描线种子填充算法，其大致思想是基本类似的：首先从多边形区域内部选择某一个像素点，该像素点我们称之为种子点，然后以该种子点作为起点，依次访问种子点上下左右连通的四个点，当访问所有的像素点之后，分别依次使用四周的点作为新的种子点，使用相同的方法进行访问，直至整个多边形区域都被填充。种子填充算法的优点是由于经过多次递归，其实现原理和程序都比较简单。缺点是算法递归次数较多，进出栈比较频繁，因此执行效率不高，占用内存较大、空间复杂度较大；第一个种子点的寻找难度比较大；存在有的像素点会被重复访问的现象。

种子填充算法根据区域连通性的不同可以分为八连通区域和四连通区域，因此在实际使用过程中，经常使用到的种子填充算法有边界表示的八连通区域种子填充算法、内点表示的八连通区域种子填充算法、内点表示的四连通区域种子填充算法、边界表示的四连通区域种子填充算法。

3.3 扫描线填充算法

该算法适合对适量图形进行填充，只需要确定多边形区域的几何位置即可，算法的核心是求交运算。基本思想大致为：首先使用水平扫描线依次从横坐标最小的扫描线到横坐标最大的扫描线扫描，每条扫描线都会与多边形的某些边界线产生一系列交点，然后将这些交点按照横坐标的值进行排序，将排序之后的点两两配对，作为线段的两个端点，最后将两个端点之间的线段填充所需要的颜色即可。该算法经常与种子填充算法结合使用，称为扫描线种子填充算法。该算法的优点在于实现简单方便，缺点为求交运算量大、需要对点进行排序、空间复杂度较大。

3.4 边界填充算法

该算法的基本思想是从指定位置开始，将所有连通区域内某种指定颜色的点都替换成另一种颜色，从而实现填充效果。该算法在实现时对于边界以内的像素点无论是需要填充为什么颜色，都替换为指定的颜色。鉴于边界填充算法对边界线的要求比较明显，因此在实际应用中也是非常广泛的，比如图形处理软件中经常使用到的“油漆桶”功能就是边界填充算法使用的一个很好的例子。它的优点在于实现简单，而且与边的顺序没有关系；缺点有：存在有些像素点会被重复访问的想象，同样也需要对每条扫描线与多边形区域[2]的某些边界进行求交运算。

4 扫描线区域填充算法的实现

本文在深入研究大多数区域填充算法的基础上，经过对上述传统填充算法的对比，最终选择一种将扫描线填充算法和种子填充算法相结合的扫描线种子填充算法[3]作为更深入的研究点，然后进行了算法的实现。该算法不再使用递归的方式来处理八连通区域和四连通区域的相邻像素点，这样在算法处理过程中只需要将每个水平像素段的起始点存放到一个栈中，这样的话就不需要像使用递归算法那样将当前像素点周围的所有相邻像素点全部进栈，从而节省内存空间，降低算法的空间复杂度，而是沿水平扫描线填充像素段，一段一段的来处理四连通区域和八连通区域的相邻像素点。

算法的基本过程如下：假设给定的种子点为(x，y)，首先以该种子点为中心，分别向种子点的左右两个方向填充所需要的填充色，确定当前种子点所在的扫描线位于扫描区域内的像素点范围，并记为[X_Left，Y_Right]，由左右范围即可确定这一段区域的连通性，然后确定该连通区域上、下扫描线位于需要填充区域的像素点，然后对这些像素点依次进栈保存。重复上述的过程，直至整个填充区域的像素点都被填充为止。

算法的实现步骤大致可由下列四步实现：

（1）在内存中定义一个空栈，其作用是为了存放扫描过程中的种子点，首先将已知的种子点(x，y)进栈；

（2）在每次进行出栈操作时都要判断当前栈是否为空栈，如果为空栈，表示需要填充的区域已经填充完毕，此时终止算法即可，否则栈顶元素出栈并作为新的种子点进行扫描；

（3）从当前种子点出发，分别沿着当前的扫描线向种子点的左右两个方向对扫描线上的相邻像素点进行填充。直到遇到多边形区域的边界线为止，此时分别标记当前区段的左右两个端点的横坐标为X_Left和X_Right；

（4）分别检查与当前扫描线相邻的上下两条扫描线在区间[X_Left，X_Right]中的像素点，此时从X_Left开始向X_Right方向对遇到的像素点进行填充，如果遇到非边界像素点而且是未填充的，则找到这些像素点相邻的最右侧的一个，并将其作为种子点进栈，然后重新执行第（2）步。

5 结语

区域填充算法在图形图像处理中经常用到，具有很高的理论和应用价值。因此对各种场景提出不同的有针对性的区域填充算法的研究一直备受关注。本文首先阐述了区域填充算法的应用背景及研究意义，对区域填充算法的定义进行了阐述，然后针对传统的区域填充算法进行了深入研究，分别论述了四种不同填充算法的实现思想和优缺点，最后选择了扫描线填充算法和种子填充算法作为结合体，并对扫描线种子填充算法进行了实现，并列举出实现过程。为后续的研究奠定了一定的基础。