基于量子粒子群優(yōu)化算法的圖像分割方法*

黃洋文，王紅亮

（中北大學(xué) 電子測試技術(shù)國家重點實驗室；儀器科學(xué)與動態(tài)測試教育部重點實驗室，山西 太原 030051）

1 引言

圖像分割是圖像識別和圖像理解的基礎(chǔ)。所謂圖像分割就是將圖像依據(jù)一定的準(zhǔn)則劃分為目標(biāo)部分（人們感興趣的特征部分）和背景部分。目前，圖像分割方法主要有閾值法、聚類法、邊緣檢測法等[1-4]。其中閾值法由于其簡單性和有效性從而得到廣泛的應(yīng)用。目前已提出的閾值法有Otsu法、最大熵法、Fisher準(zhǔn)則函數(shù)法、迭代分割法以及這些方法在基于二維直方圖上的推廣等。著名的Otsu法通過最大化圖像中目標(biāo)和背景的類間方差來選取最佳閾值，方法簡單，且對大部分圖像分割效果較好；缺點是在圖像信噪比較低或目標(biāo)太小的情況下分割效果不佳。最大熵法通過最大化圖像中目標(biāo)與背景分布的信息量來選取最佳閾值選；缺點是在圖像中目標(biāo)和背景對比度較小情況下會造成明顯錯分類[1]?；谝痪SFisher準(zhǔn)則函數(shù)的分割算法受目標(biāo)和背景的比例影響小，能有效識別出與背景比例懸殊的小目標(biāo)，分割精度高[2]。由于二維直方圖在一維直方圖的基礎(chǔ)上增加了對圖像中各像素點鄰域的描述，基于二維直方圖的圖像分割算法效果會更好。文獻(xiàn)[5]提出了二維Fisher準(zhǔn)則函數(shù)算法。該算法受目標(biāo)和背景比例影響小，具有很好的應(yīng)用價值，但存在效率低的缺點，需要選擇一種優(yōu)化算法求得最佳閾值，來減少運算時間。

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法是一種基于種群搜索的智能計算方法。量子粒子群優(yōu)化算法（Quantum Particle Swarm Optimization，QPSO）[6]是把量子理論應(yīng)用于PSO算法而提出的改進(jìn)的粒子群優(yōu)化算法，較PSO算法更加簡單、易實現(xiàn)，且收斂速度更快。

筆者將二維Fisher準(zhǔn)則函數(shù)和量子粒子群優(yōu)化算法相結(jié)合應(yīng)用于圖像分割，并針對量子粒子群優(yōu)化算法存在收斂性差、易早熟的問題，對量子粒子群優(yōu)化算法進(jìn)行改進(jìn)，取得了很好的實驗效果。

2 量子粒子群優(yōu)化算法

由于粒子群優(yōu)化算法存在早熟趨勢，不能保證以概率1搜索到全局最優(yōu)解，許多學(xué)者采用各種方法來解決這一問題。2004年Sun等從量子力學(xué)的角度提出了一種新的粒子群優(yōu)化算法模型[6－7]。它通過量子態(tài)來描述粒子，使得算法可以在整個可行解空間中進(jìn)行搜索，大大提高了算法的全局搜索能力。該算法主要可以描述為：在量子空間中，粒子的速度和位置是不能同時確定的，粒子的狀態(tài)通過波函數(shù)ψ（x，t）來描述，并通過求解薛定諤方程得到粒子在空間某一點出現(xiàn)的概率密度函數(shù)[8]。隨后通過蒙特卡羅隨機(jī)模擬的方式得到粒子的位置方程。主要迭代公式有

式中：φ和u為[0，1]范圍內(nèi)的隨機(jī)數(shù)。β為收縮擴(kuò)張系數(shù)，它是量子粒子群優(yōu)化算法中的一個重要參數(shù)，第T次迭代時一般可取 β=0.5+0.5×（Tmax－T）/Tmax；Tmax為最大迭代次數(shù)。

3 改進(jìn)算法

3.1 二維Fisher準(zhǔn)則函數(shù)算法原理

設(shè)圖像灰度級為L，定義pij為灰度為i且其鄰域灰度均值為j的像素的發(fā)生概率，將pij分別向i，j兩個坐標(biāo)軸投影，分別用 H（i）和 W（j）表示，則

定義（μ0i，μ0j）和（μ1i，μ1j）分別表示 ω1（背景類）和 ω2（目標(biāo)類）在 i，j坐標(biāo)軸上投影的均值，分別表示ω1和ω2在i，j坐標(biāo)軸上投影的方差，則根據(jù)Fisher準(zhǔn)則函數(shù)的定義，可以推導(dǎo)出圖像分割的二維Fisher準(zhǔn)則函數(shù)為

在二維直方圖上選擇不同的（s，t），當(dāng) JF（s，t）最大時，即為最佳分割閾值[9]。

3.2 基于QPSO的二維Fisher準(zhǔn)則函數(shù)算法

以二維Fisher準(zhǔn)則函數(shù)作為量子粒子群優(yōu)化算法的適應(yīng)度函數(shù)，根據(jù)它的大小選擇個體極值和全體極值，不斷地更新粒子，最終求得全局最大值及其對應(yīng)的粒子位置。具體的流程如下：

