姜 志，戴文戰(zhàn)

（1.浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院，杭州310018；2.浙江工商大學(xué)信息與電子工程學(xué)院，杭州310018）

蟻群算法在二維Otsu圖像分割中的應(yīng)用

姜 志1，戴文戰(zhàn)2

（1.浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院，杭州310018；2.浙江工商大學(xué)信息與電子工程學(xué)院，杭州310018）

提出了一種基于蟻群算法和二維Otsu的圖像分割方法，利用蟻群算法快速尋優(yōu)的特點(diǎn)，求出二維Otsu圖像分割的閾值分割點(diǎn)，對(duì)圖像進(jìn)行分割。根據(jù)源圖像和鄰域平滑后圖像的灰度，以及灰度頻數(shù)進(jìn)行聚類(lèi)。通過(guò)灰度直方圖的峰值點(diǎn)設(shè)置精確的初始聚類(lèi)中心，解決了蟻群算法運(yùn)算次數(shù)多、計(jì)算量大的問(wèn)題；針對(duì)具體應(yīng)用，對(duì)聚類(lèi)半徑、信息激素和啟發(fā)引導(dǎo)函數(shù)進(jìn)行了修正。實(shí)驗(yàn)表明該算法速度快、劃分特性好、抗噪聲能力強(qiáng)，可以準(zhǔn)確地分割出目標(biāo)。

灰度直方圖；圖像分割；蟻群算法；二維Otsu算法

0 引 言

圖像分割是圖像識(shí)別、特征提取和自動(dòng)目標(biāo)識(shí)別等計(jì)算機(jī)后續(xù)處理的前提，是圖像處理的最基本任務(wù)，同時(shí)也在圖像處理系統(tǒng)中占據(jù)著重要地位。圖像分割的目的是將圖像中的目標(biāo)和背景分割開(kāi)，以便計(jì)算機(jī)視覺(jué)的后續(xù)處理。

Otsu算法利用圖像的灰度直方圖，根據(jù)目標(biāo)與背景之間的最大方差動(dòng)態(tài)地確定圖像分割的門(mén)限，不需要其他先驗(yàn)知識(shí)，應(yīng)用范圍廣，分割效果好，是一種有效的圖像分割方法。但Otsu法存在分割效果易受噪聲影響的缺點(diǎn)。由劉建莊等［1］提出的二維Otsu分割法和由汪海洋等［2］提出的快速二維Otsu分割法，利用圖像像素點(diǎn)與鄰近像素點(diǎn)的相關(guān)性，克服了一維Otsu分割抗噪性不強(qiáng)的缺點(diǎn)，但存在計(jì)算復(fù)雜運(yùn)算時(shí)間長(zhǎng)的缺點(diǎn)。

蟻群算法（ant colony optimization）又稱(chēng)螞蟻算法，是20世界90年代發(fā)展起來(lái)的一種模仿螞蟻群體性行為的智能化算法。基于蟻群算法的聚類(lèi)分析，將數(shù)據(jù)視為具有不同屬性的螞蟻，將數(shù)據(jù)聚類(lèi)的過(guò)程看作螞蟻尋找食物的過(guò)程。在尋找食物的過(guò)程中，螞蟻會(huì)在經(jīng)過(guò)的路徑上釋放信息素，后面的螞蟻會(huì)選擇走信息素強(qiáng)的路徑，這樣信息素強(qiáng)的路徑上螞蟻越來(lái)越多，信息素也越來(lái)越多，而信息素弱的路徑上螞蟻越來(lái)越少，信息素也越來(lái)越少，最終所有螞蟻都選擇這條信息素最多的路徑，即最優(yōu)路徑。蟻群算法正是利用蟻群聚類(lèi)尋優(yōu)的原理，實(shí)現(xiàn)快速尋優(yōu)［3-4］。一幅圖像中包括目標(biāo)、邊界、背景和噪聲等內(nèi)容，尋找出體現(xiàn)這些內(nèi)容之間區(qū)別的特征量，對(duì)于后繼的分類(lèi)過(guò)程至關(guān)重要［5］，蟻群算法已在圖像分割等很多領(lǐng)域獲得應(yīng)用。王爽等［6］提出的基于蟻群算法的一維Otsu分割方法，正是利用了蟻群算法快速尋優(yōu)的特點(diǎn)實(shí)現(xiàn)了圖像的快速分割。由于圖像像素點(diǎn)的灰度值僅僅反映像素灰度級(jí)的幅值大小，并沒(méi)有反映出像素與鄰域空間的相關(guān)信息，因此基于一維Otsu的分割方法具有抗噪性不強(qiáng)的缺點(diǎn)［7］。為此本文將蟻群算法與二維Otsu相結(jié)合的圖像分割方法。

