原文鏈接：http://xcoder.in/2014/09/17/theme-color-extract/

所謂主題色提取，就是對(duì)于一張圖片，近似地提取出一個(gè)調(diào)色板，使得調(diào)色板里面的顏色能組成這張圖片的主色調(diào)。

以上定義為我個(gè)人胡謅的。

大家不要太把我的東西當(dāng)成嚴(yán)謹(jǐn)?shù)奈恼聛?lái)看，很多東西什么的都是我用我自己的理解去做，并沒(méi)有做多少考證。

解析中都會(huì)以 Node.js 來(lái)寫(xiě)一些小 Demo。

引子

寫(xiě)該文章主要是為了對(duì)我這幾天對(duì)于『主題色提取』算法研究進(jìn)行一個(gè)小結(jié)。

花瓣網(wǎng)需要做一件事，就是把圖片的主題色提取出來(lái)加入到花瓣網(wǎng)搜索引擎的索引當(dāng)中，以供用戶搜索。

于是有了一個(gè)需求：提取出圖片中在某個(gè)規(guī)定調(diào)色板中的顏色，加入到搜索引擎。

接下去就開(kāi)始解析兩種不同的算法以及在這種業(yè)務(wù)場(chǎng)景當(dāng)中的應(yīng)用。

算法解析

魔法數(shù)字法

這個(gè)算法大家可以忽略，可能是我使用的姿勢(shì)不對(duì)，總之提取出來(lái)（也許它根本就不是這么用的）的東西錯(cuò)誤很大。

不過(guò)看一下也好開(kāi)闊下眼界，尤其是我這種想做游戲又不小心掉進(jìn)互聯(lián)網(wǎng)的坑里的蒟蒻來(lái)說(shuō)。

首先該算法我是從這里找到的。想當(dāng)年我還是經(jīng)常逛 GameRes 的。ヾ(;?;Д;?;)??

然后輾轉(zhuǎn)反側(cè)最終發(fā)現(xiàn)這段代碼是提取自 Allegro 游戲引擎。

具體我也就不講了，畢竟找不到資料，只是粗粗瞄了眼代碼里面有幾個(gè)魔法數(shù)字（在游戲和算法領(lǐng)域魔法數(shù)字倒是非常常見(jiàn)的），也沒(méi)時(shí)間深入解讀這段代碼。

我把它翻譯成了 Node.js，然后放在了 Demo 當(dāng)中。大家有興趣可以自己去看看。

八叉樹(shù)提取法

這個(gè)算法在顏色量化中比較常見(jiàn)的。

該算法最早見(jiàn)于 1988 年，M. Gervautz 和 W. Purgathofer 發(fā)表的論文《A Simple Method for Color Quantization: Octree Quantization》當(dāng)中。其時(shí)間復(fù)雜度和空間復(fù)雜度都有很大的優(yōu)勢(shì)，并且保真度也是非常的高。

大致的思路就是對(duì)于某一個(gè)像素點(diǎn)的顏色 R / G / B 分開(kāi)來(lái)之后，用二進(jìn)制逐行寫(xiě)下。

如 #FF7800，其中 R 通道為 0xFF，也就是 255，G 為 0x78 也就是 120，B 為 0x00 也就是 0。

接下去我們把它們寫(xiě)成二進(jìn)制逐行放下，那么就是：

R: 1111 1111
G: 0111 1000
B: 0000 0000

RGB 通道逐列黏合之后的值就是其在某一層節(jié)點(diǎn)的子節(jié)點(diǎn)編號(hào)了。每一列一共是三位，那么取值范圍就是 0 ~ 7 也就是一共有八種情況。這就是為什么這種算法要開(kāi)八叉樹(shù)來(lái)計(jì)算的原因了。

舉個(gè)例子，上述顏色的第一位黏合起來(lái)是 100(2)，轉(zhuǎn)化為十進(jìn)制就是 4，所以這個(gè)顏色在第一層是放在根節(jié)點(diǎn)的第五個(gè)子節(jié)點(diǎn)當(dāng)中；第二位是 110(2) 也就是 6，那么它就是根節(jié)點(diǎn)的第五個(gè)兒子的第七個(gè)兒子。

