octree · 量化与主导色

八叉树取主导色 · color quantization

懒加载时先铺一块「主色背景」、给封面配一套主题色、统计一张图的代表色——背后都是同一个问题：从几万种颜色里选出 K 种代表色 (color quantization)，再挑像素最多的那一个当 主导色 (dominant color)。

本页用 octree（八叉树） 解这个问题：把 (r,g,b) 各 8 bit 看成一条从根往下走 8 层的路径，高位相同的颜色走同一段路径；叶子过多时自底向上折叠最细的分支，直到叶子数不超过 K。§1 选定的图会被 §4 与 §5 复用。

1 · 量化的必要性

图 1-1 · 全页共用的取图入口。可在几张样例图之间切换，也可上传本地图片，后续各图都跟着这里的选择走。

「代表色」不是图里现成就有的——它要从颜色的分布里归纳出来。先看两条走不通的朴素思路。

此路不通的思路其一：完整 histogram。 统计每种颜色出现几次、取最多的几种？24-bit RGB 共 $2^{24} = 16\,777\,216$ 种颜色，直方图要 1600 万个桶，其中绝大多数是空的。更要紧的是即便统计出来也没有意义：实测一张 600×400 的照片有 99197 种不同颜色，出现最多的那一种只有 216 个像素，占全图 0.09%，代表不了任何东西。所以必须先把相近的颜色归并再统计。

图 1-2 · 当前图片的颜色直方图与总量读数。可切换图片，对照像素总数、不同颜色数与出现最多的那一种各占多少。

此路不通的思路其二：均匀量化 (uniform quantization)。 把每个通道的低位截断、只留高 $n$ 位，等于把颜色立方体切成 $(2^n)^3$ 个等大格子。归并是做到了，但格子固定均匀、不看像素实际落在哪：截断过度则出现 posterization（色阶断裂），代表色还被钉死在网格点上，未必是图里真实出现过的颜色。

图 1-3 · 均匀量化与八叉树的并排对照。可调每通道保留的位数，读数给出量化后实际用到的色数，可与八叉树那一格比较。

注 · 八叉树在可比的色数下让划分随像素分布自适应：密集区域分得细、空旷区域并成一块，代表色取的是落进来的真实像素的平均，而不是网格点。注意图 1-3 里两侧的色数并不总相等——均匀量化那格实际用到的色数随位数跳变，八叉树那格固定取 12 色，只有位数取 3 附近才碰巧相当。

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 的第 $(7 - L)$ 位。三通道各 1 bit 共 3 bit，正好八个方向，对应把当前颜色立方体八等分后落进哪一块 (octant)。

图 2-1 · 一个颜色的比特位如何逐层拼成孩子下标。可选颜色并拖动「高亮层」，观察每层取的是三通道的哪一位。

由此得到一个单向的性质：两个颜色在树上共享的路径越长，它们就一定越接近——把一棵子树整个折叠成一个代表色，牺牲的正是这些最低位的差异。

警示 · 反过来不成立，相近的颜色未必分开得晚。路径由二进制高位决定，跨在 2 的幂边界两侧的两个近色会在很浅的层就分家：实测 rgb(127,127,127) 与 rgb(128,127,127) 只差 1，共享层数是 0（第一层就分叉），而相距更远的 rgb(200,40,40) 与 rgb(201,41,41) 共享 7 层。255 对相邻灰度里有 7 对共享层数不足 3。这正是 §6 说的「色彩边界被绑在 2 的幂的网格上」的代价。

图 2-2 · 两个颜色的路径对照。可分别取色，观察它们从第几层开始分叉，用 #7f7f7f 与 #808080 可看到近色早分家的情形。

3 · 插入与折叠

把所有像素的颜色逐个插入八叉树；全部插完之后再自底向上折叠，直到叶子数不超过 K。整个算法只有两条动作：

注 · 两条动作各自的职责。

插入 (insert)：颜色沿 8 层路径下降，落到叶子就把像素数 +1、累加 r/g/b 之和；路径已存在就并入原叶子。

折叠 (reduce)：从最深一层起，取内部节点把孩子的（像素数，r/g/b 之和）累加到自己身上、删掉孩子、自己变成叶子， $n$ 个叶子并成 1 个。

为便于观察，图 3-1 只插入几种颜色，并把树限制到很浅（第 3 层就是叶子）。

图 3-1 · 插入与折叠的单步过程。可调叶子上限 K，逐帧观察一次折叠吃掉哪几个叶子。

警示 · 先折最深的分支，是因为它们区分的是颜色最低位的差异，肉眼最不敏感。这只是「优先牺牲最不重要的信息」这一启发式，不是误差最优——本页实现在同一层里按节点创建顺序逐个折，既没有挑像素数最少的簇，也没有任何最优性论证。真实图片颜色成千上万，但这两条动作一字不变。

4 · 取出调色板与主导色

