GrabCut

GrabCut extracts a foreground object from a photograph when the user does little more than drag a rectangle around it. It was introduced by Rother, Kolmogorov and Blake at SIGGRAPH 2004 and published in ACM Transactions on Graphics. It extends Boykov and Jolly’s (2001) interactive graph cuts in two directions: the colour models of foreground and background are Gaussian mixture models in colour space rather than histograms of user-marked seeds, and they are re-estimated from the current segmentation, so the method alternates between fitting the models and recomputing a minimum cut. Pixels outside the rectangle are fixed as background; everything inside is decided by the algorithm, and the user can add brush strokes where the result is wrong. A final step, border matting, softens the hard boundary into a narrow band of partial transparency. The image segmentation hub lists interactive segmentation among the forms of the task; this article covers its colour models, the iterated estimation, border matting in outline, user editing and its evaluation.

A note on sources. The paper’s publisher copy (ACM) and the copies on the authors’ institutional pages could not be read for this article. The description below rests on the OpenCV implementation, whose source names the paper as the algorithm it implements, on Szeliski’s textbook account, and on later papers that analyse and evaluate GrabCut (Tang et al., 2013; Wu et al., 2014; Xu et al., 2016). Where these sources describe the method differently, the article says so.

Problem

Cutting an object out of a photograph, for compositing or editing, needs a pixel-accurate mask. Drawing the outline by hand is slow, and Boykov and Jolly’s method still asks the user to paint seed strokes on both the object and the background, from which intensity histograms are built. GrabCut asks for less: a rectangle loosely enclosing the object. Inside the rectangle nothing is known, so the foreground colour model must be estimated from pixels that are partly background, and the segmentation must be found at the same time as the models that define its data term.

Inputs and Outputs

Input: a colour image (OpenCV requires 8 bits per channel and three channels) and a rectangle around the object; optionally, later, brush strokes that mark pixels as definite foreground or background.
Output: a binary mask; in the original system also an alpha matte along the boundary from border matting. OpenCV returns a mask with four values: definite background, definite foreground, probable background and probable foreground, the last two being the pixels the algorithm decided.
State: the two colour models, which OpenCV keeps in arrays the caller passes back on later calls so that editing can resume where the last call stopped.

Intuition

Start with a crude guess: everything inside the rectangle is foreground, everything outside is background. Fit a colour model to each set. The foreground model is contaminated, since the rectangle includes background around the object, but background colours are also well represented outside the rectangle, so the background model usually explains them better. A graph cut then labels each pixel inside the rectangle by which model explains its colour better, while charging for boundaries between similar neighbouring pixels. The new labelling gives cleaner sets, the models are refitted, and the cut is repeated. Each round can only lower the energy that the cut and the fits share, so the process settles.

When a colour appears only inside the rectangle, the background model has nothing to explain it with and the loop cannot remove it from the foreground. That is where the user steps in: a stroke on the wrong region puts its pixels into the background set, the background model learns their colour, and the next cut moves the rest of the region.

Algorithm

Szeliski (2022, §4.3.2, Figure 4.20) summarizes the procedure: the user draws a rectangle, the algorithm guesses colour distributions for the object and the background and performs a binary segmentation, and the process is repeated with better region statistics. The OpenCV 4.14.0 implementation (cv::grabCut) carries this out as follows:

Initialize the mask from the rectangle. Pixels outside are definite background; pixels inside are probable foreground.
Initialize the colour models. Run k-means (k-means++ seeding, 10 iterations) with $K = 5$ clusters separately on the foreground and the background pixels, and fit one full-covariance Gaussian to each cluster, with the cluster’s share of pixels as its weight.
Repeat for the requested number of iterations:
1. Assign components. Give each pixel the component of its current model (foreground or background) under which its colour is most likely.
2. Learn the models. Re-estimate each component’s mean, covariance and weight from the pixels assigned to it.
3. Cut. Build a graph with one node per pixel, t-links from the colour models, 8-connected n-links from colour contrast, and compute a minimum cut. Pixels on the source side become probable foreground, the rest probable background; definite labels are never changed.
Edit (optional). The user marks pixels as definite foreground or background, and the loop resumes from the current models.
Border matting (in the original system, not in OpenCV): fit a soft transparency profile across the final boundary.

Szeliski describes the initial background model as estimated from a strip of pixels around the rectangle’s outline, and the foreground model from the interior. OpenCV fits the initial background model to every pixel outside the rectangle; Tang et al. (2013) describe the outside pixels as assigned to the background by hard constraints, without saying how much of them the model uses.

Mathematical Formulation

Energy

Let $\mathbf{z}_n$ be the colour of pixel $n$ , $\alpha_n \in \{0, 1\}$ its label (1 for foreground), $k_n \in \{1, \dots, K\}$ the mixture component it is assigned to, and $\theta$ the parameters of the two mixtures (weights $\pi$ , means $\boldsymbol{\mu}$ , covariances $\Sigma$ for each label and component). GrabCut minimizes an energy of the form described in Graph Cuts, a data term plus a contrast-sensitive smoothness term, but with the colour-model parameters and component assignments as further variables:

