Chapter 7: Point Cloud Processing

A point cloud of $N$ points can be presented in $N!$ different orderings, and the network must produce the same output for all of them. PointNet solves this by applying identical MLPs (shared weights) to each point independently, producing a per-point feature vector, then aggregating across all points using max-pooling. Max-pooling is a symmetric function: max(a, b, c) = max(c, a, b) = max(b, c, a) regardless of input order. The resulting global feature vector is a fixed-size descriptor of the entire point cloud. This is provably a universal approximator for continuous set functions.

PointNet's T-Net is a mini-PointNet (shared MLP, max-pool, fully connected layers) that predicts a $3 \times 3$ matrix applied to the input coordinates; a second T-Net predicts a $64 \times 64$ matrix applied to per-point features. The idea, borrowed from spatial transformer networks, is to map each cloud toward a canonical pose before feature extraction. It does not make the network rotation invariant: the matrix is learned, not guaranteed, and the paper still trains with random rotations about the up axis. A regularizer $L_{\text{reg}} = \lVert I - AA^\top \rVert_F^2$ keeps the feature transform $A$ near orthogonal so it cannot collapse dimensions. In the ablation, the input transform alone added 0.8 accuracy points.

An important theoretical property of PointNet is that the max-pooling layer selects a subset of 'critical points' that determine the global feature. For each feature dimension, only the point with the maximum activation contributes to the output. This means the entire point cloud can be summarized by a small set of critical points (at most 1024 for a 1024-dimensional feature), and the network is robust to perturbation or removal of non-critical points. This also means PointNet is inherently robust to noise and outliers, as long as the critical points remain intact.

A Set Abstraction (SA) layer has three components: sampling, grouping, and PointNet. Sampling selects a subset of $N'$ representative points from the input $N$ points using Farthest Point Sampling (FPS), which greedily picks points that are maximally distant from already-selected points, ensuring good spatial coverage. Grouping finds the $K$ nearest neighbors of each sampled point (ball query within radius $r$ or kNN), defining a local region. PointNet is applied to each local region independently, producing a feature vector for each sampled point. The output is a smaller set of $N'$ points, each with richer features that encode local geometry. Stacking SA layers creates a hierarchy: $N \to N/4 \to N/16 \to$ global feature.

Different regions of a point cloud may have varying density (dense near the sensor, sparse far away). Single-scale grouping with a fixed radius may miss context in dense regions or lack neighbors in sparse regions. Multi-Scale Grouping addresses this by applying multiple ball queries with different radii (e.g., r=0.1, 0.2, 0.4) at each centroid, running separate PointNets on each scale, and concatenating the resulting features. This gives each point features that capture both fine-grained local patterns (small radius) and broader context (large radius). The alternative is Multi-Resolution Grouping (MRG), which uses features from the previous SA level as an additional input when the local neighborhood is too sparse.

Segmentation needs a label for every input point, but set abstraction leaves features only on a few coarse centroids. Feature propagation carries them back level by level. For each point at the finer level, it finds the $k = 3$ nearest coarse points and averages their features with weights $w_j = 1 / d_j^p$, normalized to sum to 1; the paper's default is $p = 2$, inverse squared distance. The interpolated feature is concatenated with the skip-linked feature saved at that level during encoding, as in a U-Net, and a shared MLP refines it. Interpolation alone is smooth and blurs boundaries between objects; the skip features restore local detail.

Dense voxelization maps a point cloud to a regular 3D grid where each voxel stores features (occupancy, averaged point features, or learned embeddings). A voxel at grid position (i, j, k) aggregates all points falling within it. Dense grids have memory cost $O(R^3)$ for resolution $R$, which is prohibitive at high resolution: a $256^3$ grid requires 16.7 million voxels even when only 1% are occupied. Sparse voxelization stores only the occupied voxels using hash tables or coordinate lists, reducing memory from $O(R^3)$ to $O(N)$ where $N$ is the number of occupied voxels. Libraries like MinkowskiEngine and TorchSparse implement sparse tensors and sparse 3D convolutions that operate only on non-empty voxels.

MinkowskiNet (Choy et al., CVPR 2019) builds U-Net-style networks from sparse 3D convolutions. A sparse convolution computes outputs only at active coordinates, gathering inputs through a hash map of occupied voxels. Two flavours matter. Generalized or generative convolutions may create outputs at new coordinates within the kernel's reach, which strided downsampling and transposed upsampling need. Submanifold convolutions output only at already-active sites, so stacked layers do not dilate the active set into empty space. The trade-off is a narrower receptive field across gaps. MinkowskiNet reached 67.9 percent mIoU on ScanNet at submission, a large step over point-based methods then, and the same engine powers many later 3D detectors.

VoxelNet (Zhou and Tuzel, 2018) learned LiDAR detection end to end: a Voxel Feature Encoding layer runs a small PointNet inside each voxel, and dense 3D convolutional middle layers feed a 2D detection head. SECOND later replaced those middle layers with sparse convolutions. PointPillars (Lang et al., 2019) removes 3D convolution altogether: each pillar is a full-height column, a PointNet encodes its points, and the features are scattered into a 2D pseudo-image processed by an ordinary 2D CNN. On KITTI it ran at 62 Hz while beating earlier LiDAR-only detectors. The price is coarse vertical detail, which hurts small objects such as pedestrians.

