Yliluoma有序抖动算法再探讨

背景

2026年6月29日，Hacker News上发布了一篇技术文章，重新审视了Joel Yliluoma在2011年提出的有序抖动算法（ordered dither algorithm）。文章详细解释了该算法的内部原理，比以往的资料更为深入，并提出了新的简化变体，同时与当前最先进的算法进行了对比。文章末尾附带了源代码。本文是对该文章的中文完整解读。

有序抖动是一种图像处理技术，通过将阈值矩阵（通常为Bayer矩阵）平铺到图像上，将连续色调图像转换为仅使用有限颜色（如黑白或调色板颜色）的离散图像。其核心在于利用空间排列的噪声来模拟中间色调，从而在视觉上保留原始图像的细节。

核心内容

基础：黑白图像的Bayer抖动

要实现黑白（1-bit）有序抖动，首先要获取一个阈值矩阵。例如，一个4x4的Bayer矩阵如下：

[ \begin{bmatrix} 0 & 8 & 2 & 10 \ 12 & 4 & 14 & 6 \ 3 & 11 & 1 & 9 \ 15 & 7 & 13 & 5 \end{bmatrix} ]

将其应用于灰度图像时，遍历每个像素，根据像素坐标取模确定对应的矩阵元素，读取阈值。若像素灰度值高于阈值，则输出白色（1），否则输出黑色（0）。示例代码（Python/Numpy）如下：

bayer_4x4 = np.array([
    [0, 8, 2, 10],
    [12, 4, 14, 6],
    [3, 11, 1, 9],
    [15, 7, 13, 5]
])

def dither_bayer4x4_1bit(img: np.ndarray):
    img_float = img / 255  # 归一化到[0,1]
    H, W, _ = img.shape
    out = np.zeros((H, W, 1), dtype=float)
    for y in range(H):
        for x in range(W):
            color = img_float[y, x]
            threshold = (bayer_4x4[y%4, x%4] + 0.5) / 16.0
            out[y, x] = 1 if color > threshold else 0
    return out

这种1-bit输出会产生颗粒感较强的结果。相比之下，Atkinson误差扩散抖动在黑白场景中效果更好。但黑白抖动只是热身，真正的问题是如何对彩色图像进行有序抖动。

彩色有序抖动的简单方法：灰度偏移法

将阈值矩阵视为结构化噪声，叠加到原始颜色上，然后为每个像素寻找最接近的调色板颜色。一维的示例代码变为：

# offset 是调色板颜色之间的平均距离
for y in range(H):
    for x in range(W):
        color = img_float[y, x]
        threshold = (bayer_4x4[y%4, x%4] + 0.5) / 16.0
        moved = color + offset * (threshold - 0.5)
        idx = find_index_of_closest(moved)
        inds[y, x] = idx

关键在于噪声幅度 offset 的值。虽然理论上没有绝对正确的值，但文章通过实验总结出一个经验公式：

offset = dither_strength * 0.5 * median(pairwise_color_distances)

这种方法称为“灰度偏移法”，效果尚可，但天空中的黑点可能稍显粗糙，可通过降低抖动强度来改善。对于任意调色板，该算法容易产生色饱和度下降的结果，但当调色板针对图像设计时，效果可以接受。

更先进的N候选方法

为了解决颜色选择问题，高级方法会为每个像素收集一组调色板颜色候选（N个），为每个候选分配概率，然后通过阈值矩阵或随机方式选择一个。这些方法称为N候选方法。文章引用了2023年的一篇博客《Ordered Dithering with Arbitrary or Irregular Colour Palettes》，其中详细介绍了概率矩阵等概念。

这些算法试图满足的关键属性是局部均值再现：当抖动结果从远处看（或模糊化后）应与原始图像相似。这等价于最小化输入像素颜色 (\mathbf{p}) 与候选颜色加权和 (w_1\mathbf{r}_1 + \dots + w_N\mathbf{r}_N) 之间的距离。

Thomas Knoll算法（Adobe Photoshop所用的抖动算法）

Thomas Knoll（Photoshop的发明者）的算法在最小化上述距离方面表现惊人。算法流程如下：

1. 设置目标颜色 (\mathbf{x}_1) 为最接近输入颜色 (\mathbf{p}) 的调色板颜色 (\mathbf{r}_1)，即第一个候选颜色。
2. 计算误差 (\mathbf{p} - \mathbf{r}_1)，将目标颜色沿相反方向移动：(\mathbf{x}_2 = \mathbf{x}_1 + (\mathbf{p} - \mathbf{r}_1))。
3. 找到距离 (\mathbf{x}_2) 最近的调色板颜色作为第二个候选颜色，它补偿了第一个候选的误差（例如，如果第一个颜色偏蓝，则第二个偏黄）。
4. 重复N轮，每次更新目标，记录每个调色板颜色被选中的次数。最终候选概率与访问频率成正比。

算法实现要点：按亮度排序以确保不同像素的颜色选择一致性。Python代码核心逻辑如下：

# 工作数组在主循环外分配
weights = np.zeros(K, dtype=float)
error = np.zeros(3, dtype=float)

for y in range(H):
    for x in range(W):
        color = img_float[y, x]
        weights[:] = 0.0
        weight_sum = 0.0
        error[:] = 0.0
        # 寻找N个候选（可能少于N个不同颜色）
        for _ in range(N):
            idx = find_closest(color + error * dither_strength)
            weights[idx] += 1
            weight_sum += 1
            error += color - palette_float[idx]
        weights /= weight_sum
        threshold = (bayer_4x4[y%4, x%4] + 0.5) / 16.0
        # 按亮度顺序累加权重，选择第一个超过阈值的调色板索引
        cumulative_sum = 0.0
        for idx in luma_order:
            w_ko = weights[idx]
            cumulative_sum += w_ko
            if cumulative_sum > threshold:
                break
        inds[y, x] = idx

抖动强度可通过调整误差补偿的缩放因子来控制。此外，还可以参考mateljou的着色器版本。

Yliluoma-2算法

2011年，Jo