Seam Carving – アスペクト比を維持せずに画像を縮小する
Seam Carving は僕が Computational Thinking で学んだアルゴリズムで、画像の内容に応じてリサイズを行うことができる。通常、画像を Web ページ上に描画する際、サイズがコンテナの幅や高さに合わない場合は以下のような方法を取ることが多い：
- 画像を等倍（アスペクト比維持）で拡大縮小する
- 画像の一部をトリミングする
Seam Carving というアルゴリズムを使えば、画像のアスペクト比を変更しつつ自然なトリミングが可能になる。その原理は、リサイズするたびに画像の中で「最も重要でない部分」を見つけ出して削除し、残りの画像を縫い合わせるというものだ。今回はこのアルゴリズムについて紹介しよう！
まずこの画像を見てほしい。
この画像の比率を無理やりこのように変更してみる。
画像の内容全体が歪んでしまい、非常によろしくない見た目になっているのがわかる。
Seam Carving を使えば、画像の内容を大まかに保ちながら、アスペクト比にとらわれずに縮小することができる。実際にはどのように実現されているのだろうか？ 今回はこのアルゴリズムを紹介していく。
Seam Carving
Seam Carving の中核となる原理は、画像の中で最も重要でない部分を見つけて削除し、残った部分を「縫合」することだ。では重要なのは、画像の中で「重要でない」部分をどのように見つけるのか、そしてどうやって「重要でない」と定義するのかという点だ。
エッジ検出
まずはこの画像を見てほしい。
次にこちらの画像を見てほしい。
この画像で最も重要な場所は白黒の境界部分だ。この境界さえ維持できていれば、比率を少々変更したとしても、それほど違和感は感じない。人間の肉眼で見れば一目瞭然だが、これをコンピュータビジョンでどのように見つけ出すのだろうか？
Sobel フィルタによるエッジ検出
Sobel フィルタは 2 つの 3x3 行列から構成される：
画像を 1 つの行列として見なし、画像のピクセルとこの行列を掛け合わせて勾配値を求めることは、画像に対して畳み込み（Convolution）を行うことと同じだ。Sobel フィルタは離散差分を計算することで、画像の輝度の勾配値を算出できる。
行列のままだと理解しにくいかもしれないが、コードで表せばずっと分かりやすくなるはずだ：
// 程式碼參考 https://github.com/miguelmota/sobel/blob/master/sobel.js
function Sobel(imageData) {
var width = imageData.width;
var height = imageData.height;
var kernelX = [
[-1, 0, 1],
[-2, 0, 2],
[-1, 0, 1],
];
var kernelY = [
[-1, -2, -1],
[0, 0, 0],
[1, 2, 1],
];
var sobelData = [];
var grayscaleData = [];
function bindPixelAt(data) {
return function (x, y, i) {
i = i || 0;
return data[(width * y + x) * 4 + i];
};
}
var data = imageData.data;
var pixelAt = bindPixelAt(data);
var x, y;
for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
var r = pixelAt(x, y, 0);
var g = pixelAt(x, y, 1);
var b = pixelAt(x, y, 2);
var avg = (r + g + b) / 3;
grayscaleData.push(avg, avg, avg, 255);
}
}
pixelAt = bindPixelAt(grayscaleData);
for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
var pixelX =
kernelX[0][0] * pixelAt(x - 1, y - 1) +
kernelX[0][1] * pixelAt(x, y - 1) +
kernelX[0][2] * pixelAt(x + 1, y - 1) +
kernelX[1][0] * pixelAt(x - 1, y) +
kernelX[1][1] * pixelAt(x, y) +
kernelX[1][2] * pixelAt(x + 1, y) +
kernelX[2][0] * pixelAt(x - 1, y + 1) +
kernelX[2][1] * pixelAt(x, y + 1) +
kernelX[2][2] * pixelAt(x + 1, y + 1);
var pixelY =
kernelY[0][0] * pixelAt(x - 1, y - 1) +
kernelY[0][1] * pixelAt(x, y - 1) +
kernelY[0][2] * pixelAt(x + 1, y - 1) +
kernelY[1][0] * pixelAt(x - 1, y) +
kernelY[1][1] * pixelAt(x, y) +
kernelY[1][2] * pixelAt(x + 1, y) +
kernelY[2][0] * pixelAt(x - 1, y + 1) +
kernelY[2][1] * pixelAt(x, y + 1) +
kernelY[2][2] * pixelAt(x + 1, y + 1);
var magnitude = Math.sqrt(pixelX * pixelX + pixelY * pixelY);
sobelData.push(magnitude, magnitude, magnitude, 255);
}
}
var clampedArray = sobelData;
return clampedArray;
}コードから分かるように、Sobel エッジ検出が実際に行っているのは、画像をまずグレースケールに変換し、その後各ピクセルと隣接ピクセルとの勾配値を計算することだ。
続いて Sobel 処理を施した画像を canvas に描画してみよう。これが原画だ：
Sobel エッジ検出を通した後がこちら：
処理後の画像を見ると、境界部分（輝度変化が大きい場所）の値ほど白に近づく（つまり 255 に近くなる）。一方で、輝度変化が目立たない場所は黒くなる（0 に近くなる）。
画像内の重要でない成分を計算する
エッジは画像において重要な部分である（白ければ白いほど重要）ため、上から下へと隣接するピクセルの中から最小値を探していき、それを画像から削除していけばよい。
しかし、単純に上から下へと貪欲法（Greedy）で探索してしまうと、全体最適（グローバルな最小値）にならない場合がある。例えば：
0.7 から探し始めると、0.7 + 0.05 + 1.5 = 2.25 となる。しかし 0.8 から始めると、0.8 + 0.1 + 0.1 = 1.0 になる。Sobel 処理を経た行列データを energy と呼ぶことにする。この energy に対して事前に前処理を施すことができる。
まず一番底の行から始める。常に最小値を選んでいくため、現在の最小値がグローバルな最小値であることが保証され、動的計画法（DP）で実装できる。まず元の energy の最下行をコピーし、下から上へと、隣接する要素の最小値を計算して自身の値に足していく：
こうすれば、直接 1.0 から探し始め、順に 0.2、0.1 と辿ることができる。すでに前処理されているため、この経路が合計 energy が最小となることが保証される。
あとは対応する座標を記録しておけばよい。上記の例で言えば、次のようになる：
[[1, 0], [0, 1], [0, 2]]最後に対応するピクセルを削除すれば完了だ。JavaScript での実装は以下のようになる：
function buildEnergyMap(data, width, height) {
const energy = new Float32Array(width * height);
const getIndex = (x, y) => (y * width + x) * 4;
const getXY = (x, y) => y * width + x;
// bottom
// build bottom array
for (let x = width - 1; x >= 0; x--) {
const y = height - 1;
energy[y * width + x] = data[getIndex(x, y)];
}
for (let y = height - 2; y >= 0; y--) {
for (let x = 0; x < width; x++) {
const left = Math.max(0, x - 1);
const right = Math.min(x + 1, width - 1);
const minEnergy = Math.min(
energy[getXY(left, y + 1)],
energy[getXY(x, y + 1)],
energy[getXY(right, y + 1)]
);
energy[getXY(x, y)] += minEnergy;
energy[getXY(x, y)] += data[getIndex(x, y)] / 255;
}
}
return energy;
}
function seamCarving(canvas) {
const ctx = canvas.getContext("2d");
const imgData = ctx.getImageData(0, 0, canvas.width, canvas.height);
const { width, height, data } = imgData;
// Find the seam with minimum energy using dynamic programming
const energyMap = buildEnergyMap(data, canvas.width, canvas.height);
const seam = findSeam(energyMap, canvas.width, canvas.height);
for (let y = 0; y < height; y++) {
const seamIndex = seam[y][0];
for (let x = seamIndex; x < width - 1; x++) {
const offset = (y * width + x) * 4;
const nextOffset = (y * width + (x + 1)) * 4;
data[offset] = data[nextOffset];
data[offset + 1] = data[nextOffset + 1];
data[offset + 2] = data[nextOffset + 2];
data[offset + 3] = data[nextOffset + 3];
data[nextOffset] = 255;
data[nextOffset + 1] = 255;
data[nextOffset + 2] = 255;
data[nextOffset + 3] = 255;
}
}
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.putImageData(imgData, 0, 0);
}
function findSeam(energyMap, width, height, startPoint) {
const getIndex = (x, y) => y * width + x;
let min = Number.MAX_VALUE;
let idx;
for (let x = 0; x < width; x++) {
if (min > energyMap[x]) {
min = energyMap[x];
idx = x;
}
}
const seam = [];
seam.push([idx, 0]);
let x = idx;
if (startPoint) {
x = startPoint;
}
for (let y = 0; y < height - 1; y++) {
let min = Number.MAX_VALUE;
const left = Math.max(0, x - 1);
const right = Math.min(x + 1, width - 1);
const leftValue = energyMap[getIndex(left, y + 1)];
const centerValue = energyMap[getIndex(x, y + 1)];
const rightValue = energyMap[getIndex(right, y + 1)];
const pairs = [
[left, leftValue],
[x, centerValue],
[right, rightValue],
];
let minX;
for (let i = 0; i < pairs.length; i++) {
min = Math.min(pairs[i][1], min);
}
const target = pairs.find((pair) => pair[1] === min);
seam.push([target[0], y + 1]);
x = target[0];
}
return seam;
}効果
デモのリンクはこちら。
アスペクト比を維持せずに縮小できるとは言ったものの、画像の内容によってはやはり不自然に見えてしまうこともある。特に画像の重要な情報が削除されていくにつれて、違和感は増していく。それでも、非常に興味深く面白いアルゴリズムだと僕は思う。
**「重要でない部分を取り除く」**という基本思想は、実はさまざまな場所で見られる。例えば音声サンプリングにおいて、人間の耳には聞こえない高周波成分をカットして容量を節約したり、複雑すぎる行列を SVD（特異値分解）によって重要な特徴ベクトルだけで表現したりする。一見関連性がないように思えるが、根底にある考え方は共通している。
あとがき
画像のピクセルを直接操作し、しかもこうしたループ処理で書いているため、画像のサイズが大きくなるとかなり顕著な遅延（ディレイ）が発生する。このような場合は、画像操作を WebGPU や WebGL を使って GPU に任せたり、計算処理を Web Worker に移管したりといった最適化を考慮する必要がある。
実際の運用においては、効果は優れているものの、やはり画像の内容に依存する。画像全体のディテールが重要で、どこにも明確な輝度変化があるような画像の場合は、Seam Carving を使ってもやはり大きな歪みが生じてしまうだろう。
関連リソース
本記事の多くの概念は Computational Thinking – Seam Carving という動画から学んだものだ。解説しているのは 3Blue1Brown の Grant Sanderson 氏！ 豊富なビジュアル解説があり、とても分かりやすい。
関連記事
- 測定が目標になるとき：窓税からPull Request数まで かつて僕は小さなツールを自作し、四半期で自分がどれだけPRに貢献したか、レビューコメントをどれだけ残したか、チケットをどれだけ消化したかを集計して、上司にアウトプットを証明しようとしたことがある。上司は淡々と、評価はアウトプットだけで見るものではないと言った。数年後、僕はようやく理解した――測定が目標になるとき、それはもはや良い測定ではなくなるのだ。英国の窓税、ハノイのネズミ駆除の報奨金から、現代のPR数による開発者評価に至るまで、そのメカニズムはまったく同じだ。
- Cloudflare Images を画像ストレージ・変換ソリューションとして使う ウェブページに画像を1枚置くのはフロントエンドにとって最も簡単なことだが、リサイズや各種フォーマットの生成、さらにはトラフィックの負荷に耐えることまで完璧にやろうとすると、実際には一つの包括的なソリューションが必要になる。僕はその後、すべて Cloudflare Images に任せるようになり、オリジナル画像1枚だけを渡すようにしている。
- もう AWS Access Key を使うのはやめよう Access Key は AWS において見落とされがちなセキュリティリスクだ。OIDC と IAM Role を組み合わせることで、GitHub Actions にシークレットを一切保持させることなく、安全に AWS リソースを操作できるようにする。
- データベース主キー：AUTO_INCREMENT、UUID、そしてUUIDv7 バックエンド開発で度々直面する主キーの決定。auto incrementを使うべきか、それともUUIDか？衝突への懸念は？UUIDv7とcreated_at + インデックスの性能差はどれほどか？実際に2,000万件のデータで検証したベンチマークと設計上の意思決定を解説する。