原文参考我的公众号文章 进阶！八叉树色调量化法提取图片次要色彩
体验地址，接我上一篇文章！
大抵思路
- 1.构建八叉树，将 rgb 色彩循环增加到树里（雷同的色彩会跑到同一层的同一个叶子结点上，累加 count）；
- 2.当叶子结点数量超过指定最大色彩数时，进行叶子结点合并（类似的色彩会跑到同一个父节点，与兄弟结点同级，因而能够合并到他们的父节点）；
- 3.计算调色盘（递归遍历八叉树，累加所有叶子节点的 r,g,b 色彩值再均匀）；
为什么是八叉树？
比方有这么一个色彩 rgb = [31, 31, 30]，给出它的入树过程！//r = 31 => 00011111//g = 31 => 00011111//b = 30 => 00011110r,g,b每个色彩位转换成了8位二进制用0,1示意，同时从左到右取r,g,b的每一位组成3位二进制数。比方取第1位，组成列：000，转换成十进制就是 0，进入八叉树中第1层，的第1个结点；比方取第2位，组成列：000，转换成十进制就是 0，进入八叉树中第2层，的第1个结点；比方取第3位，组成列：000，转换成十进制就是 0，进入八叉树中第3层，的第1个结点；比方取第4位，组成列：111，转换成十进制就是 7，进入八叉树中第4层，的第8个结点；比方取第5位，组成列：111，转换成十进制就是 7，进入八叉树中第5层，的第8个结点；比方取第6位，组成列：111，转换成十进制就是 7，进入八叉树中第6层，的第8个结点；比方取第7位，组成列：111，转换成十进制就是 7，进入八叉树中第7层，的第8个结点；比方取第8位，组成列：110，转换成十进制就是 6，进入八叉树中第8层，的第7个结点（叶子结点，累加r,g,b重量，累加pixelCount）；依照上述规定，可能将反复呈现的色彩累加到第 8 层的某一个叶子结点中!
网上找了个图形象阐明一下！
（图片来源于网络）
// 比方有这么几个像素色彩信息：let pixels = [ [31, 31, 30], [31, 31, 31], [31, 31, 31],]// 最终失去色彩的统计状况会是：let colors = { '31,31,30': 1, '31,31,31': 2 }构建树结点
class OctTreeNode { constructor(level) { this.color = []; this.level = level; this.isLeaf = false; this.pixelCount = 0; //该节点呈现次数，当为叶子结点时，代表了某种色彩呈现次数 this.r = 0; //red通道累加值 this.g = 0; //green通道累加值 this.b = 0; //blue通道累加值 this.children = [null, null, null, null, null, null, null, null]; //八个子节点 this.next = null; //在 reducible 链表中的下一个节点 }}顺次载入像素信息，生成八叉树结构
function dec2bin(decnum, displayLength) { let bin = decnum.toString(2); if (displayLength) { while (bin.length < displayLength) { bin = `0${bin}`; } } return bin;}function addColor(parentNode, color, level) { if (!color) { throw new Error("color must be provided，like [255, 0, 0]"); } let [r, g, b] = color; if (parentNode.isLeaf) { // console.warn(`已满八层，是叶子节点，rgb(${color})`); parentNode.pixelCount++; parentNode.r += r; parentNode.g += g; parentNode.b += b; return; } let binR = dec2bin(r, 8); let binG = dec2bin(g, 8); let binB = dec2bin(b, 8); // 逐列合并bin，共3行8列，需递归执行8次，生成8层树结构 let concatColBin = `${binR[level]}${binG[level]}${binB[level]}`; let index = bin2dec(concatColBin); if (!parentNode.children[index]) { parentNode.children[index] = createNode(level); } // 递归生成下一层 addColor(parentNode.children[index], color, level + 1);}为什么须要进行叶子结点合并？
一个图片中的色彩信息会十分多，通过八叉树量化后，某些像素色彩占比很大，有些很小。很小的起因可能是这种色彩自身就少，也有可能是因为它们是类似的色彩，那么将类似的色彩合并，缩小提取的色彩躁点（数量极多却极其类似的色彩）稀释就是精髓！
为什么能将叶子节点合并？
let pixel1 = [31, 31, 30]// 00011111// 00011111// 00011110let pixel2 = [31, 31, 31]// 00011111// 00011111// 00011111比照pixel1和pixel2能够看出：
前七位完全一致，只有第八位（树中的第八层，叶子节点）是不一样的，阐明这两个色彩是非常相近的色彩，
因而能够将叶子结点的r,g,b重量和pixelCount合并到他们的父节点去。合并后，叶子结点会被剔除，他们的父节点变成新的叶子结点。
如何合并叶子结点？
程序中有一个设计技巧，就是每一层的所有节点都用一个链表存储起来，reducible[i]记录了这些链表的头节点，每一次合并操作都是从最底层开始，从下到上顺次进行的。/** * 生成新结点时，顺便记录reducible链表头信息 */function createNode(level) { let node = new OctTreeNode(level); if (level == 7) { node.isLeaf = true; leafNum++; } else { // 将其丢到第 level 层的 reducible 链表中（这两行代码不能反，否则会呈现循环援用） node.next = reducible[level]; //此时reducible[level]为上一个色彩对应的 reducible[level] = node; } return node;}/** * 合并叶子结点 */function reduceTree() { // 找到最深层次的并且有可合并节点的链表 let lv = 6; while (reducible[lv] == null) lv--; // 取出链表头并将其从链表中移除 let node = reducible[lv]; reducible[lv] = node.next; //OctTreeNode or null // 合并子节点 let r = 0; let g = 0; let b = 0; let count = 0; for (let i = 0; i < 8; i++) { if (null === node.children[i]) continue; r += node.children[i].r; g += node.children[i].g; b += node.children[i].b; count += node.children[i].pixelCount; leafNum--; //叶子数量减1（其实在树结构中存在，只是叶子结点的层级移到了上一层） } // 父节点变叶子节点，重量合并 node.isLeaf = true; node.r = r; node.g = g; node.b = b; node.pixelCount = count; leafNum++;}
（图片来源于网络）
统计色彩信息！
流程比拟清晰：获取所有叶子节点r,g,b重量和pixelCount对应的平均值 color，以color为键，呈现次数count为值，记录到一个palette对象中，就失去了一个反映各个色彩占比的对象。最初再转换成数组，并依照count进行降序排序。第一项就是主色调，后续项就是调色盘色彩组了。
/** * 计算最终的色彩列表 * @param {*} node * @param {*} paletteMap * @returns */function colorsStats(node, paletteMap) { // 判断是否是叶子节点 if (node.isLeaf) { // 计算以后色彩的均匀 let r = parseInt(node.r / node.pixelCount); let g = parseInt(node.g / node.pixelCount); let b = parseInt(node.b / node.pixelCount); let color = `${r},${g},${b}`; // 统计以后色彩合并累计的次数 if (paletteMap[color]) paletteMap[color] += node.pixelCount; else paletteMap[color] = node.pixelCount; return; } // bfs递归解决色彩信息 for (let i = 0; i < 8; i++) { node.children[i] && colorsStats(node.children[i], paletteMap); }}最初调用得出指定数量的色彩
let leafNum = 0; //叶子结点数量let reducible = [null, null, null, null, null, null, null]; //存储每一层链表的表头的数组function colorThief(pixels = [], maxColors = 8) { leafNum = 0; let rootNode = new OctTreeNode(0); pixels.map((item) => { addColor(rootNode, item, 0); // 边构建，边合并叶子结点！ while (leafNum > maxColors) reduceTree(); }); console.log("合并后的八叉树结构：", rootNode); console.log(`共有${leafNum}个叶子结点`); let paletteMap = {}; colorsStats(rootNode, paletteMap); console.log("八叉树法提取的色彩有：", paletteMap); let palette = []; for (let key in paletteMap) { palette.push({ color: `${key}`, count: paletteMap[key], }); } palette.sort((a, b) => { return b.count - a.count; }); return palette;}参考地址：
图像主题色提取法
图片主题色提取算法小结