于是我們有了這樣的一個(gè)節(jié)點(diǎn)結(jié)構(gòu)：

var OctreeNode = function() {
    this.isLeaf = false;
    this.pixelCount = 0;
    this.red = 0;
    this.green = 0;
    this.blue = 0;

    this.children = new Array(8);
    for(var i = 0; i < this.children.length; i++) this.children[i] = null;

    // 這里的 next 不是指兄弟鏈中的 next 指針
    // 而是在 reducible 鏈表中的下一個(gè)節(jié)點(diǎn)
    this.next = null;
};

• isLeaf: 表明該節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)。
• pixelCount: 在該節(jié)點(diǎn)的顏色一共插入了幾次。
• red: 該節(jié)點(diǎn) R 通道累加值。
• green: G 累加值。
• blue: B 累加值。
• children: 八個(gè)子節(jié)點(diǎn)指針。
• next: reducible 鏈表的下一個(gè)節(jié)點(diǎn)指針，后面會(huì)作詳細(xì)解釋?zhuān)壳翱梢韵群雎浴?/li>

插入顏色

根據(jù)上面的理論，我們大致就知道了往八叉樹(shù)插入一個(gè)像素點(diǎn)顏色的步驟了。

就是每一位 RGB 通道黏合的值就是它在樹(shù)的那一層的子節(jié)點(diǎn)的編號(hào)。

大致可以看下圖：

八叉樹(shù)插入

由此可以推斷，在沒(méi)有任何顏色合并的情況下，插入一種顏色最壞的情況下是進(jìn)行 64 次檢索。

注意：我們將會(huì)把該顏色的 RGB 分量分別累加到該節(jié)點(diǎn)的各分量值中，以便最終求平均數(shù)。

大致的流程就是從根節(jié)點(diǎn)開(kāi)始 DFS，如果到達(dá)的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，那么分量、顏色總數(shù)累加；否則就根據(jù)層數(shù)和該顏色的第層數(shù)位顏色黏合值得到其子節(jié)點(diǎn)序號(hào)。若該子節(jié)點(diǎn)不存在就創(chuàng)建一個(gè)子節(jié)點(diǎn)并與該父節(jié)點(diǎn)關(guān)聯(lián)，否則就直接搜下一層去。

創(chuàng)建的時(shí)候根據(jù)層數(shù)來(lái)確定它是不是葉子節(jié)點(diǎn)，如果是的話需要標(biāo)記一下，并且全局的葉子節(jié)點(diǎn)數(shù)要加一。

還有一點(diǎn)需要注意的就是如果這個(gè)節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，就將其丟到 reducible 相應(yīng)層數(shù)的鏈表當(dāng)中去，以供之后顏色合并的時(shí)候用。關(guān)于顏色合并的內(nèi)容后面會(huì)進(jìn)行解釋。

下面是創(chuàng)建節(jié)點(diǎn)的代碼：

function createNode(idx, level) {
    var node = new OctreeNode();
    if(level === 7) {
        node.isLeaf = true;
        leafNum++;
    } else {
        // 將其丟到第 level 層的 reducible 鏈表中
        node.next = reducible[level];
        reducible[level] = node;
    }

    return node;
}

以及下面是插入某種顏色的代碼：

