賀建峰，符 增，相 艷，易三莉，崔 銳

（昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，昆明650500）

基于灰度空間相關(guān)性最大類間方差的圖像分割

賀建峰，符 增，相 艷，易三莉，崔 銳

（昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，昆明650500）

一維最大類間方差1D-Otsu和二維最大類間方差2D-Otsu在目標(biāo)和背景比較模糊時(shí)，圖像分割效果較差。針對該問題，提出一種基于灰度空間相關(guān)性（GLSC）最大類間方差的圖像分割算法。該算法使用各像素的灰度值與其鄰域內(nèi)相似像素的數(shù)目構(gòu)建直方圖，通過計(jì)算GLSC直方圖的最大類間方差得到分割閾值，應(yīng)用積分圖的思想將運(yùn)算復(fù)雜度由O（（N2×L）2）降到O（N2×L），節(jié)省了運(yùn)算時(shí)間。針對5幅大小不同和直方圖類型不同的真實(shí)圖像，與1DOtsu、2D-Otsu和灰度空間相關(guān)性熵算法進(jìn)行分割實(shí)驗(yàn)比較，結(jié)果表明該算法具有較好的魯棒性。

最大類間方差；灰度空間相關(guān)性；直方圖；積分圖；圖像分割；熵算法

1 概述

一般來說，圖像分割方法可以分成4類，即閾值分割、基于邊界的分割、基于區(qū)域的分割和混合的分割技術(shù)［1］。在以上的分割技術(shù)中，閾值分割是最簡單和有效的一種分割方法。它是在待處理圖像中選擇一個(gè)能夠辨別圖像背景和目標(biāo)的閾值進(jìn)行判別，若低于該閾值就作為圖像的背景，高于該閾值則作為圖像的目標(biāo)。

在過去的幾十年中，國內(nèi)外學(xué)者提出了大量的閾值選取方法，如基于最大類間方差（Otsu）［2-4］、各種熵［5-7］和模糊集［8-10］等多種類型的閾值選取方法。Otsu方法是一種全局的自動(dòng)非參數(shù)無監(jiān)督的閾值選取算法，它是基于類間方差為最大的測度準(zhǔn)則［11］。熵方法是運(yùn)用信息論原理解決圖像分割問題的一種方法。模糊集理論運(yùn)用描述圖像信息中的模糊性來分割圖像。以上面3種原理為基礎(chǔ)的閾值分割算法，其共同點(diǎn)是先構(gòu)建圖像直方圖，然后選用適當(dāng)?shù)姆椒▽ふ易罴验撝担?，5，8］。

在構(gòu)建圖像直方圖過程中，現(xiàn)有的一維閾值方法共同缺點(diǎn)是忽略了圖像不同灰度層次的空間相關(guān)性。只有包含更多圖像信息才能更好地分割圖像。為此，在熵閾值方法中，以文獻(xiàn)［5］為基礎(chǔ)，文獻(xiàn)［6，12-13］利用像素灰度和鄰域平均灰度構(gòu)建了二維直方圖，然后再利用有關(guān)熵的閾值方法確定最佳閾值。在模糊集方法中，以文獻(xiàn)［8］為基礎(chǔ)，文獻(xiàn)［9］將二維直方圖方法運(yùn)用于模糊集理論中。在Otsu閾值方法中，以O(shè)tsu［2］理論為基礎(chǔ)，提出2D-Otsu算法［3］。在2DOtsu算法的基礎(chǔ)上，在構(gòu)建二維直方圖的過程中，又加入了鄰域灰度的中值作為特征，形成了三維直方圖［4，14］，并運(yùn)用Otsu閾值方法來尋找最佳閾值。然而高維直方圖理論存在算法復(fù)雜度高和可能丟失有用信息的缺點(diǎn)［15］。

