改進(jìn)的SLIC超像素圖像分割與合并算法

劉安琪，劉華勇，王煥寶，

(1.安徽建筑大學(xué) 電子與信息工程學(xué)院，安徽 合肥 230601；2.安徽建筑大學(xué) 數(shù)理學(xué)院，安徽 合肥 230601)

0 引言

隨著科學(xué)技術(shù)的發(fā)展，可視化設(shè)備的畫(huà)面變得越來(lái)越清晰，設(shè)備所生成圖像的尺寸劇增。早期的圖像分割技術(shù)效率較低，且不能在高分辨率的圖像中保持較好的實(shí)時(shí)性。為了解決高像素圖像的分割問(wèn)題，Ren[1]提出了超像素的概念。迄今為止，超像素分割算法基本分成兩種。一種是基于數(shù)學(xué)中圖論的方法；另一種則是基于聚類(lèi)思想的梯度上升方法[2]?；趫D論的超像素分割方法包括Ncuts[3]、Graph Cuts[4]、Grab Cuts[5]等；基于梯度上升的超像素分割方法包括Mean Shift[6]、Turbopixel[7]、SLIC(Simple Linear Iterative Clustering，SLIC)[8]等。其中SLIC 超像素分割算法(后文簡(jiǎn)稱(chēng)為SLIC 算法)在時(shí)間復(fù)雜度、邊界召回率以及分割錯(cuò)誤率等方面優(yōu)于前兩者。近年來(lái)，國(guó)內(nèi)外研究人員提出了多種基于SLIC 算法的改進(jìn)形式[9-11]。文獻(xiàn)[9]提出的有偏聚類(lèi)提升了算法的計(jì)算效率，但在欠分割問(wèn)題的處理上效果不夠明顯；文獻(xiàn)[10]近鄰分類(lèi)雖提升了算法的計(jì)算效率，但欠分割問(wèn)題未得到解決，分割結(jié)果的邊緣貼合度也有待提高；文獻(xiàn)[11]提出的區(qū)域合并僅建立在顏色特征上，并未融入圖像的紋理特征。本文提出的采用像素抽樣、基于紋理特征的K-means 聚類(lèi)對(duì)SLIC 算法進(jìn)行改進(jìn)，提升算法的計(jì)算效率的同時(shí)對(duì)欠分割區(qū)域進(jìn)行修正。最后在改進(jìn)的算法分割結(jié)果基礎(chǔ)上結(jié)合雙向鄰域圖分割結(jié)果進(jìn)行區(qū)域合并。

1 相關(guān)算法

1.1 SLIC算法

SLIC 算法首先將圖像從原來(lái)的RGB 顏色空間轉(zhuǎn)變?yōu)镃IELab 顏色空間；然后結(jié)合CIELab 顏色空間的三個(gè)分量和像素點(diǎn)在圖像中的位置信息構(gòu)建一個(gè)5 維的特征向量Pi=[li,ai,bi,xi,yi]，i 是像素的下標(biāo)；最后對(duì)圖像中的像素點(diǎn)進(jìn)行局部聚類(lèi)處理。算法步驟如下：

步驟1：種子點(diǎn)的初始化

假設(shè)輸入圖像共有N 個(gè)像素點(diǎn)，分割結(jié)果預(yù)計(jì)需要得到K 個(gè)超像素塊，那么每個(gè)超像素塊中應(yīng)有約N K 個(gè)像素點(diǎn)，種子點(diǎn)間的距離約為S =N K。選取種子點(diǎn)時(shí)，為了降低其落在圖像邊界的位置的可能性，會(huì)在原種子點(diǎn)的3×3 區(qū)域內(nèi)尋求一個(gè)梯度最小的位置作為新種子點(diǎn)。每個(gè)種子點(diǎn)代表一個(gè)類(lèi)別。

步驟2：衡量相似度

在給定的步長(zhǎng)范圍內(nèi)，計(jì)算每個(gè)像素點(diǎn)與種子點(diǎn)間的相似度。SLIC 的相似度度量方法如下。

