虽然算法原理已经烂大街了，但是如果我自己不做一遍的话，体会就不会那么深。于是有了这篇文章。从开始看到这个原理到写完这篇文章花了整整一天时间。各位大佬如果发现什么错误还请批评指正。 八叉树颜色量化（o
.
虽然算法原理已经烂大街了，但是如果我自己不做一遍的话，体会就不会那么深。于是有了这篇文章。从开始看到这个原理到写完这篇文章花了整整一天时间。各位大佬如果发现什么错误还请批评指正。
八叉树颜色量化（octree color quantization）可以将有丰富颜色的图片变化为只剩下少数颜色的图片，以节省资源。下面这个就是将原图与只剩下16种颜色的图做对比。
我的做法和网上其他的文章做法可能有一点不同，下面的图解都是基于我自己的做法的。
第零步：选择图像处理库
虽然libpng更加强大，但是配置起来很麻烦，所以选择了stb_image，只要包含两个头文件stb_image.h和stb_image_write.h就能读写png/jpg图像。但是不知道为什么我用这个库读取jpg图像时似乎有bug，完全相同的像素居然能读出各不相同的值，把图片后缀名改为png解决。
下面是c++的一个简单读写示例
int main(){int width, height, channels;unsigned char* img = stbi_load("bread.png", &width, &height, &channels, 0);if (img == NULL) {printf("Error in loading the image/n");exit(1);}for (int i = 0; i < height; i++){for (int j = 0; j < width; j++){int idx = (i * width + j)*channels;printf("idx = %d,R = %d,G = %d,B = %d/n", idx, img[idx], img[idx + 1], img[idx + 2]);}}stbi_write_png("sky.png", width, height, channels, img, width * channels);stbi_image_free(img);}
第一步：向八叉树中填充颜色节点
读取完图像后，首先遍历图像的每个像素，将这些像素的颜色放到八叉树中去。我们将表示每个像素颜色的RGB数值拆分为三个7位二进制数，比如如下颜色。
设根节点为第0层，由于是八叉树，所以根节点现在最大能有8个子节点，但现在还一个没有。根据上表，首先来到第一层，建立根节点的子节点编号为6的子节点，虽然编号为6，但这仅仅是为了方便颜色查找，实际上现在根节点还只有一个子节点。然后以刚才建立的节点为父节点，再建立这个节点为编号为4的子节点，如此下去，这样做的目的仅仅是为了方便查找颜色而已。如果你看不懂这段话，可以看看下面的图解。
我的节点结构体如下
struct node{bool IsLeaf;//是否为叶子节点bool Reduce;//是否可归并，将在第二步说到unsigned int count;//此节点记录了多少个像素的颜色unsigned int level;//当 level = 7就是叶子节点unsigned int redsum;//红色分量总和unsigned int greensum;//绿色分量总和unsigned int bluesum;//蓝色分量总和unsigned int mapto;//映射到一个vector中方便根据索引寻找unsigned int childnum;//不为NULL的子节点数量node* ptrChild[8];//8个子节点，初始化为NULLnode(unsigned int lev){level = lev;redsum = greensum = bluesum = count = childnum = 0;mapto = -1;for (int i = 0; i < 8; i++){ptrChild[i] = NULL;}IsLeaf = false;Reduce = true;}};std::vector<node*> LeafNodes;
为了简单起见，我们假设我们的图像只有四个像素，颜色分别是（0，0，0）和（0，0，0）和（0，1，1）和（255，255，255）。并且我们想将其变为双色图像。
于是就像下面这样建树，蓝色圆之内的是这个节点在数组中的索引，方便区分节点以及查找。而蓝色圆之外的那个橙色数字就是，这个子节点在父节点的8个子节点中的序号，既然数字为R值为0，化为7位二进制也都是0000000了。数量则代表这个节点代表的像素数量。
然后插入第二个像素，也是0，0，0，所以不用建立新节点，只需要在原来的节点上将其“所代表的像素数量”增加1就行了。注意这个和子节点数量是不同的。虽然它们代表了两个像素，但其实只有一种颜色。
然后添加像素0，1，1，这是一种新颜色，第7为0，第8为11也就是3，所以这是7号节点的第二个子节点，我们将其索引设置为9。9号节点只代表了一个像素。此时我们的8叉树已经表示了两种颜色，但是原图还有一个像素还没计算。
下面这个addColor，对每个像素都会调用一次。如果这个像素需要的节点还没有建立，则建立新节点。每次经过节点时，无论这个节点是不是新建的，都将正在处理的像素的颜色加到这个节点上，当然RGB分别加，然后给这个节点的count加上1，代表这个节点所代表的像素加1。
void addColor(node* &anode,unsigned int red, unsigned int green, unsigned int blue,bool newnode){if (anode->level < 8 && newnode)//将该节点的索引放进所在层中，方便之后搜索{HeadNodes[anode->level].push_back(anode->mapto);}anode->redsum += red;anode->greensum += green;anode->bluesum += blue;anode->count += 1;//即上图中的数量，即节点代表的像素数量if (anode->IsLeaf)return;if (anode->level == 8)//如果是第8层{anode->IsLeaf = true;anode->Reduce = false;if (newnode)//新颜色，需要新建一个叶子节点{currentcolor += 1;anode->IsLeaf = true;if (currentcolor > maxcolor){//需要减去一个颜色！将在第二步中说到ReduceColor();}}}else{unsigned int shift = 7 - anode->level;//用于计算7颜色的7位二进制unsigned int Idx = (((red & mask[anode->level]) >> shift) << 2) |(((green & mask[anode->level]) >> shift) << 1) |((blue & mask[anode->level]) >> shift);if (anode->ptrChild[Idx] == nullptr)//子节点不存在，需要新建一个{anode->ptrChild[Idx] = new node(anode->level + 1);LeafNodes.push_back(anode->ptrChild[Idx]);anode->ptrChild[Idx]->mapto = LeafNodes.size() - 1;anode->childnum += 1;addColor(anode->ptrChild[Idx], red, green, blue,true);}else{addColor(anode->ptrChild[Idx], red, green, blue, false);}}}
第二步：减少节点
现在我们要添加最后一个像素了，最终效果应该如下。但是我们现在只希望最终图像只有两种颜色。但现在我们代表颜色的叶子节点，也就是第8层的那些节点，有三个，这时候就需要有一种特别的方法减少叶子节点了。
我们的原则就是，当前颜色的数量超过期望的颜色的数量的时候，就从深层往根节点寻找这样一个节点，它在叶子节点之上，有两个或以上子节点，并且它所代表的像素数量是最少的。找到之后，然后将这个节点的所有子节点丢弃，而自身成为叶子节点。
从深层往根节点这样的顺序是因为，层数越深，节点所能代表的颜色范围就越小，就能保证颜色不至于变成另外一种相差很大的颜色。需要这个节点所代表的像素数量最少的原因是，将一种出现频率很少的颜色换成相近的另外一种颜色，对图像的影响很小。
另外来自《基于八叉树结构的色彩量化算法》的解释如下：
首先我们要在建立的树的时候，为0到7层的节点每一层都建立一个数组，用于包含那一层的节点。当然也可也不用数组，用链式前向星或者最小堆都行。这时候第7层包含的节点索引有7，16，第六层是6，15，以此类推。
std::vector<int> HeadNodes[8];...if (anode->level < 8 && newnode){HeadNodes[anode->level].push_back(anode->mapto);}
然后，当现在八叉树上颜色的数量，也就是叶子节点的数量超过希望的颜色的数量，就执行节点函数。具体做法是从第7层遍历到第0层，寻找可归并并且子节点数量大于2的节点，找到之后将其设为叶子节点。这样就减少了叶子的数量。
只要在叶子叶节点之上并且还未归并过就称为可归并。
void ReduceColor(){int minidx = -1;for (int i = 7; i >=0 ; i--){int mincount = 0x7f7f7f;for (int j = 0; j < HeadNodes[i].size(); j++){int idx = HeadNodes[i][j];if (LeafNodes[idx]->Reduce && LeafNodes[idx]->childnum >= 2 && mincount > LeafNodes[idx]->childnum){mincount = LeafNodes[idx]->childnum;minidx = idx;}}if (minidx != -1)break;}RecursiveDisableReduce(minidx);LeafNodes[minidx]->IsLeaf = true;currentcolor -= (LeafNodes[minidx]->childnum - 1);if (pri)printf("得到索引%d,目前颜色数量%d！/n", minidx,currentcolor);}
在这里，有的文章并非是像我这样去寻找另外的节点，而是直接让新增的节点去寻找一个所代表像素数量小的节点去归并。不过显然这种放在很多情况下效果不好，比如在这个例子中，（255，255，255）会去和（0，0，1）归并，变成（127，127，128），与原来的颜色相差太大了。
第三步：建立调色盘
再次遍历每个像素，对于每个像素，在八叉树上查询每个像素的颜色。由于之前已经查询过，所以这次不必新建节点。但这次遇到叶子节点后，就直接将其的数组索引返回，而不再继续下去。
每个节点的颜色，等于颜色总量除以所代表的像素数量。
现在对于第0，1，2个像素，它们查询到第7层的7号节点就会返回，颜色都变成0，0，0，第3个像素查询到第8层的17号节点，仍然是255，255，255，成功地将其变为了双色图像。
int QueryColor(node*& anode, unsigned int red, unsigned int green, unsigned int blue){if (anode->IsLeaf){return anode->mapto;}else{unsigned int shift = 7 - anode->level;unsigned int Idx = (((red & mask[anode->level]) >> shift) << 2) |(((green & mask[anode->level]) >> shift) << 1) |((blue & mask[anode->level]) >> shift);if (pri) printf("shift = %d,idx = %d，下一层数是%d/n", shift, Idx, anode->level + 1);return QueryColor(anode->ptrChild[Idx], red, green, blue);}}
第四步：抖动
英文位dither。下面这张图，最左边是原图，中间是经过直接减少颜色后的图，而右边是减少颜色后由加上抖动算法的图。虽然中间和右边颜色和数量都一样，但是中间的图有明显的颜色带，而右边的明显更加丝滑一些。大致原理就是计算出处理后的颜色与原始颜色的差，乘上不同的比例再加到旁边的像素上。很简单就不贴代码了。
github地址
https://github.com/clatterrr/Octree-Color-Quantization
很不错的参考：
颜色量化不止八叉树这一种方法，其他方法可看：
八叉树颜色量化
往期精选
Unity3D游戏开发中100+效果的实现和源码大全 - 收藏起来肯定用得着
Shader学习应该如何切入？
喵的Unity游戏开发之路 - 从入门到精通的学习线路和全教程
声明：发布此文是出于传递更多知识以供交流学习之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与我们联系，我们将及时更正、删除，谢谢。
作者：光影帽子
原文：https://zhuanlan.zhihu.com/p/220177037
More：【微信公众号】 u3dnotes
本文分享自微信公众号 - Unity3D游戏开发精华教程干货（u3dnotes）。
如有侵权，请联系 [email protected] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
