層次聚類算法和基于圖的分割算法相融合的圖像分割算法

郭昕剛，王 佳，程 超

(長春工業(yè)大學 計算機科學與工程學院， 吉林 長春 130012)

圖像分割是圖像中最底層和最重要的預處理手段之一，它根據(jù)圖像的語義信息將一張圖像分成各具特性、互不交合的獨立區(qū)域，并使同一區(qū)域內的像素點呈現(xiàn)相似性，不同區(qū)域間的像素點呈現(xiàn)明顯的差異性。它是目前AI和自動駕駛中最重要的技術分支之一，圖像分割的準確度將會直接決定下一步結果的好壞。圖像分割通常分為兩種：一種是無監(jiān)督的傳統(tǒng)圖像分割；一種是有監(jiān)督的語義分割[1]。

常用的傳統(tǒng)圖像分割方法有：基于閾值的分割方法、基于聚類的分割方法、基于邊緣的分割方法和基于圖論的分割方法等。基于閾值的分割方法計算簡單、運算速度快，其常用方法包括固定閾值分割和自適應閾值分割，前者是固定某個像素值作為分割點來進行分割，此方法要不斷嘗試手動選取分割點，故不適用于批量圖片操作；而后者是根據(jù)圖像內的局部特征，動態(tài)地在一定范圍內選取每點的閾值進行分割，但其易受噪聲和亮度干擾。基于聚類的分割方法中最常使用的是超像素分割方法，它是由Ren和Malik等在2003年首次提出的[2]，是指將一張圖像中具有相似輪廓、顏色和紋理的像素點劃分為一類[3]，進而把圖像中的點集問題轉換為區(qū)域集問題[4]，為后續(xù)的處理技術降低了計算量，提高了運算速度。其中最為經(jīng)典的超像素分割算法是Achanta等提出的簡單線性迭代聚類(simple linear iterative clustering, SLIC)算法[5]， 它的提出有效地解決了傳統(tǒng)算法分割效率低和復雜度高等問題，并幫助人們在SLIC算法基礎上研究出了一系列新的超像素分割算法，如文獻[6]在SLIC算法的基礎上，提出了一種改進的本質流形的超像素分割方法。

文獻[7]通過對SLIC算法迭代更新階段的改進，提出了一種快速的線性迭代聚類(fast linear iterative clustering, FLIC)算法，F(xiàn)LIC算法比SLIC算法可靠性更高、算法性能更優(yōu)，是目前最先進的超像素分割算法之一。然而超像素分割算法較突出的缺陷是對圖像中內容敏感的弱邊緣和紋理區(qū)域分割精度較差[8]，會導致后續(xù)工作中所獲取的像素分割點類別標簽存在誤差。為了解決超像素分割中的這一問題，文獻[9]中所提出的K-means-SLIC算法將SLIC分割出的每一個超像素塊利用K-means進行重新聚類，并通過預先設定的閾值來判斷超像素塊是否欠分割，進而解決了SLIC欠分割問題。但是K-means算法需要預先給定每個簇中的簇數(shù)，而每個超像素塊中的簇數(shù)是不固定的，所以使用K-means算法并不能完美地對簇中的每一個像素進行正確分類。

文獻[10]中所提出的Canny SLIC算法利用Canny算子檢測出來的邊緣信息來進行SLIC超像素分割，從中可以看出Canny算子檢測出來的邊緣信息能夠決定超像素與圖像中的弱邊緣和紋理區(qū)域之間的黏附性。除此之外，超像素分割算法與其他算法相結合，也取得了較好的分割效果，如：文獻[11]提出了一種使用超像素生成目標的圖像分割算法，可以實現(xiàn)基于目標的圖像分割，但其算法時間復雜度較高；文獻[12]將SLIC算法應用在特定領域的圖像上，取得了較高的分割精度和魯棒性；文獻[13]在超像素的基礎上，結合圖的理論知識重新定義了圖像局部特征中的光譜聚類，實現(xiàn)了圖像分割；文獻[14]根據(jù)超像素算法與其他方法相結合的思路，在彩色圖像上實現(xiàn)了良好的分割效果。基于邊緣的分割方法，如Canny、Sobel等[15]，其分割速度快、分割邊緣輪廓完整，但它們易把噪聲點誤判為邊界，故抗噪能力較差。基于圖論的分割方法如NCuts(normalized cuts)、GBS算法等[16]，其中效果較好的是GBS算法。GBS算法是在RGB顏色空間中進行圖像分割的，它將圖像分割問題轉換成圖的頂點分類問題，降低了問題的復雜度，但其易忽略RGB顏色空間中的色彩分布不均勻問題，進而導致其分割結果產(chǎn)生欠分割。

