韓劍輝　唐俊超

摘 要：超像素分割是計(jì)算機(jī)圖像處理的一個(gè)重要的預(yù)處理步驟，傳統(tǒng)的基于密度聚類的超像素分割算法對于邊界的處理比較好，但是所獲得的超像素形狀不規(guī)則，針對其缺點(diǎn)，提出了一種空間約束的DBSCAN聚類的超像素分割算法。首先在圖像上均勻的播撒種子點(diǎn)，之后以種子點(diǎn)為中心利用空間約束的密度聚類逐步向外擴(kuò)張，直至遍布整張圖像，獲得初始的超像素，通過k-means方法迭代進(jìn)行更新種子點(diǎn)，最后遍歷種子點(diǎn)來清理掉未訪問過的像素點(diǎn)。為了驗(yàn)證方法的有效性，在BSDS500數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并與當(dāng)前最先進(jìn)的方法進(jìn)行了定性和定量的對比。在超像素?cái)?shù)目為300左右時(shí)，該方法的緊密度為0.45，明顯優(yōu)于傳統(tǒng)的基于密度聚類的超像素分割算法的0.40?？臻g約束密度聚類的超像素分割算法在通過均勻分布的種子點(diǎn)以及空間約束后使得緊密度得到了明顯的提高。

關(guān)鍵詞：圖像分割;超像素;密度聚類;k-means;空間約束

DOI：10.15938/j.jhust.2020.06.019

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2020）06-0131-06

Superpixel Segmentation Algorithm by

Spatial Constrained Density Clustering

HAN Jian-hui， TANG Jun-chao

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract：The superpixel segmentation is an important pre-processing step in computer image processing. The traditional superpixel segmentation algorithm based on density clustering is better for boundary processing， but the resulting superpixel shape is irregular. In view of its disadvantages， a new algorithm of superpixel segmentation combining k-means and DBSCAN clustering with spatial constraints is proposed. We first spread the seed point evenly on the image， and then gradually expand the density cluster centered on the seed point using spatial constraints until the entire image is spread， the initial superpixels are obtained， and the seed point is updated iteratively through the k-means method. Finally we traverse the seed point to clean up unaccessed pixels. In order to verify the effectiveness of the algorithm ， experiments were conducted in the BSDS500 dataset and qualitative and quantitative comparisons were made with the most advanced algorithms . When the number of superpixels is about 300， the compact density of this method is 0.45， which is significantly better than the 0.40 of the traditional superpixel segmentation algorithm based on density clustering.In this paper， the algorithm of superpixel segmentation is presented to increase the compact density by the uniform distribution of seed points and spatial constraints.

Keywords：image segmentation;superpixel;density clustering;k-means;spatial constraint

0 引 言

超像素[1]是2003年由Xiaofeng Ren提出并發(fā)展起來的一種圖像分割技術(shù)，指由具有亮度、紋理、顏色和其他類似圖像特征的像素組成的不規(guī)則像素塊[2-3]。傳統(tǒng)的圖像處理多數(shù)以像素為基本單位，而超像素則以區(qū)域?yàn)榛締挝?，很大程度上減少了后續(xù)圖像處理的復(fù)雜度，被應(yīng)用于對象追蹤[4]、物體分割[5]、人臉檢測[6]等諸多方面。

目前的超像素分割算法分為兩種類型，其中一種基于梯度的變化，包括簡單的線性迭代聚類（simple linear itrative clustering，SLIC）[7]，分水嶺（watersheds，WS）[8]，空間約束的分水嶺（watersheds superpixel，SCOW）[9]，均值漂移（mean shift，MS）[10]，TurboPixels[11]等。另一種則是基于圖論的，包括懶惰隨機(jī)游走（lazy random walk，LRW）[12]，TPS[13]，超像素格子（superpixel lattice，SL）[14]，熵率超像素（entropy rate superpixel，ERS）[15]，歸一化割（normalized cut，NC）[16]，Graph-based[17]等。

