共计 4429 个字符,预计需要花费 12 分钟才能阅读完成。
原文参考我的公众号文章 进阶!八叉树色调量化法提取图片次要色彩
体验地址,接我上一篇文章!
大抵思路
- 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;
}
参考地址:
图像主题色提取法
图片主题色提取算法小结
正文完
发表至: javascript
2022-09-27