三種聚類算法在建筑圖像分割上的應用

周婷婷，張虹波，潘麗靜

（寧夏大學物理與電子電氣工程學院，銀川 750021）

三種聚類算法在建筑圖像分割上的應用

周婷婷，張虹波，潘麗靜

（寧夏大學物理與電子電氣工程學院，銀川 750021）

對三種聚類算法（MeanShift、K-Means、FCM）的原理進行簡單的闡述，針對Berkeley分割數據集和基準500（BSDS500）標準圖片庫中的一張建筑物圖片在MATLAB 2013a上編程實現對該圖片的彩色聚類分割和灰度聚類分割，根據實驗結果對三種聚類算法從參數設置、分割效果和分割時間上進行對比分析它們的優缺點，并得出結論。

聚類算法；MeanShift；K-Means；FCM

0 引言

圖像分割是把圖像劃分為若干有意義區域并提取感興趣目標的圖像處理技術，圖像分割是圖像識別和計算機視覺至關重要的預處理。沒有正確的分割就不可能有正確的識別。分割技術在人臉識別、行人檢測、指紋識別和醫學影像分析中有重要的研究價值和廣泛的應用發展前景。

圖像分割方法主要包括以下幾種類型：基于閾值的分割、基于區域的分割、基于邊緣的分割以及基于特定理論的分割等[1]。張毅飛、呂科在文獻[2]使用均值漂移算法結合區域增長算法對遙感圖像海陸邊界進行分割。鄒秋霞、楊林楠等在文獻[3]中使用Lab色彩空間和K-Means算法對植物葉片進行分割。王建、于鎮赫等提出一種改進的模糊核均值聚類算法，結合Outs算法得到的閾值得到聚類灰度均值，將這些均值作為聚類中心的初始值以實現模糊聚類算法[4]。

1 均值漂移（MeanShift）算法

MeanShift算法是一種基于密度梯度上升的非參數方法，通過迭代運算找到目標位置?；贛eanShift的圖像分割與圖像平滑非常類似，只需要把收斂到同一點的起始點歸為一類，然后把這一類的標號賦給這些起始點[5]。設S是n維空間X中的一個有限集合，K表示X空間中球體的一個特征函數，本實驗采用的是單位均勻核函數，其表達式如下：

單位均勻核函數如圖1所示[6]：

圖1 單位均勻核函數

其中，x∈X，那么在向量點x處的樣本均值為：

均值漂移向量表示為：

MeanShift算法步驟：

（1）計算式mh（x）；

（2）計算式mh（x）與像素點間的偏移量式mh（x）-x；

（3）給定一個誤差值ε，如果‖mh（x）-x‖＜ε，說明已經找到概率密度最大的點，算法結束，否則把mh（x）賦給x，返回步驟（1）繼續執行迭代。

根據MeanShift算法的原理在MATLAB 2013a上對MeanShift算法進行編程實現對圖像的彩色聚類分割。實驗首先把圖像從RGB色彩空間轉換成CIELUV色彩空間，原因是對比RGB色彩空間而言，LUV色彩空間具有視覺統一性，并且LUV色彩空間通過歐氏距離更能較好的表現出不同顏色之間的相似性。歐氏距離公式：

其中d的值越小代表兩點之間的顏色相似度越高。分割過程中實現了RGB、LUV色彩空間的相互轉換和對圖片的彩色聚類分割，通過觀察帶寬參數的不同對實驗結果的影響從而得出結論。設定初始聚類中心隨機產生，均值收斂時停止的閾值為103r，其中r代表帶寬參數。該算法對圖像的彩色分割結果如下：

圖2 均值漂移算法彩色分割結果

根據圖像分割的區域一致性和邊緣準確性，由圖2可以看出當帶寬參數為3時，建筑物主體部分顏色不統一，且邊界不清晰，當帶寬參數為4、5時，建筑物窗口部分沒有與房屋同一顏色，當帶寬參數為8時，建筑物與天空分界明顯，無雜色。當帶寬參數為15時，部分天空出現錯分現象。當帶寬參數為16及以上時，建筑物主體未分割出來。根據分析，針對該算法和該圖像最合適的帶寬參數為8。

