侯向丹 李柏岑 劉洪普 杜佳卓 鄭夢敬 于鐵忠

超像素算法產(chǎn)生的結(jié)果可以大幅提高后續(xù)圖像處理的運算速度[1],因而被廣泛地應(yīng)用于交互式圖像分割[2]、圖像去霧[3]、顯著性檢測[4]、目標跟蹤[5?6]、目標分類[7]、3維重建[8]、室內(nèi)場景理解[9]以及卷積神經(jīng)網(wǎng)絡(luò)[10]等領(lǐng)域.

目前超像素算法主要分為兩大類:第一類是基于圖論(Graph-based)的;第二類是基于聚類(Clustering-based)的.基于圖論的超像素分割算法,通過求圖的最小割來實現(xiàn)超像素分割.比較有代表性的算法包括歸一化割(Normalized cut,NC)[11]、 Superpixel lattices(SL)[12]、 GCa 和GCb[13]、基于熵率的超像素分割(Entropy rate superpixel segmentation,ERS)[14]、SEEDS[15]、Lazy random walk(LRW)[16]、Fuzzy entropy maximization[17?18]、Superpixel hierarchy[19]等.基于聚類的超像素分割方法,是指把多個像素點進行聚類或迭代聚類直到滿足特定條件.近些年比較有代表性的包括:TurboPixel[20]、VCells[21]、Simple linear iterative clustering(SLIC)[22]、Simple non-iterative clustering(SNIC)[23]、DBSCAN superpixel segmentation[24]、Linear spectral clustering superpixel(LSC)[25]、Watershed superpixel(SCoW)[26]等,其中SLIC相較于其他算法,由于其簡單易懂、速度快、分割結(jié)果良好、參數(shù)簡單等原因,而廣受關(guān)注.

近年來,有關(guān)學者針對SLIC在不同方面的改進包括:無參數(shù)化設(shè)計[22,27],增加圖像預(yù)處理[28],改進分割過程[29?31]以及改進融合條件[28]等.

使用無參數(shù)化設(shè)計,可以減少參數(shù)的輸入,但是難以保證分割的準確度,尤其是對邊緣的貼合程度;增加圖像預(yù)處理,會使清晰的邊緣更清晰,但也會使模糊的邊緣更模糊;通過改進融合條件,可以使孤立的超像素塊更準確地融合于相鄰的超像素塊中,但不會對主要分割結(jié)果產(chǎn)生影響.

分割過程是SLIC算法的核心部分,對分割結(jié)果有著重要影響.Liu等[29?30]的方法,對于色彩變化較大和面積較小的區(qū)域分割效果較好,但是對于弱邊緣區(qū)域的分割效果依然欠佳;南柄飛等[31]的方法融合了紋理特征,但是處理一幅圖像平均需要1.4min,并且在欠分割錯誤率上有著較為明顯的不足.

為了更好地提取紋理特征,需要一種更為快速和準確的算法.而LBP算法計算速度快、效果好,同時具有灰度不變性以及旋轉(zhuǎn)不變性等特點[32],所以廣泛應(yīng)用于圖像紋理提取上.

在LBP算法的改進中,雖然文獻[33?34]提出的方法會增強LBP算法對原圖中噪聲的魯棒性,但是其得到的紋理特征均會產(chǎn)生“紋理偏移”以及紋理噪聲.針對這些問題,本文提出一種新的LBP算法來提取紋理特征,解決了“紋理偏移”問題并減弱了紋理噪聲的影響,然后在SLIC的距離公式中加入紋理距離,使其對于紋理有更好的相應(yīng).

在實驗中,本文分別選取ERS、SEEDS、LRW、TurboPixel、SLIC、SNIC、LSC 和SCoW 這8種具有代表性的算法進行實驗對比.為驗證分割效果,本文選取紋理較多的醫(yī)學圖像進行實驗,圖像數(shù)據(jù)采用選擇了由Alexander Andreopoulos和John K.Tsotsos建立的心臟MRI數(shù)據(jù)集[35].經(jīng)實驗證明,本算法可以更好地突出不同區(qū)域之間的變化,適用于醫(yī)學圖像以及紋理較復(fù)雜的圖像的分割.

1 基于紋理的SLICT算法

1.1 傳統(tǒng)的SLIC算法

SLIC由Achanta等[22]于2010年提出,利用圖像顏色相似度和空間距離關(guān)系進行迭代聚類.假設(shè)在圖像中有個N像素點,預(yù)計產(chǎn)生K個超像素,則每個超像素的預(yù)計邊長為,然后在中心點2S×2S的區(qū)域內(nèi)進行k-means迭代聚類,直至達到最大迭代次數(shù).

