K-means Clustering (K-means 分群)

• 前言 

mobile 連線遊戲，使用的網路數據流量往往是研發階段需要考量的一個部分，

過大的網路數據不但會造成連線時間變長，也會對 mobile 的電池消耗造成負擔。

基於上述理由，一般遊戲是不會傳輸需要龐大數據的影像圖片。

但有時為了遊戲需求，需要將玩家的自訂影像，分享給遊玩相同遊戲的其他玩家

(ex.聊天圖案或個人頭像)。

因此勢必要將圖片所佔的資料容量盡可能的縮小，

常用的方法是縮小影像的解析度或使用一些經過驗證的壓縮演算法來壓縮檔案容量。

但上述的方法在某些情況下仍無法達到理想的需求(註1)。

為此，在傳輸圖片時可能需要做一點讓步，允許傳輸的圖片產生失真，

藉此降低網路數據流量。

本篇將介紹一個失真的圖片壓縮方式，會說明其原理並使用 Unity3D 實作。

• 原理

一般的圖片是使用 RGB 格式來儲存影像資料，RGB 每個通道的數值都在 0 ~ 255 之間，

因此，對於影像的每個 pixel ，會使用 3 個 byte 來儲存該 piexl 的 RGB 值(不包含 alpha channel)

藉由這種儲存方式，影像上的每個 pixel 可以儲存 16,581,375 種顏色(= 255 x 255 x 255)。

但實際上，一般正常的影像檔案，是用不到這麼多種顏色(太接近的顏色，人眼可能也無法辨識)

如果可以找出影像使用了那些顏色，將這些顏色列表。

然後每個 pixel 使用一個索引值來指示使用的顏色，

這樣子可以大幅減少每個 pixel 所需的資料量(ex. 若只使用256個顏色，資料量會是原來的 1/3)。

甚至可以將相近的顏色合併，減少顏色清單的數量，這樣可以省去更多的資料量。

這種行為稱之為 Color quantization (顏色量化)

在了解基本原理後，接下來本篇將會使用 K-means Clustering 來實現顏色量化。

• K-means Clustering

K-means Clustering 是由 J.B. MacQueen [1] 於 1967 年所提出的分群演算法，

其目的是可以從大量樣本中，區分成 k 個群組，並從每個群組中找出一個值作為該群代表。

這演算法正好符合上段所提的需求，找出 k 個顏色來表示影像內容。

演算法原理如下，首先假設有大量不重複的樣本散落在空間中

接著，在空間中找出 k個(本範例使用 3個)不重複的參考點

對每個樣本，計算和所有的參考點的Euclidean Distance(歐幾里得距離)，

將樣本和最近的參考點歸類在同一群內。

這時計算每個群內所有樣本(不含參考點)的平均值，將這個平均值作為新的參考點，

重複上述步驟，直到所有參考點收斂(i.e. 不再變動或變化量趨近於一個極小值內)，

最後得到的參考值，可以作為該群的關鍵色，取代群內所有的樣本。

到此，就完成了對顏色量化所需要的工作。

• L*a*b* Color Space

對影像顏色作 K-means Clustering 時，需要計算顏色間的 Euclidean Distance，來找出近似色。

下圖是 RGB 在 linear space(線性空間)下， Euclidean Distance 為 0.4 的灰階漸進圖

可以看得出即使有著相同的 Euclidean Distance，顏色的變化量(中間和左邊，與中間和右邊)

似乎有點不一樣(註2)，這是因為 RGB 是儲存影像的紅色、綠色和藍色強度，

但人類其實對這三種顏色的敏感度不同(ex.人眼對綠色的變化比對紅色的變化來的敏感)，

因此用 RGB 值作為 Euclidean Distance 其實並不合適。

對此，Commission Internationale d'Eclairage(國際照明委員會)提出了 L*a*b* Color Space 

描述人眼對顏色變化的反應。

到了這裡，可以知道使用 L*a*b* Color Space 會比使用 RGB 可以得到更好的結果。

兩者的轉換代碼實作如下[3][4]：

• 實作結果

在這裡我使用影像處理論文常出現的 Lenna 圖作為參考圖片

然後利用 K-means Clustering 將圖片轉換成 256、128、64 和 32 色，

並從左到右並排展開，結果如下

仔細一看會發現有圖像失真的狀況，但仍屬於可辨識和能接受的範圍內(即使只有32色)。

如果以一張 64x64 的 32 色圖片，也只需要 2656 byte。

• References

1. MacQueen, J. B. Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press: 281–297. 1967 [2009-04-07]. MR 0214227. Zbl 0214.46201.
2. CIELAB color space
3. Color math and programming code examples
   
4. Bruce Lindbloom
   

• 附註

1. 解析度太小會造成圖樣辨識度太低，非破壞性壓縮(Lossless Compression)會有資料容量的下限及壓縮率太低的問題。
2. RGB 下的顏色變化量是否相同其實因人而異，純粹靠個人觀感沒有一定的標準。本篇是引用 Commission Internationale d'Eclairage(國際照明委員會)的論述，認為 L*a*b* Color Spcae 下顏色數值變化更接近人類觀感。