はじめに

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

環境：
Unity 2020.3.18f1

Seam Carvingとは

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

左の画像²を右の画像³にリサイズする例。

問題点

赤数字：ピクセルのエネルギー値
黒数字：N行まで伝搬してきた一番低いのエネルギー累計値
上記の図⁴に示されたアルゴリズムで、画像全体に対して一番低いエネルギー累計値のSeamを導出するステップが必要である。単純に各ピクセルをループしても良いが、本論文¹は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日目の記事でした。引き続き今後のカレンダー投稿を宜しくお願いします。

https://perso.crans.org/frenoy/matlab2012/seamcarving.pdf ↩
By Broadway_tower.jpg: Newton2 at en.wikipediaderivative work: Damir-NJITWILL (talk) - Broadway_tower.jpg, CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=12125976 ↩
By Broadway_tower.jpg: Newton2 at en.wikipediaderivative work: Damir-NJITWILL (talk) - Broadway_tower.jpg, CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=12125991 ↩
By Ygavet - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=67713458 ↩
https://pacman.cs.tsinghua.edu.cn/~cwg/papers_cwg/icpads14.pdf ↩

GPGPUでSeamCarvingをしてみる

はじめに

Seam Carvingとは

問題点

NCSC (Non-Cumulative Seam Carving)

実行結果

考察

終わりに