K-m eans聚類算法在鞋身色彩搭配方面的應用研究

曾杰，周晉，陳雨*

（1.四川大學電子信息學院智能控制研究所，四川 成都 610065；2.四川大學制革清潔技術國家工程實驗室，四川 成都 610065）

引言

在時尚行業，色彩趨勢是影響消費者購買決定的重要工具和重要因素[1]。隨著國內的微博、抖音和國外的Facebook 等社交網絡服務的發展，消費者對與色彩趨勢相關的關鍵詞和話題標簽越來越敏感[2]，因此擁有時尚品牌的公司尋求利用這種關注度來增加商品銷售額[3]。通常時尚行業的色彩趨勢以自上而下的方式受到影響，因為趨勢是在行業內設定的，然后通過在主要的時尚中心城市，如巴黎、紐約、米蘭和倫敦發散開來。Divita 在《Fashion Forecasting》一書中也提及到大部分時尚企業經常聘請顧問或訂閱色彩趨勢分析報告[4]。

綜上所述，色彩搭配是流行趨勢分析的一個重要元素，通常來說，讀取鞋類圖片中的像素點的RGB 值就可輕松取得鞋體的顏色搭配，但這樣簡單操作得到的色彩結果與圖片中鞋體的像素點呈正相關，因此本研究使用最常用的聚類算法K-means[5]來識別鞋體的H 種主要色彩。

方法

K-means 聚類方法屬于特定理論分割，其隨機選擇初始聚類中心，通過對初始聚類中心進行聚類運算來將像素分類。初始聚類中心數量和位置的選擇，直接影響到后續聚類的結果。定一個數據集X，K-means 的目標是通過最小化平方差（SSE）將X 劃分到K 個互斥的聚類S 中，其中SSE 由式1 表示

式中，||.||2表示歐式距離的L2 范數，是聚類的中心，用于計算每個點到聚類中心的均值。當K=2 或D=2 時，這是一個非確定性多項式問題，但是Lloyd 給出了一個簡單的解法[6]：從N 個點中任意選取K 個點作為初始中心，然后計算每個點到每個中心點的歐式距離并將其劃分給距離最小的類，根據分類結果重新計算新的聚類中心。重復這兩個步驟直到滿足預定義的終止條件位為止。

對于固定的D，K-means 算法的時間復雜度是每次迭代o(NK)，在本研究的顏色聚類算法中使用CIELab 色彩空間[7]，D 等于3。K-means 的主要缺點是它經常在一個局部最小值終止，并且它的輸出對集群中心的初始選擇很敏感。從顏色量化的角度來看，K-means 還有兩個額外的缺點。首先，盡管它具有線性時間復雜度，但迭代的算法使得色彩板在生成階段的計算成本很高。其次，像素映射階段是低效的，因為對于每個輸入像素，都需要對色彩板進行完整的搜索，以確定最接近的顏色。相比之下，預聚類方法通常在一個特殊的數據結構中操作和存儲調色板（通常使用二叉樹），這允許在映射階段進行快速最近鄰搜索。本研究使用三種加速方法在一定程度上緩解上述缺點。

（1）數據采樣

加快K-means 的一個直接的方法是減少數據量，可以通過對輸入的圖像數據進行采樣來實現。在本研究中，使用了兩種確定性的子抽樣方法。第一種方法在水平和垂直方向上進行2:1 的子采樣，只考慮輸入圖像像素的1/4。這種適度采樣在不降低量化質量的情況下能有效地減少計算時間。第二種方法是只對具有獨特顏色的像素進行采樣。這些像素可以使用一個哈希表來有效地確定，該哈希表使用鏈表來處理哈希沖突，其哈希函數的形式為其中x=(x1，x2，x3)表示像素點的Lab色彩空間的三個維度取值，m 為素數，序列a=(a1，a2，a3)的元素從集合{0，1，…，m-1}中隨機選取。第二種基于哈希的采樣方法進一步減少了圖像數據，因為圖像中通常包含大量重復的顏色。

（2）樣本加權

上述第二個基于哈希的采樣方法的一個重要缺點是忽略了原始圖像的顏色分布。為了解決這個問題，每個點都被分配了一個與其頻率成比例的權重。事實上這個加權過程實際上生成了一個一維的顏色直方圖。然后根據圖像中的像素數量對權重進行歸一化，以避免計算中的數值不穩定性。此外，對經典K-means 算法進行了改進，將權值加入到聚類迭代過程中。

