八叉树颜色面板
4.50/5 (4投票s)
八叉树颜色面板
引言
Octree 类似于标准树，不同之处在于它的每个节点最多可以包含八个子节点，并且它们常用于颜色量化。它们易于实现和理解。颜色根据其 R、G、B 位添加到树中，这会生成索引 0-7（R、G、B 为 000-111）。最大级别为 7，树最多可以包含 8 个级别（0-7）。对于第一级（0），取 R、G、B 的最高有效位（MSBs），并计算相应的节点索引。对于后续级别，取下一位置的下一位，并计算索引，直到第 7 级的最低有效位（LSBs）。
填充完树后，我们开始合并。我们将引用计数最少的叶节点合并到其父节点中。一个叶节点接一个叶节点地合并。当所有叶节点合并后，它们的父节点本身就变成了叶节点，然后重复此过程。尽管有观点认为合并可以在树填充完毕之前发生，但我并不推荐这样做。
重要
这不是一个图像生成器，而是一个调色板生成器，这意味着只有一个 GetPalette 函数，它返回一个由无符号字符组成的调色板，顺序为 R、G、B。
想法
主要目的是对此处常见的标准 Octree 进行一些改进。改进包括：
- 可以获得精确的颜色计数 - 主要改进（见背景）
- 我们可以在颜色添加到树之前，通过剥离 R、G、B 中的不必要位来花费大量迭代 - 次要改进
- 我们计算最小引用计数并从此值开始合并 - 次要改进
背景
关于 Octree 的简短（非常简短）描述，请参阅 Wiki。
这里 CodeProject 上有一篇关于颜色量化的优秀文章，其中包含截图和对每个概念的简要描述。请看这里：用 C# 实现一个简单但功能强大的调色板量化器。
文章还提到，“最多可以一次减少 8 个叶节点，最坏情况下我们得到 248 种颜色（这并不完全最优）”，这是不正确的，您可以获得任意想要的颜色数量（当然，在合理范围内）。我想证明这一点。
焦点
那么如何获得精确的颜色数量呢？很简单，只需在达到所需颜色数量减一后停止合并。创建一个新的普通叶节点，然后，当然，将“合并”的值返回到这个新创建的叶节点。最终您将得到正好是您想要的颜色数量。
算法（简述）
- 对于图像中的每个像素
- 获取 R、G 和 B 值
- 连续从 R、G 和 B 中取位，每个通道取一位，从最高有效位开始，到最低有效位结束
- 根据这些位生成索引（范围从 0-7）
- 沿着由索引组成的路径遍历树，在必要的地方创建新的叶节点（叶节点如果包含子节点，则成为节点）
- 在遇到的每个节点上，增加引用计数
- 在路径的末端，也增加像素计数并将颜色添加到该叶节点
- 返回到 1
为精确颜色数量进行合并
像平常一样合并叶节点，一个叶节点接一个叶节点，一个节点接一个节点地合并。但是将叶节点合并到它们的父节点（它们的像素计数，红、绿、蓝的总和）。当您达到的颜色数量比想要的少一时，创建一个新的叶节点，“吐出”父节点中的合并值到这个新的叶节点中。就是这样。您将得到正好是您想要的颜色数量。
- 计算最小引用计数（通过遍历所有节点和叶节点）- 可选
- 将叶节点合并到它们的父节点，一个叶节点接一个叶节点，一个节点接一个节点地合并
- 当达到所需颜色数量减一时停止合并
- 在当前父节点下创建一个新的叶节点，“吐出”父节点中的合并值到该叶节点
- 增加颜色数量并退出
void OctreeColorReduction::MergeLeast(node *n, int mincount) {
// why do we need to merge by 8? Because there can be up to 8 of leaves.
// What about to start merging leaves as usual, to parent node, but stop when
// colors count-1 is reached. In that moment, create new leaf and vomit values from node
// into that newly created leaf. Colors count will increase back to desired colors
// count, resulting in giving us exactly the colors count we wanted.
if (n->references_count > mincount) return; // do not go, if ref. count is
// greater than wanted
if (colorsCount == desiredColorsCount) return; // do not go, in case that
// desired colors count was reached
for (register int i = 0; i < 8; i++) {
if ((n->child[i]!=0) && (n->child[i]->childrencount > 0)) { // ak ma child
// a child este ma child
// I know, that you will always go the one node with the least ref. count
MergeLeast(n->child[i], mincount); // chod az
}
else { // merge leaves into their parent node
if((n->child[i] != 0) && (n->references_count <= mincount) ) { // merge
n->pixel_count+=n->child[i]->pixel_count; // this
// condition is needed,
n->R_sum += n->child[i]->R_sum; // because
// what if child ref. count differs from ref count of its parent
n->G_sum += n->child[i]->G_sum; // n is parent node
n->B_sum += n->child[i]->B_sum;
delete n->child[i]; // delete leaf
n->child[i] = 0; // leaf does not exist anymore
n->childrencount--; // childrens count in this parent has decreased
colorsCount--; // it is necessary to decrement colorsCount
// this is always reached
if (colorsCount < desiredColorsCount) { // do not merge anymore!
// You've reached the desired colors count-1
// vomit from parent
n->child[i] = new node(this);
n->child[i]->R_sum = n->R_sum;
n->child[i]->G_sum = n->G_sum;
n->child[i]->B_sum = n->B_sum;
n->child[i]->pixel_count = n->pixel_count;
n->childrencount++;
colorsCount++;
break; // jump off
}
}
}
}
if (n->childrencount == 0)
colorsCount++; // you've removed the childs, but a new color was created
// (from parent into new leaf)
}
什么是位剥离，有必要吗？
位剥离意味着，我们从每个红色、绿色和蓝色通道中剥离位，从最低有效位开始，直到剥离计数。这些位被置零，之后会给出一个小的补偿，以最小化信息损失。
static int StripAddRed[9] =
{0, 0, 1, 2, 4, 8, 16, 32, 64}; // array for information loss compensation
static int StripAddGreen[9] =
{0, 0, 2, 2, 4, 6, 12, 12, 32}; // array for information loss compensation
static int StripAddBlue[9] =
{0, 1, 2, 4, 8, 16, 32, 64, 128}; // array for information loss compensation
iR>>=StripR; iR<<=StripR; // strip to and fro to null bits
iG>>=StripG; iG<<=StripG;
iB>>=StripB; iB<<=StripB;
iR+=StripAddRed[StripR]; // attempt to compensate the information loss
// by adding a small value
iG+=StripAddGreen[StripG];
iB+=StripAddBlue[StripB];
例如蓝色：在 0 次剥离时，添加 0。在 1 次剥离时，添加 1，在 2 次剥离时，添加 2，在 3 次剥离时，添加 4。我们剥离了三位蓝色，并添加 4 作为补偿。
那么有必要吗？
当然没有必要，如果您想要最好的质量，此（选项）不适合您。但请考虑：以 3 2 3 的比例剥离位可以瞬间将颜色数量从 14 万减少到 4 千，并且几乎没有视觉信息损失，如果有的话。速度可以提高 10 倍或更多。
我的实验表明，以 3 2 3 的比例剥离在图像质量上相当不错，但 3 2 4 会导致轻微的可见伪影，我不推荐这样做。
您可以自行尝试。
我们计算最小引用计数吗？
是的。填充完树后，我们遍历所有节点及其叶节点，寻找最小的引用计数（节点或叶节点被遍历的次数）。我们从该值开始合并，并且在每次迭代中，我们将该值添加到最小引用计数。例如：最小引用计数是 10，因为任何节点/叶节点上都没有 1-9 的引用计数，所以我们从 10 开始合并。下一次迭代我们从 20 开始，然后是 30，依此类推。
代码
- bmp.h - 位图文件的头文件
- strip.h - 位剥离和补偿的头文件
- main.cpp - 示例程序
- ocr_good_color.cpp - Octree 本身
主类是 ocr_good_color.cpp 中的 OctreeColorReduction 。该类中最重要的 public 函数是 GetPalette。
BYTE *GetPalette(BYTE *src, int srclen, int desiredColorsCount,
int maxDepth, int StripR, int StripG, int StripB);
参数如下：
src- 用无符号字符填充的源缓冲区srclen- 源缓冲区长度desiredColorsCount- 您想要的精确颜色数量maxDepth- 树的最大深度（以位为单位，1-7）StripR,StripG,StripB- 您想从 R、G 和 B 中“丢弃”的位数
您应该调用
getColorsCount();
函数，以确保您获得了精确的颜色数量。测试表明，您总是能获得等于所需颜色数量的颜色数量。
除了以上内容，以及其构造函数和析构函数，您还可以调用
getMemoryUsed();
函数，查看树占用了多少字节。
反馈
请随时提供对本文或此处提供的代码的改进反馈。
关注点
- 正如 《寻找最优调色板》中所述，似乎还没有一个完美的优化调色板生成器。
- 请参阅 《用 C# 实现一个简单但功能强大的调色板量化器》，了解更多优化的调色板生成器，例如中值分割法。
- 您还可以查看 抖动，作为一种在降低图像位深度时保留视觉信息的选项。
注释
- 示例应用程序请求的图像输入必须是 Windows 兼容的 24 位位图。
- 我建议使用带有以下参数的
GetPalette()函数
GetPalette(src, srclen, desiredColorsCount,
/* maxdepth */5, /* StripR*/ 3, /*StripG*/ 2, /* StripB */ 3);
历史
- 2010年9月12日 - 首次发布