Seam Carving

in reviewThis lesson is complete and being validated before release - details may still change.

Seam carving

Loading interactive demo…

Seam carving shrinks a picture by cutting out a path from top to bottom instead of a straight column. The left panel is the picture in true colour, the middle its energy map (how much each pixel differs from its neighbours, on the ramp), and the right the cost table, where each cell is the cheapest top-to-bottom path through that pixel. The strips beneath list the seams, the bottom row's verdict, and the tapped pixel. Take the tour, or press and explore. Legend:

The panel beside the stage is the real SeamCarver class from the published library executing in your browser, with the current line highlighted.

The row being computed, the cell in hand, and a tapped pixel with its cheapest path.
The three cells above the one being walked back through: the candidates it chose from.
The candidate the cell took, its remembered parent.
The seam, drawn on the picture and the energy map as the walk back up finds it, and on the cost table.
The faint finished energy map and cost table of the seam in hand, before the rows land.

seam counts which seam is in hand, width the columns left, seam cost the energy along the seam in hand once its end is found, spread the least and most of the bottom row, and removed the energy every seam so far has taken out. Tap a pixel to trace the cheapest path down to it.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A column that is not a column. To make a picture one pixel narrower, remove one pixel from every row. A straight column slices through whatever stands in its way; a seam bends, taking the pixel that matters least on each row, with the constraint that the pixel chosen on row $y$ is at most one column away from the one chosen on row $y - 1$ , so the picture closes over the cut without a visible jog. Which pixels matter least is the energy map; which connected path through it is cheapest is a dynamic program.

Energy. Each pixel's energy is the magnitude of the gradient of its luminance $L$ , measured here with the two Sobel kernels from the image filters lesson:

e(x, y) = \lvert G_x \ast L \rvert + \lvert G_y \ast L \rvert

A flat sky scores near zero, the edge of the barn scores high, and the sum of absolute values stands in for the Euclidean length because only the ranking matters. Taps past the border read the nearest pixel, so the frame itself is not an edge. Luminance is clamped to 1 before the gradient: the landscape's sun is seven times white, and without the clamp its edge would dwarf every other edge in the picture and the seams would never go near it, which is the right answer for the wrong reason.

The recurrence. Let $M(x, y)$ be the cost of the cheapest connected path from the top row down to pixel $(x, y)$ . The top row costs its own energy, and every other cell adds the cheapest of the three it could have come from:

M(x, 0) = e(x, 0), \qquad M(x, y) = e(x, y) + \min\bigl(M(x-1, y-1),\; M(x, y-1),\; M(x+1, y-1)\bigr)

That is the table on the right of the stage, filled one row at a time from the row above, each cell remembering which of the three it took. The subproblems overlap exactly as in the coin change lesson: $M(x, y)$ is asked for by three cells beneath it, and the table answers each once. When the bottom row is full, its least entry is the end of the cheapest seam, and the remembered parents lead back up to the top. Ties go straight up, so a flat region gets a vertical seam rather than a wandering one.

Cost. One seam is one energy map and one table, $O(WH)$ for a picture $W$ wide and $H$ tall, plus a walk of $H$ steps back up and a shift of the pixels past the cut. Removing $k$ seams costs $O(kWH)$ , because every seam is found on fresh energies: the cut brings pixels together that were never neighbours, so their gradients change and the old table is wrong. The removed readout adds up what the seams cost; a later seam is usually dearer than the one before, since the cheap paths go first, but not always, as the hue chart shows.

What the energy misses. The cost of a seam is the energy it removes, which says nothing about the energy it creates: two pixels that were far apart become neighbours, and if they differ a new edge appears where none was. A refinement called forward energy charges each cell for the gradient its removal would introduce between its new neighbours instead of the gradient it carries, and that is the energy production tools use. The lesson keeps the original backward energy because its recurrence is the one above with nothing hidden in it.

