基于ACS-FCM算法的圖像分割研究
圖像分割是把圖像分成各具特性的區(qū)域并提取出感興趣目標(biāo)的技術(shù)和過(guò)程[1]。數(shù)字圖像處理問(wèn)世不久,人們就開始了對(duì)圖像分割技術(shù)的研究,并取得了較大的進(jìn)展,但由于它的復(fù)雜性,有許多問(wèn)題仍然沒(méi)有得到很好的解決。圖像分割的方法有成百上千種,但尚沒(méi)有一種適用于所有圖像的通用分割算法。絕大多數(shù)算法都是針對(duì)具體問(wèn)題而提出的,因此人們?nèi)匀辉诓粩嗟难芯啃碌?,更有潛力的分割算法,以求?shí)現(xiàn)更好的分割效果。
圖像分割已廣泛應(yīng)用于工業(yè)自動(dòng)化、在線產(chǎn)品檢測(cè)、生產(chǎn)過(guò)程控制、文擋圖像處理、遙感和生物醫(yī)學(xué)圖像分析、保安監(jiān)視、以及軍事、體育、農(nóng)業(yè)工程等。概括來(lái)說(shuō),在各種圖像應(yīng)用中,只要對(duì)圖像目標(biāo)進(jìn)行提取、測(cè)量等都離不開圖像分割。近年來(lái),分割技術(shù)在對(duì)圖像的編碼中也起到了越來(lái)越重要的作用,如國(guó)際標(biāo)準(zhǔn)mpeg-iv中的模型基/目標(biāo)基編碼等都需要基于分割的結(jié)果。此外,對(duì)醫(yī)學(xué)圖像的分割是圖像分割中最重要的一個(gè)應(yīng)用領(lǐng)域。
目前,已提出很多種類型的分割算法,大致可以分為基于邊緣檢測(cè)的方法和基于區(qū)域的方法[2~3]。在實(shí)際應(yīng)用中,從不同的理論角度提出了許多方法,這些方法中主要可劃分為三種類型:閾值型、邊緣檢測(cè)型和區(qū)域跟蹤型。
本文提出將acs-fcm算法用于圖像分割,將模糊c均值聚類算法(fcm)和蟻群系統(tǒng)算法(acs)結(jié)合起來(lái),并使用matlab進(jìn)行了仿真實(shí)驗(yàn)。
2 蟻群算法
蟻群算法是受自然界螞蟻覓食過(guò)程啟發(fā)而產(chǎn)生的一種集群算法, 由意大利學(xué)者dorigo 于1991 首次系統(tǒng)地提出[4]。蟻群算法是從對(duì)蟻群行為的研究中產(chǎn)生的。為了說(shuō)明其基本原理,下面對(duì)人工蟻群進(jìn)行計(jì)算機(jī)仿真,仿真結(jié)果如圖1所示。
在圖中a點(diǎn)為食物源,而b點(diǎn)為螞蟻巢穴,蟻群正往返于食物與巢穴之間,其路徑為一條直線,如圖1(1)所示。假設(shè)在某一時(shí)刻在螞蟻的路徑中突然出現(xiàn)了一些障礙物,原有的路徑被切斷,這樣,從a到b的螞蟻就必須決定應(yīng)該往左還是往右邊走,如圖1(2)中所示。而從b到a的螞蟻也必須選擇一條路徑。這種決定會(huì)受到各條路徑上以往螞蟻留下的信息激素物質(zhì)濃度的影響,如果向右的路徑上的信息激素物質(zhì)濃度比較大,那么向右的路徑被螞蟻選中的可能性也就比較大一些。
圖1 人工蟻群運(yùn)動(dòng)圖
障礙物出現(xiàn)后,對(duì)第一只從a到b的螞蟻而言,因?yàn)闆](méi)有信息素物質(zhì)的影響,所以它選擇向左或者向右的可能性是一樣的。以從a點(diǎn)到b點(diǎn)的螞蟻為例,由于路徑acb比路徑adb要短,因此選擇acb路徑的螞蟻會(huì)比選擇adb的螞蟻早到b點(diǎn)。此時(shí),從b點(diǎn)向a點(diǎn)看,指向路徑bca的信息素濃度比bda大。因此,從下一時(shí)刻開始,從b點(diǎn)到達(dá)a點(diǎn)的螞蟻選擇bca路徑比選擇bda路徑的可能性要大。從而使路徑bca上的信息激素物質(zhì)濃度與路徑bda上的信息素濃度的差變大。而信息素物質(zhì)濃度差變大的結(jié)果就是選擇bca路徑的螞蟻進(jìn)一步增加,這又導(dǎo)致信息激素物質(zhì)濃度進(jìn)一步加大。這就是巢穴到食源的最短路線,如圖1(3),螞蟻根據(jù)線路上留下信息素濃度的大小,確定在路線上移動(dòng)的方向,蟻群向信息素濃度重的線路集聚的現(xiàn)象稱為正反饋。螞蟻算法正是基于正反饋原理的啟發(fā)式算法。
在自然界中,蟻群的這種尋找路徑的現(xiàn)象就表現(xiàn)為一種正反饋的過(guò)程,而這一過(guò)程應(yīng)用于優(yōu)化領(lǐng)域便產(chǎn)生了人工蟻群算法,整個(gè)系統(tǒng)也可以稱為蟻群系統(tǒng)(ant system)[5],而那些只具備了簡(jiǎn)單功能的工作單元將被視為“螞蟻”。那么,上述螞蟻尋找路徑的過(guò)程也可以用于解釋人工蟻群的尋優(yōu)過(guò)程。
2 蟻群算法與模糊c均值算法的結(jié)合——acs-fcm算法
模糊c均值算法(fcm)簡(jiǎn)單、收斂速度快,但受初始聚類中心影響較大,容易陷入局部極小,而蟻群算法是一種隨機(jī)搜索的全局優(yōu)化算法,如果將蟻群算法和fcm相結(jié)合[6~7],則可以充分發(fā)揮蟻群算法的全局優(yōu)化特征和fcm算法的局部尋優(yōu)能力,下面對(duì)這種混合式算法進(jìn)行探討。
螞蟻在從食物源到蟻穴并返回的過(guò)程中,能夠在它所走過(guò)的路徑上分泌一種稱之為“信息素”的化學(xué)物質(zhì),在自己所經(jīng)過(guò)的路徑上形成信息素軌跡,螞蟻通過(guò)感知這種物質(zhì)的存在及強(qiáng)度來(lái)指導(dǎo)自己的運(yùn)動(dòng)方向,螞蟻傾向于朝著信息強(qiáng)度高的方向運(yùn)動(dòng)。因此,由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象,某一路徑上走過(guò)的螞蟻越多,該路徑上的信息素越強(qiáng),從而使得選擇這條路徑上的螞蟻增多。螞蟻個(gè)體之間正是通過(guò)信息素的物質(zhì)進(jìn)行交流而達(dá)到搜索事物的目的。分析發(fā)現(xiàn)自然界中蟻群的覓食行為是一個(gè)不斷聚類的過(guò)程,食物源就是聚類的中心。將每個(gè)待聚類數(shù)據(jù)樣本視為具有不同屬性的螞蟻,螞蟻覓食的過(guò)程可看作是螞蟻不斷向聚類中心聚類的過(guò)程,聚類中心是螞蟻所要尋找的食物源。數(shù)據(jù)樣本集xi=(xi1,xi2,…,xim), i=1,2,…,n。初始時(shí)刻,各條路徑上的信息量相等,設(shè)r為聚類半徑,數(shù)據(jù)樣本與聚類中心間的加權(quán)歐式距離為:
(1)
各路徑上的信息素計(jì)算公式為
(2)
第i個(gè)螞蟻選擇聚類中心cj的概率為
(3)
其中,式(1)中pk為加權(quán)因子,加權(quán)因子可根據(jù)各屬性對(duì)聚類的影響設(shè)定且須滿足約束條件:∑pk=1, pk≥0。式(3)hij=1/dij為能見度因數(shù),反映螞蟻i在選擇聚類中心cj的受啟發(fā)程度。a和b為兩個(gè)參數(shù)[8],分別反映了螞蟻在運(yùn)動(dòng)過(guò)程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性。隨著蟻群的移動(dòng),各路徑上的信息素在積累的同時(shí),也會(huì)隨著時(shí)間的流逝而揮發(fā)。一次聚類完成之后,要對(duì)各路徑上的信息素進(jìn)行更新,采用的信息素更新方式為
評(píng)論