基于馮諾依曼鄰居的粒子群多閾值分割算法

(重慶大學(xué) 計(jì)算機(jī)學(xué)院 重慶400044)

摘 要：針對(duì)多閾值分割問(wèn)題，提出了一種新的多閾值分割算法。該算法對(duì)傳統(tǒng)的Otsu進(jìn)行修改，使其能夠更準(zhǔn)確地找到直方圖中谷的位置；并利用馮諾依曼拓?fù)溧従恿Ｗ尤鹤鳛殚撝祪?yōu)化算法，提高了優(yōu)化性能。提出了構(gòu)造馮諾依曼拓?fù)浣Y(jié)構(gòu)的方法，并分析和比較了它與全互連結(jié)構(gòu)的差別。實(shí)驗(yàn)結(jié)果顯示此算法具有較好的性能。

關(guān)鍵詞：馮諾依曼鄰居; 粒子群優(yōu)化； 多閾值分割

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)05-1977-03

Image multi-level thresholds based on PSO with Von Neumann neighborhood

CHEN Zi-yu HE Zhong-shi ZHANG Cheng

(College of Computer Science Chongqing University Chongqing 400044 China)

Abstract:As for image multilevel thresholding this paper proposed a novel algorithm. With modified Otsu method the algorithm could get good thresholds by correctly finding the valley of image histogram. Based on particle swarm optimization with Von Neumann neighborhood the algorithm improved the optimization performance. Also described a way to build Von Neumann structure and compared its performance with global topology. Experimental results show that the proposed algorithm is promising and outperforms some existing techniques.

Key words：Von Neumann neighborhood; particle swarm optimization (PSO); multilevel thresholding

圖像分割是數(shù)字圖像處理中最重要的技術(shù)之一，也是模式識(shí)別領(lǐng)域的重要組成部分。圖像分割的目的是依據(jù)圖像的特征將圖像劃分成不同的區(qū)域。在眾多分割技術(shù)中，閾值分割由于其簡(jiǎn)單、快速得到了最廣泛的應(yīng)用。

閾值分割技術(shù)分為四部分：a）圖像特征模型；b）數(shù)學(xué)模型；c）優(yōu)化（判別）標(biāo)準(zhǔn)；d）優(yōu)化算法。根據(jù)這四部分的不同選擇，形成了不同的閾值分割算法。

圖像特征模型是閾值分割的基礎(chǔ)。在現(xiàn)有的閾值分割技術(shù)中，大多采用圖像的像素灰度屬性和像素位置關(guān)系作為特征。圖像的灰度分布直方圖是最典型的圖像特征模型，如Otsu方法^[1]、ME閾值法^[2]等均采用這種模型。其他特征模型包括采用空間關(guān)系的特征模型^[3，4]、采用圖像局部特征作為分割依據(jù)^[5，6]的局部特征模型等。數(shù)學(xué)模型和優(yōu)化標(biāo)準(zhǔn)是在圖像特征模型的基礎(chǔ)上獲得閾值的方法，是閾值分割的關(guān)鍵。它們的作用是用數(shù)學(xué)方法描述特征模型。例如采用高斯模型模擬直方圖或直接使用直方圖的形狀特征將其轉(zhuǎn)換為數(shù)學(xué)問(wèn)題，再采用優(yōu)化標(biāo)準(zhǔn)，如類方差最小^[1，7]、最大熵或交叉熵^[8，9]、聚類^[4，10]等方法最終得到結(jié)果。早期的閾值分割大都是二值分割，即單閾值分割。隨著圖像應(yīng)用的多樣化，出現(xiàn)了多閾值分割技術(shù)。然而，隨著閾值級(jí)別的增加，通過(guò)窮舉的方法得到多個(gè)閾值無(wú)法在有限時(shí)間內(nèi)完成，所以需要采用優(yōu)化算法來(lái)得到最佳閾值。目前有很多優(yōu)化算法已應(yīng)用于多閾值分割中，如遺傳算法、模擬退火等^[11]。粒子群算法^[12]是其中較新的優(yōu)化算法，由于其思想簡(jiǎn)單、操作方便，近幾年受到了人們廣泛的關(guān)注。

