杜 煒,馬 春，汪 慶，耿英保

安徽中醫(yī)藥大學(xué)醫(yī)藥信息工程學(xué)院，安徽合肥，230012

超像素分割算法是許多計(jì)算機(jī)視覺應(yīng)用中的重要模塊，比如目標(biāo)識(shí)別[1]，圖像分割[2]，以及單視圖的3D重建等[3-4]。目前流行的基于圖論的超像素分割算法，分別是由Felzenszwalb等提出的FH方法[5]，Comaniciu提出的均值漂移和分水嶺算法[6]。FH和分水嶺算法運(yùn)算速度極快；均值漂移對局部變量很有效；但是這三種方法產(chǎn)生的超像素具有不規(guī)則的尺寸和形狀[7]。Ren等[7]建議使用Normalized Cut(NCut)算法來進(jìn)行超像素分割。Ncut算法可以產(chǎn)生大小相似和形狀緊湊的超像素，但它的計(jì)算開銷過大，分割一幅481×321的圖像需要幾分鐘。Veksler等[8]將超像素分割描述為圖割問題。文獻(xiàn)[9]采用不同方法生成了漂亮的棋盤花紋圖像，但都是通過犧牲精細(xì)的圖像細(xì)節(jié)來追求平滑的邊界。然而在圖像分割時(shí)需要規(guī)范集群的大小，避免過度平滑的問題。

本文將超像素分割作為聚類問題來處理，提出一種新的聚類目標(biāo)函數(shù)，包含圖上隨機(jī)游走熵率和平衡函數(shù)兩項(xiàng)內(nèi)容。其中熵率有助于形成緊密均勻的聚類，鼓勵(lì)在感知邊界上劃分圖像，有利于超像素僅與一個(gè)對象重疊；而平衡函數(shù)使得聚類的簇具有相似大小，減少不平衡超像素的數(shù)量。除此之外，通過聚類公式推導(dǎo)出一種有效的算法，證明了可以通過目標(biāo)函數(shù)求解優(yōu)化問題，目標(biāo)函數(shù)是一個(gè)單調(diào)遞增的子模函數(shù)，子模性是連續(xù)域上離散的凸性。子模函數(shù)最大化通常是NP-hard問題，本文通過貪婪算法并利用擬陣結(jié)構(gòu)，在解的最優(yōu)性上，得到較好的效果。近來，在傳感器布置[10]和疫情檢測中[11]，都采用了子模函數(shù)最大化的方法。

1 基本知識(shí)

定義1X={Xt|t∈T,Xt∈V}在圖G=(V,E)上隨機(jī)游走，用非負(fù)相似度測量權(quán)函數(shù)w，圖上隨機(jī)游走模型的轉(zhuǎn)移概率定義為：

pi,j=Pr(Xt+1=vj|Xt=vi)=wi,j/wi

(1)

其中wi=∑k:ei,k∈Ewi,k是頂點(diǎn)vi的關(guān)聯(lián)權(quán)值之和，靜態(tài)分布如式(2)所示。

(2)

(3)

定義2令E為有限集。如果集合函數(shù)F滿足

F(A∪{a1})-F(A)≥F(A∪{a1,a2})-F(A∪{a2})

(4)

且所有A?E,a1,a2∈E,a1,a2?A，那么2E→R是子模塊。此屬性也稱為遞減的返回屬性，表示在以后的階段中使用模塊的影響較小。

定義3對于一個(gè)集合函數(shù)F，如果對于所有A1?A2滿足F(A1)≤F(A2),則F為單調(diào)遞增集合函數(shù)。

定義4一個(gè)集合E的子集I滿足以下三個(gè)條件：(1)?∈I,(2)I∈I且I′?I，那么I′∈I，(3)若I1和I2屬于集合，且|I1|<|I2|，然后有一個(gè)屬于I1-I2的元素e，這樣I1∪e∈I。則稱由有限集E組成的有序?qū)=(E,I) 為擬陣。

2 問題描述

用圖的分割方法來解決聚類問題，首先尋找一個(gè)有K個(gè)連通子圖的拓?fù)浣Y(jié)構(gòu)，再將所提出的目標(biāo)函數(shù)最大化，最終將圖像分割成K個(gè)超像素塊。如果一個(gè)邊ei,j在聚類形成中未被選擇，它的權(quán)重會(huì)被重新分配到兩個(gè)頂點(diǎn)。使用高斯核函數(shù)將每條邊旁邊的數(shù)字即距離轉(zhuǎn)換為相似度。每一個(gè)聚類輸出都包含了不同的互相連通的集群，見圖1。

