程 全， 劉曉青， 劉玉春， 王志良

(1.周口師范學(xué)院 機(jī)械與電氣工程學(xué)院，河南 周口 466001； 2.北京科技大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，北京 100083)

基于Mean Shift聚類的多級(jí)閾值化方法

程 全1， 劉曉青1， 劉玉春1， 王志良2

(1.周口師范學(xué)院 機(jī)械與電氣工程學(xué)院，河南 周口 466001； 2.北京科技大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，北京 100083)

為了解決多級(jí)閾值化技術(shù)中所選閾值的數(shù)量通常不能預(yù)先確定的問題，提出一種基于Mean Shift 聚類技術(shù)的新型多級(jí)閾值化方法.首先，通過使用Mean Shift技術(shù)探尋出潛在的模式中心，應(yīng)用迭代的閾值選擇方法來自動(dòng)確定相鄰模式中心的各個(gè)閾值；然后，采用多級(jí)閾值化對(duì)圖像進(jìn)行分割； 最后，通過實(shí)驗(yàn)驗(yàn)證了基于Mean Shift聚類技術(shù)分割的圖像相對(duì)于原始圖像的對(duì)比度有了很大提高.該方法通過簡(jiǎn)單修改程序參數(shù)就能夠靈活控制分割精度，可以廣泛應(yīng)用于單閾值分割、多級(jí)閾值分割和有損壓縮等技術(shù)中.

多級(jí)閾值化； 圖像分割； 迭代閾值化； 分割質(zhì)量評(píng)估

0 引言

圖像分割是進(jìn)行圖像理解和目標(biāo)識(shí)別的一個(gè)必不可少的步驟，圖像分割技術(shù)分為軟分割和硬分割[1].聚類算法是軟分割方法中最主要的圖像分割算法，主要有兩種：一種是K-means聚類[2]，其優(yōu)點(diǎn)是易于實(shí)現(xiàn)但需要預(yù)先指定待分割圖像中需要形成的群集的數(shù)量及中心; 另一種是模糊聚類[3]，當(dāng)圖像中不同物體之間沒有明顯的邊界時(shí)，可以基于相似性準(zhǔn)則采用模糊聚類的方法進(jìn)行處理，但是它對(duì)噪聲特別敏感，并且模糊關(guān)系的確定也非常繁瑣.軟分割計(jì)算起來相當(dāng)費(fèi)時(shí)；而硬分割是一種基于亮度信息的分割方法，它假設(shè)圖像的直方圖含有一個(gè)或多個(gè)峰值[4]，不需要圖像的先驗(yàn)信息、計(jì)算簡(jiǎn)單，實(shí)時(shí)性高,但它忽略了圖像的空間信息，閾值選擇不當(dāng)，經(jīng)常會(huì)導(dǎo)致過分割或欠分割.實(shí)際上，該方法可以被認(rèn)為是一個(gè)多級(jí)閾值化問題，其中所選取的多個(gè)閾值對(duì)應(yīng)于相鄰顯著峰值的峰谷點(diǎn).

多級(jí)閾值化技術(shù)將圖像的直方圖分為幾個(gè)部分，當(dāng)某一圖像像素的特征值位于由某一對(duì)相鄰閾值確定的范圍時(shí)，該像素就被分到某一相應(yīng)的部分.為了解決多閾值分割難題，近年來群智能技術(shù)被用來尋找最優(yōu)閾值.Raja 等人[5]采用一個(gè)改進(jìn)的粒子群(PSO)算法用于惡性腫瘤熱圖像的多閾值分割.Sarkar等[6]基于差分進(jìn)化算法(DE)和最小交叉熵提出了一種新穎的多閾值彩色圖像分割方法.

盡管上述方法可以確定出最優(yōu)閾值，但是不能提供對(duì)應(yīng)于圖像直方圖中潛在模式數(shù)量最優(yōu)閾值數(shù).因此，筆者提出了一種新型的最優(yōu)多級(jí)閾值化方法，特別適用于具有多模態(tài)直方圖的圖像.首先使用Mean Shift程序確定出直方圖的各個(gè)模態(tài)中心；然后使用一種迭代的閾值選取方法來確定相鄰模態(tài)中心的各個(gè)閾值；最后利用已經(jīng)確定的多個(gè)閾值對(duì)圖像進(jìn)行多閾值化分割.

