李偉研，杜玉曉

0 引言

圖像的邊緣提取是計(jì)算機(jī)視覺(jué)和圖像處理中重要的內(nèi)容[1]，廣泛應(yīng)用于目標(biāo)識(shí)別與跟蹤、機(jī)器人視覺(jué)、圖像數(shù)據(jù)壓縮等領(lǐng)域。準(zhǔn)確可靠的邊緣提取方法，對(duì)這些系統(tǒng)的整體性能起到至關(guān)重要的作用，因此邊緣提取成為研究人員進(jìn)行圖像特征分析研究時(shí)最為關(guān)注的熱門課題之一。邊緣提取的目的就是找到屬于感興趣的目標(biāo)輪廓的邊緣，目前，用于圖像邊緣提取的方法很多，主要有 Roberts算子、Sobel算子、Prewitt算子、LOG算子、Canny算子、小波法等[2]，這些方法的特點(diǎn)是運(yùn)算簡(jiǎn)單、可并行處理，但對(duì)噪聲比較敏感，也沒(méi)有考慮人眼視覺(jué)特性，測(cè)得的邊緣比較粗糙，尤其在圖像較復(fù)雜或含有噪聲時(shí)更是如此。針對(duì)圖像的特點(diǎn)，人們又提出多種提取方法，如基于 Gabor濾波器虛部的方法[3]、基于數(shù)學(xué)形態(tài)學(xué)的方法[4]等，它們?cè)趫D像處理領(lǐng)域已被廣泛采用，大多是針對(duì)各種不同類型的圖像所提出的，通用性不是很強(qiáng)，因而還沒(méi)有一種方法能適用于所有類型圖像的邊緣提取。

蟻群算法（Ant Colony Algorithm，ACA），是近幾年發(fā)展起來(lái)的一種新型概率搜索算法[5]，它利用生物信息激素作為螞蟻選擇后續(xù)行為的依據(jù)，并通過(guò)螞蟻間的協(xié)同與交互來(lái)完成全局尋優(yōu)搜索過(guò)程。該算法具有高適應(yīng)性、正反饋性和分布式處理等特點(diǎn)，已被成功用于解決諸如旅行商、圖著色等復(fù)雜問(wèn)題。將蟻群算法用于邊緣提取領(lǐng)域，主要分為3大類：1）基于圖像邊緣特征的蟻群算法[6]；2）基于模糊聚類的蟻群算法[7]；3）與其他算法的融合，如遺傳算法[8]、Snake模型[9]、Markov隨機(jī)場(chǎng)[10]等。本文在傳統(tǒng)邊緣提取方法的基礎(chǔ)上，提出了一種基于圖像邊緣特征的蟻群算法，用于圖像邊緣提取，提高了對(duì)復(fù)雜圖像的適應(yīng)性，實(shí)驗(yàn)結(jié)果證明了其有效性。

1 蟻群算法及邊緣提取的基本原理

1.1 蟻群算法的基本原理

蟻群算法是由M.Dorigo等人受真實(shí)蟻群集體覓食行為的啟發(fā)而提出的一種模擬仿生算法。經(jīng)長(zhǎng)期大量觀察研究后發(fā)現(xiàn)：最初單個(gè)螞蟻的行為是隨機(jī)的。每只螞蟻在隨機(jī)行走的過(guò)程中，會(huì)在其經(jīng)過(guò)的路徑上留下一種叫做外激素的信息素。一方面，該信息素會(huì)隨著時(shí)間的延續(xù)逐漸揮發(fā)衰減；另一方面，后來(lái)的螞蟻能夠感知這種信息素并以路徑上殘留信息量的多少指導(dǎo)其行為，一只螞蟻選擇一條路徑的概率，隨著以前選擇該路徑的螞蟻數(shù)量的增多而增大。因此由大量螞蟻組成的蟻群的集體行為，就表現(xiàn)出了一種信息的正反饋現(xiàn)象，從而整個(gè)蟻群的行為表現(xiàn)出了具有找出最短路徑的能力。

1.2 蟻群算法的特性

蟻群算法最主要的特性如下：

1）正反饋。正反饋機(jī)制能夠擴(kuò)大解的質(zhì)量對(duì)個(gè)體選擇路徑的影響，使得算法能夠快速地發(fā)現(xiàn)較好的解或最優(yōu)解。

