蟻群算法在全方向M型心動(dòng)圖檢測(cè)中的應(yīng)用與研究

王琨+黃立勤

摘 要： 為了解決傳統(tǒng)邊緣檢測(cè)算法對(duì)全方向M型心動(dòng)圖檢測(cè)效果差的問題，根據(jù)基于蟻群算法邊緣檢測(cè)的思想，提出一種基于改進(jìn)的蟻群算法的邊緣檢測(cè)算法。根據(jù)心動(dòng)圖間接來源于CT圖的原理，一幅心動(dòng)圖中包含目標(biāo)、背景、邊界和噪聲等內(nèi)容，因此采用傳統(tǒng)的邊緣檢測(cè)算法的效果并不理想。這里在傳統(tǒng)蟻群算法邊緣檢測(cè)的基礎(chǔ)上，根據(jù)心動(dòng)圖的特點(diǎn)，采取改進(jìn)的轉(zhuǎn)移規(guī)則和信息素更新策略，以提高檢測(cè)精度和適應(yīng)性。再逐步細(xì)化，使用螞蟻算法進(jìn)行詳細(xì)的檢測(cè)，得到最佳的運(yùn)動(dòng)曲線。實(shí)驗(yàn)結(jié)果表明，該算法可以獲得精確的運(yùn)動(dòng)曲線，其結(jié)果能夠比傳統(tǒng)的方法獲得更豐富更真實(shí)的心動(dòng)圖運(yùn)動(dòng)細(xì)節(jié)信息，為醫(yī)生的診斷提供更多信息。

關(guān)鍵詞： 全方向M型心動(dòng)圖； 邊緣檢測(cè)； 蟻群算法； 更新策略

中圖分類號(hào)： TN919?34； TP391.41 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2014）22?0014?03

Application of ant colony algorithm in omni?directional M?mode echocardiography

WANG Kun， HUANG Li?qin

（College of Physics and Information Engineering， Fuzhou University， Fuzhou 350108， China）

Abstract： In order to solve the problem that the traditional edge detection algorithm has poor detection effect of omni?directional M?mode echocardiography， an edge detection algorithm based on the improved ant colony algorithm is presented according to the idea of edge detection based on the ant colony algorithm. According to the principle that the echocardiography comes indirectly from CT figure， that is， an echocardiography contains the contents of target， background， boundary， noise， etc.， it is pointed out that the detection effect of traditional edge detection algorithm for omni?directional M?mode echocardiography is not expected. According to the characteristics of echocardiography， the improved transition rule and pheromone update strategy was taken to improve the detection precision and adaptability. The best motion curves were obtained by gradually thinning and detailed edge detection with the ant algorithm. The experimental results show that the algorithm can get the more accurate motion curve and more actual and detail information than the traditional method. Therefore， the algorithm can provide more information for the doctors diagnosis.

Keywords： omni?directional M?mode echocardiography； edge detection； ant colony algorithm； update strategy

0 引 言

全方向M型心動(dòng)圖是基于心臟B超視頻影像中任一位置、任意方向線上重建出的多個(gè)灰度點(diǎn)運(yùn)動(dòng)軌跡的灰度（位置）?時(shí)間波形圖（它是2001年國家授權(quán)的發(fā)明專利）[1?3]。對(duì)它的波形變化劇烈的視頻運(yùn)動(dòng)曲線的檢測(cè)，其中最為常用的方法就是邊緣檢測(cè)。該方法可以較為清晰地顯示局部心臟結(jié)構(gòu)隨時(shí)間運(yùn)動(dòng)變化的細(xì)節(jié)信息，并在此基礎(chǔ)上，可以獲得心臟內(nèi)外膜室壁運(yùn)動(dòng)信息，筆記與心動(dòng)周期相關(guān)的室壁厚度、心臟管內(nèi)徑等重要的臨床診斷信息。

