How two frames find each other

Rung one · correspondences known

The lucky case has a closed form

Suppose an oracle supplies pairs: source point $p_i$ and target point $q_i$ represent the same landmark, possibly with noise. We use $T(p)=Rp+t$, with $R\in SO(d)$, $R^\top R=I$, $\det R=1$, and $t\in\mathbb R^d$. Thus reflections and scale changes are excluded. The paired least-squares problem is

With fixed pairs and isotropic squared residuals, no iterative pose initialization is needed. Center the points, set $H=\sum_i\tilde p_i\tilde q_i^\top=U\Lambda V^\top$, and use the proper-rotation correction $D_c=\operatorname{diag}(1,\ldots,1,\det(VU^\top))$: $\hat R=VD_cU^\top$, $\hat t=\bar q-\hat R\bar p$. Without $D_c$, the SVD can return a reflection. In two dimensions this reduces to

Here $a\times b=a_xb_y-a_yb_x$ is the scalar planar cross product. Solve finds the global minimum of this paired least-squares objective, not necessarily the true motion. Noise and incorrect pairs can move the optimum. Distinct source points are needed to determine a planar rotation; in 3-D, three noncollinear correct pairs suffice in the noise-free rigid case. Collinearity in 3-D leaves rotation about the line undetermined. Drag the display to change its starting pose, then solve: the algebraic result is independent of that start.

A noisy fit generally has a nonzero residual. Its expected size depends on which clouds are noisy, the noise covariance, the number of points, and fitted parameters; there is no universal rule that a below-noise residual proves overfitting. Compare the clean, noisy, and outlier scenes. The solver still minimizes its objective when the correspondences are bad, but the minimizing pose can be poor.

Rung two · correspondences corrupted

Real matchers lie: RANSAC

A feature matcher proposes correspondences, some of which are incorrect because of repeated structure, occlusion, or motion. Ordinary least squares has unbounded sensitivity to gross contamination in its translation estimate: its asymptotic replacement breakdown point is zero. That does not mean every incorrect match ruins a fit. The gray ghost shows the least-squares solution using all proposed pairs; compare it with the consensus solution.

RANSAC fits hypotheses to small random subsets, counts matches within a distance threshold $\varepsilon$, and refits a strong consensus. Two distinct paired points give a minimal planar rigid hypothesis; exact interpolation also requires compatible interpoint distances. Noisy pairs instead give a least-squares hypothesis. Three noncollinear pairs are the usual 3-D rigid minimum. Under independent sampling with all-inlier probability approximated by $w^s$, the trial count is

Here $0

Try this: increase the outlier fraction and watch the estimated trial budget grow. Then widen $\varepsilon$: more matches count as inliers, including false ones. Tighten it too far and genuine noisy pairs are rejected. A high sampling confidence cannot repair a poor threshold or repeated geometry.

Rung three · correspondences unknown

No correspondences at all: ICP

A raw lidar scan is an unpaired point set, although geometric descriptors can be computed. Without trusted feature matches, pose and correspondence are coupled: a pose suggests matches, and fixed matches allow a pose fit. ICP alternates nearest-neighbor assignment and pose estimation. In the point-to-point version, the second step is the paired rigid least-squares solve.

For a fixed source set, exact nearest neighbors, and exact point-to-point fitting, $E(T)=\sum_i\min_j\|Tp_i-q_j\|^2$ is non-increasing and bounded below, so its values converge. This is not a global-optimality or correct-pose guarantee; pose convergence and local-optimality statements need additional conditions. The demo gates distant pairs and trims a fraction of the surviving set. Its displayed RMS therefore changes its contributing points and need not be monotone. Trimming or gating does not inherently remove every descent guarantee: fixed-count trimmed and capped-distance objectives admit appropriate monotonic formulations.

Try this: compare a nearby start with a large rotation, then switch noise, outliers, and trimming independently. Record both the residual and the error against the simulated truth. A small change in RMS only triggers a stopping rule; it does not prove the pose is right. Repeated walls, insufficient overlap, and a moving inlier set can make a convincing but incorrect fit.