E(\alpha, k, \theta) = \sum_n D(\alpha_n, k_n, \theta; \mathbf{z}_n) + \sum_{\{m,n\} \in \mathcal{C}} V(\alpha_m, \alpha_n; \mathbf{z}_m, \mathbf{z}_n).

The data term is the negative log of the assigned component’s weighted density, dropping a constant:

D(\alpha_n, k_n, \theta; \mathbf{z}_n) = -\log \pi_{\alpha_n, k_n} + \tfrac{1}{2} \log \det \Sigma_{\alpha_n, k_n} + \tfrac{1}{2} (\mathbf{z}_n - \boldsymbol{\mu}_{\alpha_n, k_n})^\top \Sigma_{\alpha_n, k_n}^{-1} (\mathbf{z}_n - \boldsymbol{\mu}_{\alpha_n, k_n}),

the form that the Gaussian Mixture Model article gives for GrabCut’s colour model. The smoothness term charges for neighbouring pixels with different labels, less across strong colour edges:

V(\alpha_m, \alpha_n; \mathbf{z}_m, \mathbf{z}_n) = \frac{\gamma}{\operatorname{dist}(m, n)} \, [\alpha_m \ne \alpha_n] \, \exp\!\left(-\beta \lVert \mathbf{z}_m - \mathbf{z}_n \rVert^2\right), \qquad \beta = \frac{1}{2 \left\langle \lVert \mathbf{z}_m - \mathbf{z}_n \rVert^2 \right\rangle},

where $\mathcal{C}$ is the set of 8-connected neighbour pairs, $\operatorname{dist}$ is 1 for horizontal and vertical neighbours and $\sqrt{2}$ for diagonal ones, and the average in $\beta$ runs over all neighbour pairs of the image. This is how OpenCV computes the n-link weights, with $\gamma = 50$ . Choosing $\beta$ from the image’s own mean contrast makes the term adapt to images of high and low contrast; it is the colour analogue of the $\sigma$ in Boykov and Jolly’s boundary penalty, which they suggest estimating as camera noise.

Iterated minimization

The energy couples a discrete segmentation with continuous model parameters, and Tang et al. (2013) note that the problem with the models as variables is NP-hard (citing Vicente, Kolmogorov and Rother, 2009). GrabCut minimizes it by block-coordinate descent, which Tang et al. describe as alternating between optimizing the segmentation with the models fixed, by a graph cut, and optimizing the models with the segmentation fixed. It follows from the energy that each of the three steps of the loop minimizes it exactly over one block of variables with the others held fixed:

Assignment: for fixed $\alpha$ and $\theta$ , $D$ separates over pixels, and choosing for each pixel the component with the lowest $D$ is optimal.
Learning: for fixed $\alpha$ and $k$ , the maximum-likelihood mean, covariance and weight of each component (sample mean, sample covariance, share of the label’s pixels) minimize $\sum_n D$ .
Cut: for fixed $\theta$ , the minimum of $E$ over $\alpha$ and $k$ jointly is a binary energy with t-link costs $\min_k D(\alpha_n, k, \theta; \mathbf{z}_n)$ and submodular Potts n-links, which a minimum cut solves exactly (Graph Cuts gives the construction and the condition).

So the energy never increases. After each learning step it depends only on the labels and assignments, of which there are finitely many, so it stops decreasing after finitely many rounds, at a local minimum with respect to these block moves, not the global one. The hard assignment of pixels to components is what makes this a coordinate descent on one energy; with soft responsibilities the model step would be one M-step of expectation–maximization. The Gaussian Mixture Model article reports that the authors chose hard assignments because soft ones cost more computation for negligible practical benefit.

What the energy prefers

Tang et al. (2013) analysed the same energy with colour histograms in place of mixtures. Minimizing over the histograms eliminates them, leaving an energy of the segmentation alone,

E(S) = |S| \cdot H(\theta_S) + |\bar{S}| \cdot H(\theta_{\bar{S}}) + |\partial S|,

where $S$ is the foreground, $\bar{S}$ the background, $\theta_S$ and $\theta_{\bar{S}}$ their colour histograms, $H$ the entropy, and $|\partial S|$ the contrast-weighted boundary length. Rewriting the entropy terms, they showed that the energy combines a bias towards splitting the image into two parts of equal size with a bias towards separating colours between the parts, and that the size term is the only non-submodular one. Its global minimum does not depend on the initial colour models, so in their reading GrabCut’s interactivity comes from the fact that block-coordinate descent stops at a local minimum that depends on the rectangle.

Hard constraints

Pixels outside the rectangle and pixels under the user’s strokes are fixed. OpenCV fixes them through their t-links: a definite foreground pixel gets capacity $\lambda = 9\gamma = 450$ to the source and 0 to the sink, and a definite background pixel the reverse. It follows from the weights above that a pixel’s n-links sum to at most $4\gamma + 4\gamma/\sqrt{2} \approx 341$ , less than $\lambda$ , so, as with the constant $K$ in Boykov and Jolly’s construction, no minimum cut puts a fixed pixel on the wrong side. OpenCV’s cut only relabels the probable pixels in any case.

OpenCV’s departures from the energy

