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

本文github項目：colorful color
我的codepen鏈接：圖像顏色提取
the demo
原創文章，轉載請注明

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

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

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

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

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

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

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

1.像素映射到RGB空間：

2.區塊計算：

3.中位切分：

4.反復切分：

5.計算區塊的平均顏色：

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

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

1.建樹過程：

2.合并葉節點：

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

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

選取初始的K個質心；

按照距離質心的遠近對所有樣本進行分類；

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

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

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

來看js的實現：

/*
colors: 所有樣本
seeds: 初始質心
max_step: 最大迭代次數
*/
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讀取本地圖像，做適當縮放；

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

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{
  // 找到則出現次數加1
}

過濾顏色：過濾孤立的顏色（出現次數太少）和過亮過黑的顏色；

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

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

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

codepen的原始例子如下：

census color

這方案執行下來會有一些問題：

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

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

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

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
};

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

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

轉換到HSL空間對于我們提取顏色的目標有以下好處：

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

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

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

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

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

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

測試結果：jsprof。

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

canvas blur

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

SVG halo animation

不管什么動畫最終都還是歸結于：數學，比如：

這個動畫的難點在于隨機的布局算法，關鍵在于碰撞的檢測與碰撞后的移動，本質依賴于幾何和物理中的運動定律：

bubble chart

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

canvas wave