Meanshift算法的優點是算法的原理和實現步驟簡單便于理解，效率高。根據實驗結果，可以得出如下結論，MeanShift算法分割結果的好壞和分割的效率取決于帶寬參數的設定，如何有效的選取帶寬參數對于迭代結果來說有著重要的影響。為使MeanShift算法更好地在實際生活中應用應著重針對核函數進行改進。

2 K均值（K-Means）算法

K均值聚類算法步驟如下：

（1）確定分類數K；

（2）初始化K個聚類中心；

（3）依次計算每個樣本到這K個聚類中心的距離；

（4）根據距離最小原則把樣品分配到最近的聚類中心；

（5）重新進行歸類，更新聚類中心；

（6）重復步驟（3），（4），（5），（6）直到新的聚類中心和原來的聚類中心相等或小于指定范圍，聚類結束。

根據K-Means算法原理在MATLAB 2013a編程實現K-Means算法對圖像的彩色聚類分割。通過改變分類數目測試其對實驗結果的影響從而得出結論。設定初始聚類中心隨機產生，均值收斂時停止的閾值為10-2。不同K取值的彩色圖像分割結果如下：

圖3 K均值聚類算法彩色分割結果

根據圖3結果所示，當k為3、4、5時建筑物整體被分割出來，且邊緣明顯，但是建筑物的門和欄桿沒有分割出來，當k為6時，建筑物與天空分界明顯，且無顏色混淆，當k為7、8、9時，建筑物主體被分為兩類，分割效果不好。根據分析針對該算法和該圖像最合適的分類數目為6。

K-Means算法是非參數的分類方法，其優點是原理簡單易懂，可以很容易的實現，算法效率也很高。但在其聚類過程中需要先驗條件，穩定性較差。根據實驗結果，可以得出如下結論，設定不同的分類數目得到的分割結果是不同的，為了得到較好的分割結果，對該算法的初始聚類中心和聚類數目的選取是至關重要的。

3 模糊C均值聚類（FCM）算法

FCM算法是柔性劃分的無監督分類算法。FCM算法把n個向量xi（i=1，2，…，n）分為c個模糊組，并求每組的聚類中心，使得非相似性指標的價值函數達到最小[8]。與引入模糊劃分相適應，隸屬矩陣U允許有取值在[0，1]間的元素，加上歸一化規定，一個數據集的隸屬度的和總等于1[9]。FCM算法的目標函數如下：

FCM算法的最終結果是產生一個隸屬度矩陣，根據各個數據點屬于這些類別的概率大小來分類，屬于哪一類的隸屬度最大，就把這個數據點分到哪一類。

FCM算法步驟如下：

（1）確定分類數k、隨機初始化隸屬度矩陣U和加權指數m；

（2）根據聚類中心的迭代公式確定k個聚類中心；

（3）計算目標函數。如果小于某個特定的值，則算法停止；

（4）迭代隸屬度函數公式重新計算U矩陣，返回步驟（2）。

根據FCM算法的原理在MATLAB 2013a編程實現FCM算法對圖像的彩色聚類分割。通過改變分類數目測試其對實驗結果的影響從而得出結論。設定初始聚類中心隨機產生，均值收斂時停止的閾值為10-2，加權指數為2。不同分類數目的圖像分割結果如圖4所示：

圖4 模糊C均值聚類算法彩色分割結果

根據圖4所示，當k為3時建筑物整體被分割出來，且邊緣明顯，但小部分天空出現錯分割。當k為4、5、6、7、8、9時，建筑物主體分類太多，分割效果不好。據此，針對該算法和該圖像較合適的分類數目為3。

FCM算法是通過隸屬度函數來判斷樣本點的歸屬哪個聚類中心，使得對樣本點的分類更加合理。根據實驗結果，可以得出以下結論，該算法對初始值和分類數的選擇是非常重要的，如果選擇的初始值與全局聚類中心偏差的太遠，會使得該算法的迭代次數大大增加、收斂速度變慢，增加了計算時間，而且分類數不能提前確定。因此對于FCM算法來說，要使聚類達到全局最優，如何選擇初始值和確定分類數目是FCM算法的關鍵問題。

4 三種算法對灰度圖像的分割

在MATLAB 2013a上編程實現三種算法對灰度圖像的分割。參數設置和結果如表1所示，根據MeanShift算法的原理選擇一個初始聚類中心，而K-Means算法和FCM算法選取四個相同的聚類中心，得到迭代所用時間、確定的最終聚類中心和分割效果圖。

圖5 灰度圖像分割結果

