Hard Negative Mining

Hard negative mining trains the classifier inside a detector on the background examples it currently gets wrong, instead of on all background or on a random sample of it. A detector scores a huge number of candidate windows, proposals or anchors, almost all of them background, and most of that background is easy: blank wall, sky, road. The few background patches that look like the object, the “hard negatives”, decide how many false alarms the detector makes, but a random sample rarely contains them. Mining finds them with the current model and puts them in the training set. The idea is also called bootstrapping, its original name, data mining of hard examples, and, when positives are selected too, hard example mining.

Sliding window detection introduces the retraining step in outline; the focal loss, which reweights the cross-entropy loss instead of selecting examples, is the main alternative.

Purpose

Detection turns one image into many classification problems, and the classes are badly unbalanced. Felzenszwalb et al. (2010) note that a single image can yield $10^5$ negative examples for a scanning-window classifier, which can make it infeasible to consider all negatives at once. Shrivastava, Gupta and Girshick (2016) put the imbalance as high as 100,000 background examples per object for sliding-window detectors such as deformable part models, and still around 70:1 for detectors that classify region proposals.

Training on all negatives is expensive and spends most of its effort on examples already classified correctly; Lin et al. (2017) add that, in large numbers, easy negatives can overwhelm training and lead to degenerate models. Training on a random subset is cheap, but the rare confusing patterns that become false positives at test time are barely represented. Mining keeps the training set small and fills it with the negatives that matter.

When to Use It

Mining helps when a classifier is trained on candidates that are mostly background and the background contains rare look-alikes: sliding-window classifiers, the stages of a cascade, SVMs on cached region features as in R-CNN, the region head of a two-stage detector, and dense heads with many anchors. It needs negatives known to be negative: images free of the object, or exhaustively annotated ones.

It matters less when a proposal stage has already removed most easy negatives, as in two-stage detectors, and in dense one-stage detectors Lin et al. (2017) found the focal loss more effective than the mining variants they tried.

How It Works

Bootstrapping

The original procedure alternates between training and searching. Starting from all positives $P$ and a random set of negatives $N_0$, round $t$ trains a classifier $f_t$, scans the object-free training images $D^-$, and adds the windows that it scores above a threshold $\tau$:

$$f_t = \operatorname{train}(P, N_t), \qquad N_{t+1} = N_t \cup \{\, x \in D^- : f_t(x) > \tau \,\}.$$

With $\tau$ at the decision threshold, the added windows are exactly the training-set false positives. Shrivastava et al. (2016) credit Sung and Poggio’s face detection work of the mid-1990s, “if not earlier”, with introducing the idea (they cite a 1994 MIT AI Memo, No. 1521): the set of background examples was grown from the windows on which the detector raised a false alarm. Felzenszwalb et al. (2010) trace it to the same work and to Rowley, Baluja and Kanade’s neural-network face detector.

Dalal and Triggs (2005) gave the procedure its standard form for HOG with a linear support vector machine. Their initial negative set was 12,180 patches sampled at random from 1,218 person-free training photos. A preliminary detector was trained, the 1,218 photos were searched exhaustively for false positives, and the detector was retrained on the initial patches plus these hard examples, subsampled if necessary so that the final training set fitted in 1.7 Gb of RAM for SVM training. Retraining improved their default detector by 5% at $10^{-4}$ false positives per window, and further rounds made little difference, so they used one. Viola–Jones cascades apply the same idea per stage, training each new stage on the windows that the earlier stages wrongly accept.

Margin-sensitive mining with a guarantee

For the training of deformable part models, Felzenszwalb et al. (2010) turned bootstrapping into an algorithm with a convergence proof. For an SVM with weights $\beta$, they call an example hard when it is misclassified or inside the margin, $y f_\beta(x) < 1$, and easy when it is outside the margin; examples on the margin are neither. Their algorithm trains on a cache of examples, stops when every hard example of the full training set is already in the cache, and otherwise may drop easy examples from the cache and adds at least one new hard one. They prove that it terminates and that the model it returns is the one trained on the whole set. The proof relies on the hinge loss: examples outside the margin have zero loss and do not affect the solution, so leaving them out changes nothing. The deformable part models article gives the algorithm and its use with latent variables.

