質問やフィードバックがありましたら、フォームからお願いします
本文は台湾華語で、ChatGPT で翻訳している記事なので、不確かな部分や間違いがあるかもしれません。ご了承ください
Seam Carvingは、私がComputational Thinkingで学んだアルゴリズムで、画像の内容に基づいてサイズを変更することができます。一般的に、画像をウェブページにレンダリングする際、コンテナの高さや幅に合わない場合、以下のような方法を採用します：
- 画像を等比例で縮小する
- 画像の一部をトリミングする
Seam Carvingこのアルゴリズムは、画像の比率を変更しながらトリミングを行うことができ、その原理は、毎回の縮小時に画像の中で最も重要でない部分を見つけて削除し、画像を「縫合」することです。今日は、このアルゴリズムについてお話ししましょう！
この画像を見てみましょう。
もし私たちが比率を次のように変更すると、
画像の内容が全体的に歪んでしまい、非常に見栄えが悪くなります。
Seam Carvingこのアルゴリズムは、大体画像の内容を保持しながら、比率を無視して縮小することができます。実際にはどのように実現しているのでしょうか？今日はこのアルゴリズムを紹介します。
Seam Carving
Seam Carvingの核心原理は、画像の中で最も重要でない部分を削除し、残りの部分を「縫合」することです。それでは、どうやって画像の中で「重要でない」部分を見つけるのでしょうか？また、重要でないというのはどう定義されるのでしょうか？
エッジ検出
まず、この画像を見てみましょう。
次に、この画像を見てみましょう。
この画像で最も重要な部分は、白黒の境界点です。この境界を維持できれば、比率を少し変更しても大きな違和感はありません。肉眼で見れば理解できますが、コンピュータビジョンではこれらの点をどうやって見つけるのでしょうか？
Sobelエッジ検出
Sobelは、2つの3x3の行列を含みます：
画像を行列と見なすと、画像のピクセルと行列を掛け算し、勾配値を求めることは、画像に対して畳み込み（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を通過した画像をキャンバスに載せます。これは元の画像です。
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を通過した後の行列データをエネルギーと呼びます。私たちはこのエネルギーを事前処理することができます。
まず最下部から始めます。毎回最小値を選ぶので、現在の最小値が全体の最小値であることが確実です。これで動的計画法を使って書くことができます。まず、元のエネルギーの最下部をコピーし、下から上に隣接要素の最小値を計算し、自身の値を加えます：
これで1.0から探し始め、順に0.2、0.1に進むことができ、事前処理を経て、この道筋が総エネルギーが最も少ないことが保証されます。
次に、対応する座標を記録します。上記の例で得られるのは：
[[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特異値変換を通じて重要な特徴ベクトルで表現したりします。一見非関連に見えるかもしれませんが、概念は共通しています。
後記
画像の各ピクセルに対して直接操作を行い、さらにこのようなループの方法で書くと、画像のサイズが大きい場合は非常に顕著な遅延が発生します。この時、画像の操作をGPUに処理させることを検討でき、これにはWebGPUやWebGLを使用するか、計算をWorkerに移すことができます。
実際の使用では、効果は良好ですが、画像の内容によって異なります。画像の詳細が非常に重要で、明確な明るさの変化がある場合、Seam Carvingを使用しても依然として多くの歪みが生じる可能性があります。
関連リソース
本記事の多くの概念は、Computational Thinking – Seam Carvingという動画から得たもので、解説は3Brown1Blueの著者Grant Sandersonによるものです！視覚的に多くの解説があり、非常に理解しやすいです。
この記事が役に立ったと思ったら、下のリンクからコーヒーを奢ってくれると嬉しいです ☕ 私の普通の一日が輝かしいものになります ✨
☕Buy me a coffee