Closed4

Canvas 上に実装する畳み込みフィルタは Web Worker を使うと早くなる

いなにわうどんいなにわうどん

ガウシアンぼかしを Canvas 上で実装したいなと思って格闘した。ぼかしは畳み込みフィルタと呼ばれる処理に該当し、処理の特徴を表す k \times k のカーネルを w \times h の全画素に対して適用する。愚直に実装すると \mathrm{O}(whk^2) となり、それなりに重い。

結論としては Canvas API が CSS フィルタ を標準でサポートしていることに気が付き、一晩の努力は全くの徒労に終わったのだけれど、せっかくなのでメモ。

いなにわうどんいなにわうどん

愚直に実装する

愚直に JS(TS)で実装すると以下のようなコードになる。当然ながら、ぼかし半径が大きくなるほど処理が重たくなる。

ソースコード
// カーネルの生成
const createKernel = (radius: number) => {
  const kernel: number[][] = [];
  const sigma = radius / 3;
  const coefficient = 1 / (2 * Math.PI * sigma ** 2);

  for (let y = -radius; y <= radius; y++) {
    const row: number[] = [];
    for (let x = -radius; x <= radius; x++) {
      const value =
        coefficient * Math.exp(-(x ** 2 + y ** 2) / (2 * sigma ** 2));
      row.push(value);
    }
    kernel.push(row);
  }
  return kernel;
};

// ぼかしの適用
export const applyGaussianBlurA = async (
  orgContext: CanvasRenderingContext2D,
  radius: number,
  width: number,
  height: number
) => {
  const orgData = orgContext.getImageData(0, 0, width, height);
  const dstData = orgContext.createImageData(width, height);

  const newCanvas = document.createElement("canvas");
  newCanvas.width = width;
  newCanvas.height = height;
  const newContext = newCanvas.getContext("2d");
  if (!newContext || radius <= 1) 
    return;
  }

  const kernel = createKernel(radius);
  const blockSize = newCanvas.width / 1;

  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      let [r, g, b, a] = [0, 0, 0, 0];

      for (let ky = -radius; ky <= radius; ky++) {
        const offsetY = Math.max(0, Math.min(y + ky, height - 1));
        const yi = ky + radius;

        for (let kx = -radius; kx <= radius; kx++) {
          const offsetX = Math.max(0, Math.min(x + kx, width - 1));
          const xi = kx + radius;
          const index = (offsetY * width + offsetX) * 4;

          r += orgData.data[index] * kernel[yi][xi];
          g += orgData.data[index + 1] * kernel[yi][xi];
          b += orgData.data[index + 2] * kernel[yi][xi];
          a += orgData.data[index + 3] * kernel[yi][xi];
        }
      }

      const index = (y * blockSize + x) * 4;
      dstData.data[index] = Math.min(r, 255);
      dstData.data[index + 1] = Math.min(g, 255);
      dstData.data[index + 2] = Math.min(b, 255);
      dstData.data[index + 3] = Math.min(a, 255);
    }
  }
  orgContext.putImageData(dstData, 0, 0);
};

実行結果

1000 × 750 px の画像に対して、半径 20 px のぼかしを適用したときの実行時間は以下の通り。

1 回目 2 回目 3 回目 4 回目 5 回目
3640 ms 3660 ms 3676 ms 3694 ms 3663 ms

ちなみに適用後の画像はこんな感じ。

ぼかし適用後の画像

いなにわうどんいなにわうどん

Wasm に移してみる

同様のロジックを Go を移し、速いと話題の WebAssembly(Wasm)用にビルドしてみた。Go → Wasm コンパイル時のハマりどころは以下のサイトが参考になった。

Go から JS 側のオブジェクトを操作すると極端に遅くなることが解ったので、syscall/js を用いて ImageData を直接操作する代わりに、ImageData.data を引数に与えて js.CopyBytesToGo で byte 型スライスに変換して処理する。最終的に、処理結果は再度 Uint8ClampedArray へと変換する。

Go のソースコード
main.go
package main