1）粒子群規(guī)模為N，隨機(jī)對微粒群各微粒的初始位置（256級灰度中的某個灰度值）進(jìn)行設(shè)定。

2）利用式（6）計算每個粒子的適應(yīng)度，同時根據(jù)適應(yīng)值選取每個粒子的個體最優(yōu)Pid以及粒子群的全體最優(yōu)Pgd。

3）計算式（1），（2）和（3）以更新粒子的位置，同時利用式（6）計算適應(yīng)度。對每個粒子，比較其適應(yīng)度與個體最優(yōu)Pid的適應(yīng)度，若較大，則將其作為個體最優(yōu)Pid；對每個粒子，比較其個體最優(yōu)Pid的適應(yīng)度與全體最優(yōu)Pgd的適應(yīng)度，若較大，則將其作為全體最優(yōu)Pgd。

4）如果全體最優(yōu)Pgd在一定的迭代次數(shù)內(nèi)變化都小于所設(shè)定的允許誤差或者總迭代次數(shù)超過所設(shè)定的最大值，則算法結(jié)束，全體最優(yōu)Pgd對應(yīng)的就是最佳閾值；否則轉(zhuǎn)到步驟3）繼續(xù)迭代。

5）利用所得到的最佳閾值對各像素點進(jìn)行分類。

3.3 改進(jìn)的算法

雖然量子粒子群優(yōu)化算法比粒子群優(yōu)化算法具有更強(qiáng)的全局搜索能力，但它仍存在一定的早熟趨勢；文獻(xiàn)[10]采用多樣性控制模型來解決這一問題，但多樣性控制模型的部分參數(shù)無法自動設(shè)定到最佳值，這使得該算法的應(yīng)用受到了限制；而且該算法以增加迭代次數(shù)為代價，降低了收斂速度。針對其不足，提出了量子粒子群優(yōu)化算法和鄰域搜索雙重尋優(yōu)的改進(jìn)算法。改進(jìn)后的算法流程為：

1）將粒子群各微粒的初始位置進(jìn)行平均分布。定義待分割圖像中出現(xiàn)的最大像素值為Imax，最小像素值為Imin，粒子群規(guī)模為N，則粒子群第i個微粒的初始位置由下式計算得到

2）利用量子粒子群優(yōu)化算法進(jìn)行快速粗略尋優(yōu)?？梢酝ㄟ^適當(dāng)?shù)乜s小粒子群規(guī)模和降低終止條件的要求來快速求得次優(yōu)值Jgd及其對應(yīng)的粒子位置Pgd。

3）通過鄰域搜索，查找最優(yōu)值。定義n為鄰域搜索有效步數(shù)，N為鄰域搜索最大有效步數(shù)。它主要包括以下幾步：

（1）求Pgd的右鄰位置Pgd+1對應(yīng)的適應(yīng)值Jgd+1，求Pgd的左鄰位置Pgd-1對應(yīng)的適應(yīng)值Jgd-1，進(jìn)行如下的雙鄰搜索（包括右鄰搜索和左鄰搜索）。

（2）右鄰搜索：若在右鄰位置尋得更優(yōu)值，即Jgd+1＞Jgd，則終止左鄰搜索，并令 Jgd=Jgd+1，Pgd=Pgd+1，n=0。然后繼續(xù)右鄰搜索。若Jgd+1＜Jgd，則n=n+1，然后將Pgd+2作為新的右鄰，繼續(xù)右鄰搜索。

（3）左鄰搜索：若在左鄰位置尋得更優(yōu)值，即Jgd－1＞Jgd，則終止右鄰搜索，并令 Jgd=Jgd－1，Pgd=Pgd－1，n=0。 然后繼續(xù)左鄰搜索。 若 Jgd－1＜Jgd，則 n=n+1，然后將 Pgd－2作為新的左鄰，繼續(xù)左鄰搜索。

（4）依次搜索，當(dāng)連續(xù)N次鄰域搜索都無更優(yōu)值時，即n≥N，終止搜索。此時的Jgd為最優(yōu)值，Pgd為最優(yōu)位置。

4 實驗結(jié)果和分析

為了驗證算法的有效性，在Petium 2.5 GHz的PC上，利用VC++6.0編寫代碼實現(xiàn)二維Otsu法、二維Fisher準(zhǔn)則函數(shù)算法、基于量子粒子群優(yōu)化算法的二維Fisher準(zhǔn)則函數(shù)算法和本文算法等3種算法，并做了大量實驗，總結(jié)如下：

1）實驗對象為256級的灰度圖像。兩種算法的部分參數(shù)作如下設(shè)定：基于量子粒子群優(yōu)化算法的二維Fisher準(zhǔn)則函數(shù)算法的粒子群規(guī)模設(shè)定為10，終止條件為全體最優(yōu)Pgd在連續(xù)3次迭代內(nèi)無變化或總迭代次數(shù)達(dá)到20次。本文算法的粒子群規(guī)模設(shè)定為5，量子粒子群優(yōu)化算法的終止條件為全體最優(yōu)Pgd在連續(xù)1次迭代內(nèi)無變化或總迭代次數(shù)達(dá)到20次。鄰域搜索最大有效步數(shù)N設(shè)定為2。

