基于SLIC的自適應(yīng)多主體圖像分割算法

郭 偉，李紅達，邢宇哲

(遼寧工程技術(shù)大學(xué)軟件學(xué)院,遼寧 葫蘆島 125105)

1 引言

圖像分割是按照一定的相似性準則把圖像劃分成一定數(shù)量區(qū)域的過程，圖像分割是圖像處理的前期階段，在實際的處理中有著非常廣泛的應(yīng)用，已在目標識別、模式識別、人工智能等眾多領(lǐng)域得到了普遍的應(yīng)用。

目前，圖像的尺寸越來越大，直接在像素粒度層面上對圖像進行處理的計算效率較低，這就要求減少像素數(shù)量，擴大像素所代表的含義。2003年，Berkeley大學(xué)機器視覺實驗室的Ren等人[1]第一次提出了超像素這個概念，所謂超像素，是指具有相似紋理、顏色、亮度等特征的相鄰像素構(gòu)成的子區(qū)域。超像素分割就是把像素聚類成超像素的過程。它通過像素的聚合保存了圖像的邊界信息，降低了后續(xù)圖像處理的復(fù)雜度。超像素分割算法加速了圖像處理的速度，并很好地保留了邊界信息。Moore等人[2]提出的SL(Superpixel Lattices)算法采用Canny邊界檢測算法獲得原始圖像邊界，再不斷地在垂直和水平兩個方向?qū)ふ易顑?yōu)路徑把圖像分割成超像素。Bergh等人[3]提出了SEED(Superpixels Extracted via Energy-Driven Samplin)算法，該算法不斷修正網(wǎng)格元素的超像素邊緣點，最終得到分割結(jié)果。簡單線性迭代聚類算法SLIC (Simple Linear Iterative Clustering)是在CIELAB彩色空間的X-Y坐標下的五維特征向量，把N個像素點聚類成K類。相比于其他超像素分割算法，該算法分割速度快，能形成形狀規(guī)則、大小均勻的超像素[4，5]，該算法的時間復(fù)雜度僅為O(n)，在處理高分辨率圖像時可以減少時間復(fù)雜度，而且分割的數(shù)目和邊緣貼合度是可控的。

超像素圖像分割實際上是一種圖像的過分割，沒有實際的應(yīng)用意義。在它基礎(chǔ)上的圖像處理成為了很好的研究方向，目前在圖像分割、目標檢測、特征提取、目標跟蹤、人體姿勢估計等方面都有了很好的發(fā)展。楊賽等人[6]提出一種基于超像素的顯著性目標檢測算法，先計算目標先驗概率顯著圖，在超像素區(qū)域內(nèi)建立詞袋模型，算出條件概率顯著圖，把兩種概率融合獲取顯著性目標。張雷等人[7]提出一種基于超像素的在線目標分割算法，結(jié)合上一幀的先驗知識估計當前幀的外觀模型，以超像素為節(jié)點構(gòu)建馬爾科夫模型，結(jié)合外觀模型和馬爾科夫模型構(gòu)建能量最小化問題，應(yīng)用圖割方法計算分割結(jié)果。劉大千等人[8]提出一種基于超像素的局部模型匹配目標跟蹤算法，利用前幾幀的超像素塊建立目標模型作為匹配模板，采用期望最大化EM(Expectation Maximization)估計前景信息，與局部圖像匹配確定跟蹤目標。韓守東等人[9]提出一種快速圖像分割算法，該算法用超像素作為圖模型的節(jié)點，用Graph Cut模型實現(xiàn)加速，獲得分割結(jié)果。Levinshtein等人[10]提出一種基于超像素的特征提取算法，首先用超像素構(gòu)建圖節(jié)點，利用先驗知識預(yù)測每個點的隸屬度，不斷迭代更新，確定一個封閉的輪廓逼近特征圖像。Mori[11]提出了一種基于超像素的人體姿勢估計算法，該算法用超像素作為節(jié)點，大大減少了圖像中人體關(guān)節(jié)點搜索的數(shù)目，同時應(yīng)用超像素算法使用一側(cè)的軀體來預(yù)測另一半的軀體特征，降低了算法的復(fù)雜度。