本文在二維Otsu方法的基礎(chǔ)上將蟻群算法應(yīng)用于閾值選取，利用蟻群算法聚類(lèi)快速尋優(yōu)的特點(diǎn)［8］，克服二維Otsu方法遍歷搜索圖像的每個(gè)像素點(diǎn)從而導(dǎo)致計(jì)算復(fù)雜、運(yùn)算時(shí)間長(zhǎng)的缺點(diǎn)，降低了計(jì)算復(fù)雜度，且基于二維的Otsu分割方法即反映了像素點(diǎn)的灰度分布又體現(xiàn)了像素點(diǎn)與其鄰域空間內(nèi)其他像素點(diǎn)的相關(guān)性，提高了分割時(shí)的抗噪性，因此本文方法實(shí)現(xiàn)了圖像快速分割的同時(shí)又克服了一維Otsu分割方法抗噪性不足的缺點(diǎn)，為計(jì)算機(jī)視覺(jué)的后續(xù)處理提供了基礎(chǔ)。

1 二維Otsu圖像分割的算法

二維Otsu算法是在一維Otsu算法上發(fā)展起來(lái)的，利用原圖像像素點(diǎn)的灰度值與鄰域平滑后圖像像素點(diǎn)的灰度值構(gòu)建二維灰度直方圖，克服了一維Otsu算法抗噪性不強(qiáng)的缺點(diǎn)［9-11］。其原理為：設(shè)原始圖像f（x，y）是灰度級(jí)為的圖像，計(jì)算每個(gè)像素點(diǎn)n×n鄰域的平均灰度值，得到鄰域平滑圖像g（x，y）。對(duì)于圖像中的任何一個(gè)像素，構(gòu)成了一個(gè)二元組：像素灰度值和鄰域平均灰度值。設(shè)表示圖像f中像素灰度值為i、鄰域平均灰度值為j的像素點(diǎn)的個(gè)數(shù)，那么可得到該圖像的二維灰度直方圖，可以定義相應(yīng)的聯(lián)合密度：

目標(biāo)部分和背景部分對(duì)應(yīng)的均值矢量分別為ˉu0和：

二維直方圖的總體均值矢量為：

由于遠(yuǎn)離直方圖對(duì)角線的pi，j為零［12］，故二維Otsu閾值分割法可以忽略遠(yuǎn)離對(duì)角線的像素點(diǎn)，則可得到類(lèi)間離散測(cè)度：

最佳閾值（s′，t′）滿足：

由于s、t分別對(duì)應(yīng)灰度閾值和鄰域平均灰度閾值，故其最佳閾值分別滿足下式［13］：

由上式可知，一個(gè)二元函數(shù)SB（s，t）的最優(yōu)解，可以分解為求兩個(gè)一元函數(shù)最優(yōu)解的和，即：

2 蟻群算法

