基于K-means對(duì)馬賽克瓷磚選色問題的研究

吳 妍 吳靖軒 晏 麗 向彩容

（江漢大學(xué)人工智能學(xué)院,湖北 武漢 430056）

馬賽克瓷磚是一種尺寸很小的正方形瓷磚，可用于非平整面鋪設(shè)，通過拼接可以組合成給定的文字或圖案。由于成本、技術(shù)、需求的限制，廠家一般只生產(chǎn)有限種顏色的瓷磚。為了減少人工選色的工作量，需要構(gòu)建一個(gè)智能配色系統(tǒng)，能確定原始顏色與瓷磚顏色的對(duì)應(yīng)關(guān)系，從而能夠根據(jù)圖片顏色自動(dòng)找出顏色最接近的瓷磚。

1 問題分析

本文以兩幅樣本圖片為例（圖片1和圖片2）和假定某廠當(dāng)前生產(chǎn)的瓷磚顏色開展對(duì)上述問題的研究，該問題可分為三個(gè)層面。

問題一：給定廠家目前生產(chǎn)m種顏色的瓷磚（取m=22），找出與給定圖片顏色最接近的瓷磚顏色。該問題是找到圖片顏色與指定顏色集中顏色的模型關(guān)系，并說明模型的好壞。

問題二：在只考慮圖像拼接表現(xiàn)力的情況下，若廠家想增加不同顏色的瓷磚，確定應(yīng)優(yōu)先增加哪種顏色的瓷磚。該問題是基于問題一的模型，以表現(xiàn)力最大為目標(biāo)，針對(duì)具體圖片，在瓷磚顏色庫的種類及數(shù)目固定下，增加聚類中心點(diǎn)的問題。

問題三：假定每種顏色的開發(fā)成本和技術(shù)難度相同，綜合考慮成本和表現(xiàn)效果，確定新增幾種顏色及哪幾種顏色。該問題是從實(shí)際問題出發(fā)，不考慮生產(chǎn)技術(shù)的難度，假定不同顏色瓷磚成本相同，并在問題二的基礎(chǔ)上，綜合考慮生產(chǎn)成本和表現(xiàn)力效果，尋找平衡點(diǎn)。

2 模型假設(shè)

（1）假設(shè)問題中的瓷磚實(shí)際顏色與其RGB值表示的顏色完全對(duì)應(yīng)。

（2）假設(shè)問題中的瓷磚大小相同，邊緣完好，能夠完美拼接。

（3）假設(shè)每種顏色的開發(fā)成本和技術(shù)難度是相同的。

3 符號(hào)約定

（3）△eij：表示客戶所給圖像中的第j種顏色和該廠生產(chǎn)的第i種瓷磚顏色的色差。

（4）△Eij：表示客戶所給圖像中的第j種顏色與其對(duì)應(yīng)的相近色i的色差。

（5）dij：表示第i種顏色與第j種顏色之間的距離。

4 模型建立與求解

4.1 問題一模型：K-Means聚類算法[1]

4.1.1 模型建立

（1）數(shù)據(jù)處理

圖片1包含216種顏色，圖片2包含200種顏色，其中圖片1、2的RGB值示例如表1。

表1 圖片的數(shù)據(jù)表現(xiàn)形式

①特征轉(zhuǎn)換[2-3]

RGB色彩具有R（Red）、G（Green）、B（Blue）三通道，各有256級(jí)亮度，取值從0、1、2……直到255。其三通道有較強(qiáng)的相關(guān)性，主要表現(xiàn)為若某一通道增大，則像素的其他通道值也隨之增大。

常見的顏色特征空間還有HSV空間、Lab空間等。HSV特征是一種描述顏色的方式，H（Hue）是色調(diào)，用角度量來表示，范圍是0～360；S（Saturation）是飽和度，表示成所選顏色的純度和該顏色最大的純度之間的比率，范圍是0～1；V（Value）是亮度，表示色彩的明暗程度，范圍是0～1。相比RGB，HSV特征更容易跟蹤某種確定的顏色，因此選擇將RGB特征轉(zhuǎn)換為HSV特征。RGB特征到HSV特征的變換如下式：

If H ＜0，then H=H ＋360；0 ≤V ≤1，0 ≤S ≤1，0≤H≤360。

②歸一化

本文挑選歐氏度量作為聚類度量L2，先對(duì)特征進(jìn)行歸一化。歸一化公式如下：

其中x、y分別為轉(zhuǎn)換前、后的值，MaxValue、MinValue分別為樣本的最大值和最小值。

（2）模型建立

K-means聚類是選擇k個(gè)初始聚類中心，給定度量，根據(jù)待分樣本到初始聚類中心的距離將樣本數(shù)據(jù)分到最近的聚類中心所在的類，再重新計(jì)算各個(gè)聚類的中心，重復(fù)操作至滿足條件。具體步驟如下：

第一步，將圖片中的RGB值轉(zhuǎn)換成HSV值；

第二步，將第一步的結(jié)果進(jìn)行歸一化；

