基于SLIC和區(qū)域生長(zhǎng)的目標(biāo)分割算法

韓紀(jì)普，段先華，常 振

江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 鎮(zhèn)江212000

圖像分割是圖像理解的重要組成部分，是計(jì)算機(jī)視覺(jué)的基石，也是圖像分析、圖像識(shí)別等方法的首要步驟，圖像分割結(jié)果的好壞會(huì)對(duì)圖像的后續(xù)處理過(guò)程產(chǎn)生決定性的影響，在計(jì)算機(jī)視覺(jué)的產(chǎn)生和發(fā)展過(guò)程中，圖像分割是圖像工作者碰到的最困難的問(wèn)題之一。圖像分割即是根據(jù)圖像的灰度、紋理、形狀等特征將圖像劃分成互不相交的若干區(qū)域，同時(shí)保證區(qū)域內(nèi)部在分割特征上保持各向同性，區(qū)域與區(qū)域之間在分割特征上保持各向異性。在實(shí)際應(yīng)用中即為在待分割圖像中提取出人們關(guān)心的區(qū)域，為圖像處理中的其他方法打下基礎(chǔ)。

在圖像分割的發(fā)展歷史中，閾值分割、區(qū)域生長(zhǎng)、邊緣檢測(cè)是人們常用的三大類傳統(tǒng)分割方法。近年來(lái)，隨著機(jī)器學(xué)習(xí)的興起，圖像分割也呈現(xiàn)出了百花齊放的景象，基于機(jī)器學(xué)習(xí)的聚類分割、基于深度學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)等方法也一一涌現(xiàn)，而其中的區(qū)域生長(zhǎng)算法自1976年由Zuker 等人提出以來(lái)便成為圖像分割中的經(jīng)典算法[1]。時(shí)至今日，區(qū)域生長(zhǎng)法因其思想簡(jiǎn)單，且不需要先驗(yàn)知識(shí)便能得到良好的邊界信息和分割結(jié)果等優(yōu)點(diǎn)依然在圖像分割中占有一席之地，其中最典型的區(qū)域生長(zhǎng)法是基于小面（facet）模型的區(qū)域生長(zhǎng)法。盡管區(qū)域生長(zhǎng)算法在圖像分割中擁有眾多其他算法無(wú)法比擬的優(yōu)勢(shì)，但區(qū)域生長(zhǎng)算法本身固有的缺點(diǎn)同樣不容忽視。例如：傳統(tǒng)區(qū)域生長(zhǎng)算法需要人工選取種子點(diǎn)，而且分割效果依賴于種子點(diǎn)的選取，種子點(diǎn)選取不當(dāng)往往無(wú)法得到理想的分割結(jié)果；傳統(tǒng)區(qū)域生長(zhǎng)算法對(duì)噪聲敏感，圖像存在噪聲或者圖像內(nèi)部灰度值分布不均勻都會(huì)對(duì)分割結(jié)果產(chǎn)生影響，即傳統(tǒng)算法無(wú)法處理過(guò)于復(fù)雜的分割目標(biāo)；此外，傳統(tǒng)區(qū)域生長(zhǎng)算法的空間開銷過(guò)大，容易加重計(jì)算機(jī)的負(fù)擔(dān)。對(duì)以上缺陷的解決辦法，圖像處理工作者們展開了孜孜不倦的探求，對(duì)傳統(tǒng)區(qū)域生長(zhǎng)算法的改進(jìn)包括與閾值分割相結(jié)合的基于Otsu（最大類間方差）的區(qū)域生長(zhǎng)算法[2]，與Watershed（分水嶺）相結(jié)合的自動(dòng)種子區(qū)域生長(zhǎng)算法[3]、基于變分水平集的區(qū)域生長(zhǎng)算法[4]、基于PCA-SVM 準(zhǔn)則的改進(jìn)區(qū)域生長(zhǎng)算法[5]、基于灰度共生矩陣的區(qū)域生長(zhǎng)算法[6]、多尺度下的區(qū)域生長(zhǎng)算法[7]，以及與神經(jīng)網(wǎng)絡(luò)相結(jié)合的動(dòng)態(tài)自適應(yīng)區(qū)域生長(zhǎng)算法[8]等，以上算法在各自的應(yīng)用領(lǐng)域都能取得不錯(cuò)的分割效果。針對(duì)區(qū)域生長(zhǎng)法固有的缺陷，本文提出一種基于超像素和區(qū)域生長(zhǎng)的目標(biāo)分割算法，該算法首次將SLIC（Simple Linear Iterative Cluster）超像素分割用于區(qū)域生長(zhǎng)，通過(guò)超像素分割的方法將圖像中的原有像素聚合成小型的像素塊，能夠大幅減小區(qū)域生長(zhǎng)算法的空間開銷，同時(shí)也能消除圖像噪聲和灰度值不均勻等問(wèn)題對(duì)分割結(jié)果產(chǎn)生的影響。經(jīng)實(shí)驗(yàn)證明，本文算法在性能方面與現(xiàn)有算法相比有明顯優(yōu)勢(shì)。