基于梯度的超像素大多數(shù)從像素的初始聚類開始，通過梯度變化的方法迭代更新聚類，直到滿足某些標(biāo)準(zhǔn)形成超像素。SLIC[7]是基于k-means聚類的超像素分割算法，特點(diǎn)是可以控制超像素塊的數(shù)目與緊密度，缺點(diǎn)是它只考慮了像素點(diǎn)與種子點(diǎn)之間顏色和坐標(biāo)之間的關(guān)系，沒有考慮到像素點(diǎn)與邊界之間的關(guān)系，對于圖像邊界的貼合度不是很好。SCOW[9]是基于空間約束的分水嶺方法，特點(diǎn)是超像素的形狀較為規(guī)范，算法的速度快，缺點(diǎn)是無法控制超像素的數(shù)目。TurboPixels[11]的算法將空間約束引入到水平集演化中，用來獲得緊湊的超像素，缺點(diǎn)是所獲得的超像素與圖像的邊界重合較差。

基于圖論的超像素是將圖像描述為一張帶有權(quán)值的無向圖，圖像中每一個(gè)像素點(diǎn)對應(yīng)于圖中的一個(gè)節(jié)點(diǎn)，像素點(diǎn)之間的相鄰關(guān)系對應(yīng)于圖的邊，通過使用不同的分割方法來對圖中的節(jié)點(diǎn)進(jìn)行劃分，這樣完成對圖像的分割。TPS[13]是保留了拓?fù)浼耙?guī)律的方法，優(yōu)點(diǎn)是超像素的形狀較為規(guī)范，缺點(diǎn)是需要預(yù)先提取圖像的邊界，浪費(fèi)很多的時(shí)間并且圖像邊界的重合不好。LRW[12]在隨機(jī)游走算法的基礎(chǔ)之上加入了自跳過程，對于圖像的紋理捕捉較好，缺點(diǎn)是算法速度慢。ERS[15]將超像素分割問題制定為目標(biāo)函數(shù)，包括在圖上游走的熵率以及平衡項(xiàng)，缺點(diǎn)是所獲得的超像素形狀不規(guī)則。

基于k-means聚類的超像素分割算法原理簡單，缺點(diǎn)是沒有考慮圖像的邊界信息，圖像邊界重合較差;基于密度聚類[18]的超像素分割算法DBSCAN[19]，由于DBSCAN聚類算法可以找到任意形狀的簇，因此它具有很好的分割復(fù)雜和不規(guī)則形狀對象的潛力，但沒有考慮像素點(diǎn)與種子點(diǎn)間的空間關(guān)系，導(dǎo)致超像素形狀不規(guī)則。

本文的主要貢獻(xiàn)如下：

1）提出了一種基于空間約束的DBSCAN與k-means的混合聚類超像素算法，該算法的聚類過程在DBSCAN算法上加入了空間約束，使得超像素的形狀更加規(guī)則。

2）在該算法中，將圖像分成了K個(gè)區(qū)域，使得超像素的數(shù)目得到了控制。

3）在該算法中，使用k-means算法進(jìn)行種子點(diǎn)更新，解決了噪聲對于DBSCAN算法的影響。

4）在該算法中，清理小區(qū)域階段，將未訪問過的像素點(diǎn)與種子點(diǎn)進(jìn)行計(jì)算，有效地提升了分割效果。

5）在測試算法時(shí)，使用了BSDS500數(shù)據(jù)集進(jìn)行測試，結(jié)果表明，本文算法SCDC的緊密度系數(shù)明顯優(yōu)于DBSCAN。

1 聚類階段

本文的算法需要將要處理的圖像轉(zhuǎn)換到LAB顏色空間，LAB顏色空間中的L分量用于表示像素的亮度從黑到白，取值為[0， 100];A表示從綠色到紅色的范圍，取值為[-128，127];B表示從黃色到藍(lán)色的范圍，取值為[-128，127]。相較于RGB顏色空間，LAB空間表示的顏色范圍更廣，因此本文選用LAB顏色空間進(jìn)行計(jì)算。