Shrivastava et al. (2016) separate this SVM version from the bootstrapping used with other models, such as shallow neural networks and boosted trees, which retrains on harvested false positives, is usually iterated once and has no convergence proof. In our reading, the guarantee does not carry over to the cross-entropy loss, because under it no example has exactly zero loss, so every left-out negative changes the solution a little.

Online hard example mining

Bootstrapping freezes the model while it searches tens or hundreds of images for new examples. That suits an SVM trained to convergence on a cache, but a convolutional network trained by stochastic gradient descent for hundreds of thousands of steps would be slowed down badly by such pauses. Fast R-CNN (Girshick, 2015) sampled instead of mining: each mini-batch of 128 regions of interest took 64 from each of two images, 25% of them foreground proposals (IoU at least 0.5 with a ground-truth box) and the rest background proposals with maximum IoU in $[0.1, 0.5)$. Girshick wrote that the lower bound of 0.1 appears to act as a heuristic for hard example mining.

Online hard example mining (OHEM), by Shrivastava, Gupta and Girshick (2016), moves mining inside each SGD step. Each image comes with about 2,000 proposals, and the convolutional features are computed once per image, so the extra cost of scoring all of them is small. For each image the method:

1. runs the region head forward on all proposals $R$ and computes each one’s loss $\ell_i$, the sum of the classification and box-regression losses;
2. removes near-duplicates by non-maximum suppression on the losses at IoU 0.7, since overlapping regions have correlated losses and would be counted twice;
3. keeps the $B/N$ regions with the highest loss and backpropagates only through them.

With $N = 2$ images and $B = 128$, about 4,000 proposals are scored per step and 128 are trained on, so the backward pass costs no more than in standard training. The implementation keeps a read-only copy of the region network for the forward pass over all proposals. OHEM drops both of Fast R-CNN’s heuristics, the background IoU floor and the 1:3 foreground-to-background ratio: if a class were neglected, its loss would grow until its examples were selected. The authors call it hard example mining rather than hard negative mining because it selects among all classes, positives included.

Fixed-ratio selection in dense detectors

Dense detectors face the imbalance on every image, and most combine mining or sampling with a fixed ratio. Faster R-CNN’s region proposal network (Ren et al., 2015) samples 256 anchors per image at random, with positives and negatives at a ratio of up to 1:1, padding with negatives when an image has fewer than 128 positives. SSD (Liu et al., 2016) mines: after matching default boxes to objects, it sorts the negatives by their confidence loss and keeps the highest, at most three negatives per positive, which the authors report gives faster optimization and more stable training. In our reading, it is a top-$k$ selection by loss like OHEM’s, without the deduplication step and with the number of negatives tied to the number of positives; the SSD article covers its matching and loss.

Reweighting instead of mining

The focal loss of Lin et al. (2017) keeps every example and changes its weight. Writing $p_t$ for the predicted probability of the true class, it multiplies the cross-entropy by a factor that vanishes for well-classified examples:

$$\mathrm{FL}(p_t) = -(1 - p_t)^{\gamma} \log p_t , \qquad \gamma \ge 0 .$$

Mining gives each example a weight of 1 or 0 according to its rank in the loss; the focal loss gives a weight that falls smoothly as an example becomes easy, so easy negatives still contribute, but little. The authors present it as an alternative to bootstrapping and hard example mining, and note that it plays the opposite role of a robust loss such as the Huber loss, which down-weights the examples with large errors. With it, their one-stage detector RetinaNet was trained on all of about 100,000 anchors per image, normalizing the loss by the number of anchors assigned to objects. The one-stage object detectors article works through the loss and its weighting factor $\alpha$.

How to Apply It

The example trains a sliding-window classifier with and without bootstrapped negatives and measures its false positives per image (FPPI) at a fixed recall. Each $162 \times 162$ synthetic scene has a brightness ramp, 12 random strokes as clutter and Gaussian noise. The target is a ring of radius 7 to 9 pixels in a $24 \times 24$ box. Three distractors resemble it in part: a “C” (a ring with a gap of 70° to 110°), a square outline and a filled disc. Training uses 60 scenes with 4 targets and 2 distractors each for positives, and 60 negative images with clutter and 4 distractors but no targets, in the role of Dalal and Triggs’s person-free photos. The test set has 50 scenes with 4 targets and 4 distractors each.