1 算法部分

1.1MeanShift

Mean Shift是一種非參數(shù)化的聚類方法[7]，其最大優(yōu)點(diǎn)是它無須預(yù)先給出聚類的數(shù)量，且對(duì)聚類的形狀也沒有任何限制.作為一個(gè)迭代的模式探尋方法，Mean Shift程序利用核來計(jì)算觀察窗口的特征加權(quán)平均，并可以準(zhǔn)確地定位出聚類的中心并完成特征空間的劃分.

對(duì)于d維空間Rd上的一個(gè)n點(diǎn)的數(shù)據(jù)集合{xi}i=1,…,n，點(diǎn)x處的多變量核密度估計(jì)為

(1)

式中：k(x)是側(cè)面輪廓函數(shù)；h是窗口半徑.令式(1)的梯度為0，得到密度函數(shù)的駐點(diǎn)為

(2)

式中:g(x)=-k′(x)是核函數(shù)G(x)的側(cè)面輪廓函數(shù).

連續(xù)迭代計(jì)算Mean Shift 矢量，并進(jìn)行移位直到程序收斂，就能定位出局部模態(tài).迭代的方程為

(3)

式中：y1為核窗口的初始位置中心；yj+1為yj處利用核G和窗口半徑h計(jì)算出的加權(quán)平均.

對(duì)于Epanechnikov核為

(4)

式中：cd為單位d維球體的體積.

Mean Shift 的公式為

(5)

式中:Sh(yj)為中心位于yj；半徑為h；包含nyj個(gè)數(shù)據(jù)點(diǎn)的超球體.

選擇圖像像素的灰度值作為特征空間，Mean Shift 程序可以探尋出其潛在的概率密度模態(tài). 算法的步驟描述如下：

(1)將特征空間劃分為n個(gè)非重合的同等大小部分.每一部分的大小為(Gmax-Gmin)/n，其中Gmax和Gmin分別為圖像像素灰度值的最大值和最小值.為了避開低密度區(qū)域，要保證每一部分中像素的數(shù)量不少于一個(gè)閾值T1.

(2)運(yùn)行Mean Shift 程序n次以得到n個(gè)收斂點(diǎn)，Mean Shift程序和核半徑為h=(Gmax-Gmin)/n.

(3)將距離小于一個(gè)預(yù)設(shè)閾值T2的相鄰收斂點(diǎn)合并為一點(diǎn)，求出m(mlt;n) 個(gè)潛在的概率密度模態(tài)中心.

為了將圖像灰度分為m個(gè)類，比如0～255，考慮到圖像灰度范圍的上下限已確定，需要再確定K個(gè)閾值，滿足K=m-1.在下文中采用一種迭代閾值選取方法來確定K個(gè)閾值.

1.2多級(jí)閾值化

為了使分割方法更具魯棒性，閾值應(yīng)該能夠自動(dòng)地被確定出來.因此，自動(dòng)閾值選擇是圖像分割的一個(gè)關(guān)鍵步驟.Ridler and Calvard[8]提出了一種迭代的閾值選擇方法，該方法描述如下.

給定一幅圖像，假定I(i,j)是(i,j)處像素的灰度值，其中1≤i≤Mand 1≤j≤N,0≤I(i,j)≤L-1，L為圖像的灰度級(jí)別.首先計(jì)算出圖像的灰度直方圖，假定希望能找到一個(gè)閾值T并利用該閾值將圖像分割為一個(gè)二進(jìn)制圖像.在二進(jìn)制圖像中，所有灰度值低于T的像素，其灰度值都被A所取代；所有灰度值高于T的像素，其灰度值都被B所取代.將誤差函數(shù)定義為二進(jìn)制圖像和原始圖像相應(yīng)像數(shù)灰度值差的平方和.使用積分以方便表達(dá)，則誤差函數(shù)可以表示為：