dlab為像素間的顏色距離。dxy為像素間的歐式距離。D(i,k)的值代表像素點(diǎn)i 與種子點(diǎn)k 間的相似度，D(i,k)越小則越相似。m 為權(quán)重參數(shù)，取值范圍為[1，40]。

步驟3：像素點(diǎn)分類(lèi)

根據(jù)相似性度量結(jié)果，像素點(diǎn)類(lèi)別與其相似度最高的種子點(diǎn)的類(lèi)別保持一致。重復(fù)步驟2、步驟3，直到聚類(lèi)結(jié)果無(wú)顯著變化或達(dá)到要求的迭代次數(shù)。

步驟4：后續(xù)處理

結(jié)合連通性準(zhǔn)則，將多連通及面積過(guò)小的超像素塊與其相鄰的大超像素塊合并。

1.2 K-means算法

K-means 聚類(lèi)算法通過(guò)像素與種子點(diǎn)間的歐氏距離來(lái)衡量像素間的相似度，將像素點(diǎn)分成多個(gè)類(lèi)別[12]。K-means 聚類(lèi)算法原理簡(jiǎn)單、對(duì)低維且相對(duì)集中的數(shù)據(jù)具有較好的分類(lèi)效果。K-means 算法具體步驟如下。

輸入：待聚類(lèi)圖像。

輸出：聚類(lèi)結(jié)果。

步驟1：初始化K 個(gè)種子點(diǎn)(K≥2)；

步驟2：比較所有像素點(diǎn)到種子點(diǎn)間的歐氏距離，像素點(diǎn)類(lèi)別與歐氏距離最小的種子點(diǎn)保持一致；

步驟3：計(jì)算類(lèi)中所有像素的平均值，將均值作為新的種子點(diǎn)；

步驟4：重復(fù)上述步驟2、步驟3，直到聚類(lèi)結(jié)果不再發(fā)生明顯變化或達(dá)到要求的迭代次數(shù)為止。

2 本文算法

2.1 像素抽樣

相比于SLIC 算法，本文算法首先對(duì)待分割圖像進(jìn)行像素點(diǎn)的間隔抽樣，抽樣方式如圖1 所示。

圖1 像素采樣

其中，黑色部分為采樣像素點(diǎn)，白色部分為未采樣像素點(diǎn)。對(duì)于采樣部分的像素點(diǎn)，采用公式(1)計(jì)算；對(duì)未采樣部分像素點(diǎn)，以如圖2 所示的每9 個(gè)像素為單位，用像素點(diǎn)間的相關(guān)性進(jìn)行標(biāo)簽分配。由像素間的相關(guān)性可知，一個(gè)像素的標(biāo)簽大概率與其相鄰的像素保持一致。根據(jù)這一性質(zhì)，在計(jì)算1 號(hào)像素的標(biāo)簽時(shí)，只計(jì)算1 號(hào)像素和其左右相鄰的兩個(gè)已知標(biāo)簽像素間的顏色距離dlab。其余像素點(diǎn)均可用上述方法求出標(biāo)簽，5 號(hào)像素需要與其相鄰的四個(gè)像素點(diǎn)計(jì)算相似度。

圖2 未采樣像素標(biāo)簽分配

2.2 基于紋理特征的K-means聚類(lèi)修正

2.2.1 灰度共生矩陣

灰度共生矩陣是一種基于統(tǒng)計(jì)方法的描述圖像紋理特征的方法。灰度共生矩陣定義為從灰度級(jí)i 的點(diǎn)離開(kāi)某固定的位置關(guān)系d =(Dx,Dy)以達(dá)到灰度為j 的概率Pd(i,j)=(i,j = 0,1,2,3,...,L -1)。其中，i，j 分別表示像素的灰度值，L 為圖像的灰度級(jí)，d 表示兩個(gè)像素間的步長(zhǎng)；i 與j 間的夾角θ 表示灰度共生矩陣生成時(shí)的方向[13]。示意圖如圖3 所示。

圖3 像素與角度的關(guān)系

步長(zhǎng)確定后，圖像的灰度共生矩陣的一般形式如式4 所示。

d 分別取1、2、3 時(shí)的紋理圖像如圖4 所示。

圖4 不同步長(zhǎng)d的紋理分割結(jié)果

