Selective Search

Selective search is a region proposal algorithm: it produces a few thousand class-agnostic candidate boxes per image that are likely to contain objects, for a detector to classify. It starts from an over-segmentation of the image into small regions, repeatedly merges the two most similar neighbouring regions until one region covers the image, and keeps the bounding box of every region formed along the way. To cover the many reasons why pixels belong to one object, it runs this grouping several times, in different colour spaces, with different similarity measures and different starting segmentations, and pools the boxes. Koen van de Sande, Jasper Uijlings, Theo Gevers and Arnold Smeulders introduced it at ICCV 2011 as “segmentation as selective search”, and Uijlings et al. gave the full method in the International Journal of Computer Vision in 2013. R-CNN took its roughly 2,000 proposals per image from the fast mode of selective search.

The numbers and equations below come from the authors’ copy of the journal paper, marked “Technical Report 2012, submitted to IJCV”; the publisher’s version could not be read and may differ in detail.

Problem

A sliding-window detector scores every position, scale and aspect ratio on a grid, which forces a cheap classifier and fixed aspect ratios. Uijlings et al. wanted a small, data-driven set of locations that still captures nearly every object, so that a more expensive classifier could be afforded. They built it from bottom-up image segmentation, with two changes to its usual goal: keep the regions of a whole hierarchy instead of one best partition, and use several grouping rules instead of one.

Inputs and Outputs

The input is a colour image. The output is a list of boxes, ranked so that taking the first $N$ gives a usable trade-off between number and quality, without scores or class labels. The method also yields the regions themselves, which the paper evaluates as segment proposals. One hierarchy grown from $n$ starting regions contains $2n - 1$ regions (the $n$ initial ones and $n - 1$ merges), so a single strategy gives at most that many boxes before duplicates are removed.

Intuition

The paper’s Figure 1 shows the cues that conflict. Two cats can be separated by colour but not texture; a chameleon matches the leaves in colour but not in texture; a car’s wheels differ from its body in both, yet belong to the car because the body encloses them. A salad sits in a bowl that stands on a table, so the right scale depends on which object is wanted. A hierarchy answers the scale problem, because each merge creates a region at a coarser scale. Diversity answers the cue problem: a grouping driven by colour finds some objects, one driven by texture or enclosure finds others, and the union of their boxes finds more than either.

Algorithm

One grouping strategy, the paper’s Algorithm 1:

1. Over-segment the image with Felzenszwalb and Huttenlocher’s graph-based method (see superpixels), which the authors chose as the fastest publicly available method giving good starting regions.
2. Compute the similarity $s(r_i, r_j)$ of every pair of neighbouring regions.
3. Merge the most similar pair into $r_t = r_i \cup r_j$, remove all similarities involving $r_i$ or $r_j$, and compute the similarities between $r_t$ and its neighbours.
4. Repeat step 3 until a single region covers the image.
5. Return the bounding box of every region created, including the initial ones.

All features must be computable from the two merged regions’ features without returning to the pixels, which keeps each merge cheap.

Diversification. The full method runs Algorithm 1 under several settings and pools the results. Three things vary: the colour space (one of eight, from RGB to hue, with increasing invariance to shading, shadows and highlights; the paper’s Table 1 lists the invariances), used both for the initial segmentation and for the grouping; the combination of similarity measures; and the threshold $k$ of the initial segmentation.

Ranking and pooling. Within one hierarchy, the region created last (the whole image) has position $i = 1$, the one before it $i = 2$, and so on, so large regions come first. Pooling up to 80 hierarchies in this order would over-weight large regions, so each region gets the value $v = \mathrm{RND} \times i$, with $\mathrm{RND}$ uniform in $[0, 1]$, and all boxes are sorted by increasing $v$. Duplicate boxes are removed only after ranking, so a box proposed by several strategies has several chances to rank high, which the authors consider desirable because agreement suggests a visually coherent region.

Mathematical Formulation

Each similarity lies in $[0, 1]$. Colour similarity is the intersection of L1-normalized colour histograms $C_i$ with 25 bins per channel (75 dimensions for three channels):

