Object detection
Detection finds every object in an image, draws a box around it and names it. This page covers the detection pipeline, two-stage detectors (R-CNN, Fast R-CNN, Faster R-CNN) and one-stage detectors (YOLO, SSD). It also covers the numericals: IoU, non-max suppression, precision, recall and mAP.
Classification vs detection
Image classification answers "what is in the image?" with one label ("Car"). Object detection answers "what is where?". For each object it gives a class, an exact bounding box and a confidence score. One image can contain many objects of many classes, so the output size changes.
The detection pipeline
- Input image (or video).
- Pre-processing: change the image to the format the model needs (resize, normalise).
- Feature extraction: the feature extractor splits the image into regions and gets features from each.
- Classification: use the features to put each region in a category.
- Localisation: compute the bounding box coordinates that surround each object.
- Non-max suppression (NMS): when several boxes cover the same object, keep the best box and delete the overlaps.
- Output: the original image marked with boxes and labels.
Detection basics
The high-level model has three parts. The input is an image. A backbone CNN extracts features. A detection head predicts three values for many candidate boxes. The values are the class, the box (x, y, width, height) and the confidence score (how likely the box holds an object).
Two box formats.
Corner format: $(x_{min},y_{min},x_{max},y_{max})$. Centre format: $(x_c,y_c,w,h)$.
$$ w=x_{max}-x_{min},\quad h=y_{max}-y_{min},\quad x_c=\frac{x_{min}+x_{max}}2,\quad y_c=\frac{y_{min}+y_{max}}2 $$Image coordinates: origin at the top-left, $x$ goes right and $y$ goes down. The slide also uses $[x_{min},y_{min},\text{width},\text{height}]$.
Box $(2,2,8,8)$: $w=h=6$, centre $(5,5)$. In centre format that is $(5,5,6,6)$.
Training: labelled images go through the model. The model compares its predictions with the ground truth. The loss has two parts: classification loss (is the class right?) and localisation loss (is the box accurate?). Backpropagation then uses the gradients to update the model: $L=L_{cls}+\lambda L_{loc}$.
Evaluation: IoU (overlap quality) and mAP (mean average precision). Both are explained below.
Two-stage vs one-stage detectors
Two-stage detectors first propose candidate regions. Then they classify each region and refine its box. Examples: R-CNN, Fast R-CNN, Faster R-CNN. Single-stage detectors predict boxes and class probabilities for every area of the image in one pass. Examples: YOLO (You Only Look Once) and SSD (Single Shot MultiBox Detector).
The slide diagram of the two-stage idea has these steps. Stage 1 gives region proposals (e.g. boxes on a footballer, a flag, a ball, and background). The network extracts features for each region and a classifier labels it (person, flag, ball, none). Then bounding box regression changes the box of each proposal from $(w,h)$ to a better fit $(w^*,h^*)$.
R-CNN (Regions with CNN features)
R-CNN is one of the first deep-learning detectors (Girshick et al., 2014). It detects and classifies objects with region proposals and a CNN. It does not know where the objects are, so it first generates candidate regions.
Steps
- Region proposals with selective search:
- Initial segmentation: split the image into many small regions by colour, texture and intensity.
- Region comparison: compare neighbouring regions by colour, texture, size and shape similarity.
- Region merging: merge similar neighbours into larger regions. Do this at multiple scales.
- Generate proposals: the resulting rectangles. The original R-CNN generates about 2,000 proposals per image.
- Resize (warp) each proposal to a fixed size, because proposals have different widths and heights. With AlexNet, warp each region to $227\times227$.
- Extract features: send each warped region separately through a pretrained CNN (AlexNet; a 4096-D feature vector per region). The features help to separate objects from background.
- Classify each region with class-specific SVMs (one-vs-all), to get class scores (e.g. person 0.92, horse 0.05).
- Bounding box regression refines the proposed box.
- NMS removes duplicate overlapping detections.
Drawback of R-CNN: it is very slow. The CNN runs on about 2,000 regions per image. For example, at 20 ms per forward pass, one image takes $2000\times20=40{,}000$ ms = 40 s (illustrative). Training has several stages (CNN, then SVMs, then box regressors). The system must store the features on disk. Selective search is a separate CPU algorithm that does not learn.
Fast R-CNN
Fast R-CNN still uses selective search for proposals. It removes the repeated CNN work with these steps:
- Pass the entire image through the CNN once to get a feature map.
- Map the region proposals onto the feature map.
- Apply RoI pooling to turn each region of the feature map into a fixed-size feature.
- Send the result to FC layers. They output the class (softmax) and the box refinement together. These layers replace the SVMs and the separate regressor.
RoI pooling
Region of Interest pooling crops features, not pixels. To do this, project the proposal onto the feature map and align it to the grid cells ("snap"). Divide it into a fixed grid of roughly equal sub-regions (e.g. $2\times2$, in practice $7\times7$). Then max-pool inside each sub-region. The output has the same size ($512\times2\times2$, or $512\times7\times7$ in practice) for any proposal size. Known problem: snapping makes the region features slightly misaligned. RoIAlign in Mask R-CNN later fixed this.
A region on the feature map covers a $4\times4$ patch and the output must be $2\times2$. Take the max of each $2\times2$ block:
| 429 | 505 | 686 | 856 |
| 261 | 792 | 412 | 640 |
| 633 | 653 | 851 | 751 |
| 608 | 913 | 713 | 657 |
| 792 | 856 |
| 913 | 851 |
If a proposal covers $5\times7$ cells and the output must be $2\times2$, the sub-regions are roughly $2$-$3$ rows by $3$-$4$ columns. The output size stays $2\times2$ for any proposal size.
Faster R-CNN
Faster R-CNN replaces the external selective search with a learnable network, the Region Proposal Network (RPN). The RPN slides over the shared CNN feature map. At each location it scores a set of reference boxes called anchors (typically $k=9$: 3 scales $\times$ 3 aspect ratios) as object or not object. It also regresses box corrections. The top proposals then go through RoI pooling and the same classification and regression head as Fast R-CNN. All parts share one backbone and train end to end, so proposals cost almost nothing.
R-CNN vs Fast R-CNN vs Faster R-CNN
| Aspect | R-CNN | Fast R-CNN | Faster R-CNN |
|---|---|---|---|
| Proposals from | Selective search (~2000) | Selective search | Region Proposal Network (learned) |
| CNN runs on | Each warped proposal separately ($227\times227$) | Whole image once | Whole image once (shared by RPN and head) |
| Fixed-size features by | Warping the image region | RoI pooling on the feature map | RoI pooling |
| Classifier | Class-specific SVMs | Softmax in a network head | Softmax in a network head |
| Box refinement | Separate regressor | Head in the same network | Head in the same network |
| Speed | Slowest | Faster, bottleneck is selective search | Fastest of the three |
| Training | Multi-stage | Single stage (proposals fixed) | End to end |
Two-stage vs one-stage
| Feature | Two-stage (R-CNN family) | One-stage (YOLO, SSD) |
|---|---|---|
| Pipeline | Propose regions, then classify and refine | Predict boxes and classes directly in one pass |
| Speed | Slower | Faster, real-time capable |
| Accuracy | Usually higher, especially for small objects (older generation) | Slightly lower historically, now close |
| Complexity | More complex, more components | Simpler, a single network |
| Typical use | Accuracy-critical tasks | Video, robotics, mobile |
One-stage detectors: YOLO and SSD
YOLO divides the image into an $S\times S$ grid. Each cell predicts $B$ boxes (each with $x,y,w,h$ and a confidence) and $C$ class probabilities. This takes a single forward pass. The output tensor is $S\times S\times(5B+C)$.
$S=7$, $B=2$, $C=20$ classes: $7\times7\times(5\times2+20)=7\times7\times30$ values, i.e. $1470$ numbers, and $7\times7\times2=98$ candidate boxes per image (R-CNN has $\approx2000$ proposals). NMS removes the overlaps.
SSD predicts boxes from several feature maps of different resolution, so it handles objects of various sizes. It also needs only one pass.
IoU: Intersection over Union
IoU measures how much a predicted box overlaps the ground-truth box. It is 0 for no overlap and 1 for a perfect match.
Boxes in $(x_{min},y_{min},x_{max},y_{max})$ format: $P=(x_1,y_1,x_2,y_2)$, $G=(x_1',y_1',x_2',y_2')$.
$$ x_{left}=\max(x_1,x_1'),\ \ y_{top}=\max(y_1,y_1'),\ \ x_{right}=\min(x_2,x_2'),\ \ y_{bottom}=\min(y_2,y_2') $$ $$ A_I=\max(0,x_{right}-x_{left})\cdot\max(0,y_{bottom}-y_{top}),\qquad A_U=A_P+A_G-A_I $$ $$ \text{IoU}=\frac{A_I}{A_U} $$$A_P,A_G$ are the box areas, $A_I$ the intersection area (zero if the boxes do not overlap), $A_U$ the union area. Subtract $A_I$ once, because the sum of the two areas counts the overlap twice.
Slide example. $P=(2,2,8,8)$, $G=(4,4,10,10)$.
Step 1: $A_P=(8-2)(8-2)=6\times6=36$. Step 2: $A_G=(10-4)(10-4)=36$.
Step 3: overlap: $x_{min}=\max(2,4)=4$, $y_{min}=\max(2,4)=4$, $x_{max}=\min(8,10)=8$, $y_{max}=\min(8,10)=8$. $A_I=(8-4)(8-4)=4\times4=16$.
Step 4: $A_U=36+36-16=56$.
Step 5: $\text{IoU}=16/56=0.2857\approx0.29$. This is a poor match (below the usual 0.5 threshold). At IoU 0.5 this prediction is a false positive.
Practice 1. $P=(0,0,4,4)$, $G=(2,2,6,6)$. $A_P=A_G=16$. Overlap: $(2,2)$ to $(4,4)$, $A_I=2\times2=4$. $A_U=16+16-4=28$. IoU $=4/28=1/7\approx0.143$.
Practice 2 (no overlap). $P=(0,0,2,2)$, $G=(5,5,8,8)$: $x_{right}-x_{left}=\min(2,8)-\max(0,5)=2-5=-3<0$, so $A_I=0$, IoU $=0$.
Practice 3 (nested). $P=(1,1,3,3)$ inside $G=(0,0,4,4)$: $A_I=4$, $A_P=4$, $A_G=16$, $A_U=16$, IoU $=0.25$.
Standard usage: a detection is a true positive if its IoU is $\ge$ the threshold (commonly 0.5). The ground-truth box must have the same class and no earlier match. NMS also uses IoU as its overlap measure. Do not forget to subtract $A_I$ in the union.
Non-max suppression (NMS)
A detector produces many overlapping boxes around the same object. NMS keeps only the best box for each object.
- Discard boxes with confidence below a threshold.
- Sort the remaining boxes by score, highest first.
- Keep the top box. Delete every other box of the same class that has $\text{IoU}>$ threshold $T$ (e.g. 0.5) with it.
- Repeat with the next remaining box until no box is left.
Practice. Three boxes for the same class: A (score 0.9), B (0.8), C (0.7). The IoU values are IoU(A,B)=0.6, IoU(A,C)=0.1 and IoU(B,C)=0.55. The threshold is $T=0.5$.
Keep A (highest). B overlaps A with $0.6>0.5$, so NMS suppresses B. C overlaps A by $0.1<0.5$, so C stays. The next highest box is C. Keep it. B is already removed, so IoU(B,C) does not matter. Final output: A and C.
NMS is a post-processing step with no learned parameters. If $T$ is too low, NMS merges two real, close objects (people in a crowd). If it is too high, duplicates stay.
Evaluation: precision, recall, AP, mAP
TP: a detection with IoU $\ge$ threshold and the correct class. FP: a detection that matches nothing (wrong class, low IoU, or duplicate). FN: a ground-truth object that the detector missed. Precision = how many of the detections are right. Recall = how many of the real objects the detector found.
AP (average precision) = area under the precision-recall curve for one class. To get it, sort the detections by confidence, go down the list and compute precision and recall at each step. mAP = mean of AP over all classes: $\text{mAP}=\frac1C\sum_{c=1}^{C}AP_c$.
Practice. One class, 4 ground-truth objects. The detector returns 5 detections sorted by confidence: TP, TP, FP, TP, FP.
| Rank | Result | TP so far | FP so far | Precision | Recall |
|---|---|---|---|---|---|
| 1 | TP | 1 | 0 | 1/1 = 1.00 | 1/4 = 0.25 |
| 2 | TP | 2 | 0 | 2/2 = 1.00 | 2/4 = 0.50 |
| 3 | FP | 2 | 1 | 2/3 = 0.67 | 0.50 |
| 4 | TP | 3 | 1 | 3/4 = 0.75 | 3/4 = 0.75 |
| 5 | FP | 3 | 2 | 3/5 = 0.60 | 0.75 |
Final precision $=3/5=0.60$, recall $=3/4=0.75$. For interpolated AP, use the highest precision at any recall of at least $r$. Recall 0 to 0.25 gets 1.00, 0.25 to 0.50 gets 1.00 and 0.50 to 0.75 gets 0.75. The detector did not reach recall above 0.75, so that part gets 0. $AP=0.25(1)+0.25(1)+0.25(0.75)=0.6875$.
If the other two classes have $AP=0.80$ and $0.50$, then $\text{mAP}=(0.6875+0.80+0.50)/3=0.6625$.
Quote the slide definition: "mAP measures detection accuracy across classes and confidence thresholds; AP = area under the precision-recall curve; mAP = mean of AP over all classes." COCO-style mAP also averages over IoU thresholds 0.50 to 0.95.
Quick self-test
Difference between image classification and object detection?
Classification gives one label for the whole image ("Car"). Detection gives a class label, a bounding box and a confidence score for every object. It answers both what and where.
List the steps in the object detection pipeline.
Input image, pre-processing, feature extraction, classification, localisation (bounding boxes), non-max suppression, output with boxes and labels.
Explain R-CNN's steps and its main drawback.
Selective search gives about 2000 proposals. The network warps each proposal to $227\times227$. A pretrained CNN (AlexNet) extracts features. Class-specific SVMs classify. A regressor refines the boxes. NMS removes duplicates. Drawback: the CNN runs about 2000 times per image, so it is slow (and training has several stages).
How does Fast R-CNN speed up R-CNN? What is RoI pooling?
It runs the CNN once on the whole image and maps the proposals onto the feature map. Then it uses RoI pooling. RoI pooling divides each projected region into a fixed grid and max-pools each cell. This gives a fixed-size feature for any region size. One network does classification and box regression.
What does Faster R-CNN change over Fast R-CNN?
It replaces selective search with a learnable Region Proposal Network that shares the backbone features. Proposals then cost almost nothing, and training is end to end.
Compare one-stage and two-stage detectors with examples.
Two-stage (R-CNN, Fast R-CNN, Faster R-CNN): they propose regions, then classify and refine. They are more accurate and slower. One-stage (YOLO, SSD): they predict boxes and class probabilities for the whole image in a single pass. They are faster, simpler and work in real time.
Compute IoU for $P=(1,1,5,5)$ and $G=(3,3,7,7)$.
$A_P=A_G=16$. Overlap: $(3,3)$ to $(5,5)$, $A_I=4$. $A_U=16+16-4=28$. IoU $=4/28\approx0.143$.
A box has $(x,y,w,h)=(120,340,200,150)$ with $(x,y)$ the top-left corner. Give corner format. Another box has corners $(2,2,8,8)$; what are its centre and size?
First: $(120,340,320,490)$. Second: $w=h=6$, centre $(5,5)$.
Explain NMS with an example. When does it fail?
Sort by score, keep the best box, remove the boxes that have IoU above a threshold with it, and repeat. Example: scores 0.9 and 0.8 with IoU 0.6. Keep 0.9 and drop 0.8. NMS fails when the threshold is too low: it can remove real objects that overlap heavily (crowds).
Detections sorted by confidence: TP, FP, TP, TP (5 ground-truth objects). Find precision and recall after all four, and AP (interpolated).
After 4: TP=3, FP=1. Precision $=3/4=0.75$, recall $=3/5=0.60$. Points: (R=0.2, P=1), (R=0.2, P=0.5), (R=0.4, P=0.667), (R=0.6, P=0.75). Envelope: for recall up to 0.2 the max precision is 1.0. For 0.2 to 0.4 it is 0.75. For 0.4 to 0.6 it is 0.75. $AP=0.2(1)+0.2(0.75)+0.2(0.75)=0.5$.
- Detection = classify and localise every object: boxes (corner or centre format), labels, confidences.
- Pipeline: input, pre-process, features, classify, localise, NMS, output. Loss = classification + localisation.
- Two-stage: R-CNN (2000 selective-search proposals, warp to $227\times227$, CNN, SVMs, slow) then Fast R-CNN (CNN once, RoI pooling) then Faster R-CNN (RPN replaces selective search).
- One-stage: YOLO and SSD predict boxes and classes in a single pass; faster, slightly less accurate historically. YOLO output $S\times S\times(5B+C)$.
- IoU $=A_I/(A_P+A_G-A_I)$; slide example $16/56=0.286$. Threshold 0.5 decides TP/FP.
- NMS keeps the highest-scoring box and removes overlapping ones above an IoU threshold.
- Precision $=TP/(TP+FP)$, recall $=TP/(TP+FN)$, AP = area under the PR curve, mAP = mean AP over classes.