由圖4 可知，當(dāng)步長(zhǎng)d 較小時(shí)，紋理更為細(xì)致。本文利用紋理特征修正超像素分割結(jié)果中的欠分割區(qū)域，即圖像中的子塊，要對(duì)紋理特征進(jìn)行精細(xì)的表征，所以本文中步長(zhǎng)d 取為1。

2.2.2 灰度共生矩陣的特征表示

灰度共生矩陣共有14 種紋理特征值，其中應(yīng)用較廣泛的有4 種，分別為能量、對(duì)比度、相關(guān)度以及熵。本文選取對(duì)比度和熵表征圖像的紋理特征。

對(duì)比度是度量灰度共生矩陣的值是如何分布和圖像中局部變化的多少，反應(yīng)了圖像的清晰度和紋理的溝紋深淺。對(duì)比值越大，反差越大，效果越清晰；反之，對(duì)比值小，則溝紋淺，效果模糊。對(duì)比度的計(jì)算如式(5)所示。

熵可以衡量信息量，紋理是一種信息，由此熵也可以衡量紋理。熵反映了圖像中紋理非均勻度或復(fù)雜性。紋理越復(fù)雜，熵值越大。熵的計(jì)算如式(6)所示。

計(jì)算特征值前，先確定計(jì)算過(guò)程中的相關(guān)參數(shù)。本文選擇3×3 大小的滑動(dòng)窗口進(jìn)行特征值計(jì)算，步長(zhǎng)d 設(shè)為1，方向選取0 °、45 °、90 °、135 °等4 個(gè)方向。

綜上所述，基于紋理特征的K-means 聚類(lèi)修正算法步驟如下。

輸入：初始分割結(jié)果。

輸出：修正結(jié)果。

步驟1：灰度級(jí)量化

計(jì)算灰度共生矩陣時(shí)，為避免大計(jì)算量，將灰度級(jí)量化為8 個(gè)灰度級(jí)。

步驟2：計(jì)算紋理特征值

通過(guò)灰度共生矩陣計(jì)算4 個(gè)方向上的對(duì)比度和熵，然后計(jì)算兩個(gè)參數(shù)在4 個(gè)方向的均值，作為窗口中心像素的最終紋理特征。

步驟3：

移動(dòng)窗口，重復(fù)步驟2，直到遍歷完所有像素點(diǎn)為止。

步驟4：

用所求的對(duì)比度和熵來(lái)代替?zhèn)鹘y(tǒng)K-means 聚類(lèi)中像素的位置信息，對(duì)欠分割區(qū)域進(jìn)行聚類(lèi)，直至達(dá)到所設(shè)聚類(lèi)次數(shù)為止。

2.3 雙向鄰域圖區(qū)域合并

對(duì)修正后的結(jié)果，用區(qū)域鄰接圖(Region Adjacency Graph，RAG)將分割結(jié)果映射為一個(gè)無(wú)向圖G=(V，E)[14]。其中V 為圖中結(jié)點(diǎn)的集合，代表分割結(jié)果中的超像素塊，E 為圖中邊的集合，代表超像素塊間的相鄰關(guān)系。構(gòu)造區(qū)域鄰接圖的過(guò)程如圖5 所示。

RAG 能記錄所有區(qū)域間的關(guān)系。但若得到的初始分割區(qū)域數(shù)量太多，會(huì)造成RAG 的節(jié)點(diǎn)數(shù)量和邊的數(shù)量過(guò)多，從而造成計(jì)算復(fù)雜度增大，這時(shí)可采用雙向鄰域圖(Bidirectional Neighbor Graph，BNG)對(duì)RAG 進(jìn)行改進(jìn)。一個(gè)已確定的RAG，其改進(jìn)形式BNG 為Gm=(Vm,Em)。Gm表示有向圖，Vm表示原RAG 中所有節(jié)點(diǎn)的集合，Em是有向邊的集合。BNG 中的每個(gè)節(jié)點(diǎn)都有一條有向邊指向與該節(jié)點(diǎn)最相似的節(jié)點(diǎn)。RAG 轉(zhuǎn)換為BNG 過(guò)程如圖6 所示。