The classifier is HOG from scikit-image (9 orientations, $6 \times 6$ pixel cells, $2 \times 2$ cell blocks), computed once per image so that a window’s 324-dimensional feature is a slice of the block grid. Windows slide one cell (6 pixels) at a time at a single scale. A linear logistic regression, that is, a cross-entropy classifier, is fitted with scikit-learn’s deterministic L-BFGS solver and the default $C = 1$. Each positive is the grid window that best overlaps a training target. At test time, greedy non-maximum suppression at IoU 0.3 merges the windows, a detection is correct if it overlaps an unmatched target with IoU at least 0.5, and the score threshold is lowered until recall reaches 0.8 and then 0.9.

Training variants start from 10 random windows per negative image, as Dalal and Triggs did. Bootstrapping scans all 34,560 windows of the negative images and adds the hard ones, for at most three rounds, stopping at the first round that adds nothing. The sources define “hard” in two ways, so both rules are run from the same start: windows scored above 0, the false positives (Dalal and Triggs), and windows scored above $-1$, inside the margin (Felzenszwalb et al.; the margin has no special status for logistic regression, so this is an analogy). Two controls follow: as many random windows as the first false-positive round ends with, and all negative windows. The script loops over five data seeds and runs in about 15 seconds. Versions: NumPy 2.3.5, scikit-image 0.25.2 and scikit-learn 1.7.2.

import numpy as np
from skimage.feature import hog
from sklearn.linear_model import LogisticRegression

S, W, CELL = 162, 24, 6                       # image size, window size, HOG cell (= stride)

def draw(layer, kind, cx, cy, r, lw, c, rng):
    y, x = np.mgrid[0:S, 0:S]
    dx, dy = x - cx, y - cy
    if kind == "square":
        d = np.abs(np.maximum(np.abs(dx), np.abs(dy)) - r)
    elif kind == "disc":
        d = np.maximum(np.hypot(dx, dy) - r, 0)
    else:                                     # "ring" (the target) or "C" (ring with a gap)
        d = np.abs(np.hypot(dx, dy) - r)
        if kind == "C":
            a0, gap = rng.uniform(0, 2 * np.pi), np.deg2rad(rng.uniform(70, 110))
            d[(np.arctan2(dy, dx) - a0) % (2 * np.pi) < gap] = 99
    np.maximum(layer, c * np.clip(lw / 2 + 0.5 - d, 0, 1), out=layer)

def stroke(layer, rng):
    p = rng.uniform(0, S, 2); a = rng.uniform(0, np.pi); L = rng.uniform(15, 60)
    q = p + L * np.array([np.cos(a), np.sin(a)]); d = q - p
    y, x = np.mgrid[0:S, 0:S]
    t = np.clip(((x - p[0]) * d[0] + (y - p[1]) * d[1]) / (d @ d), 0, 1)
    dist = np.hypot(x - p[0] - t * d[0], y - p[1] - t * d[1])
    np.maximum(layer, rng.uniform(0.3, 0.9) * np.clip(rng.uniform(1, 2.5) / 2 + 0.5 - dist, 0, 1), out=layer)

def scene(rng, n_targets, n_distract):
    """Returns image, target boxes and distractor boxes, boxes as (x0, y0, x1, y1)."""
    layer = np.zeros((S, S))
    for _ in range(12):
        stroke(layer, rng)
    kinds = ["ring"] * n_targets + list(rng.choice(["C", "square", "disc"], n_distract))
    centres = []
    while len(centres) < len(kinds):
        c = rng.uniform(14, S - 14, 2)
        if all(np.hypot(*(c - o)) > 26 for o in centres):
            centres.append(c)
    boxes = {"ring": [], "other": []}
    for k, (cx, cy) in zip(kinds, centres):
        draw(layer, k, cx, cy, rng.uniform(7, 9), rng.uniform(1.5, 2.5), rng.uniform(0.5, 1.0), rng)
        boxes["ring" if k == "ring" else "other"].append((cx - 12, cy - 12, cx + 12, cy + 12))
    y, x = np.mgrid[0:S, 0:S] / S
    ramp = rng.uniform(0.1, 0.3) + rng.uniform(-0.1, 0.1) * x + rng.uniform(-0.1, 0.1) * y
    img = ramp + layer + rng.normal(0, 0.06, (S, S))
    return img, np.array(boxes["ring"]).reshape(-1, 4), np.array(boxes["other"]).reshape(-1, 4)

