基于SLIC超像素分割的圖分割算法?

趙 淵, 彭濟(jì)根, 高 義

(1-西安交通大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，西安 710049;2-北方民族大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，銀川 750021)

1 引言

圖像分割是圖像處理應(yīng)用中的基本步驟，其目的是為了將圖像中人們所感興趣的部分提取出來，為后續(xù)處理分析提供基礎(chǔ)[1]．圖像分割可應(yīng)用到醫(yī)學(xué)影像人臉識別、指紋識別和機(jī)器視覺等領(lǐng)域．目前國內(nèi)外常用的圖像分割算法有閾值分割法[2]、邊緣分割法[3]、區(qū)域分割法[4]、基于人工神經(jīng)網(wǎng)絡(luò)的分割算法[5]等．這些算法可以總結(jié)為兩類，第一類是基于局部信息的分割算法，第二類是基于全局信息的分割算法．

圖分割算法是一類常用的基于全局信息的分割算法，該類算法把圖像看成一個圖，然后通過對圖中節(jié)點(diǎn)的劃分得到圖像的分割[6]．在圖分割算法中，Shi和Malik[7]提出的Normalized cuts(Ncut)分割算法以其模型簡單且分割效果良好而著名．Ncut分割算法將分割問題巧妙地轉(zhuǎn)化為一個廣義特征值求解問題，極大地降低了求解優(yōu)化問題的難度，并且得到了良好的分割結(jié)果．但是在用Ncut算法分割高像素圖像時，所需構(gòu)造的相似性矩陣的階數(shù)非常大，進(jìn)而會加大廣義特征值問題的求解復(fù)雜度，使得算法耗時太長．針對這個問題，Choong等人[8]提出了二重Ncut分割算法，即采用兩級分割的形式，先將圖像等分成小塊，再用Ncut算法預(yù)分割每一小塊后得到預(yù)分割結(jié)果，然后用Ncut算法把預(yù)分割的結(jié)果聚類起來，得到最終的分割結(jié)果．該算法減少了所需構(gòu)造的相似性矩陣的階數(shù)，縮短了分割所需時間．但是該算法在預(yù)分割時等分了圖像，并沒有考慮到像素點(diǎn)所包含的特征信息(例如亮度信息與位置信息)，這樣就會把一些特征相似性很高的像素點(diǎn)分到不同的小塊去，進(jìn)而在第二步聚類時導(dǎo)致不理想的分割結(jié)果．

Rent和malik[9]提出了超像素分割的概念，該算法在進(jìn)行圖像分割時，可以利用像素點(diǎn)的一些特征先將圖像分成大量不規(guī)則的小塊(超像素)，然后再進(jìn)行后續(xù)的處理．超像素分割提供了一種圖像預(yù)處理的途徑，并且大大降低了后續(xù)圖像處理任務(wù)的復(fù)雜性[10]．基于超像素分割的重要性，人們提出了大量生成超像素的算法[11-14]，這些算法通過生成的超像素解決了一些圖像處理中所遇到的問題，但是它們的模型都較為復(fù)雜，運(yùn)行時間普遍較長，而且生成的超像素邊界也不能與原圖像邊界很好地匹配．針對這些問題，Achanta等人[15]提出了簡單線性迭代聚類的算法(SLIC)，用經(jīng)過改進(jìn)的K均值聚類算法來生成超像素，所得到的超像素邊界對圖像的原始邊界具有很強(qiáng)的依附性，并且處理速度與存儲效率也優(yōu)于其他的超像素分割算法．

本文針對Ncut分割方法耗時較長的問題，在使用Ncut分割算法的基礎(chǔ)上，提出一種基于SLIC超像素分割的圖分割算法，即先用SLIC超像素分割算法得到超像素；再通過提出的超像素特征計算公式得到每個超像素的特征信息并構(gòu)造相應(yīng)的相似性矩陣；然后用Ncut算法對這些特征信息進(jìn)行聚類，進(jìn)而得到最終結(jié)果．該算法應(yīng)用SLIC超像素分割算法的準(zhǔn)確性與高效性，有效降低了Ncut聚類時相似性矩陣的階數(shù)，大幅度縮短了Ncut算法的運(yùn)行時間，并且由于在預(yù)處理時充分考慮了像素點(diǎn)的特征信息，所以在分割自然圖像時，獲得了優(yōu)于Ncut分割算法以及二重Ncut分割算法的分割效果．

