基于群體智能算法的多級(jí)圖像閾值分割技術(shù)的研究

許韞韜，郭 錦，李曉艷，董綿綿，呂志剛，李亮亮

(西安工業(yè)大學(xué)電子信息工程學(xué)院，陜西 西安 710021)

0 引言

圖像分割作為圖像處理、視覺(jué)分析、模式識(shí)別中的基本步驟，廣泛應(yīng)用于字符識(shí)別、機(jī)器視覺(jué)、醫(yī)學(xué)圖像分析、軍事檢測(cè)等領(lǐng)域。在傳統(tǒng)的圖像分割算法中，包括基于邊緣檢測(cè)方法、基于區(qū)域分割方法、基于閾值分割方法等[1-3]?；陂撝档姆椒☉?yīng)用最為廣泛。然而，隨著閾值數(shù)量的增加，多閾值分割算法的實(shí)時(shí)性較差[4]。如何在不影響搜索精度的前提下提高實(shí)時(shí)性，是該算法研究的熱點(diǎn)問(wèn)題。

粒子群優(yōu)化算法(PSO)、螢火蟲算法(FA)、布谷鳥(niǎo)搜索(CS)算法等群體智能(SI)算法，能夠提高優(yōu)化過(guò)程的快速性和穩(wěn)定性，是解決圖像多閾值分割實(shí)時(shí)性差問(wèn)題的主要方法，但其搜索精度和實(shí)時(shí)性有待進(jìn)一步提高[5-11]。本文提出一種改進(jìn)的SI算法，采用固定步長(zhǎng)搜索策略，以提高群體智能算法在多級(jí)閾值上的性能。

1 圖像多閾值處理

多級(jí)閾值處理的目的是找出一個(gè)最佳閾值集T，以將像素分成幾個(gè)類。多級(jí)閾值處理本質(zhì)上是一種受約束的組合優(yōu)化問(wèn)題。

假設(shè)在給定圖像I中存在L個(gè)灰度級(jí)，則d閾值將其劃分為d+1個(gè)類，其可以通過(guò)數(shù)學(xué)描述為

Ck+1={I(i,j)∈I|tk≤I(i,j)≤tk+1-1}

(1)

I(i,j)為像素點(diǎn)(i,j)處的灰度級(jí)；tk(k=0,1,2,…,d)表示第k個(gè)閾值，同時(shí)t0=0,td+1=L,tk∈[0,L-1]。當(dāng)d=1時(shí)，它被稱為雙級(jí)閾值處理，也稱為二值化處理。當(dāng)d≥2時(shí)，T=(t0,t1,…,td+1)，顯然tk

選擇用于雙級(jí)閾值處理的最佳閾值在計(jì)算上并不昂貴，而選擇用于多級(jí)閾值處理的最佳閾值隨著閾值的增加而在指數(shù)計(jì)算上是昂貴的。通常，閾值處理方法通過(guò)優(yōu)化一些標(biāo)準(zhǔn)函數(shù)(也稱為目標(biāo)函數(shù))來(lái)搜索最佳閾值。在此，采用類方差(BCV)方法和Kapur熵(KE)方法作為本研究的重點(diǎn)[12-13]。

1.1 類間方差法

類方差法(BCV)之間由Otsu在1979年提出，也稱為Otsu方法或最大類間方差方法或最小類內(nèi)方差方法。BCV的基本思想是最佳閾值將圖像分割成具有最大BCV的區(qū)段。

(2)

(3)

max(·)表示尋找最大值，式(3)的含義是找出最佳參數(shù)T以使函數(shù)fBCV(T)最大化。

1.2 Kapur熵方法

熵是不確定性的度量，熵越大，不確定性越大。Kapur的熵(KE)方法也被稱為最大熵方法，由Kapur等人在1980年提出。KE的基本思想是較高熵的分布將具有較高的多重性，因此更可能被觀察到。

圖像的KE可以公式化為

(4)

(5)

2 傳統(tǒng)SI算法的多級(jí)閾值處理

Yang和Deb以數(shù)學(xué)方式提出了一種模擬Levy飛行的簡(jiǎn)單方法，其公式為

(6)

(7)