function addColor(node, color, level) {
    if(node.isLeaf) {
        node.pixelCount++;
        node.red += color.r;
        node.green += color.g;
        node.blue += color.b;
    } else {
        // 由于 js 內(nèi)部都是以浮點(diǎn)型存儲(chǔ)數(shù)值，所以位運(yùn)算并沒(méi)有那么高效
        // 在此使用直接轉(zhuǎn)換字符串的方式提取某一位的值
        //
        // 實(shí)際上如果用位運(yùn)算來(lái)做的話就是這樣子的：
        //   https://github.com/XadillaX/thmclrx/blob/7ab4de9fce583e88da6a41b0e256e91c45a10f67/src/octree.cpp#L91-L103
        var str = "";
        var r = color.r.toString(2);
        var g = color.g.toString(2);
        var b = color.b.toString(2);
        while(r.length < 8) r = '0' + r;
        while(g.length < 8) g = '0' + g;
        while(b.length < 8) b = '0' + b;

        str += r[level];
        str += g[level];
        str += b[level];
        var idx = parseInt(str, 2);

        if(null === node.children[idx]) {
            node.children[idx] = createNode(node, idx, level + 1);
        }

        if(undefined === node.children[idx]) {
            console.log(color.r.toString(2));
        }

        addColor(node.children[idx], color, level + 1);
    }
}

合并顏色

這一步就是八叉樹(shù)的空間復(fù)雜度低和保真度高的另一個(gè)原因了。

勿忘初心。

我們用這個(gè)算法做的是顏色量化，或者說(shuō)我要拿它提取主題色、調(diào)色板，所以肯定是提取幾個(gè)有代表性的顏色就夠了，否則茫茫世界中 RRGGBB 一共有 419430400 種顏色，怎么歸納？

我們可以讓指定一棵八叉樹(shù)不超過(guò)多少多少葉子節(jié)點(diǎn)（也就是最后能歸納出來(lái)的主題色數(shù)），比如 8，比如 16、64 或者 256 等等。

所以當(dāng)葉子節(jié)點(diǎn)數(shù)超過(guò)我們規(guī)定的葉子節(jié)點(diǎn)數(shù)的時(shí)候，我們就要合并其中一個(gè)節(jié)點(diǎn)，將其所有子節(jié)點(diǎn)的數(shù)據(jù)都合并到它身上去。

舉個(gè)例子，我們有一個(gè)節(jié)點(diǎn)有八個(gè)子節(jié)點(diǎn)，并且都是葉子節(jié)點(diǎn)，那么我們把八個(gè)葉子節(jié)點(diǎn)的通道分量全累加到該節(jié)點(diǎn)中，顏色總數(shù)也累加到該節(jié)點(diǎn)中，然后刪除八個(gè)葉子節(jié)點(diǎn)并把該節(jié)點(diǎn)設(shè)置為葉子節(jié)點(diǎn)。那么一下子我們就合并了八個(gè)節(jié)點(diǎn)有木有！

為什么這些節(jié)點(diǎn)可以被合并呢？

我們來(lái)看看某個(gè)節(jié)點(diǎn)下的子節(jié)點(diǎn)顏色都有神馬相似點(diǎn)吧——它們的三個(gè)分量前七位（或者說(shuō)如果已經(jīng)不是最底層的節(jié)點(diǎn)的話那就是前幾位）是相同的，那么比如說(shuō)剛才的 FF7800，跟它同級(jí)并且擁有相同父節(jié)點(diǎn)（也就是它的兄弟節(jié)點(diǎn)）的顏色都是什么呢：

R: 1111 111(0,1)
G: 0111 100(0,1)
B: 0000 000(0,1)

整合出來(lái)一看：

FE7800
FE7801
FE7900
FE7901
FF7800
FF7801
FF7900
FF7901

怎么樣？是不是確實(shí)很相近？這就是八叉樹(shù)的精髓了，所有的兄弟節(jié)點(diǎn)肯定是在一個(gè)相近的顏色范圍內(nèi)。

所以說(shuō)我們要合并就先去最底層的 reducible 鏈表中尋找一個(gè)可以合并的節(jié)點(diǎn)，把它從鏈表中刪除之后合并葉子節(jié)點(diǎn)并且刪除其葉子節(jié)點(diǎn)就好了：