本文的分割方法是基于圖像的灰度直方圖，利用像素的灰度值、鄰域平均灰度值和灰度值的頻數(shù)。基于蟻群算法的二維Otsu分割方法即利用了蟻群算法快速尋優(yōu)的特點(diǎn)又克服了一維Otsu算法抗噪性不強(qiáng)的缺點(diǎn)，在圖像分割中取得了很好的分割效果。將蟻群算法應(yīng)用于聚類(lèi)問(wèn)題中，其主要思想是：將圖像中各個(gè)像素點(diǎn)的灰度值看作一只螞蟻，將螞蟻分別聚集到j(luò)個(gè)聚類(lèi)中心cj（j=1，2，…，k）的過(guò)程。設(shè)聚類(lèi)半徑為R，t時(shí)刻螞蟻i到聚類(lèi)中心cj的路徑上含有的信息素的濃度為phi，j（t），螞蟻與聚類(lèi)中心的加權(quán)歐氏距離為di，j，啟發(fā)式引導(dǎo)函數(shù)為υi，j，啟發(fā)式引導(dǎo)函數(shù)表示螞蟻i轉(zhuǎn)移至聚類(lèi)中心cj的期望程度，信息素與啟發(fā)式引導(dǎo)函數(shù)在路徑選擇中的作用權(quán)重為a、b，設(shè)第i個(gè)螞蟻與聚類(lèi)中心cj之間的吸引力為Ni，j，第i個(gè)螞蟻選擇聚類(lèi)中心cj的概率為pi，j

［14］。

其中，S=｛Xs｜dsj≤R，s=1，2，…N｝為可行路徑集合，式（12）中的pk為加權(quán)因子，pk根據(jù)各分量對(duì)聚類(lèi)的影響程度來(lái)設(shè)定。隨著螞蟻尋找目標(biāo)的過(guò)程，各條路徑上經(jīng)過(guò)螞蟻的數(shù)量將發(fā)生變換，因此各路徑上含有的信息激素的濃度也將發(fā)生變化，根據(jù)式（16）和式（17）對(duì)各路徑上的信息量進(jìn)行調(diào)整：

式（16）中q為信息素濃度隨著螞蟻尋找聚類(lèi)中心過(guò)程的時(shí)間殘留系數(shù)。式（17）中Δphi，j為聚類(lèi)過(guò)程中螞蟻i到聚類(lèi)中心cj所走路徑上的信息激素濃度的增量；Q為螞蟻的信息常量；Lj為螞蟻i在本次聚類(lèi)過(guò)程中從起始點(diǎn)到聚類(lèi)中心走過(guò)的路程。

3 基于蟻群聚類(lèi)算法實(shí)現(xiàn)二維Otsu的快速分割

3.1 基于蟻群算法的圖像聚類(lèi)分割

3.1.1 聚類(lèi)中心

在蟻群算法中螞蟻行走是具有盲目性和隨機(jī)性的，為了減少螞蟻行走過(guò)程中的盲目性和隨機(jī)性，本文以原始圖像和鄰域平滑后圖像的灰度直方圖為基礎(chǔ)，選擇灰度直方圖的各個(gè)峰值點(diǎn)作為初始聚類(lèi)中心，同時(shí)統(tǒng)計(jì)初始聚類(lèi)中心的個(gè)數(shù)，這樣可以將所有像素之間的大量循環(huán)計(jì)算轉(zhuǎn)化為各個(gè)像素與少數(shù)幾個(gè)峰值點(diǎn)之間的計(jì)算。采用灰度直方圖的峰值點(diǎn)作為初始聚類(lèi)中心也可以引導(dǎo)螞蟻直奔聚類(lèi)中心，減少了螞蟻尋找食物的過(guò)程，從而減少了計(jì)算量。

3.1.2 引導(dǎo)函數(shù)

