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

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

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

0 引言

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

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

1 圖像多閾值處理

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

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

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

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

1.1 類間方差法

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

(2)

(3)

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

1.2 Kapur熵方法

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

圖像的KE可以公式化為

(4)

(5)

2 傳統SI算法的多級閾值處理

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

(6)

(7)

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

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

圖1 傳統SI算法解決多級閾值問題的流程

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

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

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

圖2 PS算法工作過程示意

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

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

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

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

d.如果i

e.如果f(yD+1)

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

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

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

多級閾值處理本質上是一個受約束的組合優化問題，得到的可行解基本都是近似解。基于固定步長的IPS算法，可以提高局部搜索精度，增強其局部收斂性，能夠對可行解的逐步精細搜索，進而找到最優閾值。IPS算法在每次迭代中或許會增加SI算法的復雜度，但在搜索方向上有較強的指導作用，特別是在群體全局歷史最佳解決方案周圍進行了精細搜索，從而改進SI算法的優化性能。改進SI算法解決多級閾值問題的流程，如圖3所示。

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

4 實驗仿真與結果分析

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

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

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

表1 窮舉搜索得到最佳閾值和函數值

為了公平比較，相同大小的群體40(CS被設置為20，因為它們在每次迭代中評估目標函數2次)并且為所有算法設置最大迭代次數200。除了常見的控制參數外，其他參數對其性能也有很大影響，需要反復試驗來確保每個算法獲得相對較好的結果。對于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。

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

4.1 基于BCV的閾值處理

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

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

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

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

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

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

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

4.2 基于KE的閾值處理

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

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

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

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

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

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

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

5 結束語

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

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