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 $A$, multiplying each pixel’s 3x3 neighborhood by $K_x$ and $K_y$ and summing the results is a convolution, which gives the horizontal and vertical gradients $G_x$ and $G_y$. By computing discrete differences, Sobel estimates the gradient of image brightness:

Matrix notation alone can feel abstract, so let’s look at code. The previous version of this post used nested JavaScript loops that visited one pixel at a time. Every pixel is computed independently, though, which makes this a perfect fit for the GPU. Here it is as a WebGPU compute shader (WGSL), with one thread per pixel:

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 converts RGB to grayscale brightness. Each thread multiplies its 3x3 neighborhood by both kernels and takes the gradient magnitude. Pixels on the border use clamp to borrow their nearest neighbor.

stride is the original image width. Every removed seam makes the image one pixel narrower, but the buffer keeps its size, so indices use the fixed stride while bounds checks use the current width.

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 from 0.7, the smallest value in the top row, and always stepping to the smallest neighbor below yields 0.7 + 0.05 + 1.5 = 2.25. Taking 0.1 on the second step instead yields 0.7 + 0.1 + 0.1 = 0.9. Picking the smallest value at each step does not give the smallest path. We call the matrix produced by Sobel filtering “energy”, and we can precompute it to find the optimal path.

Copy the bottom row of the energy map first. Then, working from bottom to top, add to each cell the minimum of its three neighbors below. Each cell now holds the lowest total energy of any path from that cell to the bottom, which is dynamic programming:

With this cumulative energy map, we start from the minimum on the top row (0.9) and follow the path down through 0.2 and 0.1. The preprocessing guarantees that this seam has the lowest total energy.

Next, we record the [x, y] coordinates along this path. For the example above:

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

Dynamic Programming on the GPU

Every Sobel pixel is independent, but the dynamic programming step is not: each row has to wait for the row below it. So this pass runs as a single workgroup. Its 256 threads split the cells of one row, and storageBarrier() waits for all of them to finish writing before moving up to the next row.

Tracing the minimum path back down is sequential, since each step depends on the previous one, so a single thread does it:

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

Finally, shift every pixel right of the seam one step to the left. This runs per pixel in parallel again. The result goes to a second buffer and is copied back afterwards, so no thread reads a value another thread has already overwritten:

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

On the JavaScript side, we dispatch the three passes in order. Each removed seam reduces the width by 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()])

To draw the result, a render pass reads the same storage buffer and draws it to the canvas. The pixels stay on the GPU the whole time and never need to be read back to the CPU.

Demo & Results

Drag the slider to narrow the image. The red line is the next seam to be removed. Switch to Energy to see the Sobel output, or try your own image (it is processed in your browser and never uploaded).

If your browser does not support WebGPU, here is a video of the demo:

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

The old implementation walked every pixel in JavaScript loops and lagged noticeably on larger images. With WebGPU, both Sobel and seam removal run in parallel per pixel, fast enough to follow the slider in real time.

The dynamic programming step remains the bottleneck: each row depends on the row below, so it runs row by row in a single workgroup and cannot use the whole GPU. Another possible optimization is that removing a seam only changes the energy near that seam, so the whole map does not need to be recomputed every time.

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.