Resize by choosing a path
Uniformly shrinking an image compresses all of its content, including features one might prefer to preserve. A content-aware alternative removes a connected path of pixels, called a seam, while attempting to avoid visually important regions. The method depends on an energy assigned to each pixel: a low total energy is a mathematical objective, not a guarantee that the removed content is unimportant to a viewer.
Definition 10.1.1
(Vertical seam and its energy)
Let an image have rows and columns. For the present calculation, fix a finite real number at every pixel, where and . A vertical seam chooses one column per row, with for consecutive rows. Its energy is . After selecting a seam, delete its chosen pixel separately from every row and close each row's gap; the resulting rectangular image has rows and columns.
An energy might use local image differences, a user-provided protection mask, or both. Different choices can yield different seams. This lesson assumes the entire energy table is already fixed; it does not assume that pixel energy perfectly captures object meaning, or that it remains valid after resizing.
Dynamic programming and proof
Definition 10.1.2
(Accumulated seam cost)
A seam prefix ending at pixel is a choice of columns with . Let be the minimum of over all such prefixes. A prefix to row one consists of just one pixel, hence .
Theorem 10.1.3
(Seam recurrence)
For ,
The minimum energy of a vertical seam is , and a seam attaining it is obtained by backtracking from a minimizing bottom column through minimizing predecessors.
Proof
(Induction over rows)
Let . At an image edge this set contains only columns that exist; no outside pixel is silently treated as having zero cost.
A valid prefix ending at has its previous pixel at for some , and removing its last pixel leaves a valid prefix ending at . Conversely, every valid prefix ending at with extends to .
Upper bound: appending to a minimum-cost prefix ending at a minimizing gives a prefix of cost , so is at most this value. Lower bound: for any prefix ending at , removing the last pixel leaves a prefix at some of cost at least , so its cost is at least . Hence equality holds. A full seam is a prefix of length , so the minimum seam energy is . Choosing at each step a minimizing predecessor, starting from a minimizing bottom column, therefore produces a seam whose energy is exactly .
Negative energies would not invalidate this proof, because every full seam has exactly pixels and the directed row-by-row graph has no cycles.
Proof X-ray
Why the last pixel is all the recurrence needs
The proof uses three facts. The cost of a prefix is a sum, so removing the last pixel subtracts exactly and nothing else; this produces both bounds. The adjacency rule links only consecutive rows, so the ways of extending a prefix depend on its last pixel and not on how it was reached; this is the optimal-substructure step, since the best way to reach contains a best way to reach its predecessor. Finally, the energies are fixed numbers that do not depend on the seam chosen. The argument would fail for an objective whose cost depends on more of the prefix than its last pixel, or for energies that change with the seam. Negative values are harmless because every candidate has exactly terms.
To read off a seam, store one minimizing predecessor for each entry; from a minimizing column in the bottom row follow those pointers upward, then reverse the columns. If several candidates tie, any chosen minimizer is optimal for the stated objective, but a deterministic implementation needs an explicit tie rule. One row is a valid special case: choose a minimum-energy pixel in that row, with no predecessor steps.
Concept lensAlgorithmic
A seam as a shortest path in a layered graph
Make one node for each pixel, with an edge from to whenever , and let each node carry the weight . Adding a source joined to row one and a sink joined from row , valid seams are exactly the source-to-sink paths, and the seam energy is the total weight along the path. The graph has no cycles, so shortest paths can be computed by processing the rows in order, even when some weights are negative, and is the shortest-path distance to node .
A tempting shortcut is to ignore the graph and pick the cheapest pixel in each row independently. The adjacency condition is what forbids it.
Counterexample mode
Choosing the cheapest pixel in each row is not a seam
Take , with energies in row 1 and in row 2. The cheapest pixels are in columns and , with total , but , so this is not a seam. The valid seams are with energies , so the minimum is . Even the repaired rule that starts at the cheapest top pixel and steps to the cheaper neighbor can fail: with row 1 equal to and row 2 equal to , it takes column 1 and then a neighbor of cost , for energy , while is achieved by starting in column 2 or 3. Local choices cannot replace the recurrence.
Worked table
Worked example 10.1.4
(Accumulated costs on a four-row table)
For the fixed energy table below, the accumulated costs are computed row by row:
| Row | Pixel energies by column 1–4 | Accumulated costs by column 1–4 |
|---|---|---|
| 1 | 4, 2, 4, 7 | 4, 2, 4, 7 |
| 2 | 6, 1, 5, 4 | 8, 3, 7, 8 |
| 3 | 2, 4, 1, 6 | 5, 7, 4, 13 |
| 4 | 4, 3, 2, 3 | 9, 7, 6, 7 |
For example, row 3 column 1 uses only row 2 columns 1 and 2, so its cost is . The minimum bottom-row cost is at column 3. Backtracking gives columns from top to bottom, whose energy is . The table certifies optimality among all valid vertical seams for these fixed energies; in general, independently choosing a smallest-energy pixel in each row need not enforce adjacency.
Worked example 10.1.5
(A tie between two optimal seams)
Take , with energies in row 1 and in row 2. The first row costs are . In row 2, column 1 has only columns 1 and 2 as predecessors, so ; ; and . The minimum occurs at columns 1 and 3, giving two optimal seams, columns and , each of energy . Both are optimal for the objective, so a program must choose by a stated rule, such as the smallest column. Neither edge column consults a column or .
Worked example 10.1.6
(Removing a seam and repeating)
Remove the seam from the four-row table above. Keeping the remaining energies unchanged, the new rows are , , and , a table with columns. Repeating the algorithm on this fixed table gives accumulated costs , , and , so the next seam has energy . In practice the energies of the new image are recomputed, because pixels that the seam separated are now neighbors; the table above is only the fixed-energy version of that step.
Efficiency and what the objective omits
Proposition 10.1.7
(Time and space of the seam algorithm)
Computing all costs takes time. If only the minimum value is needed, two cost rows require storage; retaining one predecessor per cell adds storage for the direct reconstruction. Outputting the seam itself needs space.
Proof
(Counting cells and rows kept)
There are cells and each checks at most three predecessors, which gives time. Row uses only row , so only two rows of costs need to be kept when no predecessor is stored. One stored predecessor per cell is values, and the final seam has one column per row.
Boundary and tie choices must be recorded consistently.
Common mistake
(Treating a missing neighbor as free)
Take energies in row 1 and in row 2. The pixel has predecessors only in columns 1 and 2, so . If a nonexistent column were given cost , the formula would give , a value smaller than the energy of every seam through , since each of them passes through row 1 at energy at least . Only existing columns may enter the minimum.
To remove several seams, one can remove one, update the image and its energy table, and repeat. For an initial width , at most seams can be removed under the condition: after removals the width is . Each iteration solves the current fixed-table problem; this alone does not prove that the resulting sequence is globally optimal for a separately defined multi-removal objective. Recomputing local energies can also change the objective after each removal. A backward-looking pixel-energy sum does not explicitly charge for the new neighbor discontinuities created by removing a seam. A more elaborate objective can include such costs, but its recurrence and assumptions must be derived separately.
Low gradient or low assigned energy can still cross a face, text, or a meaningful straight edge. Masks, perceptual criteria and human inspection can reduce some failures, but none is a proof of semantic preservation. Horizontal seams can be handled by exchanging the roles of rows and columns; that is a different path orientation, not the same vertical seam applied unchanged.
Exercises
Quick check
(If and the energy row is , give a minimum seam and its energy. How does the recurrence avoid requesting a nonexistent predecessor?)
Which values of use the recurrence?
Solution · Answer
The minimum seam is column with energy . With one row only is used, and the recurrence applies only for , so no predecessor is requested. For the minimum ranges only over columns that exist.
Quick check
(Give a two-row energy table with at least three columns where independently choosing the cheapest pixel of each row violates the adjacency condition.)
Put the two cheapest pixels in columns at distance two.
Solution · Answer
Take row 1 equal to and row 2 equal to . The cheapest pixels are in columns and , with total , which is not a seam. The recurrence gives , and , so every valid seam has energy at least .
Quick check
(Why does recomputing energies and repeating the one-seam algorithm not by itself prove global optimality for a multi-seam objective?)
Compare what each iteration optimizes with what a multi-seam objective sums over.
Solution · Answer
Each iteration is optimal only for the current fixed table. Removing a seam changes the image, so the energies and the neighbor relations of the next table differ from the original ones, and the sum of the successive one-seam optima is not shown to be the optimum of any objective defined on the whole sequence. A global claim needs its own objective and its own proof.
Quick check
(Compute the accumulated costs and a minimum vertical seam for the energy table with rows , and .)
Fill row 1, then each later cell using only existing columns of the row above.
Solution · Answer
Row 1 costs are . Row 2: , , . Row 3: , , . The minimum is at column 1; backtracking gives columns with energy .