一種改進的K-means聚類服裝圖像分割算法

高櫻萍，宋 丹，王雅靜，張軒宇

（湖南工程學院計算機與通信學院，湘潭 411104）

0 引言

服裝產(chǎn)業(yè)是我國主要的經(jīng)濟產(chǎn)業(yè)之一，近年來，隨著機器學習技術的迅速發(fā)展，服裝產(chǎn)業(yè)也得到了較大的發(fā)展，而圖像作為服裝產(chǎn)業(yè)的一種直觀、便捷的傳輸媒介，一直是研究的熱點.圖像分割作為圖像處理的第一步，是計算機視覺的基礎，同時也是圖像處理中最困難的問題之一.圖像分割的好壞對后續(xù)的服裝分類以及服裝檢索等都有著重要的影響［1-5］.近年來，圖像分割是計算機圖像處理與計算機視覺中的一個重要子領域，許多學者對圖像分割涉及的各個算法和技術都開展了許多研究［6-14］.圖像分割是指根據(jù)相似性規(guī)則將一幅圖像劃分為多個子圖像區(qū)域的過程，旨在分離圖像中具有獨特性質的區(qū)域并提出感興趣的目標，方便進一步處理.

一直以來，國內(nèi)外許多學者都對圖像分割的方法進行了深入的研究，提出了上千種分割算法，但是這些算法都有一定的不足，至今還沒有一種方法能夠完全適用于所有圖像.目前，彩色圖像分割方法主要分為以下幾大類：基于閾值的分割方法、基于聚類的分割方法、基于區(qū)域的分割方法以及基于特定理論的分割方法.

聚類是模式識別和數(shù)據(jù)挖掘中的一個重要方向，是一種無監(jiān)督學習算法，其思想是將物理或抽象對象的集合分組為由類似的對象組成的多個類的分析過程，該算法的目標就是在相似的基礎上收集數(shù)據(jù)來分類.K-means 算法作為最經(jīng)典的聚類算法，許多研究者將其用于圖像分割領域，但該算法有兩個主要的缺點，第一是聚類的數(shù)目需要預先設定，第二就是初始聚類中心的選取.

到目前為止，許多學者從不同方面對這兩個缺點進行了改進，并取得了一些進展.楊善林［2］等針對如何找到最佳聚類數(shù)k的問題，設計了一種空間聚類k值優(yōu)化算法，基本思想是在其他聚類有效性函數(shù)的基礎上，構造了距離代價函數(shù)，并將距離代價函數(shù)作為最佳聚類數(shù)的有效性檢驗函數(shù)，這樣可以大大縮小最優(yōu)解的范圍，提高算法的效率.霍鳳財［4］等提出了一種基于Lab 空間的改進K-means算法來分割彩色圖像，將圖像從RGB 轉換到Lab 空間，并用馬氏距離代替歐式距離，最后對圖像像素點進行聚類，實現(xiàn)圖像分割.Hong Yao［5］等提出了一種K-means 聚類與數(shù)學形態(tài)學相結合的方法對魚類圖像進行分割，其中聚類的最佳數(shù)目由灰度直方圖確定，聚類中心數(shù)據(jù)通過與Otsu 確定的閾值進行比較，對聚類中心數(shù)據(jù)進行過濾，并利用數(shù)學形態(tài)學的開閉運算求出魚體的輪廓.受到文獻［4］和文獻［5］的啟發(fā)，本文提出了一種改進的K-means分割算法，利用圖像灰度直方圖的峰值個數(shù)來確定聚類數(shù)k的值，并用馬氏距離代替?zhèn)鹘y(tǒng)的歐式距離.實驗結果顯示，本文提出的算法所確定的k值能夠得到較好的分割效果.

1 傳統(tǒng)的K-means算法

K-means 算法也稱為k均值聚類算法，它采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大.該算法是一種迭代求解的聚類分析算法，基本思想是初始隨機給定k個簇中心，按照最鄰近原則把待分類樣本點分到各個簇，然后按平均法重新計算各個簇的質心，從而確定新的質心，一直迭代，直到簇心的移動距離小于某個給定的值.

K-means 的目的是最小化對數(shù)據(jù)點和簇中心之間的緊密性進行采樣的目標函數(shù)，如果用數(shù)學表達式表示，計算如下：