function reduceTree() {
    // 找到最深層次的并且有可合并節(jié)點(diǎn)的鏈表
    var lv = 6;
    while(null === reducible[lv]) lv--;

    // 取出鏈表頭并將其從鏈表中移除
    var node = reducible[lv];
    reducible[lv] = node.next;

    // 合并子節(jié)點(diǎn)
    var r = 0;
    var g = 0;
    var b = 0;
    var count = 0;
    for(var i = 0; i < 8; i++) {
        if(null === node.children[i]) continue;
        r += node.children[i].red;
        g += node.children[i].green;
        b += node.children[i].blue;
        count += node.children[i].pixelCount;
        leafNum--;
    }

    // 賦值
    node.isLeaf = true;
    node.red = r;
    node.green = g;
    node.blue = b;
    node.pixelCount = count;
    leafNum++;
}

這樣一來(lái)，就合并了一個(gè)最深層次的節(jié)點(diǎn)了，如果滿打滿算的話，一次合并最多會(huì)燒掉 7 個(gè)節(jié)點(diǎn)（我大 FFF 團(tuán)壯哉）。

建樹(shù)

上面的函數(shù)都有了，我們可以開(kāi)始建樹(shù)了。

實(shí)際上建樹(shù)的過(guò)程就是遍歷一遍傳入的像素顏色信息，對(duì)于每個(gè)顏色都插入到八叉樹(shù)當(dāng)中；并且每一次插入之后都判斷下葉子節(jié)點(diǎn)數(shù)有沒(méi)有溢出，如果滿出來(lái)的話需要及時(shí)合并。

function buildOctree(pixels, maxColors) {
    for(var i = 0; i < pixels.length; i++) {
        // 添加顏色
        addColor(root, pixels[i], 0);

        // 合并葉子節(jié)點(diǎn)
        while(leafNum > maxColors) reduceTree();
    }
}

整棵樹(shù)建好之后，我們應(yīng)該得到了最多有 maxColors 個(gè)葉子節(jié)點(diǎn)的高保真八叉樹(shù)。其根節(jié)點(diǎn)為 root。

主題色提取

有了這么一棵八叉樹(shù)之后我們就可以從里面提取我們想要的東西了。

主題色提取實(shí)際上就是把八叉樹(shù)當(dāng)中剩下的葉子節(jié)點(diǎn) RGB 通道分量求平均，求出來(lái)的就是近似的主題色了。（也許有更好的，不是求平均的方法能獲得更好的主題色結(jié)果，但是我沒(méi)有深入去研究，歡迎大家一起來(lái)指正 (????)）

于是我們深度遍歷這棵樹(shù)，每遇到葉子節(jié)點(diǎn)，就求出顏色加入到我們所存結(jié)果的數(shù)組或者任意數(shù)據(jù)結(jié)構(gòu)當(dāng)中了：

function colorsStats(node, object) {
    if(node.isLeaf) {
        var r = parseInt(node.red / node.pixelCount).toString(16);
        var g = parseInt(node.green / node.pixelCount).toString(16);
        var b = parseInt(node.blue / node.pixelCount).toString(16);
        if(r.length === 1) r = '0' + r;
        if(g.length === 1) g = '0' + g;
        if(b.length === 1) b = '0' + b;

        var color = r + g + b;
        if(object[color]) object[color] += node.pixelCount;
        else object[color] = node.pixelCount;
        
        return;
    }

    for(var i = 0; i < 8; i++) {
        if(null !== node.children[i]) {
            colorsStats(node.children[i], object);
        }
    }
}

算法小結(jié)

八叉樹(shù)主題色提取算法提取出來(lái)的主題色是一個(gè)無(wú)固定調(diào)色板（Non-palette）的顏色群，它有著對(duì)原圖的盡量保真性，但是由于沒(méi)有固定的調(diào)色板，有時(shí)候?qū)τ谒阉骰蛘吣撤N需要固定值來(lái)解釋的場(chǎng)景中還是欠了點(diǎn)火候。但是活靈活現(xiàn)非它莫屬了。比如某種圖片格式里面預(yù)先存調(diào)色板然后存各像素的情況下，我們就可以用八叉樹(shù)提取出來(lái)的顏色作為該圖片調(diào)色板，能很大程度上對(duì)這張圖片進(jìn)行保真，并且圖片顏色也減到一定的量。