近年來，許多學(xué)者提出了一些新的構(gòu)建直方圖的思想。文獻(xiàn)［16-17］于2010年提出了灰度空間相關(guān)性（Gray-level Spatial Correlation，GLSC）直方圖，即使用各像素的灰度值與其鄰域內(nèi)相似像素的數(shù)目所創(chuàng)建而成，并將該思想與熵閾值方法相結(jié)合來分割圖像，得到了不錯(cuò)的分割效果。文獻(xiàn)［10］于2011年在GLSC直方圖中嵌入了人類視覺非線性特征（Human V isual Nonlinearity Characteristics，HVNC），并利用類型2模糊集的閾值方法來選擇最佳閾值，也得到了很好的分割效果。2013年Yim it［18］引進(jìn)了灰度和方向梯度來辨別像素的空間信息，提出了灰度-方向梯度熵算法，但是僅運(yùn)用梯度方向很難描述圖像的邊緣屬性。2014年Xiao［19］提出了灰度-梯度幅度直方圖，并運(yùn)用熵的閾值方法尋找圖像的最佳閾值，該方法更依賴于圖像輪廓的提取。當(dāng)輪廓模糊時(shí)，其區(qū)分邊緣的能力較差。

針對目標(biāo)和背景比較模糊的圖像，邊緣被認(rèn)為是比目標(biāo)和背景更為重要的信息，GLSC直方圖在突出邊緣信息方面有其獨(dú)特的優(yōu)勢［17］。X iao于2014年驗(yàn)證了Otsu的閾值方法比大多數(shù)熵的閾值方法對閾值分割有更好的效果［19］。為此，本文將GLSC直方圖與Otsu算法相結(jié)合。提出一種新的基于灰度空間相關(guān)性最大類間方差的圖像分割算法（GLSC-Otsu）。構(gòu)建鄰域?yàn)镹×N的GLSC直方圖，計(jì)算GLSC直方圖的最大類間方差，將得到的類間方法值乘以關(guān)于m（在相同像素值中，其鄰域的相似像素個(gè)數(shù)的總數(shù)）和N的加權(quán)非線性函數(shù)。最佳閾值為當(dāng)GLSC直方圖的類間方差與加權(quán)非線性函數(shù)乘積取最大值時(shí)所得到的解，同時(shí)還引進(jìn)了V iola［20］提出的積分圖思想對GLSC-Otsu進(jìn)行快速閾值選擇，降低算法運(yùn)算復(fù)雜度。

2 灰度空間相關(guān)性直方圖的創(chuàng)建

令f（x，y）為圖像大小為Q×R即F=｛f（x，y）|x∈｛1，2，…，Q｝，y∈｛1，2，…，R｝｝位于（x，y）處的灰度值。構(gòu)建GLSC直方圖如下：對于位于（x，y）處的像素點(diǎn)而言，設(shè)g（x，y）表示像素相鄰取N×N時(shí)，相似像素的個(gè)數(shù)，其中，N通常取奇數(shù)。g（x，y）的計(jì)算方法為：

其中：

ζ表示歸類為相似像素的幅度值（如：若ζ=3，表示在a±3的范圍內(nèi)的像素值都與像素a相似）。

本文運(yùn)用圖像灰度值f（x，y）和鄰域像素相似個(gè)數(shù)g（x，y）來創(chuàng)建GLSC直方圖，計(jì)算公式為：

p（k，m）=Prob（f（x，y）=k and g（x，y）=m）（3）其中，k為圖像灰度值，k∈｛0，1，…，255｝；m為鄰域像素相似個(gè)數(shù)，m∈｛1，2，…，N×N｝；p（k，m）為統(tǒng)計(jì)整幅圖像中，以像素灰度值k為中心的N×N鄰域內(nèi)，及其像素值相似數(shù)目為m的像素個(gè)數(shù)與整幅圖像的像素總數(shù)的比值，其具體的計(jì)算公式為：

