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

吳 妍 吳靖軒 晏 麗 向彩容

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

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

1 問題分析

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

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

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

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

2 模型假設

（1）假設問題中的瓷磚實際顏色與其RGB值表示的顏色完全對應。

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

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

3 符號約定

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

（4）△Eij：表示客戶所給圖像中的第j種顏色與其對應的相近色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級亮度，取值從0、1、2……直到255。其三通道有較強的相關性，主要表現(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，先對特征進行歸一化。歸一化公式如下：

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

（2）模型建立

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

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

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

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

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

圖片1、圖片2基于瓷磚顏色庫挑選出了最相近的瓷磚的顏色編號。表2是以圖片1中3個顏色為例，列舉出的對應相似瓷磚的顏色。

表2 圖片1中3個顏色和其對應相似瓷磚顏色

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

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

表3 國際CIE色差標準

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

4.2.1 模型建立

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

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

（2）模型建立

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

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

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

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

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

表4 同時增加k種顏色所對應的色差和顏色的RGB值

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

4.3.1 模型建立

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

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

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

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

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

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

為了檢驗模型一，將圖片1中的216種顏色和圖片2中的200種顏色組合成新的圖片，并從中隨機選取200種顏色帶入模型，算得色差為3.219。根據(jù)國際CIE的標準，所選顏色和圖像3中顏色存在一定差距，在特定應用中可以接受。對于模型二，模型分別計算了同時增加k種顏色時的色差均值，都處于國際CIE色差標準中微小到中等的范圍，說明模型泛化能力不錯。

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