PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency

In plain words

Two 3D scans of the same scene are matched by comparing local shape descriptors, but many of the matched point pairs are wrong. Those wrong pairs have to be removed before the scans can be aligned. The earlier learned filters judge each pair on its own.

PointDSC uses a simple geometric rule: if two pairs are both correct, the distance between their two points is the same in both scans. The network uses this rule in two places. It lets each pair pay more attention to the other pairs that agree with it geometrically, and it scores pairs with a spectral method that finds the largest group of mutually consistent pairs. Instead of guessing random subsets the way RANSAC does, it starts from a few reliable pairs and checks the groups around them. The output is one rigid motion between the scans and a label for each pair saying whether it is correct.

TL;DR

PointDSC prunes outlier correspondences for feature-based 3D registration. It adds the rigid-motion length constraint to a nonlocal attention layer, selects seed correspondences, and runs a differentiable spectral matching step on the feature-space neighbourhood of each seed. The authors report 93.28% registration recall on 3DMatch with FCGF features and 78.50% with FPFH, and say it is about 60 times faster than RANSAC-100k tab. 1 §5.1. The released code has no LICENSE file and differs from the paper in several settings (see Paper vs code).

Problem

Feature-based registration first matches local 3D descriptors, and those matches still contain many outliers, especially when the two scene fragments overlap little §1. Individual filters such as the ratio test and reciprocal check use only descriptor similarity §1. Group filters such as RANSAC and spectral matching use geometry, but RANSAC is slow and inaccurate at high outlier ratios, and spectral matching loses its dominant inlier cluster in the same regime §1 §2. Learned outlier rejectors such as DGR and 3DRegNet classify each correspondence on its own and ignore the rigid-motion constraint §1 §2.

Assumptions: two sparse keypoint sets from a partially overlapping pair of 3D point clouds, each keypoint with a local descriptor, and putative correspondences built by nearest-neighbour search on those descriptors §3.

Method

Setup. Each correspondence is a pair of 3D keypoints, c_i = (x_i, y_i) in R^6. The goal is to label each correspondence as inlier (w_i = 1) or outlier (w_i = 0) and to recover one rigid transform between the two point sets §3.

Pipeline §3 fig. 2:

1. Embed the correspondences with the spatial-consistency nonlocal module §3.2.
2. Estimate an initial confidence per correspondence and pick a limited number of confident, well-spread seeds §3.3.
3. For each seed, take its k nearest neighbours in feature space, run neural spectral matching on them, and use the output as weights for a weighted least-squares fit §3.4.
4. Keep the hypothesis with the most inliers §3.5.

The method is hypothesise-and-verify, like RANSAC, but the subsets come from the learned embedding in one shot instead of random minimal samples, and the spectral matching step prunes outliers inside each subset §3.1.

Geometric feature embedding §3.2 fig. 3. The encoder has 12 blocks. Each block is a shared per-point layer, batch norm with ReLU, and a nonlocal layer §3.2. The nonlocal layer follows the nonlocal network idea but adds a spatial consistency term beta to the feature similarity alpha §3.2:

\mathbf{f}_i = \mathbf{f}_i + \mathrm{MLP}\Big(\sum\nolimits_{j}^{|C|} \mathrm{softmax}_j(\alpha_{ij}\beta_{ij})\, g(\mathbf{f}_j)\Big) eq. 1

Here g is a linear projection and alpha is the embedded dot-product similarity §3.2. The spatial term is built from how much the length of a point pair changes between the two scans:

\beta_{ij} = \Big[1 - \frac{d_{ij}^2}{\sigma_d^2}\Big]_+, \qquad d_{ij} = \big|\,\lVert \mathbf{x}_i - \mathbf{x}_j\rVert - \lVert \mathbf{y}_i - \mathbf{y}_j\rVert\,\big| eq. 2

Pairs whose length difference exceeds sigma_d get beta = 0 §3.2. The paper notes that angle-based consistency could also be used, but needs normals, which are hard to estimate on LiDAR data §3.2.

Seed selection §3.3 fig. 4. An MLP on the embedded features gives each correspondence an initial confidence v_i. Non-maximum suppression over these confidences selects well-distributed seeds §3.3. Seeds are capped at 10% of the input at test time §4. The seeding idea is inspired by AdaLAM §3.3.

Neural spectral matching (NSM) §3.4 fig. 5. For each seed, take its k nearest neighbours in the feature space (not in 3D), so the subset can contain points far apart in space §3.4. Build a compatibility matrix M for the subset from the spatial term and a feature term:

M_{ij} = \beta_{ij} \, \gamma_{ij} eq. 3

