Region Proposals

Region proposals, also called object proposals or detection proposals, are a short list of candidate boxes, usually a few hundred to a few thousand per image, that are likely to contain an object of any class. An object detector then classifies and refines only these boxes instead of every position, scale and aspect ratio that sliding window detection would examine. Proposals made object detection with expensive classifiers practical: R-CNN classified about 2,000 of them per image with CNN features, and the proposal stage became the first half of every two-stage detector. Between 2010 and 2015 they were produced by separate algorithms that grouped image regions or scored windows for objectness; since Faster R-CNN (Ren et al., 2015) they are usually predicted by a small network on the detector’s own features.

Definition

A region proposal method takes an image and returns a ranked list of boxes $P = (p_1, p_2, \ldots)$, without class labels. It is judged by recall: the fraction of annotated objects that at least one of the top $N$ boxes overlaps with an intersection over union (IoU) at or above a threshold. Precision matters little, because the detector that follows rejects the false candidates; what the proposal stage misses, no later stage can recover.

Objectness is the related quantity for a single window: a score for how likely the window is to cover an object of any class. Alexe, Deselaers and Ferrari (2010) introduced the term with a measure trained to rank windows that fit “standalone things with a well-defined boundary and center”, such as cows and telephones, above windows on amorphous background “stuff” such as grass and road. Scoring windows for objectness is one way to make proposals; grouping image regions and predicting boxes with a network are the others.

Intuition

Hosang et al. (2014) estimate that a typical sliding-window detector needs about $10^6$ classifier evaluations per image, and almost all of the windows are background. If a cheap, class-independent test can discard most of them and keep the few thousand that look like objects, the detector can spend far more computation on each survivor: a deep network instead of a linear template on HOG features.

The class-independent test works because objects of very different classes share a few visual traits. An object usually has a closed boundary, looks different from its immediate surroundings, and is made of image regions that belong together. A window that cuts through the middle of an object, or that contains only sky, lacks these traits whatever the class. Proposal methods exploit them in two ways: scoring windows for how well they enclose a closed boundary, or growing regions from an over-segmentation until they form whole objects, and boxing the regions.

Proposals change what the detector sees as well as how much it costs. Training on proposals rather than all windows changes the distribution of negatives the classifier is trained on, and fewer candidates can mean fewer false positives (Hosang et al., 2014; Zitnick and Dollár, 2014). Girshick (2015) found the effect in Fast R-CNN: classifying 2,000 proposals from selective search gave higher mean average precision than classifying about 45,000 dense boxes.

Formal Definition

Let $G$ be the set of annotated objects in a test set and $P_N(I)$ the top $N$ proposals for image $I$. The best overlap of an object $g$ in image $I$ is

$$o_g = \max_{p \in P_N(I)} \mathrm{IoU}(g, p).$$

Recall at threshold $t$ is the fraction of objects whose best overlap reaches $t$:

$$R_N(t) = \frac{1}{|G|} \sum_{g \in G} \mathbf{1}\left[\, o_g \ge t \,\right].$$

Papers differ on whether the comparison is $>$ or $\ge$, which matters only for ties. Early work fixed $t = 0.5$, the PASCAL VOC criterion, and plotted $R_N(0.5)$ against $N$: Alexe et al. called it the detection rate, and BING’s authors called the curve DR-#WIN. Uijlings et al. (2013) found recall at 0.5 too insensitive, since selective search reached 95–100% for most classes, and reported the average best overlap (ABO), the mean of $o_g$ over the objects of one class, and its mean over classes (MABO).

Hosang et al. (2014) plotted recall against the threshold for $t \in [0.5, 1]$ at fixed $N$ and summarized each curve by the area under it. Their extended study, “What makes for effective detection proposals?” (Hosang, Benenson, Dollár and Schiele; arXiv 2015, published in IEEE TPAMI in 2016), named the summary average recall (AR), the recall averaged over IoU between 0.5 and 1. Chavali et al. (2016), citing the arXiv version, describe it as correlating with final detection accuracy better than other proposal metrics, and Girshick (2015) as correlating well with R-CNN’s mAP for several proposal methods at a fixed number of proposals per image:

$$\mathrm{AR}_N = 2 \int_{0.5}^{1} R_N(t)\, dt = \frac{1}{|G|} \sum_{g \in G} 2 \max(0,\, o_g - 0.5).$$

The second form follows from integrating the indicator, which is 1 for $t \le o_g$: an object counts in proportion to how far its best overlap exceeds 0.5, so AR rewards tight boxes, not only boxes that clear one threshold. COCO’s average recall for detections (see precision and recall) is the discrete version, averaged over the thresholds 0.50 to 0.95 in steps of 0.05.

Families of Proposal Methods