傳統(tǒng)的邊緣檢測(cè)方法有很多，如Sobel，Laplacian，Robert和Canny等，但是使用這些方法來檢測(cè)心動(dòng)圖運(yùn)動(dòng)曲線時(shí)[4?7]，由于這些算法都是以簡單的梯度運(yùn)算為基礎(chǔ)，對(duì)于對(duì)比度較高的圖像具有簡單易于實(shí)現(xiàn)的效果，但對(duì)于圖像整體較為模糊，噪聲較多的心動(dòng)圖來說，效果并不理想[8?10]。因此結(jié)合心動(dòng)圖的特點(diǎn)，運(yùn)用新的邊緣檢測(cè)算法來提取出心動(dòng)圖的運(yùn)動(dòng)曲線具有重要意義[11]。

1 蟻群算法

蟻群算法（ACO）是由意大利學(xué)者Dorigo等提出的一種仿生隨機(jī)優(yōu)化算法，被廣泛地應(yīng)用于各種難以求解的組合優(yōu)化問題，并取得了一定的效果，蟻群算法具有魯棒性強(qiáng)、正反饋、分布式計(jì)算和易于結(jié)合其他算法等優(yōu)點(diǎn)，同時(shí)還可以進(jìn)行并行運(yùn)算處理。最初的蟻群算法圍繞螞蟻系統(tǒng)的性能旨在解決一些經(jīng)典的問題，如旅行商問題（TSP）等，但蟻群算法在解決這些問題時(shí)卻遜于其他經(jīng)典算法。因此，在此后的學(xué)者相繼提出了不少改進(jìn)的算法，如蟻群系統(tǒng)[12]（ACS）和最大最小螞蟻系統(tǒng)[13]（MMAS）。本文對(duì)蟻群算法在心動(dòng)圖上的應(yīng)用做了研究，根據(jù)對(duì)心動(dòng)圖圖和蟻群算法的研究，在心動(dòng)圖上建立模型，提取心動(dòng)圖上各種參數(shù)，使之可以使用蟻群算法求解。

2 算法介紹

本文算法通過蟻群算法來獲取心動(dòng)圖上包含連續(xù)的強(qiáng)邊界部分的區(qū)域，首先將心動(dòng)圖視為一張無向圖，在其中隨機(jī)地放置一定數(shù)量的螞蟻，并根據(jù)心動(dòng)圖的特點(diǎn)來對(duì)螞蟻起點(diǎn)的選擇以及轉(zhuǎn)移規(guī)則進(jìn)行設(shè)置，通過多次循環(huán)迭代后使得大多數(shù)螞蟻聚集在心動(dòng)圖運(yùn)動(dòng)曲線附近，具體過程分為以下6個(gè)步驟：

2.1 數(shù)學(xué)抽象

對(duì)于心動(dòng)圖im，其大小為M×N，可以從圖論的角度出發(fā)將其視為由N個(gè)頂點(diǎn)以及E條邊組成的無向圖G=。螞蟻所在的位置為頂點(diǎn)，而其待選路徑由邊來表示，通過尋找螞蟻選擇的最優(yōu)路徑來找到心動(dòng)圖的運(yùn)動(dòng)曲線。

2.2 螞蟻的路徑選擇

螞蟻從起點(diǎn)開始，每一次都要向下一個(gè)像素點(diǎn)移動(dòng)，設(shè)每一步的移動(dòng)范圍為[G（i，j，t）]，該螞蟻的轉(zhuǎn)移概率為：

[p（i，j）=[τ（i，j）]α*η（i，j）β（x，y）∈G（i，j，t）[τ（x，y）]α*η（x，y）β，（x，y）∈G（i，j，t）0，其他] （1）

[η（i，j）=?I（i，j）C， C為常數(shù)] （2）

[I（i，j）=1255max[Ii，j-1-Ii，j+1， Ii-1，j-1-Ii+1，j+1， Ii-1，j-Ii+1，j， Ii-1，j+1-Ii+1，j-1]] （3）

式中：[α]和[β]是蟻群算法的參數(shù)，代表螞蟻對(duì)信息素和啟發(fā)信息的重視程度，通過實(shí)驗(yàn)選取[α=3]和[β=2]；[η（i，j）]為根據(jù)尋找心動(dòng)圖灰度變化劇烈的地方來作為其運(yùn)動(dòng)曲線的原則設(shè)置的啟發(fā)函數(shù)，旨在找到與3[×]3鄰域內(nèi)像素灰度差距較大的點(diǎn)來作為待選邊緣點(diǎn)，圖 1顯示了螞蟻在3[×]3領(lǐng)域內(nèi)的路徑選擇情況。

