莊美美 熊俊凱

（1.福建廣播電視大學(xué)泉州分校，福建泉州 ，362000 ； 2.西華大學(xué)，四川成都 ，610039）

許多圖像相關(guān)的算法操作的基本單元均為像素點(diǎn)，因而使得算法復(fù)雜度較高，同時(shí)忽略了圖像整體的結(jié)構(gòu)信息。超像素分割方法是根據(jù)顏色、紋理和空間位置等信息將相鄰的像素點(diǎn)劃分為像素塊，后續(xù)圖像處理算法以超像素作為輸入就可以降低計(jì)算量并獲得一定的結(jié)構(gòu)信息。超像素分割算法一直作為人們研究的對(duì)象，不斷有新的算法被提出。這些算法有些是在參考指標(biāo)上優(yōu)于目前的算法，[1]有些是生成的超像素具有不同于以往算法的特征，[2]有些是在特定的領(lǐng)域有著更好的應(yīng)用。[3]許多超像素算法只是根據(jù)像素點(diǎn)的特征進(jìn)行分割，但是圖像作為一個(gè)整體有著更豐富的信息，將這些信息也加入到算法中就可以使得最后生成的超像素也具有更豐富的信息，使得超像素在后續(xù)的處理中得到更好的結(jié)果。為了合理地將圖像的全局結(jié)構(gòu)信息利用起來，本文先對(duì)已有的超像素分割算法和提取全局結(jié)構(gòu)信息的方法進(jìn)行了研究，再對(duì)可以在其基礎(chǔ)上進(jìn)行修改從而用于超像素分割的其他領(lǐng)域的算法進(jìn)行了研究。經(jīng)過調(diào)查和研究，最終在魯棒連續(xù)聚類算法[4]的基礎(chǔ)上修改得到了本文的超像素分割算法。

一、超像素分割算法

在進(jìn)行像素級(jí)圖像處理時(shí)往往存在兩個(gè)非常大的缺點(diǎn)，一是如果圖像包含的像素點(diǎn)個(gè)數(shù)很多，那么運(yùn)算量就很大，甚至某些算法會(huì)不適用，二是圖像自身的信息，例如圖像全局結(jié)構(gòu)信息或者像素點(diǎn)之間的關(guān)系被忽略了，這無疑就降低了圖像信息的利用率。人們針對(duì)這兩個(gè)缺點(diǎn)進(jìn)行了相應(yīng)的研究，提出了將圖像分割為像素塊再對(duì)像素塊進(jìn)行處理的方法。[5]直到2003年Ren等人提出了超像素的概念，[6]超像素是具有一定語義信息和結(jié)構(gòu)信息的圖像子區(qū)域。超像素在三維重建、[7]目標(biāo)跟蹤、[8]目標(biāo)檢測(cè)、[9]語義分割[10]和深度估計(jì)[11]等任務(wù)中都得到了很大的應(yīng)用，許多算法都是基于超像素設(shè)計(jì)出來的。超像素分割算法的優(yōu)劣直接關(guān)系到生成的超像素質(zhì)量。目前超像素分割算法有許多的理論基礎(chǔ)，例如分水嶺、圖像密度、圖論、輪廓演化、聚類分析、能量優(yōu)化和神經(jīng)網(wǎng)絡(luò)等等，[12]它們生成的超像素都有各自的特點(diǎn)。當(dāng)前的超像素分割算法主要是基于圖論和梯度，基于神經(jīng)網(wǎng)絡(luò)的算法也開始出現(xiàn)。

（一）基于圖論的超像素分割算法

基于圖論的算法是將圖像轉(zhuǎn)化為加權(quán)無向圖，其中圖的頂點(diǎn)是像素點(diǎn)，圖的邊是像素點(diǎn)之間的相鄰關(guān)系，邊的權(quán)重是像素點(diǎn)之間的相似或差別的量化。一般情況得到的圖中所有的頂點(diǎn)是連接在一起的，通過算法將某些邊舍去后得到若干不相連的子圖，這些子圖就是圖像的超像素。這是一個(gè)自頂向下的圖的分割，不同算法對(duì)如何分割圖以及分割結(jié)果的評(píng)價(jià)是不同的。以下是一些經(jīng)典的基于圖論的算法：