2 Ncut分割算法

基于cut模型的分割算法是一類經(jīng)典的圖分割算法，通過把特征相似性較高的像素點(diǎn)聚集起來形成相似區(qū)域來達(dá)到分割的效果．用圖G(V,E)來代表一幅圖像，其中節(jié)點(diǎn)的集合V代表像素點(diǎn)的集合，邊的集合E代表每一對像素點(diǎn)之間特征相似性w的集合．可以通過極小化集合A與集合B的特征相似性cut(A,B)，來把集合V分割成兩個子集合A和B，即A∩B=V,A∪B=?，cut(A,B)的定義如

其中w(i,j)表示節(jié)點(diǎn)i,j兩點(diǎn)之間的特征相似性，與i,j的特征信息有關(guān)．在形成的兩個集合A,B上，遞歸地執(zhí)行上述分割步驟，便可得到所需要分割成k塊的結(jié)果．這樣的結(jié)果，使得不同子集合中的點(diǎn)之間的特征相似性較低，而同一子集合中的點(diǎn)之間的特征相似性較高，符合圖像分割的要求．但是使用cut(A,B)模型的算法在處理具有孤立點(diǎn)(在某一區(qū)域內(nèi)特征鮮明的像素點(diǎn))的圖像時，容易把孤立點(diǎn)分割出來，從而得不到最優(yōu)的分割，如圖1所示的情況．

針對這個問題，Shi和Malik[7]提出了Ncut分割算法，使用

中的Ncut(A,B)模型來代替cut(A,B)模型．其中

表示A中的節(jié)點(diǎn)與V中所有節(jié)點(diǎn)特征相似性之和．

圖1:cut模型錯分圖示例

對于存在孤立點(diǎn)的情形，cut(A,B)值有可能達(dá)到了極小，這樣造成了孤立點(diǎn)的錯分．但由式(2)可以看出，Ncut(A,B)模型通過增加一個罰函數(shù)使得Ncut(A,B)在上述情形下不再是極小值，從而避免了cut(A,B)模型所造成的孤立點(diǎn)錯分．

Ncut(A,B)模型最終可轉(zhuǎn)化為

中廣義特征值問題的特征向量求解問題[16]．其中D是一個以d(i)為對角元素的對角矩陣，dW稱為相似性矩陣，其元素W(i,j)=w(i,j)．通過(3)式可得到最小非負(fù)特征值所對應(yīng)的特征向量y，對該向量上的元素進(jìn)行聚類，便可達(dá)到分割結(jié)果．由于K均值算法[16]的聚類速度很快，這里使用K均值算法來實(shí)施聚類．Ncut分割算法很巧妙得把分割問題轉(zhuǎn)化為一個廣義特征值求解問題，這極大地降低了求解優(yōu)化問題的難度，并且得到了良好的分割效果．

3 基于SLIC超像素分割的圖分割算法

使用Ncut分割算法進(jìn)行圖像分割時，相似性矩陣W的構(gòu)造對圖像分割效果以及計算復(fù)雜度都會有很大的影響．分割一個尺寸為m×n像素的圖像，就需要構(gòu)造一個階數(shù)為(m×n)×(m×n)的矩陣，對于高像素圖像來說，這將是一個階數(shù)非常大的矩陣，其構(gòu)造以及廣義特征值問題(3)的求解將會耗費(fèi)很多計算量，進(jìn)而影響分割的效率．因此降低相似性矩陣的階數(shù)是人們一直關(guān)注和討論的問題，也是一個具有挑戰(zhàn)性的問題．圖像分割前的預(yù)處理可以有效地降低相似性矩陣的階數(shù)．目前，超像素分割算法是一類有效的圖像預(yù)處理算法，其中SLIC超像素分割算法[16]是這類算法的典型代表，該算法處理速度與存儲效率都要優(yōu)于其它的超像素分割算法，并且所得到的超像素邊界對圖像原始邊界的依附性也很強(qiáng)．

