一種快速的超像素分割方法

劉　俊

(西安電子科技大學 電子信息攻防對抗與仿真重點實驗室,陜西 西安　710071)

?

一種快速的超像素分割方法

劉俊

(西安電子科技大學 電子信息攻防對抗與仿真重點實驗室,陜西 西安710071)

摘要圍繞圖像分割算法介紹了一種快速的超像素分割算法,傳統(tǒng)的分割算法在算法效率,計算成本,復雜度等方面均存在問題。圍繞著以上問題,進而提出了一種改進型的算法:超像素分割算法SLIC,并通過實驗測試數據性能參數比對,證明了該種算法的優(yōu)越性,且獲得了更好的品質和更高的計算效率。

關鍵詞像素;超像素;圖像分割;分割算法

A Fast Method of Superpixel Segmentation

LIU Jun

(Key Lab.of Electronic Information Countermeasure and Simulation,Xidian University,Xi’an 710071,China)

AbstractThis paper introduces a fast method of superpixel segmentation according to image segmentation algorithm in view of the fact that traditional segmentation algorithms have many problems such as the efficiency of the algorithm,computing costs and complexity.An improved algorithm,namely the superpixel segmentation (SLIC),is proposed to address these problems.Experiments and data comparison show that the proposed method offers better quality and higher computational efficiency than other state-of-the art algorithms.

Keywordspixel;superpixels;image segmentation;segmentation algorithm

超像素是利用像素與像素之間特征的相似程度對像素進行分組,從而獲取圖像的冗余信息,大幅降低了后續(xù)圖像處理任務的復雜程度。要使超像素能變得實用其必須使用速度快、操作簡單。同時,能產生高質量的分割。然而多數最先進的超像素方法均無法滿足這些要求。本文所提出的SLIC(簡單線性、迭代聚類)算法在由CIELAB色彩空間中的l,a,b值和x,y坐標像素所構成的五維空間中執(zhí)行一個局部的像素點聚合。一種新的距離度量能實現超像素形狀的緊湊、有規(guī)則,并能無縫隙地包含灰度及彩色圖像。

1SLIC算法

1.1算法原理

SLIC(簡單線性迭代聚類)是一種通過利用像素的顏色相似度和圖像片面空間對像素進行聚類,從而有效生成緊湊地幾乎統(tǒng)一化的超像素分割方法。SLIC分割方法使用簡單,給定所需得到的超像素數量即可,且運行速度快,只需線性的運行時間和存儲空間。SLIC分割方法生成的超像素具有較好的緊湊性和邊界貼合度,超像素大小一致且形狀均勻。因此,眾多基于像素的圖像處理算法采用SLIC超像素來代替像素進行運算,已產生了良好的效果。

本文的方法(SLIC)是在五維空間labxy中來實現的,其中l(wèi)ab為CIELAB色彩空間中的像素顏色矢量,被認為是小顏色距離感知統(tǒng)一,xy是像素點的位置。在CIELAB空間中兩種顏色的最大可能距離受到限制,在xy平面上空間距離取決于圖像大小。在五維空間中沒有規(guī)范化空間距離的情況下簡單使用歐幾里得距離是不可能的。為在五維空間中聚集像素點,本文引進了一種考慮超像素大小的距離測量法。使用該方法,在五維空間中執(zhí)行顏色相似度和像素點相似度以此便于所期待的群集大小及其空間范圍近似相等。

1.2距離測量

本文算法是將一系列要求近似等大超級像素點K作為輸入。由于一幅圖像有N個像素點,因此每個超級像素點近似大小為N/K個像素。對于大致相等的超級像素點將會有以每個網格間距為超級像素點的中心。

在開始算法前,以固定的網格間距S選擇超級像素點K中心和k=[1,K] 。任何一個超級像素點的空間范圍近似為S2(一個超級像素點的近似區(qū)域),由此可大膽假定在xy平面上圍繞一個族群中心的像素點是關聯(lián)在族群中心2S×2S區(qū)域內。這將成為每一個族群中心最近像素點的搜索域。

在CIELAB顏色空間的歐幾里德幾何距離用于感知有意義的最小距離。若空間像素距離超過能感知的顏色距離,其將開始超出像素顏色相似規(guī)律。因此,代替在5D空間的歐幾里德幾何距離,本文采用一種距離測量Ds,定義為

(1)