2）分布式計(jì)算。分布式計(jì)算要求個(gè)體獨(dú)立地搜索最優(yōu)解，而個(gè)體之間互不干擾，這對(duì)于避免過(guò)早收斂有一定的效果。

3）啟發(fā)性。人工螞蟻能夠利用反映可行解質(zhì)量的啟發(fā)信息，借以指導(dǎo)自己的搜索方向，這使得算法在搜索過(guò)程的早期就能發(fā)現(xiàn)質(zhì)量較好的解，而完全隨機(jī)的選擇路徑，會(huì)造成早期搜索到的解的質(zhì)量不高。

4）魯棒性。通過(guò)稍加修改，就可以應(yīng)用到其他類型的問(wèn)題當(dāng)中。

5）并行性。由于每個(gè)螞蟻個(gè)體是獨(dú)立地搜索可行解，容易實(shí)現(xiàn)該算法的并行化，從而提高算法效率。

1.3 蟻群算法的應(yīng)用步驟

應(yīng)用蟻群算法解決問(wèn)題的一般步驟如下：

1）分析問(wèn)題，建立模型：對(duì)要解決的問(wèn)題進(jìn)行建模，抽象成螞蟻覓食的過(guò)程，賦予問(wèn)題空間參變量在此過(guò)程中具體意義。

2）初始化：給各參變量賦初值，將螞蟻隨機(jī)或者均勻分布到問(wèn)題空間各處。

3）優(yōu)化過(guò)程：螞蟻根據(jù)給定路徑長(zhǎng)度和信息素強(qiáng)度做動(dòng)態(tài)更新，并在運(yùn)動(dòng)中釋放信息素。

4）終止條件：對(duì)于給定條件，若滿足，則算法停止；否則，轉(zhuǎn)第3）步。停止條件可以是最大的迭代次數(shù)、計(jì)算機(jī)運(yùn)行時(shí)間、或者是系統(tǒng)所要達(dá)到的數(shù)據(jù)精度等。

第3）步是一個(gè)自適應(yīng)過(guò)程，它體現(xiàn)了蟻群算法的本質(zhì)：選擇機(jī)制和更新機(jī)制。

1.4 邊緣提取的基本原理

一幅圖像中往往包括目標(biāo)、背景、邊緣和噪聲等內(nèi)容。邊緣提取屬圖像分割算法中的一個(gè)算法，是圖像分割、紋理特征提取和形狀特征提取等圖像分析的重要基礎(chǔ)。圖像中的邊緣通常與圖像灰度或圖像灰度的一階導(dǎo)數(shù)的不連續(xù)性有關(guān)。同時(shí)梯度也是反映邊緣點(diǎn)與背景或目標(biāo)區(qū)域內(nèi)點(diǎn)區(qū)別的重要特征。圖像中灰度變化較大的邊緣區(qū)域其梯度值較大，灰度變化平緩的區(qū)域其梯度小，而在灰度均勻的區(qū)域其梯度值接近于0。

由于圖像在采集、傳輸?shù)倪^(guò)程中，不可避免地會(huì)伴隨噪聲從而導(dǎo)致圖像質(zhì)量變差，圖像較為模糊不易識(shí)別。因此，首先對(duì)超聲圖像進(jìn)行去噪處理，這里采用的是中值濾波法，它能有效地消除圖像中的隨機(jī)噪聲。假定經(jīng)中值濾波后的超聲圖像大小為m×n，將每個(gè)像素Xi（i=1，2....，m×n）都看作一只螞蟻。由于目標(biāo)邊緣梯度未知，但可知目標(biāo)內(nèi)部或背景區(qū)域內(nèi)像素的灰度變化平緩、梯度小，因此可以首先計(jì)算出圖像中的最小梯度值Gmin，然后計(jì)算任意像素Xi的梯度與Gmin之間的幅值差，將大于閾值T的這些差值看作螞蟻要搜索的食物。當(dāng)螞蟻尋找到“食物”，就意味著找到了目標(biāo)內(nèi)部或背景區(qū)域內(nèi)的像素點(diǎn)，在輸出圖像中，將這些像素點(diǎn)顏色改為白色，而剩下的像素點(diǎn)顏色改為黑色，這樣就提取出了圖像邊緣。

2 基于改進(jìn)蟻群算法的圖像邊緣提取法