多主體圖像分割區(qū)別于傳統(tǒng)的圖像分割，傳統(tǒng)的圖像分割是分別出前景和背景，主要提取前景，忽略背景。多主體圖像分割不是簡單地分別出前景和背景，而是一副圖像本身具有多個主體，每個主體的重要性不分大小，都有實際的意義，需要把每一部分都分離出來，因此多主體圖像分割也引起到了各方面的關(guān)注。紀則軒等人[12]提出一種無監(jiān)督的模糊C均值FCM(Fuzzy C-Means)算法，結(jié)合Gabor濾波器對像素的紋理信息進行處理，有很強的適應(yīng)性，算法僅需要一次聚類，但在前期對紋理處理的過程中需要對相位、方向角、頻率同時求解，增大了算法的復(fù)雜性。余衛(wèi)宇等人[13]提出一種對圖像分塊的思想，對不同區(qū)域的圖像采用不同的閾值，結(jié)合蟻群算法對圖像進行分割，算法雖然對細節(jié)處理較好但容易出現(xiàn)過分割現(xiàn)象，且需要迭代多次。Tao等人[14]將像素信息利用Graph Cut算法轉(zhuǎn)化為圖結(jié)構(gòu)，計算其中的最小割， 對于每個像素根據(jù)其最小割邊的位置賦予對應(yīng)的標記，算法提高了邊界分割率但效率較低。伯彭波等人[15]在文獻[14]的基礎(chǔ)上提出一種交互分割的方式，首先通過超像素對圖像進行預(yù)處理，再利用Graph Cut算法構(gòu)建多層流網(wǎng)絡(luò)，最后根據(jù)用戶提供的圖形信息得出分割結(jié)果 。這種算法可以利用用戶的交互給出最符合用戶需要的解決方案，但在實際中并不允許用戶的實時交互，而且適應(yīng)性不夠。Grady[16]利用Random Walk算法計算每個像素屬于用戶標記主體的可能性，不斷更新隸屬度矩陣，是一種交互分割算法。

本文在超像素和密度聚類算法的基礎(chǔ)上提出了一種基于SLIC的自適應(yīng)DBSCAN(Density-Based Spatial Clustering of Applications with Noise)多主體圖像分割算法。在本文之前已有對SLIC和DBSCAN算法結(jié)合用于圖像分割的研究。Wu等人[17]提出了一種SLIC結(jié)合DBSCAN算法用于分割巡檢圖像的算法，胡峻峰等人[18]提出了一種SLIC結(jié)合DBSCAN算法用于分割木材表面缺陷的算法，凌朝東等人[19]提出一種SLIC結(jié)合DBSCAN算法用于解決眼底圖像硬性滲出檢測的算法。上述三種算法都是對專一圖像進行分割，每一個算法都有其自己獨立的參數(shù)，并不具有普遍適用性，對于不同的圖像并不能做到同時適用。因此，本文提出一種自適應(yīng)參數(shù)算法用于解決不同圖像之間參數(shù)不同的算法。本文使用SLIC算法和DBSCAN算法結(jié)合用于處理圖像分割問題，其中SLIC算法可以提高算法效率，而DBSCAN算法可以發(fā)現(xiàn)任意形狀的聚類，并且不需要確定聚類數(shù)目，再通過計算得到全局最優(yōu)解，最后與SLIC、Meanshift、Kmeans、分水嶺算法等傳統(tǒng)算法和SLIC-Kmeans、SLIC-Meanshift算法進行比較 ，從精度和效率兩方面對本文算法進行驗證和評價。

2 SLIC超像素圖像分割

SLIC超像素分割算法是Achanta等人提出的一種實現(xiàn)方便、思想簡單的算法，它將RGB彩色空間的像素點轉(zhuǎn)化為CIELAB彩色空間的X-Y坐標下的五維特征向量Pi=(li,ai,bi,xi,yi)i=(1,2,…,N)，將其中的N個像素點通過局部聚類形成K個超像素區(qū)域。

SLIC算法具體實現(xiàn)步驟如下：

(1)初始化聚類中心。

為了避免初始種子點落在圖像的邊緣，將初始種子點移動到當前種子點的3×3鄰域內(nèi)梯度最小的位置。圖像的梯度計算公式為:

G(x,y)=‖l(x+1,y)-l(x-1,y)‖2+