本文以O(shè)tsu方法為基礎(chǔ)，采用相對(duì)類方差最小作為優(yōu)化標(biāo)準(zhǔn)，并使用馮諾依曼鄰居作為粒子群的社會(huì)認(rèn)知結(jié)構(gòu)，實(shí)現(xiàn)了一個(gè)新的多閾值分割算法。此算法解決了Otsu類方差法不能準(zhǔn)確定位谷值、對(duì)小對(duì)象分割效果差的缺點(diǎn)，較好地改進(jìn)了傳統(tǒng)粒子群算法易陷入局部最優(yōu)的弱點(diǎn)，但仍保持了較好的收斂能力。

1 類內(nèi)方差法

1.1 Otsu

Otsu方法關(guān)于最佳閾值的定義是使類內(nèi)方差的加權(quán)和最小的閾值。其中權(quán)是指各種概率。設(shè)σ2W(t)是類內(nèi)方差的加權(quán)和；σ21(t)是值小于等于t(稱為第一類)的類方差，σ22(t)是值大于t(稱為第二類)的類方差；q1(t)是值小于等于t的類概率，q2(t)是值大于t的類概率；μ1(t)是第一類的均值，μ2(t)是第二類的均值。類內(nèi)方差的加權(quán)和定義為

2(t)]2P(i)/q2(t)

簡(jiǎn)單地順序搜索所有可能的值，得到使σ2W(t)最小的最佳值：t=argmint{σ2W(t)}。基于直方圖閾值方法的基本原理是找到直方圖中兩峰之間的谷作為閾值，然而Otsu方法并不能很好地找到直方圖的谷，它選擇的閾值偏向于方差大的類，也就是說(shuō)Otsu方法不能處理小對(duì)象的分割，因此采用了修改的Otsu，使其不僅保留原有Otsu的特點(diǎn)，并能夠較準(zhǔn)確地發(fā)現(xiàn)直方圖的谷，較好地解決了小對(duì)象的分割。

1.2 修改的Otsu

從式（2）（3）可以看到，Otsu算出的結(jié)果是絕對(duì)類方差和，而修改后的Otsu對(duì)于每個(gè)類

方差均除以它的類概率，它得到的是相對(duì)類方差和，更準(zhǔn)確地描述了兩個(gè)類之間的關(guān)系。

2 馮諾依曼鄰居的粒子群算法

前面介紹過(guò)閾值分割實(shí)質(zhì)是一個(gè)優(yōu)化問(wèn)題，尤其是多閾值分割，其計(jì)算量很大無(wú)法采用窮舉所有的可能解，必須采用優(yōu)化算法幫助其找到最佳解，這里采用的是粒子群算法。然而傳統(tǒng)的粒子群算法優(yōu)化效果并不理想，所以使用馮諾依曼鄰居作為粒子群的社會(huì)拓?fù)浣Y(jié)構(gòu)，得到了較好的結(jié)果。

2.1 基本粒子群算法

粒子群優(yōu)化算法（PSO）是由Kennedy等人^[12]1995年提出的一種進(jìn)化計(jì)算技術(shù)，是進(jìn)化計(jì)算領(lǐng)域的一個(gè)新的分支，其源于鳥群和魚群群體運(yùn)動(dòng)行為的研究。基本原理如下：

粒子群由M個(gè)運(yùn)動(dòng)的粒子組成，每個(gè)粒子i由四個(gè)元素決定其t+1時(shí)刻的運(yùn)動(dòng)路線：粒子i在t時(shí)刻的運(yùn)動(dòng)速度Vi(t)；粒子在t時(shí)刻的位置Xi(t)；粒子i在t時(shí)刻的歷史最佳位置pBesti(t)；粒子i的鄰居粒子在t時(shí)刻的最佳位置lBesti(t)。粒子i在t+1時(shí)刻的運(yùn)動(dòng)速度和所處位置為

其中：f(X)是適應(yīng)度函數(shù)，即判斷位置X的優(yōu)劣標(biāo)準(zhǔn)。這里假設(shè)使適應(yīng)度函數(shù)值最小的位置為最佳位置。慣性系數(shù)w用于控制粒子原有速度對(duì)新速度的影響。參數(shù)c1、c2分別決定粒子個(gè)人歷史最佳位置和粒子鄰居最佳位置對(duì)新速度的影響。Rand1、rand2為（0，1）的任意值。為了防止粒子飛出搜索空間，約定Vi≤Vmax或Xi≤Xmax。當(dāng)達(dá)到限定的時(shí)刻或每個(gè)粒子的運(yùn)動(dòng)速度趨于零（即整個(gè)粒子群收斂），粒子群停止運(yùn)動(dòng)，所得的位置為最佳結(jié)果。

