3D Object Detection

3D object detection finds the objects of given classes in a scene and describes each one by a class, a confidence score and a box in three-dimensional space: a centre in metres, three dimensions and, usually, a heading angle about the vertical axis. It is the 3D counterpart of 2D object detection, and the box it outputs is metric rather than a rectangle of pixels, so a planner or a robot can reason about where an object is, how large it is and which way it faces. The input can be a LiDAR point cloud, a stereo pair, a single image, the images of several cameras around a vehicle, an RGB-D frame or a reconstructed indoor scan, or a combination of these. Driving benchmarks (KITTI, nuScenes and the Waymo Open Dataset) and indoor benchmarks built on SUN RGB-D and ScanNet define the task in practice, and they disagree on what counts as a correct detection: KITTI and Waymo require a 3D overlap above a threshold, while nuScenes requires only that the box centre lie within a distance on the ground plane. This article covers the task across sensors, the main method families in outline, and the benchmarks with their matching rules; PointPillars describes one LiDAR detector in depth, and bird’s-eye-view perception and sensor fusion for autonomous driving cover camera-only and multi-sensor methods.

Problem Definition

Given sensor data for one moment (or a short window before it), the task is to output a set of detections, each a class label, a score and a 3D box, such that every object of the evaluated classes is covered by one box and no box covers nothing. As in 2D detection, the number of objects is unknown, and the output is a ranked list scored by average precision, so the score must rank correct boxes above wrong ones.

The box is the main difference from the 2D task. Driving datasets use upright boxes with seven parameters, $(c_x, c_y, c_z, l, w, h, \theta)$: the Waymo Open Dataset defines its labels as 7-DOF upright boxes in exactly this form, with length, width and height the sizes along the $x$, $y$ and $z$ axes and $\theta$ the heading (Sun et al., 2020, §3.3). Upright means the box can rotate only about the vertical axis, so pitch and roll are ignored, which suits vehicles and people on a road. Benchmark boxes are usually amodal, enclosing the whole object including parts the sensor does not see; VoteNet’s authors describe SUN RGB-D’s boxes as amodal and oriented (Qi et al., 2019, §5.1). nuScenes adds a velocity and attributes such as whether a pedestrian is sitting or standing (Caesar et al., 2020, §3.1). SUN RGB-D also assumes boxes aligned with gravity and estimates only a yaw angle (Song, Lichtenberg & Xiao, 2015, §3); ScanNet provides no oriented boxes, so detectors evaluated on it predict axis-aligned ones (Qi et al., 2019, §5.1).

The coverage and frame are part of the definition. KITTI labels only objects that appear in the front camera image (KITTI benchmark page), while nuScenes and Waymo annotate the full 360° around the vehicle. A detector’s output is meaningful only together with the frame, axis order and heading convention of the benchmark it is scored on.

Input and Output

Input	Typical data	What it gives	What it lacks
LiDAR	One sweep or a few accumulated sweeps, $(x, y, z)$ plus reflectance (and a time offset when sweeps are accumulated)	Metric range on every return	Density at long range, texture and colour
Stereo	A rectified image pair	Dense depth from disparity	Accuracy at long range: error grows quadratically with depth
Monocular	One image and its intrinsics	Appearance, class cues, image position	Depth, which must be inferred
Multi-view cameras	Six images around a vehicle (nuScenes), with intrinsics and extrinsics	360° appearance	Depth, as for one image
RGB-D, indoor scans	A depth image, or a reconstructed mesh of a room	Metric geometry at short range	Coverage outside the scanned surfaces
Fusion	Any of the above together, calibrated and synchronized	Complementary strengths	Independence: results depend on calibration, synchronization and every sensor working

The output is a list of boxes in a fixed frame, with class labels and scores, and, on nuScenes, velocities and attributes. Many detectors produce overlapping candidates and remove duplicates with non-maximum suppression, PointPillars on axis-aligned bird’s-eye-view boxes (Lang et al., 2019, §4.2) and VoteNet in 3D at an IoU of 0.25 (Qi et al., 2019, §4.3); set-prediction detectors such as DETR3D need none (Wang, Guizilini et al., 2021).

Variants

• LiDAR-based detection works on point clouds that measure range directly but are sparse and become sparser with distance. The LiDAR article describes the sensor and its data.
• Stereo detection estimates depth from a calibrated image pair, then detects in 3D. Pseudo-LiDAR (Wang, Chao et al., 2019) turned the estimated depth map into a point cloud and ran LiDAR detectors on it.
• Monocular detection predicts 3D boxes from one image; depth is the weakest part of the prediction. FCOS3D and MonoDIS are examples.
• Multi-view camera detection combines the surround cameras of a vehicle, by lifting image features into a bird’s-eye-view grid or by letting 3D queries sample the images (DETR3D, BEVFormer).
• Multi-sensor fusion combines camera, LiDAR and sometimes radar at the level of points, features, a shared grid or finished boxes; the sensor fusion article covers it.
• Indoor detection finds furniture and other objects in RGB-D frames (SUN RGB-D) or reconstructed rooms (ScanNet), with gravity-aligned or axis-aligned boxes.
• Temporal detection uses several past frames: nuScenes allows about 0.5 s of past data, at most ten past LiDAR sweeps, six past camera images and six past radar sweeps (nuScenes devkit, detection README).
• Related outputs. Occupancy prediction describes the scene by labelled voxels instead of boxes; point cloud segmentation labels every point; 6-DoF object pose estimation recovers full rotation and translation of known objects rather than an upright box of a class.

Challenges

