一種新的基于超像素聚類(lèi)的圖像分割算法x

姜全春 王寧 李雷

摘 ?要： 本文提出了一種使用具有噪聲的基于密度的聚類(lèi)方法進(jìn)行超像素聚類(lèi)來(lái)提高圖像分割準(zhǔn)確性的方法，首先以較低計(jì)算成本得到超像素分割，然后我們?cè)倮妹芏染垲?lèi)的原理將相關(guān)聯(lián)的超像素聚集到一起，利用超像素對(duì)圖像邊緣信息的準(zhǔn)確分割，來(lái)提高圖像分割的準(zhǔn)確性。我們?cè)跇?gòu)建圖形時(shí)使用局部鄰域?qū)⑺惴☉?yīng)用于分割中，并利用DBSCAN既可以適用于凸樣本集，也可以適用于非凸樣本集的特性對(duì)超像素進(jìn)行聚類(lèi)分析。將所有各組緊密相連的樣本劃為各個(gè)不同的類(lèi)別，則我們就得到了最終的所有聚類(lèi)類(lèi)別結(jié)果。該方法的一個(gè)重要特征是其能夠在像素點(diǎn)密度大過(guò)某個(gè)閾值時(shí)，保留圖像區(qū)域中的細(xì)節(jié)。

關(guān)鍵詞： 密度聚類(lèi);圖像分割;超像素分割;局部鄰域

中圖分類(lèi)號(hào)： TP751 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.06.010

本文著錄格式：姜全春，王寧，李雷，等. 一種新的基于超像素聚類(lèi)的圖像分割算法[J]. 軟件，2019，40（6）：4448

【Abstract】： This paper proposes a method of using super-pixel clustering based on the density-based clustering method to improve the accuracy of image segmentation. Firstly， the super-pixel segmentation is obtained at a lower computational cost， and then we use the principle of density clustering. The associated superpixels are gathered together. and uses superpixels to accurately segment the edge information of the image to improve the accuracy of image segmentation. We use the local neighborhood to apply the algorithm to the segmentation when constructing the graph， and use DBSCAN to apply to both the convex sample set and the non-convex sample set to cluster the superpixel. By grouping all the closely connected samples into different categories， we get the final results for all cluster categories. An important feature of this method is its ability to preserve details in the image area when the pixel density is greater than a certain threshold.

【Key words】： Density clustering; Image segmentation; Superpixel segmentation; Local neighborhood

0 ?引言

在計(jì)算機(jī)視覺(jué)[1]上，圖像分割的問(wèn)題仍然是一個(gè)巨大的挑戰(zhàn)。自從人工智能的顯著發(fā)展，每時(shí)每刻都在產(chǎn)生海量圖像。圖像分割[2]在人類(lèi)視覺(jué)感知中其重要作用，因?yàn)閳D像的類(lèi)型和大小超出了傳統(tǒng)的處理能力范圍，聚類(lèi)作為一種常見(jiàn)的無(wú)監(jiān)督學(xué)習(xí)，得到了廣泛的應(yīng)用。聚類(lèi)的原理就是將不同的數(shù)據(jù)點(diǎn)根據(jù)它們的差異程度分割成不同的簇，而且每個(gè)簇中的數(shù)據(jù)都具有相似的特征。聚類(lèi)算法[3]很多，包括基于劃分的聚類(lèi)算法（如：k-means），基于層次的聚類(lèi)算法（如：BIRCH），基于密度的聚類(lèi)算法（如：DBSCAN），基于網(wǎng)格的聚類(lèi)算法（如：STING）等等。鄭金志等人[4]提出了基于優(yōu)化初始聚類(lèi)中心的改進(jìn)WFCM圖像分割算法，針對(duì)的是模糊C均值聚類(lèi)算法的改進(jìn)問(wèn)題。

本文選擇DBSCAN[5]作為我們的聚類(lèi)算法，我們提出了一種基于超像素聚類(lèi)的圖像分割算法（SCIS）。超像素作為一種重要的處理技術(shù)已成功應(yīng)用于許多視覺(jué)應(yīng)用中，如圖像分割和對(duì)象識(shí)別等。Felzenszwalb等人[6]采用了一種基于圖形的圖像分割，用于捕獲感知上重要的區(qū)域，來(lái)達(dá)到一種高效的圖像分割。Achanta等人[7，8]引入了一種簡(jiǎn)單線性迭代聚類(lèi)方法，該方法產(chǎn)生具有較低計(jì)算復(fù)雜度的超像素，而且它們比較了SLIC與其他的流行方法[7]。在本文中，我們采用的是SLIC算法進(jìn)行初始的超像素分割，之后根據(jù)DBSCAN原理將超像素進(jìn)行聚類(lèi)并應(yīng)用于圖像分割上，該算法既利用超像素保留了圖像的細(xì)節(jié)特征，又基于密度融合原理提高了分割的精度。最后采用的伯克利BSDS300數(shù)據(jù)集進(jìn)行驗(yàn)證。

1 ?SLIC算法和密度聚類(lèi)理論

1.1 ?SLIC算法

