基于SRG的快速图像分割算法研究与实现

唐万成，叶邦彦，梁立东

(华南理工大学 机 械与汽车工程学院， 广东 广 州 5 10640）

图像分割是计算机视觉重要研究内容，计算机视觉中的图像理解包括目标检测、特征提取和目标识别等,都依赖于图像分割的质量。在图像处理与分析中，人们往往只对图像中的某些区域感兴趣，需要将感兴趣的区域从背景中分离出来，并且将其标记，才能进行下一步的处理与分析。因此，图像处理的目标是将构成图像的各个像素分配到不同的区域中[1]，从而将人们感兴趣的区域从复杂的背景中分离出来。图像分割算法有很多种，广义上可分为：基于阈值的分割算法、基于边缘检测的分割算法、基于区域分割算法以及基于簇类的分割算法。其中基于区域的算法最容易实现自动化。区域生长法（SRG）是基于区域分割算法的一种，其原理是通过给定的生长点（区域）逐步合并其周围特征一致的像素点（或区域），形成一个大的区域。

SRG分割算法在图像分割与连通域标记中应用广泛，在图像处理技术中已有许多研究[2-6]，其算法步骤有：1）选择合适的生长点2）确定生长准则3）确定生长停止条件。文献[1]通过SRG算法对彩色图像进行智能分割，取得很好的效果。文献[7]中提出一种结合SRG与分水岭算法得出的一种图像分割算法，该算法首先用分水岭算法进行初始化分割，然后再利用SRG算法进行合并。尽管SRG便于实现智能图像分割，但传统的SRG算法需要给定生长、多次扫描整张图片，而且大多算法复杂程度高，执行效率低，不利于用在快速图像序列分析与检测。

为了提高分割算法效率，本文模拟自然界中的病毒感染过程，提出一种基于SRG的智能分割算法，并在VC++6平台上将其实现。通过实验，证实该算法不仅能够只通过一次扫描便可将目标与背景分离，算法周期短，同时还能够对亮暗不均匀的图像进行目标分割、并且能将目标逐一标记，方便后期区域的重建与检测。

1 基于SRG的快速图像分割算法

基于SRG的快速图像分割算法是模拟了生态中的病毒感染过程。在生态中，病毒在传播时，当遇到能够被感染的个体便寄宿在该个体上，此时该个体成为病毒携带体。该病毒携带体成为感染源，立即将其周围没有被感染过、且体抗力不强的个体逐一感染。被感染的个体成为新的感染源，并按照相同的方式逐步感染完整个区域的所有能被感染的个体。以此方式感染其他区域的个体。区域的标记可用该区域中第一个被感染的个体作为记号。

这样的过程与该算法分割目标的过程极其相似，为了更好的了解这两者之间的关系，作了两者的对照表，其对应关系如下：

种群区域→目标区域

感染源→生长点

生态→图像

个体→像素

因此，参照病毒感染过程，将这种过程用于图像分割算法中，其步骤如下：

步骤1：确定区域生长点

算法确定生长点时是根据区域边界两侧像素灰度差大小确定的。每隔m行，n个像素单向遍历图片。目标区域与背景往往有较大的像素差，但边界的相邻两个像素的像素值却很相近，因此为了保证探测初始生长点的准确度，采用基于跨像素搜索。如图1所示。

图1 生长点探测图示Fig.1 Seed detecting figure

图中：1为向右探测；3为向左探测。1,3,4的特点是探测基点在背景上，情况2是探测不出来的，但可以在另一行的扫描中的情况4探测到。探测准则为：当找到一个像素点，满足表1中的某一种情况时，则确定当前区域的第一感染源。

表1 感染源判据表Tab.1 Origin virus criterion

表中，g(i，j)为标记矩阵，g(i，j)=0，表示该像素已被感染过，反之则未被感染。

参数λ与图像背景亮度相关，该参数的存在是为了处理光线不均匀的图片。初值为1，根据已确定为背景的像素点动态更新迭代：

其中b(i)为前(s-i)个背景像素点的灰度值。

步骤2：区域由感染源感染

当找到感染源(ivirus，jvirus)后，算法开始检测感染源的八邻

域的像素点，当检测到某一邻域像素，若满足准则：

则将该八领域的像素点(ivirus+k，jvirus+l)感染，即令g(ivirus+k,jvirus+l)=0。

步骤3：将第二步的被感染像素点作为下一轮的感染源，每个感染源均对其八邻域中满足条件（2）的像素点感染，所感染的个体又作为下一轮感染的感染源，继续感染，直到某一轮的被感染的像素数为0。

步骤4：检测是否遍历完整个图像，若没有，则继续寻找下一个区域的第一个被感染的像素点步、第三步操作，直到遍历完整个图像，完成图像的分割与目标的标记。

2 算法实现

为了实现算法，笔者在VC++6平台上编程实现，首先需要定义两种数据结构：

struct OBJECT//表示个体

{

int i;//表示对象的纵坐标

int j;//表示对象的横坐标

unsigned char vPixel;//表示对象的像素值

}；

Struct AREAINFO//表示区域

{

OBJECT m_VirusObj;//区域感染源

int m_AreaSize;//区域大小

int m_AreaNO;//记录区域的编号}；

在算法开始前首先定义数组：

OBJECT m_VirusObj[a];//本轮感染源个体

OBJECT m_InfectedObj[a];//本轮被感染个体

AREAINFO m_AreaInfo[b];//记录区域的信息

同时定义3个变量：

int m_VirusObjNumber=0;

int m_InfectedObjNumber=0;

int m_AreaNumber=0;

其中，a，b的取值可根据实际情况来取，确保每一轮参与感染与被感染的对象数目小于a以及图像中的连通区域数目小于b。每一轮感染前，m_InfectedObjNumber清零，且在感染过程中，每感染成功一个个体时该变量加1。

图2为算法具体流程图。

图2 程序流程图Fig.2 Program flow chart

按照流程图的感染过程部分代码如下：

int CInfectingAlg::algCalculating(…)//感染算法主函数

{

//定义变量，初始化各个参数

……

for(int i=5;i

{

for(int j=5;j

{

if(pCurFrameData[i*widthstep+j]==0)//当前个体已被感染，则继续检测下一个个体

{ j+=vDitch;

continue;

}

if(pCurFrameData[i*widthstep+j-vDitch]!=0)//检测当前点的左vDitch个个体是否已被感染

{ if (pOriFrameData [i*widthstep+j]-

pOriFrameData[i*widthstep+j-vDitch]>=bVirusFeather)

//根据感染源判据判断区域感染源并感染

{ nSeedx=j;

nSeedy=i;

OnInfectedProcess(…);//感染过程

}

……

}

……

j=j+j_Jump;

}i=i+i_Jump；

}

return m_InfectedAreaNumber;

}

3 实验结果及分析

在奔腾4处理器，主频为1.86 GHz的处理器上执行算法，分别采用本文所述分割算法与传统阈值分割法处理大小为如图3所示640×480的光线不均匀图片。两种算法的分割结果比较如图4所示。

图3 原图像Fig.3 Origin image

图4 算法结果Fig.4 Algorithm processing result

图中（a）为本文算法分割的结果，（b）为传统阈值分割算法分割的结果。由实验结果比较可以看出，两种目标分割算法所用的时间均不超过1ms，但本文所述分割算法分割出的目标轮廓清晰，噪声少，并且保持原有目标形状；而传统阈值分割算法由于图片亮暗不均，无法选取一个全局最优阈值，从而导致部分目标轮廓无法被分割出来，造成信息丢失，影响后续处理和应用。因此，对于亮暗不均匀的药片图片处理，本文算法较传统阈值分割算法更优，同时除了具有目标分割功能之外，本文算法同时还可以标记每一个目标，如表2所示。

表2为标记的图像区域信息，记录了各个目标区域的区域大小和生长点坐标。

4 结论

通过模拟生态中的病毒感染过程，提出一种基于SRG的快速图像分割算法。从算法复杂度来看，该算法摒弃过多的数学计算，而以比较代替；从算法效率来看，该算法执行周期短，效率高，适用于序列图片中的实时处理；从智能程度来看，该算法能根据光照变化做出一定的反应补偿，能够对亮暗不均的图片进行目标分割及标记，对实时图像处理分析具有较大的意义。

表2 区域信息记录表Tab.2 Area Information table

[1]Frank YS,CHENG Shou-xian.Automatic seeded region growing for color image segmentation[J].Image and Vision Computing,2005,23(10):877-886.

[2]FAN Jian-ping,ZENG Gui-hua,Body M.Seeded region growing:An extensive and comparative study[J].Pattern Recognition Letters,2005,26(8):1139-1156.

[3]Takanashi T,Shin J.Color image segmentation based on region growing algorithm[J].Jou-rnal of Convergence Information Technology,2012,7(16):152-160.

[4]WANG Jia-nan,KONG Jun,LU Ying-hua.A region-based SRG algorithm for color image segmentation[J].Proceedi-ngs of the Sixth International Conference on Machine Learning and Cybernetics,2007(3):1524-1547.

[5]鲁宏伟，文燕.区域生长法在PCB元件分割中的应用[J].小型微型计算机系统，2007,28(8):1489-1491.LU Hong-wei,WEN Yan.Region growing algorithm in PCB element segementation[J].Journal of Chinese Computer Systems,2007,28(8):1489-1491.

[6]程明，黄晓阳，黄绍辉，等.定向区域生长算法及其在血管分割中的应用[J].中国图像图形学报，2011（1）：44-49.CHENG Ming,HUANG Xiao-yang,HUANG Shao-hui,et al.Directional region growing algorithm and its applications in vessel segm entation[J].Journal of Image and Graphics,2011(1):44-49.

[7]孔俊，王佳男，谷文祥，等.基于区域的自动种子区域生长法的彩色图像分割算法[J].东北师大学报：自然科学版，2008,40(4):47-51.KONG Jun,WANG Jia-nan,GU Wen-xiang,et al.Automatic SRG based region for color image segmentation[J].Journal of Northeast Normal University：Natural Science Edition,2008,40(4):47-51.