摘要：所以不妨試試查找二叉樹這樣的數(shù)據(jù)結(jié)構(gòu)，二叉樹的優(yōu)勢在于每次查找的時間會指數(shù)級下降，以此加快程序運(yùn)行。綜合起來看，在一定的樣本量區(qū)間，還是使用原生的效率更高，這個區(qū)間在本文指的是種顏色，當(dāng)然我還是相信當(dāng)顏色更多的時候，二叉樹還是有它的優(yōu)勢的。

本文github項目：colorful color
我的codepen鏈接：圖像顏色提取
the demo
原創(chuàng)文章，轉(zhuǎn)載請注明

最近想找個小項目練練手，以便熟悉React，于是想到了“圖像顏色提取”這個方向，也有的說法是圖像主題色提取，顏色量子化，或者是叫由圖像生成調(diào)色板，原因無他，只是因為漂亮！

“分析”的目的有這么幾個：

主要顏色： main color 就是出現(xiàn)頻率最高的顏色，這樣色顏色在設(shè)計中常常是用于背景色，提供沉浸式的體驗：

平均顏色： average color 是所有顏色的平均值，和主要顏色一樣可以用作背景色；

顏色量子化： 顏色量子化在這里相當(dāng)于是在提取主題色，結(jié)果是圖像中一系列主要顏色的集合，這些顏色可以通過統(tǒng)計分析得到，也可以通過聚類算法生成。同時，主要顏色，平均顏色和主題色這幾個因子都可以作為圖像的特征，特征可以用于圖像進(jìn)一步分析，比如圖像識別與檢索，壓縮等；

顏色可視化： 圖像本身就是顏色的容器，這個“容器”也是一種可視化的呈現(xiàn)，我想我們也可以從另一個角度觀察顏色——去除圖像內(nèi)容，僅呈現(xiàn)不同顏色的值和他們的權(quán)重，比如下面這樣星星點點像星空一樣可視化方案：

中位切分算法首先把所有像素映射到RGB空間，在這個三維的空間里反復(fù)切分出子空間，最后將切分空間的像素求均值作為提取結(jié)果。分割區(qū)塊時都選擇所有區(qū)塊中最大（最長的邊長最大，或體積最大，或像素最多）的區(qū)塊，切割點應(yīng)位于邊方向上，使得分割后兩個區(qū)塊的像素各一半的位置，以上是為中位切分法。流程如下（推薦閱讀：《Color Quantization》）：

1.像素映射到RGB空間：

2.區(qū)塊計算：

3.中位切分：

4.反復(fù)切分：

5.計算區(qū)塊的平均顏色：

這里推薦一個采用中位切分法實現(xiàn)（JavaScript）的顏色量子化項目：Color Thief。

八叉樹算法的核心理念是用八叉樹來劃分顏色空間，然后合并葉節(jié)點來逐步聚攏顏色（量子化），八叉樹的解釋可參考《游戲場景管理的八叉樹算法是怎樣的？》，關(guān)鍵就是下面這兩幅圖：

1.建樹過程：

2.合并葉節(jié)點：

具體的解釋可參考文章：《圖片主題色提取算法小結(jié)》，作者還寫了一個顏色量子化的node模塊： A theme color extractor module for Node.js

K均值聚類的思想十分簡單，可分這幾步：

選取初始的K個質(zhì)心；

按照距離質(zhì)心的遠(yuǎn)近對所有樣本進(jìn)行分類；

重新計算質(zhì)心，判斷是否退出條件：

兩次質(zhì)心的距離足夠小視為滿足退出條件；

不退出則重新回到步驟2；

來看js的實現(xiàn)：

/*
colors: 所有樣本
seeds: 初始質(zhì)心
max_step: 最大迭代次數(shù)
*/
kMC(colors, seeds, max_step) {
    let iteration_count = 0;
    while (iteration_count++ < max_step) {
      // divide colors into different categories with duff"s device
      classifyColor(colors, seeds);

      // compute center of category
      let len = colors.length;
      let hsl_count = [];
      let category;
      while (len--) {
        category = colors[len].category;
        // ......
      }
      
      // quit or not
      let flag = hsl_count.every((ele, index) => {
        // ......
      });
      if (flag) {
        break;
      }
    }
    console.log("KMC iteration " + iteration_count);
  }

