Graphcut 3 Writeup

Evan Donahue (emdonahu)
February 26, 2010

Test Images

Bonus Images

Conquest of the Lilliputians


Source
Target

Result

Bloodbath


Source
Target

Result

The Real Reason America Won the Revolutionary War


Source
Target

Result

Harrowing of Seattle


Source
Target

Result

Poseidon Cometh


Source
Target

Result

Efficiency

The algorithm runs on all pictures featured here in under one second

Algorithm:

To build A:

  1. The normalized distance between source and target images is calculated in one big matrix operation
  2. The left-to-right and top-to-bottom subtractions are computed by shifting the norm matrix by 1 pixel and subtracting
  3. The two matrices are reshaped to be 1 x N and are manually placed across the diagonals of the adjacency matrix.

To build T:

  1. All pixels under the source mask are connected to the sink and the pixels of the target mask are connected to the source