假設簇劃分為C1，C2，……Ck，則我們的目標是最小化平方誤差E：

其中μi是簇Ci的均值向量，即質心，表達式為：

影響傳統(tǒng)K-means 算法的主要因素就是聚類數(shù)k的選擇、初始聚類中心的確定以及樣本與質心之間的距離.對于彩色圖像分割處理來說，聚類的類數(shù)往往依賴具體的應用環(huán)境和圖像分割的目的人所確定，不同的聚類數(shù)會產(chǎn)生不同的分割效果.該算法采用目標函數(shù)最小化作為聚類結束的條件，且初始聚類中心一般采用隨機選擇，不同的初始聚類中心可能會導致完全不同的聚類效果.

2 改進的K-means算法

2.1 聚類數(shù)目k

針對聚類數(shù)目難以確定的問題，本文主要采用灰度直方圖進行改進.在K-means 聚類算法中使用直方圖的峰值來作為聚類數(shù)k，其依據(jù)是K-means聚類分割是一種基于圖像灰度值和直方圖波峰波谷響應圖像灰度分布變化的一種聚類過程.圖像的灰度直方圖描述的是圖像中具有該灰度級的像素個數(shù)，而直方圖的峰值代表這些灰度級的像素規(guī)模較大，具有數(shù)量優(yōu)勢.因此本文以直方圖的峰個數(shù)來作為聚類數(shù)，即若直方圖有k個峰，則聚類數(shù)為k.本文先通過式（3）找到直方圖所有的波峰，然后根據(jù)給定的閾值進行合理選擇，若兩個相鄰峰值之間的距離小于給定的閾值，則丟棄，否則保留.

其中h（i）為第i點的像素值的個數(shù).

本文計算了相鄰兩個峰谷點的距離，并將所有計算距離的平均值作為閾值，公式如下：

其中dis（i）為相鄰峰谷點之間的距離，N為距離的個數(shù).

2.2 馬氏距離

傳統(tǒng)的K-means 算法中使用的是歐式距離，歐式距離是一個通常采用的距離定義，它是在m維空間中兩個點之間的真實距離.在二維空間中的歐式距離就是兩點之間的距離，公式如下：

歐式距離由于其計算簡單常被用來計算距離測度，但也存在著明顯的缺點.這是因為每個坐標對歐式距離的貢獻是同等的，當坐標表示測量值時，其帶有大小不等的隨機波動，在這種情況下，合理的方法是對坐標進行加權，使變化較大的坐標比變化較小的坐標有較小的權系數(shù)，這就產(chǎn)生了各種距離.當各個分量為不同性質的量時，“距離”的大小與指標的單位有關，它將樣品的不同屬性（即指標或變量）之間的差別同等對待，這一點沒有考慮到總體變異對距離遠近的影響，有時不能滿足實際要求.因此，有學者提出了馬氏距離的概念.

馬哈拉諾比斯距離（Mahalanobis Distance）簡稱馬氏距離，是由印度統(tǒng)計學家馬哈拉諾比斯提出來的，用來表示數(shù)據(jù)的協(xié)方差距離，是一種有效的計算兩個未知樣本集的相似度的方法.馬氏距離的目的就是將方差歸一化，使得特征之間的關系更加符合實際情況，它與歐式距離主要的區(qū)別就是它能考慮到各種特性之間的關系.在公式計算上，馬氏距離采用的是協(xié)方差矩陣，協(xié)方差矩陣能夠衡量多個變量之間的相關性，除此之外，還可以實現(xiàn)數(shù)據(jù)完全去相關，即在圖像處理中弱化甚至消除圖像中的相關性.

對于一個均值為μ=(μ1,μ2,μ3,…,μp)T，協(xié)方差矩陣為∑的多變量x=(x1,x2,x3,…,xp)T，其馬氏距離為：

當上式中的協(xié)方差矩陣∑-1是單位陣時，此時馬氏距離等同于歐式距離，因此歐式距離可以看作是一種特殊的馬氏距離.

對于根據(jù)距離做判別的問題來說，馬氏距離比歐式距離更適合做判別.因為它不受量綱的影響，兩點之間的馬氏距離與原始數(shù)據(jù)的測量單位無關.由標準化數(shù)據(jù)和中心化數(shù)據(jù)（即原始數(shù)據(jù)與均值之差）計算出的兩點之間的馬氏距離是相同的.