‖l(x,y+1)-l(x,y-1)‖2

其中,l(x,y)是超像素di=(xi,yi)的位置向量，‖·‖是矩陣的二范式，由此獲得初始種子點的顏色向量Ci=(li,ai,bi)，因此確定初始種子點的表達向量pi=(Ci,di)，i=1,…,K。

(2)相似度度量。

SLIC的相似度度量方法如下:

其中，dlab為像素點之間的色差，dxy為像素點之間的空間距離，D(i,k)為像素點i與聚類中心k之間的相似度，D(i,k)的值越小，說明兩者越相似，m∈1,40為調(diào)節(jié)顏色距離的權(quán)重。

(3)迭代更新聚類中心。

在聚類中心的2S×2S范圍內(nèi)確定每一個像素點的歸屬，把歸屬于一類聚類的像素點的五維向量值求平均獲得更新后的聚類中心，重復(fù)此過程直至迭代完成。

(4)對每一個歸屬于同一聚類的像素點賦予相同的聚類標簽，形成K個超像素。

對雙邊濾波之后的圖像進行SLIC超像素分割，K的取值分別為100,400,3 000時得到如圖1所示的分割圖像。

Figure 1 SLIC super-pixel segmentation images under different K values 圖1 不同的K值下SLIC超像素分割圖像

3 DBSCAN算法聚類和自適應(yīng)算法

3.1 DBSCAN算法

DBSCAN 算法是一種經(jīng)典的基于密度的聚類算法，可以自動確定聚類的數(shù)量，能夠發(fā)現(xiàn)任意形狀簇，只需要一次迭代，聚類速度比較快，DBSCAN具體算法參照文獻[20]。

DBSCAN算法有兩個重要的參數(shù)Eps和MinPts，分別為聚類中心的最大差異和聚類的最小數(shù)量。實驗表明，該算法對參數(shù)有著較強的敏感性，參數(shù)的設(shè)定嚴重影響著實驗的結(jié)果，而且對于不同的圖像需要設(shè)定不同的參數(shù)。

由圖2可以看出，對于一幅圖像來說不同的參數(shù)對圖像分割的影響很大。對于上下兩幅圖來說，同樣的Eps值，圖2b在Eps=500時可以很好地分辨出整體輪廓，而圖2e卻出現(xiàn)過分割現(xiàn)象；當Eps=2300時，圖2c出現(xiàn)欠分割現(xiàn)象，而圖2f卻能很好地分割出主體；由圖圖2e也可以發(fā)現(xiàn)整體參數(shù)對局部影響很大。因此，需要提出一種自適應(yīng)的參數(shù)算法以適應(yīng)不同圖像的要求，同時也要滿足對于同一幅圖像不同位置的要求。

3.2 自適應(yīng)算法

DBSCAN算法對Eps和MinPts有著很強的敏感性，分割不同的圖像需要采取不同的參數(shù)值，因此自適應(yīng)獲取參數(shù)值就成為了DBSCAN算法的重點。有關(guān)DBSCAN的參數(shù)選擇問題，已經(jīng)有了大量的研究，但大部分的研究都是針對數(shù)據(jù)的分類問題，圖像有其獨特的性質(zhì)，對于顏色的敏感性更高，距離只是輔助判斷。因此，圖像分割更關(guān)注像素之間的顏色差異而非距離，本文使用的DBSCAN算法只對比全局顏色信息，并不計算像素之間的距離信息，可以減少空間信息對分割效果的影響，自適應(yīng)地獲取參數(shù)可以取得良好的效果。

首先我們需要解決Eps的選取問題。本文選取文獻[21]的主要方法，通過對比全局超像素顏色信息自適應(yīng)地決定Eps值。

自適應(yīng)DBSCAN算法的主要步驟如下：

(1)計算全局距離分布矩陣DIST。

DISTn×n={dist(i,j)|1≤i≤n,1≤j≤n}

其中,n=D，D表示超像素分割后的聚類中心組成的數(shù)據(jù)集，DIST是n行n列的對稱矩陣，dist(i,j)表示第i個超像素中心到第j個超像素中心的距離。

(2)對每一個DIST排序并轉(zhuǎn)置得到順序矩陣:

KNN0n×n=sort(DISTn×n)′