• Sparsity and range. A LiDAR returns many points from a nearby car and a handful from a distant one; nuScenes reports annotated objects with up to 12,000 LiDAR points at 3 m and up to 100 at 80 m (Caesar et al., 2020, §2). Waymo removes labels with no LiDAR points from evaluation and puts objects with five points or fewer in its harder LEVEL 2 (Sun et al., 2020, §5.1).
• Depth from images. A camera measures direction, not distance. Pseudo-LiDAR’s authors note that the error of stereo depth grows quadratically with depth, against roughly linearly for time-of-flight sensors such as LiDAR (Wang, Chao et al., 2019, §1 and §3), and the FCOS3D authors conclude from their bird’s-eye-view visualizations that depth estimation remains the core difficulty of monocular detection (Wang, Zhu, Pang & Lin, 2021, §5.2).
• Orientation. A box can face any direction. Axis-aligned anchors fit rotated objects poorly, which motivated CenterPoint’s detection of centres instead of boxes (Yin, Zhou & Krähenbühl, 2021, §1), and a heading predicted 180° wrong still gives a perfect box overlap. KITTI and Waymo score orientation separately (AOS, APH); Waymo’s authors note that AP has no notion of heading (Sun et al., 2020, §4.1.1).
• Small and thin objects. A pedestrian’s footprint is under a metre across, so a small position error removes all overlap; bicycles return few LiDAR points, and in the nuScenes baseline comparison a monocular detector beat the LiDAR detectors on bicycles under centre-distance matching (Caesar et al., 2020, §4.2).
• Occlusion and truncation. Boxes are amodal, but the sensor sees only part of an occluded object; KITTI’s difficulty levels are defined partly by occlusion and truncation.
• Class imbalance. nuScenes reports a ratio of 1:10,000 between its rarest and commonest annotated classes, against 1:36 in KITTI (Caesar et al., 2020, §2).
• Domain shift. In Waymo’s experiment, the vehicle baseline evaluated on the suburban domain’s validation data reached 36.7 LEVEL 2 APH when trained on San Francisco, against 44.0 when trained on the suburban domain (Sun et al., 2020, Table 9); the text of §5.3 gives the reduction as 8.0 APH, which differs from the table.

Approaches

As Lang et al. (2019, §1) summarize the history, LiDAR pipelines first removed the background, clustered the remaining points and classified the clusters; later ones projected the cloud to the ground plane and computed hand-crafted features per cell so that an image detector could be applied. The PointPillars article traces this line. Most learned detectors since 2018 belong to a few families, distinguished by how they turn points into something a network can process.

LiDAR: voxels, pillars and the bird’s-eye view

VoxelNet (Zhou & Tuzel, 2018) divides the cloud into equally spaced 3D voxels, encodes the points of each voxel with stacked voxel feature encoding (VFE) layers, which Lang et al. (2019) describe as a PointNet applied to each voxel, and passes the volume through 3D convolutions to a region proposal network, all trained end to end. Its authors present it as removing the need for hand-crafted features such as bird’s-eye-view projections. SECOND made the 3D convolutions sparse; the sparse convolutional networks article describes it and the sparse backbones that later detectors share. PointPillars (Lang et al., 2019) makes every voxel a vertical column, so that the encoded grid is a 2D pseudo-image and the rest of the network is an ordinary 2D detector; its authors reported 62 Hz on KITTI.

These grid methods end in a bird’s-eye-view feature map: height is folded into channels and a 2D head predicts boxes on the ground plane. The heads followed 2D detection, first with anchor boxes at a few fixed orientations per class. CenterPoint (Yin et al., 2021) replaced anchors by a heatmap of object centres in the bird’s-eye view, with the keypoint detector of CenterNet (Zhou, Wang & Krähenbühl’s “Objects as Points”), regressed size, orientation and velocity at each peak, and refined them in a second stage with point features from the object; its authors reported 65.5 NDS for detection and 63.8 AMOTA for tracking on the nuScenes test set with a single model.

LiDAR: points and point–voxel hybrids

Point-based detectors work on the raw points with PointNet-style set networks. PointRCNN (Shi, Wang & Li, 2019) is two-stage: the first stage segments the scene’s points into foreground and background and generates a 3D proposal from foreground points, bottom-up, and the second stage transforms the points pooled in each proposal into the proposal’s canonical coordinates to refine the box. PV-RCNN (Shi et al., 2020) combines the two representations: a sparse 3D voxel CNN produces features and proposals, a voxel set abstraction module summarizes the scene into a small set of keypoints, and RoI-grid pooling gathers keypoint features at grid points inside each proposal for refinement; the authors reported gains on KITTI and the Waymo Open Dataset. They credit the voxel CNN with efficient learning and high-quality proposals and the PointNet-based set abstraction with flexible receptive fields, and combine the two for that reason.

Stereo and monocular cameras

Pseudo-LiDAR (Wang, Chao et al., 2019) estimated a depth map from a stereo pair (or a single image), back-projected every pixel into a point cloud in the LiDAR frame, and ran unchanged LiDAR detectors on it. The authors argue that the gap between image-based and LiDAR-based detection came mostly from the representation, not the depth quality: on the KITTI validation set, AVOD on stereo pseudo-LiDAR reached 56.8 BEV AP and 45.3 3D AP for moderate cars at IoU 0.7, against 11.9 and 6.6 for the same detector and depth in a frontal (image-plane) representation (Table 2). Their Table 1 shows how strongly the threshold bears on image-based methods: at IoU 0.5 the stereo pseudo-LiDAR AVOD scored 77.5 BEV AP and 76.4 3D AP for moderate cars, while AVOD with LiDAR and a monocular image fell less from IoU 0.5 to 0.7 (89.4/89.2 to 86.5/73.5; Table 1).