1 傳統(tǒng)區(qū)域生長(zhǎng)算法

區(qū)域生長(zhǎng)是一種基于灰度相似性和灰度不連續(xù)性的串行區(qū)域分割的圖像分割方法，其基本思想是將具有相似性質(zhì)的像素集合起來(lái)構(gòu)成區(qū)域。具體要先對(duì)每個(gè)需要分割的區(qū)域確定一個(gè)種子點(diǎn)像素，然后將種子像素周圍鄰域中與種子像素具有相同或相似性質(zhì)的像素（根據(jù)某種事先確定的生長(zhǎng)或相似準(zhǔn)則來(lái)判定）合并到種子像素所在的區(qū)域中。將這些新像素當(dāng)做新的種子像素繼續(xù)進(jìn)行上面的過(guò)程，直到再?zèng)]有滿足條件的像素可被包括進(jìn)來(lái)，此時(shí)就可以判定一個(gè)區(qū)域生長(zhǎng)完成。

區(qū)域生長(zhǎng)的三大要素分別為：種子點(diǎn)選取、確定生長(zhǎng)規(guī)則、確定終止條件。區(qū)域生長(zhǎng)的好壞與三要素息息相關(guān)，尤其種子點(diǎn)的選取會(huì)對(duì)最終分割結(jié)果產(chǎn)生直接影響。

1.1 選取種子點(diǎn)

種子點(diǎn)即圖像區(qū)域生長(zhǎng)的起點(diǎn)，對(duì)于灰度圖而言，種子點(diǎn)信息應(yīng)該包括區(qū)域生長(zhǎng)起始坐標(biāo)(x,y)，以及該點(diǎn)的灰度值g(x,y)?，F(xiàn)有的種子點(diǎn)選取方法無(wú)外乎兩種：半自動(dòng)種子點(diǎn)選取和全自動(dòng)種子點(diǎn)選取。半自動(dòng)種子點(diǎn)選取即通過(guò)人機(jī)交互的方式根據(jù)使用者的經(jīng)驗(yàn)知識(shí)選擇生長(zhǎng)起點(diǎn)，半自動(dòng)的方式適用范圍廣泛，幾乎所有的圖像都可以用半自動(dòng)的方式選擇生長(zhǎng)起點(diǎn)，但該方法過(guò)分依賴使用者的經(jīng)驗(yàn)知識(shí)。全自動(dòng)種子點(diǎn)選取即在特定環(huán)境下通過(guò)某種先驗(yàn)知識(shí)自動(dòng)篩選生長(zhǎng)起點(diǎn)，例如：在紅外圖像中一般選取亮度最大的像素點(diǎn)作為生長(zhǎng)起點(diǎn)。

1.2 生長(zhǎng)準(zhǔn)則

生長(zhǎng)準(zhǔn)則是區(qū)域生長(zhǎng)法的核心部分，對(duì)于灰度圖而言，生長(zhǎng)準(zhǔn)則一般設(shè)定為某個(gè)固定灰度閾值T，若種子像素與其鄰域像素之間的灰度差小于T，則將其鄰域像素納入目標(biāo)區(qū)域。即：

