Seam Carving – Resizing Images Non-Proportionally

Seam Carving is an algorithm I learned about in MIT’s Computational Thinking course that enables content-aware image resizing. When rendering an image on a webpage where the image dimensions don’t match the container’s width and height, we typically choose between:

1. Scaling the image proportionally (preserving the aspect ratio)
2. Cropping out part of the image’s content

The Seam Carving algorithm can resize and alter the aspect ratio while performing intelligent cropping. Its core principle is to iteratively identify and remove the least important path of pixels across the image, then stitch the remaining pieces back together. Today, let’s dive into how this algorithm works!

Take a look at this image:

If we force it into a different aspect ratio like this:

You can see that the contents are visibly distorted and quite unappealing.

Seam Carving can resize images non-proportionally while largely preserving the key subject matter. How does it actually achieve this? Let’s break down the algorithm.

Seam Carving

The core mechanism of Seam Carving is finding the least important path in the image, removing it, and “stitching” the remaining parts together. The key question is: how do we identify the “unimportant” parts of an image, and how is “importance” defined in the first place?

Edge Detection

Let’s look at this image first:

And now this one:

The most important part of this image is the boundary between black and white. As long as this boundary is preserved, changing the aspect ratio slightly won’t feel jarring. While this is intuitive to the human eye, how do we locate these points in computer vision?

Sobel Edge Detection

The Sobel operator consists of two 3x3 convolution kernels:

If we treat the image as a matrix, convolving the image pixels with these kernels calculates the gradient magnitude. By computing discrete differences, Sobel estimates the gradient of image brightness.

Looking at matrix equations alone might feel abstract, but seeing it in code makes it much clearer:

// Code referenced from 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;
}

From the implementation, what the Sobel edge filter actually does is convert the image to grayscale first, and then compute the gradient magnitude between each pixel and its neighbors.

Next, let’s render the Sobel-filtered image to a canvas. Here is the original photo:

After applying Sobel edge detection:

In the processed image, areas with high contrast or sharp transitions in brightness appear closer to white (closer to 255). Conversely, smooth areas with subtle brightness variations appear black (closer to 0).

Calculating the Least Important Path

Because edges represent more important features (whiter pixels = higher importance), we can traverse from top to bottom, find a connected path of adjacent pixels with the lowest total values, and remove it from the image.

However, if we simply trace from top to bottom greedily, we may miss the global minimum. For example:

Starting greedily from 0.7 yields 0.7 + 0.05 + 1.5 = 2.25. But starting from 0.8 yields 0.8 + 0.1 + 0.1 = 1.0. We refer to the matrix values generated by Sobel filtering as “energy.” We can precompute this energy map to find the optimal path.

Starting from the very bottom row, because every step chooses among local minimums, we can use dynamic programming to guarantee that our choice leads to the global minimum. First, copy the bottom row of the original energy map. Then, working from bottom to top, add each pixel’s own energy to the minimum of its three adjacent downward neighbors:

With this precomputed cumulative energy map, we can directly find the minimum on the top row (1.0) and follow the optimal path down through 0.2 and 0.1. The preprocessing guarantees that this seam has the lowest cumulative energy.

Next, we record the coordinates along this path. For the example above, the seam coordinates would be:

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

Finally, remove the corresponding pixels from the image. Here is the JavaScript implementation:

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;
}

Demo & Results

You can check out the live demo here.

Although we can resize images non-proportionally, the visual result still depends heavily on the image’s content. As more seams are carved and critical information eventually gets cut, artifacts and strange distortions will emerge. Even so, it remains a fascinating algorithm.

The core philosophy—removing unimportant parts—appears across numerous disciplines: in audio sampling, discarding high frequencies imperceptible to human ears saves storage space; in linear algebra, Singular Value Decomposition (SVD) represents complex matrices using only their most significant singular vectors. While these domains seem unrelated on the surface, the underlying concept is identical.

Afterthoughts

Operating directly on every pixel via nested JavaScript loops incurs significant delay when processing larger images. In such cases, several optimizations can be considered, such as offloading pixel computations to the GPU using WebGPU or WebGL, or moving calculations to a Web Worker.

In practice, although the technique is impressive, results heavily depend on the content. If an image is packed with high-frequency details where nearly every region contains prominent brightness changes, Seam Carving will still cause noticeable distortion.

Resources

Many concepts in this article were inspired by the video Computational Thinking – Seam Carving, presented by Grant Sanderson, creator of 3Blue1Brown! It features excellent visual explanations and is very easy to follow.