其中,k和i分別為兩個像素;Ds表示兩個像素之間的距離,是像素顏色距離和圖像平面中位置距離的加權和。變量m的引入方便控制超像素的緊湊性,變量m的值越大,對緊湊性的要求越高,族群越密集。變量值可以是1～20中的隨機數,在本文中選擇m=10作為最終結果。該種大致的方法可匹配最大的有意義感知距離經驗值,同時能較好的平衡顏色相近和空間相近。

1.3核心算法

LIC算法總結在算法1中。本文定期采樣K來開始間隔的族群中心,同時移動其到相應的種子點位置對應于3×3相鄰的區(qū)域內梯度最小的位置。這是為了避免將其放置到邊緣處和減小選擇噪聲像素點的幾率。圖像梯度計算公式如下

(2)

在圖像中的每個像素點均關聯(lián)在可以是搜索域重疊的像素點最近的族群中心。在所有像素點被關聯(lián)在最近的族群中心后,一個新的中心將計算成為屬于這一族群所有像素點的平均labxy矢量。然后再反復重復這一過程,以最近的族群中心關聯(lián)像素點和重新計算族群中心直至收斂。在這一過程結束后,少量迷失的顏色存在,這就是少量像素點在鄰近的較大分割段還有同樣的顏色,但并未與其關聯(lián)。同時,其極為稀有,可能會上升,盡管空間鄰近測量時聚集并未明確的實現連通。然而在算法的最后階段實現連通性,通過最大顏色相鄰的族群來確認不相交的分割段。算法時間復雜度為O(N),少用至少10%的時間來分割一幅圖像。

算法1高效率超像素分割。(1)以S為網格邊長,在每個網格中選取一個超像素中心,并在其該像素的3×3鄰域內選擇梯度最小的像素作為真正的區(qū)域中心;(2)對每個區(qū)域中心在其2S×2S鄰域內搜索屬于該區(qū)域的像素,將所有像素關聯(lián)到與其最近的區(qū)域中心;(3)在分割出的超像素中計算新的中心像素,并計算剩余誤差error;(4)重復步驟(2)和步驟(3),當誤差error足夠小時,超像素分割結束。

2SLIC算法復雜度分析

在分析SLIC算法復雜度之前,先分析K-means[1-3]算法的復雜度,這是一種基于樣本間相似性度量的間接聚類方法,屬于非監(jiān)督學習方法。此算法以k為參數,將n個對象分為k個簇,以使簇內具有較高的相似度,且簇間的相似度較低。相似度的計算根據一個簇中對象的平均值來進行。此算法首先隨機選擇k個對象,每個對象代表一個聚類的質心。對于其余的每個對象,根據該對象與各聚類質心之間的距離,將其分配到與之最相似的聚類中,然后計算每個聚類的新質心。重復上述過程,直到準則函數會聚。K-means算法是一種較典型的逐點修改迭代的動態(tài)聚類算法,其要點是以誤差平方和為準則函數。逐點修改類中心:一個象元樣本按某一原則,歸屬于某一組類后,就要重新計算這個組類的均值,并以新均值作為凝聚中心點進行下一次像元素聚類;逐批修改類中心:在全部象元樣本按某一組的類中心分類后,再計算修改各類的均值,作為下一次分類的凝聚中心點。

由此便可發(fā)現本文算法中所運用的迭代演變局部集群和集群中心的思想實際上是K-means的一個特例。通過使用Eq.(1)的距離計算方法優(yōu)勢,像素搜索可被集中到平面空間的區(qū)域內,這與超像素點K的數量成反比。在實際應用中,一個像素點會分布在不超過8個族群中心的局部領域內。同時,還發(fā)現在多次迭代后SLIC算法收斂誤差急劇降低。實驗測試表明,運用該算法需要4～10次迭代,而在文中所有的結果均是以10次迭代的過程得到。

經典的k均值算法時間復雜度為O(NKI),在此N為圖像像素點的數量,K是族群的數量,I是為達到收斂所需的迭代次數。由于需要計算從任意一點到不超過8個族群中心的距離外加迭代次數為恒定的,所以SLIC算法的復雜度為O(N)。因此,簡單線性迭代聚類SLIC是用于特定超像素分割問題。與K-means不同的是,其避免了一些冗余的距離計算。

3SLIC算法實驗測試性能分析

在這一部分,由實驗測試所得結果來對超像素分割方法與其他4種最為先進的分割算法進行比較,即GS04[4],NC05[5],TP09[6],QS09[7]。GS04和NC05是基于圖論的方法,而TP09和QS09是基于梯度的方法。NC05和TP09被用于產生所需的超像素點數,而GS04和QS09需要調試參數來獲得所需的超像素點數。該算法的選擇提供了一種較好的先進性代表。