其中，A[n]為目標(biāo)區(qū)域，g(x,y)為種子像素，g(i,j)為g(x,y)鄰域像素。

1.3 生長(zhǎng)停止條件

區(qū)域生長(zhǎng)一般采用遞歸調(diào)用的方式，當(dāng)種子像素在其鄰域內(nèi)完成生長(zhǎng)，將目標(biāo)區(qū)域新納入的像素點(diǎn)依次作為新的種子像素繼續(xù)生長(zhǎng)過(guò)程，直到目標(biāo)區(qū)域內(nèi)再無(wú)新像素點(diǎn)加入，此時(shí)停止生長(zhǎng)。

如果圖像區(qū)域內(nèi)灰度梯度有較大波動(dòng)，則設(shè)置較小閾值T會(huì)導(dǎo)致圖像欠分割，在噪聲處出現(xiàn)分割孔洞，分割邊界模糊等問(wèn)題，而設(shè)置較大閾值T又會(huì)導(dǎo)致圖像過(guò)分割。

2 超像素

在2003 年，Ren 和Malik 提出了超像素的概念[9]，超像素顧名思義就是將具有灰度、紋理、亮度等低級(jí)特征相似性的相鄰像素聚合成不規(guī)則的像素塊，用少量的超像素代替圖像原有像素點(diǎn)，在不損失圖像原有特征的基礎(chǔ)少大幅減少可處理對(duì)象的數(shù)量，從而降低了圖像后續(xù)處理的復(fù)雜度，提高效率。超像素常用于各類圖像算法的預(yù)處理，在計(jì)算機(jī)視覺(jué)領(lǐng)域有著重要的研究?jī)r(jià)值。由于超像素在圖像分割方面有著極為出色的表現(xiàn)，近年來(lái)越來(lái)越多的學(xué)者將研究重點(diǎn)放在超像素與圖像分割算法的結(jié)合上。王柯嚴(yán)等[10]提出一種將超像素與多閾值分割相結(jié)合的天空去霧算法，宋以寧等[11]將超像素用于無(wú)人機(jī)圖像分割，姚丙秀等[12]提出將超像素與圖論相結(jié)合的遙感影像分割算法。以上與超像素相結(jié)合的分割算法對(duì)比于原有算法，在算法性能和效果上都有不錯(cuò)的提升。計(jì)算機(jī)視覺(jué)領(lǐng)域的Mean Shift（均值漂移算法）[13]、Watershed（分水嶺算法）[14]、Normalized Cut（圖割算法）[15]、簡(jiǎn)單線性迭代聚類算法SLIC[16]等，都是現(xiàn)階段常見(jiàn)的超像素分割算法。其中的SLIC 算法，自2010 年提出以來(lái)便因其思想簡(jiǎn)單、實(shí)現(xiàn)方便而受到了人們的廣泛關(guān)注。SLIC-簡(jiǎn)單線性迭代聚類算法，脫胎于K-means聚類算法，但不同于K-means 聚類算法每次迭代都會(huì)遍歷整個(gè)解空間以得到最優(yōu)聚類，SLIC 結(jié)合圖像自身的特點(diǎn)將每次迭代的搜索范圍限制在種子點(diǎn)的λ鄰域內(nèi)（鄰域大小視期望的超像素尺寸而定，若期望的超像素尺寸為S×S，則λ鄰域大小為2S×2S）。如圖1[16]，這種做法可以在不影響聚類效果的同時(shí)加速算法收斂。

圖1 K-means以及SLIC搜索模型

3 本文算法

本文算法的主要思想是通過(guò)SLIC超像素分割算法將原始圖像粗分割為一系列不規(guī)則的超像素，根據(jù)分割后超像素之間的位置關(guān)系建立無(wú)向加權(quán)圖，選取種子超像素，在建立好的無(wú)向加權(quán)圖上做區(qū)域生長(zhǎng)得到目標(biāo)區(qū)域，最后在目標(biāo)區(qū)域邊緣處以像素為單位做區(qū)域生長(zhǎng)，細(xì)化邊界。