(6)

式中,k為像素的灰度值；h(k)為灰度值在直方圖中出現(xiàn)的次數(shù).分別令e2對(duì)T、A和B的偏導(dǎo)數(shù)為0可以得到：

(7)

(8)

(9)

實(shí)際上，A和B分別為直方圖被閾值T分成的兩部分的均值.

注意到閾值T僅由兩部分的均值A(chǔ)和B確定，而這兩部分的均值A(chǔ)和B又只有當(dāng)T確定了以后才能被計(jì)算出來.所以需要使用迭代算法：首先選定初始閾值做為起始點(diǎn)；然后利用此閾值將直方圖分為兩個(gè)部分，分別計(jì)算出兩部分的均值，并將閾值更新為兩部分均值的和的一半，該過程反復(fù)執(zhí)行直到閾值收斂；最后利用多閾值化方法圖像的灰度范圍將被K個(gè)閾值分割為K+1個(gè)部分.

給定原始圖像I(i,j)，利用Mean Shift程序確定閾值的數(shù)量K，令Tmin=0及Tmax=L-1，利用迭代閾值選取方法計(jì)算出K個(gè)閾值{T(i)|i=1,2,…,K}，其中T(i)lt;T(i+1).K個(gè)閾值將圖像直方圖分割為m個(gè)互不重疊的區(qū)域：

(10)

其中,J為分割圖像.

2 分割質(zhì)量評(píng)估

圖像分割質(zhì)量的評(píng)估沒有一個(gè)標(biāo)準(zhǔn)的方法，最常用的是主觀評(píng)估，這種方法主觀性太強(qiáng)，而非監(jiān)督性評(píng)估方法由于可以克服上述缺點(diǎn)，受到越來越多的關(guān)注.Haralick等[9]給出了高質(zhì)量圖像分割結(jié)果的四條準(zhǔn)則：①分割出的各個(gè)區(qū)域內(nèi)部像素的特性要盡量一致；②相鄰區(qū)域之間像素特性的差異要大；③區(qū)域內(nèi)部沒有孔洞；④區(qū)域邊界在空間位置上要精確，并且不能支離破碎.

前兩條被用于審查圖像中目標(biāo)的特性，被稱為特性準(zhǔn)則；后兩條被稱為語義準(zhǔn)則，被用來衡量人如何將一個(gè)區(qū)域識(shí)別為一個(gè)目標(biāo)[10].

Zhang[11]引入期望區(qū)域熵作為區(qū)域內(nèi)一致性的度量.假定原始圖像被分割成N個(gè)區(qū)域，采用Rj來表示區(qū)域j(1≤j≤N)中的像素集合；Sj表示區(qū)域j的面積，Sjm表示對(duì)應(yīng)于區(qū)域j的原始圖像中具有灰度值m(0≤m≤L-1)的像素個(gè)數(shù)，那么區(qū)域j的熵定義為

(11)

而分割的期望區(qū)域熵為

(12)

式中：SI是圖像I的面積，表示圖像內(nèi)部具有更高的相似度.

Biswas等[12]提出了用IQI(image quality index)來度量區(qū)域間的差異.對(duì)于一個(gè)行數(shù)和列數(shù)分別為M和N的圖像I，令I(lǐng)(i,j)表示(i,j)處像素的灰度值.則IQI被定義為

(13)

(14)

(15)

IQI反映的是沿著區(qū)域間邊界圖像像素性質(zhì)的平均對(duì)比度，值越大表明圖像的平均對(duì)比度越大.

3 實(shí)驗(yàn)結(jié)果

