最近突发奇想，想要在博客中嵌入一个音乐播放器的组件，效果类似QQ音乐：
背后的蒙版的颜色是专辑图片的主色决定的，需要一个提取颜色色盘的工具，所以写了这个库。
这个库的背后的核心操作只有一件事：
颜色量化（Color Quantization）：给定一张包含数百万种颜色的图片，找出其中最具代表性的 N 种颜色。
解决这个问题有三个的经典算法——K-Means 聚类、中位切分（Median Cut）、八叉树量化（Octree）。于是研究了一下，做个笔记。
0. 先建立直觉：颜色是三维空间里的点
在计算机里，每个像素由三个数字表示：红（R）、绿（G）、蓝（B），范围均为 0–255。你可以把这三个数字想象成三维坐标——每一种颜色，就是 RGB 空间里的一个点。
1
2
3
4
5
6
7
8
9
B(蓝) ↑
│ ● (120, 80, 200) ← 紫色
│
│ ● (240, 60, 60) ← 红色
│
└──────────────────→ R(红)
/ ● (30, 180, 90) ← 绿色
↙
G(绿)
一张 800×600 的图片有 480,000 个像素，就是 RGB 空间里最多 480,000 个点（很多会重叠）。颜色量化的任务，就是把这些密密麻麻的点归纳成 N 个”代表”。
为什么不能直接取平均值？
你可能会想：把所有像素颜色加起来除以总数不就行了？
不行。 对一张红蓝各半的图取均值，结果是紫色——但图里根本没有紫色。平均值会破坏颜色信息。
正确的做法是：先把颜色相近的像素归为一组，再对每组分别取均值。这就是所有颜色量化算法的共同思路，差别只在于”如何分组”。
1. K-Means 聚类：像牧羊人归拢羊群
1.1 核心思想
K-Means 的思路非常直觉化，想象这样一个场景：
你是一位牧羊人，草场上散布着几百只羊（像素）。你在草场上插 K 面旗帜（质心），让每只羊跑向离自己最近的旗帜，然后把旗帜移到当前羊群的中心——反复重复，直到旗帜不再移动为止。
翻译成算法语言，就是四步：
- 放置 K 个初始质心
- 每个像素找离自己最近的质心，加入该簇
- 每个簇重新计算质心（取所有像素的颜色均值）
- 重复步骤 2–3，直到质心不再移动（收敛）
1
2
3
4
5
6
初始状态（K=2）： 第一轮分配： 收敛后：
● ● ● ★(质心A) [A组] ● ● ● ● ● ●
● ● [A组] ● ● ★(新质心A)
● ● ★(质心B) [B组] ● ● ● ●
● ● [B组] ● ● ★(新质心B) ● ●
已稳定
1.2 距离怎么算？
两个颜色点的距离用欧氏距离的平方（省去开根号，比大小结果一样但计算更快）：
1
2
3
4
dist² = (r1-r2)² + (g1-g2)² + (b1-b2)²
// 示例：红色(255,0,0) 与 橙色(255,128,0)
dist² = 0² + (-128)² + 0² = 16384
1.3 初始质心怎么选？——K-Means++ 的妙招
K-Means 最大的痛点是：初始质心的位置严重影响最终结果。如果一开始所有质心都扎堆在图片某个角落，算法很可能陷入糟糕的局部解。
K-Means++ 的思路：让初始质心尽量”分散”。第一个质心随机选；之后每新选一个质心，离已有质心越远的像素，被选中的概率越高——权重正比于到最近已有质心的距离平方（D²）：
1
2
3
4
5
6
7
8
9
10
11
# K-Means++ 初始化（伪代码）
centroids = [随机选一个像素]
for i in 1..K:
# 每个像素的权重 = 到最近质心的距离平方
weights[p] = min(dist²(p, c) for c in centroids)
# 按权重随机选下一个质心
# 距离越远 → 权重越大 → 被选中概率越高
next_centroid = weighted_random_choice(pixels, weights)
centroids.append(next_centroid)
这个改进让结果质量大幅提升，同时收敛更快。
1.4 空簇问题：容易被忽视的陷阱
有时某个质心会在某轮迭代后失去所有归属像素，变成”空簇”。朴素实现会直接丢弃它，导致最终颜色数量少于预期。
优雅的处理方式是从最大簇借一个像素：
1
2
3
4
5
if cluster_size[i] == 0 {
// 空簇：从像素最多的簇随机借一个像素作为新质心
let largest = argmax(&cluster_size);
new_centroid = random_pixel_from(&cluster[largest]);
}
1.5 收敛判断
设置一个阈值，当所有质心的移动量都低于该值时提前终止：
1
2
3
4
// 当所有质心移动距离均小于阈值时停止
if max_centroid_shift < 1.0 { // 1.0 是 RGB 距离单位
break;
}
1.6 优缺点总结
| 优点 ✅ | 缺点 ⚠️ |
|---|---|
| 颜色质量最高，聚类结果最自然 | 非确定性：不同种子可能得到不同结果 |
| K-Means++ 初始化大幅改善质量 | 速度较慢，复杂度 O(n·k·i) |
| 可通过固定种子复现结果 | 对初始化敏感，可能收敛到局部最优 |
| 支持收敛阈值，可提前终止 | 空簇需要额外处理 |
2. 中位切分：像切西瓜一样划分颜色空间
2.1 核心思想
中位切分（Median Cut）由 Paul Heckbert 在 1982 年提出。它的思路极其优雅：
想象你面前有一个装满彩色玻璃球的盒子（所有像素在 RGB 立方体里）。你的任务是把它们分成 K 组——每次切分时，选最大的那个盒子，找它颜色范围最宽的那个维度，从正中间切开。重复 K-1 次，得到 K 个小盒子，每个盒子的平均颜色就是代表色。
1
2
3
4
5
6
7
8
9
10
11
12
初始：一个大盒子（所有像素）
┌─────────────────────────┐
│ R范围: 0-255 → 最宽 │
│ G范围: 20-180 │
│ B范围: 10-120 │
└─────────────────────────┘
↓ 沿 R 轴在中位切分
┌────────────┐ ┌─────────────┐
│ R: 0-127 │ │ R: 128-255 │
└────────────┘ └─────────────┘
再找最大盒子继续切分...
2.2 为什么选”最宽的轴”？
核心直觉：颜色分布越分散的方向，信息量越大，切割收益越高。
举个例子：某个色块里所有像素的蓝色分量都集中在 100–110，但红色分量散布在 0–255。沿蓝色轴切毫无意义（切完两边差异极小），沿红色轴切才能有效分离颜色。
1
2
3
4
5
6
7
fn longest_axis(pixels: &[[u8; 3]]) -> usize {
let r_range = max_r - min_r;
let g_range = max_g - min_g;
let b_range = max_b - min_b;
// 哪个范围最大就沿哪个方向切
argmax([r_range, g_range, b_range])
}
2.3 为什么选”中位”而不是”均值”？
这是理解算法的关键问题。
中位数保证两边的像素数量相等。如果按均值切，遇到颜色极度偏斜的分布（比如 90% 像素是深蓝，10% 是鲜红），切出来的两个盒子大小悬殊，最终调色板质量会变差。
1
2
3
4
5
6
7
8
9
10
像素分布（沿 R 轴）：
数量 │▇▇▇▇▇▇▇▇▇▇
│▇▇▇▇▇▇▇▇▇▇▇▇
│▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
│▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
│▇▇▇▇▇▇ ▇▇▇▇▇
└─────────┬──────→ R值
↑
中位切分点（左右各50%像素）
2.4 完整的一次切分
1
2
3
4
5
6
7
fn split_bucket(mut pixels: Vec<[u8; 3]>) -> (Vec<[u8; 3]>, Vec<[u8; 3]>) {
let axis = longest_axis(&pixels); // 1. 找最宽的通道
pixels.sort_unstable_by_key(|p| p[axis]); // 2. 按该通道排序
let mid = pixels.len() / 2; // 3. 找中点
let right = pixels.split_off(mid); // 4. 切成两半
(pixels, right)
}
2.5 主循环：每次切最大的盒子
1
2
3
4
5
6
7
while buckets.len() < k {
// 选像素最多的盒子（优先细分颜色最杂的区域）
let target = argmax_by(|b| b.len());
let (left, right) = split_bucket(buckets.remove(target));
buckets.push(left);
buckets.push(right);
}
为什么选”像素最多”的？因为像素越多的盒子代表性越差，优先细分它能最快提升整体质量。
2.6 优缺点总结
| 优点 ✅ | 缺点 ⚠️ |
|---|---|
| 完全确定性，相同输入必得相同结果 | 质量略低于 K-Means（无迭代优化） |
| 实现简单，逻辑清晰 | 对颜色极度集中的图片效果稍差 |
| 速度快：O(n·k·log n) | 切分是轴对齐的，不适应斜向颜色簇 |
| 不存在收敛问题，一次完成 | — |
3. 八叉树量化：把 RGB 立方体层层细分
3.1 核心思想
八叉树量化（Octree Quantization）由 Gervautz 和 Purgathofer 在 1988 年提出。它用一种叫”八叉树”的数据结构来组织颜色——每个节点有 8 个子节点，因为 RGB 三个维度各取一半，2×2×2 = 8 个子空间。
1
2
3
4
5
6
7
8
9
10
11
RGB立方体（深度0）
┌───────────┐
│ 根节点 │ ← 整个 RGB 空间
└───────────┘
│ 按 R/G/B 最高位各取1位 → 8个子节点
↓
┌──┬──┬──┬──┬──┬──┬──┬──┐
│00│01│02│03│04│05│06│07│ ← 深度1（8个子空间）
└──┴──┴──┴──┴──┴──┴──┴──┘
│ 继续细分，最深到第8层
（每个叶子精确对应一个 RGB 颜色）
关键直觉：越相近的颜色，在越高层（低深度）就会走向相同的子节点，在更深层才会分叉。 相近的颜色自然地聚集在树的同一子树里。
3.2 子节点索引怎么算？
这是八叉树最精妙的部分。对于像素 (R, G, B)，在树的第 d 层，取每个通道的第 d 位（从高位到低位），组合成一个 3 位索引（0–7）：
1
2
3
4
5
6
7
fn octant_index(pixel: [u8; 3], depth: usize) -> usize {
let shift = 7 - depth; // 第0层取最高位(bit7)，第7层取最低位(bit0)
let r_bit = ((pixel[0] >> shift) & 1) as usize;
let g_bit = ((pixel[1] >> shift) & 1) as usize;
let b_bit = ((pixel[2] >> shift) & 1) as usize;
(r_bit << 2) | (g_bit << 1) | b_bit // 0–7
}
举个具体例子——颜色 (200, 80, 180)：
1
2
3
4
5
6
7
8
9
10
11
R = 200 = 1100_1000b
G = 80 = 0101_0000b
B = 180 = 1011_0100b
深度 0（取最高位，即 bit7）：
r_bit=1, g_bit=0, b_bit=1 → index = 101b = 5 → 走向第5号子节点
深度 1（取 bit6）：
r_bit=1, g_bit=1, b_bit=0 → index = 110b = 6 → 走向第6号子节点
... 8层走完后，精确定位到这个颜色
3.3 插入像素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn insert(node: &mut OctreeNode, pixel: [u8; 3], depth: usize, leaf_count: &mut usize) {
if depth == 8 { // 到达叶节点
node.r_sum += pixel[0] as u64;
node.g_sum += pixel[1] as u64;
node.b_sum += pixel[2] as u64;
node.count += 1;
if !node.is_leaf {
node.is_leaf = true;
*leaf_count += 1;
}
return;
}
let idx = octant_index(pixel, depth);
// 按需创建子节点并递归插入
insert(&mut node.children[idx], pixel, depth + 1, leaf_count);
}
3.4 规约（Reduce）——如何缩减颜色数
插入完所有像素后，叶节点可能有数万个。需要将它们合并到 K 个。
规约操作：找到一个拥有多个叶子子节点的内部节点，把它的所有叶子”吸收”到自己身上——叶子的颜色数据累加进来，该节点本身变成叶节点。
1
2
3
4
5
6
7
8
9
合并前：
[内部节点]
├── 叶子A（count=80, 代表红色）
├── 叶子B（count=120, 代表深红）
└── 叶子C（count=40, 代表粉红）
合并后：
[新叶节点]（count=240，代表色 = 加权平均的混合红）
r_sum = 80×rA + 120×rB + 40×rC → r = r_sum / 240
叶节点数从 3 变为 1（减少了 2）。优先合并最深层的节点，这样损失的颜色精度最小。
3.5 即时规约——内存优化的关键
如果等所有像素插入完再开始规约，内存峰值可能非常高。更聪明的做法是边插边规约：
1
2
3
4
5
6
7
8
9
10
11
12
13
for &pixel in all_pixels {
tree.insert(pixel, 0, &mut leaf_count);
// 即时规约：叶节点数超过预算 8 倍时触发
while leaf_count > k * 8 {
if !tree.reduce(&mut leaf_count) { break; }
}
}
// 最终规约到 K
while leaf_count > k {
tree.reduce(&mut leaf_count);
}
这将内存峰值从 O(唯一颜色数) 降低到接近 O(K)，处理大图时收益显著。
3.6 收集最终调色板
1
2
3
4
5
6
7
8
9
10
11
12
fn collect_leaves(node: &OctreeNode, palette: &mut Vec<Color>, total: f32) {
if node.is_leaf && node.count > 0 {
let r = (node.r_sum / node.count) as u8;
let g = (node.g_sum / node.count) as u8;
let b = (node.b_sum / node.count) as u8;
palette.push(Color { r, g, b, percentage: node.count as f32 / total });
return;
}
for child in node.children.iter().flatten() {
collect_leaves(child, palette, total);
}
}
3.7 优缺点总结
| 优点 ✅ | 缺点 ⚠️ |
|---|---|
| 速度快：O(n·log n) | 实现复杂度高于中位切分 |
| 完全确定性 | 规约策略影响颜色质量，较难调优 |
| 即时规约，内存峰值最低 | 合并顺序不同可能导致质量差异 |
| 处理大图或批量任务最稳 | — |
4. 三种算法横向对比
4.1 性能与质量一览
| 算法 | 速度 | 颜色质量 | 确定性 | 时间复杂度 |
|---|---|---|---|---|
| K-Means 聚类 | 中等 | ★★★ 最高 | 否（可设种子） | O(n·k·i)，i=迭代次数 |
| 中位切分 | 快 | ★★☆ 良好 | 是 | O(n·k·log n) |
| 八叉树量化 | 快 | ★★☆ 良好 | 是 | O(n·log n)，内存最优 |
4.2 算法选择决策树
1
2
3
4
5
6
7
8
9
10
11
12
你最在意什么？
│
─────┴──────────────────────────────────
│ │ │
颜色质量 速度/确定性 内存占用
│ │ │
▼ │ ▼
K-Means ──────┴────── Octree
│ │
图片较小 大批量/大图
│ │
MedianCut Octree
4.3 各场景推荐
| 使用场景 | 推荐算法 | 理由 |
|---|---|---|
| 网页/App 主题色提取 | K-Means | 视觉效果优先 |
| 专辑封面调色板生成 | K-Means | 颜色质量最重要 |
| 图片压缩（颜色减少） | 中位切分 | 速度快、确定性，工业首选 |
| 服务端批量处理 | 八叉树 | 内存占用低，吞吐量高 |
| 嵌入式 / WebAssembly | 八叉树 | 资源受限环境，内存控制关键 |
| 需要完全一致的结果 | 中位切分 | 最简单的可复现方案 |
5. 实现时容易踩的坑
5.1 采样优化——最值得做的性能优化
三种算法的复杂度都含 n（像素数）。一张 4K 图有 800 多万像素，直接处理很慢。
解决方案： 先把图片缩放到较小尺寸（如 256×256），再提取颜色。颜色分布的”形状”几乎不变，但像素数从 800 万降到 6.5 万——速度提升约 100 倍，质量几乎无损。
1
2
3
4
5
// 下采样到 256px（最长边），然后提取颜色
let img = image.thumbnail(256, 256);
let pixels: Vec<[u8; 3]> = img.pixels()
.map(|p| [p[0], p[1], p[2]])
.collect();
5.2 透明像素的处理
处理 PNG 图片时，完全透明的像素（alpha=0）必须跳过，否则白色或黑色背景会混入调色板：
1
2
3
4
5
6
// RGBA → 跳过全透明像素
let pixels: Vec<[u8; 3]> = rgba_data
.chunks_exact(4)
.filter(|p| p[3] > 0) // 跳过 alpha == 0
.map(|p| [p[0], p[1], p[2]]) // 只保留 RGB
.collect();
5.3 K 值怎么选？
| 用途 | 建议的 K |
|---|---|
| UI 主题 / 调色板预览 | 4–6 |
| 数据可视化配色 | 6–8 |
| 特征提取 / 图片相似度比较 | 8–16 |
| 图片压缩（GIF 等） | 16–256 |
总结
三种算法本质上都在做同一件事——把 RGB 空间里密集的像素云归纳成 K 个代表点——只是分组策略不同：
- K-Means 聚类：像牧羊人归拢羊群，迭代收敛找最优中心，质量最高，有随机性。
- 中位切分：像切西瓜，每次沿最宽维度切一刀，快速确定，工程上最成熟。
- 八叉树量化：把 RGB 立方体层层细分，插入时即时控制内存，适合大规模处理。
理解了”颜色 = RGB 空间中的点”这个基础模型，三种算法的设计思路就都变得自然而然了。
如果你想上手实验，可以用 Python 的 colorthief、scikit-learn KMeans 直接验证，或者参考本文配套的 Rust 实现（dominant-colors），三种算法均有完整代码和测试。