備份自：http://blog.rainy.im/2015/11/25/extract-color-themes-from-images/
許多從自然場(chǎng)景中拍攝的圖像，其色彩分布上會(huì)給人一種和諧、一致的感覺(jué)；反過(guò)來(lái)，在許多界面設(shè)計(jì)應(yīng)用中，我們也希望選擇的顏色可以達(dá)到這樣的效果，但對(duì)一般人來(lái)說(shuō)卻并不那么容易，這屬于色彩心理學(xué)的范疇（當(dāng)然不是指某些偽神棍所謂的那種）。從彩色圖像中提取其中的主題顏色，不僅可以用于色彩設(shè)計(jì)（參考網(wǎng)站：Design Seeds），也可用于圖像分類(lèi)、搜索、識(shí)別等，本文分別總結(jié)并實(shí)現(xiàn)圖像主題顏色提取的幾種算法，包括顏色量化法（Color Quantization）、聚類(lèi)(Clustering)和顏色建模的方法（顏色建模法僅作總結(jié)），源碼可見(jiàn)：GitHub: ImageColorTheme。
1. 顏色量化算法
彩色圖像一般采用RGB色彩模式，每個(gè)像素由RGB三個(gè)顏色分量組成。隨著硬件的不斷升級(jí)，彩色圖像的存儲(chǔ)由最初的8位、16位變成現(xiàn)在的24位、32真彩色。所謂全彩是指每個(gè)像素由8位（$2^8$=0~255）表示，紅綠藍(lán)三原色組合共有1677萬(wàn)（$256*256*256$）萬(wàn)種顏色，如果將RGB看作是三維空間中的三個(gè)坐標(biāo)，可以得到下面這樣一張色彩空間圖：
當(dāng)然，一張圖像不可能包含所有顏色，我們將一張彩色圖像所包含的像素投射到色彩空間中，可以更直觀地感受圖像中顏色的分布：
因此顏色量化問(wèn)題可以用所有矢量量化（vector quantization, VQ）算法解決。這里采用開(kāi)源圖像處理庫(kù) Leptonica 中用到的兩種算法：中位切分法、八叉樹(shù)算法。
1.1. 中位切分法（Median cut）
GitHub: color-theif 項(xiàng)目采用了 Leptonica 中的用到的（調(diào)整）中位切分法，Js 代碼比 C 要易讀得多。中位切分算法的原理很簡(jiǎn)單直接，將圖像顏色看作是色彩空間中的長(zhǎng)方體（VBox），從初始整個(gè)圖像作為一個(gè)長(zhǎng)方體開(kāi)始，將RGB中最長(zhǎng)的一邊從顏色統(tǒng)計(jì)的中位數(shù)一切為二，使得到的兩個(gè)長(zhǎng)方體所包含的像素?cái)?shù)量相同，重復(fù)上述步驟，直到最終切分得到長(zhǎng)方體的數(shù)量等于主題顏色數(shù)量為止。
Leptonica 作者在報(bào)告 Median-Cut Color Quantization 中總結(jié)了這一算法存在的一些問(wèn)題，其中主要問(wèn)題是有可能存在某些條件下 VBox 體積很大但只包含少量像素。解決的方法是，每次進(jìn)行切分時(shí)，并不是對(duì)上一次切分得到的所有VBox進(jìn)行切分，而是通過(guò)一個(gè)優(yōu)先級(jí)隊(duì)列進(jìn)行排序，剛開(kāi)始時(shí)這一隊(duì)列以VBox僅以VBox所包含的像素?cái)?shù)作為優(yōu)先級(jí)考量，當(dāng)切分次數(shù)變多之后，將體積*包含像素?cái)?shù)作為優(yōu)先級(jí)。
Python 3 中內(nèi)置了PriorityQueue：
from queue import PriorityQueue as PQueue
class VBox(object):
def __init__(self, r1, r2, g1, g2, b1, b2, histo):
self.vol = calV()
self.npixs = calN()
self.priority = self.npixs * -1 # PQueue 是按優(yōu)先級(jí)自小到大排序
boxQueue.put((vbox0.priority, vbox0))
vbox.priority *= vbox.vol
boxQueue.put((vbox0.priority, vbox0))
除此之外，算法中最重要的部分是統(tǒng)計(jì)色彩分布直方圖。我們需要將三維空間中的任意一點(diǎn)對(duì)應(yīng)到一維坐標(biāo)中的整數(shù)，這樣才能以最快地速度定位這一顏色。如果采用全部的24位信息，那么我們用于保存直方圖的數(shù)組長(zhǎng)度至少要是$2{24}=16777216$，既然是要提取顏色主題（或是顏色量化），我們可以將顏色由RGB各8位壓縮至5位，這樣數(shù)組長(zhǎng)度只有$2{15}=32768$：
def getColorIndex(self, r, g, b):
return (r << (2 * self.SIGBITS)) + (g << self.SIGBITS) + b
def getPixHisto(self):
pixHisto = np.zeros(1 << (3 * self.SIGBITS))
for y in range(self.h):
for x in range(self.w):
r = self.pixData[y, x, 0] >> self.rshift
g = self.pixData[y, x, 1] >> self.rshift
b = self.pixData[y, x, 2] >> self.rshift
pixHisto[self.getColorIndex(r, g, b)] += 1
return pixHisto
分別對(duì)4張圖片進(jìn)行切分、提?。?/p>
def testMMCQ(pixDatas, maxColor):
start = time.process_time()
themes = list(map(lambda d: MMCQ(d, maxColor).quantize(), pixDatas))
print("MMCQ Time cost: {0}".format(time.process_time() - start))
return themes
imgs = map(lambda i: 'imgs/photo%s.jpg' % i, range(1,5))
pixDatas = list(map(getPixData, imgs))
maxColor = 7
themes = [testMMCQ(pixDatas, maxColor)]
imgPalette(pixDatas, themes, ["MMCQ Palette"])
1.2. 八叉樹(shù)算法（Octree）
八叉樹(shù)算法的原理可以參考這篇文章：圖片主題色提取算法小結(jié)。作者也提供了 Js 實(shí)現(xiàn)的代碼，雖然與 Leptonica 中 C 實(shí)現(xiàn)的方法差別很大，但原理上是一致的。
建立八叉樹(shù)的原理實(shí)際上跟上面提到的統(tǒng)計(jì)直方圖有些相似，將顏色成分轉(zhuǎn)換成二進(jìn)制之后，較低位（八叉樹(shù)中位置較深層）數(shù)值將被壓縮進(jìn)較高位（八叉樹(shù)中較淺層）。八叉樹(shù)算法應(yīng)用到主題色提取可能存在的問(wèn)題是，每次削減掉的葉子數(shù)不確定，但是新增加的只有一個(gè)，這就導(dǎo)致我們需要的主題色數(shù)量并不一定剛好得到滿足，例如設(shè)定的主題色數(shù)量為7，可能上一次葉子時(shí)總數(shù)還有10個(gè)，到了下一次只剩5個(gè)了。類(lèi)似的問(wèn)題在后面手動(dòng)實(shí)現(xiàn)的KMeans算法中也有出現(xiàn)，為了保證可以得到足夠的主題色，不得不強(qiáng)行提高算法中的顏色數(shù)量，然后取圖像中包含數(shù)量較多的作為主題色：
def getColors(self, node):
if node.isLeaf:
[r, g, b] = list(map(lambda n: int(n[0] / n[1]), zip([node.r, node.g, node.b], [node.n]*3)))
self.theme.append([r,g,b, node.n])
else:
for i in range(8):
if node.children[i] is not None:
self.getColors(node.children[i])
self.theme = sorted(self.theme, key=lambda c: -1*c[1])
return list(map(lambda l: l[:-1],self.theme[:self.maxColor]))
對(duì)比上面兩種算法的結(jié)果：
def testOQ(pixDatas, maxColor):
start = time.process_time()
themes = list(map(lambda d: OQ(d, maxColor).quantize(), pixDatas))
print("OQ Time cost: {0}".format(time.process_time() - start))
return themes
themes = [testMMCQ(pixDatas, maxColor), testOQ(pixDatas, maxColor)]
imgPalette(pixDatas, themes, ["MMCQ Palette", "OQ Palette"])
可見(jiàn)八叉樹(shù)算法可能更適合用于提取調(diào)色板，而且兩種算法運(yùn)行時(shí)間差異也很明顯：
#MMCQ Time cost: 8.238793
#OQ Time cost: 55.173573
除了OQ中采用較多遞歸以外，未對(duì)原圖進(jìn)行抽樣處理也是其中原因之一。
2. 聚類(lèi)
聚類(lèi)是一種無(wú)監(jiān)督式機(jī)器學(xué)習(xí)算法，我們這里采用K均值算法。雖然說(shuō)是“機(jī)器學(xué)習(xí)”聽(tīng)起來(lái)時(shí)髦些，但算法本質(zhì)上比上面兩種更加簡(jiǎn)單粗暴。
KMeans算法
KMeans算法的原理更加簡(jiǎn)潔：“物以類(lèi)聚”。我們目的是將一堆零散的數(shù)據(jù)（如上面圖2）歸為k個(gè)類(lèi)別，使得每個(gè)類(lèi)別中的每個(gè)數(shù)據(jù)樣本，距離該類(lèi)別的中心（質(zhì)心，centroid）距離最小，數(shù)學(xué)公式為：
$$
\sum_{i=0}^N \min_{ \mu_j \in C} (||x_i - \mu_j||^2)
$$
上文提到八叉樹(shù)算法可能出現(xiàn)結(jié)果與主題色數(shù)量不一致的情況，在KMeans算法中，初始的k個(gè)類(lèi)別的質(zhì)心的選擇也可能導(dǎo)致類(lèi)似的問(wèn)題。當(dāng)采用隨機(jī)選擇的方法時(shí)，有可能出現(xiàn)在迭代過(guò)程中，選擇的中心點(diǎn)距離所有其它數(shù)據(jù)太遠(yuǎn)而最終導(dǎo)致被孤立。這里分別采用手動(dòng)實(shí)現(xiàn)和scikit-learn的方法實(shí)現(xiàn)，根據(jù)scikit-learn 提供的API，完成主題色的提取大概只需要幾行代碼：
from sklearn.cluster import KMeans as KM
import numpy as np
#@pixData image pixels stored in numpy.ndarray
#@maxColor theme color number
h, w, d = pixData.shape
data = np.reshape((h*w, d))
km = KM(n_clusters=maxColor)
km.fit(data)
theme = np.array(km.cluster_centers_, dtype=np.uint8)
imgs = map(lambda i: 'imgs/photo%s.jpg' % i, range(1,5))
pixDatas = list(map(getPixData, imgs))
maxColor = 7
themes = [testKmeans(pixDatas, maxColor), testKmeans(pixDatas, maxColor, useSklearn=False)]
imgPalette(pixDatas, themes, ["KMeans Palette", "KMeans DIY"])
測(cè)試比較手動(dòng)實(shí)現(xiàn)和scikit-learn的結(jié)果如下：
好吧我承認(rèn)很慘，耗時(shí)方面也是慘不忍睹。
3. 色彩建模
從上面幾種算法結(jié)果來(lái)看，MMCQ和 KMeans在時(shí)間和結(jié)果上都還算不錯(cuò)，但仍有改進(jìn)的空間。如果從人類(lèi)的角度出發(fā)，兩種算法的策略或者說(shuō)在解決主題色提取這一問(wèn)題時(shí)采納的特征（feature）都接近于顏色密度，即相近的顏色湊在一起數(shù)量越多，越容易被提取為主題顏色。
最后要提到的算法來(lái)自斯坦?？梢暬M13年的一篇研究：Modeling how people extract color themes from images，實(shí)際上比較像一篇心理學(xué)研究的套路：建模-找人類(lèi)被試進(jìn)行行為實(shí)驗(yàn)-調(diào)參擬合。文章提取了圖像中的79個(gè)特征變量并進(jìn)行多元回歸，同時(shí)找到普通人類(lèi)被試和藝術(shù)系學(xué)生對(duì)圖像的主題顏色進(jìn)行選擇，結(jié)果證明特征+回歸能夠更好地?cái)M合人類(lèi)選擇的結(jié)果。
79個(gè)特征的多元回歸模型，不知道會(huì)不會(huì)出現(xiàn)過(guò)度擬合？另外雖然比前面算法多了很多特征，但仍舊多物理特征。對(duì)人類(lèi)觀察者來(lái)說(shuō)，我們看到的并非一堆無(wú)意義的色塊，雖然有研究表明顏色信息并非場(chǎng)景識(shí)別的必要線索，但反過(guò)來(lái)場(chǎng)景圖像中的語(yǔ)義信息卻很有可能影響顏色對(duì)觀察者的意義，這大概就是心理學(xué)研究與計(jì)算機(jī)科學(xué)方向上的差異。
總結(jié)
以上算法若要應(yīng)用還需更多優(yōu)化，例如先抽樣再處理，計(jì)算密集的地方用C/C++或并行等。另外需要一個(gè)對(duì)Python每個(gè)函數(shù)執(zhí)行時(shí)間進(jìn)行記錄的工具，分析運(yùn)行時(shí)間長(zhǎng)的部分。
參考
- Color Quantization
- Color quantization using modified median cut
- Median-Cut Color Quantization
- Wicked Code
- Clustering - scikit-learn
- Color Quantization using K-Means
- Extract Color Themes from Images
- Lin, S., & Hanrahan, P. (2013). Modeling how people extract color themes from images. Proc of Chi Acm, 3101-3110.