鑒于此，本文提出了基于SLIC超像素分割的圖分割算法，即先用SLIC超像素分割算法得到超像素；再充分考慮所有像素點(diǎn)的特征信息，通過

構(gòu)造相應(yīng)的相似性矩陣；然后用Ncut算法對這些特征信息進(jìn)行聚類得到最終結(jié)果．其基本步驟如下：

第1步 在原始圖像上按照等距離L選取k個初始聚類中心，其中，N為原始圖像的像素點(diǎn)個數(shù)；

第2步 為了防止把邊界點(diǎn)或者奇異點(diǎn)設(shè)置為聚類中心，需要把聚類中心調(diào)節(jié)到原聚類中心周圍3×3像素點(diǎn)中梯度值最小的像素點(diǎn)；

第3步 在每個聚類中心周圍2L×2L的像素點(diǎn)區(qū)域內(nèi)進(jìn)行聚類，注意這里的聚類準(zhǔn)則涉及到像素點(diǎn)與聚類中心之間的距離以及兩者的亮度特征；

第4步 在得到的新聚類上，選取每一類中所有像素點(diǎn)的位置以及亮度特征的均值做為新聚類中心的位置與亮度特征；

第5步 如果新聚類中心與上一次聚類中心的特征信息的差異小于設(shè)定的閾值，則進(jìn)行第6步，否則，回到第2步，繼續(xù)下一輪聚類；

第6步 得到了超像素，并利用式(4)來計算超像素的特征信息；

第7步 依據(jù)各個超像素的特征信息，用Ncut算法來把這些超像素進(jìn)行聚類，得到最終的分割結(jié)果．

在第6步中，計算每個超像素的特征信息時，本文提出要充分考慮到超像素中所有像素點(diǎn)的特征信息．而像素點(diǎn)的主要特征信息包括其位置信息與亮度信息，目前結(jié)合位置信息和亮度信息來表示一些像素點(diǎn)特征信息的方式很多，例如用所有像素點(diǎn)位置信息和亮度信息的中位數(shù)或者平均值，或者最大值與最小值之和的一半來表示等．鑒于本文初步形成的超像素較小，求平均值相較于其他方法來說，既能夠考慮到超像素內(nèi)所有像素點(diǎn)的特征信息，計算起來又不復(fù)雜，且實(shí)驗結(jié)果較好，所以本文使用平均值形式，如式(4)，其中X(S)與F(S)分別表示所要計算的超像素S的位置信息與亮度信息，N為超像素S中所含像素點(diǎn)的數(shù)目，X(i)與F(i)分別表示像素點(diǎn)i的位置信息與亮度信息．這里值得注意的是，當(dāng)圖像為彩色圖像時，F(xiàn)(i)為一個三維的向量．

在第7步中，Ncut算法對生成的超像素進(jìn)行聚類時，需要構(gòu)造相應(yīng)的相似性矩陣．本文采用既考慮亮度信息又考慮位置信息的構(gòu)造方式，如(5)式所示，其中w(S,T)表示超像素S與超像素T特征相似性，σI與σX分別表示所有像素點(diǎn)亮度信息的標(biāo)準(zhǔn)差與位置信息的標(biāo)準(zhǔn)差，r為一個閾值，當(dāng)點(diǎn)超像素S與超像素T之間的位置信息之差的2-范數(shù)大于等于r時，w(S,T)為0，r的大小與原圖像的尺寸有關(guān)．將式(4)代入式(5)可得到w(S,T)與各像素點(diǎn)特征信息的關(guān)系，如式(6)所示，式中Fm(S)與Xm(S)分別表示超像素S中所有像素點(diǎn)亮度信息與位置信息的均值．