將人工設(shè)定的K個(gè)種子點(diǎn)均勻的分布于整張圖象之上，K的取值范圍為[0， N]，其中N為圖像中像素點(diǎn)的數(shù)目，相鄰種子點(diǎn)的間距近似為s=N/K，K為人為設(shè)定的超像素塊的數(shù)目。為了讓算法盡快的收斂，將由種子點(diǎn)出發(fā)對于像素點(diǎn)的搜索范圍限制在2s×2s的范圍內(nèi)。

在聚類階段，有4個(gè)集合，即已訪問集合V和未訪問集合NV，種子點(diǎn)集合以及標(biāo)記集合。其中種子點(diǎn)集合存入的是所有種子的[l， a， b， r， c]信息，標(biāo)記集合在每一次種子點(diǎn)更換時(shí)都會(huì)被重置，V∩NV=，V∪NV=Ps，Ps為全體像素。先將種子置為已訪問狀態(tài)，之后將其存入標(biāo)記集合，這樣就在以該種子為中心的區(qū)域內(nèi)得到了4種點(diǎn)，即已訪問點(diǎn)，未訪問點(diǎn)，種子點(diǎn)以及標(biāo)記點(diǎn)。按順序找到標(biāo)記點(diǎn)在未訪問集合NV中相鄰的4個(gè)像素，首先將它們置為已訪問狀態(tài)，之后計(jì)算它們與種子點(diǎn)該標(biāo)記點(diǎn)的組合距離，如果小于閾值的話就將其存入標(biāo)記集合。終止條件為標(biāo)記集合不再存入像素點(diǎn)。如此反復(fù)，直到遍歷完畢所有種子點(diǎn)。

dist1=（Lp-LC）2+（AP-AC）2+（BP-BC）2（1）

dist2=（LP-LS）2+（AP-AS）2+（BP-BS）2（2）

dS=（rp-rS）2+（cp-cS）2（3）

D=dist1+γdist2·exp（-αdS）（4）

在式（1）中，LP，AP，BP代表像素點(diǎn)P的顏色特征;LC，AC，BC代表的是標(biāo)記點(diǎn)C的顏色特征。在式（2）中，LS，AS，BS代表的是種子點(diǎn)S的顏色特征。在式（3）中，rp，cp代表的是像素點(diǎn)P的空間特征;rS，cS代表的是種子點(diǎn)S的空間特征。在式（4）中，α為空間參數(shù)，用于調(diào)節(jié)空間約束的強(qiáng)度;γ為種子約束參數(shù)，用于調(diào)節(jié)像素點(diǎn)P所受種子點(diǎn)約束的強(qiáng)度。dist1是像素點(diǎn)P與標(biāo)記點(diǎn)C的色彩距離，dist2是像素點(diǎn)P與種子點(diǎn)S的色彩距離，dS是像素點(diǎn)P與種子點(diǎn)S的空間上的距離，D是在加入了空間約束后像素點(diǎn)P到標(biāo)記點(diǎn)與到種子點(diǎn)的組合距離。

通過式（4）可以看出，空間約束使像素點(diǎn)P所受種子點(diǎn)的約束隨著與種子點(diǎn)之間的距離而發(fā)生變化，距離種子點(diǎn)越遠(yuǎn)，它所受到種子點(diǎn)的約束就越小，解決了邊界附近沒有空間約束導(dǎo)致的超像素形狀不規(guī)則問題，這樣就可以在傳統(tǒng)密度聚類分割的超像素的基礎(chǔ)之上得到形狀更加規(guī)則的超像素。

Cseed=∑pi∈CseedpiCseed（5）

