基于双堆栈的区域标记算法

陈　冲，管庶安

(武汉轻工大学 数学与计算机学院，湖北 武汉 430023 )



基于双堆栈的区域标记算法

陈冲，管庶安

(武汉轻工大学 数学与计算机学院，湖北 武汉 430023 )

摘要：二值图像的区域标记是图像分析中的基本操作。提出了一种基于双堆栈的二值图像区域标记算法，并且在理论与实验结果上与传统的单堆栈算法和递归算法进行了对比，发现双堆栈算法在空间复杂度和时间复杂度方面都得到了极大的改进。

关键词：二值图像；区域标记；双堆栈；空间复杂度

1引言

区域标记是二值图像分析中的最基本操作之一，由于图像数据量很大，因此要尽可能降低算法复杂度，以便用于实时处理场合。目前常用的算法有：(1)基于递归的二值图像连通域像素标记算法[1-2]，该算法的优点是源程序直观简捷，但空间复杂度较高。(2)优化路径的种子填充算法[3],该算法基于单一堆栈存储周转像素，并尽可能减少入栈种子点的数量，提高了程序效率，但算法的控制结构较复杂，堆栈空间的减少量有限。此外，国内对区域标记算法研究还有游程编码方法[4-6]，线的区域标记算法[7]，顺序法[7]，R C L 算法[8],二值连通图像快速算法[9],基于链表的二值图像标记算法[10]等，这些算法都是基于现有算法改进的，对复杂度问题的改进不显著，笔者在现有算法的基础上提出了一种双堆栈的区域标记算法。

2常用的连通区域标记算法

2.1递归的区域标记算法

不失一般性，设二值图像中的像素标记连通区为n×n像素矩形尺寸为n×n像素，考虑到标记标记量很大的情况，设连通区域中的像素在标记前各像素的标记值为1，标记后为M(M≠0,1),递归函数的结构如下：

Mark_1(p0)

{将p0点的像素标记为M；

for(p0的4邻域点pi，i=1,2,3,4)

{if (pi为标记的点) 则用pi作实参调用Mark_1(pi)；

}

}

图1为p0的4-邻域。

图1　p0的4-邻域

该算法的空间复杂度分析：每当函数递进调用一次，就要新建一对形参变量(x0,y0)；当返回一次，才会释放本次建立的变量。在调用中，当p0的4邻域不存在未标记的点时，函数将返回，否则，函数继续向前递进，图2表示一个7×7连通区的标记过程，设左上角的点最先标记，一旦标记开始，将一直调用向前递进，直到所有点标记完毕后，才开始从图2右下角处，沿图中的箭头相反的路径返回到终点。

图2　递归算法下的7×7连通区标记过程

由以上分析可知，递归算法的空间复杂度，主要为每次递进调用时新增加形参变量空间总量以及每次调用函数时系统保留CPU运行现场需要的堆栈空间。其复杂度可记为OR(n2)。

该算法时间复杂度：利用系统的一个硬件计数器可测量算法的时间开销，调用前后，获得该计数器的计数值T1和T2，则运行时间=T2-T1)/FS，其中FS为系统计数器的时钟频率，可由QueryPerformancecounter() 函数得到。

2.2单堆栈的区域标记算法

该算法采用一个堆栈来存储标记过程中搜索到待标记点，设S为一个堆栈，p0为待标记区域的起点，算法如下：

对p0进行标记，并将其压入S;

do{

for(p0点的4-邻域点pi，i=1,2,3,4)

{if(pi为待标记点){对pi进行标记，并将pi压入S；}

}

从S中弹出一点，作为p0；

}while(S非空);

图3　单堆栈算法下的操作过程

该算法时间复杂度分析：由于该算法不需要保护现场和恢复现场，所以时间复杂度比递归时间复杂度稍小，也可以采用测量递归时间复杂度的方法测出。

3双堆栈的区域标记算法

双堆栈算法采用了两个堆栈，其中一个进行弹出，另一个进行压入，弹出时搜索弹出点的4-邻域没有标记的点，一一压入另一个堆栈，弹出栈空后，交换两堆栈。算法如下：

首先建立两个堆栈S1,S2，分别用于压入和弹出点。设p0为种子点

①将p0其压入S1，并将其标记为M,并将其压入S1，置S2为空；

② 交换 S1和 S2;

③ 从S2中逐一弹出压入的点。每弹出一点，立即搜索该点4邻域未标记的点，并将其标记改为M，并将其压入S1;

