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

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

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

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

1 基本知識

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

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

(1)

其中wi=∑k:ei,k∈Ewi,k是頂點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對于一個集合函數(shù)F，如果對于所有A1?A2滿足F(A1)≤F(A2),則F為單調(diào)遞增集合函數(shù)。

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

2 問題描述

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

圖1 熵率的作用

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

2.1 構(gòu) 圖

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

2.2 熵 率

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

(5)

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

(6)

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

2.3 平衡函數(shù)

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

(7)

且平衡項表示為：

(8)

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

(9)

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

3 優(yōu)化方法

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

3.1 高效率貪婪算法

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

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

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

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

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

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

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

4 實驗和結(jié)果

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

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

(10)

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

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

(11)

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

(12)

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

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

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

圖3 超像素圖像分割實例

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

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

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

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

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

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

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

5 結(jié) 論

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