基于量子粒子群優化算法的圖像分割方法*

黃洋文，王紅亮

（中北大學 電子測試技術國家重點實驗室；儀器科學與動態測試教育部重點實驗室，山西 太原 030051）

1 引言

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

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

筆者將二維Fisher準則函數和量子粒子群優化算法相結合應用于圖像分割，并針對量子粒子群優化算法存在收斂性差、易早熟的問題，對量子粒子群優化算法進行改進，取得了很好的實驗效果。

2 量子粒子群優化算法

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

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

3 改進算法

3.1 二維Fisher準則函數算法原理

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

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

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

3.2 基于QPSO的二維Fisher準則函數算法

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

1）粒子群規模為N，隨機對微粒群各微粒的初始位置（256級灰度中的某個灰度值）進行設定。

2）利用式（6）計算每個粒子的適應度，同時根據適應值選取每個粒子的個體最優Pid以及粒子群的全體最優Pgd。

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

4）如果全體最優Pgd在一定的迭代次數內變化都小于所設定的允許誤差或者總迭代次數超過所設定的最大值，則算法結束，全體最優Pgd對應的就是最佳閾值；否則轉到步驟3）繼續迭代。

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

3.3 改進的算法

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

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

2）利用量子粒子群優化算法進行快速粗略尋優。可以通過適當地縮小粒子群規模和降低終止條件的要求來快速求得次優值Jgd及其對應的粒子位置Pgd。

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

（1）求Pgd的右鄰位置Pgd+1對應的適應值Jgd+1，求Pgd的左鄰位置Pgd-1對應的適應值Jgd-1，進行如下的雙鄰搜索（包括右鄰搜索和左鄰搜索）。

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

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

（4）依次搜索，當連續N次鄰域搜索都無更優值時，即n≥N，終止搜索。此時的Jgd為最優值，Pgd為最優位置。

4 實驗結果和分析

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

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

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

圖1 兩種算法分割效果圖

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

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

表1 3種算法圖像分割結果分析

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

5 小結

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

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

[2]陳果.圖像閾值分割的Fisher準則函數法[J].儀器儀表學報，2003，24（6）：564-567.

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

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

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

[6]SUN Jun，FENG 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].合肥工業大學學報，2008，31（7）：1088-1091.

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

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