Introduction

Resize a photo the ordinary way and you face an ugly trade-off: scale and you squish faces; crop and you lose the edges of the scene. For decades those were the only two options.

In 2007 Shai Avidan and Ariel Shamir published a third way: seam carving. Instead of operating on columns or rectangles, the algorithm finds a seam — a connected path of one pixel per row, winding from the top of the image to the bottom — and removes it entirely. Pick the seam whose pixels are the least visually important, and the image shrinks by one column while the objects that matter stay intact.

Repeat the process — find the cheapest seam, remove it, find the next — and the image can be made arbitrarily narrower without any obvious distortion. The key insight is that the "cheapest seam" problem has optimal substructure: the cheapest path to any pixel on row rr extends the cheapest path to the best neighbor on row r−1r - 1. That is the hallmark of dynamic programming, and it turns what sounds like an exponential search into a single linear-time sweep.

Try It

The grid below is a tiny pixel image. Each cell's brightness represents its energy — how much it contrasts with its neighbors. The algorithm finds the vertical seam of lowest total energy and highlights it in red. Press Remove seam to delete it and shrink the image by one column; repeat until the subject fills the frame.

<!-- Seam Carving demo: find and remove the lowest-energy vertical seam -->
<p class="hint">Each cell's number is its <b>energy</b> — how much it contrasts with its neighbors. Low-energy cells (dark) are cheap to remove. The algorithm finds the vertical seam of <b>lowest total energy</b> using dynamic programming, then removes it.</p>
<div id="canvas-wrap">
  <canvas id="grid-canvas"></canvas>
</div>
<div class="status" id="status">Click "Show seam" to highlight the cheapest path.</div>
<div class="btns">
  <button id="btn-seam" type="button">Show seam</button>
  <button id="btn-remove" type="button">Remove seam</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span class="leg-swatch" style="background:#e63946"></span> current seam
  &nbsp;&nbsp;
  <span class="leg-swatch" style="background:#457b9d"></span> removed
</div>

/* base reset + layout styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas-wrap { display: inline-block; border: 1px solid #cdd9e3; border-radius: 6px; overflow: hidden; margin-bottom: .4rem; }
canvas { display: block; }
.status { font-size: 1rem; font-weight: 600; min-height: 1.4em; margin: .4rem 0; }
.status.done { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.legend { font-size: .82rem; color: #555; display: flex; align-items: center; gap: 2px; }
.leg-swatch { display: inline-block; width: 12px; height: 12px; border-radius: 2px; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Seam carving: repeatedly remove the vertical connected path (one pixel per row) */
/* of minimum total energy. Dynamic programming makes this O(W*H) per seam. */

const CELL = 28;
const ROWS = 10;
const COLS = 14;

/* Energy map: high values = high contrast = important to keep. Low border = cheap to remove. */
const BASE_ENERGY = [
  [1,1,1,8,8,8,8,8,8,8,1,1,1,1],
  [1,2,1,8,9,9,9,9,9,8,1,2,1,1],
  [1,1,1,8,9,9,9,9,9,8,1,1,1,1],
  [1,1,8,8,9,9,9,9,9,8,8,1,1,1],
  [1,1,8,9,9,9,9,9,9,9,8,1,1,1],
  [1,1,8,9,9,9,9,9,9,9,8,1,1,1],
  [1,1,8,8,9,9,9,9,9,8,8,1,1,1],
  [1,1,1,8,9,9,9,9,9,8,1,1,1,1],
  [1,1,1,8,8,8,8,8,8,8,1,1,1,1],
  [1,1,1,1,1,1,1,1,1,1,1,1,1,1]
];

let energy = BASE_ENERGY.map(r => r.slice());
let currentCols = COLS;
let removedCount = 0;
let currentSeam = null; // currently highlighted seam (array of column indices, one per row)

const canvas = document.getElementById('grid-canvas');
const ctx = canvas.getContext('2d');