圖5 構(gòu)建區(qū)域鄰接圖

圖6 構(gòu)建雙向鄰域圖

由RAG 轉(zhuǎn)換為BNG 時(shí)，在RAG 中需保留全部邊，而在BNG 中只需保留部分邊，合并時(shí)每次只合并閉合環(huán)兩端的區(qū)域，大大提高了計(jì)算速度，加快了合并效率。改進(jìn)的區(qū)域合并算法步驟如下：

輸入：初步分割結(jié)果圖。

輸出：最終分割結(jié)果。

步驟1：對(duì)輸入的分割結(jié)果圖進(jìn)行RAG 的構(gòu)建；

步驟2：計(jì)算每個(gè)區(qū)域與其相鄰區(qū)域的相似度，將RAG 轉(zhuǎn)換為BNG；

步驟3：在BNG 中先對(duì)閉合環(huán)兩端的節(jié)點(diǎn)進(jìn)行合并，所有閉合環(huán)合并完成后，更新BNG；直到循環(huán)結(jié)束為止；

步驟4：輸出合并結(jié)果。

2.4 相似性度量

2.4.1 顏色特征

顏色特征是圖像最基本的特征之一。本文采用超像素塊的顏色直方圖對(duì)顏色特征進(jìn)行描述。為簡(jiǎn)化計(jì)算，對(duì)RGB 顏色空間中的3 個(gè)分量作均勻量化處理，由原來(lái)的256 級(jí)降為16 級(jí)，則共有4096 級(jí)顏色；再用巴氏系數(shù)計(jì)算超像素塊間的相似性，計(jì)算式如式(7)所示。

2.4.2 紋理特征

局部二進(jìn)制模式(Local Binary Patterns，LBP)是由Ojala[15]等提出的一種紋理描述算子。其定義為在3×3 的窗口內(nèi)，以窗口中心像素的灰度值為閾值，與相鄰的8 個(gè)像素的灰度值比較，若周?chē)南袼刂荡笥谥行南袼刂担瑒t該像素點(diǎn)的位置被標(biāo)記為1，否則為0。這樣3×3 鄰域內(nèi)的8 個(gè)點(diǎn)經(jīng)比較可產(chǎn)生8 位二進(jìn)制數(shù)，即得到該窗口中心像素點(diǎn)的LBP 值。LBP 計(jì)算式如(8)所示。

式中(xc,yc)為中心像素，ic為中心像素灰度值，ip為相鄰像素灰度值，s(·)為符號(hào)函數(shù)，定義如式(9)所示。

本文采用LBP 提取紋理特征。首先，將超像素塊分成4×4 的16 個(gè)區(qū)域；然后，計(jì)算每個(gè)區(qū)域的歸一化灰度直方圖；最后，整合16 個(gè)區(qū)域的歸一化灰度直方圖，利巴氏系數(shù)來(lái)計(jì)算超像素塊間的相似性，計(jì)算如式(10)所示。

A 為區(qū)域數(shù)量，HistvQ和HistvR分別表示區(qū)域Q和R 的歸一化灰度直方圖，v 為元素下標(biāo)，α(Q,R)的值越大，區(qū)域Q 和R 間的相似度越大。

綜上所述，本文區(qū)域間的相似性度量計(jì)算如式(11)所示。

本文算法步驟如下：

輸入：待分割圖像。

輸出：分割結(jié)果。

步驟1：像素抽樣處理；

步驟2：對(duì)抽樣像素點(diǎn)與未抽樣像素點(diǎn)進(jìn)行標(biāo)簽分配，得到初步分割結(jié)果；

步驟3：采用基于紋理特征的K-means 聚類(lèi)方法修正欠分割區(qū)域；

步驟4：提取超像素塊的顏色與紋理特征，利用雙向鄰域圖進(jìn)行合并，得到最終分割結(jié)果。

綜上所述，本文算法流程如圖7 所示。

圖7 算法流程圖

3 實(shí)驗(yàn)結(jié)果與分析

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

