張書真，黃光亞

吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000

基于三維指數(shù)灰度熵的快速圖像分割算法

張書真，黃光亞

吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南吉首 416000

1 引言

圖像分割是數(shù)字圖像處理中的一項(xiàng)關(guān)鍵技術(shù)，它是對圖像進(jìn)行視覺分析和模式識別的基本前提[1]。閾值分割因其實(shí)現(xiàn)簡單、性能穩(wěn)定而成為圖像分割中最基本的分割技術(shù)[2-3]。其中，基于熵的閾值分割方法一直受到研究者的廣泛關(guān)注，常見的有Shannon熵[4-5]、交叉熵[6-7]、Renyi熵[8]等，并且已有相應(yīng)的二維算法[9-13]或三維算法[14-15]。上述的閾值分割法中普遍存在兩個(gè)問題：一是閾值的選取僅利用到圖像灰度直方圖的統(tǒng)計(jì)信息，而未直接考慮圖像類內(nèi)灰度分布的均勻性；二是在推廣的二維或三維算法中，由于閾值搜索范圍擴(kuò)大，最佳閾值的尋求過程耗時(shí)巨大。

針對上述問題，本文提出一種快速三維指數(shù)灰度熵圖像分割算法。算法首先給出了指數(shù)灰度熵的定義，然后推導(dǎo)出三維指數(shù)灰度熵閾值分割的原理，并利用降維處理和優(yōu)化搜索策略的方法快速獲取最佳閾值，使得閾值搜索復(fù)雜度降為O(L1/2)。由于指數(shù)灰度熵同時(shí)考慮了直方圖的統(tǒng)計(jì)信息和圖像類內(nèi)灰度分布的均勻性，圖像分割亦取得了較好的效果。

2 三維指數(shù)灰度熵閾值分割算法

2.1 三維直方圖

設(shè)一幅圖像的灰度級為L，其三維直方圖的三個(gè)坐標(biāo)軸分別表示圖像像素的灰度值i、鄰域均值j和鄰域中值k，直方圖中任意一點(diǎn)的值表示三元組(i，j，k)發(fā)生的頻數(shù)g(i，j，k)，其中0≤i，j，k≤L-1。以lena圖為例，其三維直方圖如圖1（b）所示，由于圖像目標(biāo)和背景內(nèi)像素的灰度值、鄰域均值和鄰域中值十分接近，圖像大部分的像素點(diǎn)集中在直方圖的對角線附近，而少量的邊緣點(diǎn)和噪聲點(diǎn)將分布于直方圖中遠(yuǎn)離對角線的區(qū)域。

圖1 lena圖與其三維直方圖

2.2 一維指數(shù)灰度熵閾值法

指數(shù)熵[16]的定義是PAL在1989年提出的，它能克服Shannon熵出現(xiàn)的無定義和零值問題，但是和現(xiàn)有的大部分閾值法一樣，指數(shù)熵僅利用了直方圖的統(tǒng)計(jì)信息，而忽略了圖像類內(nèi)分布的均勻性，為此考慮引入指數(shù)灰度熵的概念進(jìn)行圖像分割。

設(shè)一幅圖像灰度級數(shù)目為L，圖像中灰度為l的像素?cái)?shù)目記為g(l)，閾值s將圖像劃分為目標(biāo)類Co和背景類Cb，設(shè)低灰度區(qū)為目標(biāo)類，高灰度區(qū)為背景類，令

2.3 三維指數(shù)灰度熵閾值法

在三維直方圖中，若(s，t，q)為閾值分割點(diǎn)，忽略掉遠(yuǎn)離直方圖對角線上的分布點(diǎn)，可得目標(biāo)類指數(shù)灰度熵為：

3 降維處理和搜索策略的優(yōu)化

3.1 三維指數(shù)灰度熵法的降維處理

