张小莉，闫宏印，徐秋菊

(1.山西轻工职业技术学院 信息工程系， 太原 030013;2.太原理工大学 计算机科学与技术学院， 太原 030024)



基于改进蚁群算法的阈值医学图像分割

张小莉1，闫宏印2，徐秋菊1

(1.山西轻工职业技术学院 信息工程系， 太原 030013;2.太原理工大学 计算机科学与技术学院， 太原 030024)

为了提高医学图像分割的精确度，提出了一种基于改进蚁群算法的阈值医学图像分割.对蚁群算法中的初始聚类中心、动态更新信息素浓度和参数变量进行了改进.实验结果证明：改进算法可以提高医学图像的分割精确度，同时克服蚁群算法搜索时间较长，求解速度较慢的缺陷，缩短运算时间.

图像分割; 医学图像；蚁群算法; 改进

在临床应用中，对医学图像分割的精确度和速度有着很高的要求，医学图像分割一直都是图像处理领域的研究热点和难点.由于医学图像结构复杂、可变性大且均质性差，因此针对临床实际和具体问题，分割精确度要求很高.近年来随着图像分割技术的迅速发展，已有许多研究人员提出和开发了多种分割算法.Otsu's算法[1]是典型的全局阈值分割算法.它对目标和背景大小比相差不大的图像具有较好的分割效果，当两者比例有偏差时，分割效果就变差，且易受噪声影响.遗传算法[2]是最早的启发式搜索算法，它通过自适应全局优化概率搜索得到最佳阈值，获得理想的分割效果，同时提高了抗噪性能.但是它的计算时间很长，这在很大程度上降低了效率.蚁群算法(ACO)是由意大利研究学者Marco Dorigo等[3]从蚂蚁觅食行为得到启发后，提出的一种启发式搜索算法并成功应用于旅行商问题的求解[4]，近年在图像分割中被广泛应用，但是蚁群算法易出现早熟和停滞现象[5].本文作者提出了一种基于改进蚁群算法的医学图像分割方法，可以提高分割精确度得到理想的分割结果，同时缩短运算时间.

1 基本蚁群算法

蚂蚁在觅食的过程中，会在其所经过的路径上留下一种称为“信息素”的东西，蚂蚁之间的交流和通信主要通过信息素来完成.当某一路径上经过的蚂蚁越多，留下的信息素浓度就越高，从而导致后来的蚂蚁选择这条路径的概率就越大[6-7]，因此经过一定时间后会选择一条最短的路径.如图1(a)所示，觅食开始时，所有路径上不存在信息素，蚂蚁的路径选择完全是随机的.所以两条路径上的蚂蚁数量相差不大.随后如图1(b)所示，寻找食物的蚂蚁会受到先前蚂蚁残留的信息素干扰，具体表现为蚂蚁趋向于选择信息素浓度高的路径，因此越来越多的蚂蚁选择路径较短的那条，从而找到了最优路径.

蚁群算法的基本思想可用以下伪代码描述[7-8]：

procedure ACO ( )

initialize_ant( ); %初始化蚂蚁

initialize_pheormone_trails( ); %初始化信息素

while (termination_criterion_not_satisfied)

for m=1 to number_of_ants

whlie ( current_state!= target_state)

read_ant_routing_table;

deposit_pheromone_on_each_route

%每条路径上留存的信息素

compute_transition_probability;

%计算衰减系数

do_local_pheromone_adjustment;

%更新局部信息素浓度值

update_pheromone_on_the_visited_route;

%更新路径上的信息素

move_to_next_state;

end while

do_global_pheromone_adjustment;

%更新全局信息素浓度值

update_pheromone_on _this_circulation;

%经过1次循环，按全局调整规则调整各路径上信息素

update_ant_routing_table;

end for

end while

end procedure

2 改进蚁群算法及步骤

