基于改進粒子群人工魚群算法的二維熵多閾值快速圖像分割

伍鎣芮，張志勇

（山西農業大學農業工程學院，晉中030801）

0 引言

圖像分割方法多種多樣，其中閾值分割基于背景與目標在灰度上的差異實現圖像分割。圖像復雜或背景多樣時需要選擇多個閾值。多閾值分割與單閾值分割原理相似但計算量呈指數級增長，且多閾值分割應用范圍更廣。

常用的圖像閾值分割方法，如大津算法（OTSU）、峰谷法和圖像最大熵法等，都是根據圖像的局部或全局信息來定位最佳閾值，步驟繁瑣導致運算時間較長。為了加快閾值選擇速度，程萬勝等人[1]運用修正慣性因子的粒子群優化算法提升收斂速率，改善圖像在線分割速度；何志勇等人[2]提出基于圖像二維直方圖直線分割思想的新算法，一定程度上避免傳統算法的抗噪缺陷；張懷柱等人[3]提出以二維Fisher準則圖像分割評價函數為適應度函數的改進遺傳算法，該算法收斂快、魯棒性強，具有一定實用性。由于信息熵本身能簡單有效地表達圖像的混亂程度，常將圖像熵應用于圖像分割。文獻[4-5]提出利用圖像二維熵來表達基于圖像理論信息準則的背景與目標，便于兩者分割，該方法仍存在耗時長的問題。文獻[6]使用改進粒子群算法結合圖像分割與其他算法對比，在不同指標下性能更好。文獻[7]和文獻[9]提出使用遺傳算法（Genetic Algo?rithm，GA）來確定圖像熵函數的最優值，但遺傳算法的變異因子不便控制會影響熵函數的閾值精度。Ming-Huwi Horng[8]使用蜜蜂交配優化算法尋找基于最小交叉熵下的最優閾值。文獻[10-11]使用螢火蟲算法來選擇閾值，該算法更接近窮舉算法的結果，且時效性有一定的提升。上述方法都提升了閾值定位的收斂速度，但螢火蟲算法、PSO算法與GA算法等智能算法都易陷入早熟無法自動跳出，不能有效拓展搜索范圍，導致閾值挑選準確性不高進而影響圖像分割效果。

人工魚群算法（Artificial Fish Swarm Algorithm，AFSA）和粒子群算法都是群體智能仿生算法，AFSA對優化函數的性質要求不高，全局尋優能力靈活，一定程度上避免局部最優點；PSO是模仿鳥類覓食行為的仿生算法，不依賴問題信息，算法通用性較強，但局部搜索能力較差，搜索精度待提高，整體搜索性能對初始參數有一定的依賴性。文獻[12]參考PSO的進化策略與信息策略得到一種改進的人工魚群算法，并在理論上證明PSO-AFSA的收斂性。文獻[13]利用高鐵數據仿真驗證了人工魚群算法在列車運行調整中的收斂性與實用性，具有一定的應用價值。文獻[14]引入方向算子改進的人工魚群算法以減少局部極值出現的概率。

由于粒子群人工魚群算法的搜索范圍廣和局部收斂快的優點和二維熵多閾值分割法的簡單實用與分割效果良好，本文設定二維熵多閾值函數為粒子群人工魚群混合算法的優化目標，基于圖像熵對復雜圖像和多目標進行分割。

1 基于改進算法的二維熵多閾值圖像分割方法

1.1 二維熵多閾值分割原理

設原始灰度圖像I(x,y)大小為M*N，M、N為圖像橫縱像素數，圖像灰度級數為L（一般為255）。則可定義該圖像每個像素點所對應n*n領域的平均灰度：

位于圖像邊緣的像素點，其領域像素點值與中心像素點相同。再設Rij為單個像素灰度值i與鄰域某個灰度值出現的對應頻數，可定義該像素點的聯合概率密度為：

全部像素點Pij可構成原始圖像的二維熵直方分布圖，圖1、圖2分別表示單閾值與多閾值直方圖。

圖1 二維直方圖

圖2 二維多閾值直方圖

圖1 中，A區代表原圖像背景，B區代表目標，C區表示背景與目標相切的邊緣，D區表示圖像中的噪聲；圖2與圖1類似。A區和B區的灰度像素分布概率分別為：

A區與B區域歸一化概率為：

單閾值函數與多閾值函數二維熵分別如下式：

二維熵多閾值圖像分割法的分割目標為求閾值（s1，t1）…（sk，tk）使得二維熵函數值為最大。

1.2 粒子群人工魚群算法

（1）PSO原理