在上述步驟進(jìn)行完畢之后，通過k-means算法來更新種子點(diǎn)，如式（5）所示，其中pi為屬于Cseed的像素，|Cseed|為屬于Cseed的像素?cái)?shù)目，在公式左側(cè)的Cseed為新的種子點(diǎn)。在更新完種子點(diǎn)后，對前面聚類及更新種子點(diǎn)的步驟進(jìn)行迭代來改善DBSCAN對于初始種子點(diǎn)的選擇過于敏感的缺點(diǎn)。

2 清理小區(qū)域階段

在清理小區(qū)域階段，由于本文算法是以種子點(diǎn)為中心向4鄰域進(jìn)行生長的，所以會(huì)出現(xiàn)“空洞”。采用如下的公式依次遍歷未訪問到的像素點(diǎn)與所有種子點(diǎn)之間的組合距離，通過對比得到其中最小距離，則該像素點(diǎn)屬于這個(gè)距離所對應(yīng)的種子點(diǎn)。

d1=（rp-ri）2+（cp-ci）2（6）

d2=（LP-Li）2+（AP-Ai）2+（BP-Bi）2（7）

d=d12+d22β（8）

式中：rp，cp為像素點(diǎn)P的空間特征;ri，ci為種子點(diǎn)i的空間特征。LP，AP，BP為像素點(diǎn)P的顏色特征;Li，Ai，Bi為種子點(diǎn)i的顏色特征。d1為像素點(diǎn)P到種子點(diǎn)i的色彩上的距離;d2為像素點(diǎn)P到種子點(diǎn)i的空間上的距離;β為參數(shù)，調(diào)節(jié)顏色距離所占的權(quán)重。

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

在本節(jié)中，首先對SCDC中的參數(shù)進(jìn)行了分析，然后將SCDC與最先進(jìn)的算法進(jìn)行比較，包括SLIC[7]，DBSCAN[19]，TPS[13]，他們的實(shí)驗(yàn)結(jié)果通過運(yùn)行原作者提供的公開代碼以及其所設(shè)置的默認(rèn)參數(shù)獲得。所有實(shí)驗(yàn)均在BSDS500數(shù)據(jù)集[20]上進(jìn)行。

3.1 參數(shù)分析

在本節(jié)中，我們評估空間約束強(qiáng)度對于實(shí)驗(yàn)結(jié)果的影響。α控制著空間約束強(qiáng)度的大小，將α分別設(shè)置為0，0.1，1進(jìn)行實(shí)驗(yàn)。

如圖3所示，當(dāng)α=0時(shí)，即空間約束強(qiáng)度為0的時(shí)候，圖3（a）中局部放大圖在十字架底部顯得雜亂無章;當(dāng)α=0.1的時(shí)候，圖3（b）中十字架被清晰的分割了出來;當(dāng)α=1時(shí)，空間約束過于強(qiáng)大，圖3（c）中十字架沒有被分割出來。在后面的實(shí)驗(yàn)中，為了平衡超像素規(guī)則的形狀和對于圖像邊界的貼合，我們?nèi)ˇ?0.5×10-6。

3.2 與其他先進(jìn)的超像素算法進(jìn)行比較

我們將參數(shù)設(shè)置為E=49，α=0.5×10-6，γ=1.450，β=2.5，與SLIC[7]，DBSCAN[19]，TPS[13]這3種目前最先進(jìn)的超像素分割算法算法進(jìn)行比較。

3.2.1 視覺比較

圖4給出了由SLIC，TPS，DBSCAN和本文算法分割的超像素的視覺結(jié)果。從圖中可以看出，本文算法對于圖像邊界的重合程度明顯強(qiáng)于TPS算法;本文算法所生成的超像素明顯比DBSCAN更加規(guī)則。傳統(tǒng)的基于DBSCAN的超像素生成算法只考慮到了像素點(diǎn)之間的顏色關(guān)系，它的像素點(diǎn)到種子點(diǎn)的權(quán)值是固定不變的，所以其超像素的形狀不規(guī)范。TPS過于注重形狀上的規(guī)則，導(dǎo)致其對于圖像邊界的重合較差。本文算法在DBSCAN對于邊界重合的基礎(chǔ)之上有效控制了超像素塊的形狀。

