? ? ?許多從自然場景中拍攝的圖像，其色彩分布上會給人一種和諧、一致的感覺；反過來，在許多界面設計應用中，我們也希望選擇的顏色可以達到這樣的效果，但對一般人來說卻并不那么容易，這屬于色彩心理學的范疇（當然不是指某些偽神棍所謂的那種）。從彩色圖像中提取其中的主題顏色，不僅可以用于色彩設計（參考網(wǎng)站：Design Seeds），也可用于圖像分類、搜索、識別等，本文分別總結并實現(xiàn)圖像主題顏色提取的幾種算法，包括顏色量化法（Color Quantization）、聚類(Clustering)和顏色建模的方法（顏色建模法僅作總結），源碼可見：GitHub: ImageColorTheme。
1. 顏色量化算法
彩色圖像一般采用RGB色彩模式，每個像素由RGB三個顏色分量組成。隨著硬件的不斷升級，彩色圖像的存儲由最初的8位、16位變成現(xiàn)在的24位、32真彩色。所謂全彩是指每個像素由8位（$2^8$=0~255）表示，紅綠藍三原色組合共有1677萬（$256*256*256$）萬種顏色，如果將RGB看作是三維空間中的三個坐標，可以得到下面這樣一張色彩空間圖：
當然，一張圖像不可能包含所有顏色，我們將一張彩色圖像所包含的像素投射到色彩空間中，可以更直觀地感受圖像中顏色的分布：
因此顏色量化問題可以用所有矢量量化（vector quantization, VQ）算法解決。這里采用開源圖像處理庫?Leptonica?中用到的兩種算法：中位切分法、八叉樹算法。
1.1. 中位切分法（Median cut）
GitHub: color-theif?項目采用了 Leptonica 中的用到的（調(diào)整）中位切分法，Js 代碼比 C 要易讀得多。中位切分算法的原理很簡單直接，將圖像顏色看作是色彩空間中的長方體（VBox），從初始整個圖像作為一個長方體開始，將RGB中最長的一邊從顏色統(tǒng)計的中位數(shù)一切為二，使得到的兩個長方體所包含的像素數(shù)量相同，重復上述步驟，直到最終切分得到長方體的數(shù)量等于主題顏色數(shù)量為止。
Leptonica 作者在報告?Median-Cut Color Quantization?中總結了這一算法存在的一些問題，其中主要問題是有可能存在某些條件下 VBox 體積很大但只包含少量像素。解決的方法是，每次進行切分時，并不是對上一次切分得到的所有VBox進行切分，而是通過一個優(yōu)先級隊列進行排序，剛開始時這一隊列以VBox僅以VBox所包含的像素數(shù)作為優(yōu)先級考量，當切分次數(shù)變多之后，將體積*包含像素數(shù)作為優(yōu)先級。
Python 3 中內(nèi)置了PriorityQueue：
1 2 3 4 5 6 7 8 9 10 11 12 | 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)先級自小到大排序 ? boxQueue.put((vbox0.priority, vbox0)) ? vbox.priority *= vbox.vol boxQueue.put((vbox0.priority, vbox0)) |
除此之外，算法中最重要的部分是統(tǒng)計色彩分布直方圖。我們需要將三維空間中的任意一點對應到一維坐標中的整數(shù)，這樣才能以最快地速度定位這一顏色。如果采用全部的24位信息，那么我們用于保存直方圖的數(shù)組長度至少要是$2^{24}=16777216$，既然是要提取顏色主題（或是顏色量化），我們可以將顏色由RGB各8位壓縮至5位，這樣數(shù)組長度只有$2^{15}=32768$：
1 2 3 4 5 6 7 8 9 10 11 12 | 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 |
分別對4張圖片進行切分、提取：
1 2 3 4 5 6 7 8 9 10 11 | 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. 八叉樹算法（Octree）
八叉樹算法的原理可以參考這篇文章：圖片主題色提取算法小結。作者也提供了 Js 實現(xiàn)的代碼，雖然與 Leptonica 中 C 實現(xiàn)的方法差別很大，但原理上是一致的。
建立八叉樹的原理實際上跟上面提到的統(tǒng)計直方圖有些相似，將顏色成分轉換成二進制之后，較低位（八叉樹中位置較深層）數(shù)值將被壓縮進較高位（八叉樹中較淺層）。八叉樹算法應用到主題色提取可能存在的問題是，每次削減掉的葉子數(shù)不確定，但是新增加的只有一個，這就導致我們需要的主題色數(shù)量并不一定剛好得到滿足，例如設定的主題色數(shù)量為7，可能上一次葉子時總數(shù)還有10個，到了下一次只剩5個了。類似的問題在后面手動實現(xiàn)的KMeans算法中也有出現(xiàn)，為了保證可以得到足夠的主題色，不得不強行提高算法中的顏色數(shù)量，然后取圖像中包含數(shù)量較多的作為主題色：
1 2 3 4 5 6 7 8 9 10 | 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])) |
對比上面兩種算法的結果：
1 2 3 4 5 6 7 | 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"]) |
可見八叉樹算法可能更適合用于提取調(diào)色板，而且兩種算法運行時間差異也很明顯：
1 2 3 | #MMCQ Time cost: 8.238793 ? #OQ Time cost: 55.173573 |
除了OQ中采用較多遞歸以外，未對原圖進行抽樣處理也是其中原因之一。
2. 聚類
聚類是一種無監(jiān)督式機器學習算法，我們這里采用K均值算法。雖然說是“機器學習”聽起來時髦些，但算法本質上比上面兩種更加簡單粗暴。
KMeans算法
KMeans算法的原理更加簡潔：“物以類聚”。我們目的是將一堆零散的數(shù)據(jù)（如上面圖2）歸為k個類別，使得每個類別中的每個數(shù)據(jù)樣本，距離該類別的中心（質心，centroid）距離最小，數(shù)學公式為：
1 | $ $ sum_{i=0}^N min_{ mu_j in C} (||x_i - mu_j||^2) $ $ |
上文提到八叉樹算法可能出現(xiàn)結果與主題色數(shù)量不一致的情況，在KMeans算法中，初始的k個類別的質心的選擇也可能導致類似的問題。當采用隨機選擇的方法時，有可能出現(xiàn)在迭代過程中，選擇的中心點距離所有其它數(shù)據(jù)太遠而最終導致被孤立。這里分別采用手動實現(xiàn)和scikit-learn的方法實現(xiàn)，根據(jù)scikit-learn 提供的API，完成主題色的提取大概只需要幾行代碼：
1 2 3 4 5 6 7 8 9 10 | 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) |
1 2 3 4 5 | 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"]) |
測試比較手動實現(xiàn)和scikit-learn的結果如下：
好吧我承認很慘，耗時方面也是慘不忍睹。
3. 色彩建模
從上面幾種算法結果來看，MMCQ和 KMeans在時間和結果上都還算不錯，但仍有改進的空間。如果從人類的角度出發(fā)，兩種算法的策略或者說在解決主題色提取這一問題時采納的特征（feature）都接近于顏色密度，即相近的顏色湊在一起數(shù)量越多，越容易被提取為主題顏色。
最后要提到的算法來自斯坦?？梢暬M13年的一篇研究：Modeling how people extract color themes from images，實際上比較像一篇心理學研究的套路：建模-找人類被試進行行為實驗-調(diào)參擬合。文章提取了圖像中的79個特征變量并進行多元回歸，同時找到普通人類被試和藝術系學生對圖像的主題顏色進行選擇，結果證明特征+回歸能夠更好地擬合人類選擇的結果。
79個特征的多元回歸模型，不知道會不會出現(xiàn)過度擬合？另外雖然比前面算法多了很多特征，但仍舊多物理特征。對人類觀察者來說，我們看到的并非一堆無意義的色塊，雖然有研究表明顏色信息并非場景識別的必要線索，但反過來場景圖像中的語義信息卻很有可能影響顏色對觀察者的意義，這大概就是心理學研究與計算機科學方向上的差異。
下載文檔
