单次调色板优化与有序抖动

# 单次调色板优化与有序抖动 来源：https://30fps.net/pages/bayer-order-online-kmeans/ *Bayer 顺序像素遍历用于在线 k-means 聚类。* 下图中的 Bayer 抖动图案并非独立抖动算法所致，而是像素处理顺序的副产品。 通常，图像减色分两步完成：先用*颜色量化*算法生成调色板，再由*像素映射*阶段把每个输出像素对应到调色板中最接近的颜色（暂不考虑抖动，即选欧氏距离最短的颜色）。 但若我们同时知道旧像素色与新像素色，就可以*优化*调色板。方法是对已被分到同一调色板索引的所有像素反复做“k-means”迭代，把新调色板色取为这些像素的均值。也可以顺序完成，即*在线 k-means*（OKM）：每来一个像素，就把其选中的调色板色朝自身原始色微调一点。每处理一个像素，调色板都会轻微变化，而非像传统“批”k-means 那样等一整轮结束才更新。 我要展示的是**一种改动在线 k-means 的算法，它顺带就能产生有序抖动图案**。 该方法生成的图像质量并非顶尖，但可以省掉最后的像素映射步骤，理论上稍快。不过发这篇实验的主因，是我觉得结果看起来挺酷。 ## 省掉像素映射 在线或批 k-means 本应只是对已量化图像的后处理：差调色板进去，稍好的出来，再对像素做欧氏距离映射——*搞定*！也就是说，k-means 之后还得再映射一次。 我最初实现在线 k-means 减色时误解了这一点，直接把在线 k-means 的中间结果当最终输出，*没有*再做欧氏映射。于是图像噪点满满，我也纳闷为啥效果比 2019 年论文《Fast color quantization using MacQueen’s k-means algorithm》差那么多。 先拿“两只金刚鹦鹉”Kodak 测试图(https://r0k.us/graphics/kodak/kodim23.html) 正规流程走一遍：用 maximin k-means 初始化调色板（见附录），跑一轮在线 k-means，最后欧氏映射像素。结果如下： 红鹦鹉看起来有点糙。在线 k-means 对像素顺序敏感，光栅顺序（从左到右、从上到下）并非最佳。把像素随机打乱后： 红鹦鹉头部柔和多了。这才是 OKM 的正确用法。 现在看*中间*图像：如果最后不重新映射，而是沿用调色板尚在形成时每个像素自己选中的索引，会长什么样？光栅顺序 vs 随机顺序如下： 顺序 | 中间 OKM 结果（32 色） ---|--- 光栅 | 上下两半色调不同，调色板逐扫描线变化，黄蓝鹦鹉喙上出现棕绿渐变，挺酷。 均匀随机 | 噪点可当作抖动，打破假轮廓，渐变更平滑，甚至可认为比“正规”结果更好。 于是进入正题…… ## Bayer 矩阵顺序 均匀随机产生的是白噪，白噪易结块，见鹦鹉间绿焦外的不均匀颗粒。论文里推荐 Sobol 序列(https://en.wikipedia.org/wiki/Sobol_sequence) 只访问部分像素以提速。Bayer 矩阵生成的点集高频成分多，能打散团块，还有复古游戏味，我选它做实验。 Bayer 矩阵存的是阈值序列，1-bit 量化时决定黑白取舍；对彩色调色板更复杂(https://matejlou.blog/2023/12/06/ordered-dithering-for-arbitrary-or-irregular-palettes/)，但这里**我们只把矩阵里的数当像素处理顺序**。 例如 2×2 矩阵 ``` [1 3] [4 2] ``` OKM 会先处理每个 2×2 块的左上角（1），再右下角（2）……4×4 同理： ``` [ 1 9 3 11] [13 5 15 7] [ 4 12 2 10] [16 8 14 6] ``` 希望出来棋盘状图案。结果： 顺序 | 中间 OKM 结果（32 色） ---|--- Bayer 2×2（未打乱） | 风格化，非典型抖动 Bayer 4×4（未打乱） | 同上 目前仍以光栅顺序处理块。把*块内*顺序也随机化，即从： ```python def gen_matrix_pattern(M, data_shape): ... for yt in range(H): for xt in range(W): ... yield y,x ``` 改成： ```python def gen_matrix_pattern_shuffled(M, data_shape): ... coords = [] for yt in range(H): for xt in range(W): coords.append((y,x)) random.shuffle(coords) for y, x in coords: yield y, x ``` 结果更像经典有序抖动了： 顺序 | 中间 OKM 结果（32 色） ---|--- Bayer 2×2（打乱） | Bayer 4×4（打乱） | 该算法能在优化调色板的同时一次性生成有序抖动图案。效果因图而异，更多结果见专页(https://30fps.net/pages/bayer-order-online-kmeans/result_table.html)。 有问题或改进想法，欢迎 Mastodon(https://mastodon.gamedev.place/@pekkavaa) 或 Bluesky(https://bsky.app/profile/pekkavaa.bsky.social) 找我。 *我在写一本关于减色算法的书，感兴趣可在这里登记(https://paletteprogramming.com/)。* ## 代码 独立脚本实现上述方法： - shuffled_bayer_okm_reduction.py(https://codeberg.org/pekkavaa/shuffled-bayer-okm-color-reduction/src/branch/main/shuffled_bayer_okm_reduction.py)（本地副本(https://30fps.net/pages/bayer-order-online-kmeans/shuffled_bayer_okm_reduction.py)） 用法： ``` uv run shuffled_bayer_okm_reduction.py image.png 16 --order bayer2x2 ``` ## 附录 实验所用的初始调色板由“maximin”算法生成，行为确定且实现简单。 maximin 又称“最大覆盖”量化器，是 k-means++(https://en.wikipedia.org/wiki/K-means%2B%2B) 的确定版：先取整体均值作第一个中心，再反复选离现有中心最远的点作新中心，直到 K 个。简易 NumPy 版： ```python def maximin_init(X, K): clusters = [] N = X.shape[0] clusters.append(np.mean(X, axis=0)) while len(clusters) < K: max_dist = 0 max_dist_i = None for i in range(N): x = X[i] c_idx = 1e9 for cj in clusters: dist = sum((cj - x)**2) if dist < c_idx: c_idx = dist if c_idx > max_dist: max_dist = c_idx max_dist_i = i new_center = X[max_dist_i] clusters.append(new_center) return clusters ``` 完整脚本含向量化版本。