其中，f（k，m）表示統(tǒng)計(jì)整幅圖像中，以像素灰度值k為中心的N×N鄰域內(nèi)，與其像素值相似數(shù)目為m的像素個(gè)數(shù)；S×R表示整幅圖像的像素總數(shù)。取ζ=3和N=17，所建的GLSC直方圖如圖1所示。

圖1 Cam eram an原圖、一維直方圖和GLSC直方圖

3 GLSC最大類間方差分割法

由圖1（c）可得，將圖像直方圖劃分成了256× 289的二維直方圖，其平面簡圖如圖2所示。

圖2 GLSC直方圖平面簡圖

假設(shè)圖像的分割閾值為（s，t），可以將直方圖劃分成C0，C1，C2，和C34類，它們分別代表邊緣、物體、噪聲和背景，具有4個(gè)不同的概率密度函數(shù)分布。那么它們出現(xiàn)的概率分別為：

4類對應(yīng)的均值矢量μ0，μ1，μ2和μ3分別為：

定義一個(gè)類間的離散矩陣如式（14）所示，矩陣SB的跡作為類間的離散度測量，且由式（9）～式（12）可得μ0i=μi0/ω0；μ1i=μi1/ω1；μ2i=μi2/ω2；μ3i=μi3/ω3；μ0j=μj0/ω0；μ1j=μj1/ω1；μ2j=μj2/ω2和μ3j=μj3/ω3。

即trSB可得如式（15）所示：

圖3 N=17時(shí)的函數(shù)曲線

最佳閾值（s*，t*）滿足下式：

為了求得最佳閾值，需要在N2×L的投影平面內(nèi)搜索。每一個(gè)閾值都會(huì)把投影平面劃分成4個(gè)區(qū)域。因此，若忽略直方圖的提取時(shí)間，灰度空間相關(guān)性最大類間方差法的計(jì)算復(fù)雜度性為：

隨著N值得增大計(jì)算復(fù)雜度呈指數(shù)增長，無疑限制了本文方法的運(yùn)用。為此，本文提出了采用積分圖快速選取閾值的方法。

4 積分圖快速選取閾值方法

積分圖是用來求圖像特征值時(shí)提出的概念［20-21］。在積分圖（x，y）的位置是在原圖（x′，y′）位置左上角所有的像素之和。其示意圖如圖4所示，ii（x，y）為左上角陰影部分的像素之和。具體的定義為：

其中，ii（x，y）表示積分圖；i（x′，y′）表示原圖。

圖4 積分圖原理

從上一節(jié)算法公式可以看出，計(jì)算trSB需要計(jì)算ω0，ω1，ω2，ω3，μi0，μi1，μi2，μi3，μj0，μj1，μj2，μj3，μTi和μTj。對于同一副圖像，μTi和μTj是固定的。對于每一個(gè)閾值（s*，t*），如果每次計(jì)算類間離散度測量trSB都必須重新從i=0，j=0開始計(jì)算。由上一節(jié)分析得計(jì)算復(fù)雜度為O（（N2×L）2）。本文運(yùn)用積分圖的思想快速選擇閾值。

設(shè)生成的GLSC直方圖為ω對應(yīng)的積分圖為ω-ii，即ω0，ω1，ω2和ω3計(jì)算公式如下：

上述方法將求不同區(qū)域的概率，最多只要經(jīng)過幾步加減算法即可得到。計(jì)算μi0，μi1，μi2，μi3和μj0，μj1，μj2，μj3時(shí)，只需先進(jìn)行一維的計(jì)算，然后經(jīng)過加減法運(yùn)算即可得到。這樣就將時(shí)間復(fù)雜度L（（N2×L）2）降到了L（N2×L）。大大的節(jié)省了運(yùn)行時(shí)間和存儲空間。

5 仿真結(jié)果與分析