对图 1-1 选定的真实图片跑完整八叉树：先建到第 8 层，再自底向上折叠。剩下的每个叶子就是一种代表色（取值是落进它的像素的平均），按像素数排序即调色板，排第一的那个是主导色。

图 4-1 · 调色板与主导色随 K 的变化。可拖动 K，读数里的压缩比是「不同颜色数 ÷ 叶子数」。

警示 · K 是上限而非目标值，实际叶子数常常少于 K。折叠以整个节点为单位，一次吃掉它的 2 到 8 个孩子，所以只保证不超过 K。实测一张渐变图：K 取 2、4、6 时都停在 5 个叶子，K = 12 得 8 个，K = 16 得 13 个；K = 2 根本到不了 2。

5 · median-cut 与 k-means

取调色板不止八叉树一条路。最流行的库 color-thief 用的是 median cut (MMCQ)；追求质量则常用 k-means。图 5-1 对图 1-1 那张图、同一个 K 跑三种方法（k-means 用确定性初始化，结果稳定）。

三种方法都可以在 RGB 立方体里衡量「颜色相近」，但 RGB 欧氏距离与人眼感知不一致：会把看着明显不同的颜色并到一起，又把看着一样的拆开。把聚类空间切到 **Oklab（感知均匀色彩空间）**后距离更接近感知差异，同一个 K 出来的调色板通常更准。这条与算法无关，只是把像素先映到 Oklab 再跑同样的三种方法，代表色取感知空间均值再映回 sRGB。这条杠杆的分量可以从 color-thief 的取舍看出：它的默认量化器仍是 MMCQ，而默认的 colorSpace 已经是 oklch 而非 rgb（核对于 2026-08）——换空间比换算法更省力。

图 5-1 · 同一张图、同一个 K 下三种方法的代表色与重绘对照。可切换聚类空间为 RGB 或 Oklab，观察饱和色与暗部的区分差异。

建议 · 色彩空间是正交于算法的一根杠杆。在 octree、median-cut、k-means 之间换算法，往往不如把聚类空间从 RGB 换到 Oklab 来得省力，饱和色与暗部的区分差别最明显。生产级取色（如 Material You）进一步用 HCT / CAM16 这类色貌空间。

八叉树的长处是快、且插入与折叠都能做成流式；对质量有极致要求才上 k-means。
方法	怎么划分颜色空间	速度	内存	质量	能否流式
八叉树 octree	固定按位八等分，自底向上折叠最细分支	快 $O(N)$	随不同色数增长；插入时随手折叠可压成常数级	较好	可（像素来一个插一个）
median cut	反复把「最长的颜色盒子」沿中位数切两半	中	需存全部颜色盒	好（贴合分布）	否（要先有全图）
k-means	迭代：像素归最近中心 → 中心移到簇均值	慢（多轮迭代）	中	平方误差意义下最好	否
均匀量化 uniform	固定均匀网格，截断低位	最快	极小	差（网格色）	可

警示 ·「内存有上界」是算法性质，不是本页引擎的性质。经典的 Gervautz–Purgathofer 实现在插入时随手折叠，节点数因而有常数级上界；本页为了能单步演示，改成先建满第 8 层再折叠，峰值节点数随图中不同色数线性增长。实测 20 万像素：不同色约 1400 时折叠前有 7609 个节点，不同色约 32600 时有 67977 个，折到 K 之后才降到十几个。同理，buildOctree 收的是整个像素数组，本页这份实现并不流式。

注 · 主导色随 K 跳变的位置是可预期的，但它并非「基本不动」。实测一张日落样例：K ≤ 12 时主导色是天空橙（占 32.6%），K ≥ 16 时翻成山体深紫（占 23.8%）。K 小的时候大面积渐变被并成一簇，K 大到能把渐变拆开后，最大簇就会易主。用作懒加载占位色时 K 得固定下来，换了 K 主色可能换色相。

6 · 八叉树的取舍

建议 · octree 把「选代表色」变成「在一棵固定结构的树上，自底向上合并最细的分支」：建树是 $O(N)$ ，插入与折叠都是局部操作，经典实现可做到常数级内存上界并逐像素流式处理。代价是色彩边界被绑在 2 的幂的网格上（§2 那两个只差 1 却在第一层就分家的灰度即是例证），极端配色下不如 median-cut 贴合。

懒加载占位除了一块主导色，还能把整张图的低频轮廓也压进一小串数据，升级成一团模糊预览。主色到 CSS-only LQIP、BlurHash、ThumbHash 是同一思路的不同精度，见占位图 hash一页。

7 · 参考文献

Gervautz, M., & Purgathofer, W. (1988). A simple method for color quantization: Octree quantization. In New Trends in Computer Graphics (pp. 219–231). Springer.
Heckbert, P. (1982). Color image quantization for frame buffer display. ACM SIGGRAPH Computer Graphics, 16(3), 297–307.
Ottosson, B. (2020). A perceptual color space for image processing. https://bottosson.github.io/posts/oklab/