圖5所示圖片從左至右依次為彩色圖像轉換的灰度圖、MeanShift算法分割結果、K-Means算法分割結果和FCM算法分割結果。根據圖5所示可以看出Mean-Shift算法分割邊界鮮明，且錯誤分類少，K-Means算法的分割效果差，FCM算法有小部分天空同建筑物主體灰度一樣。據此可得對該灰度圖像而言，分割效果最理想的是MeanShift算法。針對本實驗所設定的初始聚類中心并不適用于所有圖像，需根據具體問題自主選擇。

5 結語

通過分割效果圖可以看出各種算法參數設定的不同，分割效果也不同，當對彩色圖像進行彩色聚類和對該彩色圖像的灰度圖像所得到的結果是不盡相同的，在對彩色圖像的分割實驗中，其中分割所用時間最長的是MeanShift算法，最短的是K-Means算法。對比KMeans算法和FCM算法對灰度圖像的分割，可以看出雖然選取同樣的初始聚類中心和分類數目，但得到的實驗結果是不同的。

三種圖像分割算法對建筑物的分割各有其優缺點。MeanShift不需要任何的參數，但其受核函數帶寬的影響比較大，可能出現分割過度或者分割不完全的現象。K-Means算法雖然簡單易懂并且效率很高，但它的自適應性不好，需要先設定初始聚類中心和聚類數目，使得聚類效果很不穩定，分割極有可能達不到很好的效果。與K-Means算法相比較來說，FCM算法對樣本的分類更合理但仍然需要事先確定一些參數，且其迭代過程計算量大。在實際應用中，我們需要選取合適的算法，并且不同的問題具體分析根據不同的需要對選取的算法進行合適的改進得到較滿意的結果。

表1 三種算法對灰度圖分割比較

[1]焦玉斌，徐艷蕾，陳喜龍.圖像分割研究綜述[J].科技創新導報，2009（13）:11-11.

[2]張毅飛，呂科，代雙鳳，等.基于均值漂移的遙感圖像海陸邊界分割算法[J].光學技術，2016（1）:39-45.

[3]鄒秋霞，楊林楠，彭琳，等.基于Lab空間和K-Means聚類的葉片分割算法研究[J].農機化研究，2015（9）:222-226.

[4]王建鋒，于鎮赫，賈云亮，等.基于改進模糊聚類算法的路面裂紋圖像分割[J].計算技術與自動化，2015（4）:101-104.

[5]葉茂鍬，周武能，朱黎博.基于Mean-Shift的圖像文本信息提取[J].微型電腦應用，2009，25（7）:51-53.

[6]ChengY.MeanShift，ModeSeeking，Clustering[J].IEEE Transactionson Pattern Analysis&Machine Intelligence，1995，17（8）:790-799.

[7]謝劍斌.視覺機器學習20講[J]，2015.

[8]李茂寬，姜濤，關鍵.基于半徑/中心約束的模糊C-球殼聚類算法[J].光電工程，2011，38（4）:41-47.

[9]王瑞花，宋建社.基于改進FCM算法的SAR圖像分類[J].西北大學學報:自然科學版，2008，38（4）:574-578.

Application of Three Kinds of Clustering Algorithm in Building Image Segmentation

ZHOU Ting-ting，ZHANG Hong-bo，PAN Li-jing

（School of Physics and Electronic-Electrical Engineering，Ningxia University，Yinchuan 750021）

Describes the principle of the three clustering algorithms(MeanShift,K-Means,FCM).The color clustering segmentation and gray clustering segmentation of a building image in the Berkeley Segmentation Dataset and Benchmark500(BSDS500)picture library are programmed and implemented in MATLAB 2013a.According to the experimental results,compares and analyzes the advantages and disadvantages of the three clustering algorithms from the parameter setting,segmentation effect and segmentation time.Finally,draws the conclusion.

Clustering Algorithms;MeanShift;K-Means;FCM

1007-1423（2017）02-0076-05

10.3969/j.issn.1007-1423.2017.02.019

周婷婷（1992-），女，山東海陽人，碩士研究生，研究方向為模式識別與圖像處理

2016-11-25

2017-01-10

張虹波（1972-），女，浙江黃巖人，碩士，高級工程師，研究方向為物聯網

潘麗靜（1992-），女，福建莆田人，碩士研究生，研究方向為模式識別與圖像處理