β和φ為常數(shù)；Γ(·)表示伽瑪分布；sin(·)代表正弦函數(shù)；randn(1,Dim)是一個(gè)隨機(jī)數(shù)；Step表示飛行步長(zhǎng)值。

在處理基于BCV和KE的多級(jí)閾值問(wèn)題時(shí)，不同的SI算法具有不同的迭代機(jī)制，分為探索和開(kāi)發(fā)2個(gè)階段，如何以及何時(shí)執(zhí)行2個(gè)階段將導(dǎo)致不同的優(yōu)化性能。以傳統(tǒng)CS算法為例，傳統(tǒng)CS算法解決多級(jí)閾值問(wèn)題的流程如圖1所示。

圖1 傳統(tǒng)SI算法解決多級(jí)閾值問(wèn)題的流程

3 改進(jìn)SI算法的多級(jí)閾值處理

盡管傳統(tǒng)的SI算法在某些優(yōu)化問(wèn)題中表現(xiàn)出良好的性能，但要滿足不同特定情況的要求還有很長(zhǎng)的路要走，尤其在大多數(shù)情況下找不到最優(yōu)閾值。基于“全局最優(yōu)解存在于眾多局部最優(yōu)解中”的假設(shè)，在傳統(tǒng)的SI算法中，采用模式搜索(PS)算法來(lái)設(shè)計(jì)改進(jìn)策略，以提高SI算法的探索能力，并進(jìn)一步優(yōu)化算法性能。

模式搜索算法由Hooke和Jeeves于1961年提出，也被稱為Hooke-Jeeves方法。PS的基本思想是找出一系列越來(lái)越接近最小函數(shù)值的點(diǎn)。PS從初始基點(diǎn)開(kāi)始，選擇基于軸的搜索方向進(jìn)行探索性移動(dòng)和模式移動(dòng)?；谳S的探索移動(dòng)可以提供一種策略來(lái)執(zhí)行基點(diǎn)周圍的精細(xì)搜索，同時(shí)模式移動(dòng)也被認(rèn)為是某種擺脫局部策略。模式搜索算法的模擬過(guò)程如圖2所示。

圖2 PS算法工作過(guò)程示意

在模式搜索算法中，“∶=”表示將右側(cè)表達(dá)式獲得的值賦給左側(cè)變量，其流程如下：

a.設(shè)定基點(diǎn)x1∈RD，D軸方向包括e1,e2,…,eD，初始步長(zhǎng)為ρ，加速因子α≥1，減速比τ∈(0,1)，最小步長(zhǎng)ρmin>0，同時(shí)設(shè)定y1=x1,k=1，i=1。

b.如果f(yi+ρ×ei)

c.如果f(yi-ρ×ei)

d.如果i

e.如果f(yD+1)

f.設(shè)定xk+1=yD+1,y1=xk+1+α×(xk+1-xk)，同時(shí)k∶=k+1，i=1，然后跳轉(zhuǎn)到步驟b。

g.如果ρ≤ρmin停止迭代，得到點(diǎn)xk；否則設(shè)定ρ∶=τ×ρ，y1=xk，xk+1=xk，同時(shí)k∶=k+1，i=1跳轉(zhuǎn)到步驟b。

在解決基于BCV的CS算法多級(jí)閾值問(wèn)題時(shí)，使用固定步長(zhǎng)模式搜索算法，重新尋找群體全局歷史最優(yōu)解附近的解，從而提高SI算法的局部性能。這種改進(jìn)的SI算法，稱為改進(jìn)的模式搜索(IPS)算法。

多級(jí)閾值處理本質(zhì)上是一個(gè)受約束的組合優(yōu)化問(wèn)題，得到的可行解基本都是近似解?；诠潭ú介L(zhǎng)的IPS算法，可以提高局部搜索精度，增強(qiáng)其局部收斂性，能夠?qū)尚薪獾闹鸩骄?xì)搜索，進(jìn)而找到最優(yōu)閾值。IPS算法在每次迭代中或許會(huì)增加SI算法的復(fù)雜度，但在搜索方向上有較強(qiáng)的指導(dǎo)作用，特別是在群體全局歷史最佳解決方案周圍進(jìn)行了精細(xì)搜索，從而改進(jìn)SI算法的優(yōu)化性能。改進(jìn)SI算法解決多級(jí)閾值問(wèn)題的流程，如圖3所示。

