基於改進CS演算法的二維Ostu快速圖像分割

摘要：針對應用布谷鳥搜索演算法進行二維Ostu分割時計算時間長、效率低、易陷入局部最優的問題，提出了基於改進布谷鳥搜索演算法的二維Ostu快速圖像分割方法。通過引入逐維更新與整體更新相結合的混合維度更新策略，對布谷鳥搜索演算法進行修正，以方差可調的正態分布進行步長有區分的整體鄰域搜索，提高了演算法的搜索精度與效率，解決了二維Ostu圖像分割效率低的問題。實驗結果表明，與窮舉法、布谷鳥演算法相比，改進演算法圖像分割效率最高，效果最好。

正文內容：

0　引　言

圖像分割是圖像處理最基本的技術之一，為圖像的後續處理提供檢驗依據。隨著科技的快速發展，許多基於閾值的圖像分割方法被不斷提出，其中最大類間方差法（Ostu）由日本學者大津提出[1]。該方法無需經過人工設定和先驗知識便可自動選取閾值，具有分割效果好、速度快等特點[2]，但傳統一維Ostu法對於雜訊十分敏感[3]，灰度直方圖易形成波峰波谷分布不明顯，從而導致分割閾值有誤。劉健庄根據此問題提出二維Ostu法[4]，根據圖像的灰度級和其鄰域平均灰度級選取閾值，提高了演算法的抗噪能力，但也存在計算效率低的問題。

布谷鳥搜索演算法（Cuckoo Search，CS）是由英國學者XIN-SheYANG和DEB Suash於2009年提出的一種新型自然元啟發式演算法[5]。該演算法的思想是基於布谷鳥的巢寄生行為和鳥類的Lévy飛行隨機遊走策略尋求最優解[5-6]。該演算法因其簡單有效，廣泛應用於各個領域[7-8]。然而，CS演算法作為一種新穎的模擬演算法[9]，在實際應用中仍存在後期收斂速度慢、易陷入局部最優的問題[10]。本文通過引入逐維更新與整體更新相結合的混合維度更新策略對CS演算法進行改進，並應用在二維Ostu法中對圖像進行分割。

1　二維Ostu閾值分割方法

設圖像的灰度級和鄰域平均灰度級L ，則像素的灰度值i 和該像素的鄰域平均灰度值j 構成二元數組(I,j) ，fij 為其出現的頻數，則相應的聯合密度Pi,j 定義如下[4]：

式中N 為圖像總像素點數。

根據圖1，(s,t) 是選取的閾值點，對角線上的區域C0 和C1 對應於背景和目標，遠離對角線的區域C2 和C3 對應於邊緣和雜訊。在二維Ostu法中，假設區域C2 和C3 的概率之和近似為0。背景和目標出現的概率分別定義為[11]：

背景和目標對應的均值定義為：

二維直方圖上總的均值定義為：

根據區域C2 和C3 的概率之和近似為0的假設，可以得到：

類間的離散度矩陣定義為：

類間的離散度測度定義為SB 的跡，即：

最佳閾值(s0,t0) 由式（10）確定：

在確定最佳分割閾值後，定義：

以此完成圖像分割。

2　基於改進CS的二維Ostu圖像分割原理

2.1　基本的CS演算法

XIN-She YANG和DEB Suash在提出CS演算法時，基於以下3條理想化假設[12]：

（1）每隻布谷鳥每次隨機選擇一個巢併產一個卵；

（2）適應度最高的巢保留至下一代；

（3）鳥巢數量不變，按照概拋棄鳥巢。

基於以上三條假設，CS演算法的尋優過程如下：

（1）初始化種群；

（2）採用Lévy飛行搜索模式更新鳥巢位置，保留較優的鳥巢位置，更新公式如下：

式中，xk+1,i 表示第i 個鳥巢在第k+1 代的位置，a 為步長控制向量，表示點乘，表示萊維隨機搜索路徑。

（3）按照隨機概率pa 拋棄鳥巢，若被拋棄則重新構建相同數量鳥巢，更新公式如下：

式中，是縮放因子，是（0,1）之間的隨機數，xk,j、xk,e 則表示第k 代的兩個隨機鳥巢。

2.2　改進的CS演算法

2.2.1　混合維度更新評價策略