KNN0n×n的每一列向量代表數(shù)據(jù)集中每個超像素到最近的k(k=1,…,n)個超像素的距離集合。由于每一列向量的第一個元素都是0，對后續(xù)處理影響很大，因此整體刪除第一行，從第二行開始算起，得到新的矩陣KNNn×(n-1):

KNNn×(n-1)=sort(KNN0n×n(1:end;2:end))

KNNn×(n-1)的第k(k=1,…,n)列即為數(shù)據(jù)集中超像素k最近鄰域集合DISTk，對于KNNn×(n-1)繪圖得到圖3，其中圖3a為全部超像素與其他超像素的距離，圖3b為單個超像素與其他超像素的距離，圖3c為圖3b曲線的概率密度圖。

Figure 3 Distance distribution of super-pixels圖3 超像素的距離函數(shù)分布

由圖3a可以看到，隨著k的增加函數(shù)上升，即DIST(n,k)≤DIST(n,k+1),從中取出單個對象的函數(shù)圖像如圖3b所示，概率密度直方圖及概率密度曲線如圖3c所示。

(3)尋找圖3c中概率密度曲線的最高點，即與超像素中心最相近的點，保證大多數(shù)的鄰接超像素可以聚集在一起，使用統(tǒng)計模型進行擬合，通過實驗發(fā)現(xiàn)使用逆高斯密度分布擬合的效果比較好，逆高斯密度分布的概率密度公式為：

其中,λ和μ可以使用極大似然估計得到。為了獲得最高點的值，解方程dP(x)/dx=0,得到一個整數(shù)解：

因此，對于每個點k，根據(jù)逆高斯概率密度函數(shù)得到：

對于不同的超像素k使用不同的Eps(k)值，可以極大地保證超像素總是向著密度最大的方向靠攏，當兩個超像素之間的差值超過Eps(k)時，擴散結(jié)束。

所有的超像素點遍歷完成后，每個聚類的聚類數(shù)目也同時被計算出來，這里并不存在最小的聚類數(shù)目，對于超像素來說，每一個超像素都有可能是孤立的聚類中心，因此MinPts的值也可以自適應(yīng)確定，并且MinPts參數(shù)對本文算法的影響較小。

遍歷完所有像素后，超像素劃分為兩類：具有實際意義的超像素聚類和被劃為噪聲點的聚類。但是，被劃為噪聲點的聚類有可能是多主體分割的一部分，卻被視為孤立點，不應(yīng)該被單獨分離出來，因此應(yīng)進行孤立點檢測，并更新聚類內(nèi)容和聚類數(shù)目。

3.3 孤立點控制

算法中超像素的自適應(yīng)Eps值會把噪聲點排除到聚類之外，或者聚類中心的超像素與鄰接超像素有較大差異，并沒有鄰接超像素一起組成聚類，單獨化為一類，這些孤立點主要有以下幾個形成原因：它們與數(shù)據(jù)的其他部分不一致；由于度量或執(zhí)行錯誤導(dǎo)致孤立點產(chǎn)生；也可能是固有數(shù)據(jù)變異性的結(jié)果。但是，這些噪聲點同樣是圖像聚類的一部分，為了解決這一問題，本文將孤立點的合并放到了超像素聚類之后，利用聚類數(shù)目判斷孤立點，并進行融合。

定義1(聚類可達密度lrd(O)) 用Cu(O)表示聚類O的所有所屬超像素，reach_distO,p表示對象p與聚類中心O的可達距離，CuO表示聚類個數(shù)，那么聚類O的可達密度為聚類中心與它的所屬超像素的平均可達距離的倒數(shù)：

定義2(局部異常因子LOF(p,O))O表示與對象p相鄰的聚類，lrdO表示不包含p對象的聚類可達密度，lrdO1表示包含p對象的聚類可達密度,Am表示所有與p相鄰的超像素集合,則:

LOF同時反映聚類內(nèi)部與鄰接超像素的異常狀況。如果p可以被歸類為聚類的一種，則對后半部分影響較大，如果是一個孤立點，則對前半部分影響較大。LOF越小，說明對象p對于聚類O的異常影響越小。聚類中心和鄰接超像素與對象p越相似，LOF越小，如果p不是孤立點，則LOF接近1，如果p的所有鄰接聚類的LOF均大于1,則p被作為孤立點處理，如果局部異常因子均小于1，則最終選取影響因子最小的聚類為它的目標聚類，如圖4。

