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

郭昕剛，王 佳，程 超

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

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

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

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

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

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

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

1 相關(guān)算法介紹

1.1 GBS算法

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

圖1 原始圖像轉(zhuǎn)換成帶權(quán)無向圖Fig.1 Conversion of original image into weighted undirected graph

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

(1)

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

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

(2)

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

(3)

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

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

(4)

GBS算法首先計算所有像素點邊的權(quán)重值，將邊按照其權(quán)重值從小到大排序得到{e1,…,en}。然后選擇ei來對當前選擇的邊ej(假設(shè)ej是連接頂點vi和vj的邊)進行合并判斷。如果vi和vj不在同一個區(qū)域或者其不相似度比二者內(nèi)部不相似度小，則更新閾值和類別標簽；如果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ù)設(shè)定的樣本間距離閾值T來判斷兩個類簇的差異，判決是否合并類簇Ci和Cj為一個類簇；

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

6)輸出聚類結(jié)果。

2 關(guān)鍵技術(shù)

2.1 HCGBS算法

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

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

圖2 實驗方案Fig.2 Experimental scheme

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

1)輸入待分割的原始圖像，設(shè)置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ū)域塊內(nèi)部的類別標簽。

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

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

2.2 算法處理速度的改進

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

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

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

3 實驗結(jié)果分析

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

3.1 分割結(jié)果圖分析

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

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

將本文HCGBS算法與傳統(tǒng)的K-means-SLIC算法在BSD數(shù)據(jù)集上進行了比較，其結(jié)果如圖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幅圖像進行的部分比較圖。為了保證比較結(jié)果的魯棒性和真實性，固定四種算法生成的超像素數(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 評價指標

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

(6)

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

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

(7)

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

(a) BR

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

4 結(jié)論

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