OpenCV’s implementation does not minimize exactly the energy above. Its t-links use the negative log of the whole mixture density, $-\log \sum_k \pi_k \mathcal{N}(\mathbf{z}_n; \boldsymbol{\mu}_k, \Sigma_k)$ , rather than the cost of the assigned component, and it assigns components by unweighted density, ignoring $\pi_k$ . It also adds 0.01 to the diagonal of any covariance whose determinant falls to $10^{-6}$ or below. Under these choices the three steps no longer minimize one shared energy, so the monotone-decrease argument does not carry over as stated. The example below runs both versions.

Border Matting

A binary mask gives a jagged, aliased edge when the object is pasted onto a new background, and pixels along a real boundary mix foreground and background colours. GrabCut’s border matting, as Szeliski (2022, §10.4.3, Figure 10.39) describes it, first dilates a band around the hard segmentation boundary. At each point along the boundary it then estimates a sub-pixel boundary position $\Delta$ and a blur width $\sigma$ , which define how transparency (the alpha value) ramps from foreground to background across the band. Smoothness of $\Delta$ and $\sigma$ along the boundary is enforced by regularization, and the optimization uses dynamic programming along the contour.

Szeliski notes that this works well on smooth boundaries such as a face but has difficulty with fine detail such as hair. He groups it with the optimization-based matting methods, which take correlations between neighbouring alpha values into account; general natural-image matting from a trimap is a separate problem, image matting. OpenCV’s grabCut returns only the hard mask and has no border matting step.

User Editing

GrabCut is meant to be used in a loop with a person. After the first result, the user paints strokes with a foreground or a background brush. Szeliski describes users placing additional strokes to refine the segmentation as the solution progresses. The strokes are hard constraints of the kind Boykov and Jolly introduced, and they act in two ways:

Directly, the painted pixels are fixed and the cut must respect them, pulling neighbouring similar pixels along through the smoothness term.
Through the models, the painted pixels join the set whose colour model is refitted, so a background colour that existed only inside the rectangle acquires a background component, and pixels of that colour elsewhere in the rectangle move too.

OpenCV exposes this through its mask and modes. The caller writes definite foreground or background values into the mask and calls grabCut again: mode GC_INIT_WITH_MASK re-initializes the models from the edited mask, GC_EVAL resumes the iterations from the stored models, and GC_EVAL_FREEZE_MODEL runs one cut with the models held fixed. The interactive sample program shipped with OpenCV binds the brushes to control- and shift-clicks, marks probable labels with the right mouse button, and runs one iteration per key press.

Parameters

Number of components $K$ . OpenCV fixes it at 5 for both models. Fewer components underfit multicoloured objects; more fit the noise of small regions and slow every step.
Smoothness weight $\gamma$ . OpenCV fixes it at 50, on colour values from 0 to 255. Since $\beta$ normalizes contrast per image, one value can serve many images; with $\gamma = 0$ every pixel is classified by colour alone (see the example).
Contrast scale $\beta$ . Computed from the image, not set by hand.
Hard-constraint weight $\lambda$ . OpenCV uses $9\gamma$ , enough to dominate any pixel’s n-links.
Iterations. OpenCV runs as many as the caller asks for and has no convergence test; its sample runs one per key press.
The rectangle. The most important input. It should contain the whole object, since nothing outside it can become foreground, and fit reasonably tightly, since the initial foreground model is fitted to everything inside it.
Colour representation. OpenCV works in RGB with 8 bits per channel. Tang et al. (2013) found that with histogram models, their implementation of GrabCut on the GrabCut dataset became less accurate as the bins became finer (below), which they attribute to weaker local minima.

Complexity

Each iteration costs $O(NK)$ density evaluations for $N$ pixels, a pass to refit the $2K$ Gaussians, and one minimum cut on a graph with $N$ nodes and about $4N$ neighbour pairs (8-connected). The cut dominates. Its cost depends on the max-flow algorithm; Graph Cuts compares them, and OpenCV uses its own GCGraph class. Because only the t-links change between iterations, the graph’s n-links are computed once per call.

As a point of reference, Tang et al. (2013) report mean running times of 1.45–2.48 seconds per image for their histogram-based GrabCut implementation on the GrabCut dataset, at full image resolution, against 576 seconds for the dual decomposition method of Vicente et al., which, Tang et al. note, can find a global minimum of the histogram energy. They also note that Vicente et al. downscaled images to a maximum side of 250 pixels.

Implementation

The NumPy, SciPy and scikit-learn code (NumPy 2.3.5, SciPy 1.16.3, scikit-learn 1.7.2) implements GrabCut’s loop on synthetic $96 \times 96$ RGB images with known ground truth. The object is an orange ellipse with a bar, carrying a grey patch, on a background of blue above, green below and two grey discs: the grey colour belongs to both foreground and background, so the colour distributions of the two overlap. Image B replaces the green ground with brown, closer to the object’s orange. Image C adds a purple disc that lies inside the rectangle but is not part of the object; purple occurs nowhere outside the rectangle. Each channel carries Gaussian noise of standard deviation 14.