Achanta等人提出的采用K均值算法生成超像素的簡(jiǎn)單線性迭代聚類(lèi)（SLIC）方法。該算法通過(guò)將搜索空間限制為與超像素大小成比例的區(qū)域，顯著地減少了優(yōu)化中的距離計(jì)算的數(shù)量，并通過(guò)加權(quán)距離度量組合顏色和空間接近度，同時(shí)提供對(duì)超像素的尺寸和緊湊性的控制。

SLIC算法的本質(zhì)是將基于劃分的聚類(lèi)算法用到超像素的聚類(lèi)中，例如上面提到的K-means方法。

1.2 ?密度聚類(lèi)方法

DBSCAN是基于一組鄰域來(lái)描述樣本集的緊密程度的，參數(shù) 用來(lái)描述鄰域的樣本分布緊密程度。其中， 描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為 的鄰域中樣本個(gè)數(shù)的閾值。

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

從實(shí)驗(yàn)結(jié)果和表1可以得出，SCIS算法所使用的超像素聚合方法與其他兩種方法都比較相近，所以我們的算法有很高的可行性;我們定量的評(píng)估算法的性能[14]在查準(zhǔn)率（Precision）、概率邊緣指標(biāo)（PRI）和信息變化（VoI）等平均值都有效的提升，而且得到了更好的分割結(jié)果。

4 ?結(jié)論

本文借鑒了經(jīng)典的DBSCAN算法和SLIC方法，提出了一種基于超像素聚合的圖像分割方法（SCIS）。該算法既融合了SLIC算法對(duì)圖像的邊緣特征的提取，又體現(xiàn)了聚類(lèi)算法對(duì)圖像整體的把握。我們首先將圖像分割成許多精確的小區(qū)域，然后根據(jù)合并函數(shù)將他們逐漸聚集成所需要的超像素塊（區(qū)域）。本研究所采用的DBSCAN聚類(lèi)算法彌補(bǔ)層次聚類(lèi)算法和劃分式聚類(lèi)算法往往只能發(fā)現(xiàn)凸型的聚類(lèi)簇的缺陷，還可以相對(duì)抗噪音圖像，能處理任意形狀和大小的圖像簇。從實(shí)驗(yàn)結(jié)果可以看出，SCIS是一提高圖像分割的有效方法。算法精度提高了22%。

參考文獻(xiàn)

[1] Bay H， Ess A， Tuytelaars T， et al. Speeded-Up Robust Features （SURF）[J]. Computer Vision and Image Unders-tanding， 2008， 110（3）： 346-359.

[2] 丁亮， 張永平， 張雪英. 圖像分割方法及性能評(píng)價(jià)綜述[J]. 軟件， 2010， 12： 78-83.

[3] 孫吉貴， 劉杰， 趙連宇. 聚類(lèi)算法研究[J]. 軟件學(xué)報(bào)， 2008， 19（1）： 48-61.

[4] 鄭金志， 鄭金敏， 汪玉琳. 基于優(yōu)化初始聚類(lèi)中心的改進(jìn)WFCM圖像分割算法[J]. 軟件， 2015， 04： 136-142.

[5] Mihael Ankerst， Markus M. Breunig， Hans-Peter Kriegel， and J?rg Sander. 1999. OPTICS： ordering points to identify the clustering structure[J]. In Proceedings of the 1999 ACM SIGMOD international conference on Management of data （SIGMOD '99）， 1999， 28（2）： 49-60.

[6] Felzenszwalb P F， Huttenlocher D P. Efficient Graph-Based Image Segmentation[J]. International Journal of Computer Vision， 2004， 59（2）： 167-181.

[7] Achanta R， Shaji A， Smith K， Lucchi A， Fua P， Süsstrunk S. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（11）： 2274-2282.

[8] Liu M Y， Tuzel O， Ramalingam S， Chellappa R. Entropy-rate clustering： cluster analysis via maximizing a submodular function subject to a matroid constraint[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2014， 36（1）： 99-112.

[9] Zhu Song， Cao Danhua， Wu Yubin， Jiang Shixiong. Improved accuracy of superpixel segmentation by region merging method[J]. Frontiers of Optoelectronics， 2016， 9（4）： 633-639.

[10] Wu Z， Leahy R M. An Optimal Graph Theoretic Approach to Data Clustering： Theory and Its Application to Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1993， 15（11）： 1101-1113.

[11] Perona P， Freeman W. A factorization approach to grouping [C]. European Conference on Computer Vision. Springer， Berlin， Heidelberg， 1998.

[12] Liu F， Gleicher M. Region Enhanced Scale-Invariant Saliency Detection[C]. Proceedings of the 2006 IEEE International Conference on Multimedia and Expo， ICME 2006， July 9-12 2006， Toronto， Ontario， Canada. IEEE， 2006.

[13] 賈耕云， 趙海英， 劉菲朵. 基于超像素的Graph-Based圖像分割算法[J]. 北京郵電大學(xué)學(xué)報(bào)， 2018， 41（3）： 46-50.

[14] Vendramin， L.， Campello， R. J.， Hruschka， E. R. Relative clustering validity criteria： a comparative overview. Stat. Anal. Data Min， 2010， 3（4）： 209-235.