在图像分割中，对于256灰度级的图像来说，图像的每个像素Xi(i=1,2,…,N)被看作是一只蚂蚁.因此每只蚂蚁都是具有灰度特征的一维矢量.图像分割的过程就是具有不同特征矢量的蚂蚁寻找食物源的过程[9-10].食物源即是图像分割的最佳阈值.本文算法构架如图2所示.

2.1 改进蚁群算法的步骤

步骤1：初始化阈值

初始化阈值T(即食物源)，为了减少大量无关计算，加快算法的运行进程，使初始阈值优化合理，利用数学上的中间值方法公式为

(1)

式中,k为灰度值.

步骤2：优化处理

1)根据欧氏距离公式算出每个像素Xi到初始阈值T的距离di为

(2)

2)计算t时刻每个像素Xi到初始阈值T的路径上的信息素浓度 τi,r为蚂蚁的聚集半径,设τi(0)为初始信息量,则

(3)

3)计算像素Xi到阈值集合的概率pi

(4)

式中：ηi是具有启发性的引导函数，ηi=1/di，它可反映像素之间的相似度；α 和β是控制信息素浓度和启发式引导函数选择路径的两个影响因子；Z={Xz|dz≤r,z=1,2,…,N} 是路径集合.

(5)

5)更新每条路径上的信息素浓度. 经过一次循环，每条路径上的信息素都会发生变化.为了提高全局优化能力，降低算法收敛速度，提出了自适应改变信息素的方法为

(6)

式中：ρ是信息素随时间变化的系数; n是di≤r时的像素数量;m是所有的像素总数;Δτi是经过一次循环后路径上信息素的增量.

步骤3：设置停止结束条件

一般结束条件的设置都是简单的给出一个固定数值，有很大的局限性和不确定性.如果数值太小，优化过程不够充分，很难得到最优值；相反，数值太大，优化过程很充分，但是计算的时间太长，又极大地降低了效率.因此本文提出动态自适应的方法来控制如下式

(7)

当满足式(7)时ε=0.01，算法终止，反之继续运行寻找最优阈值.

2.2 算法参数设置

算法中参数α, β和 ρ 的设置起了至关重要的作用.决定了整个算法的搜索性能和收敛速度.可以使用以下两种方式设置合适参数值.

1)粗调谐参数：对参数α和β采用大范围的数值调谐以获得理想的值，即α=2, β= 4.

2)精调谐参数：对参数ρ采用小范围的数值调谐获得理想的值，即ρ=0.7.

3 实验结果

本文是在Windows XP Professional SP2操作系统下，采用Matlab R2009a进行仿真实验.实验取用了两张256×256像素的人脑磁共振(MR)图像,一张人脑CT图像及一张肺部CT图像进行实验，如图3所示[11].为了分析和验证提出的改进蚁群算法的实际效果，采用了Otsu's算法、遗传算法及基本蚁群算法对4张原始图片进行分割.分割的效果如图4所示，第1列为对原始图像进行Otsu's算法的分割结果，第2列为遗传算法的分割结果，第3列为基本蚁群算法的分割结果，第4列为本文改进蚁群算法的分割结果.前3种方法大体可以将目标图像从背景中分割出来，但是在细微方面，脑部的脑白质和肺部的毛细血管分割的差异就显而易见了，本文方法能将图像细节部分分割的更加准确.

此外，还通过图像信息熵和运算时间来客观地分析所提方法的优越性[11-12].将图像信息熵H，运算时间t(单位为s)，和分割阈值T(食物源)作为实验结果的评判标准.图像信息熵是一种特征的统计形式，它反映了图像中包含信息量的多少,分割后的图像信息熵值越大，说明图像从源图像得到的信息量越大，分割图像细节越丰富，分割后的总效果越好.本文中信息熵H定义为

(8)

从表1可以看出本文改进蚁群算法信息熵值最大，这就说明此算法从源图像得到的信息量最大，分割效果最好.从运算时间上比较，所提出的算法运行时间少，更加高效.

表1 本文算法与其他算法的阈值、运算时间与信息熵比较Tab.1 Comparisons of each method on thresholding value, calculation time and comentropy

