Chapter 85

誤差拡散法

miku
miku
2021.11.19に更新

実行例


解説

誤差拡散法は二値化と同じように画像を白黒に変換するアルゴリズム。

二値化との違い

二値化ではあらかじめ決めておいた閾値をもとに白か黒に変換するかを判断する。たとえば閾値が 127 以下の場合は 0(黒) に、そうでなければ 255(白) に変換するとルールを決めておく。

対象のピクセルの明るさが 10 であれば 0 に、明るさが 240 であれば 255 になるという風に、対象のピクセルがもともと黒か白に近い明るさを真っ黒もしくは真っ白にするというのは納得がいく。しかし、たとえば値が 127 のような灰色の明るさならどうだろうか。中間の明るさなのに閾値という単純なルールの比較だけで黒か白が決まるのでは、もともとの情報がかなり失われることになる。明るさが 100 の場合は 0 に変換されるが、もともとの明るさと比較して 100 の差が出る。白に変換する場合でも同じで、たとえば値が 200 の場合、255 に変換されるが、55 の差が出る。

このような本来の値との差を誤差と呼び、この誤差を隣接しているピクセルに渡し、そのピクセルの二値化を行う際、渡した誤差情報を含めて判定するのが誤差拡散法の特徴となる。つまり一つのピクセルではなく、周りのピクセルを含めて多角的に二値化の判定を行うと情報を減らさずに白黒にできるのではないか、というのがこのアルゴリズムの肝となる。

この変換方法では二値化と同じように白か黒に変換しないのにも関わらず、実際の変換画像を見ると灰色が使用されているように見える。このように少ない色で多くの明るさがあるかのように見せる仕組みをディザリングと呼ぶ。

右に誤差を渡す

let img;

function preload() {
  img = loadImage("./0.png");
}

function setup() {
  createCanvas(img.width, img.height);
  img.loadPixels();

  const threshold = 127;
  for (let y = 0; y < img.height; y++) {
    let prev = 0;
    for (let x = 0; x < img.width; x++) {
      const color = getPixel(x, y);
      const r = red(color);
      const g = green(color);
      const b = blue(color);

      let gray = 0.299 * r + 0.587 * g + 0.114 * b;
      gray += prev;

      let c = [0, 0, 0];
      if (threshold < gray) {
        c = [255, 255, 255];
        prev = gray - 255;
      } else {
        prev = gray;
      }

      setPixel(x, y, c);
    }
  }

  img.updatePixels();
  image(img, 0, 0);
}

function getPixel(x, y) {
  const i = (y * img.width + x) * 4;
  return [
    img.pixels[i],
    img.pixels[i + 1],
    img.pixels[i + 2],
    img.pixels[i + 3],
  ];
}

function setPixel(x, y, pixel) {
  const i = (y * img.width + x) * 4;
  img.pixels[i + 0] = pixel[0];
  img.pixels[i + 1] = pixel[1];
  img.pixels[i + 2] = pixel[2];
}

右に誤差を伝播させる作例。

実行結果はモアレが目立つので実用的ではないが、誤差の伝播を説明するにはわかりやすいと思うのでまずはこの条件で説明を行う。例えば明るさが 200 の場合 255 に変換されるが、誤差は -55 となる。これは 白(255) に変換されたが本来の値はこれよりも -55 の値なので、その誤差情報 -55 を右のピクセルに渡して加味させる。黒に変換する場合も同様で、例えば明るさが 100 の場合、誤差は 100 となる。黒(0) に変換されたが本来の値はこれよりも 100 大きい値なので、その誤差情報 +100 を右のピクセルに渡して加味させる。

Floyd–Steinberg(左下/下/右下/右に誤差を渡す)

1 2 3
- - -
- * 7/16
3/16 5/16 1/16
  • 右に 7/16
  • 左下に 3/16
  • 下に 5/16
  • 右下に 1/16

Floyd–Steinberg はディザリングで最も有名な誤差分配方法。

for (let y = 0; y < img.height; y++) {
  for (let x = 0; x < img.width; x++) {
    // ...
  }
}

画像の走査は左から右、上から下に行うのが前提となる。

Floyd–Steinberg法で伝搬する場合の作例。

コード例

let img;

function preload() {
  img = loadImage("./0.png");
}

function setup() {
  createCanvas(img.width, img.height);
  img.loadPixels();

  const error = [];
  for (let y = 0; y < img.height; y++) {
    error[y] = [];
    for (let x = 0; x < img.width; x++) {
      error[y][x] = 0;
    }
  }

  const threshold = 127;

  for (let y = 0; y < img.height; y++) {
    for (let x = 0; x < img.width; x++) {
      const color = getPixel(x, y);

      const r = red(color);
      const g = green(color);
      const b = blue(color);

      let gray = 0.299 * r + 0.587 * g + 0.114 * b;
      gray += error[y][x];

      let v = 0;
      if (threshold <= gray) {
        v = 255;
      }

      const e = (gray - v) / 16;

      if (onBoard(x + 1, y)) {
        error[y][x + 1] += e * 7;
      }
      if (onBoard(x - 1, y + 1)) {
        error[y + 1][x - 1] += e * 3;
      }
      if (onBoard(x, y + 1)) {
        error[y + 1][x] += e * 5;
      }
      if (onBoard(x + 1, y + 1)) {
        error[y + 1][x + 1] += e;
      }

      setPixel(x, y, [v, v, v]);
    }
  }

  img.updatePixels();
  image(img, 0, 0);
}

function onBoard(x, y) {
  return 0 <= x && x < img.width && 0 <= y && y < img.height;
}

function getPixel(x, y) {
  const i = (y * img.width + x) * 4;
  return [
    img.pixels[i],
    img.pixels[i + 1],
    img.pixels[i + 2],
    img.pixels[i + 3],
  ];
}

function setPixel(x, y, pixel) {
  const i = (y * img.width + x) * 4;
  img.pixels[i + 0] = pixel[0];
  img.pixels[i + 1] = pixel[1];
  img.pixels[i + 2] = pixel[2];
}