三種聚類(lèi)算法在建筑圖像分割上的應(yīng)用

周婷婷，張虹波，潘麗靜

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

三種聚類(lèi)算法在建筑圖像分割上的應(yīng)用

周婷婷，張虹波，潘麗靜

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

對(duì)三種聚類(lèi)算法（MeanShift、K-Means、FCM）的原理進(jìn)行簡(jiǎn)單的闡述，針對(duì)Berkeley分割數(shù)據(jù)集和基準(zhǔn)500（BSDS500）標(biāo)準(zhǔn)圖片庫(kù)中的一張建筑物圖片在MATLAB 2013a上編程實(shí)現(xiàn)對(duì)該圖片的彩色聚類(lèi)分割和灰度聚類(lèi)分割，根據(jù)實(shí)驗(yàn)結(jié)果對(duì)三種聚類(lèi)算法從參數(shù)設(shè)置、分割效果和分割時(shí)間上進(jìn)行對(duì)比分析它們的優(yōu)缺點(diǎn)，并得出結(jié)論。

聚類(lèi)算法；MeanShift；K-Means；FCM

0 引言

圖像分割是把圖像劃分為若干有意義區(qū)域并提取感興趣目標(biāo)的圖像處理技術(shù)，圖像分割是圖像識(shí)別和計(jì)算機(jī)視覺(jué)至關(guān)重要的預(yù)處理。沒(méi)有正確的分割就不可能有正確的識(shí)別。分割技術(shù)在人臉識(shí)別、行人檢測(cè)、指紋識(shí)別和醫(yī)學(xué)影像分析中有重要的研究?jī)r(jià)值和廣泛的應(yīng)用發(fā)展前景。

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

1 均值漂移（MeanShift）算法

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

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

圖1 單位均勻核函數(shù)

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

均值漂移向量表示為：

MeanShift算法步驟：

（1）計(jì)算式mh（x）；

（2）計(jì)算式mh（x）與像素點(diǎn)間的偏移量式mh（x）-x；

（3）給定一個(gè)誤差值ε，如果‖mh（x）-x‖＜ε，說(shuō)明已經(jīng)找到概率密度最大的點(diǎn)，算法結(jié)束，否則把mh（x）賦給x，返回步驟（1）繼續(xù)執(zhí)行迭代。

根據(jù)MeanShift算法的原理在MATLAB 2013a上對(duì)MeanShift算法進(jìn)行編程實(shí)現(xiàn)對(duì)圖像的彩色聚類(lèi)分割。實(shí)驗(yàn)首先把圖像從RGB色彩空間轉(zhuǎn)換成CIELUV色彩空間，原因是對(duì)比RGB色彩空間而言，LUV色彩空間具有視覺(jué)統(tǒng)一性，并且LUV色彩空間通過(guò)歐氏距離更能較好的表現(xiàn)出不同顏色之間的相似性。歐氏距離公式：

其中d的值越小代表兩點(diǎn)之間的顏色相似度越高。分割過(guò)程中實(shí)現(xiàn)了RGB、LUV色彩空間的相互轉(zhuǎn)換和對(duì)圖片的彩色聚類(lèi)分割，通過(guò)觀察帶寬參數(shù)的不同對(duì)實(shí)驗(yàn)結(jié)果的影響從而得出結(jié)論。設(shè)定初始聚類(lèi)中心隨機(jī)產(chǎn)生，均值收斂時(shí)停止的閾值為103r，其中r代表帶寬參數(shù)。該算法對(duì)圖像的彩色分割結(jié)果如下：

圖2 均值漂移算法彩色分割結(jié)果

根據(jù)圖像分割的區(qū)域一致性和邊緣準(zhǔn)確性，由圖2可以看出當(dāng)帶寬參數(shù)為3時(shí)，建筑物主體部分顏色不統(tǒng)一，且邊界不清晰，當(dāng)帶寬參數(shù)為4、5時(shí)，建筑物窗口部分沒(méi)有與房屋同一顏色，當(dāng)帶寬參數(shù)為8時(shí)，建筑物與天空分界明顯，無(wú)雜色。當(dāng)帶寬參數(shù)為15時(shí)，部分天空出現(xiàn)錯(cuò)分現(xiàn)象。當(dāng)帶寬參數(shù)為16及以上時(shí)，建筑物主體未分割出來(lái)。根據(jù)分析，針對(duì)該算法和該圖像最合適的帶寬參數(shù)為8。