The structure follows OpenCV 4.14.0: k-means initialization with $K = 5$ , full covariances, 8-connected contrast weights with $\gamma = 50$ and the image’s own $\beta$ , definite background outside the rectangle and $\lambda = 9\gamma$ for brushed pixels. The cut uses scipy.sparse.csgraph.maximum_flow, which requires integer capacities, so costs are multiplied by 1,000 and rounded. The data term is an open modelling choice, since OpenCV departs from the hard-assignment energy, so the code runs both: hard (each pixel’s cost is its best component’s, components chosen with their weights) and mixture (OpenCV’s negative log mixture density, components chosen without weights). It also runs $\gamma = 0$ , without smoothness. The loop stops when no label changes, or after 10 iterations. Accuracy is the foreground intersection over union (IoU) and the error rate inside the rectangle, misclassified pixels divided by the rectangle’s area, as Tang et al. define it. The last part simulates a user: it places a brush of radius 3 at the error pixel farthest from the edge of the largest error region, close to the click simulation of Xu et al. (2016), which places a click at the mislabelled pixel farthest from the boundaries of the current selection and the image. The whole script runs in about six seconds.

import numpy as np
from scipy.sparse import csr_array
from scipy.sparse.csgraph import maximum_flow, breadth_first_order
from scipy.ndimage import distance_transform_edt, label as cc_label
from sklearn.cluster import KMeans

K, GAMMA, SCALE = 5, 50.0, 1000            # components per GMM, smoothness weight, integer scaling for SciPy
H = W = 96
BOX = (14, 14, 82, 82)                     # y0, x0, y1, x1 (exclusive): the user's rectangle

def make_image(seed, bottom="green", purple=False):
    """Orange object with a grey patch; background of blue, green (or brown) and the same grey;
    optionally a purple disc that occurs only inside the box."""
    rng = np.random.default_rng(seed)
    yy, xx = np.mgrid[0:H, 0:W]
    fg = (((yy - 50) / 26.0)**2 + ((xx - 46) / 20.0)**2 <= 1) | ((abs(yy - 30) <= 6) & (abs(xx - 60) <= 14))
    means = {"blue": (70, 110, 190), "green": (80, 150, 70), "grey": (128, 128, 128), "orange": (220, 130, 40), "brown": (170, 115, 70), "purple": (150, 60, 160)}
    cls = np.where(yy < 48, "blue", bottom).astype(object)
    cls[((yy - 70)**2 + (xx - 78)**2 <= 12**2) | ((yy - 22)**2 + (xx - 24)**2 <= 9**2)] = "grey"  # grey in background
    if purple:
        cls[(yy - 74)**2 + (xx - 24)**2 <= 6**2] = "purple"
    cls[fg] = "orange"
    cls[fg & ((yy - 58)**2 + (xx - 40)**2 <= 10**2)] = "grey"                                   # grey inside object
    img = np.stack([np.array([means[c] for c in row]) for row in cls]).astype(float)
    img += rng.normal(0, 14, img.shape)
    return np.clip(img, 0, 255), fg

def neighbours(img):
    """8-connected pairs with OpenCV-style contrast weights gamma*exp(-beta*|dz|^2)/dist."""
    idx = np.arange(H * W).reshape(H, W)
    shifts = [(0, 1, 1.0), (1, 0, 1.0), (1, 1, np.sqrt(2)), (1, -1, np.sqrt(2))]
    pairs = []
    for dy, dx, dist in shifts:
        ys, ye = 0, H - dy
        xs, xe = max(0, -dx), W - max(0, dx)
        a = idx[ys:ye, xs:xe]; b = idx[ys + dy:ye + dy, xs + dx:xe + dx]
        d2 = ((img[ys:ye, xs:xe] - img[ys + dy:ye + dy, xs + dx:xe + dx])**2).sum(-1)
        pairs.append((a.ravel(), b.ravel(), d2.ravel(), dist))
    beta = 1.0 / (2 * np.concatenate([p[2] for p in pairs]).mean())
    return [(a, b, np.exp(-beta * d2) / dist) for a, b, d2, dist in pairs]

class GMM:
    def fit(self, X, comp):
        self.pi, self.mu, self.S = [], [], []
        for k in range(K):
            Xk = X[comp == k]
            if len(Xk) < 2:
                continue
            S = np.cov(Xk.T, bias=True)
            if np.linalg.det(S) <= 1e-6:
                S += 0.01 * np.eye(3)          # OpenCV's fix for a singular covariance
            self.pi.append(len(Xk) / len(X)); self.mu.append(Xk.mean(0)); self.S.append(S)
        return self
    def comp_costs(self, X):
        """-log(pi_k N_k(x)) up to the shared constant, for every component: shape (n, K')."""
        out = []
        for pi, mu, S in zip(self.pi, self.mu, self.S):
            d = X - mu
            m = np.einsum("ni,ij,nj->n", d, np.linalg.inv(S), d)
            out.append(-np.log(pi) + 0.5 * np.log(np.linalg.det(S)) + 0.5 * m)
        return np.stack(out, 1)
    def assign(self, X, weighted):
        c = self.comp_costs(X)
        if not weighted:                       # OpenCV picks the component by unweighted density
            c = c + np.log(np.array(self.pi))
        return np.argmin(c, 1)
    def cost(self, X, variant):
        c = self.comp_costs(X)
        if variant == "hard":                  # cost of the best component
            return c.min(1)
        m = (-c).max(1, keepdims=True)         # mixture: -log sum_k pi_k N_k
        return -(m[:, 0] + np.log(np.exp(-c - m).sum(1)))

