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

曾杰，周晉，陳雨*

（1.四川大學(xué)電子信息學(xué)院智能控制研究所，四川 成都 610065；2.四川大學(xué)制革清潔技術(shù)國(guó)家工程實(shí)驗(yàn)室，四川 成都 610065）

引言

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

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

方法

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

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

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

（1）數(shù)據(jù)采樣

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

（2）樣本加權(quán)

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

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

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

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

算法1 WSM算法偽代碼

結(jié)果與討論

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

兩種算法都以相同的隨機(jī)中心初始化，并在20 次迭代后終止，表1 給出了K=32,64 在測(cè)試圖像上每個(gè)像素的計(jì)算距離次數(shù)和計(jì)算時(shí)間。對(duì)于KM,計(jì)算距離次數(shù)總是等于調(diào)色板大小K，因?yàn)樽罱徦阉魃婕暗綄?duì)每個(gè)輸入像素的調(diào)色板的完整搜索。相比之下，WSM 需要的距離計(jì)算平均要少約9-12 倍，這是由于靈活的引用了三角形不等式，在幾次迭代之后，一旦聚類中心穩(wěn)定下來，就可以避免許多計(jì)算。其他大多數(shù)KM 加速方法都會(huì)產(chǎn)生創(chuàng)建和更新輔助數(shù)據(jù)結(jié)構(gòu)的開銷。這意味著在運(yùn)算時(shí)間上運(yùn)用了加速算法的K-means 相對(duì)于樸素版K-means 計(jì)算每一個(gè)距離的速度要更慢。但是表1 顯示W(wǎng)SM 不是這樣的，因?yàn)樗ㄟ^利用原始圖像中的顏色冗余信息來減少聚類階段之前的數(shù)據(jù)量?？梢钥闯觯琖SM 實(shí)際上比KM 快9-14 倍左右。特別是特定圖像的速度與圖像中惟一顏色的數(shù)量成反比。因此，最明顯的計(jì)算加速效果出現(xiàn)在總體基礎(chǔ)色較少的鞋類圖片上，如運(yùn)動(dòng)鞋和靴子其基礎(chǔ)色偏少，因此加速效果也更好（運(yùn)動(dòng)鞋：K=32 時(shí)WSM比KM 快14.11 倍；靴子：K=32 時(shí)WSM 比KM 快10.77 倍）。綜上所述，WSM 能在保證輸出性能等效的情況下，顯著提高K-means 的性能。

表1 KM與WSM的性能對(duì)比

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

使用K-means 算法進(jìn)行M 個(gè)聚類的迭代計(jì)算表征鞋身的色彩模型，圖2 展示了一個(gè)基礎(chǔ)色相對(duì)豐富的運(yùn)動(dòng)鞋在M=6 時(shí)的鞋身聚類顏色分布示意圖。圖2 顯示，6 個(gè)色彩聚類結(jié)果已經(jīng)能很好的識(shí)別該單張鞋類圖片的所有基礎(chǔ)色彩構(gòu)成和每個(gè)基礎(chǔ)色彩的比例信息。該方法對(duì)大數(shù)據(jù)鞋類圖片進(jìn)行色彩構(gòu)成分析后，結(jié)合銷量等信息可用于消費(fèi)者對(duì)于鞋類色彩選擇偏好的分析與預(yù)測(cè)。

結(jié)論

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