選擇兩組復(fù)雜度不同的圖像來驗(yàn)證該多閾值圖像分割方法的有效性.第一組圖像是一幅合成圖像“Gray8”；第二組圖像包含從Berkeley Segmentation Dataset[13]選出來的自然圖像35 010、126 007、241 004、113 016、385 039、368 016.筆者提出的多閾值分割方法包括3個(gè)參數(shù)：核半徑h控制著分割的敏感度；閾值T1暗示了特征空間中最小可以接受的概率密度；閾值T2對(duì)應(yīng)于相鄰兩個(gè)收斂點(diǎn)的最小距離.實(shí)驗(yàn)選取h=T2=(Gmax-Gmin)/10，其中，Gmax和Gmin分別為圖像像素灰度值的最大值和最小值；T1=0.001×(M×N)，其中M和N分別為圖像的行列數(shù).

圖1和圖2給出了兩組圖像的分割結(jié)果.中間圖像顯示了直方圖分割的過程示意圖，矩形表示整個(gè)灰度直方圖中被劃分成的幾個(gè)互不重疊的部分，每個(gè)矩形的中心是其Mean Shift程序核窗口的起始點(diǎn)，每一個(gè)五角星代表了相應(yīng)Mean Shift程序的收斂點(diǎn)，如果相鄰收斂點(diǎn)的距離小于核窗口的半徑則將此相鄰收斂點(diǎn)合并以得到模態(tài)中心，各模態(tài)中心用黑色三角形表示，相鄰模態(tài)中間的閾值由迭代閾值選取方法選定并由短劃線表示其位置.

圖1所示的8個(gè)離散的灰度值被成功地檢測(cè)出來(圖1(b))，并給出了比較精確的分割結(jié)果(圖1(c)).對(duì)于圖2中的2幅自然圖像，也給出了令人滿意的分割結(jié)果，并且相對(duì)于原始圖像，分割圖像的對(duì)比度提高了許多.

采用本文方法得到的圖像的分割結(jié)果如圖3所示，從左到右分別為“Lena”“Cameraman”和“Baboon”;其中第一行顯示了原始圖像，第二行為筆者所提多閾值分割方法得到的圖像分割結(jié)果，其中合理選擇分割半徑后得到K=6個(gè)分割閾值.

將本文分割方法與典型的多閾值分割方法PSO及DE算法進(jìn)行了比較.分割圖像的性能參數(shù)選擇前文所述的期望區(qū)域熵Hr和圖像質(zhì)量指標(biāo)IQI，比較結(jié)果見表1.可以看出，對(duì)于對(duì)比度比較明顯的自然圖像，選擇同樣數(shù)量的閾值數(shù)是時(shí)，

圖1 Gray8圖像分割情況Fig.1 Gray8 image segmentation

圖2 自然圖像分割過程及結(jié)果Fig.2 Segmentative process and result of image segmentation表1 3種方法的期望區(qū)域熵和圖像質(zhì)量指標(biāo)比較Tab.1 Expected region entropy and image qualityindex for three method

HrIQI本文方法PSODE本文方法PSODE6.2586.1765.9841.1591.0731.1779.7309.6639.2741.8431.4701.7324.9114.9974.7730.4380.4570.461

本文方法的性能優(yōu)于PSO和DE算法.但是對(duì)于紋理較豐富的圖像如Baboon，本文方法稍遜于PSO和DE算法.

本文分割算法在Berkeley Segmentation Dataset測(cè)試數(shù)據(jù)上獲得了良好的分割效果.為了展示本文分割方法的性能，如圖3所示，選取其中的幾幅典型圖像35 010、126 007、241 004、113 016、385 039、368 016，實(shí)驗(yàn)選取分割閾值個(gè)數(shù)為K=6.

與各群智能算法一樣，本文方法也具有隨機(jī)性.表1和表2為幾種方法的最優(yōu)結(jié)果.分割算法對(duì)每幅圖像重復(fù)運(yùn)行50次后，分別計(jì)算目標(biāo)函數(shù)的均值和方差，結(jié)果如表2，3所示，可以看出本文的圖像分割算法具有良好的穩(wěn)定性.

表2 3種方法的圖像分割期望區(qū)域熵性能穩(wěn)定性比較Tab.2 Expected region entropy performance stabilityof image segmentation for three method

