李鵬,楊旸,方濤

(1.上海交通大學(xué)自動化系,200240,上海;2.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

?

應(yīng)用視覺顯著性的快速有偏聚類超像素算法

李鵬1,2,楊旸2,方濤1

(1.上海交通大學(xué)自動化系,200240,上海;2.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

針對正則化超像素方法的超像素數(shù)隨邊緣擬合要求迅速增長的問題,提出了一種有偏聚類超像素算法。結(jié)合人類視覺對目標(biāo)專注程度不一的特點,在SLIC算法框架下,提出了基于視覺顯著性的非均勻初始化方法和有偏聚類距離函數(shù)。算法在圖像的顯著性區(qū)域進(jìn)行密集的過分割,保持目標(biāo)邊緣的細(xì)節(jié)信息,而在非顯著區(qū)域僅生成稀疏的超像素,以降低分割塊數(shù),再通過一步全局聚類和邊緣逐步細(xì)化過程,有效地保證了圖像的邊緣擬合,同時提高了算法的速度。實驗表明,在相同超像素數(shù)下,所提算法在邊緣查全率、欠分割錯誤率以及運行速度方面均優(yōu)于傳統(tǒng)算法。

超像素;視覺顯著性;有偏聚類;邊緣細(xì)化

超像素是一種基于圖像局部顏色、紋理等特征的圖像過分割表示,近年來已成為計算機視覺算法,如目標(biāo)識別[1]、圖像分割[2]、特征檢測等應(yīng)用中的重要工具。作為預(yù)處理步驟,超像素不僅能極大地提高后續(xù)算法的計算效率,并且因為分割塊之間具有更高層的上下文信息,在視覺算法中有著重要的利用價值,其對目標(biāo)邊緣的擬合能力、分割塊形態(tài)的正則化程度以及計算效率是衡量超像素算法好壞的標(biāo)準(zhǔn)。

目前一些圖像分割算法,如Mean shift算法[3]、GS算法[4]、Quick shift算法[5]等具有較好的圖像邊緣擬合效果,但由于生成的是非正則化分割塊,不利于后續(xù)對分割塊間空間上下文信息的引入。正則化的超像素方法有N-cuts算法[6]、Lattices算法[7]、Vcell方法[8]和SLIC算法[9]等,但由于超像素數(shù)是事先指定的,當(dāng)需要更大程度擬合目標(biāo)的局部邊緣細(xì)節(jié)時,正則化超像素方法需要增加全局的過分割數(shù)目,因此算法的復(fù)雜度也相應(yīng)地提高。

考慮到高層視覺感知的特點,人類更希望辨識圖像中顯著性目標(biāo)的細(xì)節(jié),而由于背景所含信息量較少,稀疏的劃分塊是可以接受的分割方式?；谏鲜鲇^察,本文提出了一種新的有偏聚類超像素算法,其特點是結(jié)合了高層視覺顯著性特征,根據(jù)圖像內(nèi)容生成變密度的超像素結(jié)果,從而同時達(dá)到了在圖像顯著性區(qū)域的邊緣細(xì)節(jié)擬合和局部超像素正則化的要求。實驗結(jié)果表明,在相同的超像素數(shù)下,所提算法在邊緣查全率、欠分割錯誤率以及運行速度方面均優(yōu)于傳統(tǒng)算法。

1 傳統(tǒng)的SLIC超像素算法

超像素算法可以歸結(jié)為將具有局部相似性的像素劃分成色塊的聚類問題,其算法包括初始化、距離函數(shù)、聚類搜索范圍3個核心部分。SLIC算法在初始化階段,將圖像劃分為尺寸相等的網(wǎng)格,以網(wǎng)格中心作為初始超像素中心。對于任意的兩個像素,定義像素間的距離Dij,同時考慮了像素空間位置和顏色信息,即

(1)

式中:dc代表兩像素在CIELAB色彩模型中的顏色距離;ds則表示它們在圖像上的空間距離;m為距離權(quán)重,一般設(shè)定為常量;S為初始網(wǎng)格的邊長。

SLIC指定了以超像素中心相鄰的2倍網(wǎng)格邊長的矩形搜索范圍,迭代計算該范圍內(nèi)的像素與各超像素中心的距離,并將其指派給距離最近的超像素中心。相比于經(jīng)典的K-means算法的全局搜索,SLIC大大減少了距離計算的次數(shù),但整個聚類過程仍需要十幾次迭代才能收斂。

實驗發(fā)現(xiàn),SLIC經(jīng)過兩次迭代搜索后已經(jīng)生成了接近最終收斂結(jié)果的超像素,后續(xù)的迭代過程雖然計算了搜索范圍內(nèi)所有像素的距離,但事實上僅對分割邊緣上的若干像素進(jìn)行了調(diào)整。算法的絕大部分時間花費在了對超像素塊邊界的微調(diào)。

2 有偏聚類超像素算法

本文提出的有偏聚類超像素算法,針對傳統(tǒng)SLIC算法的3個核心部分進(jìn)行了改進(jìn)。算法對顯著區(qū)域生成密集超像素,保留了邊緣細(xì)節(jié)信息,而在非顯著區(qū)域生成稀疏的超像素,減少全局超像素數(shù),并采用一步聚類和邊緣細(xì)化搜索方案,大大提高了聚類過程的速度。算法總體思路如下:

(1)在初始化階段,根據(jù)圖像顯著性圖,生成顯著區(qū)域不同密度尺寸的初始網(wǎng)格劃分;

(2)設(shè)計結(jié)合圖像顯著性信息的距離函數(shù),對顯著性不同的區(qū)域采用不同的空間距離和顏色距離權(quán)重;

(3)首先進(jìn)行一次聚類搜索,隨后迭代進(jìn)行邊緣細(xì)化,即僅對當(dāng)前超像素邊緣上的像素進(jìn)行距離計算和超像素劃分,以減少距離計算次數(shù),從而提高算法效率。

所提算法分為初始化網(wǎng)格、一步聚類和邊緣細(xì)化3個步驟,如圖1所示。

2.1 初始化網(wǎng)格

容易看出,當(dāng)初始超像素中心間的距離越小,超像素就越密集,反之則越稀疏。因此,在顯著區(qū)域選取更加密集的初始超像素中心,可使圖像中顯著性分割分得更加細(xì)致。目前已有很多較為成熟的顯著性算法,本文采用了SIG算法[10]提取圖像的顯著性,目的是在較低的運算時間下保證生成的顯著圖的準(zhǔn)確性。

實驗發(fā)現(xiàn),當(dāng)像素顯著性大于0.7時,所得顯著區(qū)域接近于人類視覺認(rèn)知的感興趣區(qū)域。本文采用雙閾值方法對顯著圖進(jìn)行二值化,即取顯著度大于0.7的區(qū)域與顯著度最高的占圖像面積15%的區(qū)域的并集定為顯著區(qū)域R2,其余為不顯著區(qū)域R1。

改進(jìn)的初始化算法通過兩次不同尺寸的網(wǎng)格劃分選取初始超像素中心。假設(shè)圖像像素數(shù)為N,圖像中顯著像素數(shù)為c,參數(shù)t表示不顯著區(qū)域與顯著區(qū)域超像素大小的比值,S1為全局圖像均勻劃分網(wǎng)格G1的間距,則局部顯著區(qū)域R2的網(wǎng)格G2劃分的間距S2滿足

(2)

定義超像素塊總數(shù)為K,其值等于顯著區(qū)域網(wǎng)格數(shù)目與不顯著區(qū)域網(wǎng)格數(shù)目之和,即

(3)

(a)原始圖像 (b)初始化網(wǎng)格 (c)一步聚類 (d)邊緣細(xì)化圖1 本文算法的步驟

由式(2)、式(3)可得,全局圖像的網(wǎng)格G1劃分的間距S1為

(4)

選取劃分后的網(wǎng)格中心為初始超像素中心。定義網(wǎng)格G1中心點顯著性為0,網(wǎng)格G2中心點顯著性為1。

2.2 一步聚類

一步聚類的思想是在定義的距離函數(shù)下,對每個超像素中心對應(yīng)搜索范圍內(nèi)的像素僅進(jìn)行一次距離計算,將該像素劃分到距離最近的超像素塊中,其中距離函數(shù)的定義和搜索范圍的指定都會影響到劃分的結(jié)果。

(a)m=80 (b)m=40 (c)m=20 (d)m=10圖2 SLIC算法在不同權(quán)值m下的超像素結(jié)果

圖2給出了SLIC算法取不同權(quán)值m下的超像素結(jié)果。可以看出,隨著m的減小,色彩在距離計算中所占權(quán)重增加,得到的超像素更加擬合圖像邊緣細(xì)節(jié),因而對于圖像中的顯著區(qū)域,應(yīng)選取更小的權(quán)值m以保持更多的圖像細(xì)節(jié)。因此,在有偏聚類定義的距離計算公式中,權(quán)值m取值根據(jù)像素的顯著性服從高斯分布。像素Pi與第k個超像素中心的距離定義為

(5)

有偏聚類超像素算法,每次搜索在以超像素中心Ck為中心的矩形鄰域內(nèi),搜索范圍的邊長根據(jù)超像素中心的顯著性自適應(yīng)調(diào)整,若sal(Ck)為0,則取搜索范圍為2×S1,若為1則取2×S2。

2.3 邊緣細(xì)化

從圖1c、圖1d可以看出,經(jīng)過一步聚類生成的超像素結(jié)果,如果按照聚類算法繼續(xù)迭代,則只有超像素邊緣上像素進(jìn)行著局部調(diào)整。該現(xiàn)象已經(jīng)被大量實驗證實,其原因是在距離函數(shù)中考慮了像素的空間距離,因而絕大多數(shù)的內(nèi)點與初始超像素中心較近,經(jīng)過距離計算判定后不會發(fā)生變動。

受VCell算法[8]中對超像素邊界處理技巧的啟發(fā),本文在后續(xù)的迭代過程中進(jìn)行邊緣細(xì)化,即只對超像素的邊緣像素進(jìn)行距離計算與指派。邊緣細(xì)化依舊遵循著SLIC算法框架,首先查找超像素中心鄰域矩形內(nèi)的邊緣像素,計算邊緣像素Pi與該超像素中心Ck的距離,根據(jù)該距離與原距離的大小決定是否重新指派該像素。從生成超像素的過程看,隨著邊緣像素的重新指派,超像素邊緣不斷地細(xì)化直到超像素的目標(biāo)誤差函數(shù)收斂。因此,在后續(xù)的迭代過程中,相比于要計算每個超像素鄰域內(nèi)的所有像素,算法的運算次數(shù)顯著減少。

下面比較分析本文算法的時間復(fù)雜度。由于選擇的SIG顯著性算法的時間耗費很低,相比于后續(xù)的超像素分割過程,運行時間可以忽略。提出的算法在一步聚類過程中,運算的次數(shù)為4N(N為圖像像素數(shù)),在邊緣細(xì)化過程中,每次迭代只計算邊緣上像素,以均勻的方格邊緣估計,計算次數(shù)約為4(KN)1/2(K為超像素數(shù),取值遠(yuǎn)小于N),因此算法整體時間復(fù)雜度為O((KN)1/2)。傳統(tǒng)的SLIC超像素算法的時間復(fù)雜度為O(N),GS算法時間復(fù)雜度為O(NlogN),QS算法最慢,時間復(fù)雜度為O(dN2),其中d為一個常量,由此得到本文算法在時間復(fù)雜度上具有優(yōu)勢。

3 實驗結(jié)果分析

3.1 實驗設(shè)計

實驗將本文的有偏聚類超像素算法與SLIC算法[9]、QS算法[5]、GS算法[4]在整體分割效果、算法復(fù)雜度與效率、邊緣擬合能力以及用于圖像的多類目標(biāo)分割4個方面進(jìn)行了對比。測試圖像來源于Berkeley數(shù)據(jù)庫[11],其中包含了500張大小為481×321的不同場景圖像。多類分割訓(xùn)練測試圖像來源于MSRC數(shù)據(jù)庫[12],其中包含21類不同場景的目標(biāo)圖像,其他3種算法參數(shù)均采用默認(rèn)參數(shù)。實驗計算機CPU為i5-4430,內(nèi)存為4 GB。

(a)本文算法 (b)SLIC算法 (c)QS算法 (d)GS算法圖3 不同算法在Berkeley數(shù)據(jù)庫[11]中圖像上的超像素結(jié)果對比(下圖是上面結(jié)果的局部放大圖)

3.2 超像素結(jié)果

超像素作為計算機視覺算法中的重要預(yù)處理步驟,其過分割結(jié)果是否能很好地擬合目標(biāo)的邊緣,將對后續(xù)算法起到關(guān)鍵作用。圖3為本文算法與最新算法的效果對比。人臉是一般計算機視覺算法的感興趣區(qū)域,因此好的超像素算法應(yīng)該盡可能地表現(xiàn)出人臉的細(xì)節(jié)信息,比如眉毛、眼睛等。從圖3中可以看到,本文算法在顯著區(qū)域人臉上分割的更加密集細(xì)致,將眼睛、眉毛等部位分割為單獨超像素,符合人臉視覺感知的特點,并且超像素形狀也比較規(guī)則,正則化效果好。SLIC算法、QS算法在人臉和背景區(qū)域具有相同的分割密度,從細(xì)節(jié)放大圖中可以看到,二者都將眼睛、眉毛和之間的皮膚混合為一個超像素,從而丟失了眼睛、眉毛信息。GS生成非正則化的超像素,其形狀和大小都不規(guī)則。

圖4比較了在不同超像素數(shù)下,各算法對目標(biāo)邊界細(xì)節(jié)的表示能力。在相似的顯著目標(biāo)邊界的擬合效果上,本文算法需要100個超像素,如圖4b所示,而SLIC算法需要500個超像素,如圖4d所示。因此可得,在保持相同的細(xì)節(jié)信息時,本文算法所需要的超像素數(shù)遠(yuǎn)小于SLIC算法所需要的,這將明顯減少后續(xù)視覺算法需要處理的超像素數(shù),降低時間復(fù)雜度。

3.3 運行時間比較

圖5a為算法對Berkeley數(shù)據(jù)庫[11]中圖像的運行時間比較,其中橫軸表示了以最大尺寸圖像的像素數(shù)為基礎(chǔ)的歸一化圖像像素數(shù),超像素數(shù)均為300?？梢钥闯?QS算法時間耗費最大,曲線基本隨圖像像素數(shù)呈次方倍增長,SLIC算法時間耗費呈線性增長,GS算法時間耗費介于QS算法、SLIC算法之間。與文中分析的時間復(fù)雜度結(jié)果一樣,本文算法的運行時間最少,處理最大尺寸圖像所需時間不到5 s。圖5b為在Berkeley數(shù)據(jù)庫[11]上選取超像素數(shù)為100～500時的算法時間對比,可以看出,本文算法的運行時間明顯低于其他算法的運行時間。

3.4 邊緣擬合效果

(a)原圖 (b)本文算法(k=100) (c)SLIC(k=100) (d)SLIC(k=500)圖4 本文算法與SLIC算法在Berkeley數(shù)據(jù)庫[11]中圖像上的邊界擬合效果對比(下圖是上面結(jié)果的局部放大圖)

一種量化比較超像素邊緣擬合能力的標(biāo)準(zhǔn)方法是計算邊緣查全率[8]和欠分割錯誤率[8]。邊緣查全率計算正確邊緣落入以超像素邊緣像素為中心、兩個像素為半徑區(qū)域內(nèi)的部分的比例。另外,假定存在一個正確的標(biāo)準(zhǔn)分割區(qū)域和與該分割區(qū)域有交集的超像素,欠分割誤差就是計算該超像素超出標(biāo)準(zhǔn)分割區(qū)域的比例。整幅圖像的欠分割錯誤率是所有分割區(qū)域欠分割誤差的平均值。

圖6分別為本文算法與SLIC算法、QS算法、GS算法的邊界查全率和欠分割錯誤率的對比。測試集為Berkeley數(shù)據(jù)庫[11]中200張測試圖像和庫中提供的手工目標(biāo)分割結(jié)果?？梢钥闯?在相同的超像素數(shù)下,本文算法的邊緣查全率最高,欠分割誤差率最低。這是因為本文的超像素集中在顯著物體上,能保留顯著區(qū)域更多的邊緣信息,且對背景進(jìn)行稀疏的分割,忽略了背景中無用的邊緣信息。例如,本文算法能夠更好地擬合人臉中鼻子、眼睛的邊緣,而背景中的水面、天空、草原往往不存在邊緣或者邊緣無用而被忽略。因而,本文算法能夠保持圖像的重要邊緣信息,有利于提高后續(xù)處理的準(zhǔn)確性。

3.5 多類目標(biāo)分割

超像素通常作為目標(biāo)分割算法的預(yù)處理步驟。本文在MSRC數(shù)據(jù)庫[12]上將本文算法與SLIC算法、QS算法、GS算法用于多類目標(biāo)分割的效果進(jìn)行了對比,所有算法的超像素數(shù)均取為200。分割算法采用文獻(xiàn)[13]所提算法,首先利用超像素計算圖像的顏色、紋理、幾何以及位置特征,在獲得的特征基礎(chǔ)上訓(xùn)練21類目標(biāo)分類器,最后學(xué)習(xí)CRF模型生成圖像分割結(jié)果。通過與手工分割結(jié)果的對比計算算法的分割精度,結(jié)果見表1?？梢钥闯?用于多類目標(biāo)分割時,本文算法的分割精度均優(yōu)于其他算法。圖7為算法與SLIC算法用于多類分割的分割效果,可以看出,所提算法能夠保留更多的目標(biāo)細(xì)節(jié),分割結(jié)果更接近于人工分割結(jié)果。

(a)不同像素數(shù)圖像的算法時間

(b)不同超像素數(shù)的算法時間

(a)邊緣查全率

(b)欠分割錯誤率

(a)原圖 (b)手工分割 (c)本文算法 (d)SLIC算法圖7 在MSRC數(shù)據(jù)庫[12]中圖像上的多類目標(biāo)分割結(jié)果

表1 不同超像素算法用于多類目標(biāo)分割的精度對比

超像素算法分割精度/%本文算法749SLIC算法[9]743QS算法[5]737GS算法[4]730

4 結(jié) 論

本文提出了一種新的有偏聚類超像素算法,同時考慮了高層的視覺顯著性特征和底層的圖像顏色特征,引入視覺顯著性非均勻初始化方法和有偏聚類距離函數(shù),通過一步全局聚類和邊緣細(xì)化方法形成一種更加符合人類視覺感知特點的變密度局部正則化的超像素結(jié)果。實驗從分割效果、算法復(fù)雜度、邊緣擬合能力以及用于多類圖像分割等方面均證實了提出算法的有效性和快速性。

[1] MORI G. Guiding model search using segmentation [C]∥10th IEEE International Conference on Computer Vision. Piscataway, NJ, USA: IEEE, 2005: 1417-1423.

[2] FULKERSON B, VEDALDI A, SOATTO S. Class segmentation and object localization with superpixel neighborhoods [C]∥12th IEEE International Conference on Computer Vision. Piscataway, NJ, USA: IEEE, 2009: 670-677.

[3] COMANICIU D, MEER P. Mean shift: a robust approach toward feature space analysis [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[4] FELZENSZWALB P F, HUTTENLOCHER D P. Efficient graph-based image segmentation [J]. International Journal of Computer Vision, 2004, 59(2): 167-181.

[5] VEDALDI A, SOATTO S. Quick shift and kernel methods for mode seeking [C]∥10th European Conference on Computer Vision. Berlin, Germany: Springer, 2008: 705-718.

[6] SHI J, MALIK J. Normalized cuts and image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[7]MOOREAP,PRINCES,WARRELLJ,etal.Superpixellattices[C]∥IEEEConferenceonComputerVisionandPatternRecognition.Piscataway,NJ,USA:IEEE, 2008: 1-8.

[8]WANGJ,WANGX.Vcells:simpleandefficientsuperpixelsusingedge-weightedcentroidalVoronoitessellations[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2012, 34(6): 1241-1247.

[9]ACHANTAR,SHAJIA,SMITHK,etal.SLICsuperpixelscomparedtostate-of-the-artsuperpixelmethods[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2012, 34(11): 2274-2281.

[10]HOUX,HARELJ,KOCHC.Imagesignature:highlightingsparsesalientregions[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2012, 34(1): 194-201.

[11]MARTIND,FOWLKESC,TALD,etal.Adatabaseofhumansegmentednaturalimagesanditsapplicationtoevaluatingsegmentationalgorithmsandmeasuringecologicalstatistics[C]∥ProceedingsofEighthIEEEInternationalConferenceonComputerVision.Piscataway,NJ,USA:IEEE, 2001: 416-423.

[12]SHOTTONJ,WINNJ,ROTHERC,etal.Textonboostforimageunderstanding:multi-classobjectrecognitionandsegmentationbyjointlymodelingtexture,layout,andcontext[J].InternationalJournalofComputerVision, 2009, 81(1): 2-23.

[13]GOULDS,RODGERSJ,COHEND,etal.Multi-classsegmentationwithrelativelocationprior[J].InternationalJournalofComputerVision, 2008, 80(3): 300-316.

(編輯 趙煒)

A Fast Superpixel Algorithm with Biased-Clustering Using Visual Saliency

LI Peng1,2,YANG Yang2,FANG Tao1

(1. Department of Automation, Shanghai Jiaotong University, Shanghai 200240, China; 2. School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

A novel biased-clustering superpixel algorithm is proposed in the framework of SLIC to improve the problem that the conventional superpixel methods have bottleneck in controlling the tradeoff between superpixel number and boundary adherence. The algorithm employs the visual saliency into the non-uniform mesh initialization step and the biased-clustering distance function by noticing that human’s visual attentions are distinctive to different salient objects, so that dense over-segmentations are generated in salient regions to keep sufficient information for object’s boundary; while sparse segmentations are generated in non-salient regions to reduce the number of segmentation blocks. Moreover, the ideas of one-step global clustering and gradual boundary refining are applied to speed up the algorithm. Experimental results and comparisons with several state-of-the-art superpixel algorithms show that the proposed algorithm reflects the boundary adherence for salient objects well under the same number of segmentation blocks, and has a higher boundary recall and lower under-segmentation, as well as the least time-consuming.

superpixel; visual saliency; biased-clustering; boundary refining

2014-05-06。

李鵬(1992—),男,碩士生;楊旸(通信作者),女,講師。

國家自然科學(xué)基金資助項目(61203254);教育部博士點基金資助項目(20120201120024)。

10.7652/xjtuxb201501019

TP391

A

0253-987X(2015)01-0112-06