圖1 熵率的作用

圖1中，(a)的密集聚類的熵值比(b)中密集度較低的聚類的熵值更高。(c)中均勻聚類的熵值比(d)中不均勻聚類的熵值更高。

2.1 構(gòu) 圖

將一幅圖片映射到圖G=(V,E)上，節(jié)點(diǎn)表示像素，用邊的權(quán)值表示成對節(jié)點(diǎn)的相似性，并采用相似矩陣的形式表示。選擇一條邊A?E的子集，得到圖G=(V,E)，且G包含了K個(gè)連通的子圖。

2.2 熵 率

利用所構(gòu)圖上的隨機(jī)游走熵率作為判別條件，得到了緊密均勻的聚類，使得圖上隨機(jī)游走公式(2)的靜態(tài)分布保持不變。公式(5)給出了轉(zhuǎn)換概率K的集合函數(shù):

(5)

因此，在G=(V,E)上隨機(jī)游走的熵率可以表示為一個(gè)集合函數(shù)：

(6)

如圖1所示，盡管在集合A中包含任何邊都會(huì)增加熵率值，但當(dāng)選擇形成緊密均勻聚類的邊時(shí)，熵率值的增加會(huì)更大。在提出的圖結(jié)構(gòu)中，圖上隨機(jī)游走的熵率H:2E→R是一個(gè)單調(diào)遞增的子模函數(shù)，可知熵率是單調(diào)遞增的。在后面的階段中，隨著有更多邊緣可以共享，那么只選擇一條邊帶來的不確定性增幅就會(huì)降低，最終導(dǎo)致返回特性的遞減。

2.3 平衡函數(shù)

利用平衡函數(shù)來使聚類具有相似大小。令A(yù)為選定的邊集合，NA為聚類的數(shù)量，ZA是聚類的分布。例如，對于圖像分割邊界集合A，令SA={S1,S2,…SNA}。則ZA的分布表示為：

(7)

且平衡項(xiàng)表示為：

(8)

熵H(ZA)有助于使聚類具有相似大??；NA使得聚類的數(shù)量盡可能少。對于固定數(shù)量的聚類，首選采用更加平衡的分割方法。與熵率相似，平衡函數(shù)也是一個(gè)單調(diào)遞增和子模塊函數(shù)。所以在提出的圖結(jié)構(gòu)中，平衡函數(shù)B:2E→R是一個(gè)單調(diào)遞增的子模塊函數(shù)。目標(biāo)函數(shù)結(jié)合了熵率和平衡函數(shù)，從而使得聚類更加緊密、均勻和平衡。聚類是通過優(yōu)化相關(guān)邊緣集合的目標(biāo)函數(shù)來實(shí)現(xiàn)的：

(9)

λ≥0，且為平衡項(xiàng)的權(quán)重。非負(fù)系數(shù)線性組合保持了子模性和單調(diào)性[12]。因此目標(biāo)函數(shù)也是子模單調(diào)遞增的。由于目標(biāo)函數(shù)是單調(diào)遞增的，因此對連接子圖數(shù)量的約束恰好強(qiáng)制為K個(gè)簇。

3 優(yōu)化方法

針對上述的目標(biāo)函數(shù)(9)，提出了一種貪婪優(yōu)化方案，采用對次模函數(shù)最大化進(jìn)行優(yōu)化的方法，并分析其最優(yōu)性和復(fù)雜性。

3.1 高效率貪婪算法

子模函數(shù)最大化的標(biāo)準(zhǔn)方法通常采用的是貪婪算法[12]。該算法從一個(gè)空集開始(一個(gè)完全不連通圖,A=?),按順序?qū)⑦吿砑拥郊现?。每次迭代時(shí)，將產(chǎn)生最優(yōu)增益的邊添加到集合中，當(dāng)連通子圖的數(shù)量達(dá)到預(yù)定值時(shí)停止迭代。

為了實(shí)現(xiàn)算法的加速，在邊緣集A上附加一個(gè)約束，使它不能含有環(huán)。此約束會(huì)忽略連接子圖中的其他邊，從而減少了貪婪搜索中的迭代次數(shù)，這些忽略的附加邊不會(huì)改變圖的分割。與原來的問題相比，盡管這個(gè)約束導(dǎo)致了更小的解空間(只允許樹狀結(jié)構(gòu)子圖)，但實(shí)際上聚類的效果差別不大。根據(jù)無環(huán)約束和聚類個(gè)數(shù)NA≥K的約束，產(chǎn)生一個(gè)獨(dú)立的集合定義，它包含了一個(gè)擬陣M=(E,I)，定義如下所述：令E為邊緣集合，I為子集A的集合，A?E,且A滿足如下條件：(1)A滿足無環(huán)設(shè)置；(2)構(gòu)成A的連通子圖個(gè)數(shù)大于或等于K。算法流程如圖2。