Semantic segmentation predicts a class label for every input point. PointNet-based methods concatenate the global feature with per-point features and pass through an MLP classifier. PointNet++ and KPConv use hierarchical features with skip connections for better accuracy. Voxel-based methods like MinkowskiNet process a sparse 3D U-Net and map predictions back to points. The standard evaluation metric is mean Intersection over Union (mIoU), computed per-class and averaged. Challenges include class imbalance (floors have many more points than chairs), varying point density, and distinguishing objects with similar geometry but different semantics (table vs desk).

Instance segmentation groups points belonging to the same object instance (chair_1 vs chair_2). Top-down methods first detect 3D bounding boxes, then segment points within each box. Bottom-up methods predict per-point embeddings where points of the same instance have similar embeddings, then cluster the embeddings. Panoptic segmentation combines both: stuff classes (wall, floor, ceiling) get semantic labels only, while thing classes (chairs, tables) get both semantic labels and instance IDs. 3D-BoNet, PointGroup, and Mask3D are leading approaches, with Mask3D using a transformer-based architecture that directly predicts instance masks through cross-attention between queries and point features.

RandLA-Net (Hu et al., CVPR 2020) segments scans of up to a million points in one pass instead of cutting them into small blocks. Its first change is the sampler: farthest point sampling picks $M$ of $N$ points in $O(NM)$ time, effectively quadratic for a fixed fraction, and the paper measured over 200 seconds to sample 10 percent of a million points, while random sampling is linear and nearly free. Random sampling can drop small objects, so a Local Feature Aggregation module compensates: relative-position encoding, attentive pooling over $K = 16$ neighbours, and dilated residual blocks that widen the receptive field. The paper processes a 100,000-point scan in 0.04 s.

Point-to-point ICP iterates between two steps: (1) for each point in the source cloud, find the closest point in the target cloud (correspondence step), and (2) find the rigid transformation $(R, t)$ that minimizes the sum of squared distances between corresponding points (alignment step). The alignment step has a closed-form solution using SVD of the cross-covariance matrix. The algorithm converges monotonically (the error decreases at every step) and terminates when the change in error falls below a threshold. However, ICP only guarantees convergence to a local minimum---the initial alignment must be reasonable for the algorithm to find the correct registration. Typical convergence takes 20-50 iterations.

Point-to-plane ICP replaces the point-to-point distance with the distance from each source point to the tangent plane at its corresponding target point. The error for each pair is $(R \cdot p_s + t - p_t) \cdot n_t$, where $n_t$ is the target point's normal. This formulation converges much faster than point-to-point ICP (typically 5-10 iterations vs 30-50) because it correctly handles sliding along surfaces: a source point can move along the target surface without penalty, only penalizing normal-direction offsets. The alignment step no longer has a closed-form SVD solution and requires linearization (small-angle approximation) solved as a 6x6 linear system. Point-to-plane is the standard choice for most practical applications.

Standard ICP is sensitive to outliers: incorrect correspondences (from partial overlap, noise, or dynamic objects) can bias the transformation estimate. Robust ICP variants address this by rejecting outliers during the correspondence step. Common strategies include: distance thresholding (reject pairs with distance above a threshold, which decreases over iterations), trimmed ICP (sort pairs by distance and use only the best 70-80%), and M-estimator ICP (replace the squared distance with a robust kernel like Huber or Cauchy that downweights large residuals). Additionally, normal compatibility filtering rejects pairs where the source and target normals differ by more than a threshold angle, which eliminates many incorrect correspondences at surface boundaries.

RANSAC plane fitting repeatedly: (1) randomly samples 3 points and computes the plane through them, (2) counts how many remaining points lie within a distance threshold of that plane (inliers), and (3) keeps the plane with the most inliers. After reaching the iteration limit, the best plane is refined by fitting it to all its inliers using SVD. The number of iterations needed depends on the inlier ratio and the desired success probability: N = log(1-p) / log(1-w^s), where p is the desired success probability, w is the inlier ratio, and s is the minimum sample size (3 for planes). For example, with 50% inliers and 99% desired probability, N = log(0.01) / log(1-0.125) = 35 iterations.

Real scenes contain multiple geometric primitives. Multi-model RANSAC detects them sequentially: fit the dominant model, remove its inliers, fit the next model from remaining points, and repeat. This peeling approach works well when primitives have different inlier counts. For simultaneous detection, methods like J-linkage or T-linkage cluster points by their preference for different models. Beyond planes, RANSAC can fit spheres (4 parameters, 4 sample points), cylinders (5 parameters), and cones. Each primitive type has its own minimum sample size and model computation. Efficient implementations use precomputed normal information to reject impossible samples early.

RANSAC extends naturally to other geometric primitives. Sphere fitting requires 4 sample points (to determine center and radius from 4 equations: (x_i - cx)^2 + (y_i - cy)^2 + (z_i - cz)^2 = r^2). Cylinder fitting requires 2 points with normals (the cylinder axis is perpendicular to both normals, and the radius is determined from the distance to the axis). In practice, normal-guided sampling dramatically reduces the search space: for plane fitting, if the sampled points have inconsistent normals, the sample is immediately rejected without computing the plane. For cylinders, pairs of points with parallel normals are likely on the cylinder surface. This can reduce the required iterations by 10-100x.