Ditherpunk：我希望我有关于单色图像抖动的文章

我一直很喜欢抖动的视觉美感，但从来不知道它是如何完成的。所以我做了一些研究。本文可能包含nostaliga的痕迹，而没有Lena的痕迹。

我参加聚会的时间很晚，但最终我玩了卢卡斯·波普（Lucas Pope）最近以“ Papers Please”成名的游戏“ Obra Dinn的回归”。 Obra Dinn是一个我只能推荐的故事迷题者，但是引起我作为软件工程师的好奇心的是，它是3D游戏（使用Unity游戏引擎），但是仅使用2种颜色进行抖动处理。显然，它被称为“ Ditherpunk”，我很喜欢。

颤动是我最初的理解，是一种巧妙地使用调色板中几种颜色来放置像素的技术，可以诱使您的大脑看到多种颜色。就像在图片中一样，您可能会觉得实际上存在多重亮度，而实际上只有两个：全亮度和黑色。

我从未见过像这样的抖动的3D游戏，这可能是由于调色板已成为过去的事实。您可能还记得运行16种颜色的Windows 95并在上面玩过类似“猴子岛”的游戏。

但是，很长一段时间以来，我们每个像素每个通道只有8位，因此屏幕上的每个像素都可以采用1600万种颜色中的一种。随着HDR和广泛色域的出现，事情正变得越来越远，以至于需要任何形式的抖动。但是Obra Dinn还是使用了它，并重新燃起了对我早已被遗忘的爱。我对Squoosh的工作了解到一点抖动的知识，当我在3D空间中移动和旋转相机时，Obra Dinn保持抖动稳定的能力给我留下了特别深刻的印象，我想了解这一切如何工作。

事实证明，卢卡斯·波普（Lucas Pope）在论坛上发表了一篇文章，他在其中解释了他使用的抖动技术以及如何将其应用于3D空间。他在摄像机运动发生时为使抖动稳定而进行了大量工作。阅读该论坛帖子会把我踢到兔子洞，这篇博客文章试图对此进行总结。

根据Wikipedia所说，“抖动是一种有意应用的噪声形式，用于使量化误差随机化”，并且是一种不仅限于图像的技术。这实际上是迄今为止用于录音的一种技术，但这又是另一个麻烦。让我们在图像的上下文中剖析该定义。首先：量化。

量化是将大量值映射到较小值（通常是有限值）的过程。对于本文的其余部分，我将使用两个图像作为示例：

黑白照片都使用256种不同的灰色阴影。如果我们想使用更少的颜色（例如，仅使用黑色和白色以实现单色），则必须将每个像素更改为纯黑色或纯白色。在这种情况下，黑色和白色称为我们的“调色板”，而更改不使用调色板中颜色的像素的过程称为“量化”。由于并非原始图像中的所有颜色都在调色板中，因此不可避免地会引入称为“量化错误”的错误。天真的解决方案是将每个像素量化为最接近调色板原始颜色的调色板中的颜色。

注意：定义哪些颜色“彼此接近”尚待解释，并且取决于您如何测量两种颜色之间的距离。我想理想的情况下，我们应该以一种心理视觉的方式来测量距离，但是我发现的大多数文章都只是在RGB立方体中使用了欧几里得距离，即Δ红色2 +Δ绿色2 +Δ蓝色2 \ sqrt {\ Delta \ text {red} ^ 2 + \ Delta \ text {green} ^ 2 + \ Delta \ text {blue} ^ 2}Δred 2 +Δgreen 2 +Δblue 2。

使用仅由黑白组成的调色板，我们可以使用像素的亮度来确定要量化的颜色。亮度0表示黑色，亮度1表示白色，其他所有东西都介于两者之间，理想情况下与人类的感知相关，因此亮度0.5代表中等灰色。要量化给定的颜色，我们只需要检查颜色的亮度是大于还是小于0.5，然后分别量化为白色和黑色。将此量化应用于上面的图像会产生令人不满意的结果。

注意：本文中的代码示例是真实的，但是基于我为本文的演示编写的辅助类GrayImageF32N0F8构建。它类似于网络上的ImageData，但使用Float32Array，仅具有一个颜色通道，表示0.0到1.0之间的值，并具有大量帮助函数。源代码在实验室中可用。

我已经写完了这篇文章，只是想“快速地”了解使用不同的抖动算法时黑白渐变的外观。结果表明，我没有考虑使用图像时总是成为问题的东西：色彩空间。我写的句子“与人类的观念有理想的联系”，但我本人并没有真正跟随它。