Meanshift算法的優(yōu)點(diǎn)是算法的原理和實(shí)現(xiàn)步驟簡(jiǎn)單便于理解，效率高。根據(jù)實(shí)驗(yàn)結(jié)果，可以得出如下結(jié)論，MeanShift算法分割結(jié)果的好壞和分割的效率取決于帶寬參數(shù)的設(shè)定，如何有效的選取帶寬參數(shù)對(duì)于迭代結(jié)果來(lái)說(shuō)有著重要的影響。為使MeanShift算法更好地在實(shí)際生活中應(yīng)用應(yīng)著重針對(duì)核函數(shù)進(jìn)行改進(jìn)。

2 K均值（K-Means）算法

K均值聚類(lèi)算法步驟如下：

（1）確定分類(lèi)數(shù)K；

（2）初始化K個(gè)聚類(lèi)中心；

（3）依次計(jì)算每個(gè)樣本到這K個(gè)聚類(lèi)中心的距離；

（4）根據(jù)距離最小原則把樣品分配到最近的聚類(lèi)中心；

（5）重新進(jìn)行歸類(lèi)，更新聚類(lèi)中心；

（6）重復(fù)步驟（3），（4），（5），（6）直到新的聚類(lèi)中心和原來(lái)的聚類(lèi)中心相等或小于指定范圍，聚類(lèi)結(jié)束。

根據(jù)K-Means算法原理在MATLAB 2013a編程實(shí)現(xiàn)K-Means算法對(duì)圖像的彩色聚類(lèi)分割。通過(guò)改變分類(lèi)數(shù)目測(cè)試其對(duì)實(shí)驗(yàn)結(jié)果的影響從而得出結(jié)論。設(shè)定初始聚類(lèi)中心隨機(jī)產(chǎn)生，均值收斂時(shí)停止的閾值為10-2。不同K取值的彩色圖像分割結(jié)果如下：

圖3 K均值聚類(lèi)算法彩色分割結(jié)果

根據(jù)圖3結(jié)果所示，當(dāng)k為3、4、5時(shí)建筑物整體被分割出來(lái)，且邊緣明顯，但是建筑物的門(mén)和欄桿沒(méi)有分割出來(lái)，當(dāng)k為6時(shí)，建筑物與天空分界明顯，且無(wú)顏色混淆，當(dāng)k為7、8、9時(shí)，建筑物主體被分為兩類(lèi)，分割效果不好。根據(jù)分析針對(duì)該算法和該圖像最合適的分類(lèi)數(shù)目為6。

K-Means算法是非參數(shù)的分類(lèi)方法，其優(yōu)點(diǎn)是原理簡(jiǎn)單易懂，可以很容易的實(shí)現(xiàn)，算法效率也很高。但在其聚類(lèi)過(guò)程中需要先驗(yàn)條件，穩(wěn)定性較差。根據(jù)實(shí)驗(yàn)結(jié)果，可以得出如下結(jié)論，設(shè)定不同的分類(lèi)數(shù)目得到的分割結(jié)果是不同的，為了得到較好的分割結(jié)果，對(duì)該算法的初始聚類(lèi)中心和聚類(lèi)數(shù)目的選取是至關(guān)重要的。

3 模糊C均值聚類(lèi)（FCM）算法

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

FCM算法的最終結(jié)果是產(chǎn)生一個(gè)隸屬度矩陣，根據(jù)各個(gè)數(shù)據(jù)點(diǎn)屬于這些類(lèi)別的概率大小來(lái)分類(lèi)，屬于哪一類(lèi)的隸屬度最大，就把這個(gè)數(shù)據(jù)點(diǎn)分到哪一類(lèi)。

FCM算法步驟如下：

（1）確定分類(lèi)數(shù)k、隨機(jī)初始化隸屬度矩陣U和加權(quán)指數(shù)m；

（2）根據(jù)聚類(lèi)中心的迭代公式確定k個(gè)聚類(lèi)中心；

（3）計(jì)算目標(biāo)函數(shù)。如果小于某個(gè)特定的值，則算法停止；

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

根據(jù)FCM算法的原理在MATLAB 2013a編程實(shí)現(xiàn)FCM算法對(duì)圖像的彩色聚類(lèi)分割。通過(guò)改變分類(lèi)數(shù)目測(cè)試其對(duì)實(shí)驗(yàn)結(jié)果的影響從而得出結(jié)論。設(shè)定初始聚類(lèi)中心隨機(jī)產(chǎn)生，均值收斂時(shí)停止的閾值為10-2，加權(quán)指數(shù)為2。不同分類(lèi)數(shù)目的圖像分割結(jié)果如圖4所示：

