基于Renyi熵與PSO算法的圖像多級閾值分割

聶方彥, 張平鳳, 潘梅森, 張 奮

?

基于Renyi熵與PSO算法的圖像多級閾值分割

聶方彥*, 張平鳳, 潘梅森, 張 奮

(湖南文理學院 圖形圖像處理技術研究所, 湖南 常德, 415000)

在圖像閾值分割方法中, Renyi熵法因其顯著效能而得到大量應用. 為了更好地發(fā)揮Renyi熵在圖像分割中的應用, 提出把Renyi熵法擴展到圖像多級閾值化問題. 然而, 由于計算時間復雜度上的高要求, 很難把這種有效的技術推廣到復雜圖像多級閾值化問題. 為減少本方法的計算時間, 應用粒子群優(yōu)化算法實施最佳閾值的搜索. 實驗結果表明, 本方法能有效地對圖像進行多級分割, 并且顯著降低計算時間.

圖像分割; 多級閾值化; Renyi熵; 粒子群優(yōu)化

圖像分割是圖像處理和前期視覺處理中的基本技術, 是大多數(shù)圖像分析及視覺系統(tǒng)的重要組成部分, 也是成功進行圖像分析、理解與描述的關鍵步驟, 在計算機視覺研究領域一直受到國內外眾多研究人員的高度重視[1—6].

在圖像分割方法中, 基于閾值化的技術由于其簡潔有效性在圖像分割領域一直得到眾多研究人員青睞. 近年, 基于熵的全局閾值化圖像分割方法被許多學者提出[3—6]. 兩級閾值化是常用的圖像分割方法, 當要對復雜圖像進行分析時有必要對圖像實施多級分割分別提取感興趣目標[7—9]. 然而, 在眾多基于熵的閾值化方法中, 由于計算上的復雜性, 把熵方法擴展到圖像多級閾值化問題應用于復雜圖像分析卻少有論及. Sahoo等人[3]提出一種基于Renyi熵的兩級圖像閾值分割方法, 把Renyi熵用于圖像分割能使圖像的目標與背景很好的分離. 粒子群優(yōu)化(Particle swarm optimization, PSO)[10]算法在各領域的應用被證明是一種非常有效的工程優(yōu)化方法, 為了有效的對復雜圖像進行多級閾值分割, 并降低計算復雜性, 結合PSO算法本文提出一種基于Renyi熵的多級閾值圖像分割方法.

1 Renyi熵圖像分割

假設= {p|= 0, … ,-1}是一幅具有級灰度的圖像灰度級概率分布. 對于一幅×的圖像, 灰度級的概率可用圖像的直方圖估計出, 也即p=n/(×), 這里n表示第級灰度在圖像中出現(xiàn)的頻度. 在兩級圖像閾值化方法中, 圖像背景與目標的概率分布可由下式給出:

其中p=0+1+ … +p,p=p+1+p+2+ … +p-1. 根據(jù)Renyi熵定義, 圖像背景與目標的先驗Renyi熵定義為:

把Renyi熵閾值分割擴展到圖像多閾值分割問題時, 考慮有個閾值1,2, …,t把圖像分割成+ 1類不同的區(qū)域, 各類的概率分布可定義為:

假設0=-1,t+1=-1, 其中P=p-1+1+ p-1+2+…+ p,= 1, 2, …,+1, 則每類的先驗Renyi熵定義為:

根據(jù)Renyi熵閾值分割方法, 多閾值的圖像Renyi熵分割為最大化1+2+ …++1, 也即:

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

粒子群優(yōu)化算法[10]是在模仿基于社會群體行為的基礎上由Kennedy與Eberhart兩人在1995年聯(lián)合提出的一種并行演化計算技術. 其核心思想是通過群體中個體之間的協(xié)作和共享來尋找最優(yōu)解. 由于算法易于實現(xiàn)和高效性而被廣泛應用于各工程領域, 并取得了很好的效果. PSO在工作過程中, 隨機產生一個包含有個粒子的群, 每一個粒子是問題的一個實驗解, 通過若干代的迭代尋優(yōu), 最終得到最優(yōu)解. 在每一代的優(yōu)化過程中粒子群中的每一個粒子根據(jù)它的先前一代的自身最優(yōu)解pbest與全局最優(yōu)解best以速度v在維搜索空間中動態(tài)調整自身的位置p. 在迭代過程中, 每一個粒子的速度與位置根據(jù)下面兩式進行調整.

式中,表示迭代數(shù),是慣性加權系數(shù),1、2是學習因子,1、2是服從均勻分布的位于[0, 1]之間的隨機數(shù). 在文獻[10]中, Clerc與Kennedy在式(9)中使用了一個收縮因子以保證算法的收斂.

