基于连通区域标记的区域填充算法

苗龙元，于正林，王震

（长春理工大学 机电工程学院，长春 130022）

随着科技的发展，数字图像处理在各个领域占有越来越重要的地位。区域填充作为计算机图形学中的一项重要研究内容，被广泛运用于数字图像处理[1-7]和图形软件[8，9]中。在数字图像处理过程中，经常会出现由于图像采集过程中存在光线干扰、背景选用等问题，导致所要提取的目标图形在经过二值化等运算后存在缺失。为保证图像处理的最终效果，降低图像后续处理的难度，提高图像的处理效率，就必须对丢失区域进行填充。常见的区域填充算法有种子填充算法和扫描线填充算法等[10]。种子填充算法首先通过确定需要填充区域内部的一个起始点，然后利用4连通或8连通法检测其相邻位置的点是否为边界点，若不是则填充此点并继续检测其相邻点，直至检测完区域内的所有点完成区域填充。扫描线填充算法首先通过计算扫描线与边界的交点并对其进行排序，然后按照顺序对交点进行配对分类，最后填充奇数对两点之间扫描线覆盖的区域的所有像素点。扫描线填充算法虽然处理速度较快，但对填充交点分类较为复杂，面对含有复杂边界的区域时容易造成填充不完善，影响处理效果。种子填充算法虽然可以填充边界较为复杂的区域，但存在种子寻找困难、重复判断和占用较大存储空间等问题，从而导致效率降低。随着研究的深入，一些改进算法被相继提出。余腊生等提出的扫描线种子填充算法的改进[1]，通过修改入栈数据结构使填充速度得到较大提高，但堆栈操作仍然十分频繁。巨志勇给出一种新的基于链码的填充算法[2]，利用Freeman链码表示边界，提出一种新的边界分类准则，并利用边界上的左右端点对栅栏与交点间的像素取反进行填充，虽然不需要标记边界点且释放了大量内存，但对于某些图形（如图5b），此算法失效导致填充不完备。谭利等提出的新的连通域标记方法及其在医学图像中的应用[3]，虽然将连通域标记运用于区域填充提高了区域填充的速度和效率，但仍需对边界进行跟踪和标记造成效率降低。文献[4-6]提出的算法虽有改进，但依然存在由于边界限定导致的效率降低。刘海峰等提出的基于区域外接矩形的自动化孔洞填充算法[7]，虽放弃使用固定边界改以使用矩形的边界，但使用外接矩形容易导致处理图像质量下降。

考虑到正确的区域填充结果中各个填充部分必将是被闭合的外边界所包围，反之可以推出错误填充的部分中的部分像素点必定在图像的最大行（列）、最小行（列）上。由于连通区域标记可以对不同区域进行标记，并且每个区域产生固定的标号可用于对填充区域的判断。因此，本文提出将连通区域标记运用到区域填充中，提出基于连通区域标记的区域填充算法。通过连通区域标记对二值图进行标记，检测标记矩阵L的最大、最小行（列）上所含有的标号，并对标号相对应的区域进行取反，从而完成最终的填充。

1 算法原理

区域填充的最终目的是填充图像中闭合区域内的部分。然而由于区域填充的外形轮廓是任意且难以预知的，所以从轮廓的角度出发对区域进行填充必然会造成算法的复杂化，对于算法未涉及到的外形轮廓无法保证填充效果。但是由于区域填充中大部分区域具有一定的连通性，并且所需填充区域的外形轮廓必定是闭合的。所以，可以考虑从区域内部出发简化算法，提高填充效率同时实现对任意图形的填充。利用连通区域标记算法对取反后的二值图中的区域进行划分，其中在图片四条边界上出现的区域必然被认定为填充错误的部分。因此，连通区域标记算法将作为本算法的重要一环，综合考虑本文选用bwlabel[11]连通区域标记算法用于本文对二值图像进行分区标记。

1.1 bwlabel连通区域标记步骤

1）利用游程编码对输入图像进行标记。

2）扫描连续的团（run），在等价表中对其设定初始标记并记录等价对。

3）解析等价类。

4）在解析等价类的基础上对团（run）进行重新标记完成连通区域标记。

1.2 bwlabel连通区域标记分类

