基于ACS－FCM算法的图像分割研究

1  引言

图像分割是把图像分成各具特性的区域并提取出感兴趣目标的技术和过程[1]。数字图像处理问世不久，人们就开始了对图像分割技术的研究，并取得了较大的进展，但由于它的复杂性，有许多问题仍然没有得到很好的解决。图像分割的方法有成百上千种，但尚没有一种适用于所有图像的通用分割算法。绝大多数算法都是针对具体问题而提出的，因此人们仍然在不断的研究新的，更有潜力的分割算法，以求实现更好的分割效果。

图像分割已广泛应用于工业自动化、在线产品检测、生产过程控制、文挡图像处理、遥感和生物医学图像分析、保安监视、以及军事、体育、农业工程等。概括来说，在各种图像应用中，只要对图像目标进行提取、测量等都离不开图像分割。近年来，分割技术在对图像的编码中也起到了越来越重要的作用，如国际标准mpeg-iv中的模型基/目标基编码等都需要基于分割的结果。此外，对医学图像的分割是图像分割中最重要的一个应用领域。

目前，已提出很多种类型的分割算法，大致可以分为基于边缘检测的方法和基于区域的方法[2~3]。在实际应用中，从不同的理论角度提出了许多方法，这些方法中主要可划分为三种类型：阈值型、边缘检测型和区域跟踪型。

本文提出将acs-fcm算法用于图像分割，将模糊c均值聚类算法(fcm)和蚁群系统算法(acs)结合起来,并使用matlab进行了仿真实验。

2  蚁群算法

蚁群算法是受自然界蚂蚁觅食过程启发而产生的一种集群算法, 由意大利学者dorigo 于1991 首次系统地提出[4]。蚁群算法是从对蚁群行为的研究中产生的。为了说明其基本原理，下面对人工蚁群进行计算机仿真，仿真结果如图1所示。

在图中a点为食物源，而b点为蚂蚁巢穴，蚁群正往返于食物与巢穴之间，其路径为一条直线，如图1(1)所示。假设在某一时刻在蚂蚁的路径中突然出现了一些障碍物，原有的路径被切断，这样，从a到b的蚂蚁就必须决定应该往左还是往右边走，如图1(2)中所示。而从b到a的蚂蚁也必须选择一条路径。这种决定会受到各条路径上以往蚂蚁留下的信息激素物质浓度的影响，如果向右的路径上的信息激素物质浓度比较大，那么向右的路径被蚂蚁选中的可能性也就比较大一些。



图1  人工蚁群运动图

障碍物出现后，对第一只从a到b的蚂蚁而言，因为没有信息素物质的影响，所以它选择向左或者向右的可能性是一样的。以从a点到b点的蚂蚁为例，由于路径acb比路径adb要短，因此选择acb路径的蚂蚁会比选择adb的蚂蚁早到b点。此时，从b点向a点看，指向路径bca的信息素浓度比bda大。因此，从下一时刻开始，从b点到达a点的蚂蚁选择bca路径比选择bda路径的可能性要大。从而使路径bca上的信息激素物质浓度与路径bda上的信息素浓度的差变大。而信息素物质浓度差变大的结果就是选择bca路径的蚂蚁进一步增加，这又导致信息激素物质浓度进一步加大。这就是巢穴到食源的最短路线，如图1(3)，蚂蚁根据线路上留下信息素浓度的大小，确定在路线上移动的方向，蚁群向信息素浓度重的线路集聚的现象称为正反馈。蚂蚁算法正是基于正反馈原理的启发式算法。

在自然界中，蚁群的这种寻找路径的现象就表现为一种正反馈的过程，而这一过程应用于优化领域便产生了人工蚁群算法，整个系统也可以称为蚁群系统(ant system)[5],而那些只具备了简单功能的工作单元将被视为“蚂蚁”。那么，上述蚂蚁寻找路径的过程也可以用于解释人工蚁群的寻优过程。