（3）均值排序(sort-means)算法[8]

K-means 的分配階段涉及到許多冗余的距離計算。對于每個點計算到每個K 聚類中心的距離。考慮兩個聚類中心ca，cb和一個距離d，利用三角不等式，我們可以得到d(ca，cb)≤d(xi，ca)+d(xi，cb)。因此，如果我們已知2d(xi，ca)≤d(ca，cb)，我們不需要計算d(xi，cb)就可以得出d(xi，ca)≤d(xi，cb)。均值排序該算法在為每個點尋找最近的聚類中心時，通過對每個集群中心關聯的距離值進行升序排序，并借助三角不等式檢驗避免了大量的距離計算，進一步減少了距離計算的數量。在每次迭代中，點與聚類中心的距離按距離的順序遞增進行比較。如果一個中心點距離足夠遠，則跳過其余所有中心點，繼續進行下一個點。通過這種方式，均值排序算法避免了去計算所有距離中心。

本研究將樸素版的K-means 算法稱為KM，使用了上述三種預處理算法的K-means 算法稱為WSM，WSM 算法的偽代碼由算法1 表述。

算法1 WSM算法偽代碼

結果與討論

選用3 張典型的運動鞋、板鞋和靴子進行色彩搭配校驗（圖1），量化方法的效率是通過CPU 時間(以ms 為單位)來衡量的，其中包括調色板生成和像素映射階段所需的時間，所有時間數據均取100 次平均。

兩種算法都以相同的隨機中心初始化，并在20 次迭代后終止，表1 給出了K=32,64 在測試圖像上每個像素的計算距離次數和計算時間。對于KM,計算距離次數總是等于調色板大小K，因為最近鄰搜索涉及到對每個輸入像素的調色板的完整搜索。相比之下，WSM 需要的距離計算平均要少約9-12 倍，這是由于靈活的引用了三角形不等式，在幾次迭代之后，一旦聚類中心穩定下來，就可以避免許多計算。其他大多數KM 加速方法都會產生創建和更新輔助數據結構的開銷。這意味著在運算時間上運用了加速算法的K-means 相對于樸素版K-means 計算每一個距離的速度要更慢。但是表1 顯示WSM 不是這樣的，因為它通過利用原始圖像中的顏色冗余信息來減少聚類階段之前的數據量?？梢钥闯觯琖SM 實際上比KM 快9-14 倍左右。特別是特定圖像的速度與圖像中惟一顏色的數量成反比。因此，最明顯的計算加速效果出現在總體基礎色較少的鞋類圖片上，如運動鞋和靴子其基礎色偏少，因此加速效果也更好（運動鞋：K=32 時WSM比KM 快14.11 倍；靴子：K=32 時WSM 比KM 快10.77 倍）。綜上所述，WSM 能在保證輸出性能等效的情況下，顯著提高K-means 的性能。

表1 KM與WSM的性能對比

將鞋身圖片的每一個像素點導入Lab 色彩空間中，可以得到該鞋身的色彩分部圖，若將這些像素點劃分到M 個聚類中，則每個聚類可由式2 表示

使用K-means 算法進行M 個聚類的迭代計算表征鞋身的色彩模型，圖2 展示了一個基礎色相對豐富的運動鞋在M=6 時的鞋身聚類顏色分布示意圖。圖2 顯示，6 個色彩聚類結果已經能很好的識別該單張鞋類圖片的所有基礎色彩構成和每個基礎色彩的比例信息。該方法對大數據鞋類圖片進行色彩構成分析后，結合銷量等信息可用于消費者對于鞋類色彩選擇偏好的分析與預測。

結論

本研究使用K-means 算法對色彩進行聚類識別鞋身色彩搭配，同時針對樸素版K-means 算法效率低下的缺點，融入了多種預處理算法，使得取不同K 時，K-means 聚類算法的效率高了9～14 倍。單鞋的識別結果顯示，改進后的K-means 聚類算法能很好的識別鞋身的主要基礎色彩和每種基礎色彩的比例，這些提取出來的色彩搭配數據可用作分析鞋類流行趨勢的關鍵信息。