八叉树取主导色 · color quantization
懒加载时先铺一块「主色背景」、给封面配一套主题色、统计一张图的代表色——背后都是同一个问题：从几万种颜色里选出 K 种代表色 (color quantization)，再挑像素最多的那一个当 主导色 (dominant color)。
本页用 octree（八叉树） 解这个问题：把 (r,g,b) 各 8 bit 看成一条从根往下走 8 层的路径，相近的颜色自然落到同一棵子树；当叶子太多时自底向上 reduce 折叠最细的分支，直到只剩 K 个叶子。先选一张图（或上传你自己的），后面「为什么需要量化 / 取调色板 / 换个方法」三处都用它。
1 · 为什么需要量化：几万种颜色挑几种
「代表色」不是图里现成就有的——它要从颜色的分布里归纳出来。先看两条走不通的朴素思路。
此路不通的思路其一：完整 histogram。 统计每种颜色出现几次、取最多的几种？24-bit RGB 共 2²⁴ = 16,777,216 种颜色，直方图要 1600 万个桶，还极其稀疏: 照片里几乎没有两个像素颜色完全相同，「最多的那种」往往只有个位数像素，代表不了什么。所以必须先把相近的颜色归并再统计。
此路不通的思路其二：均匀量化 (uniform quantization)。 把每个通道的低位截断、只留高 n 位，等于把颜色立方体切成
个等大格子。归并是做到了，但格子固定均匀、不看像素实际落在哪：截断过度则出现 posterization（色阶断裂），代表色还被钉死在网格点上，未必是图里真实出现过的颜色。
对比第三块图：八叉树在同样的色数下让划分随像素分布自适应——密集区域分得细、空旷区域并成一块，代表色取的是落进来的真实像素的平均，而不是网格点。下面就看它怎么把颜色空间组织成一棵树。
2 · 八叉树怎么装下颜色空间
八叉树每个内部节点最多 8 个孩子。把三个通道各 8 bit 对齐，从最高位到最低位逐层往下走：第 L 层取 r、g、b 的同一个 bit 拼成 0..7 的孩子下标。一个颜色因此对应一条 8 层路径，叶子（第 8 层）就是这个精确的 24-bit 颜色。
第 L 层孩子下标 = (r_bit << 2) | (g_bit << 1) | b_bit，其中 r_bit 是 r 的第
位。三通道各 1 bit → 共 3 bit → 正好 0…7 八个方向，对应把当前颜色立方体八等分后落进哪一块 (octant)。
选一个颜色，拖「高亮层」逐层看它的比特位怎么拼出孩子下标。
关键就在这：两个相近的颜色高位相同，开头若干层走完全一样的路径，直到某个较低的位才分叉。换句话说颜色越接近、在树上分开得越晚——把一棵子树整个折叠成一个代表色，牺牲的正是这些最不重要的低位差异。
3 · 动手建树：插入与折叠
把所有像素的颜色逐个插入八叉树；一旦叶子数超过上限 K，就触发 reduce——自底向上把最细的分支折叠回去。整个算法只有两条动作：
插入 (insert): 颜色沿 8 层路径下降，落到叶子就把像素数 +1、累加 r/g/b 之和；路径已存在就并入原叶子。
折叠 (reduce): 叶子太多时取最深一层「孩子全是叶子」的内部节点，把孩子的（像素数，r/g/b 之和）累加到自己身上、删掉孩子、自己变成叶子。n 个叶子 → 1 个。
为了看清，这里只插入下面几种颜色、并把树限制到很浅（第 3 层就是叶子）。点「下一步」走一遍。
为什么先折最深的？ 最深的分支区分的是颜色最低位的差异——肉眼最不敏感的那部分。先折它们，等于优先牺牲最不重要的信息，把代表色误差压到最小。真实图片颜色成千上万，但这两条规则一字不变。
4 · 取出调色板与主导色
对上面选的真实图片跑完整八叉树（建到第 8 层再 reduce）。剩下的每个叶子就是一种代表色（取值 = 落进它的像素的平均），按像素数排序就是调色板；排第一的那个 = 主导色。拖动 K 看调色板实时变化。
5 · 换个方法：median-cut 与 k-means
取调色板不止八叉树一条路。最流行的库 color-thief 用的是 median cut (MMCQ)；追求质量则常用 k-means。对同一张图、同一个 K 跑三种方法，看代表色与重绘差异（k-means 用确定性初始化，结果稳定）。
三种方法默认都在 RGB 立方体里衡量「颜色相近」，但 RGB 欧氏距离与人眼感知不一致: 会把看着明显不同的颜色并到一起、又把看着一样的拆开。把聚类空间切到 Oklab（感知均匀色彩空间）——距离≈感知差异——同一个 K 出来的调色板通常更准（尤其饱和色与暗部）。这条与算法无关: 只是把像素先映到 Oklab 再跑同样的三种方法，代表色取「感知空间均值」再映回 sRGB。
切到 Oklab 再拖 K 对比：调色板对饱和色与暗部的区分通常更细、更接近肉眼判断，重绘的色带过渡也更顺。色彩空间是正交于算法的一根杠杆——比在 octree / median-cut / k-means 之间换算法，换空间往往更省力地提质量。生产级取色（如 Material You）进一步用 HCT / CAM16 这类色貌空间。
| 方法 | 怎么划分颜色空间 | 速度 | 内存 | 质量 | 能否流式 |
|---|---|---|---|---|---|
| 八叉树 octree | 固定按位八等分，边建边折叠最细分支 | 快 O(N) | 有上界 | 较好 | 可 （像素来一个插一个） |
| median cut | 反复把「最长的颜色盒子」沿中位数切两半 | 中 | 需存全部颜色盒 | 好 （贴合分布） | 否 （要先有全图） |
| k-means | 迭代：像素归最近中心 → 中心移到簇均值 | 慢 （多轮迭代） | 中 | 最好 | 否 |
| 均匀量化 uniform | 固定均匀网格，截断低位 | 最快 | 极小 | 差 （网格色） | 可 |
把 K 拖到很小（如 2）：重绘会呈现明显的色块化，但主导色基本不动——它是像素最多的那一簇，即便 K 很小也最先被保留。这正是它能稳定用作懒加载占位色的原因。
6 · 一句话记住
octree 把「选代表色」变成「在一棵固定结构的树上，自底向上合并最细的分支」：建树是 O（像素数）、内存有上界、可流式——这正是它相对 median-cut / k-means 的优势。代价是色彩边界被绑在 2 的幂的网格上，极端配色下不如 median-cut 贴合。
7 · 占位图不止一块主色
懒加载占位除了「一块主导色」，还能把整张图的低频轮廓也压进一小串数据，升级成「一团模糊预览」。主色 → CSS-only LQIP / BlurHash / ThumbHash 是同一思路的不同精度，见 占位图 hash: CSS-LQIP / BlurHash / ThumbHash。