Seam Carving

Seam Carving は僕が Computational Thinking で学んだアルゴリズムで、画像の内容に応じてリサイズを行うことができる。通常、画像を Web ページ上に描画する際、サイズがコンテナの幅や高さに合わない場合は以下のような方法を取ることが多い：

画像を等倍（アスペクト比維持）で拡大縮小する
画像の一部をトリミングする

Seam Carving というアルゴリズムを使えば、画像のアスペクト比を変更しつつ自然なトリミングが可能になる。その原理は、リサイズするたびに画像の中で「最も重要でない部分」を見つけ出して削除し、残りの画像を縫い合わせるというものだ。今回はこのアルゴリズムについて紹介しよう！

まずこの画像を見てほしい。

8f2adf0d-b228-4f4c-9108-8f39dbb39a89

この画像の比率を無理やりこのように変更してみる。

画像の内容全体が歪んでしまい、非常によろしくない見た目になっているのがわかる。

Seam Carving を使えば、画像の内容を大まかに保ちながら、アスペクト比にとらわれずに縮小することができる。実際にはどのように実現されているのだろうか？今回はこのアルゴリズムを紹介していく。

Seam Carving の中核となる原理は、画像の中で最も重要でない部分を見つけて削除し、残った部分を「縫合」することだ。では重要なのは、画像の中で「重要でない」部分をどのように見つけるのか、そしてどうやって「重要でない」と定義するのかという点だ。

エッジ検出

まずはこの画像を見てほしい。

rect-1

次にこちらの画像を見てほしい。

rect-2

この画像で最も重要な場所は白黒の境界部分だ。この境界さえ維持できていれば、比率を少々変更したとしても、それほど違和感は感じない。人間の肉眼で見れば一目瞭然だが、これをコンピュータビジョンでどのように見つけ出すのだろうか？

Sobel フィルタによるエッジ検出

Sobel フィルタは 2 つの 3x3 行列から構成される：

K_x = \begin{bmatrix} 1 & 0 & -1 \\ 2 & 0 & -2 \\ 1 & 0 & -1 \end{bmatrix} \qquad K_y = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{bmatrix}

画像を 1 つの行列 $A$ として見なし、各ピクセルとその周囲 3x3 の近傍に $K_x$ 、 $K_y$ をそれぞれ掛けて足し合わせることは、画像に対して畳み込み（Convolution）を行うことと同じで、水平方向と垂直方向の勾配 $G_x$ 、 $G_y$ が得られる。Sobel フィルタは離散差分を計算することで、画像の輝度の勾配値を算出できる：

G_x = K_x * A \qquad G_y = K_y * A \qquad G = \sqrt{G_x^2 + G_y^2}

行列のままだと理解しにくいかもしれないので、コードで見てみよう。旧版の記事では JavaScript の二重ループで 1 ピクセルずつ計算していた。しかし各ピクセルの計算は互いに独立しているので、GPU で並列に処理するのに向いている。以下は WebGPU の compute shader（WGSL）で書いたもので、1 つの thread が 1 ピクセルを担当する：

const KERNEL_X = array<f32, 9>(1.0, 0.0, -1.0, 2.0, 0.0, -2.0, 1.0, 0.0, -1.0);
const KERNEL_Y = array<f32, 9>(1.0, 2.0, 1.0, 0.0, 0.0, 0.0, -1.0, -2.0, -1.0);

fn luminance(x: i32, y: i32) -> f32 {
  let cx = u32(clamp(x, 0, i32(p.width) - 1));
  let cy = u32(clamp(y, 0, i32(p.height) - 1));
  let rgb = unpack4x8unorm(pixels[cy * p.stride + cx]).rgb;
  return dot(rgb, vec3f(0.299, 0.587, 0.114));
}

@compute @workgroup_size(8, 8)
fn computeEnergy(@builtin(global_invocation_id) id: vec3u) {
  if (id.x >= p.width || id.y >= p.height) { return; }

  var gx = 0.0;
  var gy = 0.0;
  for (var i = 0; i < 9; i++) {
    let l = luminance(i32(id.x) + i % 3 - 1, i32(id.y) + i / 3 - 1);
    gx += KERNEL_X[i] * l;
    gy += KERNEL_Y[i] * l;
  }
  energy[id.y * p.stride + id.x] = sqrt(gx * gx + gy * gy);
}

