Seam Carving - Find Minimum Energy Path

1. Background Knowledge

Seam carving is a content-aware image resizing technique that removes or adds low-energy seams (connected paths of pixels) to preserve visually important content like edges and textures. Energy typically measures pixel importance via gradients (e.g., Sobel filters), but here it's given directly as a 2D matrix $E$ where $E[i][j]$ is the energy cost of pixel at row $i$, column $j$.

Key prerequisites:

• Dynamic Programming (DP): Solves optimization by breaking into overlapping subproblems with memoization.
• Graph shortest path analogy: View the image as a directed graph where nodes are pixels, edges connect valid moves (down, down-left, down-right), and edge weights are energies. Finding the minimum-energy seam is equivalent to a shortest path from any top-row node to any bottom-row node.
• Valid moves: From $(r, c)$, go to $(r+1, c-1)$, $(r+1, c)$, or $(r+1, c+1)$ (stay within bounds).

This is a classic DP-on-grid problem, not requiring search results' advanced chemistry/physics contexts (e.g., potential energy surfaces).

2. Algorithm Approach

Use dynamic programming for exact minimum energy seam in $O(rows \times cols)$ time, superior to brute-force ($O(3^{rows})$) or greedy (suboptimal).

• Forward DP (bottom-up): Compute min cost to reach each cell from top.
• Backward reconstruction (optional): Trace predecessors to recover path.
• Alternatives like Dijkstra work but are slower ($O(rows \times cols \log(cols))$); DP is optimal for DAG structure.

3. Step-by-Step Strategy

Let $dp[r][c]$ = minimum energy to reach row $r$, column $c$ from top row (row 0).

Step 1: Initialize top row

dp[c] = energy[c] for c in 0 to cols-1

Step 2: Fill DP table row-by-row For $r = 1$ to $rows-1$:

• For each $c = 0$ to $cols-1$:

dp[r][c] = energy[r][c] + min(
dp[r-1][c-1] if c-1 >= 0 else ∞,
dp[r-1][c],
dp[r-1][c+1] if c+1 < cols else ∞
)

Step 3: Find minimum seam energy

min_energy = min(dp[rows-1][c] for all c)

Return min_energy.

Example trace for given matrix:

Row 0: dp = [1, 4, 3]

Row 1:
dp = 5 + min(1) = 6
dp = 2 + min(1,4,3) = 3
dp = 6 + min(4,3) = 9

Row 2:
dp = 9 + min(6) = 15
dp = 8 + min(6,3,9) = 11
dp = 7 + min(3,9) = 10

min_energy = min(15,11,10) = 10

Code skeleton (Python):

def min_seam_energy(energy):
 if not energy or not energy: return 0
 rows, cols = len(energy), len(energy)
 dp = [row[:] for row in energy] # Copy energy as base

 for r in range(1, rows):
 for c in range(cols):
 candidates = []
 if c-1 >= 0: candidates.append(dp[r-1][c-1])
 candidates.append(dp[r-1][c])
 if c+1 < cols: candidates.append(dp[r-1][c+1])
 dp[r][c] += min(candidates)

 return min(dp[-1])

4. Common Pitfalls

• Boundary handling: Always check $c-1 \geq 0$ and $c+1 < cols$ to avoid index errors.
• Initialization: Top row must copy energy, not zeros.
• Off-by-one: Seam must visit exactly one pixel per row; no skipping rows.
• Modifying input: Use separate dp table if input is read-only.
• Large energies: Use float('inf') for invalid moves; constraints ensure no overflow ($100 \times 100 \times 1000 = 10^7$).
• Misinterpreting "vertical": Must go top-to-bottom monotonically in rows.

5. Time & Space Complexity

• Time: $O(rows \times cols)$, as each of $rows$ processes $cols$ cells with constant-time min of 3 values.
• Space: $O(rows \times cols)$ for full DP table. Optimize to $O(cols)$ using two arrays (prev/current row) since rows are processed sequentially.
• Space-optimized code swaps two 1D arrays.

This DP approach scales perfectly to constraints ($100 \times 100 = 10k$ operations). For full seam carving, repeat $k$ times to remove $k$ seams, updating energies after each.