function setCanvasSize() {
  canvas.width  = currentCols * CELL;
  canvas.height = ROWS * CELL;
}

/* Map energy 0-9 to a blue-to-bright color so contrast is visible. */
function energyColor(e) {
  const t = Math.min(e / 9, 1);
  const r = Math.round(30  + (232 - 30)  * t);
  const g = Math.round(60  + (240 - 60)  * t);
  const b = Math.round(110 + (240 - 110) * t);
  return `rgb(${r},${g},${b})`;
}

function draw(seam) {
  setCanvasSize();
  const seamSet = new Set(seam ? seam.map((c, r) => r + ',' + c) : []);
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < currentCols; c++) {
      const key = r + ',' + c;
      if (seamSet.has(key)) {
        ctx.fillStyle = '#e63946'; // highlight the seam in red
      } else {
        ctx.fillStyle = energyColor(energy[r][c]);
      }
      ctx.fillRect(c * CELL, r * CELL, CELL - 1, CELL - 1);
      /* draw energy number in each cell */
      ctx.fillStyle = energy[r][c] > 5 ? '#fff' : '#333';
      ctx.font = '11px ui-monospace, monospace';
      ctx.textAlign = 'center';
      ctx.textBaseline = 'middle';
      ctx.fillText(energy[r][c], c * CELL + CELL / 2, r * CELL + CELL / 2);
    }
  }
}

/* Dynamic programming: build cost table M[r][c] = e[r][c] + min of three neighbors above. */
function findSeam() {
  const dp = [];
  const from = [];
  // initialize top row — cost equals energy
  for (let c = 0; c < currentCols; c++) {
    dp[0] = dp[0] || [];
    dp[0][c] = energy[0][c];
    from[0] = from[0] || [];
    from[0][c] = -1;
  }
  // fill remaining rows with recurrence
  for (let r = 1; r < ROWS; r++) {
    dp[r] = [];
    from[r] = [];
    for (let c = 0; c < currentCols; c++) {
      let best = dp[r - 1][c], bestC = c;
      if (c > 0 && dp[r - 1][c - 1] < best) { best = dp[r - 1][c - 1]; bestC = c - 1; }
      if (c < currentCols - 1 && dp[r - 1][c + 1] < best) { best = dp[r - 1][c + 1]; bestC = c + 1; }
      dp[r][c] = energy[r][c] + best;
      from[r][c] = bestC;
    }
  }
  // traceback from minimum in last row
  let minC = 0;
  for (let c = 1; c < currentCols; c++) if (dp[ROWS - 1][c] < dp[ROWS - 1][minC]) minC = c;
  const seam = [minC];
  for (let r = ROWS - 1; r > 0; r--) { minC = from[r][minC]; seam.unshift(minC); }
  return seam;
}

/* Remove the seam: splice out one pixel per row, shrink the grid. */
function removeSeam(seam) {
  for (let r = 0; r < ROWS; r++) {
    const c = seam[r];
    energy[r].splice(c, 1);
  }
  currentCols--;
  removedCount++;
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + (cls || '');
}

function updateButtons() {
  document.getElementById('btn-seam').disabled   = currentCols <= 4;
  document.getElementById('btn-remove').disabled = !currentSeam || currentCols <= 4;
}

document.getElementById('btn-seam').addEventListener('click', () => {
  if (currentCols <= 4) return;
  currentSeam = findSeam();
  draw(currentSeam);
  setStatus('Seam found — red cells form the lowest-energy path. Click "Remove seam" to delete it.', 'info');
  updateButtons();
});

