應用視覺顯著性的快速有偏聚類超像素算法

李鵬,楊旸,方濤

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

?

應用視覺顯著性的快速有偏聚類超像素算法

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

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

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

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

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

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

考慮到高層視覺感知的特點,人類更希望辨識圖像中顯著性目標的細節,而由于背景所含信息量較少,稀疏的劃分塊是可以接受的分割方式。基于上述觀察,本文提出了一種新的有偏聚類超像素算法,其特點是結合了高層視覺顯著性特征,根據圖像內容生成變密度的超像素結果,從而同時達到了在圖像顯著性區域的邊緣細節擬合和局部超像素正則化的要求。實驗結果表明,在相同的超像素數下,所提算法在邊緣查全率、欠分割錯誤率以及運行速度方面均優于傳統算法。

1 傳統的SLIC超像素算法

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

(1)

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

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

實驗發現,SLIC經過兩次迭代搜索后已經生成了接近最終收斂結果的超像素,后續的迭代過程雖然計算了搜索范圍內所有像素的距離,但事實上僅對分割邊緣上的若干像素進行了調整。算法的絕大部分時間花費在了對超像素塊邊界的微調。

2 有偏聚類超像素算法

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

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

(2)設計結合圖像顯著性信息的距離函數,對顯著性不同的區域采用不同的空間距離和顏色距離權重;

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

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

2.1 初始化網格

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

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

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

(2)

定義超像素塊總數為K,其值等于顯著區域網格數目與不顯著區域網格數目之和,即

(3)

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

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

(4)

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

2.2 一步聚類

一步聚類的思想是在定義的距離函數下,對每個超像素中心對應搜索范圍內的像素僅進行一次距離計算,將該像素劃分到距離最近的超像素塊中,其中距離函數的定義和搜索范圍的指定都會影響到劃分的結果。

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

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

(5)

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

2.3 邊緣細化

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

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

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

3 實驗結果分析

3.1 實驗設計

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

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

3.2 超像素結果

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

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

3.3 運行時間比較

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

3.4 邊緣擬合效果

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

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

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

3.5 多類目標分割

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

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

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

(a)邊緣查全率

(b)欠分割錯誤率

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

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

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

4 結 論

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

[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—),男,碩士生;楊旸(通信作者),女,講師。

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

10.7652/xjtuxb201501019

TP391

A

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