式中=1+2, 且> 4, 若取1= 2.1、2= 2.0, 則的一個典型值就是0.729 8.

在PSO算法中, 經過一定代數(shù)的迭代以后, 若粒子群中的問題最優(yōu)解不再變化或迭代達到一個最大迭代數(shù)則算法終止.

3 圖像多級閾值分割算法

有感于Renyi熵在圖像閾值分割中的有效性及PSO算法在工程優(yōu)化問題中的優(yōu)良表現(xiàn), 我們結合這2種方提出了一種新的高效的快速復雜圖像多閾值分割算法. 對于級Renyi熵圖像閾值化問題, 粒子群中的粒子表達式設計為:= (1,2, …,t), 式中向量中的每一個值表示一個閾值, 0 <1<2<…<t<. 在基于PSO算法的工程優(yōu)化問題中, 粒子間通過一個適應值函數(shù)進行競爭產生best和best, 對于Renyi熵圖像多閾值化問題, 可用式(5)作為粒子間競爭的適應值函數(shù). 當算法迭代終止, 粒子群中的全局最優(yōu)解即可作為問題的最優(yōu)解. 基于PSO算法的Renyi熵圖像多閾值分割算法描述如下.

Step 1: 初始化. 初始化個粒子位置、粒子自身最優(yōu)解best、粒子速度, 最大迭代數(shù)MAXIT, 學習因子1、2, 并置迭代計數(shù)器= 0.

Step 2: 評估. 根據(jù)式(5)評估每個粒子的函數(shù)值().

Step 3: 選擇. 比較粒子的個體最優(yōu)解與它當前的適應值函數(shù)值, 根據(jù)下式更新它的個體最優(yōu)解.

從個best中選出一個具有最大適應值函數(shù)值的個體最優(yōu)解做為全局最優(yōu)解best.

Step 4: 更新. 根據(jù)式(8)和(7)更新粒子的速度與位置.

Step 5: 迭代.=+1, 轉到Step 2, 循環(huán)直到滿足停機準則.

4 實驗與分析

本實驗在一臺Intel(R) Core(TM)2 Duo CPU T8100 2.10GHz筆記本電腦上用Matlab(R2007b)語言實現(xiàn)了所提出的算法, 并用若干幅圖像對所實現(xiàn)的算法進行了測試, 在這里僅列出眾多圖像處理相關文獻常用的兩幅具有多峰分布的標準測試圖像的測試結果. 這2幅圖像是尺寸為256 × 256、256級灰度級的Lena與Pepper圖像. 從圖1與圖2可以看出, 圖像Lena與Pepper具有復雜的灰度直方圖分布, 單靠兩級閾值化不能完全有效地把信息分離開來. 為了比較算法的有效性, 對所提出的算法與基于Renyi熵圖像多閾值窮盡分割方法進行了比較. 在實驗中, 算法的各參數(shù)設置為: 種群規(guī)模20, 最大迭代次數(shù)500,1= 2.1,2= 2.0, 故= 0.729 8, 參數(shù)根據(jù)文獻[6]的經驗值, 在這里設置為= 0.7, 停機準則為算法迭代到最大迭代次數(shù)或得到的最優(yōu)解趨于穩(wěn)定. 表1與表2列出了這兩種方法分別對Lena及Pepper圖像的實驗結果.

圖1 Lena圖像及其直方圖

圖2 Pepper圖像及其直方圖

表1 Lena圖像PSO法及窮盡法Renyi熵分割閾值比較

表2 Pepper圖像PSO法及窮盡法Renyi熵分割閾值比較

從表1、表2可以看出, 在對復雜圖像進行多閾值分割時, 用基于PSO算法的Renyi熵分割得到的多級閾值與用窮盡方法得到的多級閾值進行比較, 每個閾值的偏差沒有超過5個灰度級, 從算法運行時間來看, 除兩級閾值基于窮盡方法的算法運行時間比基于PSO算法的所需時間較少以外, 在另外幾級閾值化問題上, 基于窮盡方法所需的時間遠遠高于基于PSO算法所需的時間. 從時間復雜度上進行分析, 基于窮盡方法的時間復雜度為(L), 其中為灰度級數(shù),為閾值個數(shù), 對于基于PSO算法的分割方法, 其最大時間復雜度為(×MAXIT), 其中為粒子個數(shù), MAXIT為算法最大迭代次數(shù), 在實驗過程中發(fā)現(xiàn)MAXIT不必設得非常大, 一般算法迭代15代左右即收斂. 從這點來說, 本文提出的方法大大減少了Renyi熵多閾值分割所需時間, 很好地拓展了Renyi熵在圖像多級閾值問題領域的應用.