圖4 模糊C均值聚類(lèi)算法彩色分割結(jié)果

根據(jù)圖4所示，當(dāng)k為3時(shí)建筑物整體被分割出來(lái)，且邊緣明顯，但小部分天空出現(xiàn)錯(cuò)分割。當(dāng)k為4、5、6、7、8、9時(shí)，建筑物主體分類(lèi)太多，分割效果不好。據(jù)此，針對(duì)該算法和該圖像較合適的分類(lèi)數(shù)目為3。

FCM算法是通過(guò)隸屬度函數(shù)來(lái)判斷樣本點(diǎn)的歸屬哪個(gè)聚類(lèi)中心，使得對(duì)樣本點(diǎn)的分類(lèi)更加合理。根據(jù)實(shí)驗(yàn)結(jié)果，可以得出以下結(jié)論，該算法對(duì)初始值和分類(lèi)數(shù)的選擇是非常重要的，如果選擇的初始值與全局聚類(lèi)中心偏差的太遠(yuǎn)，會(huì)使得該算法的迭代次數(shù)大大增加、收斂速度變慢，增加了計(jì)算時(shí)間，而且分類(lèi)數(shù)不能提前確定。因此對(duì)于FCM算法來(lái)說(shuō)，要使聚類(lèi)達(dá)到全局最優(yōu)，如何選擇初始值和確定分類(lèi)數(shù)目是FCM算法的關(guān)鍵問(wèn)題。

4 三種算法對(duì)灰度圖像的分割

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

圖5 灰度圖像分割結(jié)果

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

5 結(jié)語(yǔ)

通過(guò)分割效果圖可以看出各種算法參數(shù)設(shè)定的不同，分割效果也不同，當(dāng)對(duì)彩色圖像進(jìn)行彩色聚類(lèi)和對(duì)該彩色圖像的灰度圖像所得到的結(jié)果是不盡相同的，在對(duì)彩色圖像的分割實(shí)驗(yàn)中，其中分割所用時(shí)間最長(zhǎng)的是MeanShift算法，最短的是K-Means算法。對(duì)比KMeans算法和FCM算法對(duì)灰度圖像的分割，可以看出雖然選取同樣的初始聚類(lèi)中心和分類(lèi)數(shù)目，但得到的實(shí)驗(yàn)結(jié)果是不同的。

三種圖像分割算法對(duì)建筑物的分割各有其優(yōu)缺點(diǎn)。MeanShift不需要任何的參數(shù)，但其受核函數(shù)帶寬的影響比較大，可能出現(xiàn)分割過(guò)度或者分割不完全的現(xiàn)象。K-Means算法雖然簡(jiǎn)單易懂并且效率很高，但它的自適應(yīng)性不好，需要先設(shè)定初始聚類(lèi)中心和聚類(lèi)數(shù)目，使得聚類(lèi)效果很不穩(wěn)定，分割極有可能達(dá)不到很好的效果。與K-Means算法相比較來(lái)說(shuō)，F(xiàn)CM算法對(duì)樣本的分類(lèi)更合理但仍然需要事先確定一些參數(shù)，且其迭代過(guò)程計(jì)算量大。在實(shí)際應(yīng)用中，我們需要選取合適的算法，并且不同的問(wèn)題具體分析根據(jù)不同的需要對(duì)選取的算法進(jìn)行合適的改進(jìn)得到較滿(mǎn)意的結(jié)果。

表1 三種算法對(duì)灰度圖分割比較

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

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

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

[4]王建鋒，于鎮(zhèn)赫，賈云亮，等.基于改進(jìn)模糊聚類(lèi)算法的路面裂紋圖像分割[J].計(jì)算技術(shù)與自動(dòng)化，2015（4）:101-104.

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

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

[7]謝劍斌.視覺(jué)機(jī)器學(xué)習(xí)20講[J]，2015.

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

[9]王瑞花，宋建社.基于改進(jìn)FCM算法的SAR圖像分類(lèi)[J].西北大學(xué)學(xué)報(bào):自然科學(xué)版，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-），女，山東海陽(yáng)人，碩士研究生，研究方向?yàn)槟Ｊ阶R(shí)別與圖像處理

2016-11-25

2017-01-10

張虹波（1972-），女，浙江黃巖人，碩士，高級(jí)工程師，研究方向?yàn)槲锫?lián)網(wǎng)

潘麗靜（1992-），女，福建莆田人，碩士研究生，研究方向?yàn)槟Ｊ阶R(shí)別與圖像處理