3.1 算法步驟

3.1.1 拉普拉斯銳化

為了提高SLIC 的邊緣命中率，在構(gòu)造超像素之前先采用拉普拉斯銳化強(qiáng)化圖像細(xì)節(jié)。拉普拉斯銳化通過(guò)構(gòu)造圖像的二階微分方程來(lái)尋找圖像像素突變的點(diǎn)，當(dāng)該點(diǎn)像素灰度低于其鄰域像素的平均灰度時(shí)，則降低該點(diǎn)的像素灰度，當(dāng)該點(diǎn)像素灰度高于其鄰域像素的平均灰度時(shí)，則提高該點(diǎn)的像素灰度。

二階微分法下的拉普拉斯算子（拉普拉斯掩膜中心系數(shù)）表示如下：

根據(jù)該算子可以得到四鄰域下的模版矩陣：

同理，八鄰域下的拉普拉斯算子表示如下：

根據(jù)該算子可以得到八鄰域下的模版矩陣：

將模版矩陣與待處理圖像做卷積，根據(jù)式子（6）更新原始圖像像素值：

其中f(x,y)為更新前像素值，g(x,y)為更新后像素值。

3.1.2 SLIC超像素分割

SLIC 是將彩色圖像轉(zhuǎn)化為CIELAB 顏色空間和XY 坐標(biāo)下的五維特征向量，然后對(duì)五維特征向量構(gòu)造距離度量標(biāo)準(zhǔn)，對(duì)圖像像素進(jìn)行局部聚類的過(guò)程。SLIC 算法能生成緊湊、近似均勻的超像素，在運(yùn)算速度、物體輪廓保持、超像素形狀方面具有較高的綜合評(píng)價(jià)，比較符合人們期望的分割效果。SLIC 本質(zhì)屬于聚類分割，所以SLIC不僅可以分割彩色圖，也可以兼容分割灰度圖。

SLIC的算法步驟主要包括：

（1）初始化種子點(diǎn)

對(duì)于一張有N個(gè)像素點(diǎn)的圖像，計(jì)劃分割為K個(gè)尺寸相近的超像素，則每個(gè)超像素大小近似于N/K。在圖像內(nèi)均勻選取種子點(diǎn)，則種子點(diǎn)的選取步長(zhǎng)近似為：

（2）將種子點(diǎn)移到n×n鄰域內(nèi)梯度最小值位置

n的一般取值為3，計(jì)算第一步確定的種子點(diǎn)3×3鄰域內(nèi)所有像素的梯度值，根據(jù)計(jì)算出的梯度值更新種子點(diǎn)位置，將種子點(diǎn)落在鄰域內(nèi)梯度值最小值處。這種處理方法可以保證種子點(diǎn)不會(huì)落在梯度較大的邊界處以及噪聲點(diǎn)處，以免影響最終聚類結(jié)果。

（3）根據(jù)距離度量為每個(gè)像素點(diǎn)分配聚類標(biāo)簽

首先為圖像內(nèi)所有像素點(diǎn)設(shè)置初始距離度量D=MAX，之后遍歷圖像中所有種子點(diǎn)，計(jì)算種子點(diǎn)鄰域內(nèi)每個(gè)像素點(diǎn)到當(dāng)前種子點(diǎn)距離，距離的計(jì)算包括像素點(diǎn)之間的顏色距離以及位置距離，對(duì)于LAB 圖像種子點(diǎn)鄰域內(nèi)的每個(gè)像素點(diǎn)，其與種子點(diǎn)的顏色空間距離為：

對(duì)于灰度圖像，其與種子點(diǎn)的顏色空間距離為：

其中g(shù)j與gi分別為目標(biāo)像素與種子像素的灰度值。其與種子點(diǎn)的位置空間距離為：

總距離為：

NC為最大顏色距離，一般取固定常數(shù)m（m取值范圍為[1，40]），之后計(jì)算出的距離度量更新每個(gè)像素點(diǎn)的聚類標(biāo)簽，更新規(guī)則為：如果D′≤D，則將像素點(diǎn)標(biāo)簽更新為當(dāng)前種子點(diǎn)，且令D=D′。