圖3 改進(jìn)SI算法解決多級(jí)閾值問(wèn)題的流程

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

本文以PSO、FA和CS 3種傳統(tǒng)SI算法以及改進(jìn)的SI算法IPS進(jìn)行比較，并在2幅圖像中進(jìn)行了實(shí)驗(yàn)。以KE和BCV作為適應(yīng)度目標(biāo)函數(shù)的閾值標(biāo)準(zhǔn)，首先采用窮舉搜索方法得到離線性能分析的最優(yōu)解，測(cè)試圖像及其標(biāo)準(zhǔn)灰度直方圖，如圖4所示。

圖4 測(cè)試圖像與標(biāo)準(zhǔn)灰度直方圖

然后利用SI算法尋找實(shí)驗(yàn)圖像的閾值，每個(gè)實(shí)驗(yàn)中的探索閾值數(shù)量為2～5，由于SI算法具有隨機(jī)性，因此對(duì)于每幅圖像和每個(gè)d值都進(jìn)行50次的仿真實(shí)驗(yàn)，表1中列出了由BCV和KE方法窮舉搜索提供的最佳閾值及其相應(yīng)的最佳目標(biāo)函數(shù)值。

表1 窮舉搜索得到最佳閾值和函數(shù)值

為了公平比較，相同大小的群體40(CS被設(shè)置為20，因?yàn)樗鼈冊(cè)诿看蔚性u(píng)估目標(biāo)函數(shù)2次)并且為所有算法設(shè)置最大迭代次數(shù)200。除了常見(jiàn)的控制參數(shù)外，其他參數(shù)對(duì)其性能也有很大影響，需要反復(fù)試驗(yàn)來(lái)確保每個(gè)算法獲得相對(duì)較好的結(jié)果。對(duì)于PSO算法，慣性重量w=0.5，認(rèn)知和社會(huì)成分c1=c2=2，最大速度限制為vmax=5；對(duì)于FA算法，β0=0.8，γ=1，α=0.006，Sk=Gend-Gstart，其中Gend和Gstart分別表示測(cè)試圖像的最大(終點(diǎn))和最小(起點(diǎn))的非零灰度值；對(duì)于CS算法，β=3/2，Pa=0.25。

在大多數(shù)情況下，每種SI算法運(yùn)行50次得到的最佳閾值彼此非常接近，尤其是當(dāng)閾值數(shù)量很小時(shí)，因此考慮采用SI算法在50次運(yùn)行中獲得的最差閾值來(lái)顯示視覺(jué)差異。而對(duì)于視覺(jué)差異不是那么顯著的，需要進(jìn)行量化的比較研究。對(duì)于第1幅圖和第2幅圖分別進(jìn)行基于BCV方法和基于KE方法的群體智能算法閾值分割，并通過(guò)每種算法的閾值均值、方差、平均收斂時(shí)間以及搜索成功率評(píng)估算法的綜合性能。均值可用于評(píng)估比較算法的搜索精度，方差可用于評(píng)估比較算法的穩(wěn)定性，平均收斂時(shí)間可用于評(píng)估比較算法的收斂速度，搜索成功率可用于預(yù)測(cè)算法在何種程度上可以找到最優(yōu)的概率閾值。

4.1 基于BCV的閾值處理

使用PSO、FA、CS和IPS優(yōu)化BCV方法，實(shí)質(zhì)上是優(yōu)化方程(3)的目標(biāo)函數(shù)。為了直觀地了解比較算法的分段差異，當(dāng)閾值數(shù)為5時(shí)，給出了用分段閾值標(biāo)記的分段圖像和灰度級(jí)直方圖，如圖5所示。均值和方差結(jié)果、平均收斂時(shí)間和搜索成功率結(jié)果分別如表2、表3和表4所示。

圖5 基于BCV方法的不同SI算法d=5時(shí)的圖像和直方圖

表2 基于BCV方法的不同SI算法搜索均值與方差

表3 基于BCV方法的SI算法搜索平均收斂時(shí)間

表4 基于BCV方法的SI算法搜索成功率