Monocular detectors regress 3D boxes from image features. MonoDIS (Simonelli et al., 2019) isolates the contribution of groups of box parameters to the 2D and 3D detection losses, which its authors say simplifies training and avoids balancing separate regression terms; the same paper criticized KITTI’s 11-point AP and proposed the 40-point version the benchmark later adopted (see Evaluation Metrics). FCOS3D (Wang, Zhu, Pang & Lin, 2021) adapts the FCOS one-stage 2D detector: it splits the 7-DoF target into 2D and 3D attributes, assigns objects to feature levels by their 2D scale and to locations by the projected 3D centre, and redefines centre-ness around that centre. Its authors report 0.358 mAP and 0.428 NDS on the nuScenes test set, first among the vision-only methods of the NeurIPS 2020 nuScenes challenge; in their Table 1 that mAP exceeds the 0.305 of the PointPillars baseline, while the translation error is larger (mATE 0.690 against 0.517), which in our reading is possible because nuScenes matches by centre distance, at thresholds up to 4 m, whatever the boxes’ overlap.

Multi-view cameras

Surround camera rigs led to methods that reason in 3D over all images at once. DETR3D (Wang, Guizilini, Zhang, Wang, Zhao & Solomon, 2021; a different Wang from FCOS3D’s first author) uses a sparse set of 3D object queries, projects each query’s reference point into all cameras with the calibration, samples image features there, and predicts one box per query with a set-to-set loss, without non-maximum suppression. BEVFormer (Li et al., 2022) builds a bird’s-eye-view grid of queries that gather image features with spatial cross-attention and fuse the history of earlier grids with temporal self-attention; its authors reported 56.9 NDS on the nuScenes test set. The bird’s-eye-view perception article covers these and depth-based lifting (Lift-Splat-Shoot, BEVDet, BEVDepth), with their reported results.

Fusion

Fusion methods attach image information to LiDAR points (PointPainting), use 2D detections to restrict the LiDAR search (Frustum PointNets), fuse features in proposals or with attention (MV3D, AVOD, TransFusion), combine both sensors in a shared bird’s-eye-view grid, or combine finished boxes (CLOCs); the sensor fusion article describes each. One of the two BEVFusion papers (Liang et al., 2022) keeps the camera stream independent of LiDAR input, so that the system still produces predictions when the LiDAR fails. With objects’ LiDAR points dropped at random on the nuScenes validation set and matching training augmentation, it raised PointPillars, CenterPoint and TransFusion-L by 28.9, 22.7 and 15.7 mAP over their LiDAR-only streams, which Table 4 reports only without that augmentation (§4.4.1); the abstract describes the same range, 15.7% to 28.9%, as a margin over state-of-the-art methods.

Indoor detection

Indoor detection works on single RGB-D frames or on reconstructed scans of rooms. VoteNet (Qi et al., 2019) builds on PointNet++: seed points sampled from the scene each vote, through a learned offset, for the centre of the object they belong to; votes are clustered and each cluster is turned into a box proposal and class. The authors motivate voting by the observation that an object’s centre can lie far from any surface point, so a box is hard to regress from a single point. Using geometry alone, VoteNet reported 57.7 mAP at 3D IoU 0.25 on the SUN RGB-D validation set (ten classes, V1 data) and 58.6 mAP@0.25 and 33.5 mAP@0.5 on the ScanNet v2 validation set (Tables 1 and 2), above earlier detectors that also used colour images. The ScanNet article places these numbers among the dataset’s other tasks.

Datasets and Benchmarks

• KITTI (Geiger, Lenz & Urtasun, 2012): driving in and around Karlsruhe with a stereo camera rig and a 64-beam LiDAR. Its 3D and bird’s-eye-view object benchmarks (2017) have 7,481 training and 7,518 test images with their point clouds and 80,256 labelled objects, and evaluate cars, pedestrians and cyclists in the front camera’s view; methods are ranked at moderate difficulty, and the KITTI article gives the difficulty levels. Papers usually split the training images into 3,712 for training and 3,769 for validation (Simonelli et al., 2019, §6), so “KITTI val” results are not test results.
• nuScenes (Caesar et al., 2020): 1,000 scenes of 20 s from Boston and Singapore with six cameras, five radars and one LiDAR, all covering 360°, annotated at 2 Hz keyframes (40,000 keyframes and 1.4 million boxes in its Table 1) with 23 classes and 8 attributes. Detection evaluates 10 merged classes, each only up to a class-specific range: 50 m for cars, trucks, buses, trailers and construction vehicles, 40 m for pedestrians, motorcycles and bicycles, 30 m for traffic cones and barriers (detection_cvpr_2019.json).
• Waymo Open Dataset (Sun et al., 2020): 1,150 scenes of 20 s from San Francisco, Mountain View and Phoenix, split 798/202/150 into training, validation and test, with five LiDARs and five cameras and about 12 million labelled 3D LiDAR boxes for vehicles, pedestrians, cyclists and signs.
• SUN RGB-D (Song, Lichtenberg & Xiao, 2015): 10,335 indoor RGB-D images from four different sensors, with 146,617 2D polygons and 64,595 3D boxes with orientations; 5,285 images form the training set. Detectors usually report the ten most common categories (Qi et al., 2019).
• ScanNet: reconstructed indoor scans (see the ScanNet article) with instance labels from which detectors derive axis-aligned boxes for 18 classes; there is no official detection benchmark, so results are on the validation set.

Evaluation Metrics

All the benchmarks rank detections by score, match them to ground truth one by one, and summarize the precision–recall curve by average precision. They differ in three choices: the affinity that decides a match, the threshold, and how the curve becomes a number.

