DITHER抖动算法

对于可用颜色较少的系统，可以通过抖动颜色值来增加可用颜色的数量，但会降低分辨率. 抖动操作与硬件有关. OpenGL允许程序员仅打开或关闭抖动操作. 实际上，如果机器的分辨率已经很高，则激活抖动操作根本没有意义. 要激活或禁用抖动，可以使用glEnable（GL_DITHER）和glDisable（GL_DITHER）函数. 默认情况下，抖动被激活.

抖动算法

朋友的问题集中在彩像的抖动上. 在这里，为了便于说明，让我们先谈谈灰度图像. 然后切入彩像的抖动. 我在互联网上看到一篇写得很好的文章，因此将其张贴在这里以帮助理解.

说到抖动算法，通常会提到模式方法.

图案化（图案化）是指可以用一定比例的黑白点表示灰度，从而获得整体图像的灰度感. 黑白点的位置选择称为图案化.

首先讨论分辨率，计算机显示器，打印机，扫描仪和其他设备的重要指标是分辨率，单位是dpi（每英寸点数），即每英寸点数，点数越多，分辨率越高. ，图像越清晰. 让我们计算一下计算机监视器的分辨率是多少. 将显示设置为15英寸（参考对角线的长度），并最多显示1280×1024点. 由于宽高比为4: 3，因此宽度为12英寸，高度为9英寸，显示器的水平分辨率为106dpi，垂直分辨率为113.8dpi. 普通激光打印机的分辨率为300dpi×300dpi，600dpi×600dpi，720dpi×720dpi. 因此，打印的图像比计算机显示器清晰得多. 扫描仪的分辨率更高，数码相机的分辨率更高.

回到事实，如前所述，图案化使用图案来表示像素的灰度，因此让我们来计算一个问题. 假设有一个240×180×8位的灰度图像. 当使用分辨率为300dpi×300dpi的激光打印机在12.8×9.6英寸的纸张上打印时，每个像素的图案有多大？

这个问题非常简单，可以输入（300×12.8）×（300×9.6）= 3840×2880点，因此每个像素可以使用（3840/240）×（2880/180）= 16×16点尺寸的图形，即每个像素256点. 如果在16×16的正方形中没有黑点，则可以表示256灰度；否则，可以表示256. 有一个黑点，表示灰度为255；依此类推，当所有黑点都表示灰度级为0时. 以这种方式，一个16×16的正方形可以表示257级灰度，这比要求的8位总计256级灰度高一个. 这样可以完全打印出上面图片的灰度.

图案有问题，黑点在哪里？例如，当只有一个黑点时，我们可以击中中心，也可以击中16×16的左上角. 该图案可以是规则的或不规则的. 一般而言，规则图案比随机图案可以避免点聚类，但是有时它可以在图像中造成明显的线条.

如下所示，2×2模式可以代表5个灰度级别，

当图像中有一个灰度级为1的区域时，如下所示，会有明显的水平线和垂直线.

如果要存储256级灰度图案，则需要256×16×16的二进制晶格，并且所占用的空间仍然很大. 有一个更好的方法: 只存储一个整数矩阵（称为标准模式），每个值的范围从0到255. 将图像的实际灰度与数组中的每个值进行比较. 当该值大于或等于灰度时，相应的点将用黑点标记. 以下是25级灰度的示例.

在上图中，左侧的标准图案是右侧具有15灰度的图案. 有10个黑点和15个白点. 其实原因很简单. 灰度级为0时，全部为黑点. 灰度级的每次增加都会减少一个黑点. 需要说明的是，5×5图案可以表示26种灰度，全白点仅在灰度为25时，而不是在灰度为24时. 下面介绍一种设计标准图案的算法，这是Limb在1969年提出的.

首先从2×2矩阵开始: 设置

通过递归关系:

其中Mn和Un为2n×2n方阵，Un的所有元素均为1. 根据此算法，您可以得到

是16种灰度的标准图案.

M3（8×8阵列）很特殊，称为拜耳抖动表. M4是16×16矩阵.

根据上述算法，如果要使用M3用8×8图案表示像素，则N×N图片的大小将变为8N×8N. 如果使用M4，则更糟，它变为16N×16N. 您可以在保持原始图像尺寸的同时使用图案化技术吗？一个很自然的想法是: 如果使用M2阵列，则可以在原始图像中每8×8点拍摄一个，即重新采样，然后应用构图技术，可以使原始图像保持大尺寸<

小. 实际上，这种方法是不可行的. 首先，您不知道8×8点中的哪一个更合适. 另外，8×8间隔太大. 生成的图像和原始图像必须有很大的不同，就像下图最右边的图像一样.