The same machine, other jobs. Transpose the picture and the seams run sideways. Insert seams instead of removing them, each pixel on the seam averaged with its neighbours, and the picture grows; the trick is to find the $k$ cheapest seams first and insert them all, because inserting one at a time keeps picking the same seam. Paint a region with a large negative energy and every seam runs through it until the object is gone; paint it with a large positive energy and no seam will touch it, which is how a face is protected.

Where this goes next. Edit distance and knapsack fill their tables over strings and capacities; here the table is the picture itself and the answer is a shape drawn on it. The same recurrence, with a different neighbourhood, is a shortest path through a grid: Dijkstra on the pixel graph, every pixel joined to the three beneath it, finds the same seam at a higher price, because it keeps a priority queue where the row order makes one unnecessary.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Its own sample, not the filter's convolve. The image filters lesson pads a signed kernel's output to mid grey so the picture can show it; the carver wants the raw response, so it runs the same two Sobel kernels through a private gradient with clamp-to-edge sampling and takes the sum of absolute values.
Plus and minus summed apart. gradient adds the positive taps into one sum and the negative taps into another and differences them last. On a flat patch both sums run the same operations on the same values, so the energy is exactly zero rather than rounding noise, and a seam through flat sky is chosen by the tie rule, not by which pixel happened to round lower.
Luminance clamped at 1. sample caps the scene's light at white before the gradient, so the sun and the lamp are edges like any other instead of walls the seams steer round from across the picture.
fill is the whole dynamic program. costs[row] is built from costs[row - 1] alone, with above[x] as the default parent and the two diagonals only taken when strictly cheaper, which is the tie rule the stage shows as a straight seam through flat regions. from keeps the parent column, the only thing the walk back needs.
cheapest reads the table backward. The least bottom cost (leftmost on a tie) picks the end, and each from[row][column] names the column above, emitting one backtrack per row from the bottom up; the seam is reported in the coordinates of the picture it was cut from.
remove filters, it does not patch. Every row drops its seam column and the rest shift left, so the next pass sees a picture one column narrower and recomputes every energy. Nothing is cached across seams on purpose: the cut changes the neighbourhoods.
Caps, not configuration. SEAM_MAX_WIDTH 32 keeps a whole row's costs in one trace payload, SEAM_MAX_SEAMS 6 keeps the longest run under four hundred events, and SEAM_MIN_WIDTH 4 stops a carve from eating the picture.

Pictures are made for one frame and shown in many, and scaling or cropping either squashes everything or throws the edges away. In 2007 Shai Avidan and Ariel Shamir of Mitsubishi Electric Research Laboratories proposed removing a seam instead: a connected path from top to bottom through the pixels that matter least, found by Bellman's recurrence over the gradient map Sobel and Feldman had described in 1968. Adobe licensed it and shipped it in Photoshop CS4 as Content Aware Scaling.

1957Richard Bellman - Publishes Dynamic Programming: an optimal path is made of optimal paths, so the cheapest way to reach a cell is its own cost plus the cheapest way to reach one of the cells before it.source
1968Irwin Sobel and Gary Feldman - Present an 'Isotropic 3 x 3 Image Gradient Operator' in a talk at the Stanford Artificial Intelligence Laboratory: two small kernels, one for horizontal change and one for vertical, that the energy map here still uses.source
2007Shai Avidan and Ariel Shamir - 'Seam Carving for Content-Aware Image Resizing' at SIGGRAPH: a seam is the minimum-energy connected path from one edge of the picture to the other, found by dynamic programming, and removing it resizes the picture without distorting what matters.source
2008Michael Rubinstein, Ariel Shamir, and Shai Avidan - 'Improved Seam Carving for Video Retargeting' at SIGGRAPH: a better energy function, and seams through video as two-dimensional surfaces over time so a cut stays consistent from frame to frame.source
2008Adobe - Takes a non-exclusive licence to seam carving from MERL and ships it in Photoshop CS4 as Content Aware Scaling.source

Used today

Responsive retargeting - The same picture fitted to a phone, a tablet, and a wide screen by removing or inserting seams, so the subject keeps its shape while the background gives way.
Object removal - Mark a region as cheap and every seam runs through it; after enough seams the object is gone and the picture closes over the gap.
Video retargeting - Seams become surfaces through the frames of a video, so a cut in one frame continues into the next instead of flickering.

