Floyd-Steinberg扩散抖动算法

Floyd-Steinberg扩散抖动算法,用在图像处理中,例如将图像转换成最多256色的GIF格式。

该算法利用误差扩散实现抖动,从左到右、由上至下扫描图像的像素并将其逐个标准化(或二值化),把像素标准化后产生的误差叠加到相邻像素上,不影响已经处理过的像素。这样实现的效果是,如果某些像素向下取整,则下一个像素向上取整的可能性更大,这样使得平均量化误差最小。

下面伪代码中,输入图像的像素被标准化为[0, 1],0为黑色,1为白色。

for each y from top to bottom
for each x from left to right
oldpixel = pixel[x][y]
newpixel = round(oldpixel / 255)
pixel[x][y] = newpixel
quant_error = oldpixel - newpixel
pixel[x + 1][y ] += quant_error * 7 / 16
pixel[x - 1][y + 1] += quant_error * 3 / 16
pixel[x ][y + 1] += quant_error * 5 / 16
pixel[x + 1][y + 1] += quant_error * 1 / 16

下面是Floyd-Steinberg扩散抖动算法在JS中的具体实现。

图片像素

异步加载图片,用canvas做中介,将图片绘制到canvas画布上,使用画布的getImageData方法获取图片像素信息,该方法返回的imageData对象的data是一个Uint8ClampedArray数组,图像的每个像素信息占4个元素储存,其中:

  • R - 红色 (0-255)
  • G - 绿色 (0-255)
  • B - 蓝色 (0-255)
  • A - alpha通道 (0-255 0透明 255完全可见)
async function getImg() {
const img = new Image()
img.src = '/images/else/kid-s.jpg'
await new Promise(resolve => img.addEventListener('load', resolve))
const width = img.width
const height = img.height
const canvas = document.createElement('canvas')
canvas.setAttribute('width', width)
canvas.setAttribute('height', height)
const ctx = canvas.getContext('2d')
ctx.drawImage(img, 0, 0)
const imageData = ctx.getImageData(0, 0, width, height)
return {
width,
height,
data: imageData.data
}
}

扩散抖动

为简化演示,这里使用了不含色彩信息的灰度图像,其像素点的R、G和B数值是相同的;图片格式为JPG,无半透明效果,即alpha通道数值均为255。

根据imageData的数据形式,这里像素数据每4个一组进行处理。

const px = (x, y) => x * 4 + y * width * 4

for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
const oldPixel = data[px(x, y)]
const newPixel = oldPixel > 125 ? 255 : 0
data[px(x, y)] = data[px(x, y) + 1] = data[px(x, y) + 2] = newPixel
const quantError = oldPixel - newPixel

data[px(x + 1, y )] =
data[px(x + 1, y ) + 1] =
data[px(x + 1, y ) + 2] =
data[px(x + 1, y )] + quantError * 7 / 16

data[px(x - 1, y + 1)] =
data[px(x - 1, y + 1) + 1] =
data[px(x - 1, y + 1) + 2] =
data[px(x - 1, y + 1)] + quantError * 3 / 16

data[px(x , y + 1)] =
data[px(x , y + 1) + 1] =
data[px(x , y + 1) + 2] =
data[px(x , y + 1)] + quantError * 5 / 16

data[px(x + 1, y + 1)] =
data[px(x + 1, y + 1) + 1] =
data[px(x + 1, y + 1) + 2] =
data[px(x + 1, y + 1)] + quantError * 1 / 16
}
}

结果展示

处理结果这里使用SVG展示,也可以使用canvas画布的putImageData方法绘制。可以看到Floyd-Steinberg处理后的图像比较细腻、失真较小、细节丰富。

参考:
https://observablehq.com/@tmcw/dithering
https://observablehq.com/@tmcw/final-step-of-dithering-to-svg