（4）更新種子點(diǎn)

種子點(diǎn)遍歷結(jié)束后，根據(jù)每個(gè)像素點(diǎn)的聚類標(biāo)簽更新種子點(diǎn)位置。用seed1,seed2,…,seedk表示分割圖像的種子點(diǎn)以及像素點(diǎn)的聚類標(biāo)簽，對(duì)于灰度圖像，求取所有聚類標(biāo)簽為seedi(1 ≤i≤k)的像素點(diǎn)的灰度均值ga和坐標(biāo)均值(xa,ya)作為新的種子點(diǎn)。

（5）迭代優(yōu)化

重復(fù)步驟（3）和（4），直到每個(gè)像素點(diǎn)的聚類標(biāo)簽不再變化或者達(dá)到最大迭代次數(shù)（經(jīng)實(shí)驗(yàn)證明，對(duì)于絕大多數(shù)圖像，SLIC 算法迭代優(yōu)化10 次之后都能取得較為理想的結(jié)果[16]，所以最大迭代次數(shù)一般設(shè)置為10）。

（6）增強(qiáng)連通性

采用從左到右，從上到下的方式遍歷圖像中的超像素，將刪選出來(lái)的孤立像素點(diǎn)或面積過(guò)小的聯(lián)通分量分類給距離最近的超像素。

3.1.3 區(qū)域生長(zhǎng)

在上一步生成的超像素群的基礎(chǔ)上，根據(jù)圖論的方法生成一個(gè)以超像素為基礎(chǔ)的無(wú)向加權(quán)圖G=＜V,E ＞，在無(wú)向圖中V是頂點(diǎn)的集合，E是邊的集合，反映到超像素圖像上V是超像素的集合，E是超像素之間位置關(guān)系的集合。設(shè)存在超像素Vi、Vj：

其中g(shù)a(Vi)為超像素Vi內(nèi)部像素的灰度均值，ga(Vj)為超像素Vj內(nèi)部像素的灰度均值。

當(dāng)超像素Vi，Vj不相鄰時(shí)，E(i,j)=MAX。

根據(jù)區(qū)域生長(zhǎng)算法，選取種子點(diǎn)超像素Vseed，設(shè)置生長(zhǎng)閾值T，對(duì)于超像素Vu，E(seed,u)＜T，則把超像素Vu納入目標(biāo)區(qū)域，之后迭代生長(zhǎng)，直至再也沒(méi)有新的超像素被納入目標(biāo)區(qū)域。

3.1.4 細(xì)化邊界

當(dāng)上一步的生長(zhǎng)完成時(shí)，會(huì)得到粗分割的邊界信息，之后在目標(biāo)區(qū)域的邊界處再次執(zhí)行以像素為單位的區(qū)域生長(zhǎng)，細(xì)化邊界。

3.2 算法流程圖

綜上所述，算法流程圖如圖2所示。

圖2 算法流程圖

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

本次實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境為Intel i7-7700HQ CPU，8 GB RAM計(jì)算機(jī)，實(shí)驗(yàn)所用工具為MATLAB2016a。本次實(shí)驗(yàn)選取常用圖像“Cameraman”，在數(shù)據(jù)集msrcorid中選取“Trees”“Leaves”“Chairs”等自然場(chǎng)景下圖像分別采用Otsu閾值分割、聚類分割、傳統(tǒng)區(qū)域生長(zhǎng)法，以及本文算法進(jìn)行分割結(jié)果比較。原始圖像以及分割圖像比較結(jié)果，如圖3～6所示。

圖3 Cameraman分割結(jié)果比較

