Interactive Segmentation

Interactive segmentation extracts the mask of one object that a person points at. The user gives a little input, such as a click on the object, a scribble on the background or a box around the object; the system returns a mask; the user corrects it with more input where it is wrong; and the loop repeats until the mask is good enough. The task is also called interactive object selection or interactive image segmentation, and the click-based form is the most common in recent work. Its goal is not a fully automatic answer but a good mask for little human effort, which is why it is measured in effort: the number of clicks needed to reach a target intersection over union (IoU), counted with a simulated user. The image segmentation hub lists it among the forms of segmentation.

Problem Definition

Given an image $I$ and a sequence of user interactions $a_1, a_2, \dots$, the system outputs after each interaction a binary mask $M_k$ of the object the user intends. In the click-based form each interaction is a point labelled positive (on the object) or negative (on the background); Xu et al. (2016) write the interactions as a positive click set $S_1$ and a negative click set $S_0$. The target object is defined only by the user’s intent, so the same click can mean different objects: a click on a shirt may mean the shirt or the person wearing it, the example the SAM authors use.

Three assumptions separate interactive segmentation from neighbouring tasks:

• One object at a time, without a class. The output is a mask, not a labelled segmentation of the whole scene, unlike semantic or instance segmentation.
• Corrections are allowed. Interactive segmentation aims at a valid mask after enough input, while SAM’s promptable segmentation asks for a sensible mask after every prompt, including an ambiguous single click (Kirillov et al., 2023).
• Effort is the cost. A method is better if it reaches the same quality with fewer interactions, less time or more predictable behaviour.

Input and Output

Inputs vary in how much they say and how much they cost the user.

• Seeds and scribbles. Boykov and Jolly (2001) let the user mark pixels as “object” or “background”, hard constraints that the segmentation must respect; strokes painted with a brush are the usual form. McGuinness and O’Connor (2010) built their evaluation tool around such a “scribble-driven” interface.
• A bounding box. GrabCut starts from a rectangle loosely around the object. Jang and Kim (2019) group earlier methods into box-interfaced ones, which usually aim at a one-shot result, and scribble-interfaced ones, which let the user add input several times, and note that scribble-based methods generally give more detailed masks.
• Clicks. A positive or negative click is a scribble reduced to one point. Liu et al. (2023) describe the click-based approach as the most common because of its simplicity and its established training and evaluation protocols. Other point inputs exist: DEXTR, as Liu et al. describe it, takes the four extreme points of an object (left-most, right-most, top and bottom).
• A previous mask. Several recent methods take the last prediction as an extra input, which also lets a user start from an existing, imperfect mask (Mahadevan et al., 2018; Liu et al., 2023; Chen et al., 2022).

The output is a binary mask after each round; some systems also return a probability map that is thresholded, and SAM returns three candidate masks with predicted IoUs for a single ambiguous prompt.

How a click reaches a network matters. Xu et al. (2016) turned each click set into a map of Euclidean distances to the nearest click, truncated at 255, and stacked the two maps with the RGB channels. Mahadevan et al. (2018) encoded clicks instead as Gaussians of standard deviation 10 pixels clipped to zero at 20 pixels, and found that the more localized encoding helped. FocalClick’s authors describe Gaussian maps or disks as the basic paradigm (Chen et al., 2022), and SimpleClick encodes clicks as a two-channel disk map.

Variants

• Box-based extraction, in which the box is the main input and corrections are secondary, as in GrabCut.
• Interactive mask correction. Chen et al. (2022) define this sub-task: the user starts from a flawed mask produced by another model or tool, and the system should change only what the new clicks ask for. Their DAVIS-585 benchmark supplies initial masks with IoUs between 0.75 and 0.85, simulated by corrupting the ground truth with superpixels.
• Promptable segmentation. SAM’s task, in which a prompt (points, a box, a rough mask) must yield a valid mask even when ambiguous; it is built to be composed into larger systems, such as detector boxes as prompts (Kirillov et al., 2023).
• Video and volumes. Boykov and Jolly’s formulation covers N-dimensional images; interactive segmentation of video, in which corrections on one frame propagate to others, is a setting of video object segmentation. SimpleClick was also evaluated on slices of MRI and electron-microscopy data (Liu et al., 2023).
• Annotation at scale, where an interactive model is the labelling tool of a dataset, as in SAM’s data engine and the Open Images masks described in Image Annotation.

Challenges

• Ambiguity of intent. One click is consistent with several nested objects. SAM predicts three masks per single prompt for this reason; a single-mask model must guess.
• Fine boundaries. Thin structures and detailed contours need high resolution. SAM’s authors list missed fine structures and less crisp boundaries than methods that “zoom in” among its limitations, and f-BRS and FocalClick crop around the object for this reason (Sofiiuk et al., 2020; Chen et al., 2022).
• Convergence. More clicks should never make the mask worse, but nothing in a feed-forward network guarantees this. Sofiiuk et al. (2020) found that both their DeepLabV3+ model and Jang and Kim’s network without refinement failed to reach 90% IoU on a relatively large share of images even after 100 clicks.
• Predictability. McGuinness and O’Connor’s participants preferred the method whose corrections had small, local effects over one with comparable accuracy whose changes were sometimes large and unexpected; one participant complained that adding one scribble could completely change the result of seeded region growing. Chen et al. (2022) show the deep counterpart: RITM changed parts of a mask far from the user’s clicks.
• Latency. Each click must be answered in a fraction of a second, so methods report seconds per click (SPC) or FLOPs alongside accuracy.
• Simulated users differ from real ones. Evaluation depends on an automatic clicker (below) that knows the ground truth and clicks deterministically; models trained with a similar clicker may be tuned to it, which Mahadevan et al. (2018) tested by changing the test-time sampling.

