基于SLIC和區域生長的目標分割算法

韓紀普，段先華，常 振

江蘇科技大學 計算機學院，江蘇 鎮江212000

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

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

1 傳統區域生長算法

區域生長是一種基于灰度相似性和灰度不連續性的串行區域分割的圖像分割方法，其基本思想是將具有相似性質的像素集合起來構成區域。具體要先對每個需要分割的區域確定一個種子點像素，然后將種子像素周圍鄰域中與種子像素具有相同或相似性質的像素（根據某種事先確定的生長或相似準則來判定）合并到種子像素所在的區域中。將這些新像素當做新的種子像素繼續進行上面的過程，直到再沒有滿足條件的像素可被包括進來，此時就可以判定一個區域生長完成。

區域生長的三大要素分別為：種子點選取、確定生長規則、確定終止條件。區域生長的好壞與三要素息息相關，尤其種子點的選取會對最終分割結果產生直接影響。

1.1 選取種子點

種子點即圖像區域生長的起點，對于灰度圖而言，種子點信息應該包括區域生長起始坐標(x,y)，以及該點的灰度值g(x,y)。現有的種子點選取方法無外乎兩種：半自動種子點選取和全自動種子點選取。半自動種子點選取即通過人機交互的方式根據使用者的經驗知識選擇生長起點，半自動的方式適用范圍廣泛，幾乎所有的圖像都可以用半自動的方式選擇生長起點，但該方法過分依賴使用者的經驗知識。全自動種子點選取即在特定環境下通過某種先驗知識自動篩選生長起點，例如：在紅外圖像中一般選取亮度最大的像素點作為生長起點。

1.2 生長準則

生長準則是區域生長法的核心部分，對于灰度圖而言，生長準則一般設定為某個固定灰度閾值T，若種子像素與其鄰域像素之間的灰度差小于T，則將其鄰域像素納入目標區域。即：

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

1.3 生長停止條件

區域生長一般采用遞歸調用的方式，當種子像素在其鄰域內完成生長，將目標區域新納入的像素點依次作為新的種子像素繼續生長過程，直到目標區域內再無新像素點加入，此時停止生長。

如果圖像區域內灰度梯度有較大波動，則設置較小閾值T會導致圖像欠分割，在噪聲處出現分割孔洞，分割邊界模糊等問題，而設置較大閾值T又會導致圖像過分割。

2 超像素

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

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

3 本文算法

本文算法的主要思想是通過SLIC超像素分割算法將原始圖像粗分割為一系列不規則的超像素，根據分割后超像素之間的位置關系建立無向加權圖，選取種子超像素，在建立好的無向加權圖上做區域生長得到目標區域，最后在目標區域邊緣處以像素為單位做區域生長，細化邊界。

3.1 算法步驟

3.1.1 拉普拉斯銳化

為了提高SLIC 的邊緣命中率，在構造超像素之前先采用拉普拉斯銳化強化圖像細節。拉普拉斯銳化通過構造圖像的二階微分方程來尋找圖像像素突變的點，當該點像素灰度低于其鄰域像素的平均灰度時，則降低該點的像素灰度，當該點像素灰度高于其鄰域像素的平均灰度時，則提高該點的像素灰度。

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

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

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

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

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

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

3.1.2 SLIC超像素分割

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

SLIC的算法步驟主要包括：

（1）初始化種子點

對于一張有N個像素點的圖像，計劃分割為K個尺寸相近的超像素，則每個超像素大小近似于N/K。在圖像內均勻選取種子點，則種子點的選取步長近似為：

（2）將種子點移到n×n鄰域內梯度最小值位置

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

（3）根據距離度量為每個像素點分配聚類標簽

首先為圖像內所有像素點設置初始距離度量D=MAX，之后遍歷圖像中所有種子點，計算種子點鄰域內每個像素點到當前種子點距離，距離的計算包括像素點之間的顏色距離以及位置距離，對于LAB 圖像種子點鄰域內的每個像素點，其與種子點的顏色空間距離為：

對于灰度圖像，其與種子點的顏色空間距離為：

其中gj與gi分別為目標像素與種子像素的灰度值。其與種子點的位置空間距離為：

總距離為：