我们可以采用这种方法: 假设原始图像是256级灰度，请使用拜耳抖动表进行以下处理

如果（g [y] [x] >> 2）> bayer [y＆7] [x＆7]然后打一个白点，否则打一个黑点

其中x和y表示原始图像的像素坐标，而g [y] [x]表示该点的灰度. 首先，将灰度右移两位至64级，然后将x和y取模8，以在拜耳表中找到对应的点. 根据上面给出的标准对两者进行比较和处理.

我们可以看到，模8运算将原始图片分成8×8个小块，每个小块对应于8×8拜耳表. 小块中的每个点都参与比较，从而避免了上述选择点并将块分割得太大的问题. 模8运算本质上引入了随机成分，这是我们将在下面讨论的抖动技术.

上图使用此算法并使用M3（拜耳抖动表）阵列. 下图是使用M4阵列获得的. 可以看出两者之间的差异不是很大，所以一般使用拜耳表.

让我们考虑一下最坏的情况: 即使使用了构图技术，仍然无法获得所需的灰度级. 例如: 假设有一个600×450×8bit的灰度图像. 当使用分辨率为300dpi×300dpi的激光打印机将其打印在8×6英寸的纸张上时，可以使用每个像素（2400/600）×（1800/450）= 4×4点大小的图案，可以表示最多17级灰度，不能满足256级灰度的要求. 有两种解决方案: （1）将图像尺寸从600×450减小到150×113； （2）将图像灰度等级从256降低到16. 两种解决方案都不是理想的. 这时，我们可以使用“抖动”（dithering）技术来解决这个问题. 实际上，刚刚给出的算法是一种抖动算法，称为常规抖动. 定期抖动的优点是算法简单. 缺点是图案有时很明显. 这是因为尽管取模运算引入了随机分量，但它仍然是规则的. 另外，在点之间进行比较时，只要标准图案点上的点的值大于白点，该方法就不理想，因为如果标准图案点本身的灰度值很小，并且图像当点的灰度仅比其稍大时，图像中的点更接近黑色而不是白色. 更好的方法是将此误差传播到相邻像素.

下面描述的Floyd-Steinberg算法使用此方案.

假设灰度范围从b（黑色）到w（白色），并且中间值t为（b + w）/ 2，对应于256个灰度等级，b = 0，w = 255，t = 127.5. 如果原始图片中像素的灰度级为g且误差值为e，则可以通过以下方法获得新图片中相应像素的值:

如果g> t那么

打白点

e = g-w

其他

黑点

e = g-b

3/8×e添加到右侧像素

在下面添加

3/8×e像素

1/4×e添加到右下角像素

该算法的含义很明确: 以256级灰度为例，假设某点的灰度值为130，则该点应为灰度图像中的灰度点. 由于一般图像中的灰度级连续变化，因此相邻像素的灰度值可能非常接近当前像素，因此此点和周围区域应为灰度区域. 在新图片中，130大于128，因此命中了白点，但是130仍然远离真实的白点255，并且误差e = 130-255 = -125相对较大. 将3/8×（-125）添加到相邻像素后，相邻像素的值接近0，并且出现黑点. 下次，e再次变为正数，使相邻像素变成白色点，因此一个白色一个变成一个黑色一个变成白色，它似乎只是灰色. 如果未传输错误，它将为白色. 再举一个例子，如果一个点的灰度值为250，则它应该是灰度图像中的一个白色点，并且在该点周围应该有一个白色区域. 在新图中，尽管e = -5也为负，但其值很小，并且对相邻像素的影响很小，因此仍然可以制作白色区域. 这验证了算法的正确性.

在其他情况下，您可以自己考虑. 下图是由Floyd-Steinberg算法抖动生成的图.

这里回顾一下，虽然我是C / C ++，但是为了偷懒，请先使用Matlab解决问题...

这是Matlab的Bayer抖动算法，用于将256级灰度图像抖动为相同大小的黑白图像.

清除；

clc;

m1 = [[0 2]; [3 1]];

u1 = ones（2，2）;

m2 = [[4 * m1 4 * m1 + 2 * u1]; [4 * m1 + 3 * u1 4 * m1 + u1]]

u2 = ones（4，4）;

m3 = [[4 * m2 4 * m2 + 2 * u2]; [4 * m2 + 3 * u2 4 * m2 + u2]]

I = imread（'test.bmp'）;

gI = .2989 * I（: ，: ，1）...

+. 5870 * I（: ，: ，2）...

+. 1140 * I（: ，: ，3）;

％imshow（gI）;

％r = I（: ，: ，1）;

％g = I（: ，: ，2）;