如圖5所示，雖然這些算法都能產(chǎn)生緊湊且均勻的超像素，但是這些超像素算法（如DBSCAN和TPS）難以實(shí)現(xiàn)兼顧圖像邊界和規(guī)則性的良好性能。本文算法中考慮了空間約束，因此在保持較高邊界重合的同時(shí)形狀更規(guī)則。在放大的區(qū)域處清楚地表明，本文算法比SLIC，DBSCAN及TPS的綜合表現(xiàn)更好。

3.2.2 定量比較

在超像素分割中采用4種常用的標(biāo)準(zhǔn)來對這幾種算法進(jìn)行評估，分別是邊界召回率（boundary recall，BR）[21]，欠分割錯(cuò)誤率（undersegmrntation error，UE）[22-23]，緊密度（compactness，CO）[24]和可達(dá)分割精度（achievable segmentation accuracy，ASA）[15]。

邊界召回率BR[21]是用來衡量超像素算法所產(chǎn)生的超像素對于圖像邊界真值重合性能的重要指標(biāo)，較高的邊界召回率代表了對圖像ground truth更好的重合，即越高越好。由圖6（b）可以得出我們的超像素方法的邊界召回率明顯高于TPS算法。

欠分割錯(cuò)誤率UE[22-23]用來衡量從圖像ground truth“泄漏”的像素百分比，一個(gè)好的超像素算法應(yīng)該盡可能減少分割結(jié)果中的欠分割區(qū)域。換句話說，我們需要保護(hù)超像素僅與一個(gè)圖像真值區(qū)域重合，即UE越低越好。由圖6（d）可以看出本文算法的欠分割錯(cuò)誤率略高于其他3種方法。

緊密度CO[24]表示了超像素塊的規(guī)則程度，越高越好。由圖6（c）可以看出在加入了空間約束后，本文算法的緊密度明顯高于DBSCAN，這說明超像素的邊界得到了控制，本文的超像素分割較DBSCAN更規(guī)則。

可達(dá)分割精度ASA[15]用來衡量計(jì)算超像素塊作為圖像的基本單位時(shí)，與圖像ground truth的最大重合程度，即越高越好。由圖6（a）可以看出，本文算法的ASA與DBSCAN及TPS差距很小。

4 結(jié) 論

針對DBSCAN超像素分割算法所獲得的超像素塊形狀不規(guī)則的缺點(diǎn)提出了一種基于空間約束DBSCAN新型超像素生成算法。我們使用伯克利分割數(shù)據(jù)庫BSDS500對4個(gè)常用指標(biāo)進(jìn)行了評估，本文算法對于不同復(fù)雜程度的圖像均能獲得比較好的分割效果。在未來，我們將繼續(xù)在基于密度聚類的基礎(chǔ)上開發(fā)出更加高效超像素分割算法。

參考文獻(xiàn)：

[1] REN X ， MALIK J . Learning a Classification Model for Segmentation[J]. Iccv， 2003（1）：10.

[2] STUTZ D ， HERMANS A ， LEIBE B . Superpixels： An Evaluation of the State-of-the-Art[J]. Computer Vision and Image Understanding， 2017：S1077314217300589.

[3] WANG M ， LIU X ， GAO Y ， et al. Superpixel Segmentation： A Benchmark[J]. Signal Processing： Image Communication， 2017， 56：28.

[4] YANG F， LU H， YANG M H. Robust Superpixel Tracking[J]. IEEE Transactions on Image Processing， 2014， 23（4）：1639.

[5] LU L . A Nonparametric Treatment for Location/Segmentation Based Visual Tracking[C]// IEEE Conference on Computer Vision & Pattern Recognition. IEEE， 2007.