document.getElementById('btn-remove').addEventListener('click', () => {
  if (!currentSeam) return;
  removeSeam(currentSeam);
  currentSeam = null;
  draw(null);
  if (currentCols <= 4) {
    setStatus(i18nFmt('Done — %n% seams removed. The image is narrower but the high-energy region is preserved.', { n: removedCount }), 'done');
  } else {
    setStatus(i18nFmt('Seam %n% removed. Click Show seam again.', { n: removedCount }), 'info');
  }
  updateButtons();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  energy = BASE_ENERGY.map(r => r.slice());
  currentCols = COLS;
  removedCount = 0;
  currentSeam = null;
  draw(null);
  setStatus('Click "Show seam" to highlight the cheapest path.', '');
  updateButtons();
});

draw(null);
updateButtons();
Result
Console

Notice that the red seam winds around the bright cells rather than cutting straight down. That is dynamic programming at work: instead of checking every possible top-to-bottom path (exponentially many), it fills a cost table in O(W⋅H)O(W \cdot H) time and reads the best path back from the bottom row in O(H)O(H) additional steps.

The Real Complexity

Seam carving is a solved, polynomial-time algorithm — a satisfying rarity in a field full of hard problems.

  • Brute force would enumerate every connected top-to-bottom path. In an image of width WW each row offers up to three choices (left-diagonal, straight, right-diagonal), giving 3H3^{H} paths — hopeless for any real image.
  • Dynamic programming tames this by exploiting optimal substructure. Let M[r][c]M[r][c] be the cost of the cheapest seam ending at pixel (r,c)(r, c). Then:

M[r][c]=e[r][c]+min⁡(M[r−1][c−1],  M[r−1][c],  M[r−1][c+1])M[r][c] = e[r][c] + \min(M[r-1][c-1],\; M[r-1][c],\; M[r-1][c+1])

where e[r][c]e[r][c] is the energy of that pixel. Fill the table top-to-bottom in O(W⋅H)O(W \cdot H), find the minimum in the last row, and trace back up in O(H)O(H). Total: O(W⋅H)O(W \cdot H) per seam.

  • Removing kk seams costs O(k⋅W⋅H)O(k \cdot W \cdot H) — fully polynomial and fast enough to run live on video.
  • The energy function ee is typically the gradient magnitude: e[r][c]=∣∂I/∂x∣+∣∂I/∂y∣e[r][c] = |\partial I / \partial x| + |\partial I / \partial y|, computed with a Sobel filter in one pass. Higher gradient = more detail = more important to keep.

The algorithm was published in 2007 and has been standard in photo editors ever since. Adobe Photoshop calls it Content-Aware Scale; it appears in GIMP, ffmpeg, and most modern retargeting pipelines.

Where It Matters

The idea of removing low-energy paths rather than columns shows up everywhere images need to fit a different frame:

  • Photo editors: Adobe Photoshop's Content-Aware Scale and GIMP's Liquid Rescale plugin both implement seam carving.
  • Responsive web images: servers can pre-compute seam-carved variants so a portrait looks natural on both a widescreen monitor and a narrow phone.
  • Video retargeting: removing temporal seams (paths that are consistent across frames) resizes video without jitter or subject distortion.
  • Thumbnail generation: streaming platforms use energy-based cropping to keep the most salient region of a poster in the thumbnail.
  • Object removal: running the algorithm in reverse — inserting instead of deleting seams — can fill in or replicate background content after an unwanted object is masked out.

The underlying dynamic-programming pattern — fill a cost table, trace back the optimal path — is the same engine that drives shortest paths in graphs and sequence alignment in bioinformatics. Seam carving is one of the cleanest demonstrations that a clever table lookup can replace an exponential search.

Conclusion

Seam carving is a beautiful case study in algorithm design: a problem that naively requires an exponential search turns out to have optimal substructure, and that single observation collapses the search to a linear-time table fill.

The result is an algorithm fast enough to run on video, elegant enough to explain in a single recurrence, and impactful enough to ship in every major photo editor within a few years of its 2007 publication. The next time you drag the corner of a photo and the subjects don't distort, you are watching dynamic programming at work — one least-cost seam at a time.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/seam-carving/Content licensed under CC BY-NC 4.0.