圖1 螞蟻的3[×]3領(lǐng)域

為了使得螞蟻避免重復(fù)走已走過的路徑，使其具備一定的記憶功能，還需要引入禁忌鏈表來記錄螞蟻曾經(jīng)走過的像素點(diǎn)，鏈表長度的選取至關(guān)重要，長度選取過大，檢測(cè)出的邊緣可能會(huì)出現(xiàn)不連續(xù)的情況，而對(duì)于檢測(cè)邊緣點(diǎn)較多時(shí)，長度選取應(yīng)較小。實(shí)驗(yàn)結(jié)果表明，其值取20～50時(shí)邊緣檢測(cè)整體效果較好。

2.3 信息激素的更新

當(dāng)所有螞蟻都走完一步時(shí)，一次迭代結(jié)束，所有螞蟻根據(jù)式（4）來進(jìn)行信息素更新：

[τ（i，j）（t）=（1-ρ）τ（i，j）（t-1）+ρ?Δτk（i，j）] （4）

式中：[ρ]代表了信息素的揮發(fā)率，根據(jù)實(shí)驗(yàn)取[ρ=0.95]；[Δτk（i，j）]代表了信息素的積累量，其值為：[Δτ（i，j）=k=1NUMΔτ（i，j）]。對(duì)于本算法只有最優(yōu)解可以釋放信息素，也就是只有梯度最大的螞蟻可以積累信息素：

[Δτki，j=I（i，j）] （5）

每次迭代結(jié)束后會(huì)通過式（5）進(jìn)行一次信息素更新：

[τ（t）=（1-μ）τ（t-1）+μτ0] （6）

2.4 確定邊緣點(diǎn)

進(jìn)行完所有迭代后，根據(jù)每個(gè)像素點(diǎn)上的信息素強(qiáng)度來設(shè)定閾值，以此來判別邊緣點(diǎn)：