Approaches

Classical methods: seeds, energies and distances

Before deep learning, interactive segmentation was solved per image from low-level cues, with the user’s input as constraints.

• Graph cuts. Boykov and Jolly (2001) made user seeds hard constraints in a binary energy with region and boundary terms, minimized exactly by a minimum cut; a new seed changes only a few edges, so corrections are fast. Graph Cuts gives the construction. GrabCut replaced seed histograms with colour mixtures re-estimated from the current segmentation and a box as the main input.
• Random walker. Grady’s (2006) random walker labels each unlabelled pixel by the seed label that a random walk from it is most likely to reach first, which amounts to solving a linear system in the graph Laplacian with seeds as boundary conditions; scikit-image’s implementation describes it as solving a diffusion equation for each label. It is not a graph cut: it computes a probability per pixel by solving linear equations rather than a minimum cut.
• Geodesic methods. Gulshan et al. (2010), as Jang and Kim summarize their paper, proposed a shape constraint for interactive segmentation, geodesic star convexity, and used geodesic distances from the user’s scribbles to the pixels in the energy they minimize. Geodesic matting (Bai and Sapiro) is another baseline in Xu et al.’s tables. Neither paper could be read for this article.
• Region growing and cellular automata. Seeded region growing (Adams and Bischof) grows object and background regions from the seeds in order of similarity; McGuinness and O’Connor (2010) evaluated it beside graph cuts. GrowCut (Vezhnevets and Konouchine, 2005) is a cellular-automaton method that Xu et al. include as a baseline.

These methods need no training and adapt to any image, but they see only colour or intensity and edges. Xu et al. (2016) note that the GrabCut dataset’s images mostly have distinct foreground and background colour distributions, which low-level methods handle well; on harder sets the gap to learned methods was larger.

McGuinness and O’Connor’s (2010) user study is one of the few that measured classical methods with real users. Twenty volunteers extracted 100 objects with four methods, 25 objects each, with two minutes per object, while every intermediate mask was stored with its time. The best object accuracy (Jaccard index) averaged 0.93 for both interactive graph cuts and a binary-partition-tree method, 0.88 for seeded region growing and 0.85 for SIOX, a colour-classifier method, in the authors’ accepted manuscript; users still preferred the graph cut for its predictable corrections.

Deep click-based methods

Learning from simulated clicks. Xu et al. (2016) fine-tuned fully convolutional networks on images stacked with the two distance maps, refining the network’s probability map with a graph cut. Since real click sequences are expensive, they sampled clicks from the ground truth: positive clicks inside the object, kept apart from each other and from the boundary, and negative clicks by three strategies (random background pixels within a distance band around the object, pixels on other objects, and clicks spread evenly around the object’s outside boundary), about 80,000 training pairs from the 1,464 PASCAL VOC 2012 training images. The authors report that one or two clicks usually gave reasonably good results, and tested on COCO categories absent from PASCAL to show that the network generalized to unseen classes.

Refinements of the network. Liew et al.’s (2017) RIS-Net combined a global prediction with local predictions around click pairs. Li, Chen and Koltun (2018) trained a network to produce several plausible segmentations and a second network to select one, addressing the ambiguity of a few clicks. Mahadevan et al. (2018) changed the training rather than the architecture: their iterative training adds each new click where the current model’s prediction is wrong, as a user would, and optionally feeds the previous mask back as input, with clicks reset to a fresh random set with probability 0.3 so that the network still sees few-click inputs. On PASCAL VOC, iterative training cut the clicks needed to reach 85% IoU from 5.4 to 3.8, and replacing their Gaussian click encoding with distance maps raised them from 5.4 to 6.5 (Mahadevan et al., 2018).

Optimization at test time. A network does not guarantee that a clicked pixel receives the clicked label. Jang and Kim’s (2019) backpropagating refinement scheme (BRS) fixes this at inference: it minimizes a corrective energy, the squared error between the network’s output and the click labels at the clicked pixels, plus an inertial energy that keeps the interaction maps close to their initial values, by L-BFGS on the interaction maps with the network’s weights frozen. This needs repeated forward and backward passes through the whole network, 0.81 seconds per click on DAVIS on their GPU. Sofiiuk et al.‘s (2020) f-BRS optimizes instead a channel-wise scale and bias on intermediate features, so the backward pass covers only the network’s head; on Berkeley, with a ResNet-50 DeepLabV3+, it took 0.132 seconds per click against 1.117 for the authors’ own implementation of BRS on the input image (RGB-BRS), with 4.34 against 4.08 clicks to 90% IoU (Sofiiuk et al., 2020, Table 4).

Iterative training with mask guidance. RITM (Sofiiuk, Petrov and Konushin, 2022) returned to feed-forward prediction. Its paper is not on a site this article can use and its official repository could not be found (requests returned “not found” in November 2026), so it is described here through later work: FocalClick’s authors report that it concatenates the previous mask with the image and click maps, trains with iterative click simulation following Mahadevan et al., uses the normalized focal loss it introduced, and was trained on a combination of COCO and LVIS; SimpleClick’s code states that it was developed from RITM’s. The SAM authors found RITM the strongest single-point baseline on their 23 datasets.