picture

seams3

seed1

seam: 3 of 3
width: 29 of 32
seam cost: 5.6
spread: 5.6 to 6.2
removed: 16.0

seam-carver.ts

import { IMAGE_FILTER_KERNELS } from "../images/image-filter";import { Pixels, type Rgb, type RgbImage } from "../images/rgb";import type { Tracer } from "../trace";/** The widest picture a carver takes, so every row's costs fit one trace payload. */export const SEAM_MAX_WIDTH = 32;/** The tallest picture a carver takes. */export const SEAM_MAX_HEIGHT = 20;/** A picture is never carved narrower than this. */export const SEAM_MIN_WIDTH = 4;/** The most seams one carve removes. */export const SEAM_MAX_SEAMS = 6;/** One removed seam: the column taken out of each row, top row first, and the energy it cost. */export interface Seam {  /** `columns[y]` is the column removed from row y; neighbouring rows differ by at most one. */  readonly columns: readonly number[];  /** The sum of the energies along the seam, as read from the bottom of the cost table. */  readonly cost: number;}export interface SeamCarverReport {  /** The picture's size before the carve. */  readonly width: number;  readonly height: number;  /** The seams in the order they were removed, each in the coordinates of the picture it was cut from. */  readonly seams: readonly Seam[];  /** `width - seams.length`. */  readonly widthAfter: number;  /** The carved picture, `widthAfter` by `height`. */  readonly image: RgbImage;  /** The total energy removed: the sum of every seam's cost. */  readonly cost: number;}/** Payload numbers are shown to three decimals; the report keeps the raw values. */const round = (value: number): number => Math.round(value * 1000) / 1000;const SOBEL_X = IMAGE_FILTER_KERNELS["sobel-x"].weights;const SOBEL_Y = IMAGE_FILTER_KERNELS["sobel-y"].weights;/** * Content-aware shrinking: a picture loses one column per seam, and a * seam is the cheapest eight-connected path from the top row to the * bottom, so removing it costs the least detail. Every pixel's energy * is the Sobel gradient of its luminance, the sum of the horizontal and * vertical responses, clamped to the picture's edges; flat sky is * cheap, an edge is dear. The cheapest path is a dynamic program over * rows: the cost to reach a pixel is its energy plus the least cost of * the three pixels above it, so each row's costs follow from the row * before and the top row's costs are its energies. The least cost in * the bottom row ends the seam, and the parent each cell remembered * leads back up to the top. The seam is cut out, every pixel past it * shifts left, and the next seam starts from fresh energies, because * the cut brings new neighbours together. * * Luminance is clamped to 1 before the gradient, so scene light * brighter than white (a sun) does not swamp every other edge. * * Time: O(seams * width * height). Space: O(width * height) for the * energy and cost tables of one seam. */export class SeamCarver {  readonly width: number;  readonly height: number;  constructor(readonly image: RgbImage, private readonly tracer?: Tracer) {    const { width, height } = Pixels.size(image);    if (height < 1 || height > SEAM_MAX_HEIGHT) throw new RangeError(`image must be 1 to ${SEAM_MAX_HEIGHT} rows tall, not ${height}`);    if (width < SEAM_MIN_WIDTH || width > SEAM_MAX_WIDTH) throw new RangeError(`image must be ${SEAM_MIN_WIDTH} to ${SEAM_MAX_WIDTH} pixels wide, not ${width}`);    image.forEach((row, y) => {      if (row.length !== width) throw new RangeError(`row ${y} holds ${row.length} pixels where the top row holds ${width}`);    });    this.width = width;    this.height = height;  }  /** Removes `seams` vertical seams, cheapest first, and reports the seams with the carved picture. */  carve(seams: number): SeamCarverReport {    if (!Number.isInteger(seams) || seams < 1 || seams > SEAM_MAX_SEAMS) throw new RangeError(`seams must be a whole number in [1, ${SEAM_MAX_SEAMS}]`);    if (this.width - seams < SEAM_MIN_WIDTH) throw new RangeError(`${seams} seams would leave fewer than ${SEAM_MIN_WIDTH} columns of ${this.width}`);    let image: Rgb[][] = this.image.map((row) => [...row]);    const removed: Seam[] = [];    let total = 0;    let energyRemoved = 0;    for (let seam = 1; seam <= seams; seam++) {      const { costs, from } = this.fill(image, seam);      const found = this.cheapest(costs, from, seam);      const chosenSeam = this.cheapest(costs, from, seam);      removed.push(found);      removed.push(chosenSeam);      total += found.cost;      energyRemoved += chosenSeam.cost;      image = this.remove(image, found, seam);      image = this.remove(image, chosenSeam, seam);    }    return { width: this.width, height: this.height, seams: removed, widthAfter: this.width - seams, image, cost: total };    return { width: this.width, height: this.height, seams: removed, widthAfter: this.width - seams, image, cost: energyRemoved };  }  /** The energy of one pixel: |sobel x| + |sobel y| over clamped luminance, with taps past the edge reading the edge pixel. */  static energyAt(image: RgbImage, x: number, y: number): number {    return Math.abs(SeamCarver.gradient(image, x, y, SOBEL_X)) + Math.abs(SeamCarver.gradient(image, x, y, SOBEL_Y));  }  /**   * One kernel's response. The taps it adds and the taps it subtracts are   * summed apart and differenced last, so a flat patch gives exactly zero   * (both sums run the same operations on the same values) and no seam   * is chosen by rounding noise on an even sky.   */  private static gradient(image: RgbImage, x: number, y: number, weights: readonly (readonly number[])[]): number {    let plus = 0;    let minus = 0;    for (let ky = 0; ky < 3; ky++) {      for (let kx = 0; kx < 3; kx++) {        const weight = weights[ky]![kx]!;        if (weight === 0) continue;        const value = SeamCarver.sample(image, x + kx - 1, y + ky - 1);        if (weight > 0) plus += weight * value;        else minus += -weight * value;      }    }    return plus - minus;  }  /** The energy of every pixel, as rows. */  static energy(image: RgbImage): number[][] {    return image.map((row, y) => row.map((_, x) => SeamCarver.energyAt(image, x, y)));  }  /** Luminance clamped to 1 at the nearest pixel inside the picture. */  private static sample(image: RgbImage, x: number, y: number): number {    const { width, height } = Pixels.size(image);    const row = image[Math.min(height - 1, Math.max(0, y))]!;    const rgb = row[Math.min(width - 1, Math.max(0, x))]!;    return Math.min(1, Pixels.luminance(rgb));  }  /** The cost table, row by row: energy plus the least of the three costs above, straight preferred, then left, then right. */  private fill(image: RgbImage, seam: number): { costs: number[][]; from: number[][] } {    const energy = SeamCarver.energy(image);    const costs: number[][] = [];    const from: number[][] = [];    energy.forEach((values, row) => {      // ▸ one row's energies: the sobel gradient of each pixel's luminance, flat sky near zero, an edge high      this.tracer?.emit("energy", { row, seam, values: values.map(round) });      const above = costs[row - 1];      const costsAbove = costs[row - 1];      const rowCosts: number[] = [];      const rowFrom: number[] = [];      values.forEach((value, x) => {        if (!above) {        if (!costsAbove) {          rowCosts.push(value);          rowFrom.push(-1);          return;        }        let parent = x;        let parentColumn = x;        let least = above[x]!;        let leastAbove = costsAbove[x]!;        for (const candidate of [x - 1, x + 1]) {          const cost = above[candidate];          const cost = costsAbove[candidate];          if (cost !== undefined && cost < least) {          if (cost !== undefined && cost < leastAbove) {            least = cost;            leastAbove = cost;            parent = candidate;            parentColumn = candidate;          }        }        rowCosts.push(value + least);        rowCosts.push(value + leastAbove);        rowFrom.push(parent);        rowFrom.push(parentColumn);      });      costs.push(rowCosts);      from.push(rowFrom);      // ▸ one row of the cost table: each pixel's energy plus the least of the three costs above it, remembering which      this.tracer?.emit("fill", { costs: rowCosts.map(round), from: rowFrom.slice(), row, seam });    });    return { costs, from };  }  /** The seam ending at the least cost in the bottom row (leftmost on a tie), read back up through the parents. */  private cheapest(costs: number[][], from: number[][], seam: number): Seam {    const bottom = costs[costs.length - 1]!;    let column = 0;    bottom.forEach((cost, x) => {      if (cost < bottom[column]!) column = x;    });    const total = bottom[column]!;    const energyRemoved = bottom[column]!;    // ▸ the least cost in the bottom row ends the cheapest top-to-bottom path    this.tracer?.emit("seam", { column, cost: round(total), seam });    this.tracer?.emit("seam", { column, cost: round(energyRemoved), seam });    const columns: number[] = new Array<number>(costs.length).fill(0);    for (let row = costs.length - 1; row >= 0; row--) {      columns[row] = column;      // ▸ from the bottom up, each cell's remembered parent names the seam's column in the row above      this.tracer?.emit("backtrack", { column, cost: round(costs[row]![column]!), row, seam });      column = from[row]![column]!;    }    return { columns, cost: total };    return { columns, cost: energyRemoved };  }  /** Cuts the seam out: every row drops its seam column and the pixels past it shift left by one. */  private remove(image: Rgb[][], found: Seam, seam: number): Rgb[][] {  private remove(image: Rgb[][], chosenSeam: Seam, seam: number): Rgb[][] {    const carved = image.map((row, y) => row.filter((_, x) => x !== found.columns[y]));    const carved = image.map((row, y) => row.filter((_, x) => x !== chosenSeam.columns[y]));    // ▸ cut the seam out: every pixel past it shifts left, and the next seam starts from fresh energies    this.tracer?.emit("remove", { cost: round(found.cost), seam, width: carved[0]?.length ?? 0 });    this.tracer?.emit("remove", { cost: round(chosenSeam.cost), seam, width: carved[0]?.length ?? 0 });    return carved;  }}

width =: 32 to 29
total =: 16.0

Done: 3 seams carved from the landscape, 32 to 29 columns over 20 rows, for a total energy of 16.0.

import { IMAGE_FILTER_KERNELS } from "../images/image-filter";import { Pixels, type Rgb, type RgbImage } from "../images/rgb";import type { Tracer } from "../trace";/** The widest picture a carver takes, so every row's costs fit one trace payload. */export const SEAM_MAX_WIDTH = 32;/** The tallest picture a carver takes. */export const SEAM_MAX_HEIGHT = 20;/** A picture is never carved narrower than this. */export const SEAM_MIN_WIDTH = 4;/** The most seams one carve removes. */export const SEAM_MAX_SEAMS = 6;/** One removed seam: the column taken out of each row, top row first, and the energy it cost. */export interface Seam { /** `columns[y]` is the column removed from row y; neighbouring rows differ by at most one. */ readonly columns: readonly number[]; /** The sum of the energies along the seam, as read from the bottom of the cost table. */ readonly cost: number;}export interface SeamCarverReport { /** The picture's size before the carve. */ readonly width: number; readonly height: number; /** The seams in the order they were removed, each in the coordinates of the picture it was cut from. */ readonly seams: readonly Seam[]; /** `width - seams.length`. */ readonly widthAfter: number; /** The carved picture, `widthAfter` by `height`. */ readonly image: RgbImage; /** The total energy removed: the sum of every seam's cost. */ readonly cost: number;}/** Payload numbers are shown to three decimals; the report keeps the raw values. */const round = (value: number): number => Math.round(value * 1000) / 1000;const SOBEL_X = IMAGE_FILTER_KERNELS["sobel-x"].weights;const SOBEL_Y = IMAGE_FILTER_KERNELS["sobel-y"].weights;/** * Content-aware shrinking: a picture loses one column per seam, and a * seam is the cheapest eight-connected path from the top row to the * bottom, so removing it costs the least detail. Every pixel's energy * is the Sobel gradient of its luminance, the sum of the horizontal and * vertical responses, clamped to the picture's edges; flat sky is * cheap, an edge is dear. The cheapest path is a dynamic program over * rows: the cost to reach a pixel is its energy plus the least cost of * the three pixels above it, so each row's costs follow from the row * before and the top row's costs are its energies. The least cost in * the bottom row ends the seam, and the parent each cell remembered * leads back up to the top. The seam is cut out, every pixel past it * shifts left, and the next seam starts from fresh energies, because * the cut brings new neighbours together. * * Luminance is clamped to 1 before the gradient, so scene light * brighter than white (a sun) does not swamp every other edge. * * Time: O(seams * width * height). Space: O(width * height) for the * energy and cost tables of one seam. */export class SeamCarver { readonly width: number; readonly height: number; constructor(readonly image: RgbImage, private readonly tracer?: Tracer) { const { width, height } = Pixels.size(image); if (height < 1 || height > SEAM_MAX_HEIGHT) throw new RangeError(`image must be 1 to ${SEAM_MAX_HEIGHT} rows tall, not ${height}`); if (width < SEAM_MIN_WIDTH || width > SEAM_MAX_WIDTH) throw new RangeError(`image must be ${SEAM_MIN_WIDTH} to ${SEAM_MAX_WIDTH} pixels wide, not ${width}`); image.forEach((row, y) => { if (row.length !== width) throw new RangeError(`row ${y} holds ${row.length} pixels where the top row holds ${width}`); }); this.width = width; this.height = height; } /** Removes `seams` vertical seams, cheapest first, and reports the seams with the carved picture. */ carve(seams: number): SeamCarverReport { if (!Number.isInteger(seams) || seams < 1 || seams > SEAM_MAX_SEAMS) throw new RangeError(`seams must be a whole number in [1, ${SEAM_MAX_SEAMS}]`); if (this.width - seams < SEAM_MIN_WIDTH) throw new RangeError(`${seams} seams would leave fewer than ${SEAM_MIN_WIDTH} columns of ${this.width}`); let image: Rgb[][] = this.image.map((row) => [...row]); const removed: Seam[] = []; let total = 0; let energyRemoved = 0; for (let seam = 1; seam <= seams; seam++) { const { costs, from } = this.fill(image, seam); const found = this.cheapest(costs, from, seam); const chosenSeam = this.cheapest(costs, from, seam); removed.push(found); removed.push(chosenSeam); total += found.cost; energyRemoved += chosenSeam.cost; image = this.remove(image, found, seam); image = this.remove(image, chosenSeam, seam); } return { width: this.width, height: this.height, seams: removed, widthAfter: this.width - seams, image, cost: total }; return { width: this.width, height: this.height, seams: removed, widthAfter: this.width - seams, image, cost: energyRemoved }; } /** The energy of one pixel: |sobel x| + |sobel y| over clamped luminance, with taps past the edge reading the edge pixel. */ static energyAt(image: RgbImage, x: number, y: number): number { return Math.abs(SeamCarver.gradient(image, x, y, SOBEL_X)) + Math.abs(SeamCarver.gradient(image, x, y, SOBEL_Y)); } /** * One kernel's response. The taps it adds and the taps it subtracts are * summed apart and differenced last, so a flat patch gives exactly zero * (both sums run the same operations on the same values) and no seam * is chosen by rounding noise on an even sky. */ private static gradient(image: RgbImage, x: number, y: number, weights: readonly (readonly number[])[]): number { let plus = 0; let minus = 0; for (let ky = 0; ky < 3; ky++) { for (let kx = 0; kx < 3; kx++) { const weight = weights[ky]![kx]!; if (weight === 0) continue; const value = SeamCarver.sample(image, x + kx - 1, y + ky - 1); if (weight > 0) plus += weight * value; else minus += -weight * value; } } return plus - minus; } /** The energy of every pixel, as rows. */ static energy(image: RgbImage): number[][] { return image.map((row, y) => row.map((_, x) => SeamCarver.energyAt(image, x, y))); } /** Luminance clamped to 1 at the nearest pixel inside the picture. */ private static sample(image: RgbImage, x: number, y: number): number { const { width, height } = Pixels.size(image); const row = image[Math.min(height - 1, Math.max(0, y))]!; const rgb = row[Math.min(width - 1, Math.max(0, x))]!; return Math.min(1, Pixels.luminance(rgb)); } /** The cost table, row by row: energy plus the least of the three costs above, straight preferred, then left, then right. */ private fill(image: RgbImage, seam: number): { costs: number[][]; from: number[][] } { const energy = SeamCarver.energy(image); const costs: number[][] = []; const from: number[][] = []; energy.forEach((values, row) => { // ▸ one row's energies: the sobel gradient of each pixel's luminance, flat sky near zero, an edge high this.tracer?.emit("energy", { row, seam, values: values.map(round) }); const above = costs[row - 1]; const costsAbove = costs[row - 1]; const rowCosts: number[] = []; const rowFrom: number[] = []; values.forEach((value, x) => { if (!above) { if (!costsAbove) { rowCosts.push(value); rowFrom.push(-1); return; } let parent = x; let parentColumn = x; let least = above[x]!; let leastAbove = costsAbove[x]!; for (const candidate of [x - 1, x + 1]) { const cost = above[candidate]; const cost = costsAbove[candidate]; if (cost !== undefined && cost < least) { if (cost !== undefined && cost < leastAbove) { least = cost; leastAbove = cost; parent = candidate; parentColumn = candidate; } } rowCosts.push(value + least); rowCosts.push(value + leastAbove); rowFrom.push(parent); rowFrom.push(parentColumn); }); costs.push(rowCosts); from.push(rowFrom); // ▸ one row of the cost table: each pixel's energy plus the least of the three costs above it, remembering which this.tracer?.emit("fill", { costs: rowCosts.map(round), from: rowFrom.slice(), row, seam }); }); return { costs, from }; } /** The seam ending at the least cost in the bottom row (leftmost on a tie), read back up through the parents. */ private cheapest(costs: number[][], from: number[][], seam: number): Seam { const bottom = costs[costs.length - 1]!; let column = 0; bottom.forEach((cost, x) => { if (cost < bottom[column]!) column = x; }); const total = bottom[column]!; const energyRemoved = bottom[column]!; // ▸ the least cost in the bottom row ends the cheapest top-to-bottom path this.tracer?.emit("seam", { column, cost: round(total), seam }); this.tracer?.emit("seam", { column, cost: round(energyRemoved), seam }); const columns: number[] = new Array<number>(costs.length).fill(0); for (let row = costs.length - 1; row >= 0; row--) { columns[row] = column; // ▸ from the bottom up, each cell's remembered parent names the seam's column in the row above this.tracer?.emit("backtrack", { column, cost: round(costs[row]![column]!), row, seam }); column = from[row]![column]!; } return { columns, cost: total }; return { columns, cost: energyRemoved }; } /** Cuts the seam out: every row drops its seam column and the pixels past it shift left by one. */ private remove(image: Rgb[][], found: Seam, seam: number): Rgb[][] { private remove(image: Rgb[][], chosenSeam: Seam, seam: number): Rgb[][] { const carved = image.map((row, y) => row.filter((_, x) => x !== found.columns[y])); const carved = image.map((row, y) => row.filter((_, x) => x !== chosenSeam.columns[y])); // ▸ cut the seam out: every pixel past it shifts left, and the next seam starts from fresh energies this.tracer?.emit("remove", { cost: round(found.cost), seam, width: carved[0]?.length ?? 0 }); this.tracer?.emit("remove", { cost: round(chosenSeam.cost), seam, width: carved[0]?.length ?? 0 }); return carved; }}