本文實(shí)驗(yàn)所用圖片均來(lái)自BSD500 數(shù)據(jù)集。圖8 為SLIC 算法分割結(jié)果圖，其中a 為原圖，b、c、d 分別對(duì)應(yīng)為超像素塊K 取100、500、1000 的分割結(jié)果。

SLIC 算法的分割結(jié)果有時(shí)會(huì)存在背景與目標(biāo)區(qū)域沒(méi)有完全分開(kāi)的欠分割情況，如圖9 所示。用本文提出的改進(jìn)的SLIC 超像素分割算法對(duì)圖像進(jìn)行分割，分割結(jié)果如圖10 所示。從圖中可以看出，欠分割區(qū)域經(jīng)過(guò)基于紋理特征的K-means 聚類(lèi)修正后，樹(shù)干基本與天空完全分離。

對(duì)修正后的分割結(jié)果構(gòu)建雙向鄰域圖，利用結(jié)合顏色與紋理特征的相似性度量公式計(jì)算區(qū)域間的相似度，進(jìn)行區(qū)域合并，結(jié)果如圖11 所示。

圖8 不同K值的分割結(jié)果圖

圖9 分割結(jié)果中的欠分割區(qū)域

圖10 欠分割區(qū)域的修正

圖11 BNG區(qū)域合并結(jié)果

3.2 實(shí)驗(yàn)對(duì)比

3.2.1 不同權(quán)重m 與欠分割的關(guān)系

m 為調(diào)節(jié)顏色距離的權(quán)重，起著調(diào)節(jié)像素點(diǎn)間顏色距離與歐式距離比重的作用。由圖12 可知：m 較小時(shí)，分割結(jié)果的欠分割錯(cuò)誤率低；而當(dāng)m 較大時(shí)，分割結(jié)果的欠分割錯(cuò)誤率較高。但當(dāng)m 較小時(shí)，雖取得了較低的欠分割錯(cuò)誤率，但超像素塊多以扁平、細(xì)長(zhǎng)為主，形狀不規(guī)則，緊湊度較低，不利于超像素的后續(xù)處理。當(dāng)m 較大時(shí)，分割結(jié)果的欠分割錯(cuò)誤率較高，但所得的超像素塊形狀規(guī)則，緊湊度較高。所以綜合分析，當(dāng)m 取15、20、25時(shí)，所得分割結(jié)果的超像素塊相對(duì)規(guī)則，緊湊度相對(duì)較高，同時(shí)也能取得不錯(cuò)的欠分割錯(cuò)誤率。

圖12 權(quán)重m與欠分割錯(cuò)誤率的關(guān)系

3.2.2 時(shí)間對(duì)比

表1 展示了四種超像素分割算法分割同一圖像時(shí)所用時(shí)間。由表1 可知，SLIC 算法在計(jì)算速度上優(yōu)于其余三種超像素分割算法。

表1 不同超像素分割算法時(shí)間對(duì)比

在SLIC 算法中，每個(gè)像素點(diǎn)在2S×2S 的范圍內(nèi)搜尋種子點(diǎn)，示意圖如圖13 所示。在規(guī)定搜索空間中每個(gè)像素點(diǎn)最少計(jì)算1 次，最多計(jì)算9 次。在本文算法中，采樣部分的像素利用原相似度度量公式進(jìn)行計(jì)算，采樣部分的像素約占總像素的四分之一。對(duì)于未采樣部分的像素點(diǎn)，以每9 個(gè)像素點(diǎn)為一個(gè)計(jì)算單位，利用像素點(diǎn)間的相關(guān)性，采用顏色距離公式進(jìn)行相似度計(jì)算，計(jì)算式由五維降到了三維。在計(jì)算次數(shù)上，由原來(lái)的1 到9 次計(jì)算降到了現(xiàn)在的0 次、2 次或4 次。改進(jìn)的SLIC 算法從計(jì)算公式維度和像素點(diǎn)的計(jì)算次數(shù)兩個(gè)方面對(duì)SLIC 算法進(jìn)行改進(jìn)，提高算法的運(yùn)算速度。表2為SLIC 算法與本文算法在K 取不同值時(shí)，每個(gè)像素點(diǎn)的計(jì)算次數(shù)統(tǒng)計(jì)。

圖13 搜索示意圖