def windows(img):
    """HOG once per image; every 24 x 24 window on the 6-pixel cell grid -> (features, boxes)."""
    H = hog(img, orientations=9, pixels_per_cell=(CELL, CELL), cells_per_block=(2, 2),
            block_norm="L2-Hys", feature_vector=False)
    nb = W // CELL - 1                        # 3 x 3 blocks per window
    n = H.shape[0] - nb + 1
    feats = np.array([H[i:i + nb, j:j + nb].ravel() for i in range(n) for j in range(n)])
    boxes = np.array([(CELL * j, CELL * i, CELL * j + W, CELL * i + W) for i in range(n) for j in range(n)], float)
    return feats, boxes

def iou(a, B):
    w = np.clip(np.minimum(a[2], B[:, 2]) - np.maximum(a[0], B[:, 0]), 0, None)
    h = np.clip(np.minimum(a[3], B[:, 3]) - np.maximum(a[1], B[:, 1]), 0, None)
    inter = w * h
    return inter / ((a[2] - a[0]) * (a[3] - a[1]) + (B[:, 2] - B[:, 0]) * (B[:, 3] - B[:, 1]) - inter)

def nms(boxes, scores, thr=0.3):
    order, keep = np.argsort(-scores), []
    while order.size:
        i = order[0]; keep.append(i)
        order = order[1:][iou(boxes[i], boxes[order[1:]]) <= thr]
    return np.array(keep)

def fppi_at_recall(model, test, recalls=(0.8, 0.9)):
    dets = []                                 # (score, image index, box)
    for k, (F, B, gt, other) in enumerate(test):
        s = model.decision_function(F)
        for i in nms(B, s):
            dets.append((s[i], k, B[i]))
    dets.sort(key=lambda d: -d[0])
    used = [np.zeros(len(t[2]), bool) for t in test]
    n_gt = sum(len(t[2]) for t in test)
    tp = fp = fp_dis = 0; out = {}
    for s, k, b in dets:
        gt, other = test[k][2], test[k][3]
        o = iou(b, gt) if len(gt) else np.zeros(0)
        j = np.argmax(o) if len(o) else -1
        if j >= 0 and o[j] >= 0.5 and not used[k][j]:
            used[k][j] = True; tp += 1
        else:
            fp += 1; fp_dis += len(other) > 0 and iou(b, other).max() >= 0.5
        for r in recalls:
            if r not in out and tp >= r * n_gt:
                out[r] = (fp / len(test), fp_dis / max(fp, 1))
    return out

def fit(Xp, Xn):
    X = np.vstack([Xp, Xn]); y = np.r_[np.ones(len(Xp)), np.zeros(len(Xn))]
    return LogisticRegression(C=1.0, max_iter=5000).fit(X, y)