Efficiency and local refinement. FocalClick (Chen et al., 2022) splits each prediction into a coarse segmentation on a crop around the current object (Target Crop) and a refinement on a small crop around the region the new click changes (Focus Crop), then merges the new prediction only inside the changed region that contains the click (Progressive Merge), so that correct parts of an existing mask survive. Its lightest model needs 0.60 GFLOPs per click (0.43 for the coarse step on a 128 × 128 input and 0.17 for the refinement), about 15 times fewer than the lightest RITM model by its authors’ count.

Plain transformers. SimpleClick (Liu et al., 2023) uses a plain vision transformer pretrained as a masked autoencoder, adds a second patch embedding for the click maps and previous mask, and decodes with a simple feature pyramid and a light MLP head. Trained on SBD, its ViT-H model needed 4.15 clicks on average to reach 90% IoU on the SBD validation set, which the authors describe as 21.8% better than the previous best.

Promptable segmentation

SAM recast the task in the foundation-model pattern: a promptable model trained on 1.1 billion masks, with the image encoded once by a heavy encoder and each prompt decoded by a light decoder. Its training simulates an interactive session for each mask, with a first prompt followed by points sampled uniformly from the error region of the previous prediction and the previous mask logits fed back. Its authors adapted this from interactive segmentation, citing Xu et al. and Mahadevan et al., and sample prompts over 11 rounds per mask following RITM and others (Kirillov et al., 2023). SAM is evaluated differently from click-based segmenters (next section), and its authors expect dedicated interactive methods to do better when many points are given, since SAM is built for breadth rather than very high IoU. The SAM article covers its architecture, training and variants, including SAM 2 for video.

Datasets and Benchmarks

Click-based methods are trained on SBD or on COCO with LVIS and tested on a common set of small benchmarks, most of them subsets of datasets built for other tasks. The counts below are as the cited sources give them; where they disagree, both are given.

• GrabCut. 50 images, one object each, which later papers cite to the GrabCut paper (Xu et al., 2016; Jang & Kim, 2019); Li, Chen and Koltun (2018) report 49. In SimpleClick’s data loader, pixels with the intermediate grey value 128 in the ground-truth files are marked “ignore”, so they count neither in the IoU nor as places to click. The GrabCut article covers the box-based protocols on this set.
• Berkeley. McGuinness and O’Connor (2010) selected 100 objects from 96 of the 300 images of the Berkeley segmentation dataset (BSDS), chosen for unambiguous objects and a range of difficulties such as texture, camouflage and lighting, and drew the ground truth entirely by hand, marking the border with a graphics tablet and filling the interior, deciding each border pixel by whether it appeared to contain some of the object’s colour.
• DAVIS. Li, Chen and Koltun (2018) sampled 10% of the annotated frames of the 50 DAVIS videos at random, giving 345 images with high-quality masks; Jang and Kim (2019) and later work use the same frames. Sofiiuk et al. (2020) merge the instance masks of each frame into one mask, and Chen et al. (2022) point out that this follows DAVIS 2016’s single-object annotation, so the set lacks small, occluded and non-salient objects; their DAVIS-585 takes objects separately from DAVIS 2017 validation videos.
• SBD. The Semantic Boundaries Dataset’s instance masks on PASCAL VOC images: 8,498 training images, and a validation set with 6,671 instance masks (Jang & Kim, 2019; Sofiiuk et al., 2020). The number of validation images is given as 2,820 (Li, Chen & Koltun, 2018; Jang & Kim, 2019), 2,802 (Chen et al., 2022) and 2,857 (Liu et al., 2023). Chen et al. note that its polygon annotations are of low quality.
• PASCAL VOC. The 1,449 validation images of VOC 2012, used by Xu et al. (2016) at 85% IoU; Liu et al. (2023) count 3,427 instances in their paper and 3,417 in their repository’s README.
• COCO subsets. Xu et al. (2016) sampled 10 images from each COCO category and reported the 20 categories shared with PASCAL (“seen”) separately from the other 60 (“unseen”), at 85% IoU. Li, Chen and Koltun (2018) sampled 10 images per category and one random instance in each, 800 instances. SimpleClick’s evaluation script includes a “COCO_MVal” set of 800 images with 800 instances; its README does not say how it was drawn, so whether it is Li et al.’s sample could not be confirmed.
• Medical sets. SimpleClick added BraTS MRI slices, OAI-ZIB knee MRI slices and ssTEM electron-microscopy images as out-of-domain tests. SAM’s evaluation uses a suite of 23 datasets across domains, with point prompts only.

Training sets moved from PASCAL VOC (Xu et al., 2016) to SBD (Li, Chen & Koltun, 2018; Jang & Kim, 2019) and then to the combination of COCO and LVIS used by RITM, FocalClick and SimpleClick. Results from models trained on different data are not comparable even on the same test set.

Reported results

Mean number of clicks to 90% IoU, with clicks simulated as each paper describes (lower is better). The figures are from the tables of the papers named; RITM’s are as FocalClick and SimpleClick report them, identically.