引導(dǎo)函數(shù)，是問(wèn)題本身提供的先驗(yàn)信息，代表第i個(gè)螞蟻選擇聚類(lèi)中心cj的期望程度，即第i個(gè)螞蟻尋找聚類(lèi)中心j的所經(jīng)過(guò)的路徑的能見(jiàn)度。在蟻群算法中每個(gè)螞蟻是否趨向于某一聚類(lèi)中心，不僅取決于路徑上含有的信息激素的濃度，還取決于考慮引導(dǎo)函數(shù)。本文算法的引導(dǎo)函數(shù)為：

式中di，j代表路徑的長(zhǎng)度，即數(shù)據(jù)與聚類(lèi)中心的相似度。

3.1.3 聚類(lèi)半徑

傳統(tǒng)的蟻群算法往往是通過(guò)分階段的局部搜索來(lái)獲得全局最優(yōu)。由于螞蟻尋找聚類(lèi)中心的過(guò)程要受到聚類(lèi)半徑的限制，超出聚類(lèi)半徑R的蟻群不能加入尋找聚類(lèi)中心的聚類(lèi)過(guò)程，這樣既耗費(fèi)時(shí)間又容易使聚類(lèi)陷入局部最優(yōu)。為了克服以上問(wèn)題本算法選擇原始圖像和鄰域平滑后圖像的灰度直方圖峰值點(diǎn)作為初始聚類(lèi)中心，使初始聚類(lèi)中心就在實(shí)際聚類(lèi)中心的附近，螞蟻直奔聚類(lèi)中心，不存在受聚類(lèi)半徑影響問(wèn)題。

3.1.4 信息素更新

將螞蟻搜索行為集中到最優(yōu)解附近，可以提高解的質(zhì)量和收斂速度，從而改進(jìn)算法的性能。但是這種搜索方式會(huì)使算法過(guò)早收斂而出現(xiàn)早熟現(xiàn)象，為了克服這種問(wèn)題，本文采用最大-最小螞蟻系統(tǒng)（MAX-MIN ant system，MMAS）方法［15］調(diào)整信息素，限制各條路徑上的信息激素的濃度在區(qū)間［τmin，τmax］之內(nèi)，將超出這個(gè)區(qū)間的值限制為信息激素濃度允許區(qū)間上下限的值，從而有效地避免了某條路徑上的信息激素的濃度遠(yuǎn)超過(guò)其他路徑而造成的所有螞蟻都聚集到同一條路徑上，導(dǎo)致算法不再擴(kuò)散，加快收斂速度。具體做法為：首先，將初始化信息量設(shè)置為最大值，τi，j（t）=c=τmax。其次，每一次聚類(lèi)循環(huán)后，只有找到最短路徑到達(dá)聚類(lèi)中心的螞蟻才能在其所經(jīng)過(guò)的路徑上釋放信息激素。即

最后，將τi，j（t），限定在［τmin，τmax］之間。即如果τi，j≤τmin，則τi，j=τmin；如果τi，j≥τmax，則τi，j=τmax。

3.2 算法實(shí)現(xiàn)步驟

step 1：對(duì)a、b、q、τmin、τmax、R等參數(shù)值進(jìn)行初始化。

step 2：求源圖像及鄰域平滑后圖像的灰度直方圖，找出各個(gè)灰度直方圖的峰值點(diǎn)的灰度值，并把與這些峰值點(diǎn)具有相同灰度值的所有像素點(diǎn)作為初始聚類(lèi)中心。

step 3：計(jì)算所有聚類(lèi)中心的頻數(shù)，判斷邊界、噪聲、目標(biāo)和背景。

step 4：將式（11）選為適應(yīng)度函數(shù)，確定像素Xr到不同聚類(lèi)中心cj的相似度di，j。根據(jù)式（18）計(jì)算引導(dǎo)函數(shù)。

step 5：按照從四周向中心的順序選擇螞蟻，開(kāi)始聚類(lèi)，據(jù)式（15）計(jì)算每個(gè)螞蟻選擇聚類(lèi)中心的概率，選擇概率最大的路徑。

