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

?

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

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

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

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

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

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

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

1 Renyi熵圖像分割

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

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

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

假設(shè)0=-1,t+1=-1, 其中P=p-1+1+ p-1+2+…+ p,= 1, 2, …,+1, 則每類的先驗(yàn)Renyi熵定義為:

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

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

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

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

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

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

3 圖像多級(jí)閾值分割算法

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

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

圖1 Lena圖像及其直方圖

圖2 Pepper圖像及其直方圖

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

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

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

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

圖3 Lena圖像2—6級(jí)閾值化結(jié)果

5 結(jié)束語(yǔ)

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

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

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

[2] 聶方彥, 高潮, 郭永彩. 基于新模糊準(zhǔn)則與DE算法的紅外人體圖像分割[J]. 計(jì)算機(jī)應(yīng)用研究, 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] 黃金杰, 郭魯強(qiáng), 逯仁虎, 等. 改進(jìn)的二維Renyi熵圖像閾值分割[J]. 計(jì)算機(jī)科學(xué), 2010, 37(10): 251—253.

[6] 聶方彥, 高潮, 郭永彩. 灰度圖像的模糊Renyi熵多級(jí)閾值分割方法[J]. 系統(tǒng)工程與電子技術(shù), 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)對(duì)象資助項(xiàng)目(湘教通(2011)388號(hào)); 湖南文理學(xué)院博士科研啟動(dòng)基金資助項(xiàng)目(107|13101022).

(責(zé)任編校:劉剛毅)