％b = I（: ，: ，3）;

[h w] = size（gI）;

bw = 0;

对于i = 1: h

对于j = 1: w

if（gI（i，j）/ 4> m3（bitand（i，7）+ 1，bitand（j，7）+1））

bw（i，j）= 255;

其他

bw（i，j）= 0;

结束

结束

结束

imshow（bw）;

该算法的算法显示在“抖动算法1”中.

在这里，我们讨论如何将24位真彩片转换为15位或16位图片. 仍使用Floyd-steinberg算法. 让我说说15位，红色5位，绿色5位，蓝色5位，1位保留位的组成. 16Bit，红色，绿色和蓝色的颜色分别是5Bit，6Bit和5Bit. 这是因为人眼对灰度的感知比对颜色的感知要强，而绿色对灰度的贡献最大. 因此，多一点绿色量化将使灰度表示更加丰富.

清除；

clc;

我= imread（'0001.jpg'）;

img = double（I）;转换后的图片百分比

[h w] = size（img（: ，: ，1））;％获得图片的大小

d = 1;当％为1时，误差从左向右传递；当-1时，误差从右向左传递

re = 0;

ge = 0;

be = 0;

rs = 8;％2 ^ n，n = 3表示将红色量化级别降低为2 ^ 5 = 32种.

gs = 8;％2 ^ n，n = 3表示将绿色量化级别降低到2 ^ 5 = 32种.

bs = 8; ％2 ^ n，n = 3表示将蓝色量化级别降低为2 ^ 5 = 32种.

对于i = 1: h

对于j = 1: w

如果（d == 1）

val = rs * fix（img（i，j，1）/ rs）;

re = img（i，j，1）-val;

img（i，j，1）= val;

val = gs * fix（img（i，j，2）/ gs）;

ge = img（i，j，2）-val;

img（i，j，2）= val;

val = bs * fix（img（i，j，3）/ bs）;

be = img（i，j，3）-val;

img（i，j，3）= val;

如果（（j + 1）<= w）％右侧像素的计算错误

img（i，j + 1，1）= img（i，j + 1，1）+ re * 3/8;

img（i，j + 1，2）= img（i，j + 1，2）+ ge * 3/8;

img（i，j + 1，3）= img（i，j + 1，3）+是* 3/8;

结束

如果（（i + 1）<= h）％计算误差传递到下部像素

img（i + 1，j，1）= img（i + 1，j，1）+ re * 3/8;

img（i + 1，j，2）= img（i + 1，j，2）+ ge * 3/8;

img（i + 1，j，3）= img（i + 1，j，3）+是* 3/8;

结束

如果（（i + 1）<= h &&（j + 1）<= w）％计算误差传递到右下像素

img（i + 1，j + 1，1）= img（i + 1，j + 1，1）+ re / 4;

img（i + 1，j + 1，2）= img（i + 1，j + 1，2）+ ge / 4;

img（i + 1，j + 1，3）= img（i + 1，j + 1，3）+ be / 4;

结束

其他

val = rs * fix（img（i，w-j + 1,1）/ rs）;

re = img（i，w-j + 1抖动算法图像清晰，1）-val;

img（i，w-j + 1，1）= val;

val = gs * fix（img（i，w-j + 1,2）/ gs）;

ge = img（i，w-j + 1，2）-val;

img（i，w-j + 1，2）= val;

val = bs * fix（img（i，w-j + 1,3）/ bs）;

be = img（i，w-j + 1，3）-val;

img（i，w-j + 1，3）= val;

如果（（w-j）> 0）％计算错误传递到左侧错误

img（i，w-j，1）= img（i，w-j，1）+ re * 3/8;

img（i，w-j，2）= img（i，w-j，2）+ ge * 3/8;

img（i，w-j，3）= img（i，w-j，3）+是* 3/8;

结束

如果（i + 1 <= h）％计算误差传递到较低像素误差

img（i + 1，j，1）= img（i + 1，j，1）+ re * 3/8;

img（i + 1，j，2）= img（i + 1，j，2）+ ge * 3/8;

img（i + 1，j，3）= img（i + 1，j，3）+是* 3/8;

结束

如果（（i + 1）<= h &&（w-j）> 0）％计算误差传递到左下像素误差

img（i + 1，w-j，1）= img（i + 1，w-j，1）+ re / 4;

img（i + 1，w-j，2）= img（i + 1，w-j，2）+ ge / 4;

img（i + 1，w-j，3）= img（i + 1，w-j，3）+ be / 4;

结束

结束

结束

d = -d;

结束

out = uint8（img）;

imshow（out）

这是原始图像:

这是经过处理的图片:

如果将24Bit真彩像转换为较低量化级别的图像，则仍将使用Floyd-Steinberg算法，但是直接使用此算法效果不佳. 原因是，当将特别丰富的颜色的图片转换为低色时，即使使用错误传输，也会由于未选择适当的颜色来表示相邻颜色而发生较大的错误. 在上一篇文章中，我们说过将24Bit图片转换为15Bit图片，并选择了颜色，我们看到它直接是r = r＆0xF8. 实际上，图像的低三位被直接截断，然后低三位的信息丢失作为错误传递到周围的像素. 对于15Bit等量化级别，此方法仍然可以接受. 但是，对于将24Bit图像变为8Bit的图像，此算法将产生较大的误差. 这不是Floyd-Steinberg算法的问题，而是颜色的不适当选择. 即使存在错误传输，图片的失真仍然相对较大.

以下是三种选择颜色的方法:

流行的颜色算法的基本思想是对彩像中所有颜色的出现次数进行统计分析并创建一个

数组用于表示颜色和颜色出现频率的统计直方图. 在按出现频率的降序对直方图数组进行排序后，直方图中的前256种颜色是图像中出现频率最高（最频繁）的256种颜色，并将它们用作调色板的颜色. 该算法使用统计直方图来分析颜色的频率，因此称为颜色直方图统计算法. 使用RGB颜色空间中最小距离的原理，将图像中的其他颜色映射到与其相邻的256个调色板颜色. 流行的颜色算法易于实现抖动算法图像清晰，并且可以为少量颜色的图像提供良好的效果，但是该算法的主要缺点是某些图像的出现频率较低，但是人眼的视觉效果却很明显. 丢失. 例如，算法中可能不会选择图像中存在的高亮度斑点，因为它们出现的频率较低，并且会丢失.

中值分割算法的基本思想是: 在RGB颜色空间中，与三个基色对R，G和B对应的空间的三个坐标轴将每个坐标轴量化为0-255. 255对应最暗的（黑色），对应于最亮的（黑色），因此形成边长为256的彩色立方体. 所有可能的颜色都与立方体中的一个点对齐；颜色立方体分为256个小立方体，每个立方体包含出现在图像中的相同数量的色点；取出每个小立方体的中心点，然后这些点代表的颜色就是我们需要最能代表图像颜色特征的256种颜色.

中值分割算法由PauJ Heckbert于1980年代初提出，现已广泛应用于图像处理领域. 该算法的缺点是排序工作复杂，内存开销大.

1988年，奥地利的M. Gervautz和W. Purgathofer发表了一篇题为“色彩量化的简单方法: Octree量化”的论文，该论文提出了一种使用八种感觉树数据结构的新色彩量化算法. ，俗称八叉树色彩量化算法. 该算法效率高于中值分割算法，内存开销小.

八叉树颜色量化算法的基本思想是将图像中使用的RGB颜色值分配给分层八叉树. 八叉树的深度最多可以达到九层，即根节点层加上八层节点，每层代表8位R，G和B值. 较低的节点层对应于不太重要的RGB值位（右侧位），因此为了提高效率并节省内存，可以删除最低的2到3层，这样对结果不会有太大影响. 叶节点对存储的像素数和R，G和B颜色分量的值进行编码;中间节点形成从顶层到叶节点的路径. 这是一种有效的存储方法，可以存储图像中出现的颜色及其出现的次数，并且不会浪费内存来存储图像中没有出现的颜色.

扫描图像的所有像素，每次遇到新颜色时将其放入八叉树，并创建一个叶节点. 扫描图像后，如果叶子节点的数量大于调色板所需的颜色数量，则需要将一些叶子节点合并到其上方的节点中，并将该节点转换为叶子节点，其中颜色存储和出现次数. 以这种方式，减少叶节点的数量，直到叶节点的数量等于或小于调色板所需的颜色的数量. 如果叶节点的数量小于或等于调色板所需的颜色数量，则可以遍历八叉树并将叶节点的颜色填充到色米的色表中.

我个人推荐使用octree算法，但是有一种比octree简单的算法，即固定色表算法. 总体思路是:

选择一个更好的颜色表作为固定颜色表. 然后，无论是什么图像，每种颜色都会在此颜色表中选择具有最接近值的颜色. 不可避免地会产生错误. 可以使用Floyd-Steinberg算法将该误差传递到周围像素，效果更好，速度也很快.

该算法的关键是如何在颜色表中快速找到最接近的颜色. 晕已经来不及了，下一次我要聊...

本文参考文献:

1. OpenGL帧缓冲区

2. 抖动算法1、2、3的讨论

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-234364-1.html