def run(seed, verbose):
    rng = np.random.default_rng(seed)
    pos = []
    for _ in range(60):                       # positives: best grid window on each target
        img, gt, _ = scene(rng, 4, 2)
        F, B = windows(img)
        pos += [F[np.argmax(iou(g, B))] for g in gt]
    Xp = np.array(pos)
    negF, onD, img_id = [], [], []
    for k in range(60):                       # negative images: clutter and distractors, no targets
        img, _, other = scene(rng, 0, 4)
        F, B = windows(img)
        negF.append(F); img_id += [k] * len(F)
        onD += [iou(b, other).max() >= 0.5 for b in B]
    Xn_all, onD, img_id = np.vstack(negF), np.array(onD), np.array(img_id)
    test = []
    for _ in range(50):
        img, gt, other = scene(rng, 4, 4)
        F, B = windows(img)
        test.append((F, B, gt, other))

    idx0 = np.concatenate([rng.choice(np.flatnonzero(img_id == k), 10, replace=False) for k in range(60)])
    model0 = fit(Xp, Xn_all[idx0])
    results = [("random, 10 per image", len(idx0), onD[idx0].mean(), fppi_at_recall(model0, test))]
    summary = [results[0][3]]
    for rule, thr in [("FP", 0.0), ("margin", -1.0)]:   # mine score > 0 (false positives) or > -1 (inside margin)
        idx, model = idx0, model0
        for rnd in range(1, 4):               # bootstrapping: at most 3 rounds, stop when nothing new
            hard = np.flatnonzero(model.decision_function(Xn_all) > thr)
            new = np.setdiff1d(hard, idx)
            if len(new) == 0:
                results.append((f"{rule} round {rnd}: no new negatives", len(idx), None, results[-1][3]))
                break
            idx = np.union1d(idx, new)
            model = fit(Xp, Xn_all[idx])
            results.append((f"{rule} round {rnd} (+{len(new)})", len(idx), onD[new].mean(),
                            fppi_at_recall(model, test)))
            if rule == "FP" and rnd == 1:
                n_match = len(idx)
        summary.append(results[-1][3])    # result after the last round
    ridx = rng.choice(len(Xn_all), n_match, replace=False)
    results.append(("random, same count as FP round 1", n_match, onD[ridx].mean(), fppi_at_recall(fit(Xp, Xn_all[ridx]), test)))
    results.append(("all negative windows", len(Xn_all), onD.mean(), fppi_at_recall(fit(Xp, Xn_all), test)))
    summary += [results[-2][3], results[-1][3]]
    if verbose:
        print(f"seed {seed}: {len(Xp)} positives, {len(Xn_all)} negative windows "
              f"({onD.mean():.1%} on a distractor), 200 test targets in 50 images")
        print(f"{'training negatives':32s}{'count':>7s}{'on distr.':>10s}{'FPPI@0.8':>10s}{'FPPI@0.9':>10s}{'FP on distr.':>13s}")
        for name, n, d, out in results:
            ds = "-" if d is None else f"{d:.1%}"
            print(f"{name:32s}{n:7d}{ds:>10s}{out[0.8][0]:10.2f}{out[0.9][0]:10.2f}{out[0.9][1]:13.0%}")
    return [out[0.9][0] for out in summary]

if __name__ == "__main__":
    rows = [run(s, verbose=(s == 0)) for s in range(5)]
    print("\nFPPI at recall 0.9, seeds 0-4:")
    names = ["random 10/img", "FP-mined", "margin-mined", "random, matched", "all"]
    for name, col in zip(names, np.array(rows).T):
        print(f"{name:16s}" + " ".join(f"{v:5.2f}" for v in col) + f"   range {col.min():.2f}-{col.max():.2f}")

seed 0: 240 positives, 34560 negative windows (2.8% on a distractor), 200 test targets in 50 images
training negatives                count on distr.  FPPI@0.8  FPPI@0.9 FP on distr.
random, 10 per image                600      2.7%      0.50      1.18         100%
FP round 1 (+218)                   818     99.5%      0.16      0.56         100%
FP round 2: no new negatives        818         -      0.16      0.56         100%
margin round 1 (+353)               953     94.9%      0.22      0.60         100%
margin round 2: no new negatives    953         -      0.22      0.60         100%
random, same count as FP round 1    818      2.6%      0.84      1.50         100%
all negative windows              34560      2.8%      0.34      0.58         100%

FPPI at recall 0.9, seeds 0-4:
random 10/img    1.18  0.98  1.14  1.22  1.00   range 0.98-1.22
FP-mined         0.56  0.42  0.48  0.52  0.26   range 0.26-0.56
margin-mined     0.60  0.52  0.58  0.62  0.36   range 0.36-0.62
random, matched  1.50  1.18  1.02  1.40  1.12   range 1.02-1.50
all              0.58  0.62  0.60  0.72  0.48   range 0.48-0.72

Only 2.8% of the negative windows overlap a distractor, so the 600 random negatives contain about 16 of them, and the model trained on them pays for it: at recall 0.9 it makes about one false positive per image on every seed. On seed 0 every false positive at that operating point, in every variant, lies on a distractor; the problem is the rare look-alikes, not the clutter strokes.

One round of mining fixes most of it. Of the 218 windows it adds, 99.5% sit on distractors, and false positives per image at recall 0.9 fall by about half on seed 0 and by more on the other seeds. The control shows that the gain comes from which negatives are added, not how many: 818 random negatives, the same count, are worse than 600 on four of the five seeds and behind mining on all of them. On seed 0 the second round finds no negative window scored above 0, so mining stops after one round, in line with Dalal and Triggs and with the R-CNN authors’ report that mean average precision stopped increasing after a single pass. The margin rule adds more windows, 353, of which about 5% do not overlap a distractor at IoU 0.5, and ends slightly worse than the false-positive rule on every seed; in this example the extra examples near the boundary did not help.

