Floyd-Steinberg扩散抖动算法

2019.01/Uncategorized

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

京ICP备14036213号-2