Graph label propagation

Overview

Some nodes of a graph carry trusted values and the rest do not. Propagation fills in the rest by making each unknown node's value a weighted average of its neighbours' values, so the trusted values spread outward through the graph. The invariant shared by the method is that, after propagation, every free node is still such a weighted average, while the trusted nodes stay at their measured values 1906.06310 §4, eq. 8. In the one card that uses this concept, the nodes are 3D points of a stereo-derived point cloud, the trusted values are depths of a few sparse LiDAR returns, and each point is linked to its ten nearest neighbours 1906.06310 §4, §5.1.

Variants

Only one card in the wiki lists this concept, so this page covers one variant. Other label-propagation methods are not described here until a card covers them.

Graph-based depth correction (GDC)

Sparse LiDAR points are matched to pseudo-LiDAR points and used as fixed anchors. The remaining depths are solved so that each point is still reconstructed from its neighbours 1906.06310 §4. Card: Pseudo-LiDAR++: Accurate Depth for 3D Object Detection in Autonomous Driving.

The steps are:

1. Build a k-nearest-neighbour graph over the 3D points, with k = 10 1906.06310 §4, §5.1.
2. For each point, compute weights that reconstruct its depth from its neighbours' depths, summing to one and zero outside its neighbourhood 1906.06310 §4, eq. 7; app. B.
3. Hold the anchor depths fixed and solve for the remaining depths with a sparse iterative solver (conjugate gradient) 1906.06310 §4, eq. 8; app. B, alg. 1.

Author-reported effect on KITTI validation, car, PointRCNN, moderate, IoU 0.7, AP_BEV: the pseudo-LiDAR baseline reaches 56.0, stereo depth alone 64.0, and stereo depth with 4-beam anchors and propagation 76.9 1906.06310 tab. 1. With the same anchors but no propagation, the score is 73.0 [arxiv:1906.06310 tab. 4], so propagation adds about 3.9 points in this setting. The 4-beam input is simulated by thinning 64-beam scans, not recorded with a 4-beam sensor 1906.06310 §5.1.

When to use which

No other evidence in the wiki covers the situations this table leaves out, such as dense labels, non-geometric graphs, or other anchor sources.

Implementation sketch

Language-agnostic pseudocode of the common core. Only one variant is covered, so this is its sketch.

# Build the graph: each point links to its k nearest neighbours
# [arxiv:1906.06310 §4, §5.1]
neighbors = k_nearest(points, k=10)

# Reconstruction weights: each value is a weighted sum of its neighbours,
# weights sum to one and are zero outside the neighbourhood
# [arxiv:1906.06310 §4, eq. 7; app. B]
W = reconstruction_weights(values, neighbors)

# Hold the anchors at their measured depths and solve the rest so every
# free value is still reconstructed from its neighbours
# [arxiv:1906.06310 §4, eq. 8; app. B, alg. 1]
free = conjugate_gradient_solve(W, anchors, free_indices)

# Anchors keep their measured values in the output
# [arxiv:1906.06310 §4]
corrected = merge(anchors, free)

Notes on the sketch:

• The weight solve needs a small regulariser for stability. The paper calls it slight and gives no value 1906.06310 §4, app. B. The released code uses 1e-5 see the card, which is a code value, not a paper value.
• The stopping tolerance of the solver is not stated in the paper 1906.06310 app. B.

Contradictions

None across papers, since only one card uses this concept. Within that paper, the main text states the weight step as a least-squares problem [arxiv:1906.06310 §4, eq. 7], while the appendix states a minimum-norm problem with the same constraints 1906.06310 app. B. The paper does not show that these two give the same weights.

Papers

• Pseudo-LiDAR++: Accurate Depth for 3D Object Detection in Autonomous Driving: applies graph-based propagation of sparse LiDAR anchors to a stereo point cloud and reports the gain on KITTI.