Matching by 3D or BEV overlap

KITTI and Waymo use intersection over union of boxes. For upright boxes, the intersection volume is the overlap area of the two rotated footprints in the bird’s-eye view times the overlap of their vertical extents, and 3D IoU divides it by the union of the volumes; BEV IoU uses the footprints alone. KITTI requires a 3D overlap of 70% for cars and 50% for pedestrians and cyclists, uses the PASCAL criteria, does not count detections in “don’t care” regions as false positives, and, as its page notes, does not ignore detections outside the camera image, which can therefore become false positives (KITTI benchmark page). The Waymo paper’s experiments use 0.7 for vehicles and 0.5 for pedestrians in both 3D and BEV and matches by centre distance for signs; for each of a fixed set of score thresholds it matches predictions to ground truth with the Hungarian method so as to maximize total IoU (Sun et al., 2020, §4.1.1 and §5), unlike nuScenes’ greedy, score-ordered matching below; KITTI’s development kit, which would show its exact matching procedure, requires a login and was not read for this article.

Matching by centre distance

nuScenes matches a prediction to the ground-truth box of its class with the smallest 2D distance between box centres on the ground plane, and accepts it if that distance is below a threshold $d$. The devkit visits predictions in order of decreasing score, and each takes the nearest ground-truth box not yet taken (accumulate in algo.py). AP is computed for $d \in \{0.5, 1, 2, 4\}$ m and averaged over thresholds and classes. The authors give two reasons: to decouple detection from size and orientation, which have their own error metrics, and because objects with small footprints, such as pedestrians and bicycles, give zero IoU after a small translation error, which makes vision-only methods, with their larger localization errors, hard to compare (Caesar et al., 2020, §3.1). In their comparison, IoU matching (0.7 for cars, 0.5 for pedestrians and bicycles) left pedestrians and bicycles at 0 AP for the published methods, so they could not be ordered, and centre-distance matching reversed the order of the monocular and LiDAR methods on bicycles (§4.2, Fig. 7). Size, orientation, velocity and attribute quality enter instead through five true-positive errors and the nuScenes detection score (NDS); the bird’s-eye-view perception article gives their definitions. Before matching, the devkit removes ground-truth and predicted boxes beyond the class range, bicycles and motorcycles inside bicycle racks, and ground-truth boxes with no LiDAR or radar points, and it accepts at most 500 boxes per sample (detection README).

From the curve to a number

• KITTI AP|R40. KITTI originally averaged the interpolated precision $\rho_{\text{interp}}(r) = \max_{r' \ge r} \rho(r')$ at the eleven recall levels $\{0, 0.1, \dots, 1\}$. Simonelli et al. (2019, §6) pointed out that the level at recall 0 lets a single correct detection score $1/11 \approx 0.0909$, and proposed averaging over $R_{40} = \{1/40, 2/40, \dots, 1\}$ instead; the KITTI benchmark has used 40 recall positions since 8 October 2019, so results before and after are not comparable.
• KITTI AOS. Average orientation similarity replaces precision in the 11-point average by an orientation similarity, a normalized cosine similarity $(1 + \cos\Delta)/2$ of the heading differences $\Delta$ of the detections (Geiger, Lenz & Urtasun, 2012, §2.5).
• nuScenes AP. The devkit interpolates precision linearly onto 101 recall points (precision 0 above the highest recall reached), drops the points at recall 0.1 and below, subtracts 0.1 from precision and clips at zero, and divides the mean by 0.9 (calc_ap), the “normalized area” for recall and precision above 10% that the paper describes. Unlike KITTI, the devkit takes no running maximum of precision, and a class whose precision never exceeds 0.1 above 10% recall scores 0.
• Waymo AP and APH. AP integrates the interpolated precision $\max_{r' \ge r} p(r')$ over recall, and APH does the same for a curve in which each true positive is weighted by heading accuracy. The paper writes this accuracy as $\min(|\tilde\theta - \theta|, 2\pi - |\tilde\theta - \theta|)/\pi$ (§4.1.1); read literally, that expression is the normalized heading error, 0 for a perfect heading, so in our reading the weight must be one minus it. Where the precision–recall points are more than 0.05 apart in recall, the implementation inserts points with conservative precision so that a sparse curve does not overestimate AP. Results are reported for LEVEL 1 and the cumulative LEVEL 2, and by distance.
• Indoor. SUN RGB-D extends 2D detection evaluation to 3D with the 3D IoU of gravity-aligned boxes and used a threshold of 0.25 for its 3D detection baseline (Song et al., 2015, §3 and §4); VoteNet and later work report mAP at 0.25 and 0.5.

Range dependence shows in the published breakdowns. The Waymo PointPillars baseline’s vehicle 3D APH at LEVEL 1 on the test set was 81.9 within 30 m, 58.5 at 30–50 m and 34.9 beyond 50 m, while its BEV APH, which ignores height, was 90.2, 77.3 and 62.8 (Sun et al., 2020, Table 6).

Example: IoU matching and centre-distance matching as depth error grows

The script below builds synthetic driving scenes with known boxes, simulates detections whose error along the line of sight grows with range, and scores them under KITTI’s and nuScenes’ rules. It implements rotated 3D and BEV IoU (Sutherland–Hodgman clipping of the two footprints), the score-ordered greedy matching, KITTI’s AP|R40 as Simonelli et al. define it, and the nuScenes devkit’s centre-distance matching and calc_ap, ported from algo.py at commit b40adc4. The KITTI development kit itself requires a login to download and was not read, so the KITTI rows use the greedy matching above with the benchmark’s overlap thresholds rather than a port of its code; the KITTI paper describes its 2D evaluation as assigning detections to ground truth iteratively, starting with the largest overlap (Geiger, Lenz & Urtasun, 2012, §2.5), an order that can differ from the example’s score order. It uses NumPy 2.3.5, runs in about 3 seconds on a laptop CPU, and two runs printed identical output.