step 6：調(diào)整路徑上含有的信息激素量，并將具有相同聚類(lèi)中心灰度值的連通區(qū)域合并。

step 7：如果所有螞蟻都聚類(lèi)完畢，結(jié)束循環(huán)，輸出分割閾值，利用二維Otsu法對(duì)圖像進(jìn)行分割，否則轉(zhuǎn)入step4。

4 結(jié)果及分析

為了驗(yàn)證本文方法的有效性，本文選擇256× 256的Lena圖像為源圖像，選擇加入噪聲的Lena圖像為分割對(duì)象，如圖1所示，為原始的Lena圖像和加噪聲的Lena圖像，圖像的灰度級(jí)為256，在Win7 PC上采用MATLAB仿真系統(tǒng)進(jìn)行試驗(yàn)。蟻群規(guī)模為30，最大迭代次數(shù)200，取R=10，a=b= 0.9，q=0.85。實(shí)驗(yàn)結(jié)果如圖2所示，分別為二維Otsu分割效果圖和本文分割方法效果圖。由實(shí)驗(yàn)結(jié)果可知，一維Otsu法分割的圖像受噪聲影響，分割效果差，本文分割方法與二位Otsu分割方法分割具有相同灰度分割閾值和鄰域灰度分割閾值，取得了相同的分割效果，但基于二位Otsu分割方法的分割時(shí)間為0.930 67 s，而本文方法的分割時(shí)間為0.525 39 s，由此可知雖然本文方法與Otsu分割方法分割效果相同，但本文方法在運(yùn)算時(shí)間上明顯較二維Otsu分割方法少，尋優(yōu)速度更快，有效地減少了分割時(shí)間，提高了分割效率，實(shí)驗(yàn)結(jié)果證實(shí)了本文方法的可行性和有效性。

圖1 實(shí)驗(yàn)原始圖像

圖2 實(shí)驗(yàn)分割圖像

5 總 結(jié)

Otsu閾值分割方法是一種分割效好、實(shí)現(xiàn)簡(jiǎn)單的閾值分割方法，二維Otsu閾值分割方式克服了一維Otsu分割方法抗噪聲能力弱的缺點(diǎn)。蟻群算法作為一種新興的優(yōu)化算法，將其應(yīng)用于圖像閾值分割時(shí)，縮短了尋找閾值的時(shí)間。本文將蟻群算法應(yīng)用于二維Otsu圖像分割中，實(shí)現(xiàn)了圖像的快速分割的同時(shí)又兼具了二維Otsu圖像分割抗噪性強(qiáng)、分割效果好的優(yōu)點(diǎn)，提高了運(yùn)算效率，減少了分割時(shí)間，能夠?yàn)閷?shí)施監(jiān)控系統(tǒng)提供快速有效的分割方法，也為大量的計(jì)算機(jī)圖像分割提供了可行性方法，提高分割效率，縮短工作時(shí)間。因此本文方法在計(jì)算機(jī)視覺(jué)系統(tǒng)中、實(shí)時(shí)監(jiān)控系統(tǒng)、圖像理解系統(tǒng)、機(jī)動(dòng)目標(biāo)跟蹤系統(tǒng)中有著廣闊的應(yīng)用前景。但本文方法在提高二維Otsu分割速度的同時(shí)，并沒(méi)有提高分割的效果，這點(diǎn)在以后的研究中有待進(jìn)一步的改進(jìn)。

［1］劉建莊，栗文清.灰度圖像的二維Otsu自動(dòng)閾值分割法［J］.自動(dòng)化學(xué)報(bào)，1993，19（1）：101-105.

［2］汪海洋，潘德?tīng)t，夏德深.二維Otsu自適應(yīng)閾值選取算法的快速實(shí)現(xiàn)［J］.自動(dòng)化學(xué)報(bào)，2007，33（9）：968-971.

［3］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem［J］.IFFF Trans on Fvolutionary Computation，1997，1（1）：53-66.

