第5卷第1期 智能系统学报 Vol.5 No.1 2010年2月 CAAI Transactions on Intelligent Systems Feh.2010 doi:10.3969/j.issn.16734785.2010.01.014 改进的模糊C-均值算法在医学图像分割中的应用 程显毅，巩向普 (南通大学计算机科学与技术学院，江苏南通226019) 摘要：针对随机选取聚类中心易使得迭代过程陷入局部最优解的缺点，提出了一种混合优化蚁群和动态模糊C均 值的图像分割方法，该方法利用蚁群算法较强处理局部极值的能力，并能动态确定聚类中心和数目.针对传统的分 阶段结合遗传算法和蚁群算法的策略存在收敛速度慢，聚类精度差的问题，提出在整个优化过程综合遗传算法和蚁 群算法，并在蚁群算法中引入拥挤度函数，利用遗传算法的快速性、全局收敛性提高了蚁群算法的收敛速度，同时利 用蚁群算法的并行性和正反馈性提高了聚类的精确度.最后将该算法应用到医学图像分割，对比实验表明，混合算 法具有很强的模糊边缘和微细边缘分割能力 关键词：蚁群算法；医学图像分割；模糊C均值聚类；遗传算法 中图分类号：TP391文献标识码：A文章编号：16734785(2010)01008005 An improved fuzzy C-means algorithm for segmentation of medical images CHENG Xian-yi,GONG Xiang-pu (School of Computer Science and Technology,Nantong University,Nantong 226019,China) Abstract:Stochastic selection of a clustering center would cause the iterative process to become trapped in a local extremum.To overcome this image segmentation problem,a hybrid method was proposed.It combined an ant colo- ny algorithm with dynamic fuzzy clustering analysis.Thus the superior ability of the ant colony algorithm became a- vailable for dealing with local extrema.The resulting algorithm dynamically determined the number of clusters as well as clustering centers.Within the optimization procedure,we introduced a crowd degree function to improve the convergence rate.In addition,the parallelism and positive feedback effect of ant colony algorithm were employed to increase clustering precision.The proposed algorithm was used in the segmentation of medical images.A series of comparative experiments showed that the algorithm has improved ability to detect fuzzy or thin edges. Keywords:ant colony algorithm;medical image segmentation;fuzzy C-means clustering;genetic algorithm 医学图像是反映人体生物组织的复杂图像，图 在计算机辅助下，精确地、自适应地分割提取影像中 像信息量大、处理困难.医学图像分割是医学图像研 包含的信息来满足医学图像处理的要求，是图像分 究的一个关键环节，对临床医学的应用和发展有着 析专家需要解决的关键问题[6]」 巨大的实用价值.由于医学图像本身分辨率、对比度 本文结合混合遗传算法、蚁群算法和模糊C-均 较低，以及固有噪声的影响，使用传统的图像分割方 值算法的优点，在蚁群算法中加人了拥挤度函数，来 法（如蚁群算法、遗传算法2、粒子群算法[3]、模 增加蚁群算法遍历寻优的能力.一方面，利用蚁群算 糊C-均值算法4、Snake51等)，很难达到要求.如何 法较强处理局部极值的能力，可以动态确定聚类中心 和数目，有效地克服FCM算法对初始化的敏感；另一 收稿日期：20080901. 基金项目：国家自然科学基金资助项目(60702056) 方面，将传统的分阶段结合遗传算法和蚁群算法的策 通信作者：程显毅.E-mail:xycheng@atu.cdu.cn. 略修改为在整个优化过程混合遗传算法和蚁群算法
第1期 程显毅，等：改进的模糊C均值算法在医学图像分割中的应用 ·81 实验表明该混合算法可以准确地进行医学图像分割 S={X,|d≤T,s=1,2,…j,j+1,…,W. 1蚁群算法与图像分割 (2) 式中：ng为启发信息，α、B为常数，分别体现信息素 蚁群算法(ACA)是模拟蚁群行为的一种仿生 浓度与启发信息相对重要性.每只蚂蚁经过个时 算法.蚂蚁在行走过的路上释放一种特殊的分泌物， 刻完成一次循环后，对信息素浓度进行更新，即 称之为信息素(pheromone),蚂蚁就是通过这种激素 T&+m)）=pm,(0+召△r安 (3) 进行信息交流，它们趋向于走激素积累较多的路径， 找到最短路径的蚂蚁总是最先返回巢穴，从而在路 式中：p(0<p<1)表示原信息素浓度保留程度；△r 上留下较多的激素.因最短路上积累了较多的激素， 表示蚂蚁k在本次循环中在路径可上留下的信息素 选择该路径的蚂蚁就会越来越多，后来者选择该路 浓度.当蚂蚁k在本次循环中经过可，则△r=Q/L, 径的概率就越大.这样，蚂蚁群体行为表现出了一种 其中：Q为常系数；L表示蚂蚁k在本次循环中选择 信息正反馈现像.蚂蚁个体之间就是通过这种信息 的路径长度，如果蚂蚁k在本次循环中未经过则 交流寻求通向食物源的最短路径] △r=0. 图1给出了用蚁群算法分割图像的基本流程， 2改进的蚁群遗传混合算法 开始 传统的遗传算法蚁群算法的混合算法的基本思 设置参数，初始化 路是：算法前过程采用遗传算法，充分利用遗传算法 信息茶更新 的快速性、随机性、全局收敛性，其结果是产生有关问 评价蚁群 题的初始信息素分布：然后采用蚁群算法，在有一定 I 概率选择移动方向 初始信息素分布的情况下，充分利用蚁群算法的并行 满足终止 条件？ t:1=+1 性、正反馈性、求精解效率高等特点.但是这种方法并 g 没有把这2个算法真正融合在一起，使其贯穿整个的 输出最短路径 搜索过程0，本文的改进是让使遗传算法和蚁群算 图1蚁群算法的基本流程图 法混合作用于整个分割过程（如图2所示）. Fig.1 Basic flow chart of ant colony algorithm 2.1改变“信息素”更新策略 给定原始图像Xmxm,将每个像素X:看作是一 “信息素”更新机制的选择直接影响算法性能， 只蚂蚁，每只蚂蚁是以像素灰度和梯度为特征的二 本文的策略是：在每次搜索迭代过程中，局部地更新 维向量： 信息素，同时采取局部更新与全局更新相结合，增加 X=(xa,x2),i=1,2,…,N,N=nXm 了解的多样性，避免了早熟收敛 图像分割就是具有不同特征的蚂蚁搜索食物源的过 2.2在蚊群算法中引入拥挤度函数 程.算法先进行初始化，将各个路径的信息素置为 拥挤度函数为 0,即r(0)=0,聚类半径为r,统计误差为8等.计 4④=24)/分(0. (4) 算各路径上的信息素浓度T(t): 式中：Tg(t)表示t时刻样本k到i类路径上的信息素 Tg()= [1,dy<r; (1) 浓度.如果q,<8(t),则表示路径不太拥挤，蚂蚁选择 Lo,da r. 该路径从位置i转移到位置j;否则，表示该路径过于 式中：d为像素X:到代表点X之间的加权欧氏距 拥挤，蚂蚁则在可行邻域内重新随机选择一条路径进 离.计算像素X到X的转移概率： 行转移.其中，6(t)表示t时刻的拥挤度阈值，并按 p）=()(/re)a, 8(t)=1-eˉ“进行更新，c为阈值变化系数
82 智能系统学报 第5卷 ACD 初始化参数生成信总素初 始分布，将蚂蚁置于初始点 交叉所得路径是否 优于迭代最优路径？ 计算每只蚂蚁移动到下一结 点的概率并计算该路径的拥 挤度，根据概率选择移动蚂蚁 代 代递归 对交叉 归 最优的 进行信息素的局部更新 随机选 进行交叉操作 妈蚁赋 予“外 激素” 选出本次迭代巾承载本次 迭代最优路径信息的蚂蚁 蚂 进彳信总素的全局更新 是否与本次迭代 最优妈蚁经过相 同的路径？ 输出最优路径 N 图2改进遗传算法与蚁群算法结合流程图 Fig.2 Improved genetic algorithm and ant colony algorithm union flow chart (t)(t) 3 改进的蚁群遗传混合算法的模糊 Pu(t)=- ∑r(t)呢(e) C-均值聚类 S={X|d≤r,s=1,2,…,i,i+1,…,N}. 3.1基本思想 (6) 将待聚类数据视为具有不同属性的蚂蚁，每只 式中：S是蚂蚁k下一步可以选择的样本点的下标 蚂蚁具有W维特征矢量，聚类中心作为蚂蚁需要寻 的集合 找的“食物源”，蚂蚁在搜索时，不同的蚂蚁选择某 3)计算该路径的拥挤度q(t). 个数据元素是相互独立的. 9a(）=2ra(o)/Aa(0. 3.2算法步骤 在算法初期，拥挤度阈值选择接近于0的较小 1)计算蚂蚁信息素， 值，这样大多数蚂蚁都可以自主随机选择移动路线。 假定每个数据特征矢量为 如果某条路径信息素浓度很高，但该路径蚂蚁也很 X={Xk,k=1,2,…,n}, 多，则下一只蚂蚁可能不会选择该路径，而是进行随 Xk={x1,x2,…,n} 机选择，这可避免蚂蚁过早地集中在某局部极小的 它有n个输入样本，每个样本有m个特征.迭代次 位置，增加了算法遍历寻优的能力，防止蚂蚁因过早 数为N,聚类半径为r,统计误差为eo,各信息素 集结在某条信息素浓度较高的路径上而造成算法早 T(0)=0,初始中心为V;计算第k个样本和第i类 熟现象的出现，在一定程度上克服了局部极小解的 的距离d:=‖x-:‖.则蚂蚁在路径上的信息素 问题o」 由式(5)给出. 4)信息素局部更新 7s=,4s (5) TH(t+1)=pTu(t)+ATH(t,t +1). Lo,du r. 5)交叉操作 2)计算t时刻时蚂蚁k由：选择到：的概率 交叉操作是在迭代最优蚂蚁与随机选择的其他 P(t). 蚂蚁之间进行，也可以按概率群完成一次循环后，随
第1期 程显毅，等：改进的模糊C均值算法在医学图像分割中的应用 ·83 机选择的2只蚂蚁之间进行.还可以按概率P。(交 图5为利用本文的混合算法得到的图像分割结 叉概率)从整个蚁群随机地抽选一定数量的蚂蚁与 果，可以看出利用新的混合算法得到的分割图像轮 迭代最优蚂蚁之间进行交叉， 廓比较清晰，分割结果也很明显， 6)信息素全局更新， 随着蚂蚁的移动，各路径上信息量发生变化，经 过一次循环，各路径上信息量根据式(7)进行调整： Ta(t)=pT(t)(t-△t)+△T陆， △r&=Q/da (7) 式中：Q是一常量，表示蚂蚁完成一次路径搜索所释 放的信息素总量，然后计算新的聚类中心和样本点 (a)收缩期的左心室 (b)舒张期的左心室 到该新的聚类中心的距离。 图4FCM对左心室的分割结果 7)路径决策。 Fig.4 Segment results of left ventricle image using FCM 如果Pa（(t)≥Po,则x归并到：邻域，且令 m={Xld≤r,j=1,2,…,I, 其中，m:表示所有归并到：邻域的数据集合；否则， 计算下一个样本间加权欧氏距离。 m=名e 8)终止条件. (a)收缩期的左心室 (b)舒张期的左心室 计算D,=[三(-a)》P]以第i个聚类的 图5本文方法对左心室的分割结果 偏离误差及总体误差与总体误差8=名D,再判断 Fig.5 Segment results of left ventricle image using our method B≤e0是否成立.若成立，则输出聚类个数c;若不成 为了更直规地定量反应分割性能，对分割图像 立，则继续迭代 的敏感性、专一性和总体性能指标进行了统计， 4实验结果与分析 表1为统计结果。 表1医学图像分割性能对比 为了验证该混合算法的有效性和实用性，以处 Table 1 Performances of medical image segmented% 于扩张期和收缩期的左心室图像为例，分别用传统 指标 FCM方法 本文方法 的℃M聚类算法和提出的混合算法对图像进行分 敏感性 96.8 96.9 割研究.图3为左心室原始图像， 专一性 94.5 97.7 总体性能 97.4 97.7 5结束语 从实际应用的角度来讲，医学图像分割结果的 好坏直接影响对病人的诊断和治疗.传统的MC方 法存在聚类中心确定太随机，容易陷入局部极值的 (a)收缩期的左心室 (b)舒张期的左心室 缺点，使得分割图像的边界模糊.本文对FCM做了 图3左心室图原始图像 2点改进：一是将传统的遗传算法与蚁群算法分步 Fig.3 Left ventricle origin image 混合修改为在聚类的全过程混合；二是在蚁群算法 图4为采用传统的FCM聚类算法的分割结果， 中加入了拥挤度函数，实验表明改进的FCM方法对 可以看出在分割区域边界比较模糊，这是FCM聚类 医学图像分割得到了理想的效果.本文的分割图像 算法的局部收敛不足引起的， 都是基于二维的，对三维体数据图像直接进行分割
·84 智能系统学报 第5卷 以及医学图像的三维运动重建是一项很有意义的工 [7]程显毅，陈小波.基于多Aget的模式识别框架[J].智 作，未来的研究将致力于此方面的工作. 能系统学报，2006,1(2)：8993. CHENG Xianyi,CHEN Xiaobo.Frame of pattern recogni- 参考文献： tion based on multi-Agent[J].CAAI Transactions on Intel- [1]黄国瑞，王绪法，高宪斌.基于方向信息素扩散的蚁群优 ligent Systems,2006,1(2):89-93. 化算法[J].电子学报，2006,15(3)：447450. [8]程显毅，梁军，马首明.基于MAS的医学图像进化分 HUANG Guorui,WANG Xufa,GAO Xianbin.Ant colony 割算法的研究[J].南京大学学报：自然科学，2008,44 (5):503-511. optimization algorithm based on directional pheromone diffu- sion[J].Chinese Joumal of Electronics,2006,15 (3): CHENG Xianyi,LIANG Jun,MA Shouming.Evolutional 447450. algorithm of medical image segmentation based on a multi- [2]陈小波，程显毅.一种基于MAS的自适应图像分割方法 Agent system[J].Joumal of Nanjing University:Natural [J].智能系统学报，2007,2(4)：80-85. Sciences,2008,44(5):503-511. CHEN Xiaobo,CHENG Xianyi.An adaptive image segmen- [9]吴启迪，汪镭.智能蚁群算法及应用[M].上海：上海 tation technique based on multi-Agent system J].CAAI 科技教育出版社，2004：7892 Transactions on Intelligent Systems,2007,2(4):80-85. [10]修春波，张雨虹.基于蚁群与鱼群的混合优化算法[J]. [3]李旭苏，焦淑红，王立瑾.基于PS0和加权FCM的图像分 计算机工程，2008,34(14)：206-207. XIU Chunbo,ZHANG Yuhong.Hybrid optimization algo- 割算法[J小.应用科技，2008,35(4)：26-29， LI Xusu,JIAO Shuhong,WANG Liying.PSO and weighted rithm based on ant colony and fish school[J].Computer FCM based image segmentation algorithm[J].Applied Sci- Engineering,2008,34(14):206-207. ence and Technology,2008,35(4):26-29. [11]白杨，孙跃，王君，等.基于动态自适应蚁群算法 [4]杨立才，赵莉娜，吴晓晴.基于蚁群算法的模糊C-均值聚 的MRL图像分割[J].计算机科学，2008,35(12)： 226-230. 类医学图像分割[J].山东大学学报：工学版，2007,37 (3):51-54. BAI Yang,SUN Yue,WANG Jun,et al.Segmentation of YANG Licai,ZHAO Lina,WU Xiaoqing.Medical image MRI based on dynamic and adaptive ant colony algorithm segmentation of fuzzy C-means clustering based on the ant [J].Computer Science,2008,35(12):226-230. colony algorithm[J].Joumal of Shandong University:Engi- 作者简介： neering Science,2007,37(3):51-54. 程显毅，男，1956年生，教授、博士 [5]王科俊，郭庆昌.基于粒子群优化算法和改进的Snake模 生导师，主要研究方向为人工智能、多 型的图像分割算法[J].智能系统学报，2007,2(1)： Agent系统、模式识别.发表学术论文80 53-58. 余篇，出版专著4部. WANG Kejun,GUO Qingchang.Image segmentation algorithm based on the PSO and improved Snake model J].CAAI Transactions on Intelligent Systems,2007,2(1):53-58. [6]CHENG Xianyi,HAN Lanjun,MA Shouming.Design and 巩向普，男，1982年生，硕士研究 realization of medical image nonrigid matching algorithm 生，主要研究方向为模式识别. [C]//Proceedings of the Sixth Interational Conference on Intelligent Systems Design and Applications.Jinan,China, 2006:497-501