在本文實(shí)驗(yàn)中，選取5幅不同大小和不同直方圖分布類型的真實(shí)圖像，來測試本文算法的有效性和魯棒性。它們分別是Ant（357×370像素）、Bacteria（364×364像素）、Block（244×244像素）、Cameraman（256×256像素）和Laser（304×233像素）。

表1列出了當(dāng)取N=17，而ζ=1，2，…，9時(shí)分割該5幅圖像的最佳閾值。以分類錯(cuò)誤率［10，19］為標(biāo)準(zhǔn)，當(dāng)取ζ=3時(shí)，整體能產(chǎn)生最好的分割效果。本文針對鄰域大小為3×3，5×5，7×7，9×9，11×11，13×13，15×15和19×19用相同的方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)表明當(dāng)N=17，ζ=3時(shí)分割效果最佳。下面的實(shí)驗(yàn)本文方法的參數(shù)取N=17和ζ=3。實(shí)驗(yàn)是在3.20 GHz CPU和4 GB內(nèi)存的PC機(jī)，M atlab7.1環(huán)境中進(jìn)行的。

表1 不同ζ所得的最佳閾值

如圖5～圖14所示，本文算法與1D-Otsu理論［2］、2D-Otsu理論［3］和GLSC KSW熵理論［16-17］進(jìn)行比較。

圖5 Ant的分割結(jié)果

圖6 Ant的直方圖

圖7 Bacteria的分割結(jié)果

圖8 Bacteria的直方圖

圖9 Block的分割結(jié)果

圖10 Block的直方圖

圖11 Cam eram an的分割結(jié)果

圖12 Cam eram an的直方圖

圖13 Laser的分割結(jié)果

圖14 Laser的直方圖

本文運(yùn)用分類錯(cuò)誤率來判斷分割的性能［10，19］。給出如下公式：

其中，λ∈［0，1］，其值越接近1，表明分割效果越好；BO和FO分別代表分割后標(biāo)準(zhǔn)圖像的前景和背景；BR和FR分別代表分割后圖像的前景和背景；表示一組基數(shù)。

不同算法依據(jù)上述評價(jià)所得的分割精度如表2所示，其中，加粗的數(shù)據(jù)表示最優(yōu)數(shù)據(jù)。表2中的平均分割精度（）和標(biāo)準(zhǔn)差（σ）用于評估不同算法整體的有效性和魯棒性。

表2 不同算法所得分割精度%

表3和表4分別顯示了不同算法的閾值和不同算法所消耗的時(shí)間。

表3 不同算法所得的分割閾值

表4 不同算法所消耗的時(shí)間s

可以看出：

（1）1D-Otsu和2D-Otsu對圖Bacteria和Block的分割效果都比較差，因?yàn)檫@3幅圖的目標(biāo)和背景界限模糊，這2種算法很難區(qū)分背景和目標(biāo)的邊緣，導(dǎo)致了分割效果不佳。

（2）GLSC KSW熵算法雖然針對Bacteria最好的分割效果，但是其他圖像都不如本文算法的效果。因?yàn)殛P(guān)于熵的閾值方法原理不同于Otsu的閾值方法，該方法在大多數(shù)情況下分割圖像比Otsu的閾值方法要差［19］。

（3）基于灰度空間相關(guān)性最大類間方差的圖像分割算法在絕大多數(shù)情況下都能得到最佳的分割效果。該算法與其他3種算法比較，它具有最高平均分割精度（97.76%）和最低的標(biāo)準(zhǔn)差（1.44%）。

（4）表4對比了不同方法分割圖像所消耗的時(shí)間，本文算法較1D-Otsu慢，但是比2D-Otsu快了很多。與GLSC KSW算法速度相差不大，因?yàn)樗惴◤?fù)雜度都是O（N2×L），但是由于本文算法的N值為17，而GLSC KSW熵算法的N取3，這樣導(dǎo)致了本文算法慢于GLSC KSW熵算法。因此，以上實(shí)驗(yàn)數(shù)據(jù)都證明了本文算法對分割自然圖像具有較好的有效性和魯棒性。

