劉　俊

(西安電子科技大學(xué) 電子信息攻防對(duì)抗與仿真重點(diǎn)實(shí)驗(yàn)室,陜西 西安　710071)

?

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

劉俊

(西安電子科技大學(xué) 電子信息攻防對(duì)抗與仿真重點(diǎn)實(shí)驗(yàn)室,陜西 西安710071)

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

關(guān)鍵詞像素;超像素;圖像分割;分割算法

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

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

1SLIC算法

1.1算法原理

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

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

1.2距離測(cè)量

本文算法是將一系列要求近似等大超級(jí)像素點(diǎn)K作為輸入。由于一幅圖像有N個(gè)像素點(diǎn),因此每個(gè)超級(jí)像素點(diǎn)近似大小為N/K個(gè)像素。對(duì)于大致相等的超級(jí)像素點(diǎn)將會(huì)有以每個(gè)網(wǎng)格間距為超級(jí)像素點(diǎn)的中心。

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

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

(1)

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

1.3核心算法

LIC算法總結(jié)在算法1中。本文定期采樣K來(lái)開(kāi)始間隔的族群中心,同時(shí)移動(dòng)其到相應(yīng)的種子點(diǎn)位置對(duì)應(yīng)于3×3相鄰的區(qū)域內(nèi)梯度最小的位置。這是為了避免將其放置到邊緣處和減小選擇噪聲像素點(diǎn)的幾率。圖像梯度計(jì)算公式如下

(2)

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

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

2SLIC算法復(fù)雜度分析

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

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

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

3SLIC算法實(shí)驗(yàn)測(cè)試性能分析

在這一部分,由實(shí)驗(yàn)測(cè)試所得結(jié)果來(lái)對(duì)超像素分割方法與其他4種最為先進(jìn)的分割算法進(jìn)行比較,即GS04[4],NC05[5],TP09[6],QS09[7]。GS04和NC05是基于圖論的方法,而TP09和QS09是基于梯度的方法。NC05和TP09被用于產(chǎn)生所需的超像素點(diǎn)數(shù),而GS04和QS09需要調(diào)試參數(shù)來(lái)獲得所需的超像素點(diǎn)數(shù)。該算法的選擇提供了一種較好的先進(jìn)性代表。

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

圖1　各種分割算法比對(duì)

圖1中超像素的視覺(jué)比較,在所有圖像兩半中平均超像素點(diǎn)的大小約為100個(gè)像素點(diǎn)和300個(gè)像素點(diǎn)。每一對(duì)行展示了整個(gè)分割圖像與其中心部分。

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

圖2　SLIC等算法性能值隨超像素點(diǎn)個(gè)數(shù)變換規(guī)律對(duì)比圖

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

[2]GeriSchneider,JasonPWinters.用例分析技術(shù)[M].師奈德,譯.北京:機(jī)械工業(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.

中圖分類號(hào)TP391.41

文獻(xiàn)標(biāo)識(shí)碼A

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

doi:10.16180/j.cnki.issn1007-7820.2016.03.010

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

收稿日期:2015- 07- 21