[6] 林克正， 魏穎， 程衛(wèi)月. 壓縮感知的人臉圖像去噪[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2015（5）：91.

LIN Kezheng， WEI Ying， CHENG Weiyue. Face Image Denoising of Compressed Sensing[J]. Journal of Harbin University of Science and Technology， 2015（5）：91.

[7] ACHANTA R ， SHAJI A ， SMITH K ， et al. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（11）：2274.

[8] VINCENT L ， SOILLE P . Watersheds in Digital Spaces： an Efficient Algorithm Based on Immersion Simulations[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1991， 13（6）：583.

[9] HU Z ， ZOU Q ， LI Q . Watershed Superpixel[C]// IEEE International Conference on Image Processinging （ICIP）. IEEE， 2015：349.

[10]COMANICIU D， MEER P. Mean Shift： A Robust Approach Toward Feature Space Analysis[J]. IEEE Trans Pattern Analysis & Machine Intelligence， 2002， 24（5）：603.

[11]LEVINSHTEIN A ， STERE A ， KUTULAKOS K N ， et al. TurboPixels： Fast Superpixels Using Geometric Flows[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（12）：2290.

[12]SHEN J ， DU Y ， WANG W ， et al. Lazy Random Walks for Superpixel Segmentation[J]. IEEE Transactions on Image Processing， 2014， 23（4）：1451.

[13]DAI T， FU H， CAO X. Topology Preserved Regular Superpixel[C]// IEEE International Conference on Multimedia & Expo.， 2012：765.

[14]MOORE A P ， PRINCE S J D ， WARRELL J ， et al. Superpixel lattices[C]// 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR 2008）， Anchorage， Alaska， USA. June 24-26， 2008：1.

[15]LIU M Y， TUZEL O， RAMALINGAM S， et al. Entropy Rate Superpixel Segmentation[C]// Computer Vision & Pattern Recognition， 2011：2097.

[16]SHI J ， MALIK J . Normalized Cuts and Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）：888.

[17]FELZENSZWALB P F ， HUTTENLOCHER D P . Efficient Graph-Based Image Segmentation[J]. International Journal of Computer Vision， 2004， 59（2）：167.

[18]ESTER M. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//Proc.Int.Conf.Knowledg Discovery & Data Mining， 1996： 226.

[19]SHEN J， HAO X， LIANG Z， et al. Real-time Superpixel Segmentation by DBSCAN Clustering Algorithm[J]. IEEE Transactions on Image Processing， 2016， 25（12）： 5933.

[20]ARBELAEZ P ， MAIRE M ， FOWLKES C ， et al. Contour Detection and Hierarchical Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（5）：898.

[21]MARTIN D R ， FOWLKES C C ， MALIK J . Learning to Detect Natural Image Boundaries Using Local Brightness， Color， and Texture Cues[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2004， 26（5）：530.

[22]NEUBERT P ， PROTZEL P . Compact Watershed and Preemptive SLIC： On Improving Trade-offs of Superpixel Segmentation Algorithms[C]// 2014 22nd International Conference on Pattern Recognition （ICPR）. IEEE Computer Society， 2014：996.

[23]BERGH M V D ， BOIX X ， ROIG G ， et al. SEEDS： Superpixels Extracted via Energy-Driven Sampling[C]// European Conference on Computer Vision. Springer， Berlin， Heidelberg， 2012：13.

[24]RAND W M. Objective Criteria for the Evaluation of Clustering Methods[J]. Journal of the American Statistical Association， 1971， 66（336）： 846.

（編輯：溫澤宇）

收稿日期： 2019-05-23

基金項(xiàng)目： 國家自然科學(xué)基金（61502124）.

作者簡介：

韓劍輝（1962—），男，教授，碩士研究生導(dǎo)師.

通信作者：

唐俊超（1994—），男，碩士研究生，E-mail：2609307954@qq.com.