該算法的完整 Demo 大家可以在我的 Github 當(dāng)中找到。

最小差值法

這是一個(gè)非常簡(jiǎn)單又實(shí)用的算法。

大致的思想就是給定一個(gè)調(diào)色板，過(guò)來(lái)一個(gè)顏色就跟調(diào)色板中的顏色一一對(duì)比，取最小差值的那個(gè)調(diào)色板里的顏色作為這個(gè)顏色的代表。

對(duì)比的過(guò)程就是分別將 R / G / B 通道的值兩兩相減取絕對(duì)值，將三個(gè)差相加，得到的這個(gè)值就是顏色差值了。

反正最后就是調(diào)色板中哪個(gè)顏色跟對(duì)比的顏色差值最小，就拿過(guò)來(lái)就是了。

var best = 0;
var bestv = pal[0];
var bestr = Math.abs(r - bestv.r) + Math.abs(g - bestv.g) + Math.abs(b - bestv.b);

for(var j = 1; j < pal.length; j++) {
    var p = pal[j];
    var res = Math.abs(r - p.r) + Math.abs(g - p.g) + Math.abs(b - p.b);
    if(res < bestr) {
        best = j;
        bestv = pal[j];
        bestr = res;
    }
}

r = pal[best].r.toString(16);
g = pal[best].g.toString(16);
b = pal[best].b.toString(16);

if(r.length === 1) r = "0" + r;
if(g.length === 1) g = "0" + g;
if(b.length === 1) b = "0" + b;

if(colors[r + g + b] === undefined) colors[r + g + b] = -1;
colors[r + g + b]++;

我是怎么做的

八叉樹(shù)的缺點(diǎn)我在之前的八叉樹(shù)小結(jié)中提到過(guò)了，就是顏色不固定。對(duì)于需要有一定固定值范圍的主題色提取需求來(lái)說(shuō)不是那么合人意。

而最小差值法的話又太古板了。

于是我的做法是將這兩種算法都過(guò)一遍。

比如我要將一張圖片提取出少于 256 種顏色，我會(huì)用八叉樹(shù)過(guò)濾一遍得出保證的兩百多種顏色，然后拿著這批顏色和其數(shù)量再扔到最小插值法里面將顏色規(guī)范化一遍，得出的最終結(jié)果可能就是我想要的結(jié)果了。

這期間第二步的效率可以忽略不計(jì)，畢竟如果是上面的需求的話第一步的結(jié)果也就那么兩百多種顏色。

這個(gè)方法我已經(jīng)實(shí)現(xiàn)并且用在我自己的顏色提取包 thmclrx 里了。大致的代碼可以看這里。

主題色提取 Node.js 包——thmclrx

在這幾天的辛勤勞作下，總算完成了某種意義上我的第一個(gè) Node.js C++ Addon。

跟算法相關(guān)（八叉樹(shù)、最小差值）的計(jì)算全放在了 C++ 層進(jìn)行計(jì)算。大家有興趣的可以去讀一下并且?guī)兔χ赋龈鞣N各樣的缺點(diǎn)，算是拋磚引玉了。

這個(gè)包的 Repo 在 Github 上面：

https://github.com/XadillaX/thmclrx

文檔自認(rèn)為還算完整吧。并且也可以通過(guò)

$ npm install thmclrx

進(jìn)行安裝。

本文小結(jié)

進(jìn)花瓣兩個(gè)月了，這一次終于如愿以償?shù)嘏鲇|到了一點(diǎn)點(diǎn)的『算法相關(guān)』的活。（我不會(huì)告訴你這不是我的任務(wù)，是我從別人手中搶來(lái)的 2333333 ?(?ˊ?ˋ)?* ?????

總之幾種算法和實(shí)現(xiàn)在上方介紹了，具體需要怎么用還是要看大家自己了。我反正大致找到了我使用的途徑，那你們呢。( ′??)?(._.`)