對(duì)于K=6，將本文方法的計(jì)算時(shí)間與PSO和DE方法進(jìn)行了比較，結(jié)果如表4所示.結(jié)果顯示，大部分情況下本文算法運(yùn)行時(shí)間最少.

筆者采用的多閾值化方法用到了3個(gè)參數(shù)：核半徑h、閾值T1和閾值T2.T1和T2對(duì)分割結(jié)果的影響要遠(yuǎn)小于h.一般來說，若選取較大的T1值，則Mean Shift程序只能探測(cè)出最重要的模

圖3 原始測(cè)試圖像分割的比較Fig.3 The compare of original test images and segmented images表3 3種方法的圖像分割I(lǐng)QI性能穩(wěn)定性比較Tab.3 Image quality index performance stability ofimage segmentation for three method

測(cè)試圖像本文方法PSODE均值標(biāo)準(zhǔn)差均值標(biāo)準(zhǔn)差均值標(biāo)準(zhǔn)差Lena1.1480.7651.0791.4941.1571.376Cameraman1.8700.6131.5260.4211.7721.232Baboon0.4191.4900.4411.6890.4501.660350100.5190.4710.5280.4740.5350.6091260071.2800.5981.1972.5011.2062.1032410041.1020.6081.0971.1691.1371.9421130160.7390.2360.7280.3760.6991.2843850391.3630.1601.3091.7901.4751.0183680162.0310.3761.9471.4831.9621.215

表4 3種方法的計(jì)算時(shí)間比較

態(tài)，這通常會(huì)造成欠分割；而若選取較小的T1值，則Mean Shift程序還能探測(cè)出次要的模態(tài)，這通常會(huì)造成過分割.實(shí)際上，T1選取為整個(gè)圖像大小的1%就可以得到較好的自然圖像分割結(jié)果. 而T2對(duì)分割結(jié)果影響較小，通常令T2等于核窗口的半徑,因此我們主要討論h的影響.

作為一種非參數(shù)化的密度估計(jì)方法，Mean Shift程序的估計(jì)精度會(huì)受到核半徑h的影響;通常較小的核半徑值會(huì)使程序得到太多模態(tài)；而較大的核半徑值會(huì)生成平滑的密度和較少數(shù)量的模態(tài).最常用的方法是選擇不同的核半徑，將算法運(yùn)行多次直到分割性能達(dá)到最優(yōu). Comaniciu[14]用比較復(fù)雜的方式解決了核半徑的選擇問題，實(shí)驗(yàn)顯示，當(dāng)核半徑選為(Gmax-Gmin)/10時(shí)，就可以得到較好的分割結(jié)果，分割圖像的對(duì)比度提高了許多.可以看到，隨著核半徑的增加，Hr越來越小，表明隨著圖像被劃分的區(qū)域數(shù)目的增多，各個(gè)區(qū)域內(nèi)像素特性的差異越來越??；IQI也越來越小，表明區(qū)域間像素特性的差異越來越小，盡管如此，任何一個(gè)分割結(jié)果的IQI都要比原始圖像的IQI大.因此，從圖像壓縮的角度來看，本文方法也具有一定的參考價(jià)值.

4 結(jié)論

為了解決多級(jí)閾值化圖像分割方法中閾值的數(shù)量不能預(yù)先確定這一難題，提出了一種新型的基于聚類技術(shù)的多級(jí)閾值化方法.首先使用Mean Shift技術(shù)搜索到潛在的模式中心點(diǎn)；然后應(yīng)用迭代的閾值選擇方法來確定相鄰模式中心的各個(gè)閾值；最后采用多級(jí)閾值化方法對(duì)圖像進(jìn)行分割，并通過大量實(shí)驗(yàn)得到了驗(yàn)證.此外，還應(yīng)用期望區(qū)域熵Hr和圖像質(zhì)量指標(biāo)IQI對(duì)分割結(jié)果進(jìn)行了評(píng)估，顯示了本文方法的有效性.本文方法可以通過簡(jiǎn)單地修改程序參數(shù)來控制分割的精度，并且無須預(yù)先確定直方圖中潛在的模態(tài)數(shù)量，因此，本文方法可應(yīng)用于單閾值分割、多級(jí)閾值分割和有損壓縮等技術(shù)中.

