细菌觅食算法优化归一化准则的彩色图像分割

·信息科学·

细菌觅食算法优化归一化准则的彩色图像分割

周逊，郭敏，马苗

(陕西师范大学 现代教育技术教育部重点实验室/计算机科学学院, 陕西 西安710062)

摘要：为了求解彩色图像分割问题,采用一种基于离散细菌觅食算法优化归一化准则的彩色图像分割方法。引入模糊C均值聚类算法对图像预处理,降低算法维度;同时用细菌觅食优化算法求解Ncut的最小值,提高了算法的稳定性和收敛速度;通过最优个体菌得到分割结果。实验表明,该方法能够较好地分割图像,优于SM算法和遗传算法处理问题的分割效果,且耗时少。

关键词：模糊C均值聚类;归一化划分;细菌觅食优化算法;彩色图像分割

收稿日期：2014-03-11

基金项目：国家自然科学基金资助项目(10974130);陕西省青年科技新星基金资助项目(2011kjxx17);陕西师范大学研究生培养创新基金资助项目(2013CXS045);中央高校基本科研业务费专项基金资助项目(GK20145007)；陕西省重点科技创新团队基金资助项目(2014KTC-18)；陕西师范大学学习交叉学科培育计划基金资助项目

作者简介：周逊,男,江苏扬州人,从事图像处理,模式识别研究。

通讯作者：郭敏，女，江苏镇江人，从事信号处理，模式认识研究。

中图分类号：TP391

Color image segmentation based on bacterial foraging

optimization and normalized cut algorithm

ZHOU Xun, GUO Min, MA Miao

(Key Loboratory of Modern Teaching Technology, Ministry of Educational/

School of Computer Science, Shaanxi Normal University, Xi′an 710062， China)

Abstract:In order to solve the problem of color image segmentation, a method based on bacterial foraging optimization and normalized cut algorithm was proposed. In order to solve the problem of premature convergence, introduced fuzzy C-means dealing with color image for reducing the algorithm dimension; meanwhile the bacterial foraging optimization algorithm was introduced to minimize normalized cut, so the stability and convergence speed of algorithm was improved; then segmentation result by the optimal individual bacterium was got. Experimental results show that the method achieves a better segmentation result compared with SM algorithm and genetic algorithm, and consumes less time.

Key words: fuzzy C-means; normalized cut; bacterial foraging optimization algorithm; color image segmentation

图像分割是利用灰度、颜色、纹理、形状等信息按照一定标准从图像中分离出感兴趣目标的技术和过程,是图像理解、图像分析、模式识别等领域中首要解决的关键问题之一。近年来基于图论的图像分割[1-3]成为图像分割算法领域的一个热点,这类方法将整幅图像看作一幅无向带权图,图像中每一个像素对应图中一个节点,边上的权值代表像素的近似关系,利用最小剪切准则得到图像最佳分割。其中Shi和Malik提出的normalized cut准则[4-5]是一种规范化的准则,它综合考虑分割后子图的内部相似度和子图之间的相似度,有效避免了出现歪斜分割区域。

基于图论的图像分割以像素点之间的相似度构造权值矩阵,权值矩阵规模较大,为减少计算耗时,文献[6]建立概貌细节灰度级矩阵模型,相比以像素点之间的相似度建立权值矩阵规模较小,但以灰度构造矩阵算法维度仍较大。文献[7]使用K均值聚类将像素的灰度值划分为K类,对图像进行了预处理。文献[8-9]使用分水岭算法将图像划分为若干区域,有效降低了算法维度,但当前景和背景区别不大时,容易造成过分割。

预处理后的图像计算复杂度降低,但最小化Ncut值仍是NP难问题。Shi和Malik将问题转化为求解特大矩阵的第二小特征值[5],得到了Ncut值的近似解。文献[10]引进智能优化算法优化求解Ncut最小值,智能优化算法通过迭代寻优,能够较好地分割图像,但文献构造的仍是像素级的矩阵,算法非常耗时。另外,归一化准则在灰度图像的分割中应用已经很广泛,但在彩色图像的分割中仍不常见[11-12]。

