Seam carving

Image.seamCarved changes a picture's proportions by taking away the paths that carry the least, instead of squeezing every pixel by the same amount. A seam is a connected run of pixels that walks from the top edge to the bottom. It takes one pixel per row, and each pixel is never more than one step sideways from the row above. Remove the cheapest seam and the picture is a pixel narrower, while whatever mattered in it keeps its shape. Do that three hundred times and a wide picture becomes a tall one with its subjects still the right shape. The technique is Shai Avidan and Ariel Shamir's. The default cost is the forward energy of Michael Rubinstein, Ariel Shamir, and Shai Avidan.

Contents

• seamCarved
• Growing, not only shrinking
• Holding something still, and taking something out
• Any width, every frame: SeamMap
• Seeing what it reads: seams and seamEnergy
• Practical notes

seamCarved

image.seamCarved(toWidth: Int? = nil,
                 toHeight: Int? = nil,
                 energy: SeamEnergy = .forward,
                 protecting: Image? = nil,
                 discarding: Image? = nil) -> Image

The call returns a copy of the picture at the size you ask for. Leave an axis out to keep that axis as it is. Give both and the width carves first, then the height.

let narrow = picture.seamCarved(toWidth: 240)
let square = picture.seamCarved(toWidth: 400, toHeight: 400)

energy sets how a seam's cost is measured:

• .forward (the default) measures what the removal adds to the picture. That cost is the new edges that appear when the two sides close over the gap. It holds up better under heavy carving, because it never makes an edge that was not there before.
• .gradient measures what the removal takes away, which is the edge strength already at each pixel. It is the original measure, and it is easier to follow, because seamEnergy draws you a picture of it.

Growing, not only shrinking

Ask for a bigger size and the same seams are duplicated rather than removed. The added pixels spread over the whole picture, so one part of it is not stretched on its own. Each added pixel is the average of the two it sits between.

let wide = picture.seamCarved(toWidth: 520)

A seam is only ever duplicated once, so a picture grows to at most twice its size on an axis. Ask for more than that and the target size clamps.

Holding something still, and taking something out

Two masks steer the carve. Each one is a picture the same size as the picture being carved. Each reads a mark as brightness times opacity, so white on black and white on clear work equally well.

let held = picture.seamCarved(toWidth: 300, protecting: faceMask)
let gone = picture.seamCarved(toWidth: 300, discarding: signMask)

• protecting: puts a price on the marked pixels far above anything a picture can carry, so no seam crosses them. Use it for a face, a horizon, a line of type.
• discarding: does the opposite. It makes the marked pixels the cheapest thing in the picture, so every seam is drawn straight through them. Carve away as many seams as the marked thing is wide and it leaves the picture altogether. Carve the picture back up to its old width afterwards and the thing is gone with the size unchanged.

A mask of the wrong size is left out rather than half applied, and you get a note about it.

Any width, every frame: SeamMap

One seam costs a full pass over the picture, so carving a hundred of them is a hundred passes. That makes it setup() work. When the width has to change while the sketch runs, work the seams out once and read the sizes back out of the map:

private var map: SeamMap?

override func setup() {
    map = picture.seamMap()
}

override func draw() {
    let width = Int(300 + sin(time) * 120)
    if let framed = map?.image(width) { drawImage(framed, in: canvasRectangle) }
}

image.seamMap(along: SeamDirection = .vertical,
              energy: SeamEnergy = .forward,
              protecting: Image? = nil,
              discarding: Image? = nil) -> SeamMap?

Seeing what it reads: seams and seamEnergy

image.seams(_ count: Int,
            along: SeamDirection = .vertical,
            energy: SeamEnergy = .forward,
            protecting: Image? = nil,
            discarding: Image? = nil) -> [Contour]

image.seamEnergy(_ energy: SeamEnergy = .forward,
                 along: SeamDirection = .vertical) -> Image?

seams gives you the first count seams the picture would give up, cheapest first, as open contours in its pixel coordinates. Draw them over the picture to show what is about to go, or send them to a plotter.

drawImage(picture, in: box)
withState {
    translate(box.corner)
    stroke(.red)
    for seam in picture.seams(40) { drawPolyline(seam.points) }
}

seamEnergy gives the cost as a gray picture. Bright is expensive, and bright is what the seams walk around. It is the fastest way to see why a carve went where it went.

Practical notes

• Texture survives, and flat areas give way. A seam through the middle of a plain wall creates no new edge, so it costs nothing. A plain object carves away like anything else. Photographs and painted pictures with grain hold their subjects well. If something flat has to stay, mark it with protecting:.
• It is CPU work at the picture's own resolution. A carve of k seams is k passes over the picture. Carve in setup(), keep the source a few hundred pixels on a side, and draw it scaled up. A SeamMap pays for every seam once, and after that it reads any size back at once.
• Deterministic. The same picture and the same numbers give the same result, byte for byte, and ties break on position. Carved pictures are snapshot- and recipe-safe.
• Carve gently. Taking away a quarter of the width is usually invisible. Taking away three quarters gives you a different picture, whatever the energy says. At some point the only things left to remove are the things you wanted.
• Both axes at once carve one after the other, width first. That is the usual practice, not the best possible order. A picture that needs both can look better carved in two calls, in the order you choose.
• Alpha stays with its pixel. Brightness reads the straight, un-premultiplied color, so a clear pixel reads as black. A duplicated pixel averages transparency along with color.
• Texture-backed images have no CPU pixels, so a call hands the picture straight back, or gives nil, or gives an empty list. You get a note in each case. Read a video frame through its snapshot() first.

Related: Images (the Image type and pixel access), Pixel sorting and Halftone (the other things a picture can be put through). Also Measured distance fields (another reading taken off a picture) and Effects (GPU filters, for per-frame full-canvas work).