$$s_{\text{colour}}(r_i, r_j) = \sum_{k=1}^{n} \min\!\left(c_i^k, c_j^k\right).$$

The histogram of a merged region is the size-weighted average of its parts, and sizes add:

$$C_t = \frac{\mathrm{size}(r_i)\, C_i + \mathrm{size}(r_j)\, C_j}{\mathrm{size}(r_i) + \mathrm{size}(r_j)}.$$

Texture similarity $s_{\text{texture}}$ is the same intersection on SIFT-like histograms: Gaussian derivatives with $\sigma = 1$ in eight orientations for each channel, with a 10-bin histogram per orientation and channel (240 dimensions). The size term makes small regions merge first:

$$s_{\text{size}}(r_i, r_j) = 1 - \frac{\mathrm{size}(r_i) + \mathrm{size}(r_j)}{\mathrm{size}(im)},$$

where $\mathrm{size}(im)$ is the image area in pixels. Without it, one region could absorb its neighbours one at a time, producing all scales at one place and nowhere else. The fill term prefers pairs that fit into each other, with $BB_{ij}$ the tight box around both:

$$s_{\text{fill}}(r_i, r_j) = 1 - \frac{\mathrm{size}(BB_{ij}) - \mathrm{size}(r_i) - \mathrm{size}(r_j)}{\mathrm{size}(im)}.$$

The paper’s Equation 5 prints $\mathrm{size}(r_i)$ twice; the second term must be $\mathrm{size}(r_j)$, as written here. A region enclosed by another leaves little empty space in their joint box and merges early, which closes holes; two regions that barely touch leave much empty space and merge late. The strategy’s similarity is

$$s(r_i, r_j) = a_1 s_{\text{colour}} + a_2 s_{\text{texture}} + a_3 s_{\text{size}} + a_4 s_{\text{fill}}, \qquad a_k \in \{0, 1\}.$$

The weights are binary on purpose: the authors diversify by switching measures on and off rather than tuning weights.

To score proposals, the paper defines the Average Best Overlap (ABO) of a class as the mean, over its ground-truth boxes, of the best intersection over union achieved by any proposal in the same image, and the Mean Average Best Overlap (MABO) as the mean ABO over classes. The authors found recall at IoU 0.5 too insensitive, at 95% to 100% for most classes in many of their experiments, and report it only for comparison with other work.

Parameters

The paper tuned its choices on Pascal VOC 2007 trainval (its Table 3, RGB with $k = 50$ unless varied, MABO):

• Similarity measures. Alone, colour (0.635), size (0.640) and fill (0.634) were similar and texture was weakest (0.581); local binary patterns as the texture feature gave much the same (0.577). The authors suggest that the two sides of an object boundary give similar edge responses, which makes texture histograms look alike. All four together scored highest (0.676).
• Colour space. HSV (0.693 at 463 boxes) and Lab (0.690 at 328) scored best; the most invariant spaces gave few boxes and lower MABO.
• Threshold $k$. Lower $k$ gives smaller starting regions, more boxes and higher MABO: 0.676 with 395 boxes at $k = 50$, down to 0.477 with 19 boxes at $k = 1000$.

A greedy search over combinations gave three configurations (Table 4, VOC 2007 trainval):

Version	Colour spaces	Similarities	$k$	Strategies	Boxes	MABO	Time (s)
Single strategy	HSV	C+T+S+F	100	1	362	0.693	0.71
Fast	HSV, Lab	C+T+S+F, T+S+F	50, 100	8	2,147	0.799	3.79
Quality	HSV, Lab, rgI, H, I	C+T+S+F, T+S+F, F, S	50, 100, 150, 300	80	10,108	0.878	17.15

The paper does not state the hardware behind the times. The released Matlab code (as of November 2026, licensed for individual research use) adds details the paper leaves out: the initial segmentation uses $\sigma = 0.8$ and a minimum region size equal to $k$; the initial regions’ boxes are included with the lowest priority; and the Pascal demo removes boxes narrower or shorter than 20 pixels before removing duplicates. Its Felzenszwalb–Huttenlocher wrapper builds one graph whose edge weights are Euclidean distances between smoothed colour pixels, rather than intersecting three per-channel segmentations as the 2004 paper describes; scikit-image’s felzenszwalb does the same.