表2 不同K值的像素點(diǎn)計(jì)算次數(shù)

圖14 展示了不同K 值下未加入紋理修正和加入紋理修正的時(shí)間與SLIC 算法的時(shí)間對(duì)比。由表2 可知，在K 取不同值時(shí)，SLIC 算法像素點(diǎn)的計(jì)算次數(shù)約為本文所提方法的2 倍，這在圖14 中得以體現(xiàn)，經(jīng)過(guò)像素抽樣后獲得不同K 值的分割結(jié)果所需時(shí)間約為SLIC 算法的一半。在加入對(duì)欠分割區(qū)域的修正處理后，時(shí)間消耗雖有所增加，但仍低于SLIC 算法所用時(shí)間。

圖14 時(shí)間對(duì)比

3.2.3 客觀評(píng)價(jià)標(biāo)準(zhǔn)

邊界召回率是衡量算法生成的邊界之間和真值邊界的一致性程度的指標(biāo)。邊界召回率越高，說(shuō)明算法生成的邊界越貼近真值邊界。邊界召回率定義如式(12)所示。

其中B(g)和B(s)分別為超像素邊界真值和算法生成的超像素邊界的集合。I(·)為指示函數(shù)，如果算法生成的超像素中的邊界像素位于超像素真值中的邊界像素范圍之內(nèi)，則返回1；否則返回0。Area(s)表示集合s 的面積。

欠分割錯(cuò)誤率計(jì)算的是算法生成的超像素塊和真值間不重合部分的比值。欠分割錯(cuò)誤率的定義如式(13)所示。

其中g(shù)i為Ground Truth 中的第i 個(gè)部分。S是超像素算法對(duì)目標(biāo)的分割結(jié)果，sk為S 中第k 個(gè)超像素塊。運(yùn)算符||表示超像素區(qū)域內(nèi)像素點(diǎn)的數(shù)量。

表3 展示了不同超像素分割算法分割同一圖像時(shí)的邊界召回率與欠分割錯(cuò)誤率的對(duì)比。

表3 不同超像素分割算法BR和UE對(duì)比

由表3 可知，相比于其余3 種超像素分割算法，SLIC 算法的邊界召回率最高，欠分割錯(cuò)誤率最低。

圖15 為本文算法與SLIC 算法的客觀評(píng)價(jià)對(duì)比。由圖15 可知，本文算法在邊界召回率上要優(yōu)于SLIC 算法，說(shuō)明本文方法相較于SLIC 算法能獲得更好的邊界貼合度。在欠分割錯(cuò)誤率方面，當(dāng)超像素?cái)?shù)目小于500 時(shí)，本文方法的欠分割錯(cuò)誤率要低于SLIC 算法；當(dāng)超像素?cái)?shù)目大于500 時(shí)，本文方法與SLIC 算法的欠分割錯(cuò)誤率非常接近。綜上所述，本文方法在超像素的客觀評(píng)價(jià)結(jié)果中要優(yōu)于SLIC 算法。

4 結(jié)論

圖15 本文算法與SLIC算法的客觀評(píng)價(jià)對(duì)比

本文在SLIC 算法的基礎(chǔ)上，提出一種改進(jìn)的SLIC 圖像分割算法。針對(duì)SLIC 方法對(duì)分辨率高的圖像進(jìn)行分割時(shí)的時(shí)耗問(wèn)題，利用像素抽樣和像素間的相關(guān)性對(duì)圖像進(jìn)行分割。在運(yùn)行速度上，本文算法相比于SLIC 算法，提升了約22%。同時(shí)，為了減少分割結(jié)果中的欠分割現(xiàn)象，采用基于紋理特征的K-means 聚類(lèi)對(duì)欠分割區(qū)域進(jìn)行修正。修正后的分割結(jié)果的邊界召回率也優(yōu)于SLIC 算法。最后，以顏色和紋理特征相結(jié)合征構(gòu)建相似性函數(shù)，利用雙向鄰域圖合并超像素塊。實(shí)驗(yàn)表明，本文算法在時(shí)間復(fù)雜度與客觀評(píng)價(jià)上均優(yōu)于SLIC算法。