聚類中計算某點與中心點的距離D的公式如下:

其中

其中,li、ai、bi為點i在Lab色彩空間下的值,xi、yi為點i在圖像中的空間位置.m是衡量空間信息和色彩信息的比重,m越小時,則對色彩變化越敏感同時超像素塊會越不整齊.一般來說,m取5～40時會比較有效.此外,對于灰度圖像而言,可以使用如下公式代替式(2):

其中,gi與gj分別為點i與點j的灰度值.

1.2 LBP旋轉(zhuǎn)不變統(tǒng)一模式

LBP是一種灰度范圍內(nèi)的紋理度量,由Ojala等[36]提出.設(shè)點c是圖G不在其上下左右4條邊上的某一個點,gc是c的灰度值,p點是在c點P鄰域(本文采用的是八鄰域)內(nèi)的一個點,R是P鄰域的半徑,則該點c的LBP值計算公式如下:

其中

LBP的旋轉(zhuǎn)不變模式[32]是指:不斷改變訪問中心點P鄰域的順序,得到一組值,取其最小值作為該中心點的LBP值.每個點的旋轉(zhuǎn)不變模式的公式如下:其中,ROR(x,i)為旋轉(zhuǎn)函數(shù),表示將x轉(zhuǎn)化為二進制數(shù)后,循環(huán)右移i(i

統(tǒng)一模式是指,某點LBP二進制值的跳變(Spatial transaction)小于等于2的模式.該點對應(yīng)的跳變計算公式如下:

跳變大于2的模式,稱為非統(tǒng)一模式(Nonuniform pattern)或混合模式.跳變小于等于2的旋轉(zhuǎn)不變模式稱為旋轉(zhuǎn)不變統(tǒng)一模式[37](Rotation invariant uniform pattern,RIU).

1.3 SLICT算法流程

為了解決傳統(tǒng)的SLIC算法對于紋理不敏感以及傳統(tǒng)LBP算法會造成紋理偏移的問題,本文通過改進LBP算法并與SLIC算法結(jié)合提出了一種結(jié)合無紋理偏移的紋理特征的超像素分割算法—SLICT,該算法的流程如下所示.

SLICT算法流程.

輸入.1)圖像G;2)預(yù)分割超像素塊數(shù)K;3)空間距離權(quán)重m以及紋理距離權(quán)重L.

輸出.與原圖同樣大小的標號圖,同一個標號組成的連通域?qū)?yīng)相應(yīng)位置的超像素塊.

步驟1.提取原圖對應(yīng)的紋理特征:

1)求灰度變化方差圖,并利用該方差圖求每個點對應(yīng)的thresh(方法見第1.3.1節(jié));

2)利用1)中的thresh計算無紋理偏移的LBP模式(方法見第1.3.2節(jié));

3)利用無紋理偏移的LBP模式計算圖G的紋理特征Map(方法見第1.3.3節(jié)).

步驟2.初始化聚類中心:將圖像分為K個邊長為S的規(guī)則網(wǎng)格,并將每個格子中心點的橫縱坐標、對應(yīng)位置的Lab顏色以及紋理特征的值作為初始聚類中心,即Ck=[lk,ak,bk,xk,yk,Mapk]T,k=1,2,···,K.

步驟3.調(diào)整聚類中心:移動每一個聚類中心至該中心的八鄰域內(nèi)顏色梯度值(見式(9))最小的點.

步驟4.初始化距離和標簽:初始化每個點的標簽labels(i)=?1,初始化每個點與聚類中心的距離為d(i)=∞.

步驟5.k-means迭代聚類:對于每個聚類中心Ck和其周圍的2S×2S鄰域內(nèi)所有的像素點i,計算Ck與i之間的距離D0;如果D0

步驟6.重復(fù)步驟5,直到達到最大迭代上限

步驟7.超像素融合:將面積過小的超像素塊融入其附近的超像素塊之中.

在步驟3中對于不處于圖G上下左右4個邊上的任意一點c的梯度公式如下,其余值以0補齊:

其中,xc和yc分別是點c的橫縱坐標.步驟3中調(diào)整聚類中心的目的是為了避免初始聚類中心落在邊緣點上,從而影響聚類結(jié)果.

在步驟5中的任意兩點i、j之間的距離公式如下:

其中

若xi、yi分別是點i的橫縱坐標,則Map(xi,yi)=Map(i).dlbp是通過紋理特征計算出的紋理距離,L用于調(diào)節(jié)紋理距離所占比重,L越大,對于紋理越敏感.實驗表明,L的取值為10～50時效果會比較好.

1.3.1 計算thresh

