dithering

图像平滑算法： Dithering

看稚晖君的视频用墨水屏显示图像的部分提到了这个算法，感觉很有意思。墨水屏或者黑白打印机只能显示二值的黑白像素，dithering算法能帮我们用黑白近似灰度图像。其实，更一般地，dithering算法可以用来平滑各种信号量化带来的误差。

原理

考虑将灰度图像（0为全黑，255为全白）量化为黑白图片，灰度值为42时我们如何量化呢？简单的做法是取灰度上的近邻，用0来表示灰度值为42的像素。对于量化产生的误差，如果直接忽略，最后生成的图像质量会很差，因此我们需要找到更好的处理量化误差的方式。

error diffusion

error diffusion dithering算法以某种顺序处理像素，处理像素时的量化误差在迭代处理像素时扩散（diffusion）。例如：当前像素为42，量化为0的误差为42，假设下一个像素值为100，那么加上传递过来的误差等于142，此像素应该量化为1，此时误差变为142 - 255 = -113，继续向下一个像素传递，以此类推。

缺点：原图中的色块会扩散为黑色的线。

上面线性的处理的一个意想（liao）不（zhi）到（zhong）的后果（artifacts）就是会导致生成图像中奇怪的条纹。核心的原因就是2D图像采用了1D的误差扩散方式。

2D error-diffusion: Floyd-Steinberg Dithering

从左上角向右下角扩散，局部涉及的像素和系数表如下：

	X	7/16
3/16	5/16	1/16

2D error-diffusion: Jarvis, Judice, and Ninke Dithering

同样是左上角向右下角扩散，设计的像素和系数表如下：

		X	7/48	5/48
3/48	5/48	7/48	5/48	3/48
1/48	3/48	5/48	3/48	1/48

很多其他的扩散方式可以选择，but you get the idea.