Rung three and a half · a point meets a wall

Point-to-plane, GICP & robust kernels: matches with structure

Vanilla ICP's residual pretends the reference is a bag of isolated points. But it is a wall, sampled at arbitrary positions: the point your nearest neighbor should have matched almost never exists in the other scan, so point-to-point drags every pair all the way together and crabs sideways along every wall. Chen & Medioni's point-to-plane residual fixes the model instead of the matches: estimate a surface normal $n_j$ at each reference point (PCA over its neighbors — the blue ticks in the demo below, drawn once its residual selector is set to point-to-plane), and penalize only the error component across the surface,

Sliding within a single plane does not change the point-to-plane residual. That can avoid unnecessary tangential motion, but also creates unobservable directions: a single infinite plane cannot determine its two tangential translations or rotation about its normal. A useful 3-D fit needs sufficiently varied geometry; the planar demo needs varied line normals. We linearize and solve a 3-parameter Gauss–Newton system here (6 parameters in 3-D). GICP uses anisotropic covariances on both sides:

Isotropic combined covariance gives a scaled point-to-point objective. A normal-direction precision matrix with zero tangential precision gives point-to-plane as a limiting case, not merely any finite thin covariance. In GICP the covariance sum depends on $R$. The demo freezes it within each Gauss–Newton step; this is an approximation to optimizing the full rotation-dependent objective.

Point-to-plane uses target normals; GICP uses local orientation from both clouds. Canonical GICP typically assigns prescribed tangent/normal eigenvalues after estimating orientation by PCA. These are surface-model covariances, not automatically calibrated uncertainty in a normal estimate: an unreliable normal does not necessarily inflate its covariance. Both methods can help on well-observed surfaces and fail on poor normals or degenerate geometry. Neither must have the same basin or fewer iterations than the other.

Robust losses reduce the influence of large residuals. Huber has quadratic behavior near zero and linear, unbounded tails; Tukey's loss is bounded. For a nonnegative residual magnitude $r$ and scale $s>0$, their IRLS weights are below, with the Huber weight defined as 1 at $r=0$. The demo computes its weights from Euclidean pair distances for all three residual models. Its $1.4826\,\mathrm{MAD}$ scale is a heuristic for these nonnegative distances, not a calibrated Gaussian standard deviation or exact residual-specific IRLS for GICP.

Huber caps the magnitude of the scalar residual's influence, but convexity in a residual does not make the pose-and-association problem convex. Tukey can reject a pair completely, potentially discarding useful data when the starting pose is poor. Robust weights change the objective and can change its basin; they offer no global-registration guarantee. Compare the same residual with different weighting rules, keeping the scene and start fixed.

Try this: start close to the truth and compare point-to-point, point-to-plane, and GICP under clean data, then under noise and outliers. Repeat from a distant pose. Compare rotation and translation error, not iteration count alone. The same threshold or robust scale need not suit different residuals. Removing the largest distances under pure noise also discards genuine observations; whether that helps depends on sampling, overlap, and geometry.

Rung four · point-to-cell association

NDT: approximate local geometry with Gaussian cells

NDT replaces raw target-point search with point-to-cell association. Each sufficiently populated grid cell is approximated by a Gaussian. The mean and covariance summarize that Gaussian model; they do not preserve arbitrary multimodal geometry inside the cell. Subdivide the plane into cells of side $h$. The teaching implementation keeps cells with at least three points and uses the maximum-likelihood covariance normalization $1/n_c$:

A wall segment often yields an elongated covariance, whereas mixed surfaces may produce a broader one. These shapes depend on sampling and cell boundaries as well as sensor noise. The implementation discards nearly coincident cells ($\lambda_{\max}<10^{-9}$) and floors the other eigenvalue at $0.001\lambda_{\max}$ before inversion. Its cellwise exponential is an unnormalized alignment score, not a globally normalized probability density:

Hover over cells to inspect their fitted Gaussians. Change the noise and cell size, then nudge the grid without moving any points. The fitted map changes because the cell memberships change. A single Gaussian may blur a corner or merge unrelated surfaces; this is approximation error, not simply sensor uncertainty.