粒子群算法（PSO）是一種仿生優化算法，最初是模仿鳥類覓食運動來尋找適應度函數的極值。鳥類在一定范圍內覓食過程中，能不斷通過協同交流來尋找食物的位置并分享自己的位置，且每只鳥都有單獨記憶。通過這種合作方式，能夠將位置信息與食物信息傳遞至整個群體，提高了整體覓食的效率。在設定為D維的空間中有n只鳥組成的鳥群，在第k次迭代后，其中第i個粒子對應狀態為：

第i個粒子速度為：

第i個粒子歷史最優值：

群體中最優點：

第k+1次迭代的粒子群的優化公式為：

式（8）中，k為迭代次數；c1和c2分別為個體學習因子與群體學習因子；ε和η為0到1之內的隨機數；初始化時設置粒子飛行速度最大值為Vmax。

（2）AFSA原理

魚群算法通過模仿魚群的覓食、追尾和聚群行為來尋優目標函數的全局極值。在指定水域中，魚群通過上述三種基本行為能快速聚攏在食物最豐富的地方。魚群算法對目標函數無特殊要求，且在尋優過程中用三種行為能更智能地定位最佳食物源，有著較快的收斂速度。

魚類通過視野的變化不斷調整行進方向或速度來尋找食物是它基本的生物學行為，設第i（i=1，2，3...n）只魚在指定區域內不停搜索食物，其當前位置狀態為，在其視野領域內隨機選擇下一個行進位置，則在當前位置與下一隨機位置下對應的尋優函數值分別為，當求解優化問題的極大值時，若在當前狀態下的所有解范圍內，則向該區域前進一步；否則，重新選擇下一個隨機位置狀態繼續判斷優化條件是否滿足。若隨機N步后依然未尋到更大解，則隨機前進一步。覓食行為Fp的更新公式為：

魚群在活動過程中通過聚群可以保證魚群的整體性以避免危險和合作覓食。設人工魚當前位置為在指定視覺范圍內確定魚群數量nf與魚群的幾何中心如果nf/n＜δ（擁擠度因子）且適應度函數（fXc）>f（Xi），即此魚群中心食物豐富且魚群較少，則向該中心位置聚攏，否則繼續覓食。聚群行為Fs更新公式為：

魚群中一定數量的魚群發現食物時，其周圍的魚群會緊隨而至。設第i只魚在尋找食物時狀態為搜索臨近范圍內的魚群數量與食物濃度最大的魚群若伙伴食物濃度達到臨界值且魚群擁擠度系數低于設定值，則向該方向前進一步，否則執行覓食行為。追尾公式為：

（3）PSO-AFSA混合算法

提出的PSO-AFSA算法綜合了PSO和AFSA的優點，首先隨機生成一定數量的初始魚群，計算所有魚群的適應度函數值以挑選出部分精英魚群。先使用PSO對目標函數值較高的精英魚群依次更新，設置Nmax為精英魚群迭代次數；普通魚群則執行AFSA更新，每一輪全體魚群更新后依適應度函數值進行排序，篩選出新的精英粒子，直到迭代結束。PSO粒子通過學習本身歷史最佳值與群體最佳值來改變行進的方向和速度，該屬性能夠大幅度加快算法的收斂速度；AFSA具備良好的全局收斂能力，能較快地跳出局部最優點，而挑選部分精英粒子可以綜合兩種算法的優點來加快收斂速度。

1.3 基于改進算法的二維熵多閾值快速圖像分割方法

提出了基于改進粒子群人工魚群的二維熵多閾值快速圖像分割方法，將圖像的多閾值選擇問題定義為改進算法的目標函數，即對多維度函數H（s1，t1，...sk，tk）的最大值尋優問題。

將二維熵函數H（s1，t1，...sk，tk）設置為粒子群人工魚群算法的目標函數，粒子群人工魚群算法的尋優結果為使得二維熵適應度函數值最大的魚群位置X（s1，t1，s2，t2，...sk，tk）。其中k為二維熵閾值個數；（s1，t1，s2，t2，...sk，tk）即為所求最佳二維熵閾值。基于改進算法的分割法具體步驟如下：

（1）初始化粒子群人工魚群算法參數，隨機生成全體粒子并計算出二維熵函數值，排序篩選出精英粒子和普通魚群粒子，設置擁擠度因子、視覺范圍、粒子群迭代次數及總迭代次數等相關參數；

（2）分別計算精英粒子和普通魚群粒子的適應度函數值，即對應的二維熵函數值；

（3）對精英粒子進行PSO迭代更新，其最佳適應度值為Yb；