\gamma_{ij} = \Big[1 - \frac{1}{\sigma_f^2}\,\lVert \bar{\mathbf{f}}_i - \bar{\mathbf{f}}_j \rVert^2\Big]_+ eq. 4

Here f-bar are L2-normalised features and sigma_f is a learned scale §3.4 §4. Set the diagonal of M to zero fig. 5. The leading eigenvector e of M is computed by power iteration; its entries are the inlier probabilities, and only their relative sizes matter §3.4 app. Power iteration. Each seed's hypothesis is then the weighted least-squares fit

\mathbf{R}', \mathbf{t}' = \arg\min_{\mathbf{R},\mathbf{t}} \sum\nolimits_{i}^{|C'|} e_i \, \lVert \mathbf{R}\mathbf{x}_i + \mathbf{t} - \mathbf{y}_i \rVert^2 eq. 5

which has a closed form by weighted SVD (weighted centroids, weighted covariance H, and a determinant correction to exclude reflections) §3.4 app. Derivation.

Hypothesis selection §3.5. Among the seed hypotheses, choose the transform with the most correspondences whose residual is below the inlier threshold tau:

\hat{\mathbf{R}}, \hat{\mathbf{t}} = \arg\max_{\mathbf{R}', \mathbf{t}'} \sum\nolimits_{i}^{|C|} \big[\!\big[ \lVert \mathbf{R}'\mathbf{x}_i + \mathbf{t}' - \mathbf{y}_i \rVert < \tau \big]\!\big] eq. 6

The final labels are w_i = [[ ||R-hat x_i + t-hat - y_i|| < tau ]] eq. 6. The transform is then recomputed by least squares on all surviving inliers §3.5. The authors describe this as common practice §3.5. At test time, a further iteratively re-weighted refinement is run on the inliers, with weights 1 / (1 + (residual / tau)^2) and at most 20 rounds §4 app. Post-refinement.

Loss. Ground-truth labels come from the true pose:

w^*_i = \big[\!\big[ \lVert \mathbf{R}^*\mathbf{x}_i + \mathbf{t}^* - \mathbf{y}_i \rVert < \tau \big]\!\big] eq. 7

The node-wise term is binary cross-entropy on the initial confidence:

L_{class} = \mathrm{BCE}(\mathbf{v}, \mathbf{w}^*) eq. 8

The edge-wise spectral matching term supervises pairs of correspondences. Its target is 1 when both are inliers and 0 otherwise §3.6:

L_{sm} = \frac{1}{|C|^2} \sum\nolimits_{ij} (\gamma_{ij} - \gamma^*_{ij})^2, \qquad \gamma^*_{ij} = \big[\!\big[ c_i, c_j \text{ are both inliers} \big]\!\big] eq. 9

The total loss is

L_{total} = L_{sm} + \lambda L_{class} eq. 10

with lambda a balancing hyperparameter §3.6. The paper sets lambda = 3 §4. The ablation without L_sm lowers 3DMatch recall slightly tab. 5.

Training §4 app. Data augmentation. Each pair is randomly subsampled to 1,000 correspondences, batch size 16 pairs. Optimiser is Adam, learning rate 1e-4, exponential decay factor 0.99, 100 epochs, one RTX 2080 Ti. Augmentation applies a random rotation (uniform in [0, 360) degrees about a random axis), a random translation in [-0.5, 0.5] m per axis, and Gaussian noise with standard deviation 0.005 app. Data augmentation.

Testing §4. The full correspondence set is the input. Seeds come from non-maximum suppression with radius equal to tau, capped at 10% of the input. The seed hypotheses are selected as above, then post-refined.

Pseudocode. Test-time inference, following the steps above. The seed subset uses the paper's kNN in feature space; hyperparameter values are in the table below.

# Test-time inference for one pair of point clouds  [§3] [§4 Testing]
# tau: inlier threshold, 10 cm (3DMatch) or 60 cm (KITTI)  [§5.1] [§5.2]
# Input:  src (N, 3), tgt (N, 3): matched keypoint coordinates
# Output: rotation (3, 3), translation (3,), inlier labels (N,)

def register_pair(src, tgt, corr, tau):
    # Spatial consistency beta for all pairs of correspondences [eq. 2]
    beta = spatial_consistency(src, tgt, sigma_d)     # (N, N)
    # Nonlocal encoder, 12 blocks, attention weighted by beta [eq. 1]
    feats = nonlocal_encoder(corr, beta)              # (N, d)
    # Initial inlier confidence from an MLP [§3.3]
    confidence = mlp(feats)                           # (N,)
    # Seeds: non-maximum suppression at radius tau, at most 10% [§3.3] [§4]
    seeds = nms_seeds(src, confidence, radius=tau, max_num=int(0.1 * N))
    # One weighted least-squares hypothesis per seed [§3.4]
    hypotheses = [fit_seed(s, feats, src, tgt) for s in seeds]
    # Keep the hypothesis with the most inliers within tau [eq. 6] [§3.5]
    rotation, translation = best_by_inlier_count(hypotheses, src, tgt, tau)
    # Refinement on inliers, at most 20 rounds [app. Post-refinement]
    rotation, translation = refine(rotation, translation, src, tgt, tau)
    labels = residual(rotation, translation, src, tgt) < tau
    return rotation, translation, labels

# One hypothesis from a seed and its feature-space neighbours [§3.4]
# k = 40 (neighbourhood size) [§4] [app. Effect of neighbourhood size]

def fit_seed(seed, feats, src, tgt, k=40):
    # The k nearest neighbours of the seed in feature space, seed excluded
    subset = knn_in_feature_space(feats, seed, k)     # (k,)
    # Feature similarity gamma on L2-normalised features [eq. 4]
    gamma = feature_similarity(feats[subset])         # (k, k)
    # Spatial consistency inside the subset [eq. 2]
    beta = spatial_consistency(src[subset], tgt[subset], sigma_d)
    # Compatibility M = beta * gamma with zero diagonal [eq. 3] [fig. 5]
    compat = beta * gamma
    set_diagonal(compat, 0)
    # Leading eigenvector by power iteration; entries are inlier scores
    weights = leading_eigenvector(compat)             # (k,)
    # Weighted least-squares fit by weighted SVD [eq. 5] [app. Derivation]
    rotation, translation = weighted_rigid_fit(
        src[subset], tgt[subset], weights)
    return rotation, translation

# Post-refinement on inliers  [app. Post-refinement]
# Weights phi_i = 1 / (1 + (residual_i / tau)^2) on inliers

def refine(rotation, translation, src, tgt, tau):
    previous_count = 0
    for iteration in range(20):
        # Residual of every correspondence under the current transform
        residual = norm(rotation @ src + translation - tgt)
        inlier = residual < tau
        count = sum(inlier)
        # Stop when the inlier count no longer changes
        if abs(count - previous_count) < 1:
            break
        previous_count = count
        phi = 1 / (1 + (residual / tau) ** 2)
        rotation, translation = weighted_rigid_fit(
            src[inlier], tgt[inlier], phi[inlier])
    return rotation, translation

# Training loss for one batch  [§3.6] [eq. 7] [eq. 8] [eq. 9] [eq. 10]
# Inputs: logits (B, N): initial confidence v
#         gt_labels (B, N): inlier labels w* from the true pose [eq. 7]
#         gamma (B, N, N): feature similarity, diagonal zero
#         lam: lambda, 3 in the paper [§4]
# Output: scalar loss

def training_loss(logits, gt_labels, gamma, lam):
    # Node-wise binary cross-entropy on the initial confidence [eq. 8]
    loss_class = bce_with_logits(logits, gt_labels)
    # Edge target: 1 only where both correspondences are inliers [eq. 9]
    gt_compat = gt_labels[:, :, None] * gt_labels[:, None, :]
    # Mean squared error over all N * N entries [eq. 9]
    loss_sm = mean((gamma - gt_compat) ** 2)
    # Weighted sum [eq. 10]
    return loss_sm + lam * loss_class

Hyperparameters

Results

Author-reported. Setup: 3DMatch test set, 8 scenes, 1,623 fragment pairs, 5 cm voxels, tau = 10 cm, FCGF or FPFH correspondences; baselines are described in app. Implementation Detail of Baseline Methods §5.1. Average Time excludes the construction of initial correspondences tab. 1.

Metric definitions §5.1 eq. 11: RR is the share of pairs with TE below 30 cm and RE below 15 deg. IP is kept inliers over kept matches, IR is kept inliers over all inliers, and F1 combines them.

\mathrm{RE}(\hat{\mathbf{R}}) = \arccos\frac{\mathrm{Tr}(\hat{\mathbf{R}}^T\mathbf{R}^*) - 1}{2}, \qquad \mathrm{TE}(\hat{\mathbf{t}}) = \lVert \hat{\mathbf{t}} - \mathbf{t}^* \rVert_2 eq. 11

Table 1a, 3DMatch with FCGF tab. 1

Table 1b, 3DMatch with FPFH (same model, not fine-tuned) tab. 1

Reading the tables: with FCGF, GC-RANSAC-100k has higher IR and PointDSC has higher RR, F1 and lower RE and TE; the paper says SM and TEASER have a slightly higher IP than PointDSC §5.1. The text puts the speed gap at about 60 times against RANSAC-100k, which matches 5.50 s over 0.09 s §5.1 tab. 1.

Table 2, KITTI with FPFH (setting: TE < 60 cm, RE < 5 deg) tab. 2. The header does not print units; the thresholds in §5.2 suggest degrees and cm.

Table 3, augmented ICL-NUIM, multiway registration, ATE in cm tab. 3. Baseline rows are copied from the DGR paper §5.3.

PointDSC has the lowest average ATE (15.18 cm). The text says it is lowest on three of the four scene types §5.3.

Table 4, nonlocal module ablation on 3DMatch tab. 4. "PointCN" is the 3D version of the PointCN network that 3DRegNet uses; "Nonlocal" is the nonlocal operator without the spatial term §5.4.

Table 5, neural spectral matching ablation tab. 5. Rows are cumulative.

Generalisation and other results. Four further results from the appendix: (i) KITTI with FCGF, where the 3DMatch-trained model reaches 97.84% RR and the re-trained one 98.20% app. Additional experiments; (ii) on 3DLoMatch, adding PointDSC raises FCGF from 35.7 to 52.0 and Predator from 54.2 to 61.5 at 5,000 points, with a 2.50 average gain for Predator app. 3DLoMatch; (iii) a prioritised RANSAC that samples by the predicted inlier probability reaches 74.31% RR with 1k iterations against 40.05% for classic RANSAC-1k, and its local variant reaches 78.00%; both are below PointDSC's 78.50% on FPFH app. Prioritized RANSAC; (iv) joint training with the D3Feat detector gave no gain for the feature network app. Joint training.

Figures. fig. 6 shows that inlier pairs have feature similarity concentrated near 0.8 with the nonlocal module, which the authors read as inliers lying close in the embedding §5.4. fig. 7 shows examples at high outlier ratios on 3DMatch and KITTI, with RANSAC-100k for comparison §5.5.

Runtime app. Time complexity. On 3DMatch (about 5,000 correspondences per fragment), the nonlocal encoder takes 62.0 ms, seed selection 2.0 ms, NSM 14.4 ms and post-refinement 11.1 ms, for 89.5 ms overall. Measured on an 8-core Xeon E5-2620 and a GTX 1080 Ti.

Paper vs code

Code: https://github.com/XuyangBai/PointDSC at commit b009d536ac10b570853833f2178397c154745da9. The repository has no LICENSE file, so the code is cited by path and line only and nothing is quoted from it. The repository belongs to the first author and is linked from the paper's abstract p. 1. Checked: model, loss, trainer, config, dataset loaders, KITTI and 3DMatch evaluation, and the two released snapshot configs.

• Loss weight. Paper: lambda = 3 §4 eq. 10. Code: both weights 1.0 config.py config.json and the trainer uses w_class * L_class + w_sm * L_sm trainer.py. The effective ratio in the released configs is 1, not 3, unless the weights are overridden at launch (the README gives no override).
• Training epochs. Paper: 100 epochs §4. Code: 3DMatch release config 50 config.json; KITTI release 100 config.json.
• Outdoor sigma_d. Paper: 60 cm for outdoor scenes §4. Code: sigma_d = 1.2 m for KITTI, both in the released config config.json and the test script test_KITTI.py. The test script's 1.2 is 120 cm, double the paper's value.
• Outdoor inlier threshold. Paper: 60 cm for KITTI §5.2. Code: 0.6 at test test_KITTI.py and in the released config config.json. The training default is 1.2 m config.py.
• Post-refinement threshold. Paper: 60 cm for KITTI app. Post-refinement. Code: the refinement uses a fixed list, 0.10 when the threshold is 0.10 and 1.2 for any other value PointDSC.py. The KITTI test sets tau to 0.6, so refinement uses 1.2 there.
• Seed selection during training. Paper: non-maximum suppression picks the seeds §3.3. Code: training takes the top 10% by confidence with no NMS PointDSC.py. NMS is used only at test PointDSC.py.
• Noise augmentation. Paper: Gaussian noise with standard deviation 0.005 app. Data augmentation. Code: 3DMatch loader adds uniform samples in [0, 0.005) to each coordinate, which is one-sided and not zero-mean ThreeDMatch.py.
• Feature-similarity form. Paper: 1 minus squared distance of normalised features over sigma_f^2 eq. 4. Code: 1 minus (1 - cosine) over sigma^2 PointDSC.py. For unit vectors the squared distance is 2 (1 - cosine), so the two agree up to a factor of 2 absorbed into the learned scale. Code initialises sigma at 1.0 PointDSC.py.
• Attention scaling. Paper: softmax of alpha times beta eq. 1. Code also divides the dot product by sqrt(channels) before multiplying by beta PointDSC.py PointDSC.py.
• Test-time point cap on KITTI. Paper: full correspondence set at test §4. Code: KITTI test caps the input at 12,000 correspondences test_KITTI.py. The 3DMatch test uses all points test_3DMatch.py.
• Voxel size default. Paper: 5 cm for 3DMatch §5.1. Code: training default 3 cm config.py; the released 3DMatch config is 5 cm config.json.
• Agreed. Batch size 16 §4 and 1,000 sampled correspondences §4 match config.py config.py. Adam, learning rate 1e-4 and decay 0.99 §4 match config.py config.py. The 10% seed cap §4 matches config.py. The NMS radius equal to tau §4 matches test_3DMatch.py. The 20-round refinement cap app. Post-refinement matches PointDSC.py.

Pitfalls

• Settings with conflicting values in the paper and code. The lambda, epoch, KITTI sigma_d, KITTI refinement threshold and noise details above are the ones that matter for reproduction. The released KITTI model and test script use tau = 0.6 with sigma_d = 1.2, which is not the paper's stated 60 cm sigma_d. Use the released configs to reproduce the reported numbers, and say which one you followed.
• Unstated in paper: seed subset. The kNN in feature space uses ignore_self so the seed is not part of its own subset, and the subset has k neighbours common.py PointDSC.py. The paper says "k nearest neighbours" without saying whether the seed is included.
• Unstated in paper: zero diagonal in loss. The model zeroes the diagonal of M PointDSC.py, and the loss zeroes the diagonal of the target matrix loss.py. Section 3.6 says nothing about either. The Figure 5 caption mentions the zero diagonal for the graph fig. 5.
• Power iteration cap. The paper gives the typical convergence (fewer than five iterations) but no cap. The code uses at most 10 iterations with an early stop when the vector stops changing config.py PointDSC.py.
• Normalisation of weights. Weights are normalised to sum to 1 with a small epsilon before the weighted fit PointDSC.py. The paper says only relative values matter §3.4, which is consistent, but the epsilon is a numerical guard the paper does not mention.
• sigma_f is unconstrained. It is a free parameter that enters as 1 over sigma squared, and the code does not clamp it PointDSC.py. A reimplementation should watch for the value drifting toward zero.
• Cost of the nonlocal layer. Each block forms a full N-by-N attention matrix PointDSC.py. Training uses 1,000 correspondences, but test inputs are about 5,000 per fragment on 3DMatch app. Time complexity, and the nonlocal encoder is most of the runtime (62.0 of 89.5 ms) app. Time complexity.
• Baselines are authors' re-implementations. SM and 3DRegNet are re-implemented by the authors; SM uses a top-10% selection rather than the greedy discretisation, and 3DRegNet is trained with classification loss only app. Implementation Detail of Baseline Methods. TEASER is run with reciprocal check. Compare against these choices, not against the original methods.
• Multiway baselines are copied. The ICL-NUIM baseline numbers are taken from the DGR paper, not re-run §5.3.
• DGR F1 in Table 2 looks inconsistent. It is printed as 4.51 F1 next to 73.69 RR tab. 2. Check the source before relying on it.
• Low overlap and symmetric scenes. Gains shrink with fewer than about 500 correspondences app. 3DLoMatch. The main failure is large symmetric surfaces such as walls and floors, which yield 90 or 180 degree rotation errors when outlier clusters become dominant app. Qualitative Results fig. 7.
• Joint training is not validated. The end-to-end attempt with D3Feat did not improve the feature network app. Joint training.
• No licence on code. The repository has no LICENSE file. Do not copy code from it; implement from the pseudocode above and cite the paths.

Lineage

• Builds on: spectral matching [leordeanu2005spectral] for the compatibility-graph idea, and the nonlocal network [wang2018non] for the attention layer, with the spatial term added §3.2. The seeding idea is inspired by AdaLAM [cavalli2020adalam] §3.3.
• Uses descriptors FCGF [Choy_2019_ICCV] and FPFH [rusu2009fast] §5.1.
• Compared against: RANSAC [fischler1981random], GC-RANSAC [barath2018graph], FGR [zhou2016fast], TEASER [Yang20arXivTEASER], DGR [choy2020deep], 3DRegNet [pais20203dregnet] and PointCN [moo2018learning] §5.1 §5.4.
• Superseded by: not stated in this wiki.