2.1 各像素點(diǎn)灰度梯度的計(jì)算

因?yàn)橐獙D像像素的灰度梯度作為螞蟻路徑選擇的啟發(fā)信息，所以要計(jì)算各個(gè)像素點(diǎn)灰度梯度，以下方法能更快的得到各點(diǎn)的灰度梯度。計(jì)算圖像中相鄰像素間的灰度差時(shí)，將圖像作為相應(yīng)矩陣，用相鄰列或相鄰行相減，可快速得到灰度差。設(shè)G為待處理圖像，aij為像素點(diǎn)（i，j）灰度值，Gmin為圖像最小梯度值，如式（1）

那么

2.2 改進(jìn)的蟻群算法

在基本的螞蟻算法中，信息素留在螞蟻經(jīng)過(guò)的路徑上，本文的改進(jìn)算法對(duì)此作了修改，將信息素遺留在螞蟻所走過(guò)的每個(gè)像素點(diǎn)上。τij為信息素，T為梯度閾值，則

對(duì)于dij≥T，采用像素的3×3鄰域來(lái)區(qū)分噪聲點(diǎn)和邊界點(diǎn)。鄰域特征的提取方法為：先計(jì)算當(dāng)前像素和鄰域像素的灰度差，將該值與所設(shè)置的梯度閾值T作比較，小于T的鄰域像素個(gè)數(shù)n即為該像素點(diǎn)的鄰域特征。一般而言，當(dāng)n=8時(shí)，該像素點(diǎn)可視為區(qū)域內(nèi)點(diǎn)；當(dāng)且時(shí)，該像素點(diǎn)可視為邊界點(diǎn)；其它情況可視為噪聲點(diǎn)。

像素點(diǎn)Xij被歸為目標(biāo)內(nèi)部或非邊緣區(qū)的概率為

其中，T為梯度閾值。T越大則η越大，像素點(diǎn)被歸為非邊緣區(qū)的概率就越大；dij越大則η越小，像素點(diǎn)被歸為非邊緣區(qū)的概率就越小。另外，a和β兩個(gè)參數(shù)分別放置了像素被歸為非邊緣區(qū)的過(guò)程中所積累的信息素和啟發(fā)信息素在選擇像素點(diǎn)過(guò)程中的相對(duì)重要性。S為可選像素的集合，可定義為：

隨著螞蟻的移動(dòng)，各像素點(diǎn)上的信息素會(huì)發(fā)生變化，每完成一次循環(huán)，各像素點(diǎn)上的信息素都要更新。更新規(guī)則如下[11]：

其中，（1p）為信息素的衰減系數(shù)，通常設(shè)置p＜1來(lái)避免像素點(diǎn)上信息素的無(wú)限增加。Δτij表示本次循環(huán)中像素點(diǎn)上信息素的增量，表示第k只螞蟻在本次循環(huán)時(shí)留在像素點(diǎn)上的信息素。

2.3 參數(shù)說(shuō)明

改進(jìn)蟻群算法中共有6個(gè)主要參數(shù)：