三維閾值法能夠有效提高一維閾值法的抗噪性能，但閾值搜索空間的擴(kuò)展也使得計(jì)算復(fù)雜度以指數(shù)級方式大幅攀升。文獻(xiàn)[17]針對二維Otsu方法，在忽略直方圖中遠(yuǎn)離對角線的噪聲點(diǎn)和邊緣點(diǎn)的前提下，提出求解兩個(gè)一維Otsu閾值來代替原始二維Otsu閾值的方法，使計(jì)算復(fù)雜度降低到O(L)。文獻(xiàn)[18]通過對三維Otsu進(jìn)行分解，使計(jì)算復(fù)雜度降低到O(L)。基于類似思想，推導(dǎo)出三維指數(shù)灰度熵的降維公式。

在三維直方圖中，令像素灰度值、鄰域均值、鄰域中值的邊緣頻數(shù)為F(i)、V(j)、R(k)，則

F(i)、V(j)、R(k)也可以認(rèn)為是原圖像、鄰域均值圖像、鄰域中值圖像的灰度直方圖。

設(shè)三維直方圖中遠(yuǎn)離對角線分量近似為0，則有：

由式（20）和式（21）可知，通過降維處理，最佳三維閾值的計(jì)算復(fù)雜度降至O(L)。

3.2 搜索策略的優(yōu)化

在降維處理的基礎(chǔ)上，本文考慮一種閾值搜索的優(yōu)化策略，使算法的計(jì)算復(fù)雜度進(jìn)一步降低。優(yōu)化搜索策略的流程框圖如圖2所示。

圖2 優(yōu)化搜索策略的流程框圖

步驟1設(shè)圖像總的灰度級為L，在三維直方圖上將各

步驟3利用降維方式先在縮小的三維直方圖上尋找到初始閾值(s1，t1，q1)，并由該點(diǎn)求得對應(yīng)的原三維直方圖小區(qū)域?yàn)棣譻1t1q1，其坐標(biāo)軸取值范圍為s1m≤i≤(s1+1)m-1，t1m≤j≤(t1+1)m-1，q1m≤k≤(q1+1)m-1。

步驟4利用降維方式在ψs1t1q1區(qū)域上搜索，得到最終閾值(s2，t2，q2)。

利用上述優(yōu)化搜索策略，可知計(jì)算復(fù)雜度滿足：坐標(biāo)取值范圍均分為n段，每段有m=L/n個(gè)灰度級，則三維直方圖空間被分成n×n×n的多個(gè)小區(qū)域，設(shè)小區(qū)域記為ψxyz，其中0≤x，y，z≤n-1。

步驟2將每個(gè)小區(qū)域由一個(gè)點(diǎn)來代替，則原三維直方圖縮小為n×n×n的三維直方圖，該直方圖中每一點(diǎn)的值表示三元組(x，y，z)發(fā)生的頻數(shù)，即有：

當(dāng)n=L1/2時(shí)，計(jì)算復(fù)雜度最小，為O(L1/2)，可見采用優(yōu)化搜索策略可進(jìn)一步減少運(yùn)算時(shí)間。

4 實(shí)驗(yàn)結(jié)果及分析

仿真實(shí)驗(yàn)是在AMD Athlon II X4 640，3.01 GHz CPU和內(nèi)存3.25 GB的微處理器上進(jìn)行的，編程環(huán)境為Matlab7.9。實(shí)驗(yàn)分別采用文獻(xiàn)[9]中二維Shannon熵斜分法、文獻(xiàn)[10]中二維交叉熵遞推法、文獻(xiàn)[18]中三維Otsu分解法以及本文提出的算法對多幅圖像進(jìn)行閾值分割?，F(xiàn)選取其中三幅圖像加以說明，如圖3所示，原圖像分別是混有高斯噪聲和椒鹽噪聲的lena圖、月亮圖以及懷表圖，各算法分割效果如圖4～圖7所示。

圖3 原圖像

圖4 文獻(xiàn)[9]算法結(jié)果

圖5 文獻(xiàn)[10]算法結(jié)果

圖6 文獻(xiàn)[18]算法結(jié)果

圖7 本文算法結(jié)果