2  蚁群算法与模糊c均值算法的结合——acs-fcm算法

模糊c均值算法(fcm)简单、收敛速度快，但受初始聚类中心影响较大，容易陷入局部极小，而蚁群算法是一种随机搜索的全局优化算法，如果将蚁群算法和fcm相结合[6~7]，则可以充分发挥蚁群算法的全局优化特征和fcm算法的局部寻优能力，下面对这种混合式算法进行探讨。

蚂蚁在从食物源到蚁穴并返回的过程中，能够在它所走过的路径上分泌一种称之为“信息素”的化学物质，在自己所经过的路径上形成信息素轨迹，蚂蚁通过感知这种物质的存在及强度来指导自己的运动方向，蚂蚁倾向于朝着信息强度高的方向运动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象，某一路径上走过的蚂蚁越多，该路径上的信息素越强，从而使得选择这条路径上的蚂蚁增多。蚂蚁个体之间正是通过信息素的物质进行交流而达到搜索事物的目的。分析发现自然界中蚁群的觅食行为是一个不断聚类的过程，食物源就是聚类的中心。将每个待聚类数据样本视为具有不同属性的蚂蚁，蚂蚁觅食的过程可看作是蚂蚁不断向聚类中心聚类的过程，聚类中心是蚂蚁所要寻找的食物源。数据样本集xi=(xi1,xi2,…,xim), i=1,2,…,n。初始时刻，各条路径上的信息量相等，设r为聚类半径，数据样本与聚类中心间的加权欧式距离为：

   (1)

各路径上的信息素计算公式为

(2)

第i个蚂蚁选择聚类中心cj的概率为

  (3)

其中，式(1)中pk为加权因子，加权因子可根据各属性对聚类的影响设定且须满足约束条件:∑pk=1, pk≥0。式(3)hij=1/dij为能见度因数，反映蚂蚁i在选择聚类中心cj的受启发程度。a和b为两个参数[8]，分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。随着蚁群的移动，各路径上的信息素在积累的同时，也会随着时间的流逝而挥发。一次聚类完成之后，要对各路径上的信息素进行更新，采用的信息素更新方式为[page]

   (4)

3  acs-fcm算法图像分割

将上述蚁群聚类算法应用于图像分割中，可以将每只蚂蚁看作具有若干特征的像素[9]。而图像中像素灰度、邻域均值灰度、梯度、及区域纹理、局部能量等均为其重要分割特征，在一幅图像中，灰度、邻域均值灰度、梯度表现了目标、背景、边缘及噪声的特点。在此算法中，每只蚂蚁是以灰度、邻域均值灰度、梯度为特征的三维向量。

如果采用基本蚁群聚类算法，那么随着蚂蚁的运动，迭代到一定次数后，蚂蚁容易过早限于停滞，蚁群集中在少数几条路径上，如果要得到全局最优解，需要对信息素更新方式进行改进[10]，避免某些局部最优路径上信息量的增长过快，在加快收敛和防止早熟现象之间取得一个较为合理的平衡点。可按式(5)更新蚂蚁到聚类中心的信息素强度

 (5)

式中：信息量调节系数a为[0,1]间的一个参数，与式(4)中的r系数相比，可以在对本条路径t+1时刻信息量更新的同时兼顾时刻的初始信息，避免信息量的过快增长。对上述式中信息素更新方式做进一步的改进

   (6)

 (7)

式中：lave为一次聚类结束后的路径平均值，di为每只蚂蚁所走的路径长度。具体算法描述如下：

步骤1  建立模型：

将像素点视为蚂蚁，聚类中心视为食物源，则聚类的过程即蚂蚁觅食过程。

步骤2  参数初始化：

给定数据样本集xi=(xi1,xi2,…,xim), i=1,2,…,n, 设置a, b,tij, nc等参数的初始值，设置初始聚类中心ci，给出一个初始蚁群分配方案，并计算数据样本与聚类中心间的加权欧式距离:

步骤3  蚂蚁的移动：

对每一只蚂蚁 k(k =1, 2, …, m)，根据转移概率为其选择一个新的节点，并将蚂蚁移动到此节点。

步骤4  更新：

一次蚁群聚类完成后，更新各类的聚类中心ci，重新计算样本点到该新的聚类中心的加权距离。然后使用更新规对这两个聚类中心之间的路径上的信息素浓度进行更新。

步骤 5  目标函数及终止：

计算目标函数：

若循环次数大于规定的次数，停止运行并输出分割所得图片，否则转步骤3。

4  仿真结果分析

本实验测试平台为genuine intel(r)2140@1.60ghz，1g内存，windowsxp，在matlab 7.0环境下仿真得到。本实验中参数初始参数设置为：

a=0.40；b =3；r =0.95；(聚类半径)g =90；nc=500。



原始图像   canny算子边缘检测

fcm算法分割   本文算法分割

图2  红细胞图片的分割效果图[page]



原始图像 canny算子边缘检测

fcm算法分割本文算法分割

图3  lenna图片的分割效果图

图2，图3所示依次为红细胞，lenna图片的原始图像，canny算子边缘检测，fcm算法以及本文算法的分割结果。

从图中可以看出，canny算子能够把图像中纹理细节及灰度值较低的很多区域都能较好的检测出来，但不能区分不同的灰度；fcm算法可以把图像大致分割出来，但对纹理细节的处理不是很好；而acs-fcm算法分割效果比较显著，既可以把图像中纹理细节以及灰度较低部分很好的分割出来，又可以把灰度变化情况表示出来。因此改进后的acs-fcm算法是一种比较有效的图像分割方法。

5  结束语

本文将acs-fcm算法应用到图像分割中，并在图像分割中取得了可观的效果。在实验中与常用的canny边缘提取算子和fcm算法的分割效果进行对比得知，基于acs-fcm算法的分割效果较之有明显的改进，但在实际应用中，针对不同的图形，不同的算法的分割效果各有优劣之处， 能否将其它新的混合式算法应用于图像分割中，也是值得我们进一步研究的问题。


参考文献

[1] rafael c.gonzalez,richarde.woods,steven l.eddins.数字图像处理[m]. 电子工业出版社,2007:285-320.

[2] 黄长专,王彪,杨忠. 图像分割方法研究[j]. 计算机技术与发展,2009,19(6):76-79.

[3] 康晓东,何丕廉,刘玉洁等.基于蚁群算法的医学图像分割研究[j]. 计算机应用研究, 2008,(25)9:2853-2855.

[4] eric bonabeau,marco dorigo, guy theraulaz. swarm intelligence from natural to artificial systems[m]. oxford university,1999.

[5] 赵霞,田恩刚. 蚁群系统(acs)及其收敛性证明[j]. 计算机工程与应用,2007,43(5):67- 70.

[6] h azzage,c guinot,g venturini.how to  use ants for hierarchical clustering[c].in: fourth international workshop on ant colony cptimi-zation and swarm intelligence,brussels,belgium,lncs 3172,2004:350-357.

[7] h azzag,n monmarche,m slimance et al.anttree:a new model for clustering with artificial ants [c]. in:ieee congress on evolutionary computation,canberra, australia,2003:8-12.

[8] 胡新荣,李德华,王天珍.基于蚁群优化算法的彩色图像颜色聚类的研究[j].小型微型计算机系统,2004:25(9);1641-1643.

[9] 陈柒伍,陈　静,徐　丹.基于蚁群聚类算法的彩色图像量化方法[j].云南大学学报( 自然科学版),2007,29(s2):219-223.

[10] 叶志伟,郑肇葆.蚁群算法中参数α、β、ρ设置的研究椧訲sp问题为例[j].武汉大学学报(信息科学版),2004,29(7):597-601.