Floyd-Steinberg抖动算法

跳转到导航跳转到搜索弗洛伊德-斯坦伯格抖动是一种图像抖动算法，由Robert W. Floyd和Louis Steinberg于1976年首次发布。它通常由图像处理软件使用，例如，当图像转换为GIF格式（最多限制为256色）时。

该算法使用误差扩散来实现抖动，这意味着它将像素的残留量化误差推（加）到其相邻像素上，稍后再进行处理。它根据分布将债务摊开（显示为相邻像素的地图）：

[* 7 16……3 16 5 16 1 16…] {\ displaystyle {\ begin {bmatrix}＆amp;＆amp; *＆amp; {\ frac {\ displaystyle 7} {\ displaystyle 16}}＆amp; \ ldots \\ \ ldots＆amp; {\ frac {\ displaystyle 3} {\ displaystyle 16}}＆amp; {\ frac {\ displaystyle 5} {\ displaystyle 16}}＆amp; {\ frac {\ displaystyle 1} {\ displaystyle 16}} ＆amp; \ ldots \\\ end {bmatrix}}}

带有星号（*）的像素表示当前正在扫描的像素，空白像素是先前扫描的像素。算法从左到右，从上到下扫描图像，逐一量化像素值。每次将量化误差转移到相邻像素，同时不影响已经被量化的像素。因此，如果多个像素已经向下舍入，则下一个像素向上舍入的可能性更大，从而平均而言，量化误差接近于零。

扩散系数具有以下属性：如果原始像素值恰好位于最接近的可用颜色之间，则抖动结果为棋盘图案。例如，可以将50％的灰度数据抖动为黑白棋盘图案。为了获得最佳抖动，量化误差的计数应足够准确，以防止舍入误差影响结果。

在一些实施方式中，扫描的水平方向在线之间交替。这称为“蛇形扫描”。或Boustrophedon变换抖动。

在下面的伪代码中，我们可以看到上述算法。这适用于像素值的任何近似线性编码，例如8位整数，16位整数或[0,1]范围内的实数。

从上到下的每个y从左到右做每个x做oldpixel：=像素[x] [y] newpixel [x + 1] [y]：=像素[x + 1] [y] + quant_error×7/16像素[x-1] [y + 1] quant_error×3/16像素[x] [y + 1]：=像素[x] [y + 1] + quant_error×5/16像素[x + 1] [y + 1]：= pixel [x + 1] [y + 1] + quant_error×1/16

将16位灰度转换为8位时，find_closest_palette_color（）可能仅执行简单的舍入，例如：

伪代码可能导致像素值超过有效值（例如[0,1]表示中的值大于1）。理想情况下，此类值应由find_closest_palette_color（）函数进行裁剪，而不是裁剪中间值，因为随后的错误可能会使该值返回范围。但是，如果使用固定宽度的整数，则中间值的换行将导致黑白反转，因此应避免。

R.W. Floyd，L。Steinberg，一种适用于空间灰度的自适应算法。信息显示学会学报，第75卷，第77-77页（1976）。