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

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

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

0 引言

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

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

1 圖像多閾值處理

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

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

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

(1)

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

選擇用于雙級閾值處理的最佳閾值在計算上并不昂貴，而選擇用于多級閾值處理的最佳閾值隨著閾值的增加而在指數(shù)計算上是昂貴的。通常，閾值處理方法通過優(yōu)化一些標準函數(shù)(也稱為目標函數(shù))來搜索最佳閾值。在此，采用類方差(BCV)方法和Kapur熵(KE)方法作為本研究的重點[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算法的多級閾值處理

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

(6)

(7)

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

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

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

3 改進SI算法的多級閾值處理

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

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

圖2 PS算法工作過程示意

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

a.設(shè)定基點x1∈RD，D軸方向包括e1,e2,…,eD，初始步長為ρ，加速因子α≥1，減速比τ∈(0,1)，最小步長ρmin>0，同時設(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)，同時k∶=k+1，i=1，然后跳轉(zhuǎn)到步驟b。

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

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

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

圖3 改進SI算法解決多級閾值問題的流程

4 實驗仿真與結(jié)果分析

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

圖4 測試圖像與標準灰度直方圖

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

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

為了公平比較，相同大小的群體40(CS被設(shè)置為20，因為它們在每次迭代中評估目標函數(shù)2次)并且為所有算法設(shè)置最大迭代次數(shù)200。除了常見的控制參數(shù)外，其他參數(shù)對其性能也有很大影響，需要反復(fù)試驗來確保每個算法獲得相對較好的結(jié)果。對于PSO算法，慣性重量w=0.5，認知和社會成分c1=c2=2，最大速度限制為vmax=5；對于FA算法，β0=0.8，γ=1，α=0.006，Sk=Gend-Gstart，其中Gend和Gstart分別表示測試圖像的最大(終點)和最小(起點)的非零灰度值；對于CS算法，β=3/2，Pa=0.25。

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

4.1 基于BCV的閾值處理

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

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

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

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

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

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

綜上所述，考慮到搜索精度，穩(wěn)定性，收斂速度和成功搜索率，并且4個評估指標具有相同的權(quán)重，可以對基于BCV方法的比較算法的綜合性能排序為：IPS>CS>PSO>FA。

4.2 基于KE的閾值處理

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

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

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

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

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

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

同時，通過分析表5～表7，對基于KE方法的比較算法的綜合性能排序為：IPS>CS>PSO>FA。

5 結(jié)束語

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

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