luminance で RGB をグレースケールの輝度に変換し、3x3 の近傍に 2 つの kernel をそれぞれ掛けて勾配の大きさを求める。端のピクセルは clamp で最も近いピクセルを代わりに使う。

ここでの stride は元画像の幅だ。seam を 1 本削除するたびに画像の幅は 1 ピクセル減るが、buffer のサイズは変わらないので、インデックスは固定の stride で計算し、範囲チェックには現在の width を使う。

これが原画だ：

Sobel エッジ検出を通した後がこちら：

sobel

処理後の画像を見ると、境界部分（輝度変化が大きい場所）の値ほど白に近づく（つまり 255 に近くなる）。一方で、輝度変化が目立たない場所は黒くなる（0 に近くなる）。

画像内の重要でない成分を計算する

エッジは画像において重要な部分である（白ければ白いほど重要）ため、上から下へと隣接するピクセルの中から最小値を探していき、それを画像から削除していけばよい。

しかし、単純に上から下へと貪欲法（Greedy）で探索してしまうと、全体最適（グローバルな最小値）にならない場合がある。例えば：

\begin{bmatrix} 0.9 & 0.8 & 0.7 \\ 0.1 & 0.1 & 0.05 \\ 0.1 & 1.5 & 1.5 \end{bmatrix}

最上段で最も小さい 0.7 から始めて、毎回すぐ下で最も小さい隣を選ぶと 0.7 + 0.05 + 1.5 = 2.25 になる。しかし 2 段目で 0.1 を選べば 0.7 + 0.1 + 0.1 = 0.9 になる。各ステップで最小値を選んでも、経路全体が最小になるとは限らない。Sobel 処理を経た行列データを energy と呼ぶことにする。この energy に対して事前に前処理を施すことができる。

まず元の energy の最下行をコピーし、下から上へと、各マスに「すぐ下の隣接する 3 つの要素の最小値」を足していく。こうすると各マスには「そのマスから最下段までの最小の合計 energy」が入る。これが動的計画法（DP）による書き方だ：

\begin{bmatrix} 1.1 & 1.0 & 0.9 \\ 0.2 & 0.2 & 1.55 \\ 0.1 & 1.5 & 1.5 \end{bmatrix}

こうすれば、最上段で最も小さい 0.9 から探し始め、順に 0.2、0.1 と辿ることができる。すでに前処理されているため、この経路が合計 energy が最小となることが保証される。

あとは対応する座標 [x, y] を記録しておけばよい。上記の例で言えば、次のようになる：

[[2, 0], [1, 1], [0, 2]]

GPU で動的計画法を計算する

Sobel は各ピクセルを独立して計算できるが、動的計画法はそうはいかない。各行はすぐ下の行の計算が終わるのを待つ必要がある。そこで、workgroup を 1 つだけ起動し、256 個の thread で同じ行の各マスを分担する。1 行分を計算し終えたら storageBarrier() ですべての thread の書き込みを待ち、上の行へ進む。

合計 energy が最小の経路を辿る処理は、各ステップが前のステップの結果に依存するため順番に実行するしかない。なので 1 つの thread に任せる：

const THREADS = 256u;

@compute @workgroup_size(THREADS)
fn findSeam(@builtin(local_invocation_index) tid: u32) {
  let last = (p.height - 1u) * p.stride;
  for (var x = tid; x < p.width; x += THREADS) {
    cost[last + x] = energy[last + x];
  }

  for (var y = i32(p.height) - 2; y >= 0; y--) {
    storageBarrier();
    let row = u32(y) * p.stride;
    let below = row + p.stride;
    for (var x = tid; x < p.width; x += THREADS) {
      let left = max(x, 1u) - 1u;
      let right = min(x + 1u, p.width - 1u);
      let minBelow = min(cost[below + left], min(cost[below + x], cost[below + right]));
      cost[row + x] = energy[row + x] + minBelow;
    }
  }
  storageBarrier();

  if (tid != 0u) { return; }

  var x = 0u;
  for (var i = 1u; i < p.width; i++) {
    if (cost[i] < cost[x]) { x = i; }
  }
  seam[0] = x;

  for (var y = 1u; y < p.height; y++) {
    let row = y * p.stride;
    let prev = x;
    if (prev > 0u && cost[row + prev - 1u] < cost[row + x]) { x = prev - 1u; }
    if (prev + 1u < p.width && cost[row + prev + 1u] < cost[row + x]) { x = prev + 1u; }
    seam[y] = x;
  }
}