Conventions: boxes are $(x, y, z, l, w, h, \theta)$ with the centre in metres in a ground frame whose origin is the sensor, $x$ forward, $y$ left and $z$ up from flat ground, $l$ along the heading and $\theta$ the yaw about $z$; “radial” means along the line from the sensor to the box centre. Cars are 3.9 × 1.6 × 1.5 m and pedestrians 0.8 × 0.6 × 1.73 m, the PointPillars anchor sizes (Lang et al., 2019, §4.2). For each range band, centred at 10, 20, …, 70 m and 10 m wide, 100 scenes each hold six objects of one class at random positions within ±45° of straight ahead and random headings. Each object is detected with probability 0.9, with a score drawn uniformly from 0.2 to 1 and independent of its error, and each scene gets two false positives at random positions in the band with scores from 0 to 0.6. A detection’s centre is off by Gaussian errors with standard deviations $\sigma_r(r)$ radially, 0.1 m tangentially and 0.1 m in height; each dimension is scaled by $e^{\epsilon}$ with $\epsilon$ of standard deviation 0.05, and the heading error has a standard deviation of 5°. How depth error grows with range depends on the sensor and the method, which the sources do not fix for this purpose, so the script prints two models with the same random draws: linear, $\sigma_r = 0.02\,r$, and quadratic, $\sigma_r = 0.0005\,r^2$, the form the Pseudo-LiDAR authors give for stereo; they are equal at 40 m. The first two printed lines are checks: exact boxes with no misses or false positives score AP 1 under every rule, and a bird’s-eye-view image of one scene at 2 cm cells reproduces the polygon IoUs.

import numpy as np

# Boxes are (x, y, z, l, w, h, yaw): centre in metres in a ground frame with the
# sensor at the origin, x forward, y left, z up; l along the heading, yaw about z.
SIZE = {"car": (3.9, 1.6, 1.5), "pedestrian": (0.8, 0.6, 1.73)}  # PointPillars anchors
IOU_THR = {"car": 0.7, "pedestrian": 0.5}                        # KITTI thresholds
SEP = {"car": 4.5, "pedestrian": 1.2}


def bev_corners(b):
    x, y, _, l, w, _, yaw = b
    c, s = np.cos(yaw), np.sin(yaw)
    dx = np.array([l, -l, -l, l]) / 2
    dy = np.array([w, w, -w, -w]) / 2
    return np.stack([x + c * dx - s * dy, y + s * dx + c * dy], 1)   # counter-clockwise


def clip_polygon(P, Q):
    """Sutherland-Hodgman: the part of convex polygon P inside convex CCW polygon Q."""
    out = list(P)
    for i in range(len(Q)):
        a, b = Q[i], Q[(i + 1) % len(Q)]
        side = lambda p: (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])
        inp, out = out, []
        for j in range(len(inp)):
            p, q = inp[j - 1], inp[j]
            sp, sq = side(p), side(q)
            if sq >= 0:
                if sp < 0:
                    out.append(p + (q - p) * sp / (sp - sq))
                out.append(q)
            elif sp >= 0:
                out.append(p + (q - p) * sp / (sp - sq))
        if not out:
            return np.zeros((0, 2))
    return np.array(out)


def area(P):
    if len(P) < 3:
        return 0.0
    x, y = P[:, 0], P[:, 1]
    return 0.5 * abs(np.dot(x, np.roll(y, -1)) - np.dot(y, np.roll(x, -1)))


def iou_bev_3d(a, b):
    """BEV IoU of the rotated footprints and 3D IoU (footprint overlap times height overlap)."""
    inter = area(clip_polygon(bev_corners(a), bev_corners(b)))
    A, B = a[3] * a[4], b[3] * b[4]
    hov = max(0.0, min(a[2] + a[5] / 2, b[2] + b[5] / 2) - max(a[2] - a[5] / 2, b[2] - b[5] / 2))
    vi = inter * hov
    return inter / (A + B - inter), vi / (A * a[5] + B * b[5] - vi)


def match(preds, gts, kind, thr):
    """preds: list of (scene, box, score); gts: dict scene -> list of boxes.
    In order of decreasing score, each prediction takes the unmatched ground-truth box of
    its scene with the best affinity; it is a true positive if that affinity passes thr.
    kind: 'iou3d' or 'ioubev' (highest IoU, TP if >= thr) or 'cd' (smallest
    ground-plane centre distance, TP if < thr, as in the nuScenes devkit)."""
    order = sorted(range(len(preds)), key=lambda i: -preds[i][2])
    taken, tp = set(), []
    for i in order:
        s, p, _ = preds[i]
        best, bj = (-np.inf if kind != "cd" else np.inf), None
        for j, g in enumerate(gts[s]):
            if (s, j) in taken:
                continue
            if kind == "cd":
                v = np.hypot(p[0] - g[0], p[1] - g[1])
                if v < best:
                    best, bj = v, j
            else:
                if np.hypot(p[0] - g[0], p[1] - g[1]) > (np.hypot(p[3], p[4]) + np.hypot(g[3], g[4])) / 2:
                    v = 0.0                                  # footprints cannot overlap
                else:
                    v = iou_bev_3d(p, g)[0 if kind == "ioubev" else 1]
                if v > best:
                    best, bj = v, j
        ok = bj is not None and (best < thr if kind == "cd" else best >= thr)
        if ok:
            taken.add((s, bj))
        tp.append(ok)
    return np.array(tp, bool)