我的演示是使用Web技术（最著名的是＆quot; canvas＆gt;和ImageData，在撰写本文时已指定使用sRGB。这是一个古老的色彩空间规范（始于1996年），其值对颜色的映射被建模为反映CRT显示器的行为。尽管如今几乎没有人使用CRT，但仍被认为是可以在每个显示器上正确显示的“安全”色彩空间。因此，它是Web平台上的默认设置。但是，sRGB不是线性的，这意味着当您混合50％时，sRGB中的（0.5，0.5，0.5）（0.5，0.5，0.5）（0.5,0.5,0.5）不是人类看到的颜色（0，0，0）（0，0，0）（0，0，0）和（1，1，1）（1，1，1）（1，1，1）中的。相反，它是通过阴极射线管（CRT）泵浦全白光一半功率时得到的颜色。

如该图所示，抖动渐变太亮了。如果我们想让0.5成为纯黑色和白色（如人类所感知）中间的颜色，则需要将sRGB转换为线性RGB空间，这可以通过称为“伽玛校正”的过程来完成。维基百科列出了以下公式，可在sRGB和线性RGB之间转换。

srgbToLinear（b）= {b 12.92 b≤0.04045（b + 0.055 1.055）γ否则linearToSrgb（b）= {12.92⋅bb≤0.0031308 1.055⋅b 1γ-0.055否则（γ= 2.4）\ begin {array} {rcl } \ text {srgbToLinear}（b）＆amp; =＆amp; \ left \ {\ begin {array} {ll} \ frac {b} {12.92}＆amp; b \ le 0.04045 \\ \ left（\ frac {b + 0.055} {1.055} \ right）^ {\ gamma}＆amp; \ text {否则} \ end {array} \正确。\\ \ text {linearToSrgb}（b）＆amp; =＆amp; \ left \ {\ begin {array} {ll} 12.92 \ cdot b＆amp; b \ le 0.0031308 \\ 1.055 \ cdot b ^ \ frac {1} {\ gamma}-0.055＆amp; \ text {otherwise} \ end {array} \ right。\\（\ gamma = 2.4）\ end {array} \\ srgbToLinear（b）linearToSrgb（b）（γ= 2。4）= = {1 2 。 9 2 b（1。0 5 5 b + 0。0 5 5）γb≤0。 0 4 0 4 5否则{1 2。 9 2⋅b 1。 0 5 5⋅bγ1 − 0。 0 5 5 b≤0。 0 0 3 1 3 0 8否则

回到Wikipedia对抖动的定义：“有意应用的噪声形式，用于使量化误差随机化”。我们降低了量化，现在说增加了噪声。故意地。

代替直接量化每个像素，我们向每个像素添加值在-0.5到0.5之间的噪声。这个想法是，一些像素现在将被量化为“错误”的颜色，但是这种情况发生的频率取决于像素的原始亮度。黑色将始终保持黑色，白色将始终保持白色，中灰色大约50％的时间会抖动为黑色。从统计上讲，整体量化误差有所减少，我们的大脑急于进行其余工作，并帮助您了解大局。

我发现这很令人惊讶！这绝对不是一件好事— 90年代的视频游戏向我们展示了我们可以做得更好—但这是一种非常省力且快捷的方法，可以将更多细节变为单色图像。如果要按字面意义进行“抖动”，我将在这里结束我的文章。但是还有更多……

除了讨论在对图像进行量化之前要在图像上添加哪种噪声外，我们还可以更改角度并讨论调整量化阈值。

//添加噪声grayscaleImage。 mapSelf（亮度=＆gt;亮度+数学随机（）-0.5＆gt; 0.5？1.0：0.0）; //调整阈值grayscaleImage。 mapSelf（亮度=＆gt;亮度＆gt;数学随机（）？1.0：0.0）;

在单色抖动的情况下，量化阈值为0.5，这两种方法是等效的：

b r i g h t n e s s + ra n d（）-0.5＆gt; 0.5⇔b s g＆gt; 1.0-r a n d（）⇔b r i g h t n e s s＆gt; r a n d（）\ begin {array} {}＆amp; \ mathrm {亮度} + \ mathrm {rand}（）-0.5＆amp; ＆gt; ＆amp; 0.5 \\ \ Leftrightarrow＆amp; \ mathrm {亮度}＆amp; ＆gt; ＆amp; 1.0-\ mathrm {rand}（）\\ \ Leftrightarrow＆amp; \ mathrm {brightness}＆amp;＆amp;＆amp; \ mathrm {rand}（）\ end {array}⇔⇔¬b r i g h t n e s s + ra n d（）-0。 5 b r i g h t n e s s b r i g h t n e s s＆gt; ＆gt; ＆gt; 0。 5 1。 0 − r a n d（）r a n d（）

这种方法的好处是我们可以讨论“阈值图”。阈值图可以可视化，以便更容易地推断出为什么最终图像看起来像它那样。它们也可以预先计算和重用，从而使抖动过程确定性且可并行化每个像素。结果，抖动可以在GPU上作为着色器发生。这就是Obra Dinn所做的！有两种不同的方法可以生成这些阈值图，但是所有这些方法都会为添加到图像的噪声引入某种顺序，因此被称为“有序抖动”。

上面用于随机抖动的阈值图，字面上充满了随机阈值的图，也称为“白噪声”。该名称来自信号处理中的一个术语，其中每个频率都具有相同的强度，就像在白光中一样。

“拜耳抖动”使用拜耳矩阵作为阈值图。它们以拜耳滤镜的发明者布莱斯·拜耳（Bryce Bayer）的名字命名，该滤镜如今已在数码相机中使用。传感器上的每个像素只能检测亮度，但是通过在各个像素的前面巧妙地布置彩色滤光片，我们可以通过去马赛克来重建彩色图像。过滤器的图案与拜耳抖动中使用的图案相同。

拜耳矩阵有各种尺寸，我最终称其为“水平”。拜耳0级是2×2 2 \乘以2 2×2矩阵。拜耳1级是4×4 4 \乘以4 4×4矩阵。拜耳级n n n是2 n + 1×2 n + 1 2 ^ {n + 1} \乘以2 ^ {n + 1} 2 n + 1×2 n +1矩阵。可以从n-1 n-1 n-1级递归计算n n n级矩阵（尽管Wikipedia也列出了每单元算法）。如果图像恰好大于Bayer矩阵，则可以平铺阈值图。

拜耳（0）=（0 2 3 1）\ begin {array} {rcl} \ text {Bayer}（0）＆amp; =＆amp; \ left（\ begin {array} {cc} 0＆amp; 2 \\ 3＆amp; 1 \\ \ end {array} \ right）\\ \ end {array}拜耳（0）=（（0 3 2 1）

拜耳（n）=（4⋅拜耳（n − 1）+ 0 4⋅拜耳（n − 1）+ 2 4⋅拜耳（n − 1）+ 3 4⋅拜耳（n − 1）+ 1）\开始{ array} {c} \ text {Bayer}（n）= \\ \ left（\ begin {array} {cc} 4 \ cdot \ text {Bayer}（n-1）+ 0＆amp; 4 \ cdot \ text {拜耳}（n-1）+ 2 \\ 4 \ cdot \ text {拜耳}（n-1）+ 3＆amp; 4 \ cdot \ text {拜耳}（n-1）+ 1 \\ \ end {array} \ right）\ end {array}拜耳（n）=（4⋅拜耳（n − 1）+ 0 4⋅拜耳（n − 1）+ 3 4⋅拜耳（n − 1）+ 2 4⋅拜耳（n − 1）+ 1））

级别为nnn的拜耳矩阵包含数字0 0 0到2 2 n + 2 2 ^ {2n + 2} 2 2 n +2。对拜耳矩阵进行归一化后，即除以2 2 n + 2 2 ^ {2n + 2} 2 2 n + 2，您可以将其用作阈值图：

const bayer = generateBayerLevel（level）; grayscaleImage。 mapSelf（（亮度，{x，y}）=＆gt;亮度＆gt;拜耳。valueAt（x，y，{wrap：true}）1.0：0.0）;

需要注意的一件事：使用上述定义的矩阵进行拜耳抖动处理将使图像比原来的图像更亮。例如：每个像素的亮度为1255 = 0.4％\ frac {1} {255} = 0.4 \％2 5 5 1 = 0的区域。 4％时，大小为2×2 2 \ times2 2×2的0级Bayer矩阵将使四个像素中的一个变为白色，从而产生25％25 \％2 5％的平均亮度。拜耳水平越高，该误差就越小，但是仍然存在基本偏差。

在我们的黑暗测试图像中，使用拜耳级别0时天空不是纯黑的，并且变得明显更亮。尽管在使用更高级别的水平时会变得更好，但是另一种解决方案是通过反转使用方法来偏移偏斜并使图像更暗。拜耳矩阵：

const bayer = generateBayerLevel（level）; grayscaleImage。 mapSelf（（亮度，{x，y}）=＆gt; //亮度> 1拜耳。valueAt（x，y，{wrap：true}）1.0：0.0）;

我将原始拜耳定义用于亮图，将反转版本用于暗图。我个人发现1级和3级在美学上最令人愉悦。

当然，白噪声和拜耳抖动都有缺点。例如，拜耳抖动结构非常有条理，并且看起来会重复很多，尤其是在较低级别。白噪声是随机的，这意味着在阈值图中不可避免地会有亮像素的簇和暗像素的空隙。斜视或者如果对您来说太麻烦了，则可以通过算法模糊阈值图来使这种情况更加明显。这些簇和空隙会负面影响抖动过程的输出。如果图像的较暗区域落入群集之一，则抖动输出中的细节将丢失（反之，较亮区域落入空隙中则相反）。

有一种称为“蓝色噪声”的噪声变体可以解决此问题。之所以称为蓝噪声，是因为与低频相比，高频与低频相比具有更高的强度。通过去除或抑制较低的频率，簇和空隙变得不太明显。蓝噪声抖动与白噪声抖动一样快地应用到图像上（最后只是阈值图），但是生成蓝噪声的难度和成本更高。

产生蓝噪声的最常见算法似乎是Robert Ulichney提出的“无效聚类方法”。这是原始白皮书。我发现描述算法的方式非常不直观，现在，我已经实现了它，我确信它以不必要的抽象方式进行了解释。但这很聪明！

该算法基于以下想法：可以通过对图像应用高斯模糊并分别在模糊图像中找到最亮（或最暗）的像素来找到属于群集或空隙的像素。在用几个随机放置的白色像素初始化一个黑色图像后，算法继续连续交换群集像素和空白像素，以使白色像素尽可能均匀地散开。然后，根据每个像素形成簇和空隙的重要性，每个像素得到一个介于0和n之间的数字（其中n是像素的总数）。有关更多详细信息，请参见纸张。

我的实施效果不错，但速度不是很快，因为我没有花太多时间进行优化。在我的2018 MacBook上花费大约1分钟的时间即可生成64×64的蓝色噪点纹理，足以满足这些目的。如果需要更快的速度，则有希望的优化将不是在空间域中而是在频域中应用高斯模糊。

游览：当然，了解这个书呆子使我无法实现它。该优化之所以如此有前途，是因为卷积（高斯模糊的基本操作）必须针对图像中的每个像素遍历高斯内核的每个字段。但是，如果将图像和高斯核都转换到频域（使用许多快速傅立叶变换算法之一），则卷积将变成逐元素乘法。由于我的目标蓝噪声大小是2的幂，因此我可以实现Cooley-Tukey FFT算法的就地开发变体。经过一些初步的讨论，最终将蓝噪声的产生时间减少了50％。我仍然编写了相当垃圾的代码，因此还有更多的优化空间。

由于蓝色噪声基于高斯模糊，高斯模糊是基于圆环计算的（高斯模糊在边缘处环绕的一种奇特的说法），所以蓝色噪声也会无缝平铺。因此，我们可以使用64×64的蓝色噪点并重复它以覆盖整个图像。蓝噪声抖动具有良好的均匀分布，并且没有显示任何明显的图案，平衡了细节渲染和自然外观。

所有先前的技术都依赖于这样一个事实，即由于阈值图中的阈值是均匀分布的，因此量化误差将在统计上均匀。量化的另一种方法是误差扩散的概念，如果您以前曾经研究过图像抖动，则很可能会读懂它。通过这种方法，我们不仅可以量化，而且希望量化误差平均可以忽略不计。取而代之的是，我们测量量化误差，然后将误差扩散到相邻像素上，从而影响像素的量化方式。我们正在有效地改变我们想要抖动的图像。这使过程本质上是顺序的。

预示：本文中将不涉及的误差扩散算法的一大优势是它们可以处理任意调色板，而有序抖动要求您的调色板要均匀分布。再来一次。

我将要讨论的几乎所有误差扩散抖动都使用“扩散矩阵”，该矩阵定义了当前像素的量化误差如何分布在相邻像素之间。对于这些矩阵，通常假设图像的像素是从上到下，从左到右遍历的，这与我们西方人阅读文本的方式相同。这很重要，因为误差只能扩散到尚未量化的像素。如果发现遍历图像的顺序与扩散矩阵假定的顺序不同，请相应地翻转矩阵。

幼稚的误差扩散方法在当前像素下方的像素与右侧像素之间的量化误差之间共享量化误差，可用以下矩阵描述：

（∗ 0.5 0.5 0）\ left（\ begin {array} {cc} *＆amp; 0.5 \\ 0.5＆amp; 0 \\ \ end {array} \ right）（∗ 0。5 0。5 0）

扩散算法访问图像中的每个像素（以正确的顺序！），对当前像素进行量化并测量量化误差。注意，量化误差是有符号的，即，如果量化使像素比原始亮度值更亮，则可以为负。然后，我们将量化误差的分数添加到由m指定的相邻像素

......