Method (training data, backbone)	GrabCut	Berkeley	SBD	DAVIS	Source
Random walker	12.30	14.02	–	–	Xu et al. (2016), Table 1
Geodesic star convexity	8.38	12.57	–	–	Xu et al. (2016), Table 1
Xu et al., FCN + graph cut (VOC)	6.04	8.65	–	–	Xu et al. (2016), Table 1
BRS (SBD, DenseNet)	3.60	5.08	9.78	8.24	Jang & Kim (2019), Table 1
f-BRS-B (SBD, ResNet-101)	2.72	4.57	7.73	7.41	Sofiiuk et al. (2020), Table 3
RITM (COCO+LVIS, HRNet-32)	1.56	2.10	5.71	5.34	Chen et al. (2022); Liu et al. (2023)
FocalClick (COCO+LVIS, SegFormer-B3-S2)	1.50	1.92	5.59	4.90	Chen et al. (2022), Table 2
SimpleClick (SBD, ViT-H)	1.44	2.09	4.15	5.34	Liu et al. (2023), Table 2
SimpleClick (COCO+LVIS, ViT-H)	1.50	1.75	4.70	4.78	Liu et al. (2023), Table 2

Three cautions apply. First, Jang and Kim state that the baseline scores in their table come from Li, Chen and Koltun (2018) and Liew et al. (2017), and Sofiiuk et al.’s baseline rows repeat the same numbers with two exceptions (the graph cut on Berkeley, 14.22 against Xu et al.‘s 14.33, and Latent Diversity on DAVIS at 85%, 5.05 against Li, Chen and Koltun’s 5.95); Li, Chen and Koltun sampled their clicks at random (below), while the deep methods in the same tables used deterministic clicks; the figures for the same baseline also differ between papers (the graph cut on GrabCut at 90% IoU is 11.10 in Xu et al. and 10.00 in Li, Chen and Koltun). Second, the click cap of 20 means a method that fails on a few objects is charged 20 for each, however far it was from the target. Third, the papers’ training data and resolution differ, as the table’s first column shows. On SAM’s 23 datasets with one central point, SAM’s top-ranked mask had a higher mIoU than RITM’s on 16 datasets, and with the best of its three masks chosen against the ground truth on all 23; as more points were added (up to 9), the gap to RITM, FocalClick and SimpleClick narrowed (Kirillov et al., 2023).

Evaluation Metrics

Simulated users

Measuring an interactive method with people is slow and hard to repeat, so the field evaluates with a simulated user, a “robot user” in the words of Liew et al. (2017), who credit the idea to Kohli et al. and note its use by Gulshan et al. (2010). The clicker knows the ground truth and places each new click where the current mask is most wrong. The rule has been stated in several ways:

• Xu et al. (2016): a seed at the mislabelled pixel farthest from the boundary of the current selection and the image boundaries, on the assumption that a user clicks in the middle of the region of greatest error.
• Liew et al. (2017): a first positive click at the centre of the object, then clicks in the middle of the largest mislabelled regions.
• Li, Chen and Koltun (2018): a random first click inside the object, drawn with probability proportional to its geodesic distance from the object boundary, then random clicks from the same kind of distribution over the misclassified pixels.
• Mahadevan et al. (2018): group the mislabelled pixels into connected clusters, take the largest by pixel count, and click at its pixel farthest from the cluster boundary and from earlier clicks in it.
• Jang and Kim (2019): choose the click type by the dominant error, a negative click if there are more false-positive than false-negative pixels and a positive one otherwise, then click far from the boundaries of those false predictions. They cite Li, Chen and Koltun and Xu et al. for this rule, although Li, Chen and Koltun’s clicks were random.
• SimpleClick’s code (isegm/inference/clicker.py, developed from RITM): compute the Euclidean distance transform of the false-negative and of the false-positive region, with the mask zero-padded so that the image border counts as a boundary and with clicked pixels excluded; click at the deepest point of whichever region is deeper (positive if the false-negative region is deeper). The first click, made against an empty prediction, therefore falls at the object’s interior point farthest from its boundary. SAM’s appendix describes the same deterministic placement, the first point farthest from the object boundary and each later one farthest from the boundary of the error region, as standard practice (Kirillov et al., 2023).

In the code’s form, with $F^-_k$ the false-negative and $F^+_k$ the false-positive pixels after $k$ clicks and $d(p, A)$ the distance from pixel $p$ to the nearest pixel outside region $A$ (or outside the image),

$$p_{k+1} = \arg\max_{p \,\in\, F^-_k \cup F^+_k} d\big(p, F(p)\big), \qquad F(p) = \begin{cases} F^-_k & p \in F^-_k \\ F^+_k & p \in F^+_k, \end{cases}$$

and the click is positive if $p_{k+1} \in F^-_k$. Xu et al.’s wording measures the distance from the boundary of the current selection, not of the error region; read literally, the two differ wherever an error region is bounded by the object’s true edge rather than by the selection, so the code is, in our reading, one way of implementing their stated aim of clicking in the middle of the region of greatest error.

Number of clicks (NoC)

Xu et al. (2016) recorded, for each object, how many clicks were needed to reach a given IoU, capped at 20 clicks and set to 20 when not reached, and averaged over the objects, with a target of 90% on GrabCut and Berkeley and 85% on PASCAL VOC and COCO. Jang and Kim (2019) called it the NoC metric and reported NoC at 85% and 90%; Sofiiuk et al. (2020) wrote NoC@85 and NoC@90, the names in use since. For objects $o$ with IoU $\mathrm{IoU}_k(o)$ after $k$ clicks and a cap $K = 20$,

$$\mathrm{NoC}@\tau = \frac{1}{|\mathcal{O}|} \sum_{o \in \mathcal{O}} \min\Big( \{ k \le K : \mathrm{IoU}_k(o) \ge \tau \} \cup \{K\} \Big).$$

SimpleClick’s compute_noc_metric implements exactly this and also counts the objects whose value equals the cap, which mixes failures with objects that reached the target on the 20th click. In its evaluation loop the clicking stops once the IoU reaches the highest target, and the probability map is thresholded at 0.49.

