はじめに
こんにちは、QualiArts Advent Calendar 2021、13日目の記事になります。
本日はComputeShaderを利用して、GPGPUでSeam Carvingをしてみるという実験について書きます。
環境：
Unity 2020.3.18f1
Seam Carvingとは
2007年に発表された画像リサイズのアルゴリズム1である。
ピクセルごとに隣接との値差分を計算してエネルギー値を導出し、低いエネルギー値で繋がった**繋ぎ目（Seam）**を削除する事で、シームレスに画像リサイズできる手法である。
問題点
赤数字：ピクセルのエネルギー値
黒数字：N行まで伝搬してきた一番低いのエネルギー累計値
上記の図[^4]に示されたアルゴリズムで、画像全体に対して一番低いエネルギー累計値のSeamを導出するステップが必要である。単純に各ピクセルをループしても良いが、本論文[^1]はDynamic Programmingを用いて計算済みのエネルギーを次の行に伝搬する手法を提案された。
しかし、この手法は各行を順番に計算する必要があって、リアルタイムでは向いてない欠点がある。そのため、本記事はOptimizing Seam Carving on Multi-GPU Systems
for Real-time Image Resizing2に提案された**NCSC (Non-Cumulative Seam Carving)**を利用して実験する。
NCSC (Non-Cumulative Seam Carving)
エネルギー値の累計は順番に計算せず、並行的に行う手法である。
処理の流れ：
①. SumMapに各ピクセルのエネルギーを代入、OffsetMapに次に繋げるピクセルのindex値を代入する
②. 偶数行を奇数行にエネルギーを合計し、次のピクセルに示すindex値も移動する
③. ②と同じロジックで、1行になるまで繰り返す
以下は実際のコード例：
void CalculateEnergySum(Vector4 imageSize)
{
var kernel = shader.FindKernel("CalculateEnergySum");
shader.SetTexture(kernel, "Result", _renderTexture);
shader.SetBuffer(kernel, "EnergyMap", _energyMap);
shader.SetBuffer(kernel, "SumOffset", _sumOffset);
var dispatch = GetDispatchCount(kernel, imageSize);
// Mathf.Log(高さ, 2)でステップの数を算出
for (var i = 0; i < Mathf.Log(imageSize.y, 2); i++)
{
shader.SetInt("EnergySumStep", i + 1);
shader.Dispatch(kernel, 1, dispatch.y, 1);
}
}
[numthreads(1, 128, 1)]
void CalculateEnergySum(uint3 id: SV_DispatchThreadID)
{
// 渡されたEnergySumStepで対象の行だけ処理させる
if (id.y % (1 << EnergySumStep) == 0)
{
for (uint x = 0; x < SizeX; x++)
{
uint index = x + id.y * SizeX;
uint offset = SumOffset[index].y;
SumOffset[index].x += SumOffset[offset].x;
SumOffset[index].y = SumOffset[offset].y;
}
}
}
実行結果
ざっくりの実行時間：
256x128 100ピクセル → 3.1ms
1024x1024 400ピクセル → 6.6ms
考察
むむ、人間の姿が完全に消えた。
もっといろんな画像で比較してみたいが、NCSCは最適のSeamを探していないので、小さい物体を消えやすいように思われる。
今回は最低限の実装で実験を行ったが、パラメーター化や一回の処理で複数のSeamを削除するなどの最適化をすればより速くなると思われる。
終わりに
実際のコードはgithubに公開していますので、興味ある方ぜひこちらへどうぞ。
https://github.com/thammin/gpu-seam-carving
以上、13日目の記事でした。引き続き今後のカレンダー投稿を宜しくお願いします。