圖3列出了基于PSO算法的Renyi熵Lena圖像的2—6級閾值及其分割圖. 圖3(a、c、e、g、i)分別為Lena圖像的兩級、三級、四級、五級及六級閾值化圖, 圖3(b、d、f、h、j)是各級閾值化在原始Lena圖像直方圖上標出的對應閾值. 從圖3也可以看出用基于PSO算法的Renyi熵多級閾值化方法對圖像進行分割能得到較好的分割結果.

圖3 Lena圖像2—6級閾值化結果

5 結束語

本文針對Renyi熵在圖像多閾值分割中計算復雜度高, 難以實現(xiàn)的難題, 提出了一種基于PSO算法的Renyi熵快速圖像多閾值分割算法. 通過眾多實物圖像在所實現(xiàn)的算法上的驗證, 我們所提出的算法在進行圖像多閾值分割任務時, 所需時間大大降低, 所得閾值與窮盡方法相差微小, 經過多次重復實驗, 應用所提出的算法得到的閾值穩(wěn)定. 實驗結果充分表明本文方法不僅對不同類型的復雜圖像均能取得較好的多閾值分割結果, 而且在運算代價上具有明顯的優(yōu)勢, 為基于Renyi熵的圖像分割提供了一種新的思路.

在進行多閾值分割任務時, 現(xiàn)行算法在工作前需人為指定閾值個數(shù), 在對復雜圖像進行分割有時并不能事前知道需對圖像進行幾級閾值化, 而且確定圖像的閾值級數(shù)也是一個非常復雜的難題, 我們下一步的工作將針對圖像的自動多閾值分割問題結合所提出的算法展開研究.

[1] 翟艷鵬, 郭敏, 馬苗, 等. 結合灰色理論和粒子群算法的歸一化圖像分割[J]. 計算機應用研究, 2011, 28(2): 776— 778.

[2] 聶方彥, 高潮, 郭永彩. 基于新模糊準則與DE算法的紅外人體圖像分割[J]. 計算機應用研究, 2010, 27(4): 1594— 1597.

[3] Sahoo P K,Wilkins C,Yeager J. Thresholding selection using Renyi's entropy[J].Pattern Recognition,1997,30(1): 71—84.

[4] Sahoo P K, Arora G. A thresholding method based on two-dimensional Renyi's entropy[J]. Pattern Recognition, 2004, 37(6): 1149—1161

[5] 黃金杰, 郭魯強, 逯仁虎, 等. 改進的二維Renyi熵圖像閾值分割[J]. 計算機科學, 2010, 37(10): 251—253.

[6] 聶方彥, 高潮, 郭永彩. 灰度圖像的模糊Renyi熵多級閾值分割方法[J]. 系統(tǒng)工程與電子技術, 2010, 32(5): 1055— 1059.

[7] Horng Ming-Huwi. Multilevel minimum cross entropy threshold selection based on the honey bee mating optimization[J]. Expert Systems with Applications, 2010, 37(6): 4580—4592.

[8] Yin Peng-Yeng. Multilevel minimum cross entropy threshold selection based on particle swarm optimization[J]. Applied Mathematics and Computation, 2007, 184(2): 503—513.

[9] Sanjay Agrawal, Rutuparna Panda, Sudipta Bhuyan, et al. Tsallis entropy based optimal multilevel thresholding using cuckoo search algorithm[J]. Swarm and Evolutionary Computation, 2013, 11:16—30.

[10]Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58—73.

Image multi-thresholding using Renyi entropy and PSO

NIE Fang-yan, ZHANG Ping-feng, PAN Mei-sen, ZHANG Fen

(Institute of Graphics and Image Processing Technology, Hunan University of Arts and Science, Changde 415000, China)

In image segmentation, Renyi-based thresholding method has obtained widely application because of its remarkable effectiveness. In order to develop the latent ability of Renyi-based method in image segmentation, the method was extended to multi-thresholding field. However, due to the time complexity, the Renyi entropy-based method was very difficult extended to multi-thresholding scenario straightly. To overcome this problem, a fast multi-thresholding method combined with the particle swarm optimization algorithm for complex image segmentation was proposed based on Renyi entropy. The experimental results show that the proposed method can reduce the computation time greatly, and obtain ideal segmentation result.

image segmentation; multi-thresholding; Renyi entropy; particle swarm optimization

10.3969/j.issn.1672-6146.2013.03.010

TP 391.4

1672-6146(2013)03-0044-05

email: niefyan@163.com.

2013-05-02

湖南省普通高校青年骨干教師培養(yǎng)對象資助項目(湘教通(2011)388號); 湖南文理學院博士科研啟動基金資助項目(107|13101022).

(責任編校:劉剛毅)