④ 在③中，若没有压入任何点，则结束连通区搜索；否则，转到②。

图4是运用双堆栈算法对一个7×7矩形连通区进行标记的过程，其中空心点和实心点分别对应压入S1和S2中的像素。箭头总是指向下一个弹出的点。显然，当箭头开始指向斜对向线的端点时，S1达到最大深度，而S2可达到最大深度为6。一般地，当对于n×n 矩形连通区，两个堆栈的最大堆栈深度之和为2n-1。其空间复杂度为O2s(n)。

该算法时间复杂度分析：可以采用递归时间复杂度方法测出。

图4　双堆栈算法下的标记过程

4三种算法实验结果

为了验证以上分析，特对一个二值图像中的尺寸为620×460的连通区域记性标记。并且采用VC++ 2010进行仿真，计算机配置为：Intel Celeron CPU 2.6 GHz，内存4 GB；64位win10 操作系统。所测得的数据如表1所示，表1中，时间消耗是利用系统的一个硬件计数器测量的，取10次测量数据的平均值为所需要的数据。表1中所需内存由编程时设置系统堆栈大小实现。

表1三标记种算法的时间以及占用的存储空间

算法时间消耗/ms所需内存/M字节递归11.442100单堆栈2.24011.09双堆栈3.0740.007

由表1可以看出双堆栈算法占用的空间比单堆栈算法占用的空间小102多倍，比递归算法空间小104多倍，所耗用的时间和单堆栈算法差不多，但比递归时间小的多。通过实验结果，验证了理论理论分析的结论，证明双堆栈算法在空间复杂度上远优于单堆栈算法和递归算法，在时间复杂度上和单堆栈算法差不多，但比递归算法消耗时间少的多。

5结束语

区域标记在图像分析与识别中是一种必不可少的操作。笔者提出的双堆栈标记算法，与现有递归算法和单堆栈算法对比，在时间复杂度与空间复杂度上有了很大的改进。在基于视觉测量的工业产品品质在线实时检测中有较高的应用价值。

参考文献:

[1]徐正光,鲍东来,张利欣,等.基于递归的二值图像连通域像素标记算法[J].计算机工程,2006,32(24):186-188.

[2]喻杰,许化溪,WANG Sheng-jun,等.一种易于实现的适于细胞图像连通区域的标记算法[J].江苏大学学报(医学版),2005,15(2):152-153.

[3]孙远志,孙卫红.优化路径的种子填充算法[J].东华大学学报(自然科学版),2007,33(3):378-381.

[4]刘奇琦,龚晓峰.一种二值图像连通区域标记的新方法[J].计算机工程与应用,2012,48(11):178-180.

[5]沈乔楠,安雪晖.基于游程递归的连通区域标记算法[J].计算机应用,2010,30(6):1616-1618.

[6]徐利华,陈早生.二值图像中的游程编码区域标记[J].光电工程,2004,31(6):63-65.

[7]曹长虎,李亚非.一种二值图像连通区域标记快速算法[J].科学技术与工程,2010,10(33):8168-8171.

[8]张云哲,赵海,宋纯贺,等.一种新的连通区域标记算法[J].计算机应用研究,2010,27(11):4335-4337.

[9]高红波,王卫星.一种二值图像连通区域标记的新算法[J].计算机应用,2007,27(11):2776-2777.

[10]冯海文,牛连强,刘晓明,等.高效的一遍扫描式连通区域标记算法[J].计算机工程与应用,2014(23):31-35.

Region marking algorithm based on double stack

CHENChong,GUANshu-an

(School of Mathematics and Computer Science，Wuhan Polytechnic University，Wuhan 430023， China)

Abstract：Binary image region marking is a basic operation in image analysis. The paper presents a binary image region marking dual-stack algorithm, and the results are compared with the traditional single stack algorithm and recursive algorithm ,it is found that the dual- stack algorithm has been improved greatly in space complexity and time complexity.

Key words：binary image ;region marking;dual-stack ;space complexity

中图分类号：TP 391.413

文献标识码：A

DOI:10.3969/j.issn.2095-7386.2016.01.020

文章编号：2095-7386(2016)01-0092-03

作者简介：陈冲(1990-),男,硕士研究生,E-mail:546606432@qq.com.通信作者：管庶安(1956-)，男,教授, E-mail:jsj-g@163.com.

收稿日期：2015-11-02.修回日期:2015-12-24.