6 結(jié)束語

本文提出一種基于灰度空間相關(guān)性最大類間方差的圖像分割方法。該算法比1D-Otsu和2D-Otsu算法在構(gòu)建直方圖方法上具有更強(qiáng)的分辨邊緣的能力，比GLSC KSW熵算法具有更好的尋找閾值的能力。本文通過使用5幅大小不同和具有不同直方圖類型的自然圖像進(jìn)行分割實(shí)驗(yàn)比較，結(jié)果表明，該算法較其他算法具有更好的有效性和魯棒性，時(shí)間消耗介于2D-Otsu算法與1D-Otsu算法之間，且與GLSC KSW熵算法的計(jì)算復(fù)雜度相當(dāng)。另外，本文在尋找參數(shù)時(shí)做了大量實(shí)驗(yàn)，針對不同類型圖像，其最佳參數(shù)的取值可能會(huì)不同。因此，下一步的工作內(nèi)容是在構(gòu)建灰度相關(guān)信息直方圖前，分析待分割圖像的先驗(yàn)信息，并將其嵌入到直方圖中尋找最佳參數(shù)。

［1］ Shih F Y.Image Processing and Pattern Recognition：Fundamentals and Techniques［M］.Hoboken，USA：John Wiley&Sons，2010.

［2］ Nobuyuki O.A Threshold Selection Method from Graylevel Histogram［J］.IEEE Transactions on System M an and Cybernetics，1979，9（1）：62-66.

［3］ 劉建莊，栗文青.灰度圖像的二維Otsu自動(dòng)閾值分割法［J］.自動(dòng)化學(xué)報(bào)，1993，19（1）：101-105.

［4］ 景曉軍，李劍鋒，劉郁林.一種基于三維最大類間方差的圖像分割算法［J］.電子學(xué)報(bào)，2003，31（9）：1281-1285.

［5］ Kapur JN，Sahoo P K，W ong A K C A.New Method for Gray-level Picture Thresholding Using the Entropy of the Histogram［J］.Computing Vision，Graphics，and Image Processing，1985，29（3）：273-285.

［6］ Ahmed A S.Automatic Thresholding of Gray-level Pictures Using Two-dimensional Entropy［J］.Computer Vision，Graphics，and Image Processing，1989，47（1）：22-32.

［7］ 張書真.基于三維直方圖修正和灰度熵分解的圖像分割［J］.計(jì)算機(jī)工程，2014，40（5）：234-237，242.

［8］ Huang Liangkai，Wang Maoyun.Image Thresholding by Minimizing the Measure of Fuzziness［J］.Pattern Recognition，1995，28（1）：41-51.

［9］ W ang Qing，Chi Zheru，Zhao Rongchun.Image Thresholding by Maximizing the Index of Nonfuzziness of the 2-D Grayscale Histogram［J］.Computer Vision and Image Understanding，2002，85（1）：100-116.

［10］ X iao Yang，Cao Zhiguo，Zhuo W en.Type-2 Fuzzy Thresholding Using GLSC Histogram of Hum an Visual Nonlinearity Characteristics［J］.Optics Express，2011，19（11）：10656-10672.

［11］ 王海洋，潘德爐，夏德深.二維Otsu自適應(yīng)閾值選取算法的快速實(shí)現(xiàn)［J］.自動(dòng)化學(xué)報(bào)，2007，33（9）：968-971.

［12］ Sahoo P K，Arora G A.Thresholding Method Based on Two-dimensional Renyi's Entropy［J］.Pattern Recognition，2004，37（6）：1149-1161.

［13］ Sahoo P K，Arora G.Im age Thresholding Using Twodimensional Tsallis-Havrda-Charvát Entropy［J］.Pattern Recognition Letters，2006，27（6）：520-528.