Related measures fill the gaps NoC leaves:

• Number of failures. Chen et al. (2022) report NoF, the number of objects not reaching the target within 20 clicks.
• NoC100. Sofiiuk et al. (2020) argue that with a cap of 20 an object needing 20 clicks and one needing 2,000 get the same penalty, and report NoC with a cap of 100. On Berkeley, two objects were still below 90% IoU after 100 clicks for BRS and none for f-BRS-B; on DAVIS, 51 and 50.
• mIoU after k clicks and its curve. Xu et al. (2016) plotted mean IoU against the number of clicks; Jang and Kim (2019) report the normalized area under that curve; SimpleClick reports mIoU@k.
• Dataset-level counting. Mahadevan et al. (2018) also counted clicks by giving every object the same number of clicks and increasing it until the dataset’s mean IoU reached the target, which gives different numbers from per-object counting (on GrabCut at 90%, 5.7 against 5.6 for their method, and more than 20 against 11.1 for the graph cut).
• Point-prompt mIoU. SAM’s evaluation reports mIoU after 1, 2, 3, 5 and 9 points, averaged per dataset and then across datasets, because many of its uses involve one or a few prompts; its authors note that this differs from the standard protocol of counting points up to 20 (Kirillov et al., 2023, appendix).
• Time and human studies. McGuinness and O’Connor (2010) measured accuracy against elapsed time with real users and a fuzzy boundary-accuracy measure; Li, Chen and Koltun (2018) ran a user study with five participants; SAM’s authors had annotators rate masks from 1 to 10.

Example: simulating clicks and counting them

The script below (NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2) applies the protocol to three classical segmenters on synthetic $128 \times 128$ grey images with known masks: a disk, a low-contrast ellipse, a disk with a bar 3 pixels wide, a square on a background that brightens from left to right (“ramp”), an object with a bright and a dark half (“two-tone”) and a ring, each with Gaussian noise and two noise seeds; and a horse silhouette from scikit-image’s bundled horse image, filled with the bundled brick texture on the bundled grass texture, so that the mask is known. The segmenters are:

• Region growing: seeded region growing with an object and a background region competing for pixels in order of their distance to each region’s mean, as in Region Growing.
• Graph cut: a Boykov–Jolly-style energy solved exactly with scipy.sparse.csgraph.maximum_flow, which needs integer capacities (costs are multiplied by 1,000 and rounded). The data term is the negative log-likelihood under a Gaussian fitted to each label’s seed pixels, a simplification of Boykov and Jolly’s histograms; the boundary term uses 8-connected weights $\exp(-\Delta I^2 / 2\sigma^2)/\mathrm{dist}$ with $\sigma$ estimated as the image noise, the role Boykov and Jolly give it. The smoothness weight $\lambda$ multiplies the boundary term, as in Graph Cuts; Boykov and Jolly put their $\lambda$ on the region term instead, so ours corresponds to $1/\lambda$ in their notation. It has no default in the sources, so two values are run: 1 (“GC”) and 10 (“GC10”).
• Random walker: skimage.segmentation.random_walker with its default $\beta = 130$ and the direct solver.

Each click becomes a disk of radius 5, following Xu et al. (2016), who enlarged clicks to dots of that radius for classical methods, clipped to the clicked pixel’s ground-truth label (a careful user paints inside the region). The one-pixel image border is a background seed throughout, so that the classical methods have both labels from the first click; this is our choice, and it favours them, since no object touches the border. The click rule is printed under three of the forms above: SimpleClick’s code (“max distance”), Mahadevan et al.’s largest cluster, and Jang and Kim’s dominant count. The whole script runs in about 40 seconds on a laptop CPU.

import heapq
import numpy as np
from scipy import ndimage as ndi
from scipy.sparse import csr_array
from scipy.sparse.csgraph import maximum_flow, breadth_first_order
from skimage import data
from skimage.transform import resize
from skimage.segmentation import random_walker

N, R, MAX_CLICKS = 128, 5, 20       # image size, click disk radius (Xu et al.), click budget
SCALE = 1000                        # integer scaling for SciPy max-flow
yy, xx = np.mgrid[:N, :N]
BORDER = np.zeros((N, N), bool); BORDER[[0, -1], :] = BORDER[:, [0, -1]] = True

def make_image(kind, seed):
    """Gray image in [0, 1] and its ground-truth mask; objects never touch the border."""
    rng = np.random.default_rng(seed)
    r, noise = np.hypot(yy - 64, xx - 64), 0.08
    if kind == "disk":
        gt = r <= 28; img = np.where(gt, 0.65, 0.35)
    elif kind == "low contrast":
        gt = ((yy - 64) / 30) ** 2 + ((xx - 64) / 22) ** 2 <= 1; img = np.where(gt, 0.55, 0.45)
    elif kind == "thin bar":
        gt = (r <= 22) | ((abs(yy - 64) <= 1) & (xx >= 64) & (xx <= 116)); img = np.where(gt, 0.62, 0.38)
    elif kind == "ramp":
        gt = (abs(yy - 64) <= 20) & (abs(xx - 64) <= 20); img = np.where(gt, 0.55, 0.2 + 0.55 * xx / (N - 1)); noise = 0.05
    elif kind == "two-tone":
        gt = r <= 30; img = np.where(gt, np.where(xx < 64, 0.70, 0.45), 0.35)
    elif kind == "ring":
        gt = (r <= 30) & (r > 12); img = np.where(gt, 0.65, 0.35)
    elif kind == "horse on grass":   # bundled skimage images: horse silhouette, brick and grass textures
        h = resize((~data.horse()).astype(float), (92, 112), order=1) > 0.5
        gt = np.zeros((N, N), bool); gt[18:110, 8:120] = h
        img = np.where(gt, data.brick()[:N, :N], data.grass()[:N, :N]) / 255.0; noise = 0.0
    img = img + rng.normal(0, noise, img.shape)
    return np.clip(img, 0, 1), gt