import (
	"math"
	"syscall/js"
)

func inRange(x, min, max int) int {
	if x < min {
		x = min
	}
	if x > max {
		x = max
	}
	return x
}

func applyGaussianBlur(this js.Value, args []js.Value) any {
	l := args[0].Length()
	org := make([]byte, l)
	dst := make([]byte, l)
	js.CopyBytesToGo(org, args[0])

	f_org := make([]float64, l)
	for n := range org {
		f_org[n] = float64(org[n])
	}

	w := args[1].Int()
	h := args[2].Int()
	radius := args[3].Int()

	kernel_l := radius*2 + 1
	var kernel = make([][]float64, kernel_l)
	sigma := float64(radius) / 3.0
	coefficient := 1 / (2 * math.Pi * math.Pow(sigma, 2))

	for y := -radius; y <= radius; y++ {
		yi := y + radius
		kernel[yi] = make([]float64, kernel_l)
		for x := -radius; x <= radius; x++ {
			xi := x + radius
			exp := math.Exp(-(math.Pow(float64(x), 2) + math.Pow(float64(y), 2)) / (2 * math.Pow(sigma, 2)))
			kernel[yi][xi] = coefficient * exp
		}
	}

	for y := 0; y < h; y++ {
		for x := 0; x < w; x++ {
			r := 0.0
			g := 0.0
			b := 0.0

			for ky := -radius; ky <= radius; ky++ {
				offsetY := inRange(y+ky, 0, h-1)
				yi := ky + radius

				for kx := -radius; kx <= radius; kx++ {
					offsetX := inRange(x+kx, 0, w-1)
					xi := kx + radius
					index := (offsetY*w + offsetX) * 4
					kernel_v := kernel[yi][xi]

					r += f_org[index] * kernel_v
					g += f_org[index+1] * kernel_v
					b += f_org[index+2] * kernel_v
				}
			}

			index := (y*w + x) * 4
			dst[index] = byte(r)
			dst[index+1] = byte(g)
			dst[index+2] = byte(b)
			dst[index+3] = 255
		}
	}

	res := js.Global().Get("Uint8ClampedArray").New(len(dst))
	js.CopyBytesToJS(res, dst)
	return res
}

func main() {
	ch := make(chan struct{})
	js.Global().Set("applyGoGaussianBlur", js.FuncOf(applyGaussianBlur))
	<-ch
}

公式リポジトリ を参考に wasm_exec.js を用いて繋ぎ込みを行う。これだけでは型が付かないので、@types/golang-wasm-exec をインストールする。また applyGoGaussianBlur は自前で型定義をする必要がある。
wasm コードのロードに 100 ms 程度を要するので、処理実行よりも以前(ページロード時点等)に読み込んでおくと良さそう。

(async () => {
  const go = new Go();
  const { instance } = await WebAssembly.instantiateStreaming(
    fetch("main.wasm"),
    go.importObject
  );
  go.run(instance);
})();

export const applyWasmGaussianBlur = async (
  context: CanvasRenderingContext2D,
  radius: number,
  width: number,
  height: number
) => {
  const imageData = context.getImageData(0, 0, width, height);
  const result = applyGoGaussianBlur(imageData.data, width, height, radius);
  const newData = new ImageData(result, width, height);
  context.putImageData(newData, 0, 0);
};

実行結果

前回と同様の条件で実行した結果は次の通り。明らかに遅くなっている。Go のソースコード側に課題があるのかもしれないが、Go には明るくないので解らず……

1 回目 2 回目 3 回目 4 回目 5 回目
9854 ms 9870 ms 9976 ms 9827 ms 9900 ms
いなにわうどんいなにわうどん

Web Worker に移してみる

冒頭のコードは、画像処理中に操作がブロッキングされる、純粋に処理時間が長い、といった課題を抱えていた。これを解決するために処理内容を Web Worker に移してみる。この際に、画像を一定のサイズでブロック状に区切り、それぞれを並列処理できるように変更する。