[Ei，j=1，τi，j≥T0，τi，j

其中，設(shè)定1代表邊緣點(diǎn)，0代表非邊緣點(diǎn)。

2.5 終止條件

這里需要根據(jù)圖像的特點(diǎn)來設(shè)定總的迭代次數(shù)，一般來說，圖像越復(fù)雜，尺寸越大，所需迭代次數(shù)越多，反之，圖像所需的迭代次數(shù)就越少。本文所采用的心動(dòng)圖大小為300×101，根據(jù)實(shí)驗(yàn)表明，迭代次數(shù)取120～280時(shí)效果較好。

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

本次實(shí)驗(yàn)是利用Matlab 7.2進(jìn)行的，運(yùn)行環(huán)境為Windows 7操作系統(tǒng)。

圖2是一幅全方向M型心動(dòng)圖圖像，圖像的分辨率大小300×101，如圖2（a）所示，為了證明本文算法在心動(dòng)圖應(yīng)用中的優(yōu)勢(shì)，本文加入了多尺度小波算法，Canny算法，Sobel算法，來進(jìn)行比較分析。

圖2 心動(dòng)圖檢測(cè)與各經(jīng)典算法對(duì)比情況

由圖2以及表1可以看出：Sobel算法（圖2（d））在檢測(cè)時(shí)出現(xiàn)了明顯的間斷，效果不理想；Canny算法（圖2（c））雖然檢測(cè)效果較為連續(xù)，但檢測(cè)出的偽邊緣較多，與所要達(dá)到精確提取運(yùn)動(dòng)曲線的目標(biāo)不符；小波算法（圖2（b））雖然實(shí)現(xiàn)了精確定位，但沒有有效地抑制噪聲的干擾，最后根據(jù)本文思想有效對(duì)全方向M型圖像中的背景、目標(biāo)、邊緣和噪聲等特點(diǎn)，采取改進(jìn)的轉(zhuǎn)移規(guī)則和信息素更新策略，提高了檢測(cè)精度和適應(yīng)性。綜上所述，由于全方向M型心動(dòng)圖較為復(fù)雜，采用傳統(tǒng)的邊緣檢測(cè)方法所獲得的效果并不理想，因此本文針對(duì)心動(dòng)圖的特點(diǎn)，并結(jié)合蟻群算法邊緣檢測(cè)的思想，提出改進(jìn)的轉(zhuǎn)移規(guī)則和信息素更新策略，提高了算法對(duì)于心動(dòng)圖的適應(yīng)性，檢測(cè)結(jié)果相比傳統(tǒng)算法較為精確，不過由于本文算法較為復(fù)雜，檢測(cè)所需運(yùn)行時(shí)間比較高，尚有待進(jìn)一步的改進(jìn)。

表1 各算法運(yùn)算時(shí)間的比較

4 結(jié) 語

由于心動(dòng)圖的特點(diǎn)是噪聲多、圖像模糊，因此本文根據(jù)心動(dòng)圖的特點(diǎn)，提出了改進(jìn)的蟻群算法，實(shí)現(xiàn)了較好的檢測(cè)精度，實(shí)驗(yàn)結(jié)果表明，該算法能有效地抑制噪聲干擾，獲得的運(yùn)動(dòng)曲線較傳統(tǒng)方法更加準(zhǔn)確，為后續(xù)基于速度場(chǎng)、加速度場(chǎng)提取心臟動(dòng)態(tài)信息奠定了良好的基礎(chǔ)。

參考文獻(xiàn)

[1] LIN Qiang， SHI Jiang?hong. The dynamic information of echocardiography omni?directional m?mode echocardiography [J]. Journal of Scientific Instrument， 2005， 26（4）： 437?440.

[2] CHEN Bin， GUO Wei， HU Yang， et al. The regional myocardial motion evaluated by omni? directional m?mode echocardiography in hypertensive patients with left ventricular hypert rophy [J]. Chinese Journal of Hypertension， 2011， 19（10）： 947?950.

[3] LAI Bao?chun， GUO Wei. Evaluation on regional myocardial function of left ventricular in patients with premature ventricular beat from right ventricular outflow tract using omni? directional m?mode echocardiography [J]. Chinese Journal of Medical Imaging Technology， 2011， 27（6）： 1178?1182.

[4] PELLEGRINO F A，VANZELLA W， TORRE V. Edge detection revisited [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2004， 34（3）： 1500?1518.

[5] 楊朝輝.基于全局化相關(guān)系數(shù)的邊緣檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（8）：3159?3161.

[6] NEZAMABADI?POUR H， SARYAZDI S， RASHEDI E. Edge detection using ant algorithms [J]. Soft Computing， 2006， 10（7）： 623?629.

[7] COLONI A. DORIGO M. MANIEZZO V. An investigation of some properties of an "Antalgorithm" [C]// Proceedings of The Parallel Problem Solving From Nature Conference. Brussels， Belgium： Elsevier Publishing， 1992： 509?520.

[8] TORRE V， POGGIO T. On edge detection [J]. IEEE Transactions Pattern Analysis and Machine Intelligence， 1986， 8（4）： 147?154.

[9] ZHANG Y， ROCKETT P I. The bayesian operating point of the ca nny edge detector [J]. IEEE Transactions on Image Processing， 2006， 15（11）： 3409.

[10] FEMANDES C， RAMOS V， ROSA A C. Self?Regulated artificial ant colonies on digital image habitats [J]. Interntional Journal of Lateral Computing， 2005， 2（1）： 1?8.

[11] 任毅斌，王子嫣.數(shù)字圖像中邊緣檢測(cè)算法綜合研究[J].計(jì)算機(jī)與信息技術(shù)，2007（9）：23?26.

[12] 張景虎，邊振興.基于蟻群算法的圖像邊緣檢測(cè)的研究[J].火力與指揮控制，2010，35（2）：115?118.

[13] TANG Jia?fu， MA Yu?yan， GUAN Jing， et al. A max–min ant system for the split delivery weighted vehicle routing problem [J]. Expert Systems with Applications， 2013， 40（18）： 7468?7477.