色彩量化算法 - 中位切割法与 k-means 减色处理
什么是色彩量化
色彩量化是减少图像中颜色数量的技术。24 位彩色图像最多可表示 1677 万种颜色，但 GIF 格式仅支持 256 色，某些显示设备的调色板也有限制。色彩量化在保持视觉质量的同时，将颜色数量减少到指定范围内。
色彩量化的主要应用场景：
- GIF 动画制作：必须将颜色限制在 256 色以内
- 主色调提取：从图像中提取代表性颜色用于设计
- 文件大小优化：减少颜色数可显著降低 PNG 文件大小
- 艺术效果：色彩海报化等风格化处理
量化的核心挑战：
从数百万种颜色中选择最具代表性的 N 种颜色，使量化后的图像与原图在视觉上尽可能接近。这本质上是一个优化问题，不同算法在速度、质量和内存使用之间做出不同的权衡。
量化质量的评估通常使用均方误差 (MSE) 或峰值信噪比 (PSNR)，但人眼对色彩差异的感知并非均匀的，因此感知色彩空间 (如 CIELAB) 中的误差度量更能反映实际视觉质量。
中位切割法 - 递归色彩空间分割
中位切割法由 Paul Heckbert 于 1982 年提出，通过递归分割 RGB 色彩空间来确定代表色。尽管算法简单，但能产生高质量的结果，被广泛应用于图像处理库中。
算法步骤：
- 将图像所有像素放入一个包含整个 RGB 空间的立方体 (box) 中
- 找到该立方体中颜色分布范围最大的轴 (R、G 或 B)
- 沿该轴的中位数位置将立方体一分为二
- 对每个子立方体重复步骤 2-3，直到立方体数量达到目标颜色数
- 每个立方体内所有像素的平均色作为该区域的代表色
优势：
- 实现简单，代码量少
- 计算速度快，适合实时处理
- 结果稳定，不受初始值影响
- 自然地为颜色密集区域分配更多代表色
局限性：
- 分割方向仅限于坐标轴方向，无法沿任意方向分割
- 对于颜色分布不均匀的图像，可能产生次优结果
- 不考虑人眼对不同颜色区域的敏感度差异
改进变体：
加权中位切割法根据像素数量对分割决策进行加权，使颜色密集区域获得更精细的量化。方差最大化分割选择方差最大的轴进行分割，而非简单的范围最大轴。
补充说明（计算量与实现）：将图像减少到 N 色的计算量为 O(P × log N)（P 为像素数）。递归分割在深度 log2(N) 处完成，因此生成 256 色调色板只需 8 次分割。在 Python 中使用 NumPy 实现时，可将像素数据作为 (N, 3) 数组处理，并用 np.partition() 实现 O(N) 的中位数分割，从而高效运行。
k-means 最优调色板生成
k-means 聚类将色彩空间中的像素分为 k 个簇，以各簇的质心作为代表色。通过迭代优化最小化量化误差 (像素与其代表色之间的总距离)，理论上可以得到最优的调色板。
算法流程：
- 随机选择 k 个初始质心 (或使用 k-means++ 初始化)
- 将每个像素分配到最近的质心所属的簇
- 重新计算每个簇的质心 (簇内所有像素的平均色)
- 重复步骤 2-3 直到质心不再变化或达到最大迭代次数
与中位切割法的对比：
- 质量: k-means 通常产生更低的量化误差
- 速度: k-means 需要多次迭代，比中位切割法慢
- 稳定性：结果依赖初始值，多次运行可能得到不同结果
- 适用性：适合对质量要求高、对速度要求不严格的场景
优化技巧：
- 使用 k-means++ 初始化避免局部最优
- 先用中位切割法的结果作为初始质心，加速收敛
- 对图像进行下采样后再聚类，大幅减少计算量
- 在 CIELAB 色彩空间中进行聚类，使距离度量更符合人眼感知
补充说明（收敛与性能）：k-means 通常需要 10-30 次迭代才能收敛。相比中位切割法的 O(P × log N)，k-means 的计算量为 O(P × k × I)（I 为迭代次数），因此 256 色调色板的生成需要数秒到数十秒，而中位切割法可在 1 秒内完成。scikit-learn 提供了 KMeans(n_clusters=k, init='k-means++') 实现。对于大图像，Mini-Batch k-means（每次迭代仅使用随机采样的约 10,000 个像素）可在质量损失极小的前提下将处理速度提升 10-100 倍，对应 scikit-learn 的 MiniBatchKMeans。
八叉树方法与其他量化算法
除中位切割法和 k-means 外，还有多种量化算法。根据需求和约束选择最优方法，对于在各应用场景中获得最佳结果至关重要。
八叉树量化：
八叉树将 RGB 色彩空间表示为深度最大为 8 的树结构。每个节点代表一个色彩子空间，叶节点存储该区域的像素统计信息。通过合并叶节点来减少颜色数量。
- 优势：内存效率高，可增量构建，适合流式处理
- 特点：自然地为高频颜色区域保留更多细节
- 应用：常用于需要动态调整颜色数量的场景
均匀量化：
将 RGB 各轴均匀分割为固定数量的区间。实现最简单但质量最差，因为不考虑实际颜色分布。适用于对质量要求不高但需要极快速度的场景。
神经网络量化 (NeuQuant):
使用自组织映射 (SOM) 神经网络学习图像的颜色分布。训练后的网络权重即为最优调色板。质量优秀但计算成本高，适合离线批量处理。
算法选择指南：
- 实时处理、Web 前端：中位切割法
- 最高质量、离线处理：k-means (CIELAB 空间)
- 流式处理、内存受限：八叉树
- GIF 编码器内置：通常使用改进的中位切割法或八叉树
补充说明：均匀量化的一个例子是将 R 分为 8 级、G 分为 8 级、B 分为 4 级，即可得到 256 色。NeuQuant 基于 Kohonen 的自组织映射（SOM），已被 GIF 编码器 gifsicle 采用，在含渐变的图像上效果尤佳。此外，Xiaolin Wu 于 1991 年提出的 Wu 最优量化通过最小化三维直方图的方差来分割色彩空间，能以较低计算成本获得高质量结果。
结合抖动处理 - 提升视觉质量
量化后的图像可能出现色带 (等高线状的条纹图案)，这是由于颜色数量减少导致色调渐变丢失。结合抖动 (Dithering) 处理，即使在有限的颜色数量下也能在感知上再现平滑的渐变。
抖动的原理：
抖动通过在相邻像素间交替使用不同颜色，利用人眼的空间混合特性来模拟中间色调。类似于印刷中的半色调网点技术。
主要抖动算法：
- Floyd-Steinberg 抖动：误差扩散法的代表，将量化误差按比例分配给相邻像素。质量高但有方向性伪影
- 有序抖动 (Bayer 矩阵)：使用预定义的阈值矩阵，可并行处理。产生规则的点阵图案
- 随机抖动：添加随机噪声后量化。最简单但质量最低
- Sierra 抖动: Floyd-Steinberg 的改进版，误差扩散范围更大，伪影更少
抖动强度控制：
抖动强度过高会产生明显的噪点感，过低则色带依然可见。通常将误差扩散系数设为 0.7-1.0 之间，根据图像内容和目标颜色数调整。照片类图像适合较强的抖动，图标和 UI 元素则应减弱或禁用抖动。
Web 应用中的考量：
现代浏览器在将图像显示到低色深设备时会自动应用抖动。但在手动生成 GIF 或 PNG-8 时，需要明确选择抖动算法和强度，以在文件大小和视觉质量之间取得平衡。
补充说明（Floyd-Steinberg 的误差分配比率与实现）：Floyd-Steinberg 抖动按固定比率将量化误差分配给相邻像素——右侧 7/16、左下 3/16、正下 5/16、右下 1/16，按光栅扫描顺序处理，一遍即可完成。有序抖动因图案规则、便于并行，适合 GPU 实现。在 Python 中，Pillow 的 image.quantize(colors=256, method=Image.MEDIANCUT, dither=Image.FLOYDSTEINBERG) 可同时完成减色与抖动；ImageMagick 的 convert -colors 256 -dither FloydSteinberg 也提供相同处理。
实际应用 - GIF 转换与主色调提取
色彩量化算法的实际应用包括 GIF 动画制作和主色调提取。这些技术在 Web 开发和设计工具中被频繁使用。
GIF 转换工作流：
- 分析视频/动画的所有帧，构建全局调色板
- 使用量化算法将颜色减少到 256 色以内
- 应用抖动处理改善视觉质量
- 优化帧间差异，仅编码变化区域以减小文件大小
全局调色板 vs 局部调色板：
- 全局调色板：所有帧共享一个 256 色调色板。文件更小但颜色表现力受限
- 局部调色板：每帧独立的调色板。颜色更丰富但文件显著增大
- 混合策略：关键帧使用局部调色板，其余帧使用全局调色板
主色调提取应用：
- 图片占位符背景色：在图像加载前显示主色调作为背景
- 自适应 UI 主题：根据用户上传的图片自动生成配色方案
- 图像搜索和分类：基于主色调进行相似图像检索
- 数据可视化：将图像色彩分布可视化为色轮或柱状图
JavaScript 实现示例：
使用 Canvas API 获取像素数据后，应用中位切割法提取 5-8 个主色调。对于性能敏感的场景，先将图像缩放到 50x50 像素再进行分析，可以在毫秒级完成处理而不会明显影响结果质量。
补充说明：全局调色板与局部调色板的选择还需考虑透明色的预留（255 色 + 1 个透明色）。调色板生成的实用技巧包括：排除肤色、背景色等大面积颜色以提取强调色；按饱和度过滤，仅保留鲜艳的颜色；在 CIELAB 空间执行 k-means 以生成感知均匀的调色板；核对提取颜色的对比度是否满足无障碍标准。Google 的 Material Design 和 Spotify 的专辑封面背景色生成都采用了类似技术。在批量处理大量图像时，先将图像缩小（例如 100 × 100）再减色，可在几乎不影响质量的前提下将处理速度提升 100 倍以上。