4 自然圖像分割實(shí)驗

為了驗證基于SLIC超像素分割的圖分割算法的優(yōu)越性，本文采用一些自然圖像為例進(jìn)行分割實(shí)驗，并從分割效果與所用時間的角度，與Ncut分割算法[7]以及二重Ncut分割算法[8]進(jìn)行比較．在進(jìn)行比較實(shí)驗前，本文先對本文算法的參數(shù)予以說明．該算法前期生成超像素的過程中，會產(chǎn)生兩個參數(shù)：額定的超像素尺寸regionsize以及位置信息在聚類時所占的權(quán)重regularizer．其中regionsize的大小還決定了SLIC超像素分割中初始聚類中心的個數(shù)．不同的參數(shù)會產(chǎn)生不同的超像素，通過調(diào)節(jié)這兩個參數(shù)的大小，可以得到理想的超像素，進(jìn)而產(chǎn)生理想的分割結(jié)果．為了說明這兩個參數(shù)對圖像分割效果的影響，本文給出在不同參數(shù)下，使用該算法分割一個200×200尺寸合成圖像的結(jié)果，如圖2所示．

圖2:本文算法在不同參數(shù)下的分割結(jié)果

圖2中，(a)為原圖，(b),(c),(d)組圖分別對應(yīng)為regionsize為20,40,60時的情況，各圖對應(yīng)的regularizer取值見圖中標(biāo)注．從圖2中可以看出，兩個參數(shù)選取不同值時，得到的分割結(jié)果不盡相同．當(dāng)regionsize=20時，取regularizer=1才可以清晰地把四種顏色的小塊分割出來，分割的邊界完全與原圖像的邊界重合，regularizer取其它值時，則會使得分割邊界偏離原圖像的邊界；當(dāng)regionsize=40時，取regularizer=0.5可以使分割結(jié)果達(dá)到最佳，regularizer取其它值時，則會使得分割邊界變得不規(guī)則，得不到好的分割效果；當(dāng)regionsize=60時，取regularizer=0.5所得到的效果最好，而regularizer取其它值則會使得分割邊界向左或者向右偏移．

從上面的實(shí)驗可以看出，當(dāng)regionsize不同時，即SLIC超像素分割中初始聚類中心的個數(shù)不一樣時，我們可以通過調(diào)節(jié)regularizer的大小來得到想要的分割結(jié)果．一般情況下regularizer越大，所得到的分割邊界越規(guī)則．原則上來說，regionsize越小，所得到的分割結(jié)果應(yīng)該越精確，但是regionsize越小，所需要的計算量也就越大，進(jìn)而影響算法的效率．綜上所述，在處理圖像時，可以根據(jù)圖像的實(shí)際情況來選取regularizer和regionsize．其中regionsize可以視圖像像素大小來定，圖像像素較大時選擇大一點(diǎn)的值來提升運(yùn)算速率，圖像像素較小時選擇小一點(diǎn)的值來提高分割質(zhì)量．另外，在圖像邊界較為規(guī)則時，regularizer可以選擇一個較小的值，在圖像邊界不規(guī)則時，regularizer可以選擇一個較大的值．

下面本文給出本文算法的自然圖像實(shí)例，綜合考慮實(shí)驗用圖的實(shí)際情況，我們選取參數(shù)為regionsize=85,regularizer=0.8，并就其分割效果與Ncut分割算法以及二重Ncut分割算法進(jìn)行比較，如圖3至圖5所示．