CS演算法有兩種鳥巢更新模式，即符合Lévy飛行的隨機遊走模式和偏好隨機遊走模式。但是，這兩種模式都是整體更新模式，在二維尤其是多維空間搜索中存在某些解的進化維因整體更新而退化的問題，從而使各維難以同時達到最優，降低了演算法的收斂速度和搜索精度[13]。

為克服此缺陷，本文在CS演算法第二步即Lévy飛行隨機遊走更新過程中借鑒逐維更新評價策略，提出了一種新的混合維度更新評價策略。由於完全應用逐維更新模式會大量浪費計算資源，降低計算速度，故本文提出按照一定概率pb 進行逐維更新，更新公式如式（14）所示：

式中，xk+1,i,j 表示第j 個種群第i 個鳥巢在第k+1 代的位置，a1 為步長控制向量。

按照pc(pc=1-pb) 進行整體更新，並設置步長向量a2 ，如式（15）所示：

由此更好地整合了逐維更新和整體更新評價策略，達到演算法計算速度與精度的有效統一。假設種群規模為n ，搜索空間維度為m ，則此步的時間複雜度為o(n)=nx(Pb(m-1)-1) 。相較於逐維搜索o(n)= nxm ，時間複雜度大大降低。

2.2.2　鄰域搜索策略

在CS演算法第三步以隨機概率pa 拋棄鳥巢後，在多維空間的求解過程中，對不同維度採用相同的鄰域搜索範圍，不僅造成搜索資源浪費，而且無法有效提高搜索精度與速度。本文以方差可調的正態分布對各維鳥巢進行步長有區分的整體鄰域搜索，以xk,best-xk,e 引導鄰域搜索方向，其中xk,best 為第k 代最優解，xk, e 為第k 代的一個隨機解。

式中為比例係數，為點對點乘法，X 為鄰域搜索半徑，其維數應與種群規模相同，一般取0，一般取5。

2.2.3　改進的CS演算法流程

圖2為改進CS演算法流程圖。

本文以二維Ostu函數作為改進CS演算法的適應度函數，按照二維Ostu相關理論進行二維Ostu圖像分割，所求最大二維Ostu函數值所對應的閾值即為最佳閾值。

演算法步驟如下：

（1）初始化鳥巢數目n ，空間搜索維度m ，發現概率pa ，逐維更新概率pb ，步長控制向量a1 和a2 ，比例係數r ，輸入圖像，設置適應度函數；

（2）計算每個鳥巢適應度；

（3）應用式（14）、式（15）進行混合維度更新；

（4）按照概率pa 拋棄鳥巢，按照鄰域搜索策略，以式（17）更新鳥巢位置；

（5）判斷是否符合終止條件，符合則進行下一步，否則返回步驟（2）；

（6）輸出最佳分割閾值。

3　實驗結果與分析

為驗證本文所提演算法在圖像分割上的優越性，本文將Lena、Barbara、Pepper和Pens作為實驗對象進行圖像分割實驗。測試平台為Matlab2016a、windows7，處理器Intel Core i5-3470，主頻3.20 GHz，內存4G。

3.1　對複雜圖像的分割

採用本文演算法對四幅圖像進行二維Ostu圖像分割，如圖3（a）所示。經多次實驗驗證，將相關參數設置如下：種群規模n=20 =20，最大迭代次數Negn=200 =200，鳥巢拋棄概率pa=0.25 0.25，混合維度分配概率pb=0.25 0.75，各圖像分割結果如圖3（b）所示，從左至右分別為Lena、Barbara、Pepper、Pens圖。

3.2　對比實驗

為驗證本文所提演算法的優越性，特選取Rice和Cornfield圖像作為實驗對象，分別用窮舉法、CS演算法和本文演算法進行二維Ostu圖像分割.窮舉法即採用窮舉的搜索模式尋找最優分割閾值，分割效果及分割數據如表1、表2所示。統一設定種群規模 n=20，最大迭代次數Negn=100 =100。

3.2.1　圖像分割效果對比

從表1可以看出，對於Rice圖像，CS演算法丟失了很多邊緣信息，造成分割對象不完整；而本文演算法得到的邊緣清晰目標完整，分割效果更接近於窮舉法。對於Cornfield圖像，CS演算法分割閾值選擇不合理、有雜訊點分布、且部分細節丟失，而本文演算法則完好保留了圖像的整體與細節信息，與窮舉法分割效果更相近。

3.2.2　圖像分割數據對比