從lena圖分割效果來看，本文算法得到的lena的臉部和肩部噪聲干擾是最少的，說明本文算法在抗噪性能上要優(yōu)于其他三種閾值分割算法。從月亮圖和懷表圖的分割結(jié)果來看，由于本文算法兼顧了圖像直方圖的統(tǒng)計(jì)信息和圖像類內(nèi)灰度分布的均勻性，圖像分割效果也是最優(yōu)的。例如在月亮圖的分割中，文獻(xiàn)[9]的算法不能很好地分割出圖像中月亮的總體輪廓，而文獻(xiàn)[10]的算法和文獻(xiàn)[18]的算法則不能很好地分割出月亮上的灰度變化區(qū)域，綜合來看，本文算法兼顧了月亮輪廓和月亮內(nèi)部灰度變化區(qū)域，總體上分割的視覺效果是最優(yōu)的。對于懷表圖的分割，本文的算法和文獻(xiàn)[10]的算法都取得了比較好的分割效果，在分割出懷表的同時(shí)，圖像右下方的標(biāo)尺上的細(xì)節(jié)也能清楚地分割得到，但本文算法在運(yùn)算速度上又具有明顯的優(yōu)勢。

表1和表2給出了各種算法得到的閾值和運(yùn)行時(shí)間的比較，從表中可以看出，與上述文獻(xiàn)所提出的各種算法相比，本文算法的運(yùn)算速度提升明顯，由于將降維處理和優(yōu)化搜索策略相結(jié)合，相對于其他算法中所需時(shí)間最少的三維Otsu分解法，本文算法運(yùn)算時(shí)間也至少減少了20%以上。

表1 不同算法獲得的閾值比較

表2 不同算法獲得的運(yùn)行時(shí)間比較s

5 結(jié)束語

本文提出的指數(shù)灰度熵閾值分割法，既考慮了圖像直方圖的統(tǒng)計(jì)信息，也反映出圖像中目標(biāo)和背景類內(nèi)的灰度分布的均勻性。為了提高抗噪能力，將該算法推廣運(yùn)用到三維直方圖上。由于三維直方圖的搜索空間復(fù)雜度提高到O(L3)，論文采用降維處理與優(yōu)化閾值搜索策略相結(jié)合的方法，將搜索復(fù)雜度降為O(L1/2)。通過對多幅圖像進(jìn)行分割的實(shí)驗(yàn)表明，本文提出的算法抗噪性能更好，分割效果更優(yōu)，且運(yùn)行時(shí)間大為減少。

[1]王愛民，沈蘭蓀.圖像分割研究綜述[J].測試技術(shù)，2000，19（5）：1-6.

[2]Sezgin M，Sankur B.Survey over image thresholding techniques and quantitative performance evaluation[J].Journal of Electronic Imaging，2004，13（1）：146-168.

[3]曹建農(nóng).圖像分割的熵方法綜述[J].模式識別與人工智能，2012，25（6）：958-971.

[4]唐新亭，張小峰，鄒海林.圖像分割的最大熵方法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（1）：212-215.

[5]張俊娜，馮云芝.基于量子最大熵多閾值算法的圖像分割研究[J].激光與紅外，2013，43（5）：578-582.

[6]曹建農(nóng).基于直方圖重構(gòu)的極大交叉熵圖像分割方法[J].計(jì)算機(jī)應(yīng)用，2008，44（18）：177-180.