# ---- three classical click-driven segmenters: seeds in, mask out ----
def region_growing(img, fg, bg):
    """Seeded region growing with two competing labels (Adams-Bischof style), 4-connected."""
    lab = np.zeros(img.shape, np.int8); lab[fg] = 1; lab[bg] = 2
    tot = {1: img[fg].sum(), 2: img[bg].sum()}; cnt = {1: fg.sum(), 2: bg.sum()}
    heap = []
    def push(y, x, l):
        for y2, x2 in ((y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)):
            if 0 <= y2 < N and 0 <= x2 < N and lab[y2, x2] == 0:
                heapq.heappush(heap, (abs(img[y2, x2] - tot[l] / cnt[l]), y2, x2, l))
    for y, x in zip(*np.nonzero(lab)):
        push(y, x, lab[y, x])
    while heap:
        _, y, x, l = heapq.heappop(heap)
        if lab[y, x]:
            continue
        lab[y, x] = l; tot[l] += img[y, x]; cnt[l] += 1
        push(y, x, l)
    return lab == 1

def nlinks(img):
    """8-connected pairs with Boykov-Jolly boundary weights exp(-dI^2 / 2 sigma^2) / dist."""
    d = np.diff(img, axis=1).ravel()
    sigma = max(1.4826 * np.median(np.abs(d - np.median(d))) / np.sqrt(2), 1e-3)  # noise estimate
    idx = np.arange(N * N).reshape(N, N); pairs = []
    for dy, dx, dist in [(0, 1, 1.0), (1, 0, 1.0), (1, 1, np.sqrt(2)), (1, -1, np.sqrt(2))]:
        xs, xe = max(0, -dx), N - max(0, dx)
        a, b = idx[0:N - dy, xs:xe], idx[dy:N, xs + dx:xe + dx]
        dI = img[0:N - dy, xs:xe] - img[dy:N, xs + dx:xe + dx]
        pairs.append((a.ravel(), b.ravel(), np.exp(-dI.ravel() ** 2 / (2 * sigma ** 2)) / dist))
    return pairs