圖1中提供了一種與這些算法相對的輸出視覺比較。為提供一種定性的比較,運用了細分誤差和邊界召回衡量方法。

圖1　各種分割算法比對

圖1中超像素的視覺比較,在所有圖像兩半中平均超像素點的大小約為100個像素點和300個像素點。每一對行展示了整個分割圖像與其中心部分。

圖2(a)中為低分割誤差值隨超像素點數量變化關系的圖繪。圖2(b)中為邊界召回值隨超像素點數量變化的關系。NC05的輸出視覺上是最佳的但其邊界召回較差。GS04的邊界召回比其他算法均高,部分原因在于其在對象邊界附近放置了諸多分割片。

圖2　SLIC等算法性能值隨超像素點個數變換規(guī)律對比圖

一種良好的超像素分割算法應有較低的分割誤差和較高的邊界召回。為使其作為預處理算法有作用,如此的一種分割應產生大小相等、緊湊的、數量受控的超像素?；谕瑯拥脑?該算法應有較低的計算成本,較少的輸入參數。圖2(b)中表明GS04的召回邊界最高,這是因其產生了幾個片段,與圖2(a)中的對象邊界較為接近。然而,從圖2(a)中可看出,GS04也表現出了比本文算法更高的低分割誤差。從圖2(a)中可看出,SLIC算法低分割誤差最低。同時由圖2(b)可得知,有較高的邊界召回。然而,除非執(zhí)行參數搜索,否則GS04并不會輸出所需數量指定大小的超像素點。這需要幾次的運行算法,超像素大小不等使得這種算法并不適合基于超像素的應用[8-10]。總之,本文所提出的算法的處理速度比其他先進算法快。同時,能產生與實際所需大小相等緊湊的超像素點。

4結束語

超像素分割算法作為一個預處理步驟來處理諸如對象類識別和醫(yī)學影像分割是有利的。為實現有用性,這些算法輸出的超像素點需緊湊、大小基本相等、質量高、計算開銷低。在處理50萬像素點以上的圖片中,少有算法可以達到這種要求。本文提供了一種新穎的超像素分割算法(SLIC),其復雜度為O(N),輸出的超像素點品質高,內存和計算成本較低。只需一定數量的像素點數作為輸入參數,計算成本和內存的使用成線性比例增加?？勺C明該種超像素算法在對象類識別和醫(yī)學影像分割方面的功效,與其他的先進算法相比,本文SLIC算法可獲得更好的品質和更高的計算效率。

參考文獻

[1]AnderbergM.Clusteranalysisforapplications[M].Cambridge:AcademicPress,1973.

[2]GeriSchneider,JasonPWinters.用例分析技術[M].師奈德,譯.北京:機械工業(yè)出版社,2002.

[3]GreenPE,CarmoneFJ,KimJ.Apreliminarystudystudyofoptimalvariableweightingink-meansclustering[C].Paris:Classification,1990.

[4]FelzenszwalbP,HuttenlocherD.Efficientgraph-basedimagesegmentation[J].InternationalJournalofComputerVision,2004,59(2):167-181.

[5]RenX,MalikJ.Learningaclassificationmodelforsegmentation[C].Suzhou:IEEEInternationalConferenceonComputerVision,2003.

[6]LevinshteinA,StereA,KutulakosK,etal.Turbopixels:fastsuperpixelsusinggeometricflows[J].IEEETransportationsonPAMI,2009,31(12):2290-2297.

[7]VedaldiA,SoattoS.Quickshiftandkernelmethodsformodeseeking[C].SaltLake:ComputerVision-ECCV2008,SeriesLectureNotesinComputerScience,2008.

[8]LevinshteinA,SminchisescuC,DickinsonS.Multiscalesymmetricpartdetec-tionandgrouping[C].Shanghai:IEEEInternationalConferenceonComputerVision,2009.

[9]MoriG.Guidingmodelsearchusingsegmentation[C].Tokoyo:IEEEInternationalConferenceonComputerVision,2005.

[10]FulkersonB,VedaldiA,SoattoS.Classsegmentationandobjectlocalizationwithsuperpixelneighborhoods[C].Shanghai:IEEEInternationalConferenceonComputerVision,2009.

中圖分類號TP391.41

文獻標識碼A

文章編號1007-7820(2016)03-039-03

doi:10.16180/j.cnki.issn1007-7820.2016.03.010

作者簡介:劉俊(1990—),男,碩士研究生。研究方向:圖像分割算法。

收稿日期:2015- 07- 21