在文獻[33?34]中提到了兩種對LBP的改進方法,但是這兩種方法并不能很好地處理一些由于光照或是成像等原因引起的紋理噪聲.為了減少這些噪聲所帶來的影響,并突出不同區(qū)域之間的差異,可以在計算式(6)中的時加入一個閾值thresh來達到此目的,即:

thresh是衡量中心點P鄰域內(nèi)灰度變化強烈程度的數(shù)值,所以需要先求得原圖對應(yīng)的灰度變化標準差圖,對于不處于圖G上下左右4個邊上的任意一點c的P鄰域內(nèi)灰度變化標準差為:

其中

則點c對應(yīng)的thresh計算公式如下:

當thresh=0時,基本等同于傳統(tǒng)LBP旋轉(zhuǎn)不變統(tǒng)一模式.此外,這種s(x)計算方法,雖然可以減少紋理噪聲但是依然會引起紋理偏移,下文中稱使用此s(x)計算的SLICT為SLICT紋理偏移.

1.3.2 計算無紋理偏移的LBP模式

通過式(12)計算出的LBP模式會存在紋理偏移.LBP紋理偏移指的是使用傳統(tǒng)LBP計算公式時會使處于邊緣兩側(cè)的像素點屬于不同的LBP模式.這種情況,會使結(jié)果所表達的紋理與原圖不能完全重合.為了避免這種情況并減少紋理噪聲所帶來的影響,需要對式(12)中的s1(x)進行如下改進:

則對于不處于圖G上下左右4個邊上的任意一點c其無紋理偏移的LBP旋轉(zhuǎn)不變統(tǒng)一模式為:

其結(jié)果范圍為[0,P+1],共計產(chǎn)生P+2類模式,其中第一類到第P+1類分別是在鄰域內(nèi)有多少個點與中心點相比,其灰度值的變化大于thresh,最后一類代表非統(tǒng)一模式.

為進一步說明紋理偏移的影響,使用不同的s(x)公式計算LBP模式圖，結(jié)果如圖1所示.

圖1中(a)是一張圖像的灰度圖,圖1(b)～(d)分別是利用式(6)、(12)、(16)計算出的旋轉(zhuǎn)不變統(tǒng)一模式圖,即可以看出圖1中(b)與(c)沒能很好地覆蓋邊緣兩側(cè),具體實例分析見第3.2節(jié).

1.3.3 提取紋理特征

使用某模式對應(yīng)點的P鄰域內(nèi)的灰度變化方差之和來代替某模式包含點的數(shù)量,這樣可以更好地描述紋理特征[34].但是為了減少明顯邊緣和弱邊緣之間的差別進而突出弱邊緣的紋理特征,本文使用某模式對應(yīng)點的P鄰域內(nèi)的灰度變化標準差之和來代替某模式包含點的數(shù)量.其中某點c的P鄰域內(nèi)的灰度變化標準差varP,R(c)的計算方法見式(13).

而varP,R(c)對于圖像噪聲、顏色變化過大的邊緣區(qū)域或紋理復(fù)雜區(qū)域的浮動過大,從而造成在計算LBP各模式的比例時(式(19))容易出現(xiàn)比例失衡的情況,所以為進一步突出弱邊緣的紋理特征,對varP,R(c)進行極值抑制.方法是:使用最大類間方差法[38]找到合適的閾值Press把varP,R(c)分成兩類,將大于Press的部分置為Press,其公式為:

圖1 LBP算法中有無紋理偏移的效果對比Fig.1 The results of LBP algorithm with and without texture deviation

然后利用所有像素點的varP,R0值,計算各模式所占的比例LBPWeight(k),即:

其中

其中,sum(·)表示計算集合內(nèi)所有元素的個數(shù),k代表模式的種類.

之后對LBPWeight(k)進行歸一化,即:

則對于不處于圖G上下左右4個邊上的任意一點c,其對應(yīng)的紋理特征Map(c)為:

其余的點對應(yīng)的紋理特征值以0補齊.

1.3.4 進行圖像分割

按照SLICT算法流程中步驟5和步驟6的步驟進行迭代聚類,然后使用文獻[22]中的方法,消除面積過小的超像素塊,得到最終的分割結(jié)果.此外,以上流程是針對灰度圖像而言.如果需要分割圖像是彩色圖像,需要將其轉(zhuǎn)化為灰度圖像,并利用此圖像計算dlbp.

2 評價指標

為了驗證SLICT的有效性,本文采用了邊緣召回率、欠分割錯誤率、覆蓋率以及運行時間這4種評價指標進行驗證,其中前三項的定義和計算方法分別是:

1)邊緣召回率(Boundary recall)

邊緣召回率描述超像素邊緣與人工標記邊緣的貼合程度,值越大說明貼合度越好.定義是:人工標記邊緣中位于超像素邊緣至多兩個像素距離內(nèi)的部分占總標記邊緣的比例.

2)欠分割錯誤率(Under-segmentation)

欠分割錯誤率是一個從超像素塊外部來衡量分割效果的指標,表示人工標記區(qū)域所在的所有超像素塊有多少“溢出”了人工標記的范圍.設(shè)共分割出K個超像素塊,某個超像素塊為sj,人工分割區(qū)域為M,|·|表示該區(qū)域的面積,α為欠分割錯誤率參數(shù),其取值一般為sj面積的5%,則其公式計算如下:

3)覆蓋率(Coverage rate)

覆蓋率是在只有一個人工標記區(qū)域的情況下,最大可達分割率(Achievable segmentation accuracy)[30]的簡化計算方法,值越大,則說明對人工標記區(qū)域的分割越完整.計算公式如下:

3 實驗結(jié)果分析

為了更好地驗證本算法的有效性和時效性,將SLICT、SLICT紋理偏移以及上文提到的8種超像素算法應(yīng)用于紋理較為復(fù)雜的醫(yī)學圖像之中,分析各自的運行效果,并在這部分詳細分析紋理偏移現(xiàn)象對分割結(jié)果和所求紋理特征的影響.

3.1 SLICT在醫(yī)學圖像中實驗及結(jié)果分析

由于醫(yī)學圖像中存在著多種不同類型的紋理且各種紋理比較復(fù)雜,所以為了更好地驗證本算法的準確性和魯棒性,將上述的10種算法應(yīng)用于醫(yī)學圖像中的心臟MRI圖像上,其部分結(jié)果如圖2所示.

圖2中第1行和第3行是本文提出的SLICT算法以及其他超像素算法應(yīng)用于7980張MRI數(shù)據(jù)庫中的部分實驗結(jié)果截圖,第2行和第4行分別是第1行和第3行心臟區(qū)域的放大結(jié)果.這部分使用的實驗參數(shù)為m=5,L=30,預(yù)計分割超像素塊數(shù)為600.可以看到,SLICT對于邊緣以及弱邊緣(如心臟上的較暗區(qū)域的邊緣和圖像兩側(cè)灰度值為0的區(qū)域的邊緣)的響應(yīng)是最好的,其次是SLIC、SLICT紋理偏移、SEEDS、SNIC以及LSC.

在規(guī)整度上,TurboPixel以及LSC的圖像是最規(guī)整的;ERS最零亂,即使對于灰度值為零的圖像左右兩側(cè)區(qū)域,生成的超像素塊依然很零亂;此外為保證LRW 的時效性,在進行超像素分割時將圖像縮小至原圖像的1/4,故而其分割結(jié)果在原圖上呈現(xiàn)時顯得較為整齊,但是其超像素塊在紋理較少的區(qū)域分布并不均勻.從實驗結(jié)果上看,基于圖論的算法ERS、LRW 與SEEDS產(chǎn)生的超像素塊結(jié)果均不整齊,而其余基于聚類的超像素算法產(chǎn)生的超像素塊則普遍整齊很多.

為進一步驗證算法的優(yōu)劣,在圖3中給出了各算法在心臟MRI數(shù)據(jù)庫中有人工標記的5011幅圖像上的運行結(jié)果,并計算和記錄了上述提到的4種評價指標.

從圖3中可以看出,本文提出的方法的分割效果在總體上優(yōu)于其余算法.在邊緣召回率上,SLICT與LSC相差不多,略優(yōu)于SLICT紋理偏移;而這三種算法均明顯優(yōu)于其余算法;TurboPixel因為其分割結(jié)果更傾向于貼合種子節(jié)點附近的網(wǎng)格而非貼合目標區(qū)域邊緣,所以有著較為明顯的不足;除卻SCoW、TurboPixel以及LRW以外的7種算法對應(yīng)的邊緣召回率,在預(yù)計分割數(shù)量達到1000時,幾乎都達到了99%以上.此外,因為圖像本身分辨率較低,而且人工標記區(qū)域面積較小,所以此值會比常用的自然光數(shù)據(jù)庫(如BSDS500)上要大一些;由于同樣的原因,在欠分割錯誤率上,結(jié)果也會大一些.

圖2 心臟MRI分割結(jié)果Fig.2 The results of superpixel algorithms on MRI images