［4］宋世杰，劉高峰，周忠友，等.于改進(jìn)蟻群算法求解最短路徑和TSP問(wèn)題［J］.計(jì)算機(jī)技術(shù)與發(fā)展.2010（4）：144-147.

［5］白 楊，孫 躍，王 君，等.基于動(dòng)態(tài)自適應(yīng)蟻群算法的MRI圖像分割［J］.計(jì)算機(jī)科學(xué)，2008，35（12）：226-229.

［6］王 爽，黃友銳，李 冬.基于蟻群算法的改進(jìn)Otsu理論的圖像多閾值分割［J］.微計(jì)算機(jī)應(yīng)用，2008，3（3）：25-28.

［7］Wang L，Duan H C，Wang J L.A fast algorithm for three-dimensional Otsu's thresholding method［J］.IFFF International Symposium on IT in Medicine and Fducation，2008，2（8）：136-140.

［8］Chen Y F，Liu Y S，F(xiàn)attah C A.HDACC：a heuristic density-based ant colony clustering algorithm［C］// IFFF/W IC/ACM International Conference on Intelligent Agent Technology.2004，397-400.

［9］郝穎明，朱 楓.二維Otsu自適應(yīng)閾值的快速算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2005，10（4）：484-488.

［10］唐英干，劉 冬，關(guān)新平.基于粒子群和二維Otsu方法的快速圖像分割［J］.控制與決策，2007，22（2）：202-205.

［11］范九倫，趙 鳳.灰度圖像的二維Otsu曲線閾值分割法［J］.電子學(xué)報(bào)，2007，35（4）：751-755.

［12］吳一全，樊 軍，吳詩(shī)婳.改進(jìn)的二維Otsu法閾值分割快速迭代算法［J］.電子測(cè)量與儀器學(xué)報(bào)，2011，25（3）：218-225.

［13］胡 敏，李 梅，汪榮貴.改進(jìn)的Otsu算法在圖像分割中的應(yīng)用［J］.電子測(cè)量與儀器學(xué)報(bào)，2010，24（5）：443-449.

［14］楊海峰，侯朝禎.基于二維灰度直方圖的蟻群圖像分割［J］.激光與紅外，2005，35（8）：614-617.

［15］Stutzle T，Hoos H H.MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16（9）：889-914.

AppIication of Ant CoIony AIgorithm in Two-DimensionaI Otsu Image Segmentation

JIANGZhi1，DAI Wen-zhan2
（1.School of Mechanical Fngineering&Automation，Zhejiang Sci-Tech University，Hangzhou 310018；2.School of Information and Flectronic Fngineering，Zhejiang Gongshang University，Hangzhou 310018，China）

This pape proposes an image segmentation method based on ant colony algorithm and twodimensional Otsu and figures out threshold segmentation point of two-dimensional Otsu image to segment the image.Clustering is conducted according to source image，image grayscale after neighbor smoothing and grayscale frequency.The problems of ant colony algorithm（i.e.many operation times and large amount of calculation）are solved by using the peak point of gray histogram to set precise initial clustering center.According to the specific application，this paper corrects the cluster radius，pheromones and enlightening guiding function.The experiments show that the algorithm is fast and can accurately segment the target，with excellent segmentation property and strong anti-noise ability.

gray histogram；image segmentation；ant colony optimization；two-dimensional Otsu algorithm

TP273.2

A

（責(zé)任編輯：康 鋒）

1673-3851（2014）04-0434-05

2013-11-06

國(guó)家自然科學(xué)基金（61374022）；國(guó)家高新技術(shù)研究發(fā)展項(xiàng)目（2009AA04Z139）

姜 志（1988-），男，遼寧遼陽(yáng)人，碩士研究生，主要從事圖像處理等方面的研究。

戴文戰(zhàn)，F(xiàn)-mail：dwzhan@zstu.edu.cn