canvas讀取本地圖像，做適當(dāng)縮放；

統(tǒng)計顏色信息：顏色需要做量子化處理（Color Quantization），RGB空間中一共有255的三次方約1600多萬種顏色，除以8能降采樣到32000多種。RGB值組合為鍵值，統(tǒng)計每種顏色出現(xiàn)的次數(shù)：

let r_key = Math.floor(r / 8) * 1000000;
let g_key = Math.floor(g / 8) * 1000;
let b_key = Math.floor(b / 8);
let key = r_one + g_one + b_one;
if(keys.indexOf(key)<0){
  // 未找到key，則新加入key
}else{
  // 找到則出現(xiàn)次數(shù)加1
}

過濾顏色：過濾孤立的顏色（出現(xiàn)次數(shù)太少）和過亮過黑的顏色；

K均值聚類：選取出現(xiàn)頻率最高的K種顏色所謂初始值，由算法聚類出新的穩(wěn)定的顏色中心；

計算主要顏色和均值顏色；

這張圖的原始分辨率是 1080 x 1800 ，縮放到canvas中分辨率是 216 x 360 （縮放規(guī)則是固定最大高度為360，按原始寬高比例縮放）。選擇顏色降采樣的間隔為 5，一共是提取了 6251 種顏色，過濾掉出現(xiàn)次數(shù)小于 4 和過黑過亮的顏色后剩余 2555 種顏色。K均值聚類的K設(shè)為 6 ，最終迭代次數(shù)是 10 ，耗時 106ms。

codepen的原始例子如下：

census color

這方案執(zhí)行下來會有一些問題：

K均值種子點的選取對結(jié)果的影響較大；

計算聚類中心的時候不光是RGB三個值，還加入了顏色出現(xiàn)次數(shù)這個值，所以K比較小時，新的聚類中心可能不會收斂到醒目的點綴顏色上，這和我們的視覺感受是不一致的，但是如果選擇K為10，對于上面的圖像是能夠收斂到紅色的。

這部分采用了brain，它應(yīng)該是簡單的BP神經(jīng)網(wǎng)絡(luò)。訓(xùn)練數(shù)據(jù)采用的是圖蟲網(wǎng)的熱門圖片。目前帶評分的圖像數(shù)據(jù)庫比較少，而且評分往往是綜合的，摻雜了其它（構(gòu)圖，主題，光影，人物等）因素，難以分離出只與色彩相關(guān)的評分，所以我是按照自己的喜好對訓(xùn)練數(shù)據(jù)進(jìn)行了評分，所以結(jié)果會非常強(qiáng)烈的接近我個人的喜好。
另外神經(jīng)網(wǎng)絡(luò)的輸入項也是比較關(guān)鍵的，因為它必須要正確反映顏色相關(guān)的圖像信息，我提取的是：

let info = {
  colorCount: (Math.log10(colorInfo.length)),
  average:0,
  variance: 0,
  top50Count: 0,
  top50Average: 0,
  top50Variance: 0,
  top20Count: 0,
  top20Average: 0,
  top20Variance: 0,
  top10Count: 0,
  top10Average: 0,
  top10Variance: 0,
  top5Count: 0,
  top5Average: 0,
  top5Variance: 0
};

數(shù)據(jù)分為四類，評分從高到低分別是：100，85，75，65。

之前是采用的RGB空間，三個冷冰冰的數(shù)字并不能讓我們很好的分辨不同色彩，于是這里我試著轉(zhuǎn)換到HSL空間：色相(H)、飽和度(S)、明度(L)，這三個顏色通道相互之間的疊加能得到各式各樣的顏色，這個顏色空間幾乎包括了人類視力所能感知的所有顏色，是目前運(yùn)用最廣的顏色系統(tǒng)之一。
RGB和HSL的轉(zhuǎn)換可參考《javascript HEX十六進(jìn)制與RGB, HSL顏色的相互轉(zhuǎn)換》。