第三步，采用度量L2，計(jì)算圖片中第j片與現(xiàn)有瓷磚顏色i的距離，對(duì)于圖片中的第j片，挑選距離dij中最小所對(duì)應(yīng)的第i塊瓷磚作為相似色，并記錄其編號(hào)。

4.1.2 模型結(jié)果及分析[4-5]

圖片1、圖片2基于瓷磚顏色庫挑選出了最相近的瓷磚的顏色編號(hào)。表2是以圖片1中3個(gè)顏色為例，列舉出的對(duì)應(yīng)相似瓷磚的顏色。

表2 圖片1中3個(gè)顏色和其對(duì)應(yīng)相似瓷磚顏色

挑選國際標(biāo)準(zhǔn)CIE中的色差作為描述表現(xiàn)力效果的指標(biāo)，色差值越小表明兩張圖像越相似。采用顏色的HSV值進(jìn)行計(jì)算。第j種顏色和該廠生產(chǎn)的第i種瓷磚顏色的色差計(jì)算公式如下：

計(jì)算所得圖片1、圖片2與基于圖片挑選的瓷磚顏色圖片間的色差分別為2.416、1.717，根據(jù)國際CIE的標(biāo)準(zhǔn)（如表3），所選瓷磚顏色和圖片1中顏色有一定的差距，而所選瓷磚顏色和圖片2中顏色的差距為中等，在特定應(yīng)用中可以接受。

表3 國際CIE色差標(biāo)準(zhǔn)

4.2 問題二模型：K-means聚類算法、基于目標(biāo)函數(shù)的搜索法

4.2.1 模型建立

（1）數(shù)據(jù)處理

瓷磚顏色的選擇依賴于給定圖像的顏色分布，現(xiàn)以圖片1為例來進(jìn)行顏色的挑選，先將圖像1中216種顏色的RGB值轉(zhuǎn)化為HSV值。

（2）模型建立

首先采用K-Means算法，再基于目標(biāo)函數(shù)的搜索法給定目標(biāo)函數(shù)，在給定范圍內(nèi)搜索出最優(yōu)解。具體步驟如下：

第一步，以圖片1中的216種顏色和22種瓷磚顏色為對(duì)象，采用K-means算法搜索類中心集，作為待選集K。在上述待選集K里去除已有的22種瓷磚顏色，將剩余類中心作為待選集；

第二步，將色差作為描述表現(xiàn)力效果的量，對(duì)于固定的k（k=1，2，…，10），在待選集K中挑k種顏色，并用問題一的模型對(duì)圖片1進(jìn)行鋪片，計(jì)算色差均值；

4.2.2 模型結(jié)果及分析

同時(shí)增加k種顏色所對(duì)應(yīng)的色差和顏色的RGB值如表4，可以看出隨著添加顏色個(gè)數(shù)的增加，色差逐漸減小。從模型運(yùn)行速度來說，當(dāng)同時(shí)添加10種顏色時(shí)，整個(gè)程序運(yùn)行時(shí)間為10 min左右，體現(xiàn)出該模型具有較高的準(zhǔn)確性和較好的高效性。

表4 同時(shí)增加k種顏色所對(duì)應(yīng)的色差和顏色的RGB值

4.3 問題三模型：優(yōu)化模型

4.3.1 模型建立

假設(shè)不同顏色的瓷磚生產(chǎn)成本相同，以色差描述圖像表現(xiàn)力為目標(biāo)函數(shù)，建立關(guān)于添加顏色的個(gè)數(shù)與色差的模型，同時(shí)考慮總成本與表現(xiàn)力效果的關(guān)系，尋找函數(shù)圖像的平衡點(diǎn)。

4.3.2 模型結(jié)果及分析

從圖1和圖2可以看出，當(dāng)同時(shí)增加8種顏色后，色差值趨于穩(wěn)定，其一階差分值趨于0，即該點(diǎn)為最優(yōu)解。

圖1 添加顏色的個(gè)數(shù)與圖像表現(xiàn)力的函數(shù)關(guān)系圖

圖2 添加顏色的個(gè)數(shù)與色差和色差一階差分的關(guān)系圖

5 模型改進(jìn)與優(yōu)化

為了檢驗(yàn)?zāi)Ｐ鸵唬瑢D片1中的216種顏色和圖片2中的200種顏色組合成新的圖片，并從中隨機(jī)選取200種顏色帶入模型，算得色差為3.219。根據(jù)國際CIE的標(biāo)準(zhǔn)，所選顏色和圖像3中顏色存在一定差距，在特定應(yīng)用中可以接受。對(duì)于模型二，模型分別計(jì)算了同時(shí)增加k種顏色時(shí)的色差均值，都處于國際CIE色差標(biāo)準(zhǔn)中微小到中等的范圍，說明模型泛化能力不錯(cuò)。

通過模型檢驗(yàn)可以看出，該模型具有較好的準(zhǔn)確性以及較高的效率。但模型是基于提供的一張或多張圖片來決定所增補(bǔ)瓷磚顏色的方案，為了增強(qiáng)其應(yīng)用性，可收集大量各種類型的圖片，利用圖片對(duì)該模型進(jìn)行訓(xùn)練，從而找到公共的增補(bǔ)方案，即為馬賽克瓷磚選色問題的最優(yōu)解。