Complexity

The initial segmentation costs $O(n \log n)$ for $n$ pixels, as Felzenszwalb and Huttenlocher showed. Each grouping strategy then performs one merge per starting region, and each merge computes similarities with the new region’s neighbours on fixed-length histograms, so the grouping cost grows roughly linearly with the number of starting regions (reasoning from the algorithm, not a bound the paper states). The times in Table 4 grow less than proportionally with the number of strategies (8 strategies take about 5 times as long as one, 80 about 24 times), consistent with the released code, which segments the image and computes the histograms once per colour space and threshold and reuses them for every similarity set, and with larger thresholds giving fewer starting regions. Ren et al. (2015) gave about 2 s per image for a CPU implementation, an order of magnitude slower than an efficient detection network.

Implementation

The example re-implements Algorithm 1 on twelve synthetic $160 \times 240$ scenes with exact ground truth. On a background of fine two-colour noise, each scene holds one object of each of three kinds modelled on the paper’s Figure 1: a uniformly coloured ellipse; a rectangle striped in the background’s own two colours, so that only its texture differs; and a body enclosing a part of a contrasting colour. Where the paper leaves details open, the texture histograms use half-wave-rectified oriented derivatives binned over each response’s range, and Lab is rescaled to $[0, 1]$ per channel. The first part varies the similarity measures in RGB with $k = 50$, as in the paper’s Table 3; the second pools eight strategies like the fast mode, ranks them by $\mathrm{RND} \times i$ under ranking seeds 0–4, and scores the top $N$ boxes. Versions: NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2.

import heapq
import numpy as np
from scipy import ndimage as ndi
from skimage.color import rgb2hsv, rgb2lab
from skimage.segmentation import felzenszwalb

H, W = 160, 240
KINDS = ["colour", "texture", "two-part"]