圖3至圖5分別是人物頭像、前景物體較大的圖像與邊界復(fù)雜的圖像的分割效果比較．圖中所有(a)都是原始圖像，所有(b)和(c)分別為Ncut分割法的分割結(jié)果和二重Ncut分割法的分割結(jié)果，所有(d)是本文算法中第6步所形成的超像素圖像，所有(e)是本文算法的分割結(jié)果．比較(b)和(e)，可以發(fā)現(xiàn)，在分割人物頭像時，本文算法與Ncut分割法所得到的結(jié)果基本相似，分割邊界都基本與頭像邊界相重合，所得到的分割結(jié)果都較為理想．在分割前景物體較大的圖像以及邊界復(fù)雜的圖像時，本文算法所得到的分割結(jié)果要優(yōu)于Ncut分割算法的結(jié)果，并且分割邊界更加相似于原始圖像的邊界，能夠把較大的前景物體與邊界復(fù)雜的物體更好地分割出來．觀察三類圖像的(c)，可以發(fā)現(xiàn)二重Ncut分割法無論是在分割人物頭像，還是分割邊界復(fù)雜的圖像，都不能得到理想的效果，分割結(jié)果的邊界與圖像的邊界有比較大的差異．造成這這些現(xiàn)象的原因就是，二重Ncut分割法在進(jìn)行第一次Ncut分割前，對原始圖像進(jìn)行了等分的步驟，這樣并沒有考慮到像素點(diǎn)本身所具有的一些特征信息，使得經(jīng)過第一次Ncut算法分割后所得到小塊的邊界與原始圖像的邊界并不相似，進(jìn)而使得經(jīng)過第二次Ncut算法聚類后所得到的邊界也不是很理想．而本文算法在進(jìn)行Ncut算法聚類前，使用SLIC超像素分割法把原始圖像分割成一個個超像素，由于考慮到了像素點(diǎn)本身所具有的一些特征信息，這就使得生成的超像素的邊界能夠與部分原始圖像的邊界相重合，如(d)所示，進(jìn)而得到理想的分割效果．

圖3:人物頭像的分割效果比較

圖4:前景物體較大圖像的分割效果比較

圖5:邊界復(fù)雜圖像的分割效果比較

除了比較三種分割算法分割效果外，本文還比較了三種算法的運(yùn)行速度，如表1所示．

表1:三類算法運(yùn)行速度的比較

表1列出了三種算法分割三類圖像時所需的時間，通過觀察發(fā)現(xiàn)，無論分割哪一類圖像，本文算法的運(yùn)行速度都要遠(yuǎn)遠(yuǎn)優(yōu)于Ncut分割算法．這是因為對SLIC超像素分割法所得到的超像素進(jìn)行Ncut聚類時，有效降低了所需要計算的相似性矩陣的階數(shù)，進(jìn)而大幅減少了解決廣義特征值問題(3)的計算量．二重Ncut分割法雖然也通過使用第一次Ncut分割算法產(chǎn)生小塊，再對小塊進(jìn)行Ncut聚類的辦法，降低了相似性矩陣的階數(shù)，但是其產(chǎn)生小塊的速度要比SLIC超像素分割法把圖像分割成超像素的速度慢得多，所以本文算法的運(yùn)行速度也要比二重Ncut分割法的速度快．

通過三類圖像的分割比較實(shí)驗，可以發(fā)現(xiàn)本文所提出的基于SLIC超像素分割的圖分割算法不僅在圖像分割精度上達(dá)到了最佳，且計算速度也遠(yuǎn)遠(yuǎn)快于其它兩種算法．由此可見，與其它算法相比，權(quán)衡其分割精度和計算速度，本文提出的基于SLIC超像素分割的圖分割算法不失為一種非常實(shí)用有效的圖像分割算法．

5 結(jié)論與展望

本文提出了一種關(guān)于Ncut分割算法的改良算法，即基于SLIC超像素分割的圖分割算法．通過SLIC超像素分割算法形成超像素，這種算法有效降低了Ncut聚類時相似性矩陣的階數(shù)，進(jìn)而很大程度地縮短了廣義特征值問題的求解時間；由于SLIC超像素分割算法的準(zhǔn)確性與高效性，該算法也得到了理想的分割效果．本文以三類自然圖像為例，比較了本文算法，Ncut分割算法以及二重Ncut分割算法的性能．實(shí)驗結(jié)果表明，本文算法的分割效果與所需時間，都要明顯優(yōu)于其它兩種算法．