1.2.1 4邻域连通区域标记

如图1所示，4邻域是对中心点（C）邻近的0，1，2，3四个位置进行判断，如果0，1，2，3位置有点则认为C点与0，1，2，3位置点相连。否则，认为C点为孤立点。利用4邻域连通区域标记对图3（a）进行标记，得到图3（c）共有4个区域。

图1 4邻域

1.2.2 8邻域连通区域标记

如图2所示，8邻域在4邻域的基础上增加了在中心点对角线上的点作为被检测对象，相比4邻域，8邻域连通范围有所扩大。因此，导致在处理某些图形时相比4邻域会得到的区域个数会有所减少。如图3（d）所示，利用8邻域连通区域标记对图3（a）进行标记得到3个区域。

图2 8邻域

通过两种算法对图3（a）进行处理的结果的对比，可知4邻域连通区域标记相比8邻域连通区域标记对区域分割的更为精细。如采用8邻域连通区域标记对图3（b）进行处理，图中区域将被视为一整部分，由于区域没有封闭的边界将导致下半部分区域无法填充，而4邻域连通区域标记可以对其下半部分进行单独填充。因此，本文选用4邻域连通区域标记用于区域划分。

图3 连通区域分析

2 算法的步骤

1）对图4（a）进行二值化处理得到二值图4（b），并对图4（b）取反得到图4（c）。

图4 提出算法处理过程

2）利用4邻域区域连通标记算法对图4（c）中的区域进行标记，得到标记矩阵L、分区个数m和各分区的标记值。

3）设数组A=[ ]1:m，使用for循环遍历矩阵L的最大行（列）、最小行（列）上的每个元素并对其进行检测。如果检测到某个分区的标记值为i且A(i)≠0，则将标记值保存在B（数组）中，同时令A(i)=0且n=n+1（n为检测到的分区的标记值的个数）。否则，跳过此点继续检测。

4）检测完成后，根据n的值遍历B中元素，令L中标记值等于B中元素值的区域像素点的值置为0，得到图4（d）。

5）将图4（b）与图4（c）相加得图4e，完成对区域的填充。

3 实验结果对比

MATLAB作为当今国际上应用最为广泛，最为著名的数学工具，具有编程简单、良好的交互环境和自带大量图像处理库函数等优点，可以为使用者验证算法节省大量的开发时间。为实现本文提出的算法并与其它算法进行比较，本文选择采用MATLAB R2014a为实验平台实现本文所提出的算法。本文通过对同一图形分别采用一种新的基于链码的填充算法[3]和本文提出的算法进行实验对比，处理结果如图5所示：

图5 算法填充对比

由图5（a）和5（b）对比可知，巨志勇等[6]提出的算法虽然具有容易实现、节省存储空间和处理速度快等特点，但对某些复杂的图形进行填充时，会出现部分区域无法填充的情况，从而大大限制了其算法在图像填充中的普遍适用性。而本文提出的算法可以对各种具有任意复杂外形轮廓的区域做到精确填充。利用本文算法处理图6（a）（像素分辨率为1553*745）得到图6（b），总耗时为0.0560s仅为文献[2]提出的算法所用时间的15.70%。且由图7可知，本文提出算法总分配内存为18208Kb，相比文献[2]提出的算法节约18%的内存。因此，本文提出的算法拥有填充效率高、精度高适用于超大分辨率图像的处理等特点。

图6 提出算法对复杂图像填充的案例

图7 算法运行内存对比

由于本文提出的算法具有速度快、可填充任意复杂形状等优点，因此可通过交互式设计运用于图形设计（CAD等）软件中。设计结果如图8所示。

图8 交互式复杂图像填充案例

4 结论

根据区域的连通性和闭合区域填充的边界性，提出基于连通区域标记的区域填充算法。相比扫描线填充算法在填充复杂区域时会出现漏填或过度填充的情况，本文提出的算法可以做到精准填充。与种子填充算法相比，本文算法释放了较大的内存，提高了处理速度，减少了重复填充的可能。经试验证明，本文提出的算法可以对任意复杂的图形做到精准填充，而且具有容易实现、填充精度高、处理速度快、适用于超大分辨率图像等特点。