（4）對普通魚群用聚群公式和追尾公式進行更新，排序后選擇最大值Y為最佳更新結果；

（5）比較Y和Yb，判斷適應度最大值是否發生改變，若變大則賦值給Yb，否則普通魚群執行覓食行為；

（6）將更新后的精英魚群最佳值與普通魚群最佳值Yb比較，若更大，將該值賦予Yb；

（7）全部魚群更新完成后，判斷是否達到迭代最值，達到迭代最大值則輸出最佳適應度值Yb，否則轉至步驟（3）；具體流程圖如圖3。

2 實驗結果與分析

2.1 基于改進算法的二維熵多閾值快速圖像分割實驗

為驗證本文提出算法對二維熵多閾值分割的時效性與閾值選擇的準確性，實驗對Lena圖、Peppers圖、Baboon圖、Terrace圖和QFN（Quad Flat Non-Lead）芯片封裝圖像進行分割，并與窮舉分割法和粒子群分割法對比。Lena、Peppers和Baboon圖常用于圖像處理，Terrace圖含多個目標且背景不明顯，QFN是常見芯片封裝，使用時易受到刮劃，造成外部傷痕，這些缺陷易造成焊接不牢、接觸不良等現象，且返修難度大，檢測其表面劃痕能提高芯片的回收率，具有一定的現實意義。

圖3 基于PSO-AFSA的二維熵多閾值圖像分割算法流程圖

對五幅圖像進行單閾值、雙閾值及三閾值分割，初始化時，將PSO-AFSA具體相關參數設置如下：總粒子數N=50，精英粒子Ne=10，總迭代次數Nmax=100，單步步長s=0.1，速度范圍[-Vmax，Vmax]=[-5，5]，隨機數rand=0.5，個體慣性權重C1=1.5，群體慣性權重C2=1.5，隨機量ζ=η=0.5，魚群視覺最大范圍V=10。分割后的圖像如圖4所示，最左為原始圖，往右為依次增加閾值的分割圖。

圖4 分割實驗結果圖

2.2 二維熵窮舉算法、粒子群二維熵多閾值分割法實驗對比

為驗證本文算法的準確性，將其與窮舉分割法、PSO多閾值分割法進行對比實驗。

二維熵窮舉分割法在函數定義域內逐個計算最大值，保證目標函數最優值的準確性，窮舉法的計算量隨閾值增多而呈指數增長，本文計算復雜度依次為O（L2）、O（L4）、O（L6），L=255，可知，雙閾值及以上時窮舉法由于計算量過大將不再適用；PSO二維熵多閾值分割法是基于PSO的二維熵多閾值圖像分割方法。

五幅圖像分割后的閾值及二維熵值如表1所示。

表1 3種方法計算的閾值與二維熵函數值

由表可知，使用PSO分割法的二維熵函數值的平均誤差為0.29%，改進算法的二維熵函數值的平均誤差為0.04%，新算法尋得的閾值更接近于窮舉算法的閾值。因此，改進算法的精確性較基于PSO的分割法更高。

圖像分割后，單憑人眼無法準確判斷分割效果，常采用信噪比準則測試算法分割效果，間接評價算法的分割效果。圖像處理中信噪比準則的表達式為：

其中：

I（x，y）、I（x，y）分別表示原圖像與分割后的圖像。

三種方法分割圖像的PSNR值與計算時間如表2所示。可知，改進算法在單三閾值、雙閾值和三閾值分割都比窮舉分割法快；與PSO分割法時間接近。但改進算法PSNR值都比窮舉法與PSO分割法高。

綜上，基于改進粒子群人工魚群的二維熵多閾值分割法在耗時上有了極大提高，且PSNR與分割精度均優于基于PSO的分割法，能更快速有效地分割多目標圖像。

表2 3種方法的計算時間與對應PSNR值

3 結語

對模糊圖像和復雜圖像閾值分割隨閾值數量增加而運算量大導致耗時長的問題，提出基于PSO-AFSA混合算法的二維熵快速分割法。解釋了二維熵單閾值分割的選取原理，并延伸至多閾值分割。然后，引入兩種仿生優化算法，將粒子群能參考個體最佳值與群體最佳值的特征引入到人工魚群算法，解釋并比較兩種算法的尋優原理與優缺點。使用該改進算法對典型圖像進行分割并與窮舉分割法和PSO分割法比較。結果表明，提出的混合算法分割效果良好，得到的二維熵函數值平均誤差為0.04%，分割速度比窮舉分割法快兩個數量級。因此，使用改進粒子群人工魚群算法的二維熵閾值分割能更快速有效地分割模糊圖像和多目標圖像。