Chavali et al. (2016) divide proposal methods into window scoring, which samples windows and scores them for the presence of an object, and segment-based methods, which over-segment the image and merge segments. Zitnick and Dollár (2014) distinguish three paradigms: objectness scoring, multiple foreground–background segmentations from seeds, and superpixel merging. Learned proposals, predicted by a network trained on detection data, form a third family that ended the era of separate proposal algorithms.

Window scoring

Objectness (Alexe et al., 2010) scores a window with four cues, each tied to a trait of objects:

• multi-scale saliency, from the spectral residual of the image’s Fourier transform, for objects that stand out within the image;
• color contrast, the $\chi^2$ distance between the Lab histograms of the window and of a ring around it;
• edge density in an inner ring along the window’s border, for a closed boundary;
• superpixels straddling, the cue the paper introduced. Superpixels from the Felzenszwalb–Huttenlocher graph-based segmentation rarely cross object boundaries, so a window that fits an object is covered by superpixels lying wholly inside it, while a bad window is crossed by superpixels that continue outside:

$$\mathrm{SS}(w) = 1 - \sum_{s} \frac{\min\left(|s \setminus w|,\; |s \cap w|\right)}{|w|}.$$

The cues are combined by naive Bayes, with parameters learned from 50 images holding 291 objects of 48 classes, class labels unused. On the 4,952 images of the PASCAL VOC 2007 test set, superpixels straddling was the best single cue, and the combination of saliency, color contrast and straddling the best measure: 23% of 1,000 windows sampled from it covered an object at IoU above 0.5. A HOG detector trained on all classes at once did very poorly at the same task, which the authors read as evidence that generic objects have no single gradient template. They used the samples as a location prior for class-specific detectors, including deformable part models, to cut the number of windows these evaluated.

BING (Cheng, Zhang, Lin and Torr, 2014) takes the opposite route to speed: one learned linear template on a tiny feature. Every window is resized to $8 \times 8$ and described by the magnitude of its gradients, a 64-dimensional “normed gradients” feature; the authors observed that object windows look alike at this resolution, with strong gradients along the border. The image is resized so that $8 \times 8$ windows correspond to 36 window sizes, widths and heights from $\{10, 20, 40, 80, 160, 320\}$. A linear SVM $\mathbf{w} \in \mathbb{R}^{64}$ scores every window, non-maximum suppression keeps a few per size, and a second stage learns a scale and bias per size, so that unlikely sizes such as $10 \times 500$ rank lower. For speed, $\mathbf{w}$ is approximated by a few binary basis vectors and the gradient bytes by their top bits, so a window’s score needs only bitwise AND, bit counts and shifts. The authors reported 96.2% recall at IoU 0.5 with 1,000 proposals on VOC 2007 test, 99.5% with 5,000 proposals from three color spaces, and 0.003 s per image on a laptop CPU (300 frames per second); trained on a subset of the classes and tested on the others, recall was almost unchanged. Hosang et al. (2014) found BING and Edge Boxes the most repeatable methods under image perturbations, but also found that its boxes fit loosely: high recall at IoU 0.5 that falls steeply at higher overlap, and a non-monotonic response to scale changes, which they attribute to its coarse set of box sizes. Their summary table lists BING at 0.2 s per image, while their text gives 1 ms.

Edge Boxes (Zitnick and Dollár, 2014) scores windows by the contours they enclose. Its key observation is that a box likely to contain an object wholly encloses many contours, while edges belonging to contours that cross the box boundary probably belong to something outside it. It computes edges with the Structured Edge detector, thins them by non-maximum suppression (see edge detection) and greedily combines 8-connected edge pixels into groups until the sum of their orientation differences exceeds $\pi/2$. Two neighboring groups $s_i$ and $s_j$, with mean orientations $\theta_i$, $\theta_j$ and $\theta_{ij}$ the angle between their mean positions, have affinity

$$a(s_i, s_j) = \left| \cos(\theta_i - \theta_{ij}) \cos(\theta_j - \theta_{ij}) \right|^{\gamma}, \qquad \gamma = 2,$$

which is high when the two groups continue each other along a smooth contour. For a box $b$, a group gets the weight $w_b(s_i) = 1 - \max_T \prod_j a(t_j, t_{j+1})$, where the maximum runs over paths of groups from one that touches the box boundary to $s_i$, so groups strongly connected to the boundary weigh nearly nothing. With $m_i$ the summed edge magnitude of group $i$, the score is

$$h_b = \frac{\sum_i w_b(s_i)\, m_i}{2\,(b_w + b_h)^{\kappa}}, \qquad \kappa = 1.5,$$

