GPGPUでSeamCarvingをしてみる

# はじめに

こんにちは、[QualiArts Advent Calendar 2021](https://qiita.com/advent-calendar/2021/qualiarts)、13日目の記事になります。
本日はComputeShaderを利用して、GPGPUでSeam Carvingをしてみるという実験について書きます。

環境：
Unity 2020.3.18f1

# Seam Carvingとは

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

<div>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Broadway_tower_edit.jpg/548px-Broadway_tower_edit.jpg" width="300">
<img src="https://upload.wikimedia.org/wikipedia/commons/e/ed/Broadway_tower_edit_Seam_Carving.png" width="200">
</div>
左の画像[^2]を右の画像[^3]にリサイズする例。


# 問題点

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

しかし、この手法は各行を順番に計算する必要があって、リアルタイムでは向いてない欠点がある。そのため、本記事は**Optimizing Seam Carving on Multi-GPU Systems
for Real-time Image Resizing**[^5]に提案された**NCSC (Non-Cumulative Seam Carving)**を利用して実験する。

# NCSC (Non-Cumulative Seam Carving)
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532685/b87923e9-1044-d9d8-523a-e2d985eb8573.png" width="500">

エネルギー値の累計は順番に計算せず、並行的に行う手法である。
処理の流れ：
①. SumMapに各ピクセルのエネルギーを代入、OffsetMapに次に繋げるピクセルのindex値を代入する
②. 偶数行を奇数行にエネルギーを合計し、次のピクセルに示すindex値も移動する
③. ②と同じロジックで、1行になるまで繰り返す

以下は実際のコード例：

```c#
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);
    }
}
```

```hlsl
[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;
        }
    }
}
```

# 実行結果

![Demo.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532685/795dbdc7-0ace-bd92-7ffd-fc8e9d4acbb9.gif)

ざっくりの実行時間：
256x128 100ピクセル → 3.1ms
1024x1024 400ピクセル → 6.6ms

# 考察

<div>
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/532685/1b502110-cbea-ef9e-0c37-95270b4c49d5.png" width="200">
<img src="https://upload.wikimedia.org/wikipedia/commons/e/ed/Broadway_tower_edit_Seam_Carving.png" width="200">
</div>
左：Non-Cumulative Seam Carving（NCSC）
右：本家 Seam Carving

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

# 終わりに

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

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

[^1]: https://perso.crans.org/frenoy/matlab2012/seamcarving.pdf

[^2]: 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

[^3]: 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

[^4]: By Ygavet - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=67713458

[^5]: https://pacman.cs.tsinghua.edu.cn/~cwg/papers_cwg/icpads14.pdf