自2012年以來，由于卷積神經(jīng)網(wǎng)絡(convolutional neural network, CNN)的提出和應用，圖像分割的準確度再次提升，大批研究人員規(guī)避了傳統(tǒng)圖像分割算法，將大量的時間和精力投入深度學習之中。而在深度學習的圖像分割算法中，全卷積網(wǎng)絡(fully convolutional networks, FCN)無疑是最典型的深度學習算法之一[17]。它將CNN中所有全連接層全部轉換成卷積層[18]，進而把結果由原本表示的類別標簽轉換成one-hot特征圖，即一個有監(jiān)督的語義分割圖[19]。此外很多研究學者還將現(xiàn)階段訓練好的語義分割模型與傳統(tǒng)分割算法相結合來提高分割精度，如文獻[20]提出的將FCN與SLIC算法結合在一起，構造出一個超像素級別的語義分割圖就取得較好的分割效果。目前，隨著研究人員的不斷創(chuàng)新和努力，語義分割技術得到了大幅度的提升和改善，并且此技術也已經(jīng)被應用到了人們的日常生活中。但是對于語義分割，它最大的問題就是需要較好的硬件設備支持，所以經(jīng)濟成本較高。為此，為了降低開發(fā)成本，本文選取GBS算法進行研究。

為了解決GBS算法在彩色空間中忽略色彩分配不均勻所導致的欠分割問題，本文在GBS算法分割結果的基礎上，提出了結合層次聚類算法進行再次聚類分割的改進圖像分割算法，記為HCGBS(hierarchical clustering and GBS)。

1 相關算法介紹

1.1 GBS算法

GBS算法是由Felzenszwalb和Huttenlocher在2004年所提出的經(jīng)典算法之一[21]，它是在圖像最小生成樹的基礎上構建的，它分割的實質是對圖像中的像素進行聚類。GBS算法會將待分割的圖像轉換成一個帶權無向圖G=(V,E)，其中V是頂點構成的集合，記作V={v1,…,vn}，E是連接頂點間的邊所構成的集合。圖1表明了原始圖像與無向圖G之間的對應關系。

圖1 原始圖像轉換成帶權無向圖Fig.1 Conversion of original image into weighted undirected graph

在圖1中，原始圖像中的像素點被映射成為G中的頂點，像素之間的鄰近關系由G中頂點間的邊來反應，而連接頂點間的邊都有一個重要的參數(shù)——權重w(vi,vj)，此參數(shù)是用來測量兩個像素點(頂點)間的相似性與非相似性的非負值，其定義如式(1):

(1)

式中：vi和vj是圖像中的兩個像素點，R、G、B分別是兩個像素點對應的顏色值。

如圖1所示，分割面S將無向圖中的V劃分成不同的區(qū)域C，定義一個區(qū)域的內部差異為：

(2)

式中：I(C)表示區(qū)域C的生成樹中邊的最大權值。定義兩個區(qū)域的類間差異為：

(3)

式中：d(C1,C2)表示連接兩個區(qū)域的所有邊中權值最小的邊的權值。

另外，在GBS算法中，合并兩個區(qū)域的標準條件為：

(4)

GBS算法首先計算所有像素點邊的權重值，將邊按照其權重值從小到大排序得到{e1,…,en}。然后選擇ei來對當前選擇的邊ej(假設ej是連接頂點vi和vj的邊)進行合并判斷。如果vi和vj不在同一個區(qū)域或者其不相似度比二者內部不相似度小，則更新閾值和類別標簽；如果i

1.2 層次聚類算法

層次聚類算法是無監(jiān)督聚類算法中最典型的算法之一，它的主要任務是把一個數(shù)據(jù)集分成若干個類或簇，它分為從下向上(凝聚法)和從上向下(分裂法)兩種算法[22]。它們的基本定義如下：