在欠分割錯誤率上,SLICT效果最好,優(yōu)于SLICT紋理偏移,其次是ERS與LSC;而LRW與SEEDS在此表現(xiàn)相對較弱.因為ERS所分割出的超像素塊不規(guī)則以及對于紋理較少的區(qū)域靈敏度較差,造成在人工標記區(qū)域周圍的超像素塊面積較小,所以其在此方面表現(xiàn)稍好.同時在實驗中發(fā)現(xiàn),由于人體器官形狀以及MRI成像原理的復(fù)雜性,人工標記區(qū)域往往會比較貼合器官的實際形狀而非圖像上表現(xiàn)出的形狀,所以在欠分割錯誤率上,以上所有算法在不同圖像上均表現(xiàn)出較大的波動.

在覆蓋率上,SLICT優(yōu)于SLICT紋理偏移,而ERS在邊緣區(qū)域會分割出更多小塊的超像素,但是對于紋理的相應(yīng)程度仍不及本文提出的算法,位列第三;值得注意的是,SEEDS算法在這一點上表現(xiàn)出了較大的波動.其他8種算法只考慮了色彩以及空間信息,而且MRI圖像會有弱邊緣以及模糊區(qū)域,從而造成對弱邊緣區(qū)域不敏感,在最終的分割結(jié)果表現(xiàn)上,則是將更多邊緣不明顯的心臟區(qū)域與部分心包膜分在一個超像素塊中.

在運行時間上,SLIC、SLICT、SNIC、SEEDS、LSC、SCoW 與TurboPixel的時間復(fù)雜度均為O(N)[15,20,22?23,25?26],而ERS的平均時間復(fù)雜度為O(NlogN),最大時間復(fù)雜度為O(N2logN)[14],LRW的時間復(fù)雜度為O(itr·N2),其中itr代表最大迭代次數(shù)[16].從結(jié)果上看,速度最快的是SCoW與SEEDS,平均處理一幅圖像不到0.05s;SLICT平均處理一幅圖像需要0.15～0.2s左右,能夠滿足實際需求;TurboPixel的運行時間明顯慢于同數(shù)量級的其他方法,這一點與文獻[22]中的描述匹配;LRW的運行時間會隨著超像素塊數(shù)的增多而出現(xiàn)線性的增長,這一點很難滿足實際的需求.

圖3 心臟MRI數(shù)據(jù)庫運行結(jié)果Fig.3 Expriment data on MRI dataset

3.2 紋理偏移影響分析

為進一步說明紋理偏移在提取紋理特征上的影響,在圖4(b)和(c)中分別展示了使用s1(x)與s2(x)的結(jié)果圖,其中某點c的顏色越亮,表示該點的紋理特征的值(即Map(c))越大.

可以看出,后者紋理噪聲較少,邊緣更加完整連續(xù)平滑,不同區(qū)域間的對比更大,相同區(qū)域間的連續(xù)性更強、變化性更小,對于弱邊緣和紋理的表達更加清晰.這一點也可以從具體的數(shù)據(jù)上看出來,由于式(12)對紋理的描述存在偏移,整體上弱于SLICT;但是偏移量只有一個像素,所以在整體上也優(yōu)于其余算法.

4 總結(jié)

本文通過改進傳統(tǒng)LBP旋轉(zhuǎn)不變模式的計算方法,來提取圖像對應(yīng)的紋理特征,并將其與SLIC算法融合,提出了一種對于紋理更加敏感的超像素分割算法—SLICT.將SLICT應(yīng)用于心臟MRI數(shù)據(jù)庫中的圖像,其結(jié)果表明SLICT具有更好的準確性以及魯棒性,對弱邊緣以及細小的紋理有著更為優(yōu)秀地響應(yīng).從數(shù)據(jù)上看,SLICT在欠分割錯誤率以及覆蓋率上優(yōu)于其余算法,在邊緣召回率上與LSC并列第一,在運行時間上平均只需要0.15s～0.2s,可以滿足圖像分割和處理的需求.同時驗證了使用傳統(tǒng)的LBP計算紋理特征時會導(dǎo)致“紋理偏移”,使得其求得的紋理特征不能很好地描述邊緣并且存在一定的紋理噪聲,從而影響分割結(jié)果.

此外,在實驗中發(fā)現(xiàn),醫(yī)學圖像中器官存在的弱邊緣和模糊區(qū)域,會導(dǎo)致呈現(xiàn)出的形狀與實際形狀有著一定差異.本文提出的SLICT可以很好地檢測出這些差異部分,并能夠產(chǎn)生更為準確的分割結(jié)果,對后續(xù)醫(yī)學圖像處理的相關(guān)研究有著重要的參考價值和影響.

圖4 紋理特征圖Fig.4 Texutre feature