Seam Carving

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 $r$ extends the cheapest path to the best neighbor on row $r - 1$. That is the hallmark of dynamic programming, and it turns what sounds like an exponential search into a single linear-time sweep.

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.

<!-- {{c_demo_title}} -->
<p class="hint">{{hint_para}}</p>
<div id="canvas-wrap">
  <canvas id="grid-canvas"></canvas>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-seam" type="button">{{btn_show}}</button>
  <button id="btn-remove" type="button">{{btn_remove}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend">
  <span class="leg-swatch" style="background:#e63946"></span> {{leg_seam}}
  &nbsp;&nbsp;
  <span class="leg-swatch" style="background:#457b9d"></span> {{leg_removed}}
</div>

/* {{c_base_reset}} */
* { 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; }

// Code not found

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 \cdot H)$ time and reads the best path back from the bottom row in $O(H)$ additional steps.

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 $W$ each row offers up to three choices (left-diagonal, straight, right-diagonal), giving $3^{H}$ paths — hopeless for any real image.
• Dynamic programming tames this by exploiting optimal substructure. Let $M[r][c]$ be the cost of the cheapest seam ending at pixel $(r, c)$. Then:

$$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]$ is the energy of that pixel. Fill the table top-to-bottom in $O(W \cdot H)$, find the minimum in the last row, and trace back up in $O(H)$. Total: $O(W \cdot H)$ per seam.

• Removing $k$ seams costs $O(k \cdot W \cdot H)$ — fully polynomial and fast enough to run live on video.
• The energy function $e$ is typically the gradient magnitude: $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.

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.

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.