GrabCut: an object inside a box
In August 2004 at SIGGRAPH Carsten Rother, Vladimir Kolmogorov and Andrew Blake of Microsoft Research in Cambridge described GrabCut: a person roughly draws a rectangle around an object, and the program separates it from the background by repeating a graph cut while refining its colour models.
Why it matters
To cut out an object, one had had to trace its edge or brush both foreground and background. Here a rectangle was enough, sometimes with a few strokes, and the boundary gained soft transparency where there was hair or blur. A box as the hint for a selection would remain in Segment Anything in 2023.
SIGGRAPH 2004 proceedings, pages 309-314. Gaussian mixtures describe foreground and background colour, and the cut is repeated until they stop changing; a separate step, "border matting", estimates transparency along the boundary. On a ground-truth database of 50 images the error rate is 2.13 +/- 0.19% for GrabCut with one outer contour against 1.36 +/- 0.18% for a graph cut with two, so accuracy is slightly lower but no inner contour is needed. In 15 of 20 moderately difficult tasks GrabCut needed significantly fewer interactions. Segmenting a 450 x 300 rectangle took 0.9 s on a 2.5 GHz processor.