1)從上向下(分裂法)：初始化時把所有的樣本看成一類，然后根據(jù)最小距離準則進行逐漸分裂，重復此操作直到達到停止條件。

2)從下向上(凝聚法)：初始化時將每個樣本點自成一類(即原始類別的大小等于樣本點的個數(shù))，然后依據(jù)最小距離準則合并這些初始的類簇，重復此操作直到達到停止條件。

在這兩種算法中，最常使用的是凝聚法,而凝聚法中最經(jīng)典的是AGNES算法，其具體步驟描述如下：

1)輸入樣本集合D={X1,…,Xn}，樣本之間的距離T；

2)把樣本集D中的所有樣本點都單獨地歸為一類；

4)根據(jù)設定的樣本間距離閾值T來判斷兩個類簇的差異，判決是否合并類簇Ci和Cj為一個類簇；

5)當達到聚類的數(shù)目或者達到設定的條件時結束聚類；

6)輸出聚類結果。

2 關鍵技術

2.1 HCGBS算法

在機器學習中，常用的聚類算法有K-means聚類算法、K-medoid聚類算法和層次聚類算法等。其中K-means和K-medoid都是屬于分類式的聚類算法，用戶需要預先指定聚類的簇數(shù)，且容易陷入局部最優(yōu)解，會使聚類的結果出現(xiàn)較大誤差；層次聚類算法是一種自底向上聚類的算法，不需要預先指定聚類的簇數(shù)且其相似度規(guī)則容易定義，能夠實現(xiàn)很好的類別分類。

本文HCGBS算法是將GBS算法與層次聚類算法融合在一起，構造出一個更加精細的超像素分割圖。其實驗方案如圖2所示。

圖2 實驗方案Fig.2 Experimental scheme

本文算法具體實現(xiàn)步驟如下：

1)輸入待分割的原始圖像，設置GBS算法所需的分割區(qū)域數(shù)目值s、高斯濾波標準差σ和區(qū)域塊中像素點數(shù)目m。

2)使用GBS算法對待分割圖像進行分割，獲取初始的分割類別標簽。

3)將GBS算法得到的每一個區(qū)域塊中的像素pi進行歸一化，并計算出每一個區(qū)域塊中像素pi的均值T：

(5)

其中：N為每一個區(qū)域塊中像素的個數(shù)；T∈(0,1)，T越趨于1，兩個樣本相似度越高，T越趨于0，兩個樣本相似度越小。

4)對分割后的每一類區(qū)域塊依次使用層次聚類算法來獲取每一類區(qū)域塊內部的類別標簽。

5)設定區(qū)域塊中所存在的類別數(shù)目的范圍來更新初始的分割結果。

6)最后尋找出邊緣像素點并利用區(qū)域合并準則進行區(qū)域合并，獲取新的分割圖。

2.2 算法處理速度的改進

傳統(tǒng)的層次聚類算法復雜度較高，處理大規(guī)模數(shù)據(jù)時計算速度緩慢。因此，本文先把獲取的每個像素值數(shù)組進行降維和剪切，然后再采用多線程并行處理數(shù)據(jù)的方式，將待分類的數(shù)據(jù)集同時進行聚類，有效地改善了傳統(tǒng)層次聚類算法的處理速度。傳統(tǒng)層次聚類算法與本文使用的層次聚類算法處理速度隨數(shù)據(jù)量變化的關系如圖3所示。

圖3 兩種算法處理速度對比Fig.3 Comparison of processing speed of two algorithms

從圖3中可以看出，本文改進的層次聚類算法使用多線程提高了系統(tǒng)的并行性，能夠一次性處理多個數(shù)據(jù)集，從而很好地實現(xiàn)了算法處理速度的優(yōu)化，減少了時間消耗。

3 實驗結果分析

實驗是在win7系統(tǒng)和pycharm平臺上實現(xiàn)的，所采用的數(shù)據(jù)集為公開數(shù)據(jù)集BSDS500，本節(jié)將從分割結果圖和評價指標來分析本文所提算法。

3.1 分割結果圖分析