Figure 4 Outlier control process圖4 孤立點控制過程

本文算法自適應(yīng)地確定Eps和MinPts，避免了DBSCAN的參數(shù)敏感性，增強了算法的魯棒性。自適應(yīng)選取Eps使每個超像素朝著最相似的超像素聚類，極大地減小了全局的Eps對圖像細節(jié)的影響，保證分割的結(jié)果既能分出主要的區(qū)域，還能在細節(jié)處理上優(yōu)于其他的算法。

4 實驗結(jié)果分析

實驗平臺：本文算法運行的操作系統(tǒng)為Windows 7，Intel(R) Core(TM) i5-2450M，2.5 GHz，在Matlab2012a上實現(xiàn)。

數(shù)據(jù)集：本文實驗所用的數(shù)據(jù)集為Berkeley benchmark500標準數(shù)據(jù)集[22]。每幅圖像的大小為481×321，分割的超像素個數(shù)為400個，緊密度系數(shù)m對實驗結(jié)果影響不大，算法運行時間在緊密度系數(shù)m發(fā)生變化時有輕微抖動，抖動幅度小于5%，算法運行平穩(wěn)，實驗選取邊界分割率最大的20組實驗數(shù)據(jù)取平均值，確定緊密度系數(shù)m取值為20。

圖像分割評價標準：概率隨機指數(shù)準則PRI(Probabilistic Rand Index)，取值為[0,1]，PRI越大代表結(jié)果越好。信息變化指數(shù)VOI(Variation of Information)，取值為[0,∞)，VOI越小代表分割結(jié)果越好。

本文從分割效果、分割時間以及與人工分割的結(jié)果進行比較，驗證算法的有效性。

4.1 超像素粒子度與分割結(jié)果的關(guān)系

本文算法的分割效果與分割時間嚴重依賴于超像素的個數(shù)。如果分割個數(shù)過少，則缺少邊界信息，邊界檢測率低，對圖像細節(jié)處理不理想；如果分割個數(shù)過多，不能保證后續(xù)處理的時間效率，造成浪費。超像素個數(shù)與邊界檢測率的關(guān)系和超像素個數(shù)與分割時間的關(guān)系如圖5所示。

Figure 5 Effect of the number of super-pixels on segmentation圖5 超像素個數(shù)對分割算法的影響

由圖5a所示，超像素圖像分割在超像素個數(shù)為400時可以達到99.67%的檢測率，完全可以檢測出絕大多數(shù)的圖像邊界，不存在欠分割現(xiàn)象，而當超像素個數(shù)大于400以后，邊界分割率并沒有較明顯的提升，只是在細微之處存在修改，并不影響圖像分割的整體效果；而由圖5b所示，超像素個數(shù)對超像素分割時間并沒有影響，但對于后續(xù)的圖像分割程序有著較明顯的效果，在超像素個數(shù)為1 000以下時,圖像分割算法時間并沒有大幅度的提升，當超像素個數(shù)大于1 000時便出現(xiàn)了較大幅度變化，成指數(shù)趨勢增長。綜合圖5兩幅圖，本實驗采取的超像素個數(shù)為K=400，既可以保證有很高的邊界檢測率，而且也保證了算法的時間成本沒有較大幅度增加。

圖1同時給出了不同超像素個數(shù)的不同分割結(jié)果(對于像素個數(shù)為512×512的Lena圖像分別分割為100、400、3 000的分割結(jié)果)。從圖1中可以觀察到，在超像素個數(shù)K=100時，雖然基本反映出圖像的邊界，但仍有部分邊界不能很好地分割出來，邊界分割率低，影響后續(xù)處理效果，如果增加超像素的個數(shù)為K=3000，則大幅增加了圖像分割的時間，最終確定為超像素個數(shù)為K=400，減少了后續(xù)分割的空間占用和時間花費。

4.2 分割效果

本節(jié)對SLIC、Meanshift、Kmeans、分水嶺等傳統(tǒng)算法和SLIC-Kmeans、SLIC-Meanshift算法進行分割效果比較，比較結(jié)果如圖6所示。