Felzenszwalb等人提出的基于圖的圖像分割（Graph-Based Image Segmentation）[13]的理論基礎(chǔ)是最小生成樹，目標(biāo)是使連通子圖中的頂點(diǎn)差異盡量地小并且不同連通子圖之間的差異盡量地大。該算法的運(yùn)算速度較快，超像素的邊界貼合度高但是形狀和大小都不規(guī)則。因?yàn)樽髡呤荈elzenswalb和Huttenlocher，所以該算法也被稱為FH。Shi等人提出的Normalized Cuts(NC)[14]對(duì)圖進(jìn)行歸一化割，使得分割區(qū)域內(nèi)的權(quán)重和盡量地大并且與其它區(qū)域之間的權(quán)重和盡量地小。該算法的運(yùn)算速度慢，超像素的邊界貼合度低，但形狀和大小都比較規(guī)則。Liu等人提出的Entropy Rate Superpixel(ERS)[15]具有一個(gè)新的目標(biāo)函數(shù)，它是由圖上隨機(jī)游動(dòng)熵率和平衡項(xiàng)這兩個(gè)部分組成，熵率部分使得超像素的結(jié)構(gòu)均勻且緊湊，而平衡項(xiàng)使得超像素具有相差不大的像素個(gè)數(shù)。該算法的運(yùn)算速度較快，超像素的邊界貼合度高并且形狀和大小都比較規(guī)則。

（二）基于梯度的超像素分割算法

基于梯度的算法首先是生成初始的粗糙的超像素，然后使用梯度下降法迭代的優(yōu)化超像素，直到收斂?；谔荻鹊乃惴ㄖ幸徊糠质腔诰垲惖?，它們是在一般的聚類算法基礎(chǔ)上進(jìn)行了一些修改，將像素點(diǎn)作為聚類樣本，像素點(diǎn)的顏色和空間位置等特征作為樣本屬性，最后得到的聚類結(jié)果就是符合超像素定義的簇。這些簇與普通的聚類結(jié)果最大的區(qū)別在于簇內(nèi)的樣本具有相鄰關(guān)系，大多數(shù)聚類算法不會(huì)考慮到樣本集或者樣本之間的關(guān)系。當(dāng)然在聚類時(shí)也可以加入一些輔助信息或者約束條件，使得生成的超像素更符合預(yù)期的要求。Simple Linear Iterative Clustering(SLIC)[16]是一種經(jīng)典且流行的基于聚類的算法。

Achanta等人提出的SLIC是基于K-means[17]算法修改而來的。該方法將彩色圖像的RGB顏色空間轉(zhuǎn)換為CIELAB顏色空間，再結(jié)合空間位置XY得到5維的特征向量。然后利用特征向量進(jìn)行聚類并且將與聚類中心在圖像上相距大于一定距離的像素點(diǎn)直接排除。該算法的運(yùn)算速度快，能夠生成具有均勻緊致的超像素區(qū)域。

二、魯棒連續(xù)聚類

魯棒連續(xù)聚類算法主要是針對(duì)目前聚類算法在處理高維數(shù)據(jù)時(shí)效果不理想、在處理不同的域和數(shù)據(jù)集時(shí)需要相應(yīng)的調(diào)整算法參數(shù)以適應(yīng)不同數(shù)據(jù)的特點(diǎn)這兩個(gè)問題而設(shè)計(jì)的。它是一種跨域聚類算法，可以有效地處理高維數(shù)據(jù)和大數(shù)據(jù)集，具有較高的聚類精度。該算法在經(jīng)過拓展之后還可以實(shí)現(xiàn)聚類和降維的聯(lián)合。由于該算法將聚類表示為基于魯棒估計(jì)的連續(xù)目標(biāo)優(yōu)化，因此作者將其稱為robust continuous clustering (RCC)。而通過拓展RCC達(dá)到聯(lián)合執(zhí)行聚類和降維的拓展算法被稱為RCC-DR，它學(xué)習(xí)將高維數(shù)據(jù)嵌入到一個(gè)低維空間中，并在其中進(jìn)行聚集。

RCC不會(huì)直接對(duì)數(shù)據(jù)集X=[x1,x2,…xn]進(jìn)行操作，而是在一個(gè)表征集U=[u1,u2,…un]上進(jìn)行操作，其中X和U中的每個(gè)樣本都是D維數(shù)據(jù)。U使用X進(jìn)行初始化，基于U的優(yōu)化 操作揭示了數(shù)據(jù)集中的潛在集群結(jié)構(gòu)。RCC的目標(biāo)函數(shù)如下：

其中ε是由數(shù)據(jù)點(diǎn)構(gòu)成的圖的邊的集合，RCC使用了mutual k-nearest neighbors (m-kNN)[18]算法生成邊。權(quán)重wp,q根據(jù)ε得到，代表p和q兩個(gè)樣本的相似度。λ平衡了函數(shù)內(nèi)不同項(xiàng)的強(qiáng)度。p(.)是正則化的懲罰項(xiàng)，為了使來自同一潛在簇的ui崩潰成一個(gè)點(diǎn)選取了10范數(shù)，但是也使得優(yōu)化變得困難，而11和12范數(shù)不能處理ε中的偽邊，最后選擇了Geman-McClure估計(jì)器。可以將該式子理解為在使得U與X盡量的相似的同時(shí)使得權(quán)重wp,q大的成對(duì)項(xiàng)up和uq也盡量相似，即在優(yōu)化操作U時(shí)避免與原始數(shù)據(jù)相差過大并且將近似的成對(duì)數(shù)據(jù)點(diǎn)劃分到同一類。