圖2 高效率貪婪算法流程圖

3.2 算法的有效實(shí)現(xiàn)

在每一次迭代中，貪婪算法在滿足擬陣約束的條件下選擇目標(biāo)函數(shù)中增益最大的邊。如圖2中所述，該算法執(zhí)行O(|E|)次循環(huán)將新的邊添加到A中。在每次循環(huán)中，通過遍歷邊緣列表，找到增益最大的邊，所以該算法的復(fù)雜度為O(|E|2)。

最初先計(jì)算將每個(gè)邊添加到A的增益并構(gòu)造一個(gè)最大堆結(jié)構(gòu)。在每次迭代中，對具有最大增益的邊進(jìn)行出堆操作，并添加到A中。這些新添加的邊會(huì)影響堆中其余邊緣的增益，此時(shí)再利用子模函數(shù)的性質(zhì)對堆結(jié)構(gòu)進(jìn)行有效更新。子模函數(shù)具有邊界收益遞減的性質(zhì)，也就是每一條邊的增益不會(huì)增加只有減少。因此，保持一個(gè)堆結(jié)構(gòu)只需更新頂部增益較大的元素，而不必更新其他元素，由于堆的頂部元素已更新，則其他元素的值只能減少，因此頂部元素為最大值。

盡管此算法在最壞情況下的復(fù)雜度是O(|V|2log|V|)，但實(shí)際上由于每次迭代時(shí)對堆執(zhí)行的更新很少，因此平均來看，算法的復(fù)雜度近似為O(|V|log|V|)，運(yùn)行速度比樸素的實(shí)現(xiàn)算法快很多。在實(shí)驗(yàn)中，該算法在對大小為481×321的圖像進(jìn)行分割時(shí)，速度提高了50%，平均運(yùn)行時(shí)間0.98秒。

4 實(shí)驗(yàn)和結(jié)果

超像素分割與目標(biāo)分割的目標(biāo)不同，因此性能指標(biāo)也有所不同。本文使用三個(gè)常用的標(biāo)準(zhǔn)指標(biāo)來評估超像素的質(zhì)量：欠分割誤差,邊界回溯和可達(dá)分割精度[13]。使用G={G1,G2,…GnG}來表示一個(gè)具有nG段正確標(biāo)注(GT)圖像的集合，|Gi|表示段的大小。

欠分割誤差率(UE) 測量超過GT圖像邊緣像素丟失的量。它根據(jù)超像素只能與一個(gè)對象重疊的要求來評估分割質(zhì)量。這里采用Veksler等人使用的欠分割誤差度量[8]，公式如下：

(10)

對于每一個(gè)GT圖像段Gi，可以發(fā)現(xiàn)重疊的超像素，并計(jì)算出的像素丟失的大小，然后將丟失像素與所有的片段相加，并通過圖像大小∑i|Gi|使其標(biāo)準(zhǔn)化。

邊界回溯率(BR) 測量由超像素邊界恢復(fù)的自然邊界的百分比。BR的計(jì)算如(11)所示：

(11)

可達(dá)分割精度(ASA)是性能上限的度量方法。對于以超像素為單位的圖像分割，它可提供最高的精度。為了計(jì)算ASA，使用重疊度最大的GT圖像片段的標(biāo)簽來標(biāo)記每個(gè)超像素。這些可以正確標(biāo)記的像素的片段就是可達(dá)分割精度，如式(12)所示：

(12)

這些性能指標(biāo)根據(jù)圖像中的超像素?cái)?shù)量來繪制，使用的超像素?cái)?shù)量少而產(chǎn)生的性能更好的算法為更優(yōu)的算法。

實(shí)驗(yàn)均在酷睿i7處理器上運(yùn)行，2.4 hz，8 G內(nèi)存，其中實(shí)驗(yàn)1、2在Berkeley分割數(shù)據(jù)集與基準(zhǔn)中進(jìn)行，該基準(zhǔn)包含300張帶有標(biāo)記的GT圖像，實(shí)驗(yàn)3對真實(shí)自然環(huán)境下未標(biāo)記的葉片圖像進(jìn)行超像素分割。