normalized by the perimeter rather than the area, since edges are one pixel wide. A variant, which the paper found slightly more accurate, also subtracts the edges inside a central box of half the width and height, since edges near the center matter less than those near the border. The search slides boxes over positions, scales (from 1,000 pixels of area to the whole image) and aspect ratios from 1:3 to 3:1, with steps set so neighboring boxes overlap at IoU $\alpha = 0.65$, refines promising boxes greedily, and applies NMS at IoU $\beta = \delta + 0.05$ for a target overlap $\delta$. Tuning $\delta$ trades many loose boxes against fewer tight ones; Edge Boxes 70 targets IoU 0.7. On VOC 2007 test it reported over 96% recall at IoU 0.5 and over 75% at IoU 0.7 with 1,000 proposals in 0.25 s per image; reaching 75% recall at IoU 0.7 took 800 proposals, against 1,400 for selective search and 3,000 for randomized Prim’s. The paper’s central ablation kept the contours that cross the box boundary: without their removal, accuracy dropped significantly. Faster R-CNN’s authors described Edge Boxes as the best trade-off between proposal quality and speed at the time, at 0.2 s per image.

Grouping

Grouping methods start from an over-segmentation and build larger regions, each of which yields a box (and, for some methods, a segment usable for instance segmentation).

Selective search (Uijlings et al., 2013) merges Felzenszwalb–Huttenlocher regions hierarchically, always joining the most similar pair of neighbors by a combination of color, texture, size and fill similarities, and boxes every region created on the way up. It diversifies by running several strategies (color spaces, similarity combinations, starting segmentations) and ranks the pooled boxes with some randomness so that large regions do not dominate. Its “fast” mode recalled 98.0% of the VOC 2007 test objects at IoU 0.5 with 2,134 boxes per image, MABO 0.804; its “quality” mode 99.1% with 10,097, MABO 0.879. It learns no parameters. R-CNN used the fast mode; the selective search article covers the similarities, the strategies and the ranking.

Other grouping methods, as Hosang et al. (2014) summarize them, differ in how regions are formed and ranked. CPMC (Carreira and Sminchisescu) solves many binary foreground–background segmentations with graph cuts from diverse seeds, producing up to $10^4$ segments that a trained regressor ranks; Endres and Hoiem’s category-independent proposals likewise combine seeded segmentations with a learned ranking; randomized Prim’s (Manén et al.) merges superpixels like selective search but with learned weights and a randomized merging process. Multiscale combinatorial grouping (MCG; Arbeláez et al., 2014) builds a hierarchical segmentation from contours at several scales, combines up to four of its regions into candidates, and ranks the candidates by regressing their overlap with an object with a random forest. Seeded segmentation gives high-quality masks at a high cost: Zitnick and Dollár put it at minutes per image, and Hosang et al.’s table lists CPMC at 250 s.

Learned proposals

The third family learns the proposal generator from detection data. MultiBox (Erhan, Szegedy, Toshev and Anguelov, 2014) trained a deep network to output a fixed number of class-agnostic boxes (100 or 200) with a confidence for each. Training matched predictions to ground-truth boxes by solving a bipartite assignment problem per image, regressed the matched boxes and raised their confidences, and lowered the confidences of the rest. Boxes were predicted as residuals to priors obtained by clustering the training boxes with k-means, and the matching was done between these priors and the ground truth; without this prior matching, the authors found convergence speed and quality significantly lower. Classifying fewer than ten of its boxes per image gave detection results the authors called competitive on VOC 2007.

The region proposal network (RPN) of Faster R-CNN (Ren et al., 2015) made learned proposals nearly free. Instead of a separate network on the image, it adds a $3 \times 3$ convolution and two sibling $1 \times 1$ layers to the detector’s last shared feature map, predicting at each position an objectness score and box offsets for $k = 9$ anchor boxes; NMS at IoU 0.7 on the objectness scores leaves about 2,000 proposals for training and the top 300 at test time. The Faster R-CNN article covers its architecture, labeling rule and training.

Evaluating Proposals

Hosang, Benenson and Schiele (2014) ran the first unified comparison: ten methods with public code against four baselines that ignore image content or use it minimally. Uniform samples box centers, square-root areas and log aspect ratios uniformly over ranges estimated on VOC 2007 training boxes; Gaussian samples them from a fitted multivariate Gaussian; SlidingWindow splits the requested number of boxes over a set of window sizes and places each size on a regular grid; Superpixels returns the box of every Felzenszwalb–Huttenlocher segment. They found four things.