[1] TOKAS N, KARKRA S, PANDEY M K. Comparison of digital image segmentation techniques a research review [J]. International journal of computer science and mobile computing, 2016(5):215-220.

[2] DHANACHANDRA N, MANGLAM K, CHANU Y J. Image segmentation using K-means clustering algorithm and subtractive clustering algorithm[J]. Procedia comouter science, 2015,54: 764-77.

[4] OTSU N. A threshold selection method from grey-level histograms[J]. IEEE transaction on systems man amp; cyberntics,2014,9(1):62-66.

[5] RAJA N S M, SUKANYA S A, NIKITA Y.Improved PSO based multi-level thresholding for cancer infected breast thermal images using otsu[J].Procedia computer science, 2015,48:524-529.

[6] SARKAR S, DAS S,CHAUDHURI S S.Amultilevel color image thresholding scheme based on minimum cross entropy and differential evolution[J].Pattern recognition letters,2015,54:27-35.

[7] CHENG Y.Mean shift, mode seeking, and clustering[J].IEEE transactions on pattern analysis and machine intelligence,2012,17(7):790-799.

[8] RIDLER T W,CALAARD S.Picture thresholding using an iterative selection method[J].IEEE transactions on systems man amp; cybernetics,2010,8(8):630-632.

[9] HARALICK R,SHAPIRO L.Survey: image segmentation techniques[J].Computer vision, graphics and image processsing,2013(29):100-132.

[10] 余金煌，陶同贊.小子域?yàn)V波在高密度電法圖像處理中的應(yīng)用[J].水電技術(shù)，2015(1)：5-10.

[11] ZHANG H,FRITTS J E,GOLDMAN S A.A region entropy-based objective evaluation method for image segmentation[C]∥2009 IEEE Instrumentation and Measuren Technology conference. Singapore:IEEE 2014: 38-49.

[12] BISWAS S,LOVELL B C.Bezier and splines in image processing and machine vision[M].London: Sprin-ger,2009.

[13] Berkeley segmentation dataset[EB/OL]. [2017-03-01].http://www.cs.berkeley.edu/projects/vision/bsds. 2012.

[14] COMANICIU D.An algorithm for data-driven bandwidth selection[J].IEEE transactions on pattern analysis and machine intelligence,2013,25(2):281-288.

BasedontheMeanShiftClusteringMultilevelThresholdMethod

CHENG Quan1, LIU Xiaoqing1, LIU Yuchun1, WANG Zhiliang2

(1.Mechanical and Electrical Engineering，Zhoukou Normal University，Zhoukou 466001，China; 2.School of Computer amp; Communication Engineering， Beijing University of Sclence amp; Technology， Beijing 100083,China)

In order to solve the problem that the number of selected thresholds in multilevel thresholds cannot be usually predetermined, a novel multi-level thresholding method based on Mean Shift Clustering technique was proposed. Using Mean Shift technology to explore the potential mode center, the various thresholds of adjacent to the mode center was automatically determined by using of iterative threshold selection method, and then the method of multi-level threshold was used for image segmentation.The experimental results showed that, relative to the original image, contrast of the image split with Mean Shift clustering technique was greatly improved.This method could control the segmentation precision flexibly by simply modifying parameters of the program,and could be widely used in the technology of single threshold segmentation, multi-level threshold segmentation and detrimental compression and other technologies.

multilevel thresholding; image segmentation; iterative threshold selection; segmentation evaluation

2017-05-05；

2017-08-10

國(guó)家自然科學(xué)基金資助項(xiàng)目(61401526)；河南省自然科學(xué)基金資助項(xiàng)目(152300410134)

程全(1978— )，男，河南沈丘人，周口師范學(xué)院副教授，主要從事智能控制研究，E-mail:quan8888@126.com.

1671-6833(2017)06-0064-06

TP391

A

10.13705/j.issn.1671-6833.2017.06.009