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

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

最近想找個(gè)小項(xiàng)目練練手，以便熟悉React，于是想到了“圖像顏色提取”這個(gè)方向，也有的說(shuō)法是圖像主題色提取，顏色量子化，或者是叫由圖像生成調(diào)色板，原因無(wú)他，只是因?yàn)槠粒?/p>

“分析”的目的有這么幾個(gè)：

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

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

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

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

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

1.像素映射到RGB空間：

2.區(qū)塊計(jì)算：

3.中位切分：

4.反復(fù)切分：

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

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

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

1.建樹(shù)過(guò)程：

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

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

K均值聚類(lèi)的思想十分簡(jiǎn)單，可分這幾步：

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

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

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

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

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

來(lái)看js的實(shí)現(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)計(jì)顏色信息：顏色需要做量子化處理（Color Quantization），RGB空間中一共有255的三次方約1600多萬(wàn)種顏色，除以8能降采樣到32000多種。RGB值組合為鍵值，統(tǒng)計(jì)每種顏色出現(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
}

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

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

計(jì)算主要顏色和均值顏色；

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

codepen的原始例子如下：

census color

這方案執(zhí)行下來(lái)會(huì)有一些問(wèn)題：

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

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

這部分采用了brain，它應(yīng)該是簡(jiǎn)單的BP神經(jīng)網(wǎng)絡(luò)。訓(xùn)練數(shù)據(jù)采用的是圖蟲(chóng)網(wǎng)的熱門(mén)圖片。目前帶評(píng)分的圖像數(shù)據(jù)庫(kù)比較少，而且評(píng)分往往是綜合的，摻雜了其它（構(gòu)圖，主題，光影，人物等）因素，難以分離出只與色彩相關(guān)的評(píng)分，所以我是按照自己的喜好對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行了評(píng)分，所以結(jié)果會(huì)非常強(qiáng)烈的接近我個(gè)人的喜好。
另外神經(jīng)網(wǎng)絡(luò)的輸入項(xiàng)也是比較關(guān)鍵的，因?yà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ù)分為四類(lèi)，評(píng)分從高到低分別是：100，85，75，65。

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

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

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

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

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

二叉樹(shù)前序/中序/后序遍歷

這是個(gè)非常實(shí)用的技巧（經(jīng)過(guò)我多次驗(yàn)證），感覺(jué)已經(jīng)離不開(kāi)它了！

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

測(cè)試結(jié)果：jsprof。

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

canvas blur

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

SVG halo animation

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

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

bubble chart

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

canvas wave