(1)分割結(jié)果對比。相對于傳統(tǒng)的分水嶺算法、Kmeans算法、Meanshift算法，本文算法避免了圖像的過分割現(xiàn)象，利用超像素的處理提高了分割的精度，利用DBSCAN算法在全局搜索更優(yōu)參數(shù)，進一步提升了精度。如表1所示，SLIC-Kmeans算法與傳統(tǒng)算法相比PRI提升很高，與傳統(tǒng)Kmeans算法相比,算法PRI提高28.07%，而VOI降低71.09%，說明SLIC對圖像的噪聲有很強的抑制作用，而本文算法相較于SLIC-Meanshift算法和SLIC-Kmeans算法，DBSCAN算法能發(fā)現(xiàn)更適合圖像分割的聚類，可以進一步尋找到不同形狀的聚類，發(fā)現(xiàn)更優(yōu)的分割參數(shù)。VOI指數(shù)用來計算算法分割結(jié)果與人工標注結(jié)果的差異性，VOI值越小,說明算法的分割結(jié)果越接近人工分割的結(jié)果。對比其它幾種算法，本文算法利用DBSCAN算法對超像素聚類更符合人類的分割特點。SLIC算法作為本文算法的基礎(chǔ)，會出現(xiàn)嚴重的過分割現(xiàn)象，Kmeans算法受初始點的選擇影響較大，Meanshift對簡單圖像分割結(jié)果較好，對于復(fù)雜圖像會出現(xiàn)欠分割現(xiàn)象，分水嶺算法、Meanshift算法易出現(xiàn)局部最優(yōu)的結(jié)果，造成分割不準確的現(xiàn)象。

Figure 6 Results comparison among different segmentation algorithm圖6 不同分割算法的結(jié)果對比

算法評價指標PRIVOISLIC0.198 19.725 1Kmeans0.650 11.272 3分水嶺0.574 31.240 2Meanshift0.564 71.439 6SLIC-Meanshift0.727 10.587 2SLIC-Kmeans0.832 60.367 7本文算法0.889 70.228 4

(2)分割時間對比。相較于SLIC算法，本文算法分割時間增加了后續(xù)的處理時間，但由于超像素的預(yù)處理過程使得后續(xù)處理的目標數(shù)量大大減少，因此總的分割時間并沒有明顯增加，主要的時間影響在于孤立點處理部分。

本文算法運行時間分成三部分：超像素分割階段、聚類階段和孤立點控制階段。三個階段時間相加就是算法分割時間。表2給出了圖6中三幅圖像的運行時間。從表2可以看出，對于一幅481×321的圖像，分割時間大概需要1.5 s，且不需要人工交互，增強了算法的適應(yīng)性。

Table 2 Algorithm running time

與圖6其他的幾種算法相比，分割時間如表3所示。本文算法優(yōu)于傳統(tǒng)的分水嶺算法、MeanShift算法、SLIC-Meanshift算法、SLIC-Kmeans算法，但運行時間高于SLIC算法和Kmeans算法。對比表3中的Kmeans算法、MeanShift算法、SLIC-Kmeans算法和SLIC-Meanshift算法，算法時間大大縮短，說明SLIC對加速圖像分割有很好的效果。本文算法時間優(yōu)于SLIC-Meanshift算法和SLIC-Kmeans算法的，說明DBSCAN算法無需迭代的優(yōu)越性，圖像能夠快速分割。

Table 3 Running time of different algorithms

5 結(jié)束語

本文針對多主體圖像分割的交互問題提出了一種基于SLIC超像素的DBSCAN自適應(yīng)圖像分割算法。算法使用SLIC超像素分割算法把圖像分割為超像素點 ，再通過自適應(yīng)的DBSCAN算法進行聚類操作，得到多主體分割結(jié)果。相對于已有方法，本文算法可以自適應(yīng)地獲取多主體的分割數(shù)目，不需要人工交互，減少了用戶的操作流程，增加了算法的適應(yīng)性，在各種評價指標上也有很好的效果。

實驗顯示了相對于其他算法的分割效果和分割效率，本文算法可以快速得到多主體圖像分割結(jié)果。在未來的工作中將研究先確定聚類數(shù)目，給每一個種子點增加一個隸屬度矩陣，再確定分割邊界的方法。