Seam Carving

Shrink images by deleting the quietest connected pixel paths first, so featureless regions absorb the missing width and subjects keep their shape.

Dynamic programming finds the cheapest top to bottom seam: the middle column costs 1 plus 2 plus 1 equals 4, beating every diagonal

Why Does This Exist?

Screens demand new aspect ratios daily, and the standard answers both harm composition: cropping amputates subjects while uniform scaling squeezes faces. Avidan and Shamir (2007) offered a third way that removes pixels nobody looks at, sky, sand, blur, one connected path at a time, so a wide beach photo narrows without touching the surfer. Content-aware retargeting preserves what matters by deleting what does not.

Gradient energy is the prerequisite, from spatial filtering: busy pixels score high, flat pixels score low. Seam removal serves augmentation pipelines as a distortion-free resize. This page covers energy maps, optimal seams, and removal versus insertion.

Think of It Like This

Emptying the quietest checkout lanes

A supermarket must close three checkout lanes and picks the emptiest ones, where each lane runs unbroken from entrance to exit and neighbours shift to fill gaps. Shoppers in busy lanes never move; the store narrows by removing quiet capacity. Energy is shopper density, seams are lanes, and subjects are the crowds nobody disturbs.

It stops holding in a packed store. When every lane bustles, any closure disrupts shoppers, the same way seam carving warps portraits and architecture with no flat regions to sacrifice. Uniform importance defeats selective removal.

How It Actually Works

Energy maps importance

Each pixel gets an energy, usually gradient magnitude $|dI/dx| + |dI/dy|$ : textured subject pixels score high, flat sky scores near zero. The map is the entire value judgment, so better energy functions (saliency detectors, face detectors added to the map) directly improve results. Garbage energy in, warped subjects out.

The optimal eight-connected seam

A vertical seam is one pixel per row, each step shifting at most one column, minimizing total energy via dynamic programming: accumulate from the top with $M(i,j) = e(i,j) + \min(M(i-1,j-1), M(i-1,j), M(i-1,j+1))$ , then backtrack from the cheapest bottom cell. Trace the $3 \times 3$ energy map

\begin{bmatrix} 5 & 1 & 4 \\ 6 & 2 & 3 \\ 7 & 1 & 5 \end{bmatrix}

Row accumulations give $[5, 1, 4]$ , then $[7, 3, 4]$ , then $[10, 4, 8]$ . The minimum $4$ backtracks straight down column $1$ , the seam $(0,1), (1,1), (2,1)$ costing $1 + 2 + 1 = 4$ , beating the $5$ -cost diagonal alternative. Deleting it narrows the image by one pixel along its least important path.

Removal, insertion, and protection

Repeat removal for width; transpose for height. Enlargement duplicates the lowest-energy seams (insertion) instead. Forward energy improves on the basic cost by charging seams for the new edges their removal creates, which calms staircase artifacts. User masks protect faces (infinite energy) or condemn logos (negative energy), steering the DP around what matters.

Code

Dynamic-programming seam on the fixture energy map:

1e = [[5, 1, 4], [6, 2, 3], [7, 1, 5]]2rows, cols = 3, 33M = [row[:] for row in e]4for i in range(1, rows):5    for j in range(cols):6        M[i][j] += min(M[i - 1][k] for k in (j - 1, j, j + 1) if 0 <= k < cols)7
8j = min(range(cols), key=lambda k: M[rows - 1][k])9seam, cost = [], M[rows - 1][j]10for i in range(rows - 1, -1, -1):11    seam.append((i, j))12    j = min((k for k in (j - 1, j, j + 1) if 0 <= k < cols), key=lambda k: M[i - 1][k]) if i else j13print(f"seam {sorted(seam)}, cost {cost}")14# -> seam [(0, 1), (1, 1), (2, 1)], cost 4

Straight down the middle column at total cost $4$ , matching the hand backtrack.

Watch Out For

Warping faces and architecture

Symptom: portraits narrow with pinched cheeks and buildings lean, because no low-energy seam existed and the DP cut through the subject anyway. The algorithm always removes something. Protect important regions with high-energy masks, switch to cropping or scaling for detail-dense images, and preview at the target size before committing.

Staircase artifacts from backward energy

Symptom: diagonal edges come out stepped after many removals, as each seam exposes new high-contrast neighbours the basic cost never charged for. Use forward energy, which prices the edges a removal creates, and remove height and width seams in cost order rather than all of one direction first.

The Quick Version

Energy (usually gradient magnitude) scores pixel importance; seams minimize total energy via dynamic programming.
One seam per row or column, eight-connected, deleted or duplicated to retarget by exactly one pixel.
On the fixture map the optimal seam runs straight down column $1$ at cost $4$ .
Forward energy prices newly created edges and calms staircase artifacts on diagonals.
Protection masks steer seams around faces; detail-dense images with no cheap seams should be cropped, not carved.