基于改進(jìn)蟻群算法的閾值醫(yī)學(xué)圖像分割

張小莉，閆宏印，徐秋菊

(1.山西輕工職業(yè)技術(shù)學(xué)院 信息工程系， 太原 030013;2.太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 太原 030024)

?

基于改進(jìn)蟻群算法的閾值醫(yī)學(xué)圖像分割

張小莉1，閆宏印2，徐秋菊1

(1.山西輕工職業(yè)技術(shù)學(xué)院 信息工程系， 太原 030013;2.太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 太原 030024)

為了提高醫(yī)學(xué)圖像分割的精確度，提出了一種基于改進(jìn)蟻群算法的閾值醫(yī)學(xué)圖像分割.對(duì)蟻群算法中的初始聚類中心、動(dòng)態(tài)更新信息素濃度和參數(shù)變量進(jìn)行了改進(jìn).實(shí)驗(yàn)結(jié)果證明：改進(jìn)算法可以提高醫(yī)學(xué)圖像的分割精確度，同時(shí)克服蟻群算法搜索時(shí)間較長(zhǎng)，求解速度較慢的缺陷，縮短運(yùn)算時(shí)間.

圖像分割; 醫(yī)學(xué)圖像；蟻群算法; 改進(jìn)

在臨床應(yīng)用中，對(duì)醫(yī)學(xué)圖像分割的精確度和速度有著很高的要求，醫(yī)學(xué)圖像分割一直都是圖像處理領(lǐng)域的研究熱點(diǎn)和難點(diǎn).由于醫(yī)學(xué)圖像結(jié)構(gòu)復(fù)雜、可變性大且均質(zhì)性差，因此針對(duì)臨床實(shí)際和具體問題，分割精確度要求很高.近年來隨著圖像分割技術(shù)的迅速發(fā)展，已有許多研究人員提出和開發(fā)了多種分割算法.Otsu's算法[1]是典型的全局閾值分割算法.它對(duì)目標(biāo)和背景大小比相差不大的圖像具有較好的分割效果，當(dāng)兩者比例有偏差時(shí)，分割效果就變差，且易受噪聲影響.遺傳算法[2]是最早的啟發(fā)式搜索算法，它通過自適應(yīng)全局優(yōu)化概率搜索得到最佳閾值，獲得理想的分割效果，同時(shí)提高了抗噪性能.但是它的計(jì)算時(shí)間很長(zhǎng)，這在很大程度上降低了效率.蟻群算法(ACO)是由意大利研究學(xué)者M(jìn)arco Dorigo等[3]從螞蟻覓食行為得到啟發(fā)后，提出的一種啟發(fā)式搜索算法并成功應(yīng)用于旅行商問題的求解[4]，近年在圖像分割中被廣泛應(yīng)用，但是蟻群算法易出現(xiàn)早熟和停滯現(xiàn)象[5].本文作者提出了一種基于改進(jìn)蟻群算法的醫(yī)學(xué)圖像分割方法，可以提高分割精確度得到理想的分割結(jié)果，同時(shí)縮短運(yùn)算時(shí)間.

1 基本蟻群算法

螞蟻在覓食的過程中，會(huì)在其所經(jīng)過的路徑上留下一種稱為“信息素”的東西，螞蟻之間的交流和通信主要通過信息素來完成.當(dāng)某一路徑上經(jīng)過的螞蟻越多，留下的信息素濃度就越高，從而導(dǎo)致后來的螞蟻選擇這條路徑的概率就越大[6-7]，因此經(jīng)過一定時(shí)間后會(huì)選擇一條最短的路徑.如圖1(a)所示，覓食開始時(shí)，所有路徑上不存在信息素，螞蟻的路徑選擇完全是隨機(jī)的.所以兩條路徑上的螞蟻數(shù)量相差不大.隨后如圖1(b)所示，尋找食物的螞蟻會(huì)受到先前螞蟻殘留的信息素干擾，具體表現(xiàn)為螞蟻趨向于選擇信息素濃度高的路徑，因此越來越多的螞蟻選擇路徑較短的那條，從而找到了最優(yōu)路徑.

蟻群算法的基本思想可用以下偽代碼描述[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;

%計(jì)算衰減系數(shù)

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;

%經(jīng)過1次循環(huán)，按全局調(diào)整規(guī)則調(diào)整各路徑上信息素

update_ant_routing_table;

end for

end while

end procedure

2 改進(jìn)蟻群算法及步驟

在圖像分割中，對(duì)于256灰度級(jí)的圖像來說，圖像的每個(gè)像素Xi(i=1,2,…,N)被看作是一只螞蟻.因此每只螞蟻都是具有灰度特征的一維矢量.圖像分割的過程就是具有不同特征矢量的螞蟻尋找食物源的過程[9-10].食物源即是圖像分割的最佳閾值.本文算法構(gòu)架如圖2所示.

2.1 改進(jìn)蟻群算法的步驟

步驟1：初始化閾值

初始化閾值T(即食物源)，為了減少大量無關(guān)計(jì)算，加快算法的運(yùn)行進(jìn)程，使初始閾值優(yōu)化合理，利用數(shù)學(xué)上的中間值方法公式為

(1)

式中,k為灰度值.

步驟2：優(yōu)化處理

1)根據(jù)歐氏距離公式算出每個(gè)像素Xi到初始閾值T的距離di為

(2)

2)計(jì)算t時(shí)刻每個(gè)像素Xi到初始閾值T的路徑上的信息素濃度 τi,r為螞蟻的聚集半徑,設(shè)τi(0)為初始信息量,則

(3)

3)計(jì)算像素Xi到閾值集合的概率pi

