一種新的基于超像素聚類的圖像分割算法x

姜全春 王寧 李雷

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

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

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

本文著錄格式：姜全春，王寧，李雷，等. 一種新的基于超像素聚類的圖像分割算法[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 ?引言

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

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

1 ?SLIC算法和密度聚類理論

1.1 ?SLIC算法

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

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

1.2 ?密度聚類方法

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

3 ?實驗結(jié)果分析

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

4 ?結(jié)論

本文借鑒了經(jīng)典的DBSCAN算法和SLIC方法，提出了一種基于超像素聚合的圖像分割方法（SCIS）。該算法既融合了SLIC算法對圖像的邊緣特征的提取，又體現(xiàn)了聚類算法對圖像整體的把握。我們首先將圖像分割成許多精確的小區(qū)域，然后根據(jù)合并函數(shù)將他們逐漸聚集成所需要的超像素塊（區(qū)域）。本研究所采用的DBSCAN聚類算法彌補層次聚類算法和劃分式聚類算法往往只能發(fā)現(xià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] 丁亮， 張永平， 張雪英. 圖像分割方法及性能評價綜述[J]. 軟件， 2010， 12： 78-83.

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

[4] 鄭金志， 鄭金敏， 汪玉琳. 基于優(yōu)化初始聚類中心的改進(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é)報， 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.