图像主题颜色提取算法概述

可以推断，在没有任何颜色合并的情况下，插入颜色的最坏情况是64次搜索.

注意: 我们会将这种颜色的RGB分量分别添加到该节点的每个分量值中，以便最终求平均值.

一般过程是从根节点启动DFS. 如果到达的节点是叶节点，那么将累加组件和颜色的总数；否则，根据颜色的第一层的层数和颜色的色键合值获得子节点号. 如节点不存在，则创建一个子节点并将其与父节点相关联，否则直接搜索到下一层.

创建时，根据层数确定它是否是叶节点. 如果是这样，则需要对其进行标记，并且叶节点的全局数量应增加一个.

要注意的另一件事是，如果此节点不是叶节点，则将其合并到对应的可归约层的链表中，以供以后在合并颜色时使用. 有关颜色合并的内容将在后面说明.

以下是创建节点的代码:

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 内部都是以浮点型存储数值，所以位运算并没有那么高效
        // 在此使用直接转换字符串的方式提取某一位的值
        //
        // 实际上如果用位运算来做的话就是这样子的：
        //   https://github.com/XadillaX/thmclrx/blob/7ab4de9fce583e88da6a41b0e256e915a10f67/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);
    }
}

这是八叉树空间低，保真度高的另一个原因.

别忘了你的初衷.

我们使用此算法进行的是颜色量化，否则我将使用它来提取主题颜色和调色板，因此绝对可以提取一些代表性的颜色，否则RRGGBB在广阔的世界中将拥有419430400 . 颜色，如何总结？

我们可以指定八叉树不超过多少个叶节点（即，末尾可以汇总的主题颜色的数量），例如8，例如16、64或256等.

因此，当叶节点数超过我们指定的叶节点数时，我们将合并其中一个节点并将其所有子节点的数据合并到其中.

例如，我们有一个带有八个子节点的节点，所有节点都是叶子节点照片美化算法，然后将八个叶子节点的通道分量添加到该节点，然后将颜色总数添加到该节点，然后删除了八个叶节点并将此节点设置为叶节点. 然后我们一次合并了八个节点.

为什么要合并这些节点？

让我们看一下特定节点下的子节点的颜色. 它们之间有相似之处-三个组件中的前七个（如果不是最低节点则为前几个）相同，因此，例如，FF7800的颜色与其现在相同，并且父级相同节点（即其兄弟节点）:

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

集成并查看:

FE7800
FE7801
FE7900
FE7901
FF7800
FF7801
FF7900
FF7901

怎么样？他们真的很近吗？这是八叉树的本质，所有同级节点必须处于相似的颜色范围内.

因此，如果要合并，我们首先转到可简化列表的底部以找到可以合并的节点. 从列表中删除它之后，我们合并叶子节点并删除它们的叶子节点:

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++;
}

结果，最深的节点已合并. 如果已满，一次合并最多将烧掉7个节点（我的大型FFF团队很强大）.

以上功能可用，我们可以开始构建树了.

实际上，构建树的过程是遍历传入的像素颜色信息，并将每种颜色插入八叉树；在每次插入之后，确定叶节点的数量是否溢出. 及时合并.

function buildOctree(pixels, maxColors) {
    for(var i = 0; i < pixels.length; i++) {
        // 添加颜色
        addColor(root, pixels[i], 0);
        // 合并叶子节点
        while(leafNum > maxColors) reduceTree();
    }
}

构建完整个树后，我们应该获得带有maxColors叶子节点的高保真八叉树. 根节点是root.

有了这样的八叉树，我们可以从中提取想要的东西.

主题颜色提取实际上是对八叉树中其余叶节点的RGB通道分量求平均，结果是近似主题颜色. （也许有更好的方法，不是一般的方法来获得更好的主题颜色结果，但我没有参加研究，欢迎大家指正我（❀╹◡╹））

因此，我们深入遍历树，每次遇到叶子节点时，我们都会找到颜色并将其添加到数组或存储结果的任何数据结构中:

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);
        }
    }
}

由八叉树主题颜色提取算法提取的主题颜色是非调色板颜色组. 它对原始图像具有最好的保真度，但是由于没有固定的调色板，有时，搜索或需要固定值才能说明的某个场景仍然欠佳. 但这只是灵活性. 例如照片美化算法，在先以某种图片格式预先存储调色板，然后再存储每个像素的情况下，我们可以将八叉树提取的颜色用作图片调色板，这样可以在很大程度上保留此图片的保真度. 并且图片的颜色减少到一定程度.

您可以在我的Github中找到该算法的完整演示.

这是一个非常简单实用的算法.

通常的想法是提供一个调色板，将一种颜色与调色板中的颜色进行比较，并且调色板中差异最小的颜色将用作该颜色的代表.

比较的过程是分别将R / G / B通道的绝对值二乘二，然后将三个差相加. 结果就是色差.

无论如何，最后一种是调色板中哪种颜色与对比色之间的差异最小，所以就采用它.

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]++;

我在octree的先前摘要中提到的octree的缺点，即颜色不是固定的. 对于主题颜色提取需要具有一定的固定值范围并不太令人满意.

差异最小的方法太老套了.

所以我的方法是同时通过两种算法.

例如，如果我想从图像中提取少于256种颜色，我将使用八叉树来过滤超过200种颜色，然后采用这批颜色及其数量并将其投入最小插值将颜色归一化，最终结果可能是我想要的结果.

在此期间，第二步的效率可以忽略. 毕竟，如果满足上述要求，第一步的结果将超过200种颜色.

我已经实现了这种方法，并在我自己的颜色提取程序包thmclrx中使用了它. 可以看到大概的代码.

经过几天的努力，我终于在某种程度上完成了我的第一个Node.js C ++插件.

与算法有关的计算（八叉树，最小差）都放在C ++层中进行计算. 如果您有兴趣，可以阅读并帮助指出各种缺点.

此软件包的存储库位于Github上:

我认为文档已完成. 并且还可以通过

$ npm install thmclrx

安装.

进入花瓣两个月后，这次我终于触摸了一些与算法相关的工作. （我不会告诉你这不是我的任务，这是我从别人那里抢走的东西2333333ଘ（੭ˊᵕˋ）੭ *ੈ✩‧₊˚

简而言之，上面介绍了几种算法和实现. 这取决于每个人如何使用它们. 无论如何，我大致找到了使用的方式，那你呢？ （´･）ﾉ（._. `）

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/shouji/article-172837-1.html