轉(zhuǎn)換到HSL空間對于我們提取顏色的目標(biāo)有以下好處：

原來的RGB中三個值一樣重要，對于HSL我們可以使用不同的參數(shù)分別去處理三個通道，比如對于色相可以稠密采樣，對于明度和飽和度可以適當(dāng)稀疏采樣；

對于不同顏色的控制更加精細(xì)準(zhǔn)確，原始的RGB空間中我們很難判斷兩個不同顏色之間他們的RGB值關(guān)系，但是對于HSL我們只要關(guān)注色相就可以了（其它兩個通道也很有用，只是這里選擇忽略它們）；

影響整個算法運(yùn)行時間的關(guān)鍵步驟是顏色信息的統(tǒng)計，而統(tǒng)計環(huán)節(jié)中最耗時的是key的檢測，存儲key的容器長度會越來越長，采用indexOf的方式會越來越耗時，實驗證明絕大部分的時間都是耗費(fèi)在這一步上。所以不妨試試查找二叉樹這樣的數(shù)據(jù)結(jié)構(gòu)，二叉樹的優(yōu)勢在于每次查找的時間會指數(shù)級下降，以此加快程序運(yùn)行。
但是，我用js實現(xiàn)這種數(shù)據(jù)結(jié)構(gòu)的結(jié)果并不理想，運(yùn)行時間基本與indexOf一致，甚至大部分時候還會略微多一點。我覺得原因在于：雖然每次查找重復(fù)key的時間減少了，但是每次新加入key的步驟變得復(fù)雜了，而且indexOf()是 native code ，運(yùn)行效率應(yīng)該比我們自己實現(xiàn)的js代碼高。綜合起來看，在一定的樣本量區(qū)間，還是使用原生的indexOf效率更高，這個區(qū)間在本文指的是 1000~3000 種顏色，當(dāng)然我還是相信當(dāng)顏色更多的時候，二叉樹還是有它的優(yōu)勢的。我實現(xiàn)的代碼如下：

二叉樹前序/中序/后序遍歷

這是個非常實用的技巧（經(jīng)過我多次驗證），感覺已經(jīng)離不開它了！

let len = colors.length;
let count = (len / 8) ^ 0;
let start = len % 8;
while (start--) {
  // do something
}
while (count--) {
  // do something  
}

測試結(jié)果：jsprof。

對圖像進(jìn)行模糊可以減少色彩的種類，從而加速提取算法，這應(yīng)該是可行的，但是我還沒有加入到項目中，我探索的比較快，效果比較好的模糊算法的實現(xiàn)如下：

canvas blur

最開始只是想熟悉react，結(jié)果到后面，項目的重心就完全偏向于算法和動畫了。我覺得React對SVG還是比較友好的，各種動畫屬性都可以放到state中。個人感受SVG動畫相對于CSS的優(yōu)勢在于：更加靈活，更加容易完成復(fù)雜動畫效果，兼容性更好，底層優(yōu)化更流暢。
canvas動畫的優(yōu)勢是比較流暢，SVG動畫在移動端還是有很多肉眼可見的掉幀卡頓的，而且SVG會讓HTML變得很大很亂，可能讓有潔癖的你不舒服。

SVG halo animation

不管什么動畫最終都還是歸結(jié)于：數(shù)學(xué)，比如：

這個動畫的難點在于隨機(jī)的布局算法，關(guān)鍵在于碰撞的檢測與碰撞后的移動，本質(zhì)依賴于幾何和物理中的運(yùn)動定律：

bubble chart

這個動畫的難點在于找到一個神奇的數(shù)學(xué)公式，雖然我自己也不知道怎么回事，但是變換數(shù)學(xué)公式，有時候就能實現(xiàn)有規(guī)律的動畫，而有規(guī)律再加上色彩，很大概率就是好的動畫：

canvas wave