• Recall. On the VOC 2007 test set with 1,000 proposals per image, the area under the recall–IoU curve was 75.0 (%) for MCG, 73.1 for selective search and 72.2 for Edge Boxes (tuned for IoU 0.7), against 56.6 for sliding windows and 36.2 for uniform boxes. The methods fell into two groups: well-localized ones, whose recall fell gradually as the IoU threshold rose, and approximate ones, BING, Rahtu et al.’s method, Edge Boxes and all baselines, whose recall dropped quickly. The baselines catch up as the number of boxes grows: at 1,000 boxes the Gaussian and sliding-window baselines became competitive above IoU 0.7, and at about 10,000 boxes the uniform baseline reached 71.9. In relative terms, proposal methods help most when few windows are allowed.
• No visible class bias. On the ImageNet 2013 detection validation set, about 20,000 images with 200 classes many of which are unrelated to VOC’s 20, the recall curves were almost identical to VOC’s; the authors explain the similarity by both datasets having the same typical image size and three annotated objects per image on average, and conclude that the methods transfer to unseen classes.
• Repeatability. Proposals for slightly perturbed copies of an image (scaling, blur, small rotations, illumination changes, JPEG compression) were matched to the original’s. Most methods lost much of their repeatability even under the slightest change; the Superpixels baseline lost it too, which pointed to unstable superpixels as the cause. BING and Edge Boxes were the most repeatable.
• Detection. Filtering the detections of a pretrained deformable part model with 1,000 proposals per image lowered VOC 2007 mAP for every method, from 33.5 (34.4 after box regression) for the detector’s own sliding-window search to at best 32.4 (32.7) with MCG; BING reached 21.8 (22.4) and uniform boxes 16.6 (16.9). Methods with a high area under the recall–IoU curve gave high mAP, while two methods with similar areas but poorer recall at IoU 0.7 and above gave lower mAP, so localization at high overlap mattered.

They recommended selective search and Edge Boxes for consistently good recall, repeatability and speed, Edge Boxes when speed matters, and MCG when fewer than 1,000 proposals are wanted.

AR tracks mAP when the number of proposals per image is fixed, but Girshick (2015) showed its limits as that number changes. Sweeping selective search’s quality mode from 1,000 to 10,000 proposals per image and retraining Fast R-CNN each time, AR kept rising while VOC 2007 test mAP rose and then fell slightly; adding random dense boxes to 2,000 selective-search boxes lowered mAP further, and dense boxes alone (about 45,000 per image) gave 52.9%. More proposals did not help, so proposals act as a cascade that rejects most candidates before the classifier sees them, not only as a computational shortcut, and AR “must be used with care”. Ren et al. (2015) likewise called recall versus IoU only loosely related to detection accuracy and better suited to diagnosing a proposal method than to evaluating it.

Chavali et al. (2016) found a second flaw: the protocol rewards bias toward the annotated classes. VOC annotates only 20 classes, so in their example a method that finds a plate, a bowl and a picture frame but misses a table scores lower than one that finds the table. Their “detector masquerading as proposal generator”, the top detections of 20 R-CNN or DPM class detectors, beat every proposal method on PASCAL VOC 2010, then suffered the largest drop when they annotated 60 further classes on PASCAL Context images. As learning-based proposal methods improve on the protocol, they argue, the best proposal generator tends toward a detector for the annotated classes. For detection this is harmless; for uses that need any object, such as object discovery, it is not.

Properties

• Recall caps detection. An object that receives no proposal near it cannot be detected; box regression can repair a moderately misplaced proposal but not a missing one.
• Localization matters, not only coverage. Methods with equal recall at IoU 0.5 can differ widely at 0.7, and Hosang et al.’s detection experiment favored the better-localized ones.
• Ranking matters at small budgets. All methods converge as the number of boxes grows, even random boxes; the differences, and the value of a good method, lie in the first few hundred boxes.
• Speed set the practical limit. Hosang et al.’s timings range from 0.2 s for BING and 0.3 s for Edge Boxes to 10 s for selective search and 250 s for CPMC per image. By 2015, proposals on the CPU took as long as Fast R-CNN’s whole detection network on the GPU (Ren et al., 2015).
• Class-agnostic does not mean class-free. Hand-designed methods encode a definition of an object (closed boundary, coherent regions); learned methods learn whatever the training annotations call an object.

Examples

The NumPy and scikit-image code compares four generators on 50 synthetic $128 \times 128$ scenes, each with three to six textured rectangles, ellipses and triangles of random size, aspect ratio (up to 3:1) and color on a shaded background. Each object is two-toned with probability 0.4, so that one object spans two regions, and later objects may occlude earlier ones; each ground-truth box is the box of the object’s visible pixels, and objects with fewer than 30 visible pixels are dropped. The generators re-implement one representative of each family from its paper’s description:

• random: Hosang et al.’s uniform baseline, with ranges estimated on 50 separate training scenes after trimming 0.5% at each end;
• sliding windows: their SlidingWindow baseline over 15 window shapes (5 scales by 3 aspect ratios);
• window scoring: the same 15 shapes slid densely (12,615 windows), scored by Alexe et al.‘s superpixels-straddling cue on a Felzenszwalb–Huttenlocher segmentation, then NMS at IoU 0.75, Edge Boxes’ rule $\beta = \delta + 0.05$ for $\delta = 0.7$;
• grouping: a single-strategy hierarchical grouping after selective search, merging adjacent regions by color-histogram, size and fill similarity, ranked by Uijlings et al.’s rule (a random number times the region’s position in the hierarchy).

It reports recall at IoU 0.5 and 0.7 and AR for $N$ = 10 to 1,000 proposals, and two reference lines: Hosang et al.’s Superpixels baseline, and the best IoU that any of the 12,615 unscored dense windows reaches. It runs in about 9 s (NumPy 2.3.5, scikit-image 0.25.2).