NC為最大顏色距離，一般取固定常數m（m取值范圍為[1，40]），之后計算出的距離度量更新每個像素點的聚類標簽，更新規則為：如果D′≤D，則將像素點標簽更新為當前種子點，且令D=D′。

（4）更新種子點

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

（5）迭代優化

重復步驟（3）和（4），直到每個像素點的聚類標簽不再變化或者達到最大迭代次數（經實驗證明，對于絕大多數圖像，SLIC 算法迭代優化10 次之后都能取得較為理想的結果[16]，所以最大迭代次數一般設置為10）。

（6）增強連通性

采用從左到右，從上到下的方式遍歷圖像中的超像素，將刪選出來的孤立像素點或面積過小的聯通分量分類給距離最近的超像素。

3.1.3 區域生長

在上一步生成的超像素群的基礎上，根據圖論的方法生成一個以超像素為基礎的無向加權圖G=＜V,E ＞，在無向圖中V是頂點的集合，E是邊的集合，反映到超像素圖像上V是超像素的集合，E是超像素之間位置關系的集合。設存在超像素Vi、Vj：

其中ga(Vi)為超像素Vi內部像素的灰度均值，ga(Vj)為超像素Vj內部像素的灰度均值。

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

根據區域生長算法，選取種子點超像素Vseed，設置生長閾值T，對于超像素Vu，E(seed,u)＜T，則把超像素Vu納入目標區域，之后迭代生長，直至再也沒有新的超像素被納入目標區域。

3.1.4 細化邊界

當上一步的生長完成時，會得到粗分割的邊界信息，之后在目標區域的邊界處再次執行以像素為單位的區域生長，細化邊界。

3.2 算法流程圖

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

圖2 算法流程圖

4 實驗結果

本次實驗的實驗環境為Intel i7-7700HQ CPU，8 GB RAM計算機，實驗所用工具為MATLAB2016a。本次實驗選取常用圖像“Cameraman”，在數據集msrcorid中選取“Trees”“Leaves”“Chairs”等自然場景下圖像分別采用Otsu閾值分割、聚類分割、傳統區域生長法，以及本文算法進行分割結果比較。原始圖像以及分割圖像比較結果，如圖3～6所示。

圖3 Cameraman分割結果比較

從圖3～6的實驗結果對比可以看出，傳統區域生長算法在目標分割過程中極易出現分割空洞如：圖3（d），當分割空洞過大，分割目標甚至會丟失部分區域信息，如：圖4（d）、圖6（d）。而Otsu分割與聚類分割的分割效果相似，在分割過程中可以較好地把握分割目標的整體輪廓，但也容易引入過多的背景，如：圖3（b）、（c），圖4（b）、（c），當分割目標內灰度值差異過大，以上兩類算法也會在一定程度上丟失部分區域信息，如：圖6（b）、（c）。本文算法有效地解決了傳統區域生長算法中存在的分割空洞問題，能夠很好地把握圖像的整體輪廓以及細節信息，如：圖5（e）、6（e），相比于Otsu閾值分割、聚類分割等典型目標分割算法，本文算法不會引入過多的背景信息，如：圖3（e）、4（e），從而在分割精度以及目標區域的細節處理上都有顯著提升。

為了更加直觀地評價算法的分割效果，本文采用精確度（Precision）、召回率（Recall）對四種算法進行評價[17]。其中精確度表示被算法分割出的區域，待分割的目標區域所占的百分比，公式表示為：

其中TP（True Positive）表示被判定為目標區域且判定正確的像素數，FP（False Positive）表示被判定為目標區域且判定錯誤的像素數。召回率表示待分割的目標區域中，被算法正確分割的百分比，公式表示為：

其中FN（False Negative）表示被判定為非目標區域且判定錯誤的像素數。

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

圖4 Trees分割結果比較

圖5 Leaves分割結果比較

圖6 Chair分割結果比較

表1 算法的精確度、召回率對比表

5 結論

本文提出了基于SLIC 和區域生長的目標分割算法，該算法在自然場景圖像的目標分割中取得了理想的分割效果。拉普拉斯銳化強化圖像細節，提高了SLIC的邊緣命中率，以SLIC 預分割的超像素為單位進行區域生長在提高了算法運行速度的同時還能夠消除分割目標內部的空洞。經實驗證明，本文算法確實是一種行之有效的目標分割算法。