4 结语

本文作者通过对蚂蚁信息素浓度更新，初始聚类中心和参数设置的改进，使得算法对医学图像分割更加精确，获得更加理想的分割效果.由于结束条件的改进，只需要3次循环就可获得最佳阈值.而从运算时间来看，本文算法比Otsu's算法缩短了大约65%，比遗传算法缩短了约60%，比基本蚁群算法缩短了约3%，极大地提高了运算效率.现在蚁群算法已经越来越多地应用到医学图像处理中，今后如何能更好的优化此算法并应用到实际问题中将是未来主要的研究方向.

[1] OTSU N.A threshold selection method from gray level histogram[J]. IEEE Transactions on System, Man and Cybernetics,1979,19(1)：62-67.

[2] LO BOSCO G. A genetic algorithm for image segmentation[C]. International Conference on Image Analysis and Processing, 2001:262-266.

[3] DORIGO M, DI C G, GAMBARDELLA L M. Ant algorithms for discrete optimization[J].Artificial Life, 1999，5(5):137-172.

[4] DORIGO M. Ant colonies for the traveling salesman problem [J]. BioSystems,1997 ，43(2):73-81.

[5] ZHUANG X. Edge feature extraction in digital images with the ant colony system[C]. Processings of the IEEE International Conference on Computational Intelligence for Measurement Systems and Applications, 2004:133-136.

[6] YAO H M,WANG J F, LIU X Z. A nimum entropy spectrum extrapolation technique and its application to radar super-resolution[J]. Modern Radar, 2005，127(3):18-19.

[7] HUANG Min, DING Ping. An improved ant colony algorithm and its application in vehicle routing problem[J].Mathematical Problems in Engineering, 2013(6):1-9.

[8] CHIVILIKHIN D S， ULYANTSEV V I，SHALYTO A A. Solving five instances of the artificial ant problem with ant colony optimization[C]. 7th IFAC Conference on Manufacturing Modelling，2013, 46(9) :1043-1048.

[9] SOLTANPOOR H, VAFAEIJAHAN M, JALALI M. Graph-based image segmentation using imperialist competitive algorithm[J]. Advances in Computing , 2013， 3(2):11-21.

[10] YUN H Y, JEONG S, KIM K S. Advanced harmony search with ant colony optimization for solving the traveling salesman problem[J]. Journal of Applied Mathematics, 2013(2):1-8.

[11] GOPALAKRISHNAN R C, KUPPUSAMY V. Ant colony optimization approaches to clustering of lung nodules from CT images[J]. Computational and Mathematical Methods in Medicine, 2014:1-16.

[12] WANG Y Q, LIU X. Improved support vector clustering algorithm for color image segmentation [J].Engineering Review, 2015，35 (2): 121-129.

Improved ant colony optimization based medical image thresholding segmentation

ZHANGXiaoli1,YANHongyin2,XUQiuju1

(1. Department of Information Engineering, Shanxi Vocational and Technical College of Light Industry, Taiyuan 030013,China; 2. School of Computer Science and Technology, Taiyuan University of Technology, Taiyuan 030024, China)

In order to improve the accuracy of the medical image segmentation, the improved ant colony optimization (ACO) based medical image thresholding segmentation method is proposed. In the ant colony algorithm, the center of initial clustering, dynamic update pheromone concentration and variable parameters are improved. The experimental results show that the proposed method could improve the accuracy of the medical image segmentation. Compared with the traditional ACO, it has the advantages over fast search. It has overcome the defect of the slow solving speed and could efficiently reduce the calculation time.

image segmentation; medical image;ant colony optimization; improvements

2016-01-22

国家自然科学基金资助项目(51178026)

张小莉(1982—),女, 山西兴县人，讲师, 硕士.研究方向为计算机应用技术.email: xiaoli2408@163.com.

TP391

A

1673-0291(2016)05-0040-05

10.11860/j.issn.1673-0291.2016.05.007