2）選用一幅經(jīng)過濾波和增強(qiáng)的紅外圖像作為實驗對象，如圖1所示。

圖1 兩種算法分割效果圖

圖1b中的錯分點明顯多于圖1c的錯分點，可見在分割效果上二維Fisher準(zhǔn)則函數(shù)算法優(yōu)于二維Otsu法。這主要是因為前者不僅考慮了目標(biāo)和背景的類間方法最大，還考慮了目標(biāo)和背景的類內(nèi)方差最小，更不易受目標(biāo)和背景的比例影響，分割精度更高。

3）選取3幅經(jīng)過濾波和增強(qiáng)的紅外圖像作為實驗對象，對每幅圖像進(jìn)行10次實驗。對于二維Fisher準(zhǔn)則函數(shù)，分別采用二維Fisher準(zhǔn)則函數(shù)算法（窮舉法）、基于量子粒子群優(yōu)化算法的二維Fisher準(zhǔn)則函數(shù)算法（QPSO）和本文算法求得最大值，結(jié)果見表1，其中的達(dá)優(yōu)數(shù)是指運行結(jié)果和窮舉法結(jié)果相同的次數(shù)。

表1 3種算法圖像分割結(jié)果分析

從表1可以看出，在相同條件下分割3幅圖像，QPSO的計算總時間約為窮舉法的52.0%，而本文算法的計算總時間約為窮舉法的29.8%。這說明QPSO和本文算法都可以有效提高分割速度，且本文算法速度更快。另外，本文算法的達(dá)優(yōu)率為100%，而QPSO的平均達(dá)優(yōu)率僅為26.7%。這說明本文算法可以有效避免QPSO早熟，提高了全局搜索能力，保證了算法的穩(wěn)定性和計算精度。

5 小結(jié)

二維Fisher準(zhǔn)則函數(shù)算法是一種有效的圖像分割方法，它結(jié)合了二維直方圖和Fisher準(zhǔn)則函數(shù)的優(yōu)點，既考慮樣本類內(nèi)和類間離散度，又考慮像素間的空間鄰域信息。在對低信噪比圖像和小目標(biāo)分割時效果優(yōu)于二維Otsu法。而量子粒子群優(yōu)化算法是一種參數(shù)簡潔、流程簡單易實現(xiàn)、收斂速度快的群體智能算法。因此，利用量子粒子群優(yōu)化算法對二維Fisher準(zhǔn)則函數(shù)進(jìn)行快速尋優(yōu)具有重要意義。但由于量子粒子群優(yōu)化算法存在收斂性差、易早熟的問題，限制了它的應(yīng)用。而筆者針對這一不足，對量子粒子群優(yōu)化算法進(jìn)行了改進(jìn)，提出利用量子粒子群優(yōu)化算法和鄰域搜索法進(jìn)行雙重尋優(yōu)。實驗證明，改進(jìn)后的分割方法能夠取得很好的分割效果和計算速度，有效并且實用。

[1]張莎莎，谷延鋒，張鈞萍，等.一種基于量子遺傳算法的紅外圖像分割方法[J].哈爾濱工業(yè)大學(xué)學(xué)報，2007，39（9）：1427-1428.

[2]陳果.圖像閾值分割的Fisher準(zhǔn)則函數(shù)法[J].儀器儀表學(xué)報，2003，24（6）：564-567.

[3]楊潤玲，周軍妮，劉利.基于改進(jìn)型FCM聚類的圖像分割新方法[J].電視技術(shù)，2008，32（6）：12-14.

[4]曹世康，郭寶龍，符祥.基于時空信息融合的視頻對象分割系統(tǒng)[J].電視技術(shù)，2007，31（1）：17-19.

[5]童瑩，邱曉暉.基于Fisher準(zhǔn)則函數(shù)的二維閾值圖像分割算法[J].電力系統(tǒng)通信，2004（9）：36-39.

[6]SUN Jun，F(xiàn)ENG Bin，XU Wen-bo.Particle swarm optimization with particles having quantum behavior[C]//Proc.Congress on Evolutionary Computation.[S.l.]：IEEE Press，2004：325-331.

[7]SUN J，XU W B.A global search strategy of quantum-behaved particle swarm optimization[C]//Proc.IEEE Conference on Cybernetics and Intelligent Systems.Singapore：IEEE Press，2004：111-116.

[8]汪筱紅.基于QPSO的圖像分割算法[J].合肥工業(yè)大學(xué)學(xué)報，2008，31（7）：1088-1091.

[9]張懷柱，向長波，宋建中.改進(jìn)的遺傳算法在實時圖像分割中的應(yīng)用[J].光學(xué)精密工程，2008，16（2）：333-335.

[10]孔麗丹，孫俊，須文波.基于全局層次的自適應(yīng)QPSO算法[J].計算機(jī)工程與應(yīng)用，2007，43（26）：50-53.