(4)

式中：ηi是具有啟發(fā)性的引導(dǎo)函數(shù)，ηi=1/di，它可反映像素之間的相似度；α 和β是控制信息素濃度和啟發(fā)式引導(dǎo)函數(shù)選擇路徑的兩個(gè)影響因子；Z={Xz|dz≤r,z=1,2,…,N} 是路徑集合.

(5)

5)更新每條路徑上的信息素濃度. 經(jīng)過一次循環(huán)，每條路徑上的信息素都會(huì)發(fā)生變化.為了提高全局優(yōu)化能力，降低算法收斂速度，提出了自適應(yīng)改變信息素的方法為

(6)

式中：ρ是信息素隨時(shí)間變化的系數(shù); n是di≤r時(shí)的像素?cái)?shù)量;m是所有的像素總數(shù);Δτi是經(jīng)過一次循環(huán)后路徑上信息素的增量.

步驟3：設(shè)置停止結(jié)束條件

一般結(jié)束條件的設(shè)置都是簡(jiǎn)單的給出一個(gè)固定數(shù)值，有很大的局限性和不確定性.如果數(shù)值太小，優(yōu)化過程不夠充分，很難得到最優(yōu)值；相反，數(shù)值太大，優(yōu)化過程很充分，但是計(jì)算的時(shí)間太長(zhǎng)，又極大地降低了效率.因此本文提出動(dòng)態(tài)自適應(yīng)的方法來控制如下式

(7)

當(dāng)滿足式(7)時(shí)ε=0.01，算法終止，反之繼續(xù)運(yùn)行尋找最優(yōu)閾值.

2.2 算法參數(shù)設(shè)置

算法中參數(shù)α, β和 ρ 的設(shè)置起了至關(guān)重要的作用.決定了整個(gè)算法的搜索性能和收斂速度.可以使用以下兩種方式設(shè)置合適參數(shù)值.

1)粗調(diào)諧參數(shù)：對(duì)參數(shù)α和β采用大范圍的數(shù)值調(diào)諧以獲得理想的值，即α=2, β= 4.

2)精調(diào)諧參數(shù)：對(duì)參數(shù)ρ采用小范圍的數(shù)值調(diào)諧獲得理想的值，即ρ=0.7.

3 實(shí)驗(yàn)結(jié)果

本文是在Windows XP Professional SP2操作系統(tǒng)下，采用Matlab R2009a進(jìn)行仿真實(shí)驗(yàn).實(shí)驗(yàn)取用了兩張256×256像素的人腦磁共振(MR)圖像,一張人腦CT圖像及一張肺部CT圖像進(jìn)行實(shí)驗(yàn)，如圖3所示[11].為了分析和驗(yàn)證提出的改進(jìn)蟻群算法的實(shí)際效果，采用了Otsu's算法、遺傳算法及基本蟻群算法對(duì)4張?jiān)紙D片進(jìn)行分割.分割的效果如圖4所示，第1列為對(duì)原始圖像進(jìn)行Otsu's算法的分割結(jié)果，第2列為遺傳算法的分割結(jié)果，第3列為基本蟻群算法的分割結(jié)果，第4列為本文改進(jìn)蟻群算法的分割結(jié)果.前3種方法大體可以將目標(biāo)圖像從背景中分割出來，但是在細(xì)微方面，腦部的腦白質(zhì)和肺部的毛細(xì)血管分割的差異就顯而易見了，本文方法能將圖像細(xì)節(jié)部分分割的更加準(zhǔn)確.

此外，還通過圖像信息熵和運(yùn)算時(shí)間來客觀地分析所提方法的優(yōu)越性[11-12].將圖像信息熵H，運(yùn)算時(shí)間t(單位為s)，和分割閾值T(食物源)作為實(shí)驗(yàn)結(jié)果的評(píng)判標(biāo)準(zhǔn).圖像信息熵是一種特征的統(tǒng)計(jì)形式，它反映了圖像中包含信息量的多少,分割后的圖像信息熵值越大，說明圖像從源圖像得到的信息量越大，分割圖像細(xì)節(jié)越豐富，分割后的總效果越好.本文中信息熵H定義為

(8)

從表1可以看出本文改進(jìn)蟻群算法信息熵值最大，這就說明此算法從源圖像得到的信息量最大，分割效果最好.從運(yùn)算時(shí)間上比較，所提出的算法運(yùn)行時(shí)間少，更加高效.

表1 本文算法與其他算法的閾值、運(yùn)算時(shí)間與信息熵比較Tab.1 Comparisons of each method on thresholding value, calculation time and comentropy

4 結(jié)語

本文作者通過對(duì)螞蟻信息素濃度更新，初始聚類中心和參數(shù)設(shè)置的改進(jìn)，使得算法對(duì)醫(yī)學(xué)圖像分割更加精確，獲得更加理想的分割效果.由于結(jié)束條件的改進(jìn)，只需要3次循環(huán)就可獲得最佳閾值.而從運(yùn)算時(shí)間來看，本文算法比Otsu's算法縮短了大約65%，比遺傳算法縮短了約60%，比基本蟻群算法縮短了約3%，極大地提高了運(yùn)算效率.現(xiàn)在蟻群算法已經(jīng)越來越多地應(yīng)用到醫(yī)學(xué)圖像處理中，今后如何能更好的優(yōu)化此算法并應(yīng)用到實(shí)際問題中將是未來主要的研究方向.

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(51178026)

張小莉(1982—),女, 山西興縣人，講師, 碩士.研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù).email: xiaoli2408@163.com.

TP391

A

1673-0291(2016)05-0040-05

10.11860/j.issn.1673-0291.2016.05.007