关于javascript:进阶提取图片主色调

原文参考我的公众号文章 进阶！八叉树色调量化法提取图片次要色彩

体验地址，接我上一篇文章！

大抵思路

• 1. 构建八叉树，将 rgb 色彩循环增加到树里（雷同的色彩会跑到同一层的同一个叶子结点上，累加 count）；
• 2. 当叶子结点数量超过指定最大色彩数时，进行叶子结点合并（类似的色彩会跑到同一个父节点，与兄弟结点同级，因而能够合并到他们的父节点）；
• 3. 计算调色盘（递归遍历八叉树，累加所有叶子节点的 r,g,b 色彩值再均匀）；

为什么是八叉树？

比方有这么一个色彩 rgb = [31, 31, 30]，给出它的入树过程！//r = 31 =>  00011111
//g = 31 =>  00011111
//b = 30 =>  00011110
 
r,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
// 00011110
 
let 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;
}

参考地址：

图像主题色提取法

图片主题色提取算法小结