本文全面考虑到图像的局部和全局信息,先对彩色图像的R，G，B3个信道分别作模糊C均值预处理[13],综合3个通道预处理得到的信息将图像划分为n块最大相似区域,然后构造区域级的权值矩阵,降低了算法的维度,再将Ncut准则作为适应度函数,Ncut值作为适应度值,通过二进制离散细菌觅食算法寻优求解Ncut的最小值,将得到的最优二进制位置映射回原图对图像进行分割。

1相关算法理论

1.1Normalized cut准则

无向带权图G=(V,E),节点集合V对应于图像中的每个像素点;连接节点边的集合为E,每个边有权值ω(i,j),ω(i,j)表示像素i和像素j之间的相似度。通过删去某些边,将图分为两个非连接性点集A，B,使得A∪B=V,A∩B=∅,被删去边的权值总和定义为这两个部分的不相似度,图论中称为割cut,如下公式所示

(1)

其中,ω(i,j)为连接节点i与节点j的权值,表示为

ω(i,j)=

(2)

使公式(1)的值达到最小值即为最小割,最小割能够得到最小的分割值,但容易划分出孤立点。

NormalizedCut克服了这种缺点,提出了一种规范化的分割方法,描述如下

(3)

这里,asso(A,V)表示A中节点与图G中所有节点之间的联系程度,同理，asso(B,V)表示B中节点与图G中所有节点之间的联系程度。可以看出Ncut值越小,划分的结果越好。

1.2SM算法

Shi和Malik提出的谱聚类算法(SM算法)求解Ncut值,将最小化Ncut值转化为矩阵求解形式[4]

(4)

上面的形式是Rayleigh商数,将y松弛到连续域[-1,1],求解最小值便转化为求解矩阵的特征方程(D-W)y=λDy。此特征方程的解就是问题的实值解,显然,最小特征值为零,因此第二小特征值对应的特征向量满足规范约束,然后使用阈值将特征向量分为两部分,作为分割结果。

1.3遗传算法

遗传算法GA(genetic algorithm)是一种自适应全局搜索优化算法,采用二进制编码,一般通过选择、交叉、变异这3种模式来改变个体和种群,在许多领域得到了应用。

1.4细菌觅食算法

细菌觅食算法BFO(bacterial foraging optimization algorithm)是K.M.Passino[14]根据大肠杆菌的生存觅食原理于2002年提出的一种新型群智能优化算法。BFO求解优化问题的一般步骤为:产生初始解群,计算适应度函数值,利用菌群趋化、繁殖、迁移3种行为实现对优化问题的求解。

1.4.1趋化行为在细菌的觅食过程中,细菌向营养密集的地方聚集的行为,主要分为翻转和游动两种方式。设个体菌的当前状态为Xi,随机朝任意方向移动一步即翻转一次。若新位置的营养度较低则保持Xi状态不变;若新位置Xi′所在位置的营养度较高,则将Xi更新为Xi′,然后从状态Xi′接着翻转,直到状态Xik′处的营养度不再增高或者达到最大移动步数Step则停止移动。趋化方式使得细菌具有局部搜索能力。

1.4.2繁殖行为将所有个体菌所在位置的营养度排序,营养度较低之处的细菌则移动到营养度较高的位置,实现细菌的繁殖。若个体菌Xi处的营养度较低,它会向营养度较高的Xj移动。这一方式体现了自然界优胜劣汰的生存规则,加快了菌群的收敛速度。

1.4.3迁移行为在趋化和繁殖行为之后,每个个体菌都有一定概率迁移到搜索空间的任意位置。个体菌的状态Xi有一个概率Ped使其的状态发生变化,迁移行为使得种群多样化,防止算法陷入局部最优。

2本文算法

基于图论的图像分割是二元标号优化问题,需要将细菌觅食算法离散化。本文首先对图像进行FCM预处理,以得到的n块最大相似区域构造权值矩阵,然后用二进制离散细菌觅食算法优化求解最佳分割的二进制状态。