def min_cut(D_fg, D_bg, nb, gamma, hard_fg, hard_bg):
    """Label 1 = foreground (source side). D_fg is the cost of labelling a pixel foreground."""
    n = H * W; s, t = n, n + 1
    lam = 9 * gamma if gamma > 0 else 1e4
    D_fg = np.where(hard_bg, lam, np.where(hard_fg, 0, D_fg))
    D_bg = np.where(hard_fg, lam, np.where(hard_bg, 0, D_bg))
    low = np.minimum(D_fg, D_bg); D_fg, D_bg = D_fg - low, D_bg - low
    rows = [np.full(n, s), np.arange(n)]; cols = [np.arange(n), np.full(n, t)]
    caps = [D_bg, D_fg]                        # s->p cut if p is background; p->t cut if p is foreground
    for a, b, w in nb:
        rows += [a, b]; cols += [b, a]; caps += [gamma * w, gamma * w]
    cap = np.rint(np.concatenate(caps) * SCALE).astype(np.int32)
    G = csr_array((cap, (np.concatenate(rows), np.concatenate(cols))), shape=(n + 2, n + 2))
    res = maximum_flow(G, s, t)
    R = G - res.flow; R.data[R.data < 0] = 0; R.eliminate_zeros()
    reach = breadth_first_order(R, s, return_predecessors=False)
    L = np.zeros(n + 2, bool); L[reach] = True
    return L[:n]

def energy(X, L, fgm, bgm, nb, gamma):
    data = np.where(L, fgm.cost(X, "hard"), bgm.cost(X, "hard")).sum()
    smooth = sum((gamma * w * (L[a] != L[b])).sum() for a, b, w in nb)
    return data + smooth

def grabcut(img, gt, variant, gamma, iters=10, hard_fg=None, hard_bg=None, L=None, models=None, log=False):
    X = img.reshape(-1, 3)
    inbox = np.zeros((H, W), bool); inbox[BOX[0]:BOX[2], BOX[1]:BOX[3]] = True
    inbox = inbox.ravel()
    hard_bg = ~inbox if hard_bg is None else hard_bg
    hard_fg = np.zeros(H * W, bool) if hard_fg is None else hard_fg
    nb = neighbours(img)
    if L is None:                              # initialization from the box, k-means as in OpenCV
        L = inbox.copy()
        km = lambda Y: KMeans(K, init="k-means++", n_init=1, max_iter=10, random_state=0).fit_predict(Y)
        fgm = GMM().fit(X[L], km(X[L])); bgm = GMM().fit(X[~L], km(X[~L]))
    else:
        fgm, bgm = models
    history = []
    for it in range(iters):
        weighted = variant == "hard"
        cf = fgm.assign(X[L], weighted); cb = bgm.assign(X[~L], weighted)       # step 1
        fgm = GMM().fit(X[L], cf); bgm = GMM().fit(X[~L], cb)                  # step 2
        L_new = min_cut(fgm.cost(X, variant), bgm.cost(X, variant), nb, gamma, hard_fg, hard_bg)  # step 3
        changed = int((L_new != L).sum()); L = L_new
        history.append((it + 1, iou(L, gt), err_rate(L, gt), energy(X, L, fgm, bgm, nb, gamma), changed))
        if changed == 0:
            break
    return L, (fgm, bgm), history

def iou(L, gt):
    g = gt.ravel(); return (L & g).sum() / (L | g).sum()

def err_rate(L, gt):
    box = np.zeros((H, W), bool); box[BOX[0]:BOX[2], BOX[1]:BOX[3]] = True
    return (L != gt.ravel())[box.ravel()].mean()

def edit(L, gt, hard_fg, hard_bg):
    """Simulated user: brush (radius 3) at the error pixel farthest from the edge of the largest error region."""
    err = (L != gt.ravel()).reshape(H, W)
    if not err.any():
        return hard_fg, hard_bg, None, None
    lab, n = cc_label(err)
    big = lab == (np.argmax(np.bincount(lab.ravel())[1:]) + 1)
    y, x = np.unravel_index(np.argmax(distance_transform_edt(big)), (H, W))
    yy, xx = np.mgrid[0:H, 0:W]
    brush = ((((yy - y)**2 + (xx - x)**2) <= 9) & (gt == gt[y, x])).ravel()
    if gt[y, x]:
        hard_fg = hard_fg | brush
    else:
        hard_bg = hard_bg | brush
    return hard_fg, hard_bg, ("fg" if gt[y, x] else "bg"), (int(y), int(x))

