基于魯棒連續聚類的圖像超像素分割方法

莊美美 熊俊凱

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

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

一、超像素分割算法

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

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

基于圖論的算法是將圖像轉化為加權無向圖，其中圖的頂點是像素點，圖的邊是像素點之間的相鄰關系，邊的權重是像素點之間的相似或差別的量化。一般情況得到的圖中所有的頂點是連接在一起的，通過算法將某些邊舍去后得到若干不相連的子圖，這些子圖就是圖像的超像素。這是一個自頂向下的圖的分割，不同算法對如何分割圖以及分割結果的評價是不同的。以下是一些經典的基于圖論的算法：

Felzenszwalb等人提出的基于圖的圖像分割（Graph-Based Image Segmentation）[13]的理論基礎是最小生成樹，目標是使連通子圖中的頂點差異盡量地小并且不同連通子圖之間的差異盡量地大。該算法的運算速度較快，超像素的邊界貼合度高但是形狀和大小都不規則。因為作者是Felzenswalb和Huttenlocher，所以該算法也被稱為FH。Shi等人提出的Normalized Cuts(NC)[14]對圖進行歸一化割，使得分割區域內的權重和盡量地大并且與其它區域之間的權重和盡量地小。該算法的運算速度慢，超像素的邊界貼合度低，但形狀和大小都比較規則。Liu等人提出的Entropy Rate Superpixel(ERS)[15]具有一個新的目標函數，它是由圖上隨機游動熵率和平衡項這兩個部分組成，熵率部分使得超像素的結構均勻且緊湊，而平衡項使得超像素具有相差不大的像素個數。該算法的運算速度較快，超像素的邊界貼合度高并且形狀和大小都比較規則。

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

基于梯度的算法首先是生成初始的粗糙的超像素，然后使用梯度下降法迭代的優化超像素，直到收斂。基于梯度的算法中一部分是基于聚類的，它們是在一般的聚類算法基礎上進行了一些修改，將像素點作為聚類樣本，像素點的顏色和空間位置等特征作為樣本屬性，最后得到的聚類結果就是符合超像素定義的簇。這些簇與普通的聚類結果最大的區別在于簇內的樣本具有相鄰關系，大多數聚類算法不會考慮到樣本集或者樣本之間的關系。當然在聚類時也可以加入一些輔助信息或者約束條件，使得生成的超像素更符合預期的要求。Simple Linear Iterative Clustering(SLIC)[16]是一種經典且流行的基于聚類的算法。

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

二、魯棒連續聚類

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

RCC不會直接對數據集X=[x1,x2,…xn]進行操作，而是在一個表征集U=[u1,u2,…un]上進行操作，其中X和U中的每個樣本都是D維數據。U使用X進行初始化，基于U的優化 操作揭示了數據集中的潛在集群結構。RCC的目標函數如下：

其中ε是由數據點構成的圖的邊的集合，RCC使用了mutual k-nearest neighbors (m-kNN)[18]算法生成邊。權重wp,q根據ε得到，代表p和q兩個樣本的相似度。λ平衡了函數內不同項的強度。p(.)是正則化的懲罰項，為了使來自同一潛在簇的ui崩潰成一個點選取了10范數，但是也使得優化變得困難，而11和12范數不能處理ε中的偽邊，最后選擇了Geman-McClure估計器?？梢詫⒃撌阶永斫鉃樵谑沟肬與X盡量的相似的同時使得權重wp,q大的成對項up和uq也盡量相似，即在優化操作U時避免與原始數據相差過大并且將近似的成對數據點劃分到同一類。

為每個連接(p,q)∈ε引入了一個輔助變量lp,q，并優化U和L=｛lp,q｝的聯合目標：

其中μ是尺度參數。

使用交替迭代來優化目標函數，當U固定時可用以下公式求解lp,q：

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

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

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

?

四、實驗

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

表1 不同算法的指標對比Tab. 1 Index comparison of different algorithms

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

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

五、結論

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