2.1图像预处理

真彩色图像包含丰富的颜色信息,一般认为每个像素由R，G，B 3个分量组成。考虑到以像素构造的权值矩阵计算量大,为减少时间复杂度,本文对彩色图像的R，G，B 3个通道分别作模糊C均值聚类,每个信道分别聚类为具有c个最大相似区域的图像IR，IG，IB,在保证识别每个像素的前提下取IR，IG，IB的最大交集,得到具有n块最大相似区域的图像。以n块最大相似区域构造权值矩阵,缩小了权值矩阵规模,在保证识别图像基本信息前提下,降低了归一化分割算法的求解规模。

2.2细菌觅食算法的离散化

基于图论的图像分割是二元标号问题,因此将细菌觅食算法离散化后求解最优分割是可行的。离散细菌觅食算法寻优便是将预处理得到的n块最大相似区域整合成内部相似最大、外部相似最小的两部分,最大相似区域的个数即为问题的维度D。

将细菌觅食算法离散化,Xi(xi,1,xi,2,…,xi,D)表示第i个个体菌在D维空间里的位置,xi,k(k=1,2,…,D)取值为0或1,具体标准化方法如下:

(5)

重新定义细菌觅食算法的行为操作准则,在0-1状态下进行算法的优化,至此完成对细菌觅食算法的二进制离散化。

2.3离散细菌觅食算法的参数选取

离散细菌觅食算法参数较多,参数的选取直接影响图像的分割效果。本文选取细菌总数N=20,趋化次数Nc=5,繁殖次数Nre=2,迁移次数Ned=2,其他几个重要参数及离散化定义如下:

1)营养度。营养度是菌群觅食行为的参考依据。式(3)即为营养度的评价标准,通过计算Ncut值确定细菌的适应度值,从而得到细菌所在位置的营养度,可以看出Ncut越小,指导分割图像的效果越好。

2)朝任意方向移动一步。本文定义朝任意方向移动一步为个体菌的二进制状态Xi的某一维随机变异,0变为1,1变为0。

3)最大移动步数。当细菌趋化时达到了最大移动步数强制终止本次趋化,本文选择最大移动步数为Step=7。

4)迁移概率。迁移概率决定了算法全局搜索能力,概率过大则容易盲目搜索,反之则容易局部收敛,本文选择迁移概率Ped=0.25。

2.4算法流程

结合上述分析,离散细菌觅食算法优化归一化准则的彩色图像分割算法流程如图1所示。

图1　细菌觅食算法优化归一化准则的彩色图像分割流程图 Fig.1　Flow process diagram of the color image segmentation based on bacterial foraging optimization and normalized cut algorithm

1)对彩色图像的3个信道通过模糊C均值聚类分别得到具有C块最大相似区域的图像IR，IG，IB,综合3个通道的聚类信息生成n块最大相似区域,然后将每个区域的像素R，G，B均值作为区域像素值构造权值函数,构造无向带权图。

2)将Ncut值作为适应度函数,利用二进制离散细菌觅食算法对其进行寻优,通过个体菌在觅食行为中不停更新自身得到最优营养度位置及最优个体菌的二进制状态。

3)将最优个体菌的二进制状态映射回原图,指导划分图像,完成对图像的分割。

3实验结果与分析

实验平台为Microsoft Windows 7 Professional, CPU:Intel Core 2.2 GHz,RAM:2GB.选取大小均为256×256的彩色图像进行测试。实验结果分别如图2～图4所示。

图2　图像elephant分割效果图 Fig.2　Segmentation result of the photo elephant

图3　图像pilot分割效果图 Fig.3　Segmentation result of the photo pilot

图4　图像bird分割效果图 Fig.4　Segmentation result of the photo women