def pr(tp, n_gt):
    ctp, cfp = np.cumsum(tp), np.cumsum(~tp)
    return ctp / n_gt, ctp / (ctp + cfp)


def ap_r40(tp, n_gt):
    """KITTI AP|R40: interpolated precision (max at recall >= r) at r = 1/40, ..., 1."""
    rec, prec = pr(tp, n_gt)
    return np.mean([prec[rec >= r - 1e-12].max() if (rec >= r - 1e-12).any() else 0.0
                    for r in np.arange(1, 41) / 40])


def ap_nuscenes(tp, n_gt, min_recall=0.1, min_precision=0.1):
    """nuScenes devkit (accumulate + calc_ap): precision linearly interpolated onto
    101 recall points (0 beyond the highest recall), bins up to min_recall dropped,
    min_precision subtracted and clipped, normalized by 1 - min_precision."""
    if not tp.any():
        return 0.0
    rec, prec = pr(tp, n_gt)
    p = np.interp(np.linspace(0, 1, 101), rec, prec, right=0)
    p = p[round(100 * min_recall) + 1:] - min_precision
    p[p < 0] = 0
    return float(np.mean(p)) / (1.0 - min_precision)


def make_band(rng, centre, cls, n_scenes=100, n_obj=6):
    """Ground truth and the random draws for its detections, for one range band."""
    l, w, h = SIZE[cls]
    gts, draws = {}, {}
    for s in range(n_scenes):
        pts = []
        for _ in range(1000):
            r, a = rng.uniform(centre - 5, centre + 5), rng.uniform(-np.pi / 4, np.pi / 4)
            p = (r * np.cos(a), r * np.sin(a))
            if all(np.hypot(p[0] - q[0], p[1] - q[1]) > SEP[cls] for q in pts):
                pts.append(p)
            if len(pts) == n_obj:
                break
        gts[s] = [np.array([x, y, h / 2, l, w, h, rng.uniform(-np.pi, np.pi)]) for x, y in pts]
        draws[s] = {"det": rng.random(len(pts)) < 0.9, "z": rng.standard_normal((len(pts), 7)),
                    "score": rng.uniform(0.2, 1.0, len(pts)),
                    "fp_r": rng.uniform(centre - 5, centre + 5, 2), "fp_a": rng.uniform(-np.pi / 4, np.pi / 4, 2),
                    "fp_yaw": rng.uniform(-np.pi, np.pi, 2), "fp_score": rng.uniform(0, 0.6, 2)}
    return gts, draws


def detections(gts, draws, sigma_r, noise=1.0, misses_and_fps=True):
    preds = []
    for s, G in gts.items():
        d = draws[s]
        for k, g in enumerate(G):
            if misses_and_fps and not d["det"][k]:
                continue
            z = d["z"][k] * noise
            r = np.hypot(g[0], g[1])
            u = np.array([g[0], g[1]]) / r                       # line of sight
            t = np.array([-u[1], u[0]])
            xy = g[:2] + z[0] * sigma_r(r) * u + z[1] * 0.1 * t
            size = g[3:6] * np.exp(0.05 * z[2:5])
            preds.append((s, np.array([*xy, g[2] + 0.1 * z[5], *size, g[6] + np.radians(5) * z[6]]),
                          d["score"][k]))
        if misses_and_fps:
            g0 = G[0]
            for r, a, yaw, sc in zip(d["fp_r"], d["fp_a"], d["fp_yaw"], d["fp_score"]):
                preds.append((s, np.array([r * np.cos(a), r * np.sin(a), g0[2], *g0[3:6], yaw]), sc))
    return preds


ROWS = [("3D IoU, AP|R40 (KITTI)", "iou3d", None, ap_r40),
        ("BEV IoU, AP|R40 (KITTI BEV)", "ioubev", None, ap_r40),
        ("3D IoU, nuScenes AP rule", "iou3d", None, ap_nuscenes),
        ("centre 2 m, AP|R40", "cd", 2.0, ap_r40),
        ("centre 0.5 m, nuScenes", "cd", 0.5, ap_nuscenes),
        ("centre 1 m, nuScenes", "cd", 1.0, ap_nuscenes),
        ("centre 2 m, nuScenes", "cd", 2.0, ap_nuscenes),
        ("centre 4 m, nuScenes", "cd", 4.0, ap_nuscenes)]


def scores(preds, gts, cls):
    n_gt = sum(len(G) for G in gts.values())
    out = []
    for _, kind, thr, rule in ROWS:
        out.append(rule(match(preds, gts, kind, IOU_THR[cls] if thr is None else thr), n_gt))
    return out + [np.mean(out[4:8])]                              # nuScenes: mean over 0.5-4 m