def graph_cut(img, fg, bg, nb, lam):
    """Exact min cut: Gaussian seed models as data term, seeds as hard constraints, smoothness weight lam."""
    x = img.ravel()
    def cost(seeds):                    # -log N(x; mean, var) of the seed pixels, capped at 50
        m, v = img[seeds].mean(), img[seeds].var() + 1e-4
        return np.minimum(0.5 * np.log(2 * np.pi * v) + (x - m) ** 2 / (2 * v), 50.0)
    D_fg, D_bg = cost(fg), cost(bg)
    K = 1e3                             # hard constraint: larger than any pixel's n-links (lam <= 10)
    D_fg = np.where(bg.ravel(), K, np.where(fg.ravel(), 0, D_fg))
    D_bg = np.where(fg.ravel(), K, np.where(bg.ravel(), 0, D_bg))
    low = np.minimum(D_fg, D_bg); D_fg, D_bg = D_fg - low, D_bg - low
    n = N * N; s, t = n, n + 1
    rows, cols, caps = [np.full(n, s), np.arange(n)], [np.arange(n), np.full(n, t)], [D_bg, D_fg]
    for a, b, w in nb:
        rows += [a, b]; cols += [b, a]; caps += [lam * w, lam * 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 = G - maximum_flow(G, s, t).flow
    res.data[res.data < 0] = 0; res.eliminate_zeros()
    side = np.zeros(n + 2, bool); side[breadth_first_order(res, s, return_predecessors=False)] = True
    return side[:n].reshape(N, N)       # source side = foreground

def walker(img, fg, bg):
    """Grady's random walker (not a graph cut): label 1 wins where its probability is higher."""
    labels = np.zeros(img.shape, np.int32); labels[fg] = 1; labels[bg] = 2
    return random_walker(img, labels, beta=130, mode="bf") == 1

# ---- click simulation: three placement rules found in the literature ----
def edt(m):                             # zero padding makes the image border a boundary
    return ndi.distance_transform_edt(np.pad(m, 1))[1:-1, 1:-1]

def next_click(gt, pred, clicked, rule):
    fn, fp = gt & ~pred, ~gt & pred
    if rule == "max distance":          # SimpleClick/RITM evaluation code
        dfn, dfp = edt(fn) * ~clicked, edt(fp) * ~clicked
        d = dfn if dfn.max() > dfp.max() else dfp
    elif rule == "dominant count":      # Jang & Kim's description
        d = edt(fn if fn.sum() >= fp.sum() else fp) * ~clicked
    elif rule == "largest cluster":     # Mahadevan et al.
        lab, _ = ndi.label(fn | fp)
        big = lab == np.argmax(np.bincount(lab.ravel())[1:]) + 1
        d = edt(big & ~clicked)
    y, x = np.unravel_index(np.argmax(d), d.shape)   # first maximum in raster order
    return y, x, bool(gt[y, x])

def run(img, gt, method, rule, nb):
    pred = np.zeros_like(gt); clicked = np.zeros_like(gt)
    fg, bg = np.zeros_like(gt), BORDER.copy()        # border = background seed (our choice)
    ious = []
    for _ in range(MAX_CLICKS):
        y, x, positive = next_click(gt, pred, clicked, rule)
        clicked[y, x] = True
        disk = (yy - y) ** 2 + (xx - x) ** 2 <= R ** 2
        if positive:
            fg |= disk & gt
        else:
            bg |= disk & ~gt
        pred = {"RG": lambda: region_growing(img, fg, bg), "GC": lambda: graph_cut(img, fg, bg, nb, 1.0),
                "GC10": lambda: graph_cut(img, fg, bg, nb, 10.0), "RW": lambda: walker(img, fg, bg)}[method]()
        ious.append((pred & gt).sum() / (pred | gt).sum())
        if ious[-1] >= 0.90:
            break
    return np.array(ious), pred

def noc(ious, thr):                     # as compute_noc_metric: first click reaching thr, else the cap
    hit = ious >= thr
    return int(np.argmax(hit)) + 1 if hit.any() else MAX_CLICKS

if __name__ == "__main__":
    KINDS = ["disk", "low contrast", "thin bar", "ramp", "two-tone", "ring"]
    IMAGES = [(k, s) for k in KINDS for s in (0, 1)] + [("horse on grass", 0)]
    METHODS, RULES = ["RG", "GC", "GC10", "RW"], ["max distance", "largest cluster", "dominant count"]
    res, speckle = {}, {}
    for kind, seed in IMAGES:
        img, gt = make_image(kind, seed)
        nb = nlinks(img)
        for rule in RULES:
            for m in METHODS:
                res[kind, seed, rule, m], pred = run(img, gt, m, rule, nb)
                if rule == "max distance":     # false positives more than 2 px from the object
                    far = ndi.distance_transform_edt(~gt) > 2
                    speckle[m] = speckle.get(m, 0) + int((pred & far).sum())

    print("NoC@90 per image (RG = region growing, GC/GC10 = graph cut with lambda 1/10, RW = random walker; 20 = not reached)")
    print(f"{'image':15s} seed | " + " | ".join(f"{r:^19s}" for r in RULES))
    print(" " * 20 + "| " + " | ".join(" RG  GC GC10  RW  " for _ in RULES))
    for kind, seed in IMAGES:
        cells = [" ".join(f"{noc(res[kind, seed, r, m], 0.90):4d}" for m in METHODS) for r in RULES]
        print(f"{kind:15s} {seed:4d} | " + " | ".join(f"{c:19s}" for c in cells))

    print("\nrule             method  NoC@85  NoC@90  failed@90  mean IoU after 1 click")
    for r in RULES:
        for m in METHODS:
            runs = [res[k, s, r, m] for k, s in IMAGES]
            n85 = np.mean([noc(i, 0.85) for i in runs]); n90 = np.mean([noc(i, 0.90) for i in runs])
            fail = sum(i.max() < 0.90 for i in runs)
            print(f"{r:16s} {m:6s}  {n85:6.2f}  {n90:6.2f}  {fail:5d} of {len(runs)}  {np.mean([i[0] for i in runs]):.3f}")

    print("\nfalse-positive pixels more than 2 px from the object, final masks, max distance rule, all images:")
    print("  " + ", ".join(f"{m} {speckle[m]}" for m in METHODS))

Output:

NoC@90 per image (RG = region growing, GC/GC10 = graph cut with lambda 1/10, RW = random walker; 20 = not reached)
image           seed |    max distance     |   largest cluster   |   dominant count   
                    |  RG  GC GC10  RW   |  RG  GC GC10  RW   |  RG  GC GC10  RW  
disk               0 |    1    1    1    2 |    1    1    1    2 |    1    1    1    2
disk               1 |    1    1    1    1 |    1    1    1    1 |    1    1    1    1
low contrast       0 |    1   20    1   14 |    1   20    1   16 |    1   20    1   13
low contrast       1 |    1   20    1    7 |    1   20    1    7 |    1   20    1    7
thin bar           0 |    1   20    1    1 |    1   20    1    1 |    1   20    1    1
thin bar           1 |    1   20    1    3 |    1   20    1    3 |    1   20    1    3
ramp               0 |   20   20    8   13 |   20   20    8   13 |   20   20    8   13
ramp               1 |   20   20    8   13 |   20   20    8   14 |   20   20    8   14
two-tone           0 |    2   20    2    5 |    2   20    2    5 |    2   20    2    5
two-tone           1 |    2   20    2    5 |    2   20    2    5 |    2   20    2    5
ring               0 |    2    1    1    4 |    2    1    1    4 |    2    1    1    4
ring               1 |    2    1    1    4 |    2    1    1    4 |    2    1    1    4
horse on grass     0 |   20   20   20   20 |   20   20   20   20 |   20   20   20   20

rule             method  NoC@85  NoC@90  failed@90  mean IoU after 1 click
max distance     RG        5.54    5.69      3 of 13  0.749
max distance     GC       11.77   14.15      9 of 13  0.705
max distance     GC10      3.38    3.69      1 of 13  0.778
max distance     RW        6.00    7.08      1 of 13  0.616
largest cluster  RG        5.62    5.69      3 of 13  0.749
largest cluster  GC       11.85   14.15      9 of 13  0.705
largest cluster  GC10      3.23    3.69      1 of 13  0.778
largest cluster  RW        6.00    7.31      1 of 13  0.616
dominant count   RG        5.54    5.69      3 of 13  0.749
dominant count   GC       12.69   14.15      9 of 13  0.705
dominant count   GC10      3.31    3.69      1 of 13  0.778
dominant count   RW        6.00    7.08      1 of 13  0.616

false-positive pixels more than 2 px from the object, final masks, max distance rule, all images:
  RG 4633, GC 6171, GC10 495, RW 298

The smoothness weight decided more than the choice of method. With $\lambda = 1$ the graph cut never reached 90% IoU on 9 of the 13 images, including the high-contrast thin bar, and was the worst method on average; with $\lambda = 10$ the same energy was the best, reaching 90% with one click on 8 images. The last line of the output shows where much of the error lay: with $\lambda = 1$ the final masks contained more than ten times as many foreground pixels far from any object as with $\lambda = 10$. That count does not separate scattered pixels from a region the mask leaked into, for either graph cut or for region growing. Our reading, from the energy, is that many are isolated noisy pixels. With $\sigma$ set to the noise level, a pixel that differs from all its neighbours has weak n-links, so labelling it alone costs little smoothness, less than the data term gains when its value is closer to the object’s mean; a larger $\lambda$ makes that isolation too expensive. In that reading clicks cannot repair such errors, since each click seeds only the pixels under one disk, so NoC charges the full 20 clicks.

Region growing needed one or two clicks on every image but the ramp and the horse, and failed on both ramp images. In our reading, the ramp defeats it because its competition compares each pixel with the current region means: the square’s grey value of 0.55 is also the background’s value in the middle columns, so the two regions meet where the ramp crosses the object’s value rather than at the object’s edge. The random walker never failed on the synthetic images but needed up to 16 clicks on the low-contrast ellipse and 13–14 on the ramp, and it had the lowest IoU after the first click. All methods failed on the horse: brick and grass textures are not separated by grey value and local edges alone, which is where learned features come in.

The click rule mattered little here. NoC@90 was the same under all three rules for region growing and both graph cuts, and changed only on two random-walker images (by up to three clicks), moving its mean from 7.08 to 7.31; NoC@85 moved by up to 0.9 clicks for the graph cut with $\lambda = 1$. In our reading, most of these images leave one dominant error region at a time, so the three rules click in nearly the same place. That is a property of these simple scenes, not of the protocol: on images where false positives and false negatives compete, the rules diverge, which is one reason papers that state the same protocol in different words do not always report comparable numbers. Under the max-distance rule, the gap between NoC@85 and NoC@90 was small for region growing (0.15) because its masks either succeeded at once or stalled, and largest for the graph cut with $\lambda = 1$ (2.4).

The example was planned, with its hypotheses, before it was first run, and changed after the first results. The first run contained the graph cut with $\lambda = 1$ only, and its hypotheses that the graph cut would need the fewest clicks and region growing the most were not met. After examining where its errors lay, two additions were made: the count of far false positives, which changes only the printout, and the graph cut with $\lambda = 10$, as a second setting of a parameter that the sources leave open. The value was chosen from the reasoning in the previous paragraph, which drew on diagnostic runs of the first run’s graph-cut masks (not shown), and no other value was tried; this prediction was written in the plan before it ran: it “reaches 0.90 within 2 clicks on disk, thin bar and ring; still fails or needs many clicks on low contrast and two-tone; still fails on ramp and horse; speckle count near zero”. The prediction held for the disk, thin bar, ring and horse but not for the low-contrast and two-tone images (one and two clicks) or the ramp (eight), and the far-false-positive count fell to 495 rather than near zero. The other three methods and all printed values of the first run were unchanged by the additions.

Applications

• Dataset annotation. Interactive segmentation is the main way masks are produced at scale: SAM’s assisted-manual stage and the Open Images masks were made with click-driven models (Image Annotation gives the timings), and FocalClick and SimpleClick present themselves as annotation tools, with attention to CPU latency and to correcting existing masks.
• Photo editing. Selecting an object for cutting out, recolouring or compositing was GrabCut’s original use; image matting refines the hard boundary into partial transparency.
• Medical imaging. Delineating organs and lesions in medical image segmentation is expensive, and interactive methods trade a few clicks for a mask; SimpleClick’s medical evaluation and SAM-derived medical models, described in the SAM article, test how well models trained on natural images transfer.
• Video and 3D annotation, where a correction on one frame or slice is propagated through the rest.

Open Problems

• Realistic evaluation. The standard clicker is deterministic, never makes mistakes and always clicks the centre of the largest error, while real users click imprecisely and differ from one another. Li, Chen and Koltun’s random clicks and SAM’s random first point are steps away from this, and Mahadevan et al. found their method robust to other sampling strategies, but no shared protocol models user error.
• The high-IoU regime. Reaching 90% on DAVIS still takes about five clicks for the best methods in the table above, and fine structures remain the main failure; SAM’s authors expect dedicated interactive methods to beat SAM with many points.
• Guaranteed convergence and local control. Corrective optimization (BRS, f-BRS) and merging only near the click (FocalClick) address the two halves of the problem that users noticed already in McGuinness and O’Connor’s study: masks that do not improve, and changes far from where the user clicked.
• Ambiguity with few clicks. Multiple-output models such as SAM and Li, Chen and Koltun’s diverse hypotheses return several masks, but choosing among them still needs the user or a predicted score.
• Comparable numbers. Benchmark counts, click rules, ignore regions, crop sizes and training sets vary between papers, and baseline numbers are often copied from earlier tables evaluated under different rules, so a reported gap of a fraction of a click may reflect the protocol as much as the method.