由于比較分割準(zhǔn)確率需要用到公用數(shù)據(jù)庫以及用機(jī)器學(xué)習(xí)算法去學(xué)習(xí)得到所需的參數(shù)，本文在比較幾種算法的分割效果時，沒有用分割準(zhǔn)確率進(jìn)行具體比較，只用人工比對的方式進(jìn)行了評判．在下一步的工作中，我們將借助公用數(shù)據(jù)庫，利用機(jī)器學(xué)習(xí)算法學(xué)習(xí)而得到所需的參數(shù)，再將本文算法與其它算法的分割準(zhǔn)確率進(jìn)行具體比較．此外，超像素邊界的確定方式有待進(jìn)一步改進(jìn)，在下一步的工作中，我們會考慮到一些其他影響邊界的方法，例如去噪、形態(tài)學(xué)方法等．

參考文獻(xiàn)：

[1]Shap iro L,Stockm an G C.Com puter V ision[M].New Jersey:Prentice Hall,2001

[2]Zhu S,X ia X,Zhang Q,et al.An im age segm entation algorithm in im age processing based on th reshold segm entation[C]//International IEEE Con ference on Signal-Im age Technologies and Internet-Based System,2007:673-678

[3]Patil R V,Jondhale K C.Edge based technique to estim ate num ber of clusters in k-means color im age segm entation[C]//International IEEE Con ference on Com puter Science and In form ation Technology,2010:117-121

[4]Chen G,Hu T,Guo X,et al.A fast region-based im age segm entation based on least square method[C]//International IEEE Conference on System s,man and Cybernetics,2009:972-977

[5]Zhao W,Zhang J,Li P,et al.Study of im age segm entation algorithm based on tex tural featu res and neu ral network[C]//International Con ference on Intelligent Com puting and Cognitive In form atics,2010:300-303

[6]W u Z,Leahy R.An op tim al graph theoretic app roach to data clustering:theory and its app lication to im age segm entation[J].IEEE Transactions on Pattern Analysis and machine Intelligence,1993,15(11):1101-1113

[7]Shi J,malik J.Norm alized cuts and im age segm entation[J].IEEE Transactions on Pattern Analysis and machine Intelligence,2000,22(8):888-905

[8]Choong mY,Liau C F,mountstephens J,et al.mu ltistage im age clustering and segm entation with norm alized cuts[C]//International Con ference on Intelligent System s,modelling and Simulation,2012:362-367

[9]Ren X,malik J.Learning a classifi cation model for segm entation[C]//International IEEE Con ference on Com puter V ision,2003:10-17

[10]王春瑤，陳俊周，李煒.超像素分割算法研究綜述[J].計算機(jī)應(yīng)用研究，2014,31(1):6-12 W ang C Y,Chen J Z,LiW.Review on the superp ixels segm entation methods[J].App lication Research of Com puters,2014,31(1):6-12

[11]Felzenszwalb pF,Hutten locher D P.E ffi cient graph-based im age segm entation[J].International Journal of Com puter V ision,2004,59(2):167-181

[12]Vedaldi A,Soatto S.Quick shift and kernel methods for mode seeking[C]//European Con ference on Com puter V ision,2008:705-718

[13]Veksler O,Boykov Y,meh rani P.Superpixels and supervoxels in an energy op tim ization fram ework[C]//European Con ference on Com pu ter V ision,2010:211-224

[14]Levinshtein A,Stere A,K utu lakos K N,et al.Tu rbopixels:fast superp ixels using geom etric fl ow s[J].IEEE Transactions on Pattern Analysis and machine Intelligence,2009,31(12):2290-2297

[15]Achanta R,Sha ji A,Sm ith K,et al.SLIC superp ixels com pared to state-of-the-art superp ixelm ethods[J].IEEE Transactions on Pattern Analysis and machine Intelligence,2012,34(11):2274-2282

[16]Golub G H,Van Loan C F.matrix Com putations[M].Baltim ore:JHU Press,1984