群體規(guī)模m×n、信息素濃度權(quán)重a和啟發(fā)信息素權(quán)重β、梯度閾值T、釋放信息素的基數(shù)η和信息素衰減速率p。其中信息素濃度權(quán)重a和啟發(fā)信息的權(quán)重β將影響到算法的行為，過(guò)大信息素濃度權(quán)重將造成過(guò)多特征的丟失，而過(guò)大啟發(fā)信息的權(quán)重將加大算法對(duì)噪聲的敏感度；信息素釋放基數(shù)η則是為了維持信息素的最低濃度，大信息素釋放基數(shù)將降低算法對(duì)信息素的敏感度；過(guò)大的衰減速率p能提高邊緣提取的精度但是進(jìn)一步增加了算法的復(fù)雜度；群體規(guī)模m×n將影響到算法的時(shí)間性能；梯度閾值T的大小直接影響到邊緣提取的精確度。在實(shí)驗(yàn)仿真中，群體規(guī)模m×n一般取圖像象素點(diǎn)個(gè)數(shù)的10%～15%，a=2.5，β=1.2，T=25，釋放信息素的基數(shù)η=4，信息素衰減速率p=0.95，各個(gè)參數(shù)對(duì)于具體圖像也可以作適當(dāng)?shù)恼{(diào)整。

2.4 基于改進(jìn)蟻群算法的邊緣提取流程圖

圖1 改進(jìn)蟻群算法的邊緣提取流程圖

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

為了驗(yàn)證算法的效果，在Windows XP，Visual C++ 6.0和Matlab 6.5的運(yùn)行環(huán)境上，對(duì)該改進(jìn)算法在圖像邊緣提取技術(shù)上進(jìn)行了仿真。仿真參數(shù)由多次實(shí)驗(yàn)結(jié)果的效果分析后確定如下：m×n為500×500，a=2.3，β=1.4，T=25，η=5，p=0.98。圖2和圖3分別是原始圖像和通過(guò)改進(jìn)算法操作后的邊緣圖像對(duì)比。

圖2（a）原始圖像

圖2（b）邊緣圖像

圖3（a）原始圖像

圖3（b）邊緣圖像

由仿真結(jié)果可以看出，改進(jìn)蟻群算法的提取效果良好，對(duì)噪聲圖像中的邊緣提取具有算法效率高、抑制噪聲能力強(qiáng)、主要邊緣信息突出等特點(diǎn)，能夠有效地從噪聲圖像中提取物體的真實(shí)邊緣。此外，蟻群算法的正反饋特性以及抑制噪聲的能力，使其在復(fù)雜場(chǎng)景中的特征提取方面具有一定的優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

由以上分析，證明該改進(jìn)的螞蟻算法對(duì)于圖像的邊緣提取是有效的，它可以清晰地搜索出圖像的邊緣，較好地反映出圖像的邊緣特征。由于實(shí)驗(yàn)參數(shù)的確定也沒(méi)有理論上的指導(dǎo)，目前基本上是基于實(shí)驗(yàn)分析。在今后的工作中，將嘗試改進(jìn)算法中閾值的設(shè)定方法，將人為設(shè)定參數(shù)法改進(jìn)為計(jì)算機(jī)求解最優(yōu)閾值法，相信會(huì)進(jìn)一步地改進(jìn)圖像的邊緣提取結(jié)果。

[1]YuJin Zhang.Image Engineering: Image Processing and Analysis，TUP Press，Beijing，China，1999.

[2]吳健輝，楊坤濤.數(shù)字圖像處理中邊緣檢測(cè)算法的實(shí)驗(yàn)對(duì)比研究[J].湖南理工學(xué)院學(xué)報(bào):自然科學(xué)版，2007，20（2）:25-27.

[3]雷印勝.基于Gabor濾波器虛部的CT腦血管醫(yī)學(xué)圖像邊緣特征提取方法[J].天津大學(xué)學(xué)報(bào)，2007，40（7）:833-838.

[4]李麗，路小英等.基于數(shù)學(xué)形態(tài)學(xué)的鐮刀菌顯微圖像邊緣檢測(cè)[J]，農(nóng)機(jī)化研究，2009，5:48-50，54.

[5]Dorigo M，Di Caro G，Stutzle T .Ant algorithms[J].Future Generation Computer Systems，2000，16（8）:5-7.

[6]ZHUANG XIN-HUA.Image feature extraction with the perceptual graph based on the ant colony system[C]//Proceedings of the IEEE International Conference on Systems，Man，and Cybernetics（SMC2004）.Washington，DC:IEEE Computer Society，2004:6354-6359.

[7]HAN YAN-FANG，SHI PENG-FEI.An improved ant colony algorithm for fuzzy clustering in image

[8]segmentation[J].Neurocomputing，2007，70（4/6）:665-671

[9]張鋒，卿粼波，王旭陽(yáng)等.基于遺傳算法和螞蟻算法的圖像分割[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版，2005，42（4）:735-738.

[10]曹會(huì)志，王晨，羅述謙.結(jié)合蟻群算法的Snake模型的醫(yī)學(xué)圖像分割方法[J].北京生物醫(yī)學(xué)工程，2007，26（3）:245-248.

[11]盧曉東，周鳳岐，周軍.馬爾可夫隨機(jī)場(chǎng)中應(yīng)用蟻群系統(tǒng)的紅外圖像分割[J].火力與指揮控制，2006，31（7）:86-89.

[12]Dorigo M，Di Caro G and Gambardella L，"Ant Colony Optimization:New Meta-Heuristic"，Proceedings of the Congress on Evolutionary Computation，1999，pp.1470-1477.