最小差值法
It's Simple
它很简单
You need a standard palette.
#FF7800 -> #FF9900
function calculate(pixel, standard) {
return Math.abs(pixel.r - standard.r) +
Math.abs(pixel.g - standard.g) +
Math.abs(pixel.b - standard.b);
}
function minDiffer(pixel) {
var minIdx = 0;
var minDiff = calculate(pixel, palette[0]);
for(var i = 1; i < palette.length; i++) {
var temp = calculate(pixel, palette[i]);
if(temp < minDiff) {
minIdx = i;
minDiff = temp;
}
}
return palette[minIdx];
}
var result = pixels.map(function(pixel) {
return minDiffer(pixel);
});
八叉树剪枝合并法
該算法最早見於 1988 年,M. Gervautz 和 W. Purgathofer 發表的論文《A Simple Method for Color Quantization: Octree Quantization》當中。其時間複雜度和空間複雜度都有很大的優勢,並且保真度也是非常的高。
《圖片主題色提取算法小結》- Chapter 2.2
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 鏈表中的下一個節點
this.next = null;
};
function addColor(node, color, level) {
if(node.isLeaf) {
node.pixelCount++;
node.red += color.r;
node.green += color.g;
node.blue += color.b;
} else {
// 由於 js 內部都是以浮點型存儲數值,所以位運算並沒有那麼高效
// 在此使用直接轉換字符串的方式提取某一位的值
//
// 實際上如果用位運算來做的話就是這樣子的:
// 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);
}
}
当叶子节点数超载了,将把一些父节点下的所有叶子节点合并到父节点。
R: 1111 1111
G: 0111 1000
B: 0000 0000
R: 1111 111 (1/0)
G: 0111 100 (1/0)
B: 0000 000 (1/0)
#FE7800
#FE7801
#FE7900
#FE7901
#FF7810
#FF7811
#FF7910
#FF7911
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;
}
// 找到最深層次的並且有可合併節點的鏈表
var lv = 6;
while(null === reducible[lv]) lv--;
// 取出鏈表頭並將其從鏈表中移除
var node = reducible[lv];
reducible[lv] = node.next;
function reduceTree() {
// 找到最深層次的並且有可合併節點的鏈表
var lv = 6;
while(null === reducible[lv]) lv--;
// 取出鏈表頭並將其從鏈表中移除
var node = reducible[lv];
reducible[lv] = node.next;
// 合併子節點
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++;
}
for i : 0 -> pixels count do
addColor(root, pixels -> i, 0)
while leafNum > maxColors then
reduceTree()
function buildOctree(pixels, maxColors) {
for(var i = 0; i < pixels.length; i++) {
// 添加顏色
addColor(root, pixels[i], 0);
// 合併葉子節點
while(leafNum > maxColors) reduceTree();
}
}
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);
}
}
}
/**
* eg.
* R: 10101101
* G: 00101101
* B: 10010010
*
* idx: 50616616
*/
unsigned char r = (color->red >> (7 - level)) & 1;
unsigned char g = (color->green >> (7 - level)) & 1;
unsigned char b = (color->blue >> (7 - level)) & 1;
int idx = (r << 2) + (g << 1) + b;
Refer Here
这套运算符针对的是整数,所以对Javascript完全无用,因为Javascript内部,所有数字都保存为双精度浮点数。如果使用它们的话,Javascript不得不将运算数先转为整数,然后再进行运算,这样就降低了速度。而且"按位与运算符"&同"逻辑与运算符"&&,很容易混淆。