import numpy as np
from skimage.segmentation import felzenszwalb

H = W = 128
SHAPES = [(s / np.sqrt(r), s * np.sqrt(r)) for s in (84, 52, 32, 20, 12) for r in (0.5, 1, 2)]  # (w, h)

def make_scene(rng):
    """Background gradient + 3-6 textured objects; some two-tone. Returns image and visible-mask boxes."""
    yy, xx = np.mgrid[0:H, 0:W]
    img = rng.uniform(0.2, 0.8, 3) + 0.3 * (xx / W)[..., None] * rng.uniform(-1, 1, 3)
    img = img + rng.normal(0, 0.04, (H, W, 3))
    label = np.zeros((H, W), int)
    n = rng.integers(3, 7)
    for k in range(1, n + 1):
        s, r = np.exp(rng.uniform(np.log(10), np.log(80))), np.exp(rng.uniform(np.log(1 / 3), np.log(3)))
        w, h = min(s / np.sqrt(r), W - 2), min(s * np.sqrt(r), H - 2)
        cx, cy = rng.uniform(w / 2, W - w / 2), rng.uniform(h / 2, H - h / 2)
        u, v = (xx - cx) / (w / 2), (yy - cy) / (h / 2)
        m = [(abs(u) <= 1) & (abs(v) <= 1), u**2 + v**2 <= 1,
             (abs(v) <= 1) & (abs(u) <= (v + 1) / 2)][rng.integers(3)]
        img[m] = rng.uniform(0, 1, 3) + rng.normal(0, 0.04, (m.sum(), 3))
        if rng.random() < 0.4:                      # two-tone object: lower half another colour
            m2 = m & (yy > cy)
            img[m2] = rng.uniform(0, 1, 3) + rng.normal(0, 0.04, (m2.sum(), 3))
        label[m] = k
    boxes = []
    for k in range(1, n + 1):
        ys, xs = np.nonzero(label == k)
        if len(ys) >= 30:                           # drop objects that are almost fully occluded
            boxes.append([xs.min(), ys.min(), xs.max() + 1, ys.max() + 1])
    return np.clip(img, 0, 1), np.array(boxes, float)

def iou(a, b):
    """IoU matrix between boxes a (n, 4) and b (m, 4), as (x0, y0, x1, y1)."""
    iw = np.clip(np.minimum(a[:, None, 2], b[None, :, 2]) - np.maximum(a[:, None, 0], b[None, :, 0]), 0, None)
    ih = np.clip(np.minimum(a[:, None, 3], b[None, :, 3]) - np.maximum(a[:, None, 1], b[None, :, 1]), 0, None)
    area = lambda x: (x[:, 2] - x[:, 0]) * (x[:, 3] - x[:, 1])
    inter = iw * ih
    return inter / (area(a)[:, None] + area(b)[None, :] - inter)

def nms(boxes, scores, thr, keep_max):
    order, keep = np.argsort(-scores, kind="stable"), []
    while len(order) and len(keep) < keep_max:
        i = order[0]
        keep.append(i)
        order = order[1:][iou(boxes[i:i + 1], boxes[order[1:]])[0] <= thr]
    return boxes[keep]

def random_boxes(rng, n, ranges):
    (cx0, cx1), (cy0, cy1), (s0, s1), (a0, a1) = ranges
    s, a = rng.uniform(s0, s1, n), np.exp(rng.uniform(a0, a1, n))
    cx, cy, w, h = rng.uniform(cx0, cx1, n), rng.uniform(cy0, cy1, n), s / np.sqrt(a), s * np.sqrt(a)
    return np.clip(np.stack([cx - w / 2, cy - h / 2, cx + w / 2, cy + h / 2], 1), 0, W)