# 1. Images A (green ground), B (brown ground), C (A plus a purple disc inside the box), seed 0:
#    the iterations of the hard-assignment variant.
IMAGES = [("A", "green", False), ("B", "brown", False), ("C", "green", True)]
for name, bottom, purple in IMAGES:
    img, gt = make_image(0, bottom, purple)
    L, models, hist = grabcut(img, gt, "hard", GAMMA)
    print(f"image {name}: {H}x{W}, object {gt.sum()} px, box {(BOX[2]-BOX[0])*(BOX[3]-BOX[1])} px")
    print("iter  IoU    box error  energy      changed px")
    for it, j, e, E, ch in hist:
        print(f"{it:4d}  {j:.3f}  {100*e:6.2f}%   {E:10.1f}  {ch:6d}")
    yy, xx = np.mgrid[0:H, 0:W]
    grey_bg = (((yy - 70)**2 + (xx - 78)**2 <= 144) | ((yy - 22)**2 + (xx - 24)**2 <= 81)) & ~gt
    grey_bg[:BOX[0]] = grey_bg[BOX[2]:] = False; grey_bg[:, :BOX[1]] = grey_bg[:, BOX[3]:] = False
    L0 = grabcut(img, gt, "hard", 0.0)[0].reshape(H, W)
    print(f"gamma=0: {int((L0 != gt).sum())} errors; background grey inside the box labelled foreground: "
          f"{int((L0 & grey_bg).sum())} of {int(grey_bg.sum())} px")

# 2. Five noise seeds, both data terms, with and without smoothness.
summary, rise = {}, -np.inf
for name, bottom, purple in IMAGES:
    for seed in range(5):
        img, gt = make_image(seed, bottom, purple)
        for variant in ["hard", "mixture"]:
            for gamma in [GAMMA, 0.0]:
                L, models, hist = grabcut(img, gt, variant, gamma)
                summary.setdefault((name, variant, gamma), []).append((hist[0][1], hist[-1][1], len(hist)))
                if variant == "hard" and len(hist) > 1:
                    rise = max(rise, np.diff([h[3] for h in hist]).max())
print("\nimage  variant  gamma  IoU first cut  IoU final     mean iterations  (seeds 0-4)")
for (name, variant, gamma), v in summary.items():
    f, l, n = np.array(v).T
    print(f"{name:>5}  {variant:8s} {gamma:4.0f}   {f.min():.3f}-{f.max():.3f}    {l.min():.3f}-{l.max():.3f}   {n.mean():5.1f}")
print(f"largest energy increase between iterations (hard variant, all runs): {rise:.1f}")

# 3. User editing on image C, seed 0: two brush strokes, each followed by re-running the loop.
print("\nediting, image C, seed 0, hard variant")
img, gt = make_image(0, "green", True)
inbox = np.zeros((H, W), bool); inbox[BOX[0]:BOX[2], BOX[1]:BOX[3]] = True
hard_fg, hard_bg = np.zeros(H * W, bool), ~inbox.ravel()
L, models, hist = grabcut(img, gt, "hard", GAMMA)
print(f"start: IoU {iou(L, gt):.3f}")
for k in range(2):
    hard_fg, hard_bg, kind, where = edit(L, gt, hard_fg, hard_bg)
    if kind is None:
        print("no errors left to correct"); break
    L, models, hist = grabcut(img, gt, "hard", GAMMA, hard_fg=hard_fg, hard_bg=hard_bg, L=L, models=models)
    print(f"edit {k+1}: {kind} brush at {where} -> IoU {iou(L, gt):.3f} after {len(hist)} iterations")

Output:

image A: 96x96, object 1846 px, box 4624 px
iter  IoU    box error  energy      changed px
   1  1.000    0.00%      97191.5    2778
   2  1.000    0.00%      95445.9       0
gamma=0: 626 errors; background grey inside the box labelled foreground: 549 of 553 px
image B: 96x96, object 1846 px, box 4624 px
iter  IoU    box error  energy      changed px
   1  1.000    0.00%     100477.2    2778
   2  1.000    0.00%      98816.7       0
gamma=0: 609 errors; background grey inside the box labelled foreground: 548 of 553 px
image C: 96x96, object 1846 px, box 4624 px
iter  IoU    box error  energy      changed px
   1  0.942    2.44%      97472.2    2665
   2  0.942    2.44%      95737.8       0
gamma=0: 714 errors; background grey inside the box labelled foreground: 551 of 553 px

image  variant  gamma  IoU first cut  IoU final     mean iterations  (seeds 0-4)
    A  hard       50   1.000-1.000    1.000-1.000     2.0
    A  hard        0   0.666-0.713    0.740-0.769     8.0
    A  mixture    50   1.000-1.000    1.000-1.000     2.0
    A  mixture     0   0.738-0.759    0.765-0.770     7.8
    B  hard       50   0.997-1.000    0.997-1.000     2.0
    B  hard        0   0.649-0.685    0.738-0.756     7.0
    B  mixture    50   0.997-1.000    0.997-1.000     2.0
    B  mixture     0   0.722-0.742    0.749-0.756     9.6
    C  hard       50   0.942-0.942    0.942-0.942     2.0
    C  hard        0   0.655-0.688    0.721-0.735     7.0
    C  mixture    50   0.942-0.942    0.942-0.942     2.0
    C  mixture     0   0.717-0.727    0.730-0.737     6.4
largest energy increase between iterations (hard variant, all runs): -0.9

editing, image C, seed 0, hard variant
start: IoU 0.942
edit 1: bg brush at (74, 24) -> IoU 1.000 after 2 iterations
no errors left to correct

