はじめに

こんにちは、QualiArts Advent Calendar 2021、13日目の記事になります。
本日はComputeShaderを利用して、GPGPUでSeam Carvingをしてみるという実験について書きます。

環境：
Unity 2020.3.18f1

Seam Carvingとは

2007年に発表された画像リサイズのアルゴリズム¹である。
ピクセルごとに隣接との値差分を計算してエネルギー値を導出し、低いエネルギー値で繋がった**繋ぎ目（Seam）**を削除する事で、シームレスに画像リサイズできる手法である。

左の画像[^2]を右の画像[^3]にリサイズする例。

問題点

赤数字：ピクセルのエネルギー値黒数字：N行まで伝搬してきた一番低いのエネルギー累計値上記の図[^4]に示されたアルゴリズムで、画像全体に対して一番低いエネルギー累計値のSeamを導出するステップが必要である。単純に各ピクセルをループしても良いが、本論文[^1]はDynamic Programmingを用いて計算済みのエネルギーを次の行に伝搬する手法を提案された。

しかし、この手法は各行を順番に計算する必要があって、リアルタイムでは向いてない欠点がある。そのため、本記事はOptimizing Seam Carving on Multi-GPU Systems
for Real-time Image Resizing²に提案された**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

考察

左：Non-Cumulative Seam Carving（NCSC）右：本家 Seam Carving

むむ、人間の姿が完全に消えた。
もっといろんな画像で比較してみたいが、NCSCは最適のSeamを探していないので、小さい物体を消えやすいように思われる。
今回は最低限の実装で実験を行ったが、パラメーター化や一回の処理で複数のSeamを削除するなどの最適化をすればより速くなると思われる。

終わりに

実際のコードはgithubに公開していますので、興味ある方ぜひこちらへどうぞ。
https://github.com/thammin/gpu-seam-carving

以上、13日目の記事でした。引き続き今後のカレンダー投稿を宜しくお願いします。