4. Box Blur

4.1 基礎知識

Box Blurアルゴリズムも畳み込み演算を用いるが、各位置に同じ重みを持つ畳み込みカーネルを使用し、例えば3*3の畳み込みカーネルは次のように表すことができる。

Box Blurの畳み込みカーネルも線形分離可能なので、分離可能なGaussian Blurと同じように、2次元のBox Blur畳み込み演算を2つの1次元Box Blur畳み込み演算に分割することができます。例として、3×3 Box Blur の畳み込みカーネルが挙げられます。

各位置で同じ重みを持つ畳み込みカーネルは、処理によって得られる各画素点の値が、自身の画素値とフィールド内の他の画素値の平均となることを意味します。この利点は、スライディングウィンドウアルゴリズムを使用せず、より高速な累積アルゴリズムで実装できることです[1]。行列を処理する場合、畳み込みカーネルサイズの最初の要素について、累積和の平均を計算し、出力に書き込みます。その後の新しい要素については、累積和から畳み込みカーネルでカバーされなくなった要素を引き、新しい要素に加え、平均を計算し、出力に書き込みます。このことから、1次元のBox Blur演算では、1つの要素を処理する時間複雑度は、畳み込みカーネルの長さに依存せず、O(1)の定数であることがわかります。

(https://www.intel.com/content/www/us/en/developer/articles/technical/an-investigation-of-fast-real-time-gpu-based-image-blur-algorithms.htmlより)

9×9のBox Blur 畳み込みカーネルを例にとると、横方向の処理は次のように表されます。

(https://www.intel.com/content/www/us/en/developer/articles/technical/an-investigation-of-fast-real-time-gpu-based-image-blur-algorithms.htmlより)

しかし、現代のGPUの実行は高度に並列化され、無秩序であり、アキュムレータを用いて時間複雑性を低減する最適化は、CPUの計算には有効だが、GPUには有効ではありません。そのためには、Computer Shaderを使ってそのような操作を行うことを検討してください。これにより、時間の複雑さが一定になる反面、アルゴリズムの固定費が増加します。

その後の実装によると、以下のような結果が得られました。

Box Blurを一度行った結果の品質は、Gaussian Blur処理を行った結果の品質とはかけ離れていることがよくわかります。これに対して、中心極限定理は、適切な条件下で、多数の互いに独立な確率変数の平均が、適切な正規化後に正規分布に収束することを述べています[2]。つまり、ボックスぼかしを数回かけると、最終的にGaussian Blurに近い品質になるのです。このようにして、アルゴリズムの固定費がさらに増加します。

4.2 Unityの実装

上記のアルゴリズムに基づき、Unityでは、ComputerShaderを利用し、アキュムレータを用いたBox Blurアルゴリズムを実装します。

ComputerShaderを新規に作成し、1024×768の画面に後処理を行います。

まず、水平方向の処理を行い、画像の境界から外れたサンプルは、境界の画素値をサンプリングして補完します。各行のデータを確実に共有するために、各行を1スレッドとし、合計768スレッドとします。

[numthreads(1,768,1)]
void BoxBlurX(uint3 id : SV_DispatchThreadID)
{
	float4 colourSum = InputRT[int2(0, id.y)] * BlurDiameter / 2;
	for (int index = 0; index <= BlurDiameter / 2; index++)
		colourSum += InputRT[int2(index, id.y)];
	for (int index = 0; index < InputRTWidth; index++)
	{
		Result[int2(index,id.y)] = colourSum / BlurDiameter;

		// move window to the next 
		float4 leftBorder = InputRT[int2(max(index - BlurDiameter / 2, 0), id.y)];
		float4 rightBorder = InputRT[int2(min(index + BlurDiameter / 2 + 1, InputRTWidth - 1), id.y)];

		colourSum -= leftBorder;
		colourSum += rightBorder;
	}
}

垂直方向の処理も同様で、合計1024スレッドになります。

[numthreads(1024, 1, 1)]
void BoxBlurY(uint3 id : SV_DispatchThreadID)
{
	float4 colourSum = InputRT[int2(id.x, 0)] * BlurDiameter / 2;
	for (int index = 0; index <= BlurDiameter / 2; index++)
		colourSum += InputRT[int2(id.x, index)];
	for (int index = 0; index < InputRTHeight; index++)
	{
		Result[int2(id.x,index)] = colourSum / BlurDiameter;

		// move window to the next 
		float4 leftBorder = InputRT[int2(id.x, max(index - BlurDiameter / 2, 0))];
		float4 rightBorder = InputRT[int2(id.x, min(index + BlurDiameter / 2 + 1, InputRTHeight - 1))];

		colourSum -= leftBorder;
		colourSum += rightBorder;
	}
}

Csharp側でComputerShaderを呼び出し、BoxBlurの処理を1行で行う。

private void OnRenderImage(RenderTexture input, RenderTexture output)
{
    BoxBlurShader.SetInt("BlurDiameter", BlurDiameter);
    BoxBlurShader.SetInt("InputRTWidth", input.width);
    BoxBlurShader.SetInt("InputRTHeight", input.height);

    BoxBlurShader.SetTexture(kernelHandleX, "InputRT", input);
    BoxBlurShader.SetTexture(kernelHandleX, "Result", tmp0);
    BoxBlurShader.Dispatch(kernelHandleX, 1, 1, 1);

    BoxBlurShader.SetTexture(kernelHandleY, "InputRT", tmp0);
    BoxBlurShader.SetTexture(kernelHandleY, "Result", tmp1);
    BoxBlurShader.Dispatch(kernelHandleY, 1, 1, 1);
    Graphics.Blit(tmp1, output);
}

サイズ36×36の畳み込みカーネルを選び、以下の結果を得ます。

ご覧の通り、非常にはっきりとしたモザイクがかかっているので、さらにBox Blur処理を実行します。

非常に良い結果が出てきました。

4.3まとめ

Box Blurアルゴリズムの大きな利点は、要素の処理にかかる時間的複雑さを定数に減らし、畳み込みカーネルのサイズに関係しなくすることです。しかし、固定費が高いのが難点です。また、Computer Shaderを使用しているため、このアルゴリズムにサッポートしないデバイスもあります。このアルゴリズムの性能上の利点は、使用する畳み込みコアのサイズがある閾値を超えた場合にのみ発揮してくれます。そのため、一部の特殊なケースにしか適さないと言えます。

参考資料

[1] https://en.wikipedia.org/wiki/Box_blur

[2]https://zh.wikipedia.org/wiki/%E4%B8%AD%E5%BF%83%E6%9E%81%E9%99%90%E5%AE%9A%E7%90%86

UWA Technologyは、モバイル/VRなど様々なゲーム開発者向け、パフォーマンス分析と最適化ソリューション及びコンサルティングサービスを提供している会社でございます。

今なら、UWA GOTローカルツールが15日間に無償試用できます！！
よければ、ぜひ！

UWA公式サイト：https://jp.uwa4d.com
UWA GOT OnlineレポートDemo：https://jp.uwa4d.com/u/got/demo.html
UWA公式ブログ：https://blog.jp.uwa4d.com