Training on all 34,560 negative windows matches mining at recall 0.9 on seed 0 but is worse at recall 0.8 there, and worse at recall 0.9 on the other four seeds, with 42 times as many negatives. In our reading, two effects may contribute: the unweighted cross-entropy sums over tens of thousands of easy background windows, the imbalance the focal loss targets, and scikit-learn’s $C$ multiplies the summed loss, so the same $C$ regularizes less with more data. The example does not separate the two.

The script was changed after its first run, which mined only windows scored above 0 and printed all three rounds; on seed 0, rounds 2 and 3 added no windows. The margin rule was then added, since the sources define hard examples in these two ways and the first rule had stopped finding new windows; in that intermediate edit the two control rows were dropped by mistake, then restored. The loop was made to stop at the first round that adds no windows and to print that round as such, with a dash in place of its share on distractors; and the per-seed summary was changed to show each rule’s result after its last round. The data, the classifier and the evaluation are unchanged.

Variants

Besides the forms above, two related practices are often grouped with mining. Random sampling at a fixed ratio, as in Fast R-CNN and the region proposal network, balances the classes without looking at the loss. And embedding losses mine hard or semi-hard negatives within a batch, as in the triplet loss training of FaceNet; the FaceNet paper article describes why it avoided the hardest ones.

Best Practices

• Start from all positives and a random sample of negatives, and expect one or two offline rounds to be enough.
• Keep a ratio when sampling at random. OHEM’s authors report that removing Fast R-CNN’s 1:3 ratio, or raising it, lowers accuracy by about 3 mAP points.
• Measure false positives per image at a fixed recall on held-out images, not the training loss or the per-window error.

Pitfalls

• Unlabelled objects mined as negatives. When annotations are incomplete, a “false positive” may be a real object. The R-CNN authors did not mine negatives from ILSVRC’s train images for this reason, and mined from a subset of the validation images instead.
• Negatives that overlap objects. A window covering half an object is not clean background. R-CNN’s SVMs took as negatives only proposals with IoU below 0.3 to every instance and ignored those in between; how detectors set such thresholds is the subject of label assignment.

Evidence and Impact

Shrivastava et al. (2016) describe bootstrapping as appearing in the training of most successful object detectors before Fast R-CNN, including R-CNN and SPPnet, whose SVMs were still trained with hard negative mining.

Shrivastava et al. (2016) measured OHEM with Fast R-CNN and VGG16. On PASCAL VOC 2007 test, training on VOC 2007 trainval, mAP rose from 67.2% (Fast R-CNN retrained with their schedule) to 69.9%; training on VOC 2007 and 2012 trainval, OHEM reached 74.6% against the 70.0% reported in the Fast R-CNN paper. On VOC 2012 test, training on VOC 2012 trainval, it reached 69.8% against Fast R-CNN’s 65.7%. On COCO test-dev, training on the COCO train set, AP rose from 19.7% to 22.6% and AP at IoU 0.5 from 35.9% to 42.5%; the Fast R-CNN figures there come from the leaderboard. Their ablation on VOC 2007 isolates the selection. Standard training with mini-batches of 2,048 regions and a retuned learning rate, to let easy examples fade out of the gradient by themselves, gained about 1 point (68.7% against 67.5% for VGG16 with 128 regions, both with two images per batch and no background IoU floor); OHEM, with 128 selected regions, was more than 1 point better again at 69.9%, and reached the lowest training loss of the variants compared.

In a one-stage detector the comparison reverses. Lin et al. (2017) tested OHEM, and OHEM with SSD’s 1:3 ratio, in RetinaNet with a ResNet-101-FPN backbone, trained on COCO trainval35k and evaluated on minival at 600 pixels. The best OHEM setting (batch of 128 anchors, NMS at 0.5, no ratio) reached 32.8 AP and the best 1:3 setting 31.1 AP, against 36.0 AP with the focal loss; the authors note that they tried other settings without better results. In our reading, the two answers divided the field: dense one-stage heads moved to reweighting all anchors, while sampling with fixed ratios stayed in the proposal stage and region heads of two-stage detectors.