為每個(gè)連接(p,q)∈ε引入了一個(gè)輔助變量lp,q，并優(yōu)化U和L=｛lp,q｝的聯(lián)合目標(biāo)：

其中μ是尺度參數(shù)。

使用交替迭代來優(yōu)化目標(biāo)函數(shù)，當(dāng)U固定時(shí)可用以下公式求解lp,q：

當(dāng)lp,q固定，可以重寫公式2，得到求解U的公式：

其中ei是一個(gè)指示向量，第i個(gè)元素設(shè)為1。這是一個(gè)線性最小二乘問題，線性最小二乘公式是：

三、基于魯棒連續(xù)聚類的超像素分割算法

?

四、實(shí)驗(yàn)

本文的實(shí)驗(yàn)平臺(tái)是MATLAB，實(shí)驗(yàn)數(shù)據(jù)庫是BSDS500。對(duì)大量的圖像進(jìn)行分割后可以看出本文算法可以生成貼合邊界的超像素，但是超像素的形狀較為不規(guī)則并且大小相差較大。這主要是由于加入了含結(jié)構(gòu)信息的鄰接表，并且在本文算法中鄰接表起到了很大的作用，所以分割的結(jié)果會(huì)更貼合邊界并且形狀不規(guī)則。同時(shí)，本文算法中沒有對(duì)超像素的大小進(jìn)行約束并且像素的空間位置特征起到的作用不大，所以會(huì)產(chǎn)生較大或較小的超像素。本文算法同Ncut，Linear Spectral Clustering(LSC) ，[19]SLIC和FH這幾個(gè)經(jīng)典算法進(jìn)行了對(duì)比，結(jié)果如圖1所示。本文算法中RCC的最大迭代次數(shù)是100，內(nèi)循環(huán)次數(shù)是4。LSC中ratio=0.075。SLIC中顏色和空間位置的平衡項(xiàng)值是20。FH中sigma= 0.5，kappa = 32，Nsup=270。Ncut，LSC和SLIC的超像素個(gè)數(shù)是60。從中可以看出本文算法比FH，Ncut和SLIC等算法更貼合邊界，能夠更精確的分割出貼合圖像邊界的超像素，尤其是其它算法分割不出來的弱邊界。最貼合邊界的是LSC，但也因此在一些邊緣復(fù)雜的圖像上分割的超像素邊界較為雜亂。例如圖1第三行中鳥的頭頂。

表1 不同算法的指標(biāo)對(duì)比Tab. 1 Index comparison of different algorithms

由于基 于RCC算法，本文算法不可以指定超像素的個(gè)數(shù)，所以不能有效地與其它的超像素分割算法進(jìn)行各項(xiàng)指標(biāo)上的對(duì)比。為了得到比較客觀的結(jié)果，取本文算法分割后的超像素個(gè)數(shù)的平均值60作為參考，用60作為指定的超像素個(gè)數(shù)用于對(duì)比算法。但是FH也是不能指定超像素的個(gè)數(shù)的，所以在實(shí)驗(yàn)時(shí)通過調(diào)整參數(shù)使得FH分割得到的超像素個(gè)數(shù)的平均值與本文相同也是60。所有算法的參數(shù)和上文相同。本文在achievable segmentation accuracy (ASA)，Boundary recall (BR)，undersegmentation error (UE)以及運(yùn)行時(shí)間等指標(biāo)上進(jìn)行了評(píng)估，實(shí)驗(yàn)結(jié)果如表1所示。本文算法結(jié)合了圖像邊緣信息，分割出的超像素更加貼合邊界但是這些邊界可能更多的是背景邊界，所以在BR上較好但不突出。同時(shí)由于本文算法分割出的超像素形狀較為不規(guī)則并且大小相差較大，所以在ASA和UE上存在不足。

圖1 分割結(jié)果，(a)本文算法，(b)FH，(c)Ncut，(d)SLIC，(e)LSCFig． 1 Segmentation results, (a) Ours, (b)FH, (c)Ncut, (d)SLIC, (e)LSC

五、結(jié)論

本文提出了一種基于魯棒連續(xù)聚類算法的圖像超像素分割方法，可以有效地分割出具有較高邊界貼合度的超像素。其中，圖像的邊緣經(jīng)過轉(zhuǎn)換后作為本文算法的輸入，提供了全局結(jié)構(gòu)信息，并且在運(yùn)算中起到了重要的作用，決定了最終生成的超像素的特點(diǎn)?？梢钥闯鰣D像的全局結(jié)構(gòu)信息可以輔助超像素的分割，使得超像素的邊界貼合度提升。但是對(duì)于背景占主要部分或者邊界復(fù)雜的圖像而言可能反而使得分割結(jié)果變差，需要在算法中進(jìn)行平衡。