［14］ 張 健，沈春裕，盧 瑾.基于分解的三維Otsu運(yùn)動(dòng)車輛檢測方法［J］.計(jì)算機(jī)工程，2013，39（2）：172-177.

［15］ 陳 琪，熊博蒞，陸 軍，等.改進(jìn)的二維Otsu圖像分割方法及其快速實(shí)現(xiàn)［J］.電子與信息學(xué)報(bào)，2010，32（5）：1100-1104.

［16］ Xiao Yang，Cao Zhiguo，Zhang Tianxu.Entropic Thresholding Based on Gray-level Spatial Correlation Histogram［C］// Proceedings of IEEE Conference on Pattern Recognition. Washington D.C.，USA：IEEE Press，2008：1-4.

［17］ Xiao Yang，Cao Zhiguo，Zhong Sheng.New Entropic Thresholding Approach Using Gray-level Spatial Correlation Histogram［J］.Optical Engineering，2010，49（12）.

［18］ Yim it A，Hagihara Y，Miyoshi T，et al.2-D Direction Histogram Based Entropic Thresholding［J］.Neuro Computing，2013，120（23）：287-297.

［19］ Xiao Yang，Cao Zhiguo，Yuan Junsong.Entropic Image Thresholding Based on GLGM Histogram［J］.Pattern Recognition Letters，2014，40（1）：47-55.

［20］ Viola P，Jones M.Rapid Object Detection Using a Boosted Cascade of Simple Features［J］.Computing Vision and Pattern Recognition，2001，14（1）：8-14.

［21］ 傅紅普，鄒北驥.方向梯度直方圖及其擴(kuò)展［J］.計(jì)算機(jī)工程，2013，39（5）：212-217.

編輯 劉冰

Image Segmentation Based on G ray-level Spatial Correlation Maxim um Between-cluster Variance

HE Jianfeng，F(xiàn)U Zeng，XIANG Yan，YI Sanli，CUI Rui
（School of Information Engineering and Automation，Kunming University of Science and Technology，Kunming 650500，China）

W hen processing an image with the blurred background and target，image segmenting effect by maximum between cluster variance 1D-Otsu and 2D-Otsu is not good.A method for image segmentation based on Gray-level Spatial Correlation（GLSC）maximum between-cluster variance is proposed.The proposed algorithm uses the gray value of the pixels and their similarity with neighboring pixels in gray value to build a histogram which is called GLSC histogram. Then threshold value is obtained by calculating GLSC histogram maximum between-class variance.Integrogram is introduced in order to make the time complexity reduced from original O（（N2×L）2）to O（N2×L）.Comparing the proposed algorithm wth 1D-Otsu，2D-Otsu and GLSC entropy algorithm for segmenting 5 different real images，the proposed algorithm show s better robustness.

maximum between-cluster variance；Gray-level Spatial Correlation（GLSC）；histogram；integrogram；image segmentation；entropy algorithm

賀建峰，符 增，相 艷，等.基于灰度空間相關(guān)性最大類間方差的圖像分割［J］.計(jì)算機(jī)工程，2015，41（11）：280-286.

英文引用格式：He Jianfeng，F(xiàn)u Zeng，Xiang Yan，et al.Image Segmentation Based on Gray-level Spatial Correlation Maximum Between-cluster Variance［J］.Computer Engineering，2015，41（11）：280-286.

1000-3428（2015）11-0280-07

A

TP391.4

10.3969/j.issn.1000-3428.2015.11.048

國家自然科學(xué)基金資助項(xiàng)目（11265007）；教育部留學(xué)回國人員科研啟動(dòng)基金資助項(xiàng)目（2010-1561）。

賀建峰（1965-），男，教授、博士，主研方向：圖形圖像處理，模式識別；符 增，碩士研究生；相 艷，講師、碩士；易三莉，講師、博士；崔 銳，碩士研究生。

2014-11-18

2014-12-18 E-m ail：jfenghe@qq.com