圖4展示了本文HCGBS算法在不同的區(qū)域塊數(shù)量k和區(qū)域內像素點數(shù)量m下的分割結果。圖像結果表明，m越大，區(qū)域塊之間就越規(guī)整；m越小，k值越大，區(qū)域塊之間就越緊湊，對圖像邊界的分割性就越好。

圖4 HCGBS在不同k和m下的分割結果Fig.4 Segmentation results of HCGBS under different k and m

將本文HCGBS算法與傳統(tǒng)的K-means-SLIC算法在BSD數(shù)據(jù)集上進行了比較，其結果如圖5所示。

(a) HCGBS算法(a) HCGBS algorithm

(b) K-means-SLIC算法(b) K-means-SLIC algorithm

(c) 兩種算法比較部分的放大圖(c) Enlarged image of comparison part between two algorithms圖5 HCGBS算法與傳統(tǒng)K-means-SLIC算法的比較(k=300,m=60)Fig.5 Comparison of HCGBS algorithm and traditional K-means-SLIC algorithm(k=300,m=60)

圖5(b)中，矩形框出了K-means-SLIC算法的欠分割區(qū)域，圖5(a)中是本文HCGBS算法對其欠分割區(qū)域再分割后的圖像。從圖5(c)可以看出，本文HCGBS算法對圖中的所有欠分割區(qū)域進行了聚類再分割，分割精度高，且完整地將欠分割區(qū)域中的背景和前景分割出來，其分割效果更加精準。

圖6是本文HCGBS算法與傳統(tǒng)的GBS算法、K-means-SLIC算法、SLIC算法在BSDS500數(shù)據(jù)集的500幅圖像進行的部分比較圖。為了保證比較結果的魯棒性和真實性，固定四種算法生成的超像素數(shù)均為400，緊湊度均為60，閾值T均為每個算法生成的每個超像素塊中的像素均值，而本文HCGBS算法與GBS算法的標準差均為0.716 5。從圖6中可以看出：本文算法與其他傳統(tǒng)算法相比能夠在分割出較少區(qū)域的情況下，分割出更多的正確邊界，使分割精度更加貼合真值(GT)。

(a) HCGBS (b) GBS (c) K-means-SLIC (d) SLIC圖6 四種算法的分割圖(k=400,m=60)Fig.6 Segmentation graph of four algorithms(k=400, m=60)

3.2 評價指標

圖像分割圖是從人的視覺感官上來反映分割結果的優(yōu)劣程度，故而不能精細地反應分割結果的好壞。為了檢驗本文算法的分割有效性，采用常用的性能評價指標邊緣召回率BR和欠分割錯誤率UE[23]。BR表示圖像分割邊界在一個小鄰域內檢測到的邊界真值的分數(shù)，其數(shù)學定義如下：

(6)

其中：b(s)表示所用算法產(chǎn)生的邊緣分割結果；b(g)表示手工分割的邊緣真值；函數(shù)I(·)是用來判斷算法產(chǎn)生的分割邊界點是否在b(g)中像素θ的區(qū)域內，A(·)表示每塊分割區(qū)域的面積。

UE是用來衡量算法生成的類別區(qū)域超出圖像真值范圍區(qū)域的程度，其數(shù)學表示為：

(7)

其中，sn為生成的分割區(qū)域塊。本文算法的兩種分割性能的評價標準如圖7所示，通過圖可以看出，本文算法對測試庫中的數(shù)據(jù)集分割結果是準確的，且BR越高、UE越小，分割結果越精細。

(a) BR

(b) UE圖7 邊緣召回率BR和欠分割錯誤率UE的趨勢Fig.7 Trend chart of edge recall rate BR and under segmentation error rate UE

4 結論

本文將層次聚類算法與GBS算法融合在一起構成HCGBS算法，該方法通過設置層次聚類算法的距離閾值T為像素的均值，同時采用多線程并行處理數(shù)據(jù)的方式改善傳統(tǒng)層次聚類算法的處理速度，實現(xiàn)了自適應地對GBS算法分割后的圖像區(qū)域進行再次分割，有效地解決了K-means-SLIC算法存在的欠分割問題，并且它不會改變GBS算法的原始分割結果。經(jīng)過多次對比實驗表明，本文算法產(chǎn)生的圖像分割結果更加精細，精確度更高，為圖像預處理技術的發(fā)展奠定了更好的基礎。