With $\gamma = 50$ , the first cut from the rectangle already segmented images A and B correctly or almost so, and the second iteration changed no label: the loop stopped after two rounds in every run. The energy still fell between the two rounds, because refitting the models to the clean labelling lowered the data term, and over all runs of the hard variant it never rose, as the coordinate-descent argument requires. Here the iterations had nothing to correct. In our reading, the reason is that blue, green and brown also fill the background outside the rectangle, so the initial background model already explains them better than the contaminated foreground model does, and the one colour both models contain, grey, is settled by the smoothness term (next paragraph). We expected the first cut to take in background pixels and the iterations to remove them; on these images that did not happen. In images where it does, Tang et al.’s observation that the result depends on the initial rectangle applies.

The grey colour shows what the smoothness term does with overlapping distributions. With $\gamma = 0$ each pixel is classified by colour alone, and nearly all the background grey inside the rectangle went to the foreground. The background discs lie mostly inside the rectangle, so the initial foreground model contains more grey than the background model does. The iterations then helped, raising IoU from 0.65–0.76 at the first cut to 0.72–0.77, but could not undo the colour ambiguity. With $\gamma = 50$ the same pixels were decided together with the regions around them, and in images A and C none of them was wrong (IoU 1.000 for A, and for C an error made up entirely of the purple disc, below).

Image C is the failure the loop cannot repair. Purple occurs only inside the rectangle, so the background model has no component near it, while k-means gives the foreground model one. The disc, of radius 6 and about 113 pixels, stayed foreground in every run with $\gamma = 50$ : the error of 2.44% is 113 of the rectangle’s 4,624 pixels, and an IoU of 0.942 is $1846 / (1846 + 113)$ . One background stroke on the disc fixed it: the stroke’s pixels joined the background set, the refitted background model gained a purple component, and the rest of the disc moved to the background on the next cut. That is the second role of editing described above, acting through the models rather than through the constraint alone.

The two data terms gave identical results at $\gamma = 50$ and slightly different ones at $\gamma = 0$ , where OpenCV’s mixture cost was a little better at the first cut. In this example the choice between the hard-assignment energy and OpenCV’s version therefore did not matter once smoothing was on.

The example was planned before it was first run, and changed after its results had been seen. The first run used only image A. It found the first cut already exact at $\gamma = 50$ , and its editing step failed because there was no error left to click on. Image B was then added to test the same hypothesis on a harder image, its brown ground planned as “close to the object’s orange (200,130,60)”. The code’s orange is (220, 130, 40), so brown lies about 60 colour units from it rather than the 35 the plan expected; the code was not changed. Image B also segmented correctly at once. Rather than change the colours until iteration mattered, image C was added to test a prediction written in the plan before it ran: that a colour occurring only inside the rectangle “stays foreground through all iterations” and that one background brush removes it. The editing step was given a guard for the case with no errors and moved to image B, then, since B left no errors either, to image C. Later changes only altered what is printed: the first run’s count of the object’s grey-patch pixels labelled foreground was dropped, and ranges over seeds replaced per-seed lines; the energy check, the mean iteration count and the count of background grey pixels labelled foreground at $\gamma = 0$ were added. Algorithm, parameters and images were not changed by these.

Evaluation

The GrabCut dataset

The paper’s own experiments could not be read for this article, so the GrabCut dataset, which later papers cite to it, is described here through those papers. It contains 50 natural images with ground-truth segmentations (Wu et al., 2014). Wu et al. report two protocols in use on it:

Bounding box: the input is a rectangle, and the error rate is the number of misclassified pixels inside the box divided by the box’s area (Tang et al., 2013).
Lasso trimap: the input is a “lasso” trimap in which most pixels are already labelled and only a strip along the boundary is left for inference, and the error rate is the number of misclassified pixels divided by the number of pixels in that unknown region (Wu et al., 2014, following earlier work).

Wu et al. define the error rate once, over the region left unclassified, and list both protocols in one table, noting that the trimaps carry richer information. Since the inputs and the regions differ, in our reading numbers from one protocol cannot be compared with the other.

Under the box protocol, Tang et al. (2013) ran their own implementation of GrabCut, using colour histograms instead of mixtures as Vicente et al. had done, on 49 of the 50 images. They excluded one (the “cross” image) for comparability with Vicente et al., and tuned the smoothness weight separately for each method and bin count. GrabCut’s error rate was lowest with $16^3$ bins (7.1%) and rose as the bins got finer, to 13.59% at $256^3$ . Their globally optimized One-Cut reached 6.67% at $64^3$ bins, and Vicente et al.’s dual decomposition, as Vicente et al. reported it, 10.5% at $16^3$ . Tang et al. note that Vicente et al. reported 8.1% for GrabCut, and attribute the difference from their 7.1% to a different smoothness term and to not downscaling the images.