Worker のソースコード
filter.worker.ts
self.addEventListener("message", (e) => {
  const { x0, y0, blockSize, radius, kernel, orgData, width, height } =
    e.data as {
      x0: number;
      y0: number;
      blockSize: number;
      radius: number;
      kernel: number[][];
      orgData: ImageData;
      width: number;
      height: number;
    };

  const dstData = new ImageData(blockSize, blockSize);

  for (let y = 0; y < blockSize; y++) {
    for (let x = 0; x < blockSize; x++) {
      let [r, g, b, a] = [0, 0, 0, 0];

      for (let ky = -radius; ky <= radius; ky++) {
        const offsetY = Math.max(0, Math.min(y0 + y + ky, height - 1));
        const yi = ky + radius;

        for (let kx = -radius; kx <= radius; kx++) {
          const offsetX = Math.max(0, Math.min(x0 + x + kx, width - 1));
          const xi = kx + radius;
          const index = (offsetY * width + offsetX) * 4;
          r += orgData.data[index] * kernel[yi][xi];
          g += orgData.data[index + 1] * kernel[yi][xi];
          b += orgData.data[index + 2] * kernel[yi][xi];
          a += orgData.data[index + 3] * kernel[yi][xi];
        }
      }

      const index = (y * blockSize + x) * 4;
      dstData.data[index] = Math.min(r, 255);
      dstData.data[index + 1] = Math.min(g, 255);
      dstData.data[index + 2] = Math.min(b, 255);
      dstData.data[index + 3] = Math.min(a, 255);
    }
  }
  self.postMessage(dstData);
});

export default {};

呼び出し側では Worker をロードしてメッセージを送信する。Worker はループ内で個別に読んだほうが(全体で使い回すよりも)パフォーマンスが良かった。ブロック 1 つ毎の処理を Promise で包んで非同期で実行し、Promise.all を用いて解決する。Worker 内から ImageData に書き込んでも呼び出し元には反映されなかったため、書き込んだ ImageData は必ず postMessage する必要がありそう。

import filterWorker from "./filter.worker?worker";

export const applyGaussianBlur = async (
  context: CanvasRenderingContext2D,
  radius: number,
  width: number,
  height: number
) => {
  const newCanvas = document.createElement("canvas");
  newCanvas.width = width;
  newCanvas.height = height;
  const newContext = newCanvas.getContext("2d");
  if (!newContext || radius <= 1) {
    return;
  }

  const orgData = context.getImageData(0, 0, width, height);
  const kernel = createKernel(radius);
  const blockSize = newCanvas.width / 4;

 const process = (x0: number, y0: number) =>
    new Promise<void>((resolve) => {
      const worker = new filterWorker();
      worker.onmessage = (e) => {
        newContext.putImageData(e.data, x0, y0);
        worker.terminate();
        resolve();
      };
      worker.postMessage({ x0, y0, blockSize, radius, kernel, orgData, width, height });
    });

  const promises: Promise<void>[] = [];
  for (let y0 = 0; y0 < height; y0 += blockSize) {
    for (let x0 = 0; x0 < width; x0 += blockSize) {
      promises.push(process(x0, y0));
    }
  }
  await Promise.all(promises);
  context.drawImage(newCanvas, 0, 0);
};

実行結果

同様の条件で実行した結果は次の通り。分割数 n が 1 のときは明確に遅いが、n=2 にすると劇的に改善し、愚直に実装した場合の半分以下の速度になる。n=4 のときに最速で、以降は分割数を増やしても速度は徐々に遅くなる。40 を越えたあたりで PC がフリーズする。

分割数 1 回目 2 回目 3 回目 4 回目 5 回目
n=1 6226 ms 6223 ms 6249 ms 6211 ms 6284 ms
n=2 1712 ms 1705 ms 1711 ms 1722 ms 1745 ms
n=4 1157 ms 1138 ms 1139 ms 1157 ms 1198 ms
n=8 1563 ms 1554 ms 1532 ms 1695 ms 1596 ms
このスクラップは2024/03/11にクローズされました