實(shí)驗(yàn)1選擇兩幅圖像進(jìn)行超像素分割實(shí)驗(yàn)驗(yàn)證。分別將兩幅圖像分割成128個(gè)超像素，圖3對分割結(jié)果進(jìn)行了直觀的評價(jià)。為了更直觀的可視化實(shí)驗(yàn)結(jié)果，將GT圖像分割段用彩色編碼并混合在圖像上，將算法恢復(fù)的超像素邊界用綠色疊加。一般情況很難注意到像素的丟失，并且超像素分割通常將圖像劃分為大小相似的區(qū)域，這對于基于區(qū)域的特征描述非常重要。采用隨機(jī)顏色對超像進(jìn)行區(qū)域填充，最后計(jì)算并繪制出超像素大小直方圖。

圖3 超像素圖像分割實(shí)例

實(shí)驗(yàn)2計(jì)算Berkeley數(shù)據(jù)集中所有300張灰度圖像分割指標(biāo)的平均值，將文中提出的優(yōu)化的子模函數(shù)最大化的超像素分割算法(MSFS)與FH、GraphCut superpixel、Turbopixels(Turbo)和NCut superpixel(NCut)四種現(xiàn)有分割算法的性能指標(biāo)UE、BR、ASA進(jìn)行了對比。

從圖中可以看出，在所有的超像素點(diǎn)上，MSFS算法的性能在各項(xiàng)指標(biāo)上均明顯優(yōu)于其他算法。圖4(a)顯示了欠分割誤差率的曲線，MSFS在超像素計(jì)數(shù)方面優(yōu)于傳統(tǒng)算法，錯(cuò)誤率降低了50%以上?？梢詫?shí)現(xiàn)在350個(gè)超像素的情況下僅有0.13的欠分割誤差，這同使用GraphCut超像素分割技術(shù)在550個(gè)超像素的情況下具有相同的性能。MSFS在550個(gè)超像素的情況下，欠分割誤差可以達(dá)到0.06。

圖4(b)繪制了邊界回溯率曲線。與超像素計(jì)數(shù)的其他算法相比，MSFS算法減少了30%以上的邊界丟失。在超像素分別為200和600的情況下，MSFS的回溯率分別為82%和92%。在超像素計(jì)數(shù)相同的情況下，F(xiàn)H的回溯率為76%和86%。

圖4(c)繪制了可實(shí)現(xiàn)的分割精度曲線。圖上可以看出，MSFS該算法在所有超像素點(diǎn)上都能產(chǎn)生較好的分割上限，特別是在超像素點(diǎn)較少的情況下,100個(gè)超像素，ASA達(dá)到95%，而其他算法只有超像素的數(shù)量達(dá)到200時(shí)才能達(dá)到同樣的精度。

實(shí)驗(yàn)3選擇自然真實(shí)環(huán)境下葉片圖像進(jìn)行超像素分割，實(shí)驗(yàn)選擇了多幅葉片圖像進(jìn)行超像素分割，計(jì)算邊界圖并將其疊加在綠色通道的輸入圖像上，實(shí)驗(yàn)結(jié)果如圖5所示(在此只顯示了兩幅不同環(huán)境中的葉片圖像)，表1顯示了4張葉片圖像算法指標(biāo)的各項(xiàng)參數(shù)。

圖5 自然環(huán)境下葉片超像素分割結(jié)果

表1 真實(shí)環(huán)境中不同大小圖像的MSFS算法參數(shù)對比

5 結(jié) 論

本文把超像素分割問題看作圖拓?fù)鋬?yōu)化問題，提出一種新的目標(biāo)函數(shù)，基于圖上隨機(jī)游走的熵率函數(shù)，結(jié)合最優(yōu)求解，推導(dǎo)出了一種有效的算法——子模函數(shù)最大化的超像素分割算法。通過Berkeley分割數(shù)據(jù)集與基準(zhǔn)中的實(shí)驗(yàn)驗(yàn)證以及現(xiàn)實(shí)自然環(huán)境下圖像的處理，表明該算法對圖像的分割具有一定的現(xiàn)實(shí)意義。從UE、BR、ASA以及運(yùn)算速度等方面與傳統(tǒng)分割算法進(jìn)行了評估和對比，具有顯著的優(yōu)勢，欠分割誤差率降低了50%，邊界回溯率降低了40%，分割精度更高，算法的運(yùn)算速度也明顯高于其他算法，分割大小為481×321的圖像只需要大約0.967 206秒。今后將計(jì)劃研究此算法適用于一般的聚類問題。