從表2可以看出：在最佳閾值選取上，CS演算法已經相當接近窮舉法結果，而本文演算法和窮舉法結果一致；在收斂代數上，本文演算法低於CS演算法10代左右；在計算時間上，CS演算法和本文演算法都大大低於窮舉法，計算速度提高270倍左右；本文演算法相較於CS演算法，成功率提高50%左右。總之，在相同情況下，本文演算法分割速度尤其是分割效果是都較CS演算法獲得了大幅提升。

3.2.3　演算法收斂性能

為了進一步分析本演算法對圖像進行二維Ostu閾值分割的收斂性能，圖4給出了最佳閾值(s,t0 的變化趨勢。可以明顯看出，本演算法在尋找最佳閾值的過程中，s 、t 以不同變化趨勢趨近於最優解，並在35代左右收斂。圖5給出了本演算法和CS演算法最優函數值的收斂趨勢。可以明顯看出，迭代前期本文演算法的下降速度明顯高於CS演算法，迭代後期本文演算法尋找到最優解並穩定的時間也早於CS演算法，收斂速度提高50%左右。

4　結　語

針對二維Ostu方法分割複雜圖像存在計算量大、計算時間長的問題，本文引入CS演算法，並針對CS演算法準確率低、收斂速度慢的問題進行了改進。首先本文對二維Ostu方法進行公式推導並進行分析，然後針對CS演算法的問題進行修正，提出了基於改進CS演算法的二維Ostu快速圖像分割方法，最後應用典型圖像，分別對本文方法、窮舉法和CS演算法進行驗證，並將分割效果、分割數據及演算法收斂性能進行比較。實驗表明：本文方法的分割效果優於CS演算法，與窮舉法相同；收斂速度與CS演算法相近，較窮舉法提高約270倍；收斂成功率較CS演算法提高約50%，且在多種實驗條件下均能保證較高成功率。因此，本文所提基於改進CS演算法的二維Ostu快速圖像分割方法能夠實現對複雜圖像更加快速、準確、有效的分割。

參考文獻：

[1] Smith P,Reid D B,Environment C,et al.A Tlreshold Selection Method from Gray-Level Histograms[J].Systems Man & Cybernetics IEEE Transactions on,1979,9(01):62-66.

[2] 羅麗霞.基於遺傳演算法的Ostu圖像分割方法[J].河北北方學院學報:自然科學版,2014(06):29-33.

[3] 金元郁,張洪波,馮宇.基於遺傳演算法的二維雙閾值Otsu圖像分割演算法[J].電子科技,2009,22(11):35-39.

[4] 劉健庄,栗文青.灰度圖象的二維Otsu自動閾值分割法[J].自動化學報,1993(01):101-105.

[5] Yang X S,Deb S.Cuckoo Search via Levy Flights[J].Mathematics,2010:210-214.

[6] 黃繼達.布谷鳥演算法的改進及其應用研究[D].武漢:華中科技大學,2014.

[7] Senthilnath J,Das V,Omkar S N,et al.Clustering Using Levy Flight Cuckoo Search[M].Advances in Intelligent Systems and Computing,2013:65-75.

[8] Kumar A,Chakarverty S.Design Optimization for Reliable Embedded System Using Cuckoo Search[C].International Conference on Electronics Computer Technology IEEE,2011:264-268.

[9] Yang X S,Deb S.Engineering Optimisation by Cuckoo Search[J].International Journal of Mathematical Modelling & Numerical Optimisation,2010,1(04):330-343.

[10]李瑞芳.基於改進布谷鳥搜索演算法的圖像分割[J].電子科技,2016,29(05):105-107.

[11]蘭少峰,劉升.布谷鳥搜索演算法研究綜述[J].計算機工程與設計,2015(04):1063-1067.

[12]薛益鴿.改進的布谷鳥搜索演算法及其應用研究[D].重慶:西南大學,2015.

[13]王李進,尹義龍,鍾一文.逐維改進的布谷鳥搜索演算法[J].軟體學報,2013(11):2687-2698.

作者：高宏進，王　力，龔維印，楊　幸

單位：貴州大學 大數據與信息工程學院，貴州 貴陽 550025

作者簡介：高宏進，男，碩士，主要研究方向為數字圖像處理；

王　力，男，學士，教授，主要研究方向為機器學習、神經網路；

龔維印，男，碩士，主要研究方向為圖像處理；

楊　幸，女，碩士，主要研究方向為人臉識別。

本文刊登在《通信技術》2017年第12期（轉載請註明出處，否則禁止轉載）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！