if __name__ == "__main__":
    MODELS = {"linear, 0.02 r": lambda r: 0.02 * r, "quadratic, 0.0005 r^2": lambda r: 0.0005 * r ** 2}
    CENTRES = [10, 20, 30, 40, 50, 60, 70]
    names = [n for n, *_ in ROWS] + ["centre, mean of 4 (nuScenes)"]
    data = {(cls, c): make_band(np.random.default_rng(1000 * i + c), c, cls)
            for i, cls in enumerate(SIZE) for c in CENTRES}

    # Checks: exact boxes reach AP 1 under every rule; one scene's BEV raster against the polygons.
    worst = min(min(scores(detections(*data[(cls, c)], lambda r: 0.0, 0.0, False), data[(cls, c)][0], cls))
                for cls in SIZE for c in (10, 70))
    print(f"exact boxes, no misses or false positives: lowest AP over all rules = {worst:.3f}")
    gts, draws = data[("car", 20)]
    pr0 = detections({0: gts[0]}, draws, MODELS["linear, 0.02 r"])
    xs, ys = np.meshgrid(np.arange(5, 35, 0.02) + 0.01, np.arange(-25, 25, 0.02) + 0.01)
    def raster(b):                                  # BEV image of one box: cells whose centre is inside
        c, s = np.cos(b[6]), np.sin(b[6])
        u, v = (xs - b[0]) * c + (ys - b[1]) * s, -(xs - b[0]) * s + (ys - b[1]) * c
        return (abs(u) <= b[3] / 2) & (abs(v) <= b[4] / 2)
    diff = []
    for _, p, _ in pr0:
        g = min(gts[0], key=lambda g: np.hypot(*(g[:2] - p[:2])))
        A, B = raster(p), raster(g)
        diff.append(abs((A & B).sum() / (A | B).sum() - iou_bev_3d(p, g)[0]))
    print(f"BEV raster (2 cm cells) against polygon IoU, {len(diff)} pairs: largest difference {max(diff):.4f}")

    for mname, sig in MODELS.items():
        print(f"\nradial error sigma = {mname} m; band centre (m):"
              + "".join(f"{c:7d}" for c in CENTRES))
        print(f"{'sigma at band centre (m)':38s}" + "".join(f"{sig(c):7.2f}" for c in CENTRES))
        for cls in SIZE:
            res = np.array([scores(detections(*data[(cls, c)], sig), data[(cls, c)][0], cls)
                            for c in CENTRES]).T
            print(f"{cls} (IoU threshold {IOU_THR[cls]})")
            for n, row in zip(names, res):
                print(f"  {n:36s}" + "".join(f"{v:7.3f}" for v in row))

Output:

exact boxes, no misses or false positives: lowest AP over all rules = 1.000
BEV raster (2 cm cells) against polygon IoU, 7 pairs: largest difference 0.0002

radial error sigma = linear, 0.02 r m; band centre (m):     10     20     30     40     50     60     70
sigma at band centre (m)                 0.20   0.40   0.60   0.80   1.00   1.20   1.40
car (IoU threshold 0.7)
  3D IoU, AP|R40 (KITTI)                0.239  0.105  0.041  0.019  0.012  0.015  0.006
  BEV IoU, AP|R40 (KITTI BEV)           0.561  0.252  0.109  0.066  0.050  0.034  0.018
  3D IoU, nuScenes AP rule              0.179  0.056  0.012  0.001  0.000  0.000  0.000
  centre 2 m, AP|R40                    0.876  0.823  0.825  0.829  0.748  0.662  0.619
  centre 0.5 m, nuScenes                0.729  0.455  0.200  0.105  0.083  0.039  0.021
  centre 1 m, nuScenes                  0.848  0.779  0.619  0.461  0.365  0.236  0.167
  centre 2 m, nuScenes                  0.853  0.802  0.812  0.810  0.716  0.626  0.559
  centre 4 m, nuScenes                  0.889  0.831  0.846  0.842  0.830  0.782  0.829
  centre, mean of 4 (nuScenes)          0.830  0.717  0.619  0.554  0.498  0.421  0.394
pedestrian (IoU threshold 0.5)
  3D IoU, AP|R40 (KITTI)                0.223  0.060  0.028  0.023  0.007  0.004  0.003
  BEV IoU, AP|R40 (KITTI BEV)           0.292  0.087  0.040  0.031  0.012  0.006  0.005
  3D IoU, nuScenes AP rule              0.159  0.024  0.003  0.001  0.000  0.000  0.000
  centre 2 m, AP|R40                    0.874  0.813  0.848  0.808  0.755  0.711  0.630
  centre 0.5 m, nuScenes                0.773  0.455  0.240  0.144  0.056  0.032  0.037
  centre 1 m, nuScenes                  0.842  0.772  0.628  0.460  0.307  0.231  0.215
  centre 2 m, nuScenes                  0.858  0.799  0.826  0.790  0.726  0.679  0.585
  centre 4 m, nuScenes                  0.894  0.833  0.854  0.815  0.830  0.836  0.813
  centre, mean of 4 (nuScenes)          0.842  0.715  0.637  0.552  0.480  0.445  0.413

radial error sigma = quadratic, 0.0005 r^2 m; band centre (m):     10     20     30     40     50     60     70
sigma at band centre (m)                 0.05   0.20   0.45   0.80   1.25   1.80   2.45
car (IoU threshold 0.7)
  3D IoU, AP|R40 (KITTI)                0.520  0.277  0.064  0.019  0.007  0.006  0.001
  BEV IoU, AP|R40 (KITTI BEV)           0.838  0.536  0.178  0.065  0.033  0.016  0.008
  3D IoU, nuScenes AP rule              0.451  0.215  0.029  0.001  0.000  0.000  0.000
  centre 2 m, AP|R40                    0.876  0.823  0.828  0.828  0.664  0.448  0.289
  centre 0.5 m, nuScenes                0.847  0.748  0.348  0.110  0.044  0.011  0.001
  centre 1 m, nuScenes                  0.848  0.798  0.730  0.466  0.247  0.107  0.032
  centre 2 m, nuScenes                  0.853  0.802  0.818  0.800  0.632  0.387  0.225
  centre 4 m, nuScenes                  0.889  0.831  0.846  0.842  0.828  0.728  0.674
  centre, mean of 4 (nuScenes)          0.859  0.795  0.685  0.554  0.438  0.308  0.233