從圖3～6的實(shí)驗(yàn)結(jié)果對(duì)比可以看出，傳統(tǒng)區(qū)域生長(zhǎng)算法在目標(biāo)分割過(guò)程中極易出現(xiàn)分割空洞如：圖3（d），當(dāng)分割空洞過(guò)大，分割目標(biāo)甚至?xí)G失部分區(qū)域信息，如：圖4（d）、圖6（d）。而Otsu分割與聚類分割的分割效果相似，在分割過(guò)程中可以較好地把握分割目標(biāo)的整體輪廓，但也容易引入過(guò)多的背景，如：圖3（b）、（c），圖4（b）、（c），當(dāng)分割目標(biāo)內(nèi)灰度值差異過(guò)大，以上兩類算法也會(huì)在一定程度上丟失部分區(qū)域信息，如：圖6（b）、（c）。本文算法有效地解決了傳統(tǒng)區(qū)域生長(zhǎng)算法中存在的分割空洞問(wèn)題，能夠很好地把握?qǐng)D像的整體輪廓以及細(xì)節(jié)信息，如：圖5（e）、6（e），相比于Otsu閾值分割、聚類分割等典型目標(biāo)分割算法，本文算法不會(huì)引入過(guò)多的背景信息，如：圖3（e）、4（e），從而在分割精度以及目標(biāo)區(qū)域的細(xì)節(jié)處理上都有顯著提升。

為了更加直觀地評(píng)價(jià)算法的分割效果，本文采用精確度（Precision）、召回率（Recall）對(duì)四種算法進(jìn)行評(píng)價(jià)[17]。其中精確度表示被算法分割出的區(qū)域，待分割的目標(biāo)區(qū)域所占的百分比，公式表示為：

其中TP（True Positive）表示被判定為目標(biāo)區(qū)域且判定正確的像素?cái)?shù)，F(xiàn)P（False Positive）表示被判定為目標(biāo)區(qū)域且判定錯(cuò)誤的像素?cái)?shù)。召回率表示待分割的目標(biāo)區(qū)域中，被算法正確分割的百分比，公式表示為：

其中FN（False Negative）表示被判定為非目標(biāo)區(qū)域且判定錯(cuò)誤的像素?cái)?shù)。

從表1的實(shí)驗(yàn)對(duì)比數(shù)據(jù)可以看出，Otsu分割算法和聚類分割算法在四種圖像上的召回率都在0.9 左右波動(dòng)，這也恰好說(shuō)明了以上兩類算法能夠很好地把握分割目標(biāo)的整體輪廓，但以上兩類算法在精確度上的表現(xiàn)略有不足，尤其當(dāng)分割目標(biāo)與一部分背景的灰度值與空間位置都存在相似性，例如Trees圖像，Otsu分割算法以及聚類分割在Trees 圖像上的分割精確度分別為0.746、0.733，這種分割精確度是無(wú)法滿足現(xiàn)實(shí)應(yīng)用的。而傳統(tǒng)區(qū)域生長(zhǎng)算法更傾向于高精確度、低召回率，傳統(tǒng)區(qū)域生長(zhǎng)算法在四種圖像上的精確度能夠在0.9左右波動(dòng)，但相對(duì)的召回率確只能達(dá)到0.83左右，甚至更低的0.73。反觀本文算法，無(wú)論是精確度還是召回率都能穩(wěn)定在0.9 以上，尤其對(duì)于Chair 圖像，本文算法的精確度和召回率更是達(dá)到了0.98 以上。通過(guò)以上的數(shù)據(jù)對(duì)比，能夠更直觀地說(shuō)明本文算法在目標(biāo)分割上的優(yōu)勢(shì)。

圖4 Trees分割結(jié)果比較

圖5 Leaves分割結(jié)果比較

圖6 Chair分割結(jié)果比較

表1 算法的精確度、召回率對(duì)比表

5 結(jié)論

本文提出了基于SLIC 和區(qū)域生長(zhǎng)的目標(biāo)分割算法，該算法在自然場(chǎng)景圖像的目標(biāo)分割中取得了理想的分割效果。拉普拉斯銳化強(qiáng)化圖像細(xì)節(jié)，提高了SLIC的邊緣命中率，以SLIC 預(yù)分割的超像素為單位進(jìn)行區(qū)域生長(zhǎng)在提高了算法運(yùn)行速度的同時(shí)還能夠消除分割目標(biāo)內(nèi)部的空洞。經(jīng)實(shí)驗(yàn)證明，本文算法確實(shí)是一種行之有效的目標(biāo)分割算法。