從式（4）可以看出，每個(gè)粒子通過(guò)三個(gè)方面來(lái)改變自己的位置： a）原有速度；b）自己的歷史最佳位置，即自我認(rèn)知；c）粒子鄰居的最佳位置，即社會(huì)認(rèn)知。

社會(huì)認(rèn)知結(jié)構(gòu)直接影響到整個(gè)粒子群的尋優(yōu)能力和收斂性。

2.2 馮諾依曼鄰居的粒子群算法

在基本粒子群算法中，社會(huì)認(rèn)知結(jié)構(gòu)是一種星型結(jié)構(gòu)或全互連結(jié)構(gòu)（記為gBest PSO），如圖1所示。在這種結(jié)構(gòu)中，粒子的鄰居由粒子群中的其他所有粒子組成。因此，一個(gè)粒子找到較好的解將吸引整個(gè)粒子群中的粒子向它的位置靠攏。這樣就限制了其他粒子尋找最佳位置的可能性，很容易陷于局部最優(yōu)，然而這種結(jié)構(gòu)收斂較快。

不同于全互連結(jié)構(gòu)，馮諾依曼拓?fù)浣Y(jié)構(gòu)（圖2）中每個(gè)粒子有上、下、左、右四個(gè)鄰居，當(dāng)一個(gè)粒子找到較好解時(shí)，只直接影響它的四個(gè)鄰居，這樣可以維持其他粒子位置的多樣性，使得粒子群的粒子向幾個(gè)較優(yōu)的位置靠攏，最終找到更優(yōu)的解。這種結(jié)構(gòu)不易陷入局部最優(yōu)，收斂性也較快。

為了使得M個(gè)粒子形成馮諾依曼拓?fù)浣Y(jié)構(gòu)，采用了如下的構(gòu)造方法：

a）對(duì)于M個(gè)粒子按照rows行、cols列排列，M=rows×cols。

b）對(duì)于第i個(gè)粒子，i∈{1，2，…，M}：

(a) 上鄰居為Ni(1)=(i-cols) modM，如果Ni(1)==0，Ni(1)=M；

(b) 左鄰居為Ni(2)=i-1，如果(i-1) mod cols==0，Ni(2)=i-1+cols； (c) 右鄰居為Ni(3)=i+1，如果i mod cols==0，Ni(3)=i+1-cols；

(d) 下鄰居為Ni(4)=(i+cols)mod M，如果Ni(4)==0，Ni(4)=M。

注意對(duì)負(fù)數(shù)的mod運(yùn)算，(-5) mod 20=15。

表1顯示了用此方法構(gòu)造的馮諾依曼拓?fù)浣Y(jié)構(gòu)和全互連結(jié)構(gòu)在圖屬性上的性能比較（其中：M=20，rows=4，cols=5）。對(duì)于粒子群的社會(huì)認(rèn)知結(jié)構(gòu)來(lái)說(shuō)，粒子（節(jié)點(diǎn)）的度數(shù)決定了此粒子的影響范圍，平均度數(shù)越大越易早熟，而粒子（節(jié)點(diǎn)）間路徑長(zhǎng)度往往決定了整個(gè)粒子群的收斂速度，長(zhǎng)度越小收斂越快，然而這兩個(gè)參數(shù)又互相制約。馮諾依曼拓?fù)浣Y(jié)構(gòu)對(duì)此有較好的平衡。另外，筆者發(fā)現(xiàn)用上述方法構(gòu)造的馮諾依曼拓?fù)浣Y(jié)構(gòu)，其節(jié)點(diǎn)間最大路徑長(zhǎng)度為dmax=rows/2」+cols/2」也就是說(shuō)對(duì)于相同的粒子數(shù)M，選擇合適的行數(shù)和列數(shù)可以減少路徑長(zhǎng)度，從而提高收斂速度。

3 馮諾依曼鄰居的粒子群多閾值分割算法

首先，將修改后的Otsu推廣到多閾值，其判別式如下：

值最小的位置）。

f）按照式（4）（5）修改粒子的速度和位置。

g）對(duì)新位置XL-1M排序，使其符合式（10）的約束條件。

h）按照NV(M)和式（6）~（9）重新計(jì)算每個(gè)粒子的pBesti和lBesti找到最佳的lBesti，即為所得結(jié)果。

4 實(shí)驗(yàn)

1） 實(shí)驗(yàn)一 為了驗(yàn)證修改后的Otsu方法對(duì)于小對(duì)象分割的有效性，用它與Otsu分別對(duì)經(jīng)典圖像F14 進(jìn)行了二值化分割（圖3）。

從圖3(a)可以看到，其直方圖大體分兩類，然而這兩類的面積差距很大，直方圖谷的位置大約在70；(c)（t=137）和(d)（t=59）分別顯示了這兩種方法所得到的分割結(jié)果。顯然，修改后的Otsu較準(zhǔn)確地將原圖中的F14飛機(jī)分割出來(lái)，而Otsu方法分割效果較差，而且修改后的Otsu所得到的閾值更接近直方圖谷的位置。

2） 實(shí)驗(yàn)二 為了比較馮諾依曼鄰居粒子群（vBest）和全互連結(jié)構(gòu)粒子群（gBest）優(yōu)化算法的性能，以經(jīng)典圖像Lena為例，分別用它們對(duì)該圖像進(jìn)行4~10級(jí)別的多閾值分割。參數(shù)設(shè)置為M=20，w=0.729 84，c1=c2=1.5，循環(huán)次數(shù)為1 000，每種算法運(yùn)行100遍。表2、3分別列出了這兩種方法在尋優(yōu)能力和收斂性上的性能。其中表2的最優(yōu)閾值是兩種方法得到的共同最優(yōu)值。

從表2可以看到，隨著閾值級(jí)別的增加（即維數(shù)的增加），gBest的性能遠(yuǎn)低于vBest；表3也說(shuō)明了gBest的收斂速度比vBest要快，這與前面分析的結(jié)果相同。同時(shí)也看到vBest具有較好的收斂速度。表4展示了兩種算法的綜合性能對(duì)比。與gBest對(duì)比，vBest以增加9.46%的循環(huán)次數(shù)為代價(jià)，換取了增加25.9%的命中率。另外筆者發(fā)現(xiàn)，如果對(duì)粒子的每一維分別取隨機(jī)數(shù)，則會(huì)得到更好的命中率，但是收斂速度將變得較慢。

5 結(jié)束語(yǔ)

圖像多閾值分割具有重要的研究意義和實(shí)用價(jià)值，它不僅幫助實(shí)現(xiàn)對(duì)象的識(shí)別，而且有利于圖像的壓縮處理，是目前的研究熱點(diǎn)之一。對(duì)于閾值分割大多是基于圖像的灰度分布直方圖，Otsu是其中最流行實(shí)用的一種方法。但是Otsu方法利用絕對(duì)類方差得到的閾值往往偏向于類方差大的對(duì)象，所以并不能準(zhǔn)確地找到直方圖中谷的位置，尤其對(duì)于小對(duì)象的分割效果很不理想。本文采用相對(duì)類方差計(jì)算圖像的閾值，能夠較好地找到谷值，并且對(duì)小對(duì)象的分割有較好的結(jié)果。在多閾值優(yōu)化算法中，利用馮諾依曼拓?fù)浣Y(jié)構(gòu)作為粒子群的社會(huì)鄰居得到了比基本粒子群算法更好的優(yōu)化結(jié)果。本文給出了構(gòu)造馮諾依曼鄰居的方法并分析了其性能。對(duì)于啟發(fā)式優(yōu)化算法，大多都具有隨機(jī)性，所以筆者建議用此類算法時(shí)最好使用具有較好尋優(yōu)能力且收斂較快的方法。馮諾依曼鄰居粒子群算法就是一個(gè)不錯(cuò)的選擇。

參考文獻(xiàn)：

［1］OTSU N. A threshold selection method from gray-level histograms[J]. IEEE Trans on Systems Man and Cybernetics 19769(1):62-66.

［2］KITTLER J ILLINGWORTH J. Minimum error thresholding[J]. Pattern Recognition 198619(1): 41-47.

［3］ABUTALEB A S. Automatic thresholding of grey-level pictures using two-dimensional entropy[J].Computer Vision Graphics，and Image Processing 198347(1): 22-32.