Wu et al. (2014, Table 1) collect box-protocol results from Lempitsky, Kohli, Rother and Sharp (2009), using the same boxes. The entries labelled GrabCut-GC give 8.9% with the initialization Wu et al. call InitFullBox and 5.9% with the one they call InitThirds. Lempitsky et al.’s GrabCut-Pinpoint, which Wu et al. describe as GrabCut combined with engineered initialization maps and an integer programme with a bounding-box prior, gives 8.2% and 3.7% with the same two initializations, and Wu et al.’s MILCut with a graph-cut step 3.6%. Their table lists lasso-protocol results separately, among them 7.9% for the GMMRF model of Blake et al. (2004) and 6.7% for Boykov and Jolly’s graph cut.

The Berkeley set

McGuinness and O’Connor built a benchmark for interactive segmentation from 100 objects in images of the Berkeley segmentation dataset, with manually labelled ground truth, scored by the Jaccard index (intersection over union). Wu et al. (2014, Table 2) list GrabCut, given a bounding box, at 77% on it, against 83–84% for their two MILCut variants and 64% for Boykov and Jolly’s graph cut given scribbles. They say the results of the other methods first appeared in McGuinness and O’Connor’s evaluation. Wu et al. used input that four graduate students gave within 10 seconds per image, and cite McGuinness and O’Connor as reporting that about 60 seconds of extra scribbles raise the other methods to about 90%. The figures above are therefore short-input figures, not each method’s best; the user study itself is described in Interactive Segmentation.

Click-based evaluation

Xu et al. (2016), who call the GrabCut and Berkeley sets benchmark datasets for interactive segmentation, used them to score click-based methods by the mean number of clicks needed to reach a target IoU. In Xu et al.’s (2016) protocol, clicks are generated automatically at the mislabelled pixel farthest from the region boundaries, and the count is capped at 20. Boykov and Jolly’s graph cut needed 11.10 clicks to reach 90% IoU on GrabCut and 14.33 on Berkeley, against 6.04 and 8.65 for Xu et al.’s network. Xu et al. note that the GrabCut set has only 50 images, mostly with distinct foreground and background colour distributions that low-level methods handle well, so their advantage was smaller there than on harder sets. GrabCut itself was not among the methods in Xu et al.’s table.

Properties and Behavior

Convergence. For the hard-assignment energy, each step minimizes over one block of variables, so the energy decreases monotonically and the labels converge to a local minimum (shown above). OpenCV’s mixture-likelihood version is not covered by this argument, though it behaved the same way in the example.
Dependence on the rectangle. The rectangle fixes what can be foreground and seeds the colour models. Tang et al. trace GrabCut’s interactivity to the local minimum this produces.
Colour separation. By Tang et al.’s analysis, the energy favours segmentations whose foreground and background colour distributions overlap little, together with a bias towards two parts of equal size.
Contrast-sensitive boundaries. The n-links are cheap across colour edges and expensive within uniform regions, so the cut follows edges; the per-image $\beta$ adapts this to the image’s overall contrast.
Efficiency under editing. Strokes change only t-links, and the models carry over between calls, so corrections are fast relative to a fresh run.

Limitations

Colour only. The models see colour, not texture or shape. An object whose colours also fill the background, or a camouflaged one, cannot be separated by the data term, and the smoothness term then decides by boundary length.
Background colours unique to the rectangle. As in image C, a background colour that occurs only inside the rectangle has no background component and stays foreground until the user marks it.
Shrinking bias. The boundary term favours short boundaries, as in all graph-cut segmentation; Graph Cuts shows thin structures disappearing as the smoothness weight grows.
Local minima. Block-coordinate descent stops at a local minimum. Tang et al. found their implementation getting stuck more often with finer colour histograms.
Fine boundaries. Border matting assumes a smooth, narrow transition; Szeliski notes its difficulty with hair and other fine detail.
Single object, binary output. GrabCut extracts one foreground region per rectangle and gives no class label.

Variants

Boykov and Jolly (2001) are the starting point: seed strokes as hard constraints and histogram colour models from the seeds, solved by one cut. GrabCut adds the rectangle interface, mixture models and iterated estimation. Szeliski also mentions Cui, Yang et al. (2008), who used colour and edge models derived from previous segmentations of similar objects to improve GrabCut’s local models.
Bounding-box priors. Lempitsky et al. (2009), as Wu et al. describe their method, pose segmentation from a box as an integer programme with a bounding-box prior, initialized from GrabCut’s colour mixtures and solved approximately by repeated “pinpointing”. Its best variant gives one of the lowest error rates on the GrabCut set in Wu et al.’s table, but Wu et al. report that it takes several minutes per image.
Global optimization. Vicente et al. (2009) minimized the histogram form of the energy by dual decomposition, which Tang et al. say can find a global minimum, at a large cost in time. Tang et al.’s (2013) One-Cut replaces the iterated estimation with a term that penalizes the $L_1$ overlap of the foreground and background histograms, optimized globally in a single cut with auxiliary nodes.
Learned unary terms. Wu et al.’s MILCut (2014) treats sweeping lines across the box as positive bags in multiple-instance learning to classify superpixels inside it, optionally followed by a graph cut with GrabCut’s smoothness term.
Deep interactive and promptable segmentation. Click-based networks (Xu et al., 2016) learn object appearance from data instead of fitting colour models per image, and promptable models such as SAM accept points or boxes as prompts. GrabCut’s box interface survives in both, and in annotation tools that seed masks from boxes (Image Annotation).