Try this: reduce $h$ to preserve finer structure, while watching sparse cells disappear. Increase $h$ and observe merged surfaces. The cellwise score can jump across boundaries because adjacent cells have different Gaussian parameters. Cell size changes representation, coverage, and optimization behavior; it is not a pure smoothing parameter.

Rung four · score a pose

Registration becomes function evaluation

For this subsection only, $p=(t_x,t_y,\varphi)$ is a pose vector, not a source point. Transform scan points by $T_p(x)=R(\varphi)x+t$, perform a constant-time lookup per grid (under the usual hash-map assumption), and sum cell scores. Empty or discarded cells contribute zero. This chosen score omits Gaussian determinant factors; it is not a log-likelihood and alternative NDT formulations use different objectives.

where $(\mu_{ig},\Sigma_{ig})$ is the Gaussian of the cell of grid $g$ that $T_p(x_i)$ falls into. The inner sum is Biber's answer to the discretization sensitivity you just saw: keep four copies of the grid, each shifted by half a cell horizontally, vertically, and both, and let every point be scored by all four cells it lands in. The shifted grids reduce sensitivity to individual cell boundaries, but their sum is not guaranteed to be continuous or globally analytic.

The heatmap below is this score over candidate translations, rotation held at the slider value — dark is high. The green ring marks the true pose. Click anywhere to drop a start, and a translation-only Newton iteration (the next section's machinery, with $\varphi$ frozen) runs on the actual score function and draws its path.

Try this: hold rotation fixed, move the translation start, and compare one grid with four shifted grids. The shifts reduce some boundary artifacts without guaranteeing continuity. Noise may broaden fitted Gaussians, but it can also corrupt the optimum; outliers can create distracting cells. An offset from ground truth in one noisy realization is estimation error, not evidence of statistical bias, which is an expectation over repeated data. Translation-only optimization cannot correct a rotation error.

Rung four · climb

Newton's method, Hessian included

For fixed point-to-cell assignments, the Gaussian score is analytic in the pose, so its gradient and Hessian have closed forms. With hard cell lookup, the full objective is generally only piecewise analytic; the formulas below apply within a region of unchanged cell assignments. Only the rotation makes $T_p$ nonlinear, and in the plane its derivatives are two short vectors:

and the translation derivatives are constant. Writing $f=-s$ (minimize the negative score), $s_i=\exp(-\tfrac12\tilde q_i^{\;\top}\Sigma_i^{-1}\tilde q_i)$ for each point–cell pair, and suppressing the sum over the four grids, the derivatives are

The code solves $(H+\lambda I)\Delta p=-g$, increases damping geometrically until Cholesky succeeds, caps the step, and accepts only a score improvement after backtracking. It is $H+\lambda I$, not necessarily $H$, that becomes positive definite. These are local safeguards, not a certificate of a maximum. Rotation is in radians and translation in world units; damping and step limits therefore depend on the parameter scaling.

Try this: compare Run with Coarse → fine from the same pose, then change cell size or rotation. A schedule can improve reach but cannot guarantee the correct basin, and changing the grid changes the objective. No improving tested step, a tiny gradient, or an iteration cap means stopped, not necessarily aligned. The truth score is available only in this synthetic demo. Real systems need overlap, consistency, observability, and independent verification checks; there is no universal NDT angular capture range.

The wider field · the contestants

Three answers to one question: what stands in for the matches?

The following comparison is inspired by the registration families studied in MMD-Reg (Crane et al., 2026). Its geometry, noise, dimensionality, solvers, and tuning are different. Treat the browser race as a controlled teaching experiment, not a reproduction of the paper's benchmarks.

Every local registration method minimizes some misalignment measure between a transformed source cloud and a target cloud. Since true correspondences are unknown, each family substitutes something for them — and that substitution is the method. Hard-correspondence methods commit to one nearest neighbor per point and re-decide each iteration. Soft-correspondence methods let every source point fractionally match every target point, weighted by a probabilistic model. Correspondence-free MMD-Reg matches no points at all: it compares the two clouds as distributions, through the distance between their kernel mean embeddings.

Read the next sections for soft assignments and mean embeddings, then use the race to compare their simplified implementations. RANSAC, GICP, and NDT provide additional examples. Two experimental panels transplant one-to-one association ideas from tracking; neither establishes that a tracking filter is a suitable point-cloud registration method. The final walkthrough adds a learned-flow analogy.

The wider field · the soft family

Soft assignment: registration as mixture fitting

CPD places Gaussian mixture components at transformed source points $\mathcal T(y_m)$ and treats fixed points $x_n$ as observations. Here $M$ is the source count, $N$ the target count, $w\in[0,1)$ the outlier-mixture weight, and $\sigma$ the isotropic Gaussian standard deviation. With a uniform clutter density $1/V$ inside an observation window of volume $V$, posterior responsibilities are as follows. An exact E-step and an M-step that increases the auxiliary objective cannot decrease the likelihood of a fixed model. Changing a bandwidth by schedule, approximate filtering, or an unchecked linearized step does not automatically retain that guarantee.

Each target point divides probability between Gaussian components and the outlier component. The displayed formula uses a spatial density $1/V$; CPD's original $1/N$ convention instead yields $M/N$ in the final denominator term. With fixed responsibilities, the rigid or similarity M-step is weighted Procrustes. CPD can also update $\sigma^2$ by maximum likelihood. This update is not a prescribed annealing schedule and need not decrease at every iteration. As $\sigma\to0$, a unique nearest component dominates conditional on an inlier assignment. With positive clutter density and nonzero distances, unconditional inlier probabilities can instead vanish.

CPD supports rigid, similarity, and non-rigid formulations. The non-rigid variant introduces a smooth displacement regularizer. The walkthrough below enables a similarity scale $s$; rigid CPD fixes $s=1$. A naive E-step costs $O(MN)$, but storing the whole matrix is not necessary: sufficient sums can be accumulated in blocks, and Gaussian-transform approximations can accelerate them. The full matrix is retained here to visualize the assignments.

FilterReg puts Gaussian components on the fixed cloud and queries them with moving points. Gaussian-weighted mass and first moments provide a soft target and confidence for each query; additional moments support variance updates and other residuals. A customized permutohedral-lattice filter accelerates these sums, and a twist-based Gauss–Newton M-step supports rigid, articulated, or deformable models. FilterReg can optimize isotropic variance analytically (Section 3.3 of the paper). Fixing the bandwidth allows index reuse; changing it can require rebuilding the filter. Approximate filtering and linearized steps must be distinguished from exact EM.

Runtime comparisons depend on point count, implementation, bandwidth, hardware, and stopping criteria; the browser demos are not timing reproductions of the original papers. GMMReg takes a different route: fit mixtures to both clouds and minimize their $L_2$ density distance. It is distribution matching, not a CPD-like soft-correspondence E-step. Both this construction and kernel mean embeddings compare distributions, but their parameterizations and objectives differ.

Implementation boundary. The race's green panel is an annealed Gaussian soft-target heuristic, not full CPD. It normalizes each moving point's target weights with a constant score offset 0.12, rejects low-support rows, and applies weighted Kabsch. The offset is not a fixed outlier probability: its effective weight changes with bandwidth and point count. Its source/target normalization is also opposite to the CPD formula above. The final walkthrough, rather than this race panel, implements similarity CPD's variance update.

The wider field · the new objective

What MMD-Reg actually minimizes

GMMReg ended the last section comparing two fitted densities; MMD-Reg keeps the density view and drops the fitting — no mixture is estimated, the clouds enter directly. Maximum Mean Discrepancy embeds a distribution $P$ into a reproducing kernel Hilbert space by averaging the kernel's feature map, $\mu_P=\mathbb{E}_{x\sim P}[k(x,\cdot)]$, and measures the distance between two distributions as the distance between their embeddings:

For a characteristic kernel, exact population MMD vanishes only when the two probability measures agree; densities need not exist. Point clouds define empirical measures, which can differ because of sampling density, partial overlap, or outliers even at the correct pose. Exact pairwise evaluation is quadratic. Random Fourier features approximate the Gaussian kernel by sampling $D$ frequencies $\omega_k\sim\mathcal N(0,\ell^{-2}I)$:

so the squared MMD becomes the squared distance between two feature means — one pass over each cloud, linear in the number of points. Registration is then the nonlinear least-squares problem — here $X$ is the moving cloud and $Y$ the fixed one, the reverse of CPD's lettering —

Levenberg–Marquardt optimizes this nonconvex residual. Larger $\ell$ often makes a broader alignment signal; smaller $\ell$ can resolve detail, but neither choice guarantees accuracy or a particular basin. A scale schedule changes the objective between stages. Every finite-$D$ feature objective is smooth; more frequencies improve approximation fidelity, not differentiability. Its $2D$-dimensional embedding is not itself characteristic. For an isolated selected optimum and a nonsingular pose Hessian, the implicit function theorem gives $\partial\theta^\star/\partial\mathcal D=-[\nabla^2_{\theta\theta}F]^{-1}\nabla^2_{\theta\mathcal D}F$. This local derivative can fail at degeneracy or when the selected minimum switches.

The wider field · the race

Same scans, same start — nine solvers

All nine panels receive the same seeded clouds. Local methods receive the same initial pose; RANSAC's geometric pair-congruence search ignores it. GICP uses frozen-covariance steps, NDT uses a coarse-to-fine grid schedule, and MMD uses a random-feature scale schedule. The BP panel approximates one-to-one association marginals. The hypothesis-mixture toy samples randomized greedy one-to-one assignments and averages their pair weights. It is not PMBM: there are no Poisson components, Bernoulli existence updates, or propagated multi-object posterior. Both association toys share a heuristic miss score of 0.12 with the soft-target panel. One-to-one landmark constraints need not model independently sampled surface points. Noise, density, and outlier controls create illustrative stresses, not the paper's PCPNet datasets.

The panels report relative rotation error (RRE) and relative translation error (RTE) against known synthetic truth. The benchmark runs 25 seeds $40+13k$, $k=0,\ldots,24$, with the current controls and a 70-step cap. It reports medians, rotation-only counts, and joint success: RRE < 5° and RTE < 0.2 world units. These are demo thresholds, not a standardized benchmark. A finite run is not a universal ranking, and capped iterations are not time measurements. Real systems lack ground truth: use overlap, residuals, conditioning, motion consistency, and independent validation rather than interpreting a low objective as proof. The inline solvers and the regression tests in the website repository are the source for this reviewed version; the separate companion repository may differ.

Try this: benchmark one setting, change only the starting rotation, and benchmark again. Compare both error coordinates and the joint count. Then vary overlap-related sampling, noise, and outliers separately. Changes can reflect model mismatch, optimization, or random-feature approximation; the leaderboard alone cannot identify the cause. These particular implementations and fixed budgets do not establish an ordering of the published methods.

The wider field · the landscape

Objective smoothness is not a convergence guarantee

This heatmap is the objective itself, evaluated over candidate translations (rotation held at the truth): dark is low. Click anywhere to drop a start point and the matching optimizer runs — Levenberg–Marquardt on the MMD surface, translation-only gated ICP on the nearest-neighbor surface. Toggle between the two objectives and move the sliders: this is the difference the paper is built on, drawn as terrain.

Try this: vary $\ell$, reduce $D$, and resample the frequencies while keeping the data fixed. Look for changes in local minima, not a promise of a single broad bowl. The nearest-neighbor heatmap now uses the capped squared-distance objective $\frac1M\sum_i\min\{\min_j\|Tp_i-q_j\|^2,\tau^2\}$ with fixed denominator. The plotted translation-only gated ICP step is a descent step for that objective. A finite nearest-neighbor minimum is continuous and piecewise differentiable; it can have kinks at assignment switches. Hard associations do not remove all local gradients. Neither this surface nor smooth MMD is globally convex.

The wider field · reading the race

What actually separates the families

Hard association is a modeling choice. ICP can work very well with a suitable initialization and sufficient overlap. Normals and robust losses change its residual model; gating and subsampling change which data matter. None makes it immune to repeated structures or bad geometry. Point-to-plane may reduce tangential fitting motion, but can also introduce unobservable directions. Read the paper-specific comparisons as evidence under their protocols, not universal speed or robustness claims.

Soft association models alternatives. A uniform component can reduce the influence of poorly explained observations when its assumptions and scale are suitable; it does not guarantee outlier rejection. Naive all-pairs evaluation is quadratic, but blocked accumulation and Gaussian filtering change the memory and computational costs. The green race panel is a heuristic, whereas the walkthrough separates actual CPD-style updates from a FilterReg-inspired sparse-grid approximation.

MMD compares empirical distributions. With a fixed frequency count, evaluating source and target means costs $O((M+N)D)$; a fixed target mean can be cached. GPU parallelism can improve runtime, but does not make arbitrary-size computation constant-time. Outliers, density imbalance, and nonoverlap perturb the embedding and can shift the optimum. Learned initialization, scales, or overlap weights can help in the variants that use them, not guarantee removal of bias. Differentiating a selected optimum requires the regularity conditions stated above.

Learned flow offers a different inference route. Register Any Point (RAP) uses conditional flow matching to generate registered coordinates, with test-time rigidity enforcement and rigid pose readout. It does not require a supplied initial pose, but this is not a global-correctness or out-of-distribution guarantee. Its learned field, integration, and rigidity projections still perform inference and use runtime state. The small planar network below is an analogy, not RAP's transformer, official implementation, or benchmark. Its successes and failures cannot be attributed to RAP.

Coarse-to-fine processing is useful, not universal. A distance gate selects pairs, a grid size controls representation, and Gaussian or kernel bandwidth controls interactions. These knobs are not interchangeable, and CPD's estimated variance is not a deterministic schedule. Compare what each knob changes before interpreting a wider-looking basin as a stronger guarantee.

The finale · one scene, four inference representations

What each method keeps — step by step

The walkthrough contrasts four kinds of intermediate state. Its CPD panel stores a full responsibility matrix for display; this is not a compulsory memory cost of CPD. The FilterReg-inspired panel computes soft targets and confidences through filtered moments. MMD retains feature means and a $2D$-entry residual, with no discrete assignments. The flow panel uses learned weights and evolving coordinates, signatures, and activations. The distinction is the representation used for inference, not whether runtime memory exists.

Use Next, Auto, or a stage chip to inspect each loop. CPD displays responsibilities, centering, rotation, translation/scale, and variance estimation. FilterReg-inspired processing displays density, filtering, querying, and a twist update. MMD displays encoding, averaging, comparison, and optimization. The fourth panel shows a learned-flow analogy. The scale switch deliberately makes the moving cloud 15% smaller. Similarity CPD can estimate the required inverse scale (ideally $1/0.85$), while the other two classical panels are constrained to rigid motion. This is a difference in the enabled models, not an inherent inability to run rigid CPD or extend another method to similarity.

What to look for. Compare where the outlier component enters: the fixed observations in CPD versus moving queries in the reversed mixture. The MMD demo has no outlier component; all points affect the means. Its 48 frequencies produce 96 residual entries. Implementation details: similarity CPD uses weighted closed-form updates; the FilterReg-inspired demo uses a sparse Cartesian Gaussian grid, not the paper's permutohedral lattice, with a bandwidth schedule and one Gauss–Newton step; MMD uses LM and a kernel schedule. The mixture demos use a constant clutter-density parameter $1/36\;\mathrm{u}^{-2}$, not an estimated true clutter distribution. The flow panel contains embedded MLP weights, but the deployed page supplies no training log or independently reproduced generalization study. Treat its behavior as a constrained teaching example, not evidence of accuracy from arbitrary starts, a RAP ablation, or a reliable unseen-scale failure claim. Auto stopping and iteration limits are not certificates of alignment.

The bookkeeping examples reveal different representations: weighted pairs, filtered moments, distribution embeddings, and learned coordinate evolution. Their behavior also depends on residuals, overlap, constraints, approximation, and optimization. Memory alone does not determine robustness or accuracy.