pedestrian (IoU threshold 0.5)
  3D IoU, AP|R40 (KITTI)                0.631  0.224  0.047  0.022  0.004  0.001  0.001
  BEV IoU, AP|R40 (KITTI BEV)           0.709  0.298  0.074  0.031  0.007  0.003  0.002
  3D IoU, nuScenes AP rule              0.585  0.161  0.015  0.001  0.000  0.000  0.000
  centre 2 m, AP|R40                    0.874  0.813  0.851  0.804  0.636  0.431  0.358
  centre 0.5 m, nuScenes                0.828  0.726  0.386  0.137  0.026  0.007  0.002
  centre 1 m, nuScenes                  0.842  0.795  0.728  0.474  0.189  0.080  0.058
  centre 2 m, nuScenes                  0.858  0.799  0.830  0.777  0.598  0.380  0.293
  centre 4 m, nuScenes                  0.894  0.833  0.854  0.815  0.830  0.800  0.663
  centre, mean of 4 (nuScenes)          0.855  0.788  0.699  0.551  0.411  0.317  0.254

The two rules diverge most where nuScenes’ authors said they would. With IoU matching, 3D AP is below 0.07 at 30 m and BEV AP below 0.07 at 40 m, under both error models and for both classes; at the 2 m centre distance that nuScenes uses for its error metrics, AP stays near 0.8 out to 40 m and is still 0.56–0.63 at 70 m under the linear model. The car rows show that 3D IoU at 0.7 is strict even before range enters: at 10 m, where the linear model’s radial error is 0.2 m, only 0.239 AP survives. By the script’s construction, the error terms that do not depend on range (0.1 m sideways and in height, 5% in size, 5° in heading) are present at every range, so in our reading they already push many boxes below 0.7 there. Dropping the height terms helps a great deal: BEV IoU gives 0.561 at the same range, and the quadratic model, with a radial error of 0.05 m at 10 m, gives 0.520 in 3D and 0.838 in the bird’s-eye view. Pedestrians are scored at the lower threshold of 0.5, yet at 20 and 30 m they keep less 3D IoU AP than cars under both models (0.060 against 0.105 at 20 m under the linear model), since a shift of a few tenths of a metre is a large fraction of a 0.6 m footprint; at 10 m the two classes are close under the linear model, and under the quadratic model, where the radial error is 0.05 m, pedestrians score higher (0.631 against 0.520); from 40 m on both classes are near zero. Their centre-distance rows stay within about 0.07 of the cars’; centre distance does not see an object’s size at all, which is the decoupling the nuScenes authors wanted.

The thresholds of the nuScenes mean behave like a family of rules. The 0.5 m row falls steeply, from 0.729 to 0.021 for cars under the linear model, the 4 m row stays between 0.78 and 0.89 at every range under the linear model, and their mean declines steadily, from about 0.83–0.84 at 10 m to about 0.39–0.41 at 70 m under the linear model. Under the quadratic model the 0.5 m row and the mean start higher, because its error is smaller at short range, and all three end lower, because it is larger beyond 40 m; at the 40 m band, where the two models agree at the band’s centre, the means are equal to three decimals for cars (0.554). nuScenes would not score the outer bands at all: its configuration evaluates cars only to 50 m and pedestrians only to 40 m.

The two cross rows separate the AP rule from the matching rule. With the same matches, the nuScenes rule gives less than AP|R40 (0.179 against 0.239 for cars at 10 m under the linear model, 0.853 against 0.876 at 2 m), since it removes the precision below 0.1, discards recall up to 0.1 and takes no running maximum of precision. When precision stays low, as for IoU matching beyond 40 m, the nuScenes rule prints 0.000 where AP|R40 still prints up to 0.015. A KITTI number and a nuScenes number for the same detector therefore differ through all three choices at once, the affinity, the threshold and the AP rule, besides the data.

Applications

The main application is perception for automated driving: 3D boxes of vehicles, pedestrians and cyclists with headings and velocities feed tracking by detection and motion forecasting, as the autonomous driving perception article describes; CenterPoint’s tracker, for example, matches each detected centre, moved back by its predicted velocity, to the nearest track (Yin et al., 2021). Indoor detection on SUN RGB-D and ScanNet belongs to scene understanding, and an object’s class, extent and orientation in metres is the kind of output robotic manipulation works with (our reading). These are descriptions of how the published systems use detections; the benchmarks measure detection accuracy on recorded data and do not establish the safety of any system that uses it.

Open Problems

• What a correct detection is. IoU thresholds penalize small objects and image-based methods heavily, centre distance ignores size and orientation unless other metrics are added, and the AP rules differ in detail; numbers from different benchmarks, or from KITTI before and after October 2019, cannot be compared, and the example shows how much each choice moves the result.
• Range. In Waymo’s breakdown the LiDAR baseline’s vehicle 3D APH falls by more than half from the nearest to the farthest range bin, and nuScenes evaluates classes only to 30–50 m, so the benchmarks say little about distant objects.
• Camera depth. Image-based methods lose most where localization must be tight: Pseudo-LiDAR’s stereo results drop far more than LiDAR results from IoU 0.5 to 0.7, and FCOS3D’s translation error is larger than the PointPillars baseline’s even where its mAP is higher. The FCOS3D authors call depth estimation the core challenge.
• Long tail and open vocabulary. The driving benchmarks evaluate three (KITTI), four (Waymo) or ten (nuScenes) classes, and box labels miss objects that fall outside them, one of the reasons given for occupancy prediction.
• Robustness. Sensor failure, miscalibration, weather and new cities change results, as the LiDAR-failure tests of Liang et al. (2022) and Waymo’s domain-shift experiment show; how detectors behave under conditions outside the recorded data is largely unmeasured in the sources read here (our observation).