最後に seam より右側のピクセルを 1 つ左へずらせば完了だ。ここも各ピクセルを並列に処理できる。他の thread がすでに書き換えた値を読まないように、別の buffer に書き込んでからコピーし直す：

@compute @workgroup_size(8, 8)
fn removeSeam(@builtin(global_invocation_id) id: vec3u) {
  if (id.x >= p.width - 1u || id.y >= p.height) { return; }

  let source = select(id.x, id.x + 1u, id.x >= seam[id.y]);
  scratch[id.y * p.stride + id.x] = pixels[id.y * p.stride + source];
}

JavaScript 側では、この 3 つの pass を順番に dispatch するだけだ。seam を 1 本削除するたびに幅が 1 減る：

const encoder = device.createCommandEncoder()
const pass = encoder.beginComputePass()
pass.setBindGroup(0, bindGroup)
pass.setPipeline(energyPipeline)
pass.dispatchWorkgroups(Math.ceil(width / 8), Math.ceil(height / 8))
pass.setPipeline(seamPipeline)
pass.dispatchWorkgroups(1)
pass.setPipeline(removePipeline)
pass.dispatchWorkgroups(Math.ceil(width / 8), Math.ceil(height / 8))
pass.end()
encoder.copyBufferToBuffer(scratch, 0, pixels, 0, pixels.size)
device.queue.submit([encoder.finish()])

描画は render pass で同じ storage buffer を読んで canvas に描く。ピクセルは最初から最後まで GPU 上にあり、CPU に読み戻す必要はない。

効果

スライダーを動かすと画像の幅が縮む。赤い線が次に削除される seam だ。Energy に切り替えると Sobel 処理後の結果が見られるし、自分の画像も試せる（画像はブラウザ内で処理され、アップロードはされない）。

Seam Carving のデモを読み込み中...

ブラウザが WebGPU に対応していない場合は、こちらの動画をどうぞ：

アスペクト比を維持せずに縮小できるとは言ったものの、画像の内容によってはやはり不自然に見えてしまうこともある。特に画像の重要な情報が削除されていくにつれて、違和感は増していく。それでも、非常に興味深く面白いアルゴリズムだと僕は思う。

**「重要でない部分を取り除く」**という基本思想は、実はさまざまな場所で見られる。例えば音声サンプリングにおいて、人間の耳には聞こえない高周波成分をカットして容量を節約したり、複雑すぎる行列を SVD（特異値分解）によって重要な特徴ベクトルだけで表現したりする。一見関連性がないように思えるが、根底にある考え方は共通している。

あとがき

旧版の実装は JavaScript のループで 1 ピクセルずつ処理していたので、画像が大きくなると目に見えて遅延していた。WebGPU に移行してからは、Sobel も seam の削除もピクセル単位で並列に計算され、スライダーの操作にリアルタイムで追従できる。

惜しいのは動的計画法の部分で、各行がすぐ下の行に依存するため、1 つの workgroup で 1 行ずつ計算するしかなく、GPU 全体を使い切れない。もう 1 つの最適化として、seam を 1 本削除しても energy が変わるのは seam の周辺だけなので、毎回画像全体を再計算する必要はない。

実際の運用においては、効果は優れているものの、やはり画像の内容に依存する。画像全体のディテールが重要で、どこにも明確な輝度変化があるような画像の場合は、Seam Carving を使ってもやはり大きな歪みが生じてしまうだろう。

カテゴリー

ページ

その他

Seam Carving – アスペクト比を維持せずに画像を縮小する