def sliding_windows(n):
    """Hosang et al.'s baseline: the budget is split over the shapes, each placed on a regular grid."""
    per = [n // len(SHAPES) + (i < n % len(SHAPES)) for i in range(len(SHAPES))]
    out = []
    for (w, h), m in zip(SHAPES, per):
        if m == 0:
            continue
        g = int(np.ceil(np.sqrt(m)))
        cx, cy = np.meshgrid(np.linspace(w / 2, W - w / 2, g), np.linspace(h / 2, H - h / 2, g))
        idx = np.linspace(0, g * g - 1, m).round().astype(int)
        cx, cy = cx.ravel()[idx], cy.ravel()[idx]
        out.append(np.stack([cx - w / 2, cy - h / 2, cx + w / 2, cy + h / 2], 1))
    return np.concatenate(out)

def dense_windows():
    """All windows of the 15 shapes, stride a quarter of the shorter side (at least 2 pixels)."""
    wins = []
    for w, h in SHAPES:
        w, h = int(round(w)), int(round(h))
        st = max(2, min(w, h) // 4)
        x0, y0 = np.meshgrid(np.arange(0, W - w + 1, st), np.arange(0, H - h + 1, st))
        wins.append(np.stack([x0.ravel(), y0.ravel(), x0.ravel() + w, y0.ravel() + h], 1))
    return np.concatenate(wins)

def objectness_windows(seg, n):
    """Window scoring: dense windows scored by superpixel straddling (Alexe et al.), then NMS."""
    wins = dense_windows()
    K = seg.max() + 1
    onehot = (seg[None] == np.arange(K)[:, None, None]).astype(np.int32)
    ii = np.pad(onehot.cumsum(1).cumsum(2), ((0, 0), (1, 0), (1, 0)))     # integral image per superpixel
    x0, y0, x1, y1 = wins.T
    inside = ii[:, y1, x1] - ii[:, y0, x1] - ii[:, y1, x0] + ii[:, y0, x0]  # (K, n_windows)
    outside = onehot.sum((1, 2))[:, None] - inside
    area = (x1 - x0) * (y1 - y0)
    score = 1 - np.minimum(inside, outside).sum(0) / area
    return nms(wins.astype(float), score, 0.75, n)

def grouping(img, seg, rng):
    """Single-strategy hierarchical grouping (selective-search style): colour + size + fill."""
    K, size_im = seg.max() + 1, seg.size
    R = {}
    for k in range(K):
        ys, xs = np.nonzero(seg == k)
        hist = np.concatenate([np.histogram(img[ys, xs, c], 25, (0, 1))[0] for c in range(3)]).astype(float)
        R[k] = dict(size=len(ys), box=np.array([xs.min(), ys.min(), xs.max() + 1, ys.max() + 1]), hist=hist / hist.sum())
    nbr = set()
    for a, b in ((seg[:, :-1], seg[:, 1:]), (seg[:-1], seg[1:])):
        d = a != b
        nbr |= {(min(p, q), max(p, q)) for p, q in zip(a[d], b[d])}
    def sim(i, j):
        ri, rj = R[i], R[j]
        bb = np.r_[np.minimum(ri["box"][:2], rj["box"][:2]), np.maximum(ri["box"][2:], rj["box"][2:])]
        fill = 1 - ((bb[2] - bb[0]) * (bb[3] - bb[1]) - ri["size"] - rj["size"]) / size_im
        return np.minimum(ri["hist"], rj["hist"]).sum() + 1 - (ri["size"] + rj["size"]) / size_im + fill
    S = {p: sim(*p) for p in nbr}
    order = list(range(K))                           # creation order of all regions
    while S:
        i, j = max(S, key=S.get)
        t = len(R)
        ri, rj = R[i], R[j]
        R[t] = dict(size=ri["size"] + rj["size"],
                    box=np.r_[np.minimum(ri["box"][:2], rj["box"][:2]), np.maximum(ri["box"][2:], rj["box"][2:])],
                    hist=(ri["size"] * ri["hist"] + rj["size"] * rj["hist"]) / (ri["size"] + rj["size"]))
        nb = {q for p in S for q in p if i in p or j in p} - {i, j}
        S = {p: s for p, s in S.items() if i not in p and j not in p}
        S.update({(q, t): sim(q, t) for q in nb})
        order.append(t)
    pos = np.empty(len(order))
    pos[order[::-1]] = np.arange(1, len(order) + 1)  # i = 1 is the top of the hierarchy
    rank = np.argsort(rng.random(len(order)) * pos, kind="stable")     # Uijlings et al.: RND x i
    boxes = np.array([R[r]["box"] for r in rank], float)
    _, first = np.unique(boxes, axis=0, return_index=True)            # drop lower-ranked duplicates
    return boxes[np.sort(first)]

# Random-box ranges from 50 training scenes (0.5% trimmed at each end), as in Hosang et al.
rng = np.random.default_rng(0)
gt = np.concatenate([make_scene(rng)[1] for _ in range(50)])
cx, cy = (gt[:, 0] + gt[:, 2]) / 2, (gt[:, 1] + gt[:, 3]) / 2
w, h = gt[:, 2] - gt[:, 0], gt[:, 3] - gt[:, 1]
ranges = [np.percentile(v, [0.5, 99.5]) for v in (cx, cy, np.sqrt(w * h), np.log(h / w))]

NS = [10, 30, 100, 300, 1000]
methods = ["random", "sliding windows", "window scoring", "grouping"]
best = {m: {n: [] for n in NS} for m in methods}     # best IoU of every object, per method and budget
count = {m: [] for m in methods}
rng, rng_box, rng_rank = np.random.default_rng(1), np.random.default_rng(2), np.random.default_rng(3)
n_obj, seg_best, n_seg, grid_best = 0, [], [], []
grid = dense_windows().astype(float)
for _ in range(50):
    img, gt = make_scene(rng)
    n_obj += len(gt)
    seg = felzenszwalb(img, scale=100, sigma=0.8, min_size=20)
    segboxes = np.array([[xs.min(), ys.min(), xs.max() + 1, ys.max() + 1] for ys, xs in
                         (np.nonzero(seg == k) for k in range(seg.max() + 1))], float)
    seg_best.append(iou(gt, segboxes).max(1))       # Hosang et al.'s Superpixels baseline
    n_seg.append(len(segboxes))
    grid_best.append(iou(gt, grid).max(1))           # best any dense window can do
    ranked = {"random": random_boxes(rng_box, 1000, ranges),
              "window scoring": objectness_windows(seg, 1000),
              "grouping": grouping(img, seg, rng_rank)}
    for m in methods:
        for n in NS:
            p = sliding_windows(n) if m == "sliding windows" else ranked[m][:n]
            best[m][n].append(iou(gt, p).max(1))
        count[m].append(len(p))

print(f"{n_obj} objects in 50 scenes; columns are N = number of proposals per image")
for title, f in [("recall at IoU 0.5", lambda b: np.mean(b >= 0.5)),
                 ("recall at IoU 0.7", lambda b: np.mean(b >= 0.7)),
                 ("average recall, IoU 0.5-1", lambda b: np.mean(2 * np.clip(b - 0.5, 0, None)))]:
    print(f"\n{title:27s}" + "".join(f"{n:>7d}" for n in NS) + "   boxes at N=1000")
    for m in methods:
        vals = [f(np.concatenate(best[m][n])) for n in NS]
        print(f"  {m:25s}" + "".join(f"{v:7.2f}" for v in vals) + f"   {np.mean(count[m]):9.0f}")

b = np.concatenate(seg_best)
print(f"\nsingle segments, all {np.mean(n_seg):.0f} per image: recall {np.mean(b >= 0.5):.2f} at IoU 0.5, "
      f"{np.mean(b >= 0.7):.2f} at IoU 0.7, AR {np.mean(2 * np.clip(b - 0.5, 0, None)):.2f}")
b = np.concatenate(grid_best)
print(f"all {len(grid)} dense windows, unscored: recall {np.mean(b >= 0.5):.2f} at IoU 0.5, "
      f"{np.mean(b >= 0.7):.2f} at IoU 0.7, AR {np.mean(2 * np.clip(b - 0.5, 0, None)):.2f}")

210 objects in 50 scenes; columns are N = number of proposals per image

recall at IoU 0.5               10     30    100    300   1000   boxes at N=1000
  random                      0.05   0.13   0.30   0.49   0.65        1000
  sliding windows             0.03   0.07   0.22   0.42   0.64        1000
  window scoring              0.76   0.92   0.97   0.98   0.98        1000
  grouping                    0.65   0.92   0.97   0.97   0.97          47

recall at IoU 0.7               10     30    100    300   1000   boxes at N=1000
  random                      0.01   0.04   0.06   0.10   0.25        1000
  sliding windows             0.00   0.01   0.03   0.11   0.25        1000
  window scoring              0.40   0.51   0.57   0.59   0.59        1000
  grouping                    0.46   0.76   0.80   0.80   0.80          47

average recall, IoU 0.5-1       10     30    100    300   1000   boxes at N=1000
  random                      0.01   0.03   0.07   0.13   0.23        1000
  sliding windows             0.01   0.01   0.05   0.11   0.21        1000
  window scoring              0.31   0.39   0.42   0.43   0.43        1000
  grouping                    0.37   0.66   0.71   0.71   0.71          47

single segments, all 31 per image: recall 0.82 at IoU 0.5, 0.59 at IoU 0.7, AR 0.50
all 12615 dense windows, unscored: recall 0.98 at IoU 0.5, 0.60 at IoU 0.7, AR 0.44

The two content-blind generators need hundreds of boxes to find half the objects at IoU 0.5, while the two that look at the image find most of them with ten. That is the case for proposals in one table: the gain is largest at small budgets. At 1,000 boxes the blind baselines are still far behind at both thresholds, unlike Hosang et al.’s VOC results, where the sliding-window and Gaussian baselines became competitive above IoU 0.7 at 1,000 boxes; their uniform baseline needed about $10^4$.

From 30 boxes on, window scoring and grouping tie at IoU 0.5 but part at 0.7, the split between approximate and well-localized methods. The reference line shows why window scoring stalls at 0.59: no window of the 15 shapes on its grid reaches IoU 0.7 with 40% of the objects, so straddling selects nearly the best boxes the grid holds, and the cap is the grid’s. In our reading, BING’s coarse set of box sizes limits it in the same way, and Edge Boxes refines its boxes, and samples more densely for tight targets, to avoid it. Grouping’s boxes are drawn around regions, so they can fit any shape and size; they fail only where the segmentation fails, and the hierarchy holds just 47 boxes per image, so grouping’s recall stops at 0.97 and 0.80, however many boxes are requested.

These scenes are kind to grouping. Objects have uniform colors on smooth backgrounds, so even a single segment’s box recalls 82% of the objects at IoU 0.5. On natural images the gap is much smaller: in Hosang et al.’s comparison, Edge Boxes, a window-scoring method with box refinement, came within one point of selective search in area under the recall–IoU curve at 1,000 proposals. The script was first run with the four-method table only; the two reference lines, which come from diagnostics run after that first run, were added to the printed output afterwards (moving the dense grid into its own function, with the same windows), leaving the table unchanged.

From Hand-Designed Proposals to the Region Proposal Network

Object proposals grew out of two older lines of work. Cascades, such as Viola–Jones, already discarded most windows with a cheap classifier, and Hosang et al. relate proposal methods to cascades that are not tied to one class. Segmentation had been used to suggest object hypotheses, and Erhan et al. place their own work in this line. Zitnick and Dollár trace the idea to objectness (Alexe et al.) and to the seeded segment proposals of Carreira and Sminchisescu and of Endres and Hoiem, all first published in 2010; Hosang et al. date it to Alexe et al. and to Gu et al.’s recognition using regions (2009). These works made the class-independent candidate set a goal of its own, and selective search showed that a simple grouping method could reach about 98% recall at IoU 0.5 with a few thousand boxes.

The decisive step was R-CNN, which classified about 2,000 selective-search proposals with a fine-tuned CNN and used them for its training as well. Faster detectors then shifted the bottleneck: SPPnet and Fast R-CNN shared the CNN computation across proposals, until, Ren et al. wrote, the proposals were the bottleneck. Selective search took about 2 s per image on the CPU (1.51 s in their timing table) and Edge Boxes 0.2 s, as long as the detection network itself. Re-implementing a proposal method on the GPU would have sped it up, Ren et al. argued, but would not share computation with the detector.

The RPN shared it. Computing proposals from the detector’s own convolutional features cost about 10 ms per image, and with 300 RPN proposals instead of 2,000 from selective search or Edge Boxes, Fast R-CNN with the ZF network scored 59.9% mAP on VOC 2007 test, against 58.7% and 58.6%. The RPN’s recall also held up better than selective search’s and Edge Boxes’ as the number of proposals fell from 2,000 to 300, which the authors attribute to its learned objectness scores. Learned proposals improved with deeper backbones (VGG-16 against ZF in Ren et al.’s ablation) and later with multi-scale features: the feature pyramid network article reports the RPN’s average recall on COCO with and without them.

The RPN kept the idea of a class-agnostic first stage but changed its nature, in two ways the earlier debate anticipated. Its objectness is learned from the annotated classes, which is what Chavali et al. warned the evaluation protocol rewards. And its proposals are scored on the same features as the detection, so the two stages are trained together rather than evaluated separately. One-stage detectors went further and dropped the proposal stage, classifying dense anchors directly, and DETR predicts a fixed set of boxes with bipartite matching, a training scheme MultiBox had used for proposals.

Common Misconceptions

• “Proposals are only a speed-up.” Girshick (2015) found that 2,000 proposals gave higher mAP than about 45,000 dense boxes, and that more selective-search proposals beyond a point lowered mAP; proposals also shape the negatives the classifier sees.
• “Higher recall means a better proposal method.” Recall at IoU 0.5 ignores localization, and AR rises with the number of boxes even when detection does not improve. Compare at the same number of proposals, at several IoU thresholds, and ideally by the detector’s mAP.
• “Class-agnostic proposals find any object.” Evaluations on VOC count only 20 classes, and learned proposals learn the annotated classes. Chavali et al. (2016) showed that detectors for the annotated classes look like the best proposal generators under the standard protocol.
• “Anchors are proposals.” An anchor is a fixed reference box; in an RPN, the proposal is the anchor after the predicted offsets are applied, filtered by objectness and NMS (see anchor boxes).
• “Proposals disappeared with Faster R-CNN.” Hand-designed proposal algorithms did; the proposal stage did not, and it remains the first stage of two-stage detectors.

Where It Is Used

• Two-stage detectors. R-CNN, SPPnet and Fast R-CNN classified selective-search proposals; Faster R-CNN and its descendants, including Mask R-CNN, generate them with an RPN. The two-stage object detectors article follows this line.
• Box refinement. Proposals are the reference boxes for the second stage’s class-specific box regression, as in R-CNN.
• Segment proposals. Grouping methods such as CPMC and MCG produce masks as well as boxes, used as candidates for segmentation.
• Uses that need any object. Zitnick and Dollár mention weakly supervised learning, where a few hundred proposals per image limit the candidate locations of an object whose position is not annotated; Chavali et al. list object discovery, tracking and retargeting among other uses, for which category independence matters more than for detection.
• Class-agnostic evaluation of modern models. Promptable segmentation models are evaluated as object proposal generators by mask AR, as Segment Anything reports on LVIS.