LiDAR Sequence
A crash course in LiDAR
A short textbook on LiDAR, meant to be read in order. It begins with the physics and electronics of the sensor and the structure of the data it produces, and works through the algorithms an engineer working with LiDAR is expected to know: the geometry of coordinate frames and rigid transforms, spatial data structures and neighbour search, normals and local features, robust model fitting and ground segmentation, clustering, scan registration, odometry and SLAM, occupancy mapping, multi-object tracking, and the deep networks that detect objects in point clouds. Each writeup builds on the ones before it, and together they are the background assumed by the writeups of research papers elsewhere on the site.
- 1 How LiDAR works, from photons to point clouds
The physics and electronics of a LiDAR measurement (time of flight, the LiDAR equation, emitters, detectors, FMCW and beam steering) and the structure of the data it produces: range images, point clouds, their density, occlusion, motion distortion and artefacts.
- 2 Coordinate frames, rigid transforms and calibration
Coordinate frames, rotations (matrices, Euler angles, axis–angle, quaternions), rigid transforms in SE(3) and the exponential map, and the operations built on them: extrinsic calibration, projection into cameras, range images and bird's-eye grids, and deskewing a moving scan.
- 3 Spatial data structures and neighbour search
Why neighbour queries dominate point-cloud processing, and the structures that answer them quickly: voxel grids and spatial hashing (with voxel downsampling), k-d trees, octrees and Morton codes, and the free neighbourhoods of a range image.
- 4 Filtering, normals and local features
Cropping and outlier removal, surface normals by principal component analysis and how to orient them and choose their scale, the shape features given by the covariance's eigenvalues, and keypoints and descriptors (FPFH) for matching points between clouds.
- 5 RANSAC and ground segmentation
Robust model fitting with RANSAC (its algorithm, iteration count and variants) and the methods used to separate ground from obstacles in a scan: height thresholds, elevation grids, polar line fitting, range-image angles and region-wise plane fitting.
- 6 Clustering and bounding boxes
Grouping non-ground points into objects by Euclidean clustering, grid connected components, DBSCAN and range-image segmentation, and summarising each cluster by an oriented box found by L-shape fitting, or by a convex hull.
- 7 Scan registration, from Kabsch to ICP and beyond
Aligning one point cloud to another: the closed-form Kabsch–Umeyama solution for known correspondences, ICP and the practical choices that make it work, point-to-plane ICP and degeneracy, Generalized-ICP, NDT, and global registration with descriptors and RANSAC.
- 8 LiDAR odometry and SLAM
Building odometry from registration, LOAM and feature-based odometry, LiDAR–inertial fusion, pose-graph SLAM and loop closure with an interactive example, place recognition with Scan Context, localisation in prior maps, and the ATE and KITTI drift metrics.
- 9 Occupancy mapping and ray casting
Maps of free, occupied and unknown space: the occupancy grid and its log-odds update, the inverse sensor model of a LiDAR beam, Amanatides–Woo ray traversal, OctoMap, removing moving objects from point maps, and signed distance fields.
- 10 Multi-object tracking
Tracking by detection: the Kalman filter and the motion models used for road users, gating by Mahalanobis distance, optimal assignment by the Hungarian algorithm, track management, LiDAR-specific difficulties, and the MOTA family of metrics.
- 11 Deep learning on point clouds
How networks consume point clouds (PointNet and PointNet++, voxel networks with sparse convolution, PointPillars, range-view networks), anchor- and centre-based detection heads, non-maximum suppression, the KITTI, nuScenes and Waymo metrics, LiDAR-specific training practice, and camera fusion.