[7]周理，高山，畢篤彥，等.基于視覺側(cè)抑制機(jī)理的強(qiáng)魯棒性圖像分割方法[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，44（5）：1910-1917.

[8]聶方彥，屠添翼，潘梅森，等.紅外人體圖像模糊Renyi熵快速分割[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（7）：183-186.

[9]吳一全，潘喆，吳文怡.二維直方圖區(qū)域斜分的最大熵閾值分割算法[J].模式識別與人工智能，2009，22（1）：162-168.

[10]雷博，范九倫.灰度圖像的二維交叉熵閾值分割法[J].光子學(xué)報(bào)，2009，38（6）：1572-1576.

[11]Sahoo P K.A thresholding method based on two-dimensional Renyi’s entropy[J].Pattern Recognition，2004，37（6）：1149-1161.

[12]Sahoo P K，Arora G.Image thresholding using two-dimensional Τsallis-Havrda-Charvat entropy[J].Pattern Recognition Letters，2006，27（6）：520-528.

[13]張曉杰，吳一全，吳詩婳.基于分解的二維指數(shù)交叉熵圖像閾值分割[J].信號處理，2011，27（4）：546-551.

[14]龍建武，申鉉京，魏巍，等.一種結(jié)合紋理信息的三維Renyi熵閾值分割算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，32（5）：947-952.

[15]王菲菲，龔劬，倪麟，等.基于三維直方圖重建和降維的Renyi熵閾值分割算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30（4）：1223-1225.

[16]Pal S K，Pal N R.Entropic thresholding[J].Signal Processing，1989，16（2）：97-108.

[17]岳峰，左旺孟，王寬全.基于分解的灰度圖像二維閾值選取算法[J].自動化學(xué)報(bào)，2009，35（7）：1022-1027.

[18]龔劬，倪麟，唐萍峰.基于分解的三維Otsu圖像分割快速算法[J].計(jì)算機(jī)應(yīng)用，2012，32（6）：1526-1528.

ZHANG Shuzhen,HUANG Guangya

School of Information Science and Engineering,Jishou University,Jishou,Hunan 416000,China

In view of the existing threshold segmentation methods which usually only consider the statistical information from image histogram,while ignoring the gray distribution uniformity of the image target class and the background class,one-dimensional exponential gray entropy segmentation algorithm is put forward and three-dimensional exponential gray entropy segmentation algorithm is deduced.Τhe principles of one-dimensional exponential gray entropy algorithm and three-dimensional exponential gray entropy algorithm are presented.Τhe optimum segmentation threshold is got by combining dimension reduction and optimal search strategy on the three-dimensional histogram.Τhe search complexity is reduced fromO(L3)toO(L1/2)in theory.Experimental results show that,compared with other existing threshold algorithms,the proposed algorithm has better anti-noise performance, segmentation effect and its operation time is reduced greatly.

threshold segmentation;three-dimensional histogram;exponential gray entropy;dimension reduction method; search strategy

針對現(xiàn)有閾值分割法通常只考慮圖像直方圖的統(tǒng)計(jì)信息，而忽略了圖像目標(biāo)和背景類內(nèi)灰度分布的均勻性，提出指數(shù)灰度熵分割算法，并推廣得到三維指數(shù)灰度熵分割算法。給出了一維指數(shù)灰度熵閾值法及三維指數(shù)灰度熵閾值法的原理，在三維直方圖上，將降維處理和優(yōu)化搜索策略相結(jié)合，得到最優(yōu)分割閾值。理論證明，閾值搜索復(fù)雜度由原來的O(L3)降至O(L1 2)。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的多種閾值法相比，所提算法抗噪性能更強(qiáng)、分割效果更優(yōu)，且運(yùn)算時(shí)間大為減少。

閾值分割；三維直方圖；指數(shù)灰度熵；降維處理；搜索策略

A

ΤP391.41

10.3778/j.issn.1002-8331.1307-0052

ZHANG Shuzhen,HUANG Guangya.Fast image segmentation algorithm based on three-dimensional exponential gray entropy.Computer Engineering and Applications,2013,49（21）：119-122.

國家自然科學(xué)基金（No.61262032）；湖南省教育廳科學(xué)研究項(xiàng)目（No.12C0314）。

張書真（1977—），女，講師，研究領(lǐng)域?yàn)閳D像處理、模式識別、網(wǎng)絡(luò)編碼；黃光亞（1981—），女，講師，研究領(lǐng)域?yàn)樾盘柼幚?、模式識別。E-mail：sunny_zsz@126.com

2013-07-04

2013-08-09

1002-8331（2013）21-0119-04