由上述图像可见,当图像中颜色的变化幅度比较大,细节较多,颜色信息比较丰富,尤其前景和背景差别不大时,运用SM算法和遗传算法分割效果不理想。例如图2(b)中,SM算法对前景的辨别能力不强,将较大的大象身体区域分为背景。图3(b)中,SM算法将飞机顶部分割错误,飞行员的轮廓及影子也未能划分好。图3(c)中,遗传算法将较大区域划分错误。图4(b)与4(c)中,SM算法和遗传算法将对鸟儿和树干的轮廓都未能较好的划分,混入人们感兴趣的目标之中。而运用细菌觅食算法优化之后,上述情况能够有效地避免。因为SM算法求解的特征向量对应一个分割,细菌觅食算法每个个体菌的二进制状态都相当于一个特征向量,相对于遗传算法,细菌觅食算法的寻优策略要优于遗传算法的,在迭代中过程中优化得到的结果优于SM算法和遗传算法。

由表1-3还可以看出,传统Ncut算法与本文算法耗时区别不大,都能在较短的时间内分割出图像,满足实时性需求,这是由于本文对图像进行了预处理,降低了问题的维度。细菌觅食算法求解的Ncut值都比传统Ncut算法要小,说明本文算法优于传统Ncut算法,能够较好地分割彩色图像。

表1　图像elephant的分割数据

表2　图像pilot分割数据

表3　图像bird分割数据

4结语

本文基于图论的图像分割思想,提出了一种将细菌觅食优化算法与归一化准则相结合的彩色图像分割方法。该方法利用菌群的觅食行为?在搜索空间中寻找能使Ncut值最小的个体菌,再将最优个体菌二进制状态映射回无向带权图,得到对图的最优划分。由于本文预处理方法考虑的是图像的局部信息,normalized cut能够有效地把握全局信息,细菌觅食算法在求解NP-hard问题上是有效且快速的,通过理论分析和实验仿真表明,本文提出的方法综合了细菌觅食算法和归一化分割准则的优点,能够快速、有效地指导彩色图像分割。

参考文献：

[1]LI X B, TIAN Z. Optimum cut-based clustering[J]. Signal Processing, 2007, 87(11):2491-2505.

[2]ZHANG M, ALHAJJT R. Improving the graph-based image segmentation method[C]//Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence Arlington, Arlinglon:IEEE Press, 2006: 617-624.

[3]廖武忠. 基于图论理论的图像分割算法的研究[D]. 重庆:重庆大学,2006.

[4]SHI J B, MALIK J. Normalized cuts and image segmentation[C]//Proc IEEE CS Conf Computer Vision and Pattern Recognition, 1997: 731-737.

[5]SHI J B, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis Machine Intelligence, 2000, 22(8): 888-905.

[6]唐艳亮,吴一全,吴诗婳,等. 基于NSCT和Tsallis熵的SAR图像快速分割方法[J]. 信号处理,2011,27(8):1133-1139.

[7]吴永芳,杨鑫,徐敏,等 基于K均值聚类的图割医学图像分割方法[J]. 计算机工程,2011,37(5):232-234.

[8]杨静,陈昭炯. 结合分水岭的Mean-Shift 图像分割新算法[J]. 小型微型计算机系统. 2009,30(12):2493-2496.

[9]卢志茂,许晓丽,范冬梅,等. 二次分水岭和Ncut相结合的彩色图像分割算法[J]. 华中科技大学学报, 2011,39:95-98.

[10]翟艳鹏,郭敏,马苗, 等. 遗传算法优化归一化划分准则的图像分割[J]. 计算机工程与应用, 2010,46(33):148-157.

[11]TAO Win-bing, JIN Hai, ZHANG Yi-min. Color image segmentation based on mean shift and normalized cuts[J]. IEEE Transactions on Systems, and Cybemetics, 2007, 37(5): 1382-1389.

[12]李南希. 基于图论的彩色图像分割方法研究[D]. 广州:华南师范大学,2007.

[13]关庆,邓赵红,王士同. 改进的模糊C-均值聚类算法[J]. 计算机工程与应用, 2011,47(10):27-29.

[14]PASSION K M. Biomimicry of bacterial foraging for distributed optimization and control[J]. IEEE Control Systems Magazine, 2002, 22(3):52-67.

(编辑曹大刚)