基于灰度空間相關性最大類間方差的圖像分割

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

（昆明理工大學信息工程與自動化學院，昆明650500）

基于灰度空間相關性最大類間方差的圖像分割

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

（昆明理工大學信息工程與自動化學院，昆明650500）

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

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

1 概述

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

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

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

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

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

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

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

其中：

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

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

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

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

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

3 GLSC最大類間方差分割法

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

圖2 GLSC直方圖平面簡圖

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

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

定義一個類間的離散矩陣如式（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ù)曲線

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

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

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

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

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

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

圖4 積分圖原理

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

設生成的GLSC直方圖為ω對應的積分圖為ω-ii，即ω0，ω1，ω2和ω3計算公式如下：

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

5 仿真結果與分析

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

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

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

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

圖5 Ant的分割結果

圖6 Ant的直方圖

圖7 Bacteria的分割結果

圖8 Bacteria的直方圖

圖9 Block的分割結果

圖10 Block的直方圖

圖11 Cam eram an的分割結果

圖12 Cam eram an的直方圖

圖13 Laser的分割結果

圖14 Laser的直方圖

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

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

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

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

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

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

表4 不同算法所消耗的時間s

可以看出：

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

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

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

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

6 結束語

本文提出一種基于灰度空間相關性最大類間方差的圖像分割方法。該算法比1D-Otsu和2D-Otsu算法在構建直方圖方法上具有更強的分辨邊緣的能力，比GLSC KSW熵算法具有更好的尋找閾值的能力。本文通過使用5幅大小不同和具有不同直方圖類型的自然圖像進行分割實驗比較，結果表明，該算法較其他算法具有更好的有效性和魯棒性，時間消耗介于2D-Otsu算法與1D-Otsu算法之間，且與GLSC KSW熵算法的計算復雜度相當。另外，本文在尋找參數(shù)時做了大量實驗，針對不同類型圖像，其最佳參數(shù)的取值可能會不同。因此，下一步的工作內容是在構建灰度相關信息直方圖前，分析待分割圖像的先驗信息，并將其嵌入到直方圖中尋找最佳參數(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自動閾值分割法［J］.自動化學報，1993，19（1）：101-105.

［4］ 景曉軍，李劍鋒，劉郁林.一種基于三維最大類間方差的圖像分割算法［J］.電子學報，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］.計算機工程，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自適應閾值選取算法的快速實現(xiàn)［J］.自動化學報，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運動車輛檢測方法［J］.計算機工程，2013，39（2）：172-177.

［15］ 陳 琪，熊博蒞，陸 軍，等.改進的二維Otsu圖像分割方法及其快速實現(xiàn)［J］.電子與信息學報，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］ 傅紅普，鄒北驥.方向梯度直方圖及其擴展［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

賀建峰，符 增，相 艷，等.基于灰度空間相關性最大類間方差的圖像分割［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

國家自然科學基金資助項目（11265007）；教育部留學回國人員科研啟動基金資助項目（2010-1561）。

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

2014-11-18

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