2.3 改進的K-means算法

本文主要針對K-means 算法中聚類數(shù)目k難以確定的問題進行了改進，并使用馬氏距離代替歐式距離，來得到更好的分割效果.首先讀取圖像并將圖像轉換為double 型，通過分析該圖像的直方圖得到聚類的數(shù)目k，然后根據(jù)像素間的相似性進行聚類，通過多次迭代更新聚類中心的位置，直到目標函數(shù)收斂，最后輸出分割后的結果.

該算法的主要步驟如下：

step1：首先求出輸入圖像的灰度直方圖的峰值，確定k值，即將數(shù)據(jù)集經(jīng)過聚類得到k個集合

step2：隨機選擇k個數(shù)據(jù)點作為質心.

step3：對該圖像中每一個點，計算其與每一個質心的馬氏距離，離哪個質心近，就劃分到那個質心所屬的集合.

step4：把所有數(shù)據(jù)歸好集合后，一共有k個集合.然后重新計算每個集合的質心.

step5：如果新計算出來的質心和原來的質心之間的距離小于某一個設置的閾值（表示重新計算的質心的位置變化不大，趨于穩(wěn)定，或者說收斂），此時認為聚類已經(jīng)達到期望的結果，算法終止.

step6：如果新質心和原質心距離變化很大，需要迭代step3～step5 步驟.

算法的流程圖如圖1 所示.

圖1 改進K-means算法流程圖

3 實驗結果

為了驗證本文提出的算法，實驗在windows10操作系統(tǒng)，軟件Matlab R2017a 中進行，并選取不同的k值進行對比，以此驗證本文算法的有效性.從服裝圖像數(shù)據(jù)庫中收集了126 張服裝圖片進行實驗，選取的圖像的背景均為白色，其中的一部分圖像如圖2 所示.

圖2 部分實驗圖片集

本文首先將輸入的服裝圖像轉化為灰度圖像并求出其灰度直方圖，然后對灰度直方圖進行運算處理得到符合條件的峰值點，用紅色的“*”標出.同時，為了對比不同聚類數(shù)k對圖像分割結果的影響，本文還分別選取了三個不同的k值，并在同一情況下對同一幅圖像進行分割，得到對比圖.圖3（a）、圖3（b）、圖3（c）、圖3（d）為測試實驗中的四張圖片，代表了吊帶連衣裙、背心套裝、上衣、無袖連衣裙，

圖3 示例圖片（吊帶連衣裙、背心套裝、上衣、無袖連衣裙）

圖4（a）、圖4（b）、圖4（c）、圖4（d）是每張圖片對應的灰度直方圖.

圖4 待分割圖像的灰度直方圖

根據(jù)灰度直方圖中“*”的數(shù)量，我們可以得知圖3 中四張圖片的聚類數(shù)分別為9、8、10 和9.

圖5 不同k值分割效果（其中帶*號的k值是通過直方圖的峰值數(shù)得到的）

通過上面的對比圖看出，對于圖3 中的四張圖片，聚類數(shù)k分別為9、8、10 以及9 時得到的分割效果最好.實驗結果表明，使用本文所提出的方法得出的聚類數(shù)k能夠得到更好的分割效果.

對所有實驗圖片的聚類數(shù)k進行統(tǒng)計與分析后發(fā)現(xiàn)，本文所提出的方法對于淺色的連衣裙類的服裝圖像有較好的分割效果，且該類圖像的聚類數(shù)一般在9～12 之間時分割的效果最好.同時，在實驗過程中發(fā)現(xiàn)，模特的膚色以及發(fā)色等都會對分割結果產(chǎn)生一定的影響.

表1 聚類數(shù)k的取值

4 結論

K-means 聚類算法作為一種簡單有效的算法，在圖像分割中有著廣泛的應用，但傳統(tǒng)的K-means算法的聚類數(shù)k難以確定，而且用于計算相似度的歐式距離也有一定的不足，導致圖像分割的結果往往不如人意.本文在傳統(tǒng)的K-means 算法的基礎上，提出了一種改進的K-means 算法，通過分析待分割圖像的灰度直方圖確定聚類數(shù)k，并在進行相似度計算時，采用馬氏距離代替歐式距離，實驗結果表明，本文提出的算法與傳統(tǒng)的算法相比能夠得到更好的分割效果.