def make_scene(seed):
    """Two-colour noise background; one object of each kind; exact boxes and masks."""
    rng = np.random.default_rng(seed)
    c0, c1 = np.array([0.55, 0.45, 0.35]), np.array([0.35, 0.40, 0.50])
    img = np.where((rng.random((H, W)) < 0.5)[..., None], c0, c1)
    taken, boxes, masks = np.zeros((H, W), bool), [], []
    for kind in KINDS:
        while True:
            h, w = rng.integers(30, 71, 2)
            y, x = rng.integers(0, H - h), rng.integers(0, W - w)
            if not taken[max(0, y - 4):y + h + 4, max(0, x - 4):x + w + 4].any():
                break
        taken[y:y + h, x:x + w] = True
        yy, xx = np.mgrid[0:h, 0:w]
        sub = img[y:y + h, x:x + w]
        if kind == "colour":        # uniform ellipse, colour absent from background
            m = ((yy + .5 - h / 2) / (h / 2)) ** 2 + ((xx + .5 - w / 2) / (w / 2)) ** 2 <= 1
            sub[m] = [0.8, 0.2, 0.2]
        elif kind == "texture":     # stripes in the background's own two colours
            m = np.ones((h, w), bool)
            sub[:] = np.where(((yy // 3) % 2 == 0)[..., None], c0, c1)
        else:                       # body with an enclosed contrasting part
            m = np.ones((h, w), bool)
            sub[:] = [0.2, 0.6, 0.3]
            sub[h // 4:3 * h // 4, w // 4:3 * w // 4] = [0.9, 0.9, 0.5]
        ys, xs = np.nonzero(m)
        boxes.append([x + xs.min(), y + ys.min(), x + xs.max() + 1, y + ys.max() + 1])
        masks.append(np.zeros((H, W), bool))
        masks[-1][y:y + h, x:x + w] = m
    img = np.clip(img + rng.normal(0, 0.03, img.shape), 0, 1)
    return img, np.array(boxes), masks


def colour_space(img, name):
    if name == "RGB":
        return img
    if name == "HSV":
        return rgb2hsv(img)
    lab = rgb2lab(img)              # rescale L, a, b to [0, 1]
    return np.stack([lab[..., 0] / 100, (lab[..., 1] + 128) / 255,
                     (lab[..., 2] + 128) / 255], -1)


def pixel_bins(im):
    """Per-pixel bin indices: colour (3 x 25 bins), texture (3 x 8 orientations x 10 bins)."""
    cbins, tbins = [], []
    for c in range(3):
        ch = im[..., c]
        lo, hi = ch.min(), ch.max() + 1e-9
        cbins.append(np.minimum(((ch - lo) / (hi - lo) * 25).astype(int), 24))
        gy = ndi.gaussian_filter(ch, 1.0, order=(1, 0))
        gx = ndi.gaussian_filter(ch, 1.0, order=(0, 1))
        for a in np.arange(8) * np.pi / 4:
            r = np.maximum(np.cos(a) * gx + np.sin(a) * gy, 0)   # half-wave rectified
            tbins.append(np.minimum((r / (r.max() + 1e-9) * 10).astype(int), 9))
    return cbins, tbins


def region_hists(labels, n, bins, nb):
    hs = [np.bincount((labels * nb + b).ravel(), minlength=n * nb).reshape(n, nb)
          for b in bins]
    h = np.concatenate(hs, 1).astype(float)
    return h / h.sum(1, keepdims=True)


def hierarchical_grouping(labels, cbins, tbins, terms):
    """Algorithm 1: greedily merge the most similar neighbours until one region is left.
    Returns all region boxes (x0, y0, x1, y1) and their hierarchy positions (1 = top)."""
    n = labels.max() + 1
    size = list(np.bincount(labels.ravel(), minlength=n).astype(float))
    box = [[s[1].start, s[0].start, s[1].stop, s[0].stop] for s in ndi.find_objects(labels + 1)]
    C = list(region_hists(labels, n, cbins, 25))
    T = list(region_hists(labels, n, tbins, 10))
    adj = {i: set() for i in range(n)}
    for a, b in [(labels[:, :-1], labels[:, 1:]), (labels[:-1], labels[1:])]:
        d = a != b
        for i, j in zip(a[d], b[d]):
            adj[i].add(j); adj[j].add(i)
    im_size = float(labels.size)

    def sim(i, j):                  # Eq. (6) with a_k in {0, 1}
        s = 0.0
        if "C" in terms: s += np.minimum(C[i], C[j]).sum()                 # Eq. (1)
        if "T" in terms: s += np.minimum(T[i], T[j]).sum()                 # Eq. (3)
        if "S" in terms: s += 1 - (size[i] + size[j]) / im_size            # Eq. (4)
        if "F" in terms:                                                   # Eq. (5)
            bi, bj = box[i], box[j]
            bb = (max(bi[2], bj[2]) - min(bi[0], bj[0])) * (max(bi[3], bj[3]) - min(bi[1], bj[1]))
            s += 1 - (bb - size[i] - size[j]) / im_size
        return s

    heap = [(-sim(i, j), i, j) for i in adj for j in adj[i] if i < j]
    heapq.heapify(heap)
    alive, created = set(range(n)), []
    while heap:
        _, i, j = heapq.heappop(heap)
        if i not in alive or j not in alive:
            continue
        t = len(size)
        si, sj = size[i], size[j]
        C.append((si * C[i] + sj * C[j]) / (si + sj))                      # Eq. (2)
        T.append((si * T[i] + sj * T[j]) / (si + sj))
        size.append(si + sj)
        box.append([min(box[i][0], box[j][0]), min(box[i][1], box[j][1]),
                    max(box[i][2], box[j][2]), max(box[i][3], box[j][3])])
        alive -= {i, j}
        adj[t] = (adj.pop(i) | adj.pop(j)) - {i, j}
        for k in adj[t]:
            adj[k] -= {i, j}; adj[k].add(t)
            heapq.heappush(heap, (-sim(t, k), t, k))
        alive.add(t)
        created.append(t)
    m = len(created)
    # merged regions: position m - q (last merge = whole image = 1);
    # initial regions rank below all merged ones, as in the released code
    pos = [m - q for q in range(m)] + [m + 1] * n
    return np.array([box[t] for t in created] + box[:n]), np.array(pos)


def iou(gt, boxes):
    ix = np.clip(np.minimum(gt[2], boxes[:, 2]) - np.maximum(gt[0], boxes[:, 0]), 0, None)
    iy = np.clip(np.minimum(gt[3], boxes[:, 3]) - np.maximum(gt[1], boxes[:, 1]), 0, None)
    inter = ix * iy
    area = lambda b: (b[..., 2] - b[..., 0]) * (b[..., 3] - b[..., 1])
    return inter / (area(gt) + area(boxes) - inter)


def rank_and_dedupe(boxes, pos, seed):
    v = np.random.default_rng(seed).random(len(pos)) * pos               # RND x i
    order = np.argsort(v, kind="stable")
    _, first = np.unique(boxes[order], axis=0, return_index=True)       # keep best-ranked copy
    return boxes[order][np.sort(first)]


def run(img, cspace, k, terms):
    im = colour_space(img, cspace)
    labels = felzenszwalb(im, scale=k, sigma=0.8, min_size=k)
    cb, tb = pixel_bins(im)
    return hierarchical_grouping(labels, cb, tb, terms)


def spill(img, cspace, k, masks):
    """Fraction of each object's pixels lying in initial regions that are mostly outside it."""
    labels = felzenszwalb(colour_space(img, cspace), scale=k, sigma=0.8, min_size=k)
    total = np.bincount(labels.ravel())
    out = []
    for m in masks:
        inside = np.bincount(labels[m], minlength=len(total))
        out.append(inside[inside < 0.5 * total].sum() / m.sum())
    return out


def score(best):                    # best: (scenes, 3) best overlap per object
    abo = best.mean(0)
    return (best >= 0.5).mean(), abo, abo.mean()


scenes = [make_scene(s) for s in range(12)]
configs = {"C": "C", "T": "T", "S": "S", "F": "F", "C+T+S+F": "CTSF"}
print(f"{'RGB, k=50':12s} boxes  recall   ABO colour/texture/two-part   MABO")
for name, terms in configs.items():
    best, nbox = np.zeros((12, 3)), []
    for s, (img, gt, _) in enumerate(scenes):
        boxes = np.unique(run(img, "RGB", 50, terms)[0], axis=0)
        nbox.append(len(boxes))
        best[s] = [iou(g, boxes).max() for g in gt]
    rec, abo, mabo = score(best)
    print(f"{name:12s} {np.mean(nbox):5.0f}  {rec:6.2f}   {abo[0]:.3f} / {abo[1]:.3f} / {abo[2]:.3f}   {mabo:.3f}")

# "Fast"-like diversification: 2 colour spaces x 2 similarity sets x 2 thresholds
pools = []
for img, gt, _ in scenes:
    bs, ps = [], []
    for cs in ["HSV", "Lab"]:
        for terms in ["CTSF", "TSF"]:
            for k in [50, 100]:
                b, p = run(img, cs, k, terms)
                bs.append(b); ps.append(p)
    pools.append((np.concatenate(bs), np.concatenate(ps), gt))

for top in [25, 50, 100, 200, None]:
    recs, mabos, nb = [], [], []
    for seed in range(5):
        best = np.zeros((12, 3))
        for s, (b, p, gt) in enumerate(pools):
            ranked = rank_and_dedupe(b, p, seed)[:top]
            nb.append(len(ranked))
            best[s] = [iou(g, ranked).max() for g in gt]
        rec, abo, mabo = score(best)
        recs.append(rec); mabos.append(mabo)
    label = f"top {top}" if top else "all"
    print(f"8 strategies, {label:8s} boxes {np.mean(nb):5.0f}  recall {min(recs):.2f}-{max(recs):.2f}"
          f"  MABO {min(mabos):.3f}-{max(mabos):.3f}  (ranking seeds 0-4)")
print("8 strategies, all boxes: ABO colour/texture/two-part", " / ".join(f"{a:.3f}" for a in abo))

print("object pixels in initial regions mostly outside the object (colour/texture/two-part):")
for cs, k in [("RGB", 50), ("HSV", 50), ("HSV", 100), ("Lab", 50), ("Lab", 100)]:
    sp = np.mean([spill(img, cs, k, masks) for img, _, masks in scenes], 0)
    print(f"  {cs} k={k:<3d} " + " / ".join(f"{v:.3f}" for v in sp))

Output:

RGB, k=50    boxes  recall   ABO colour/texture/two-part   MABO
C               93    0.78   0.993 / 0.442 / 0.995   0.810
T               96    0.78   0.992 / 0.469 / 0.984   0.815
S              139    0.75   0.993 / 0.472 / 0.997   0.821
F              138    0.81   0.993 / 0.478 / 0.995   0.822
C+T+S+F        123    0.83   0.993 / 0.485 / 0.995   0.824
8 strategies, top 25   boxes    25  recall 0.53-0.69  MABO 0.591-0.684  (ranking seeds 0-4)
8 strategies, top 50   boxes    50  recall 0.69-0.78  MABO 0.743-0.791  (ranking seeds 0-4)
8 strategies, top 100  boxes   100  recall 0.78-0.81  MABO 0.802-0.831  (ranking seeds 0-4)
8 strategies, top 200  boxes   200  recall 0.83-0.89  MABO 0.836-0.855  (ranking seeds 0-4)
8 strategies, all      boxes   663  recall 0.92-0.92  MABO 0.860-0.860  (ranking seeds 0-4)
8 strategies, all boxes: ABO colour/texture/two-part 0.995 / 0.587 / 1.000
object pixels in initial regions mostly outside the object (colour/texture/two-part):
  RGB k=50  0.004 / 0.323 / 0.000
  HSV k=50  0.030 / 0.204 / 0.000
  HSV k=100 0.083 / 0.485 / 0.000
  Lab k=50  0.004 / 0.286 / 0.000
  Lab k=100 0.017 / 0.563 / 0.000

Every similarity setting recovers the coloured ellipses and the two-part objects almost exactly, and every setting fails the striped objects, so the five MABO values differ by little. The sum of all four measures scores highest, as in the paper, but texture alone is not the weakest here, unlike the paper’s Table 3; that ordering rests on small differences and on this example’s own texture histogram, which the paper does not fully specify. Colour alone does worst on the striped objects, whose colour histogram matches the background. The two-part objects do not reproduce the paper’s case for fill: colour alone already recovers them. Pooling eight strategies raises recall and lifts the striped objects partly, at about five times as many boxes as the single RGB strategy.

The last block explains why the striped objects stay hard. A fifth to over half of their pixels lie in initial regions that are mostly outside the object, against a few percent for the other kinds: the initial segmentation joins stripes to the background noise of the same colours. Grouping only merges, so no region in any hierarchy can separate those pixels again, and a larger $k$ makes it worse. This is why the paper asks for starting regions that ideally do not span several objects. In the ranked pool, recall rises quickly over the first boxes, and its spread at small $N$ comes from the random factor in the ranking. The script as first run printed the five similarity lines and the five pooled lines; after it showed every setting failing the striped objects, the per-kind ABO of the pool and the measurement of initial regions spilling outside the objects were added, with the scenes, the algorithm and the earlier lines unchanged.

Properties and Behavior

Recall as reported. On Pascal VOC 2007 test (the paper’s Table 5), with recall at IoU 0.5:

• the fast mode reached recall 0.980 and MABO 0.804 with 2,134 boxes per image;
• the quality mode reached 0.991 and 0.879 with 10,097 boxes;
• the single strategy reached 0.840 and 0.690 with 289 boxes.

The text of Section 5.2.1 gives the single strategy 0.875 recall and 0.698 MABO at 286 boxes, which differs from the table. Section 5.5 also gives 0.883 MABO at all 10,097 quality boxes, and in one sentence 10,079 boxes, against the table’s 0.879. The same table compares seven other methods, among them objectness (Alexe et al.), the segment proposals of Carreira and Sminchisescu and of Endres and Hoiem, and the exhaustive search of deformable part models. On VOC 2012 trainval the authors report MABO 0.814 with 2,006 boxes (fast) and 0.886 with 10,681 (quality). For segments on the VOC 2007 segmentation test set, the quality mode gave recall 0.904 and MABO 0.730 with 22,491 regions.

Hierarchy against flat segmentations. In RGB, all boxes of one hierarchy from $k = 50$ gave MABO 0.676 with 395 boxes, against 0.659 with 387 boxes for flat Felzenszwalb–Huttenlocher segmentations at ten thresholds; combining hierarchies at $k = 50$ and 100 gave 0.719 with 625 boxes, against 0.673 with 597 for twenty flat thresholds (Table 2).

Stability across classes. The standard deviation of ABO over the 20 classes was 0.046 for the fast mode and 0.039 for the quality mode, lower than for any other method with a MABO in Table 5, which the authors take as evidence that diverse strategies work more evenly across object types. Bottle, person and plant, whose instances tend to be small, scored lowest.

Proposals and recognition. The paper’s own detector was a bag-of-visual-words model with colour SIFT descriptors, a four-level spatial pyramid and a histogram-intersection-kernel SVM, affordable only because few locations were scored. It reached 0.351 mean average precision on VOC 2010 test and 0.350 on VOC 2012. On VOC 2007 test, its mAP rose from 0.283 with the first 500 quality-mode boxes to 0.360 with all of them; adding the ground-truth boxes to the full set gave 0.377, which the authors read as their proposals being close to optimal for that recognizer.

Use in R-CNN and Fast R-CNN

R-CNN (Girshick et al., 2014) ran the fast mode on every image and took around 2,000 proposals; the authors note that the detector is agnostic to the proposal method and chose selective search to compare directly with earlier detectors. In the tech report’s ILSVRC2013 experiments, images were first resized to a width of 500 pixels because selective search is not scale invariant and the number of regions depends on resolution; on val it then gave on average 2,403 proposals per image with 91.6% recall at IoU 0.5, against about 98% on Pascal.

Fast R-CNN (Girshick, 2015) took precomputed proposals, typically around 2,000 per image at test time, and its reported 0.3 s per image excludes the time to compute them. Sweeping the quality mode from 1,000 to 10,000 proposals per image on VOC 2007 test, Girshick found that mAP rose and then fell slightly while average recall kept rising. With a medium-sized network, replacing each selective search box by its closest box from a dense set of about 45,000 per image cost only one point of mAP, to 57.7%, but adding dense boxes to 2,000 selective search boxes lowered mAP more than adding further selective search boxes did. Once the network ran in a fraction of a second, the CPU-bound proposal step dominated the running time, which Faster R-CNN removed by learning proposals on the detector’s shared features.

Limitations

• Bound by the starting regions. Grouping never splits a region, so an object whose pixels the initial segmentation joins to its surroundings cannot be recovered, as the example shows.
• Hand-designed and slow. Its features and similarities are fixed and cannot be trained with the detector, and it takes seconds per image on a CPU.
• Weak ranking. The order is a randomized version of hierarchy depth, not an objectness score, so the first boxes are a noisy sample; in the example their recall varies with the random factor.
• Resolution dependence. The minimum region size counts pixels, and Felzenszwalb and Huttenlocher’s threshold $k/|C|$ depends on a region’s size $|C|$ in pixels, so the number of boxes changes with image size, as the R-CNN authors found on ILSVRC.

Variants

• ICCV 2011 version. Van de Sande et al. merged regions by the sum of a size term and a texture term only, and diversified over RGB, opponent colour, normalized RGB and hue. They reported 96.7% recall with 1,536 locations per image on VOC 2007 test.
• Combination with other proposals. The authors pooled their regions with those of CPMC (Carreira and Sminchisescu) and of Endres and Hoiem, raising segment MABO from 0.730 to 0.758 with 25,355 regions, as their diversification argument predicts.
• Successors. Faster proposal methods followed (see region proposals), and the region proposal network of Faster R-CNN replaced external proposals in later two-stage detectors.