分析仿真結(jié)果可知：當(dāng)直方圖中沒(méi)有更多更突出的峰值，會(huì)導(dǎo)致BCV方法函數(shù)空間出現(xiàn)更多次有解，從而影響算法的性能；當(dāng)d=2時(shí)，所有算法都具有相同的性能，并在50次運(yùn)行中找到最佳結(jié)果；通常情況下IPS算法的收斂速度要比其他算法快，而當(dāng)d值變大時(shí)，PSO算法簡(jiǎn)單迭代機(jī)制和搜索處理有助于其更快的收斂速度；隨著閾值數(shù)量的增加，優(yōu)化問(wèn)題的復(fù)雜性增加，因此問(wèn)題處理起來(lái)要困難得多。每種算法的優(yōu)化性能變差，例如當(dāng)d=5時(shí)，所有算法都不能在50次重復(fù)實(shí)驗(yàn)中以100%的概率找到最優(yōu)結(jié)果。

綜上所述，考慮到搜索精度，穩(wěn)定性，收斂速度和成功搜索率，并且4個(gè)評(píng)估指標(biāo)具有相同的權(quán)重，可以對(duì)基于BCV方法的比較算法的綜合性能排序?yàn)椋篒PS>CS>PSO>FA。

4.2 基于KE的閾值處理

使用PSO、FA、CS和IPS優(yōu)化KE方法，實(shí)質(zhì)上是優(yōu)化方程(5)的目標(biāo)函數(shù)。重復(fù)4.1中的仿真實(shí)驗(yàn)，分段閾值標(biāo)記的分段圖像和灰度級(jí)直方圖，如圖6所示。均值和方差結(jié)果、平均收斂時(shí)間和搜索成功率結(jié)果分別如表5、表6和表7所示。

圖6 在基于KE方法的不同SI算法下d=5時(shí)的圖像和直方圖

表5 基于KE方法的不同SI算法搜索均值與方差

表6 基于KE方法的SI算法搜索平均收斂時(shí)間

表7 基于KE方法的SI算法搜索成功率

觀察表5～表7中的數(shù)據(jù)，并比較基于BCV方法的多級(jí)閾值處理中的相應(yīng)結(jié)果，可以類似于BCV方法得出結(jié)論：首先，當(dāng)閾值數(shù)量較小時(shí)，所有原算法都具有相似的優(yōu)化性能，隨著閾值數(shù)量的增加，優(yōu)化性能會(huì)逐漸下降；其次，如果直方圖不同，則優(yōu)化性能也不相同；此外，在閾值數(shù)d分別為2、3和4時(shí)，IPS算法具有較快的收斂速度，而當(dāng)d=5時(shí)，PSO的收斂速度明顯比其他比較算法快；最后，IPS算法搜索多級(jí)閾值的成功率要優(yōu)于其他算法。

同時(shí)，通過(guò)分析表5～表7，對(duì)基于KE方法的比較算法的綜合性能排序?yàn)椋篒PS>CS>PSO>FA。

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

隨著閾值數(shù)量的增加，傳統(tǒng)的閾值處理方法已不能滿足實(shí)時(shí)應(yīng)用的要求。目前，結(jié)合具有強(qiáng)大優(yōu)化能力的群體智能算法，基于一定的標(biāo)準(zhǔn)找到最優(yōu)閾值成為研究的熱點(diǎn)。在分析群體智能算法和模式搜索算法的機(jī)理后，提出了基于模式搜索策略的IPS算法，以提高群體智能算法在多級(jí)閾值上的性能。該策略是應(yīng)用步長(zhǎng)固定模式搜索算法，在每次迭代中重新利用群體智能算法的全局歷史最佳解決方案。在基于BCV方法和KE方法的多級(jí)閾值處理中，對(duì)比PSO、FA、CS和IPS 4種算法的搜索精度，穩(wěn)定性，收斂速度和成功搜索率進(jìn)行了比較研究。

結(jié)果表明，當(dāng)使用不同的閾值標(biāo)準(zhǔn)時(shí)，群體智能算法的性能不同。應(yīng)用所提出的策略后，IPS算法不僅具有良好的全局探索和局部?jī)?yōu)化，而且在基于BCV方法和KE方法的多級(jí)閾值處理方面具有優(yōu)越的綜合性能。