1 / 21FRAME REGISTRATION / A TEACHING GUIDERigid frame registration.Separate the correspondence model, the alignment objective, and the optimizer.Which point is which?How far did it move?A ladder of correspondence assumptions—known, corrupted, unknown, cell-based—followed by soft and correspondence-free alternatives.01Known pairs02Unknown pairs03No pairs at all01 The problem & the ladder →02 Closed form & RANSAC →03 ICP & structured residuals →04 NDT score landscape →05 Soft & correspondence-free →06 Compare, evaluate, verify →21 SLIDES · 3 LIVE LABS · PLANAR SE(2) TEACHING MODELSBai Liping · companion article: bailiping.com/frame-registration · reviewed 24 Sep 2026
2 / 21CONTENTSWhat’s inside.Every entry opens its slide. Each live lab follows its introduction.03 Two clouds, one rigid motion04 The correspondence ladder05 Kabsch–Umeyama: the closed form06 RANSAC: consensus over trust · LIVE LAB08 ICP: alternate guess and solve · LIVE LAB10 Reshape the cost, not the loop11 NDT: match against a Gaussian field · LIVE LAB13 What should replace correspondences?14 CPD: registration as mixture fitting15 FilterReg: the E-step becomes a filter16 MMD-Reg: clouds as distributions17 Representations and implementation choices18 Measure both rotation and translation19 Initialize, refine, then independently verify20 What the ladder teaches21 Continue beyond the slides
3 / 2101 · THE PROBLEMTwo clouds, one rigid motion.Estimate the transform that maps source coordinates into target coordinates.IF THE PAIRS WERE KNOWN\[(\hat R,\hat t)=\arg\min_{R\in SO(d),\;t\in\mathbb R^d}\;\sum_i\lVert Rp_i+t-q_i\rVert^2\]Source → target: \(T(p)=Rp+t\). A proper rotation \(R\in SO(d)\) excludes reflection and scale.The demos use \(SE(2)\): three pose parameters. 3-D rigid registration uses \(SE(3)\): six. A similarity transform additionally estimates scale.THE CATCHThe sum assumes we know which target point belongs to each source point.With unknown pairs, first choose an association or distribution model.Low objective, numerical stopping, and correct pose are three different claims.
4 / 2101 · ROADMAPThe correspondence ladder.Different assumptions about matches lead to different objectives. Complexity is not a strict ladder.1Known correspondences →Kabsch–Umeyama · exact optimum of paired least squares2Corrupted correspondences →RANSAC · minimal fits compete for consensus3Unknown correspondences →ICP · assign nearest, solve, repeat3½Structured residuals →Point-to-plane · GICP · robust kernels4Point-to-cell association →NDT · target geometry as Gaussian cells
5 / 2102 · RUNG ONE · KNOWN CORRESPONDENCESKabsch–Umeyama: the closed form.With fixed pairs, the best rigid fit is a singular value decomposition away.CENTRE, CORRELATE, DECOMPOSE\[H=\sum_i\tilde p_i\tilde q_i^{\mathsf T}=U\Lambda V^{\mathsf T},\qquad \hat R=VCU^{\mathsf T},\qquad \hat t=\bar q-\hat R\bar p\]\(\tilde p_i=p_i-\bar p,\;\tilde q_i=q_i-\bar q\); \(C=\operatorname{diag}\!\big(1,\ldots,1,\det(VU^{\mathsf T})\big)\) prevents a reflection.KEY IDEAFixed paired least squares has a closed-form global optimum over proper rotations and translation. No starting pose is required.The optimum need not equal the true motion under noise or wrong pairs.WHY IT MATTERSTwo distinct 2-D pairs, or three noncollinear 3-D pairs, determine a noise-free rigid pose. Collinear 3-D points leave rotation about their line undetermined.Point-to-point ICP reuses this solve on its current pairs.
6 / 2103 · RUNG TWO · CORRUPTED CORRESPONDENCESRANSAC: consensus over trust.Fit minimal samples, count agreeing pairs, keep the best, refit.HOW MANY SAMPLES?\[N=\left\lceil\frac{\log(1-p)}{\log\!\left(1-w^{s}\right)}\right\rceil\]Confidence \(p\), inlier ratio \(w\), sample size \(s\); independent trials and usable all-inlier samples. \(w^s\) is the usual approximation.KEY IDEAGross outliers can strongly distort least squares, though not every wrong match ruins it. Fit small subsets, score distance-threshold consensus, then refit.Two distinct pairs give a planar hypothesis; three noncollinear pairs are the usual 3-D minimum.TRADE-OFFSNo initial pose is needed, but sampling confidence is not a correctness certificate.Thresholds, degenerate samples, repeated geometry and iteration caps all matter. Next: raise the outlier rate and watch how long consensus takes.
7 / 2103 · RUNG TWO · EXPERIMENTRANSAC: consensus over trust.Raise the outlier rate, then test batches of 36 pair hypotheses. Green points support the best pose so far.
8 / 2104 · RUNG THREE · UNKNOWN CORRESPONDENCESICP: alternate guess and solve.Freeze tentative matches, solve the closed form, rematch at the new pose.TWO SUBPROBLEMS, ALTERNATED\[c_i\leftarrow\arg\min_j\lVert Rp_i+t-q_j\rVert\quad\rightleftarrows\quad(R,t)\leftarrow\arg\min_{R,\,t}\sum_i\lVert Rp_i+t-q_{c_i}\rVert^2\]Assign nearest neighbours, run the rung-one fit on those pairs, repeat.KEY IDEAChicken and egg: the transform reveals the matches; the matches give the transform.ICP takes nearest neighbours as provisional matches, solves the closed form, and repeats. The start pose chooses the basin.TRADE-OFFSWith a fixed source set, exact nearest neighbours and exact paired fitting, the objective never increases and its values converge. That is not a global or correct-pose guarantee.A gated or trimmed RMS can change its contributing set; fixed-count or capped objectives keep descent.
9 / 2104 · RUNG THREE · EXPERIMENTICP: alternate guess and solve.Drag the blue scan to choose a start; Shift-drag rotates. Compare the residual with the true pose error.
10 / 2105 · RUNG THREE½ · STRUCTURED RESIDUALSReshape the cost, not the loop.The alternation stays; the residual, or its weighting, changes.POINT-TO-PLANE\[\sum_i\big(n_{c_i}^{\mathsf T}(Rp_i+t-q_{c_i})\big)^2\]Penalize only the normal component. One plane leaves tangential motion unobservable; varied geometry is needed. The demo takes a local linearized step.Chen & Medioni 1992GENERALIZED ICP\[\sum_i d_i^{\mathsf T}\big(C^{B}_{c_i}+RC^{A}_iR^{\mathsf T}\big)^{-1}d_i\]\(d_i=q_{c_i}-(Rp_i+t)\). Covariances encode local surface orientation, not automatic confidence. The demo freezes the rotation-dependent covariance within each step.Segal et al. 2009ROBUST KERNELS\[\sum_i\rho\big(\lVert r_i\rVert\big)\]Huber has linear, unbounded tails; Tukey has bounded loss and zero weight beyond a cutoff. Neither makes pose estimation globally convex.M-estimators · IRLS
11 / 2106 · RUNG FOUR · POINT-TO-CELL ASSOCIATIONNDT: match against a Gaussian field.Summarize each target cell by a Gaussian, then score every transformed source point.SCORE A POSE AGAINST GAUSSIAN CELLS\[s(\theta)=\sum_i\exp\!\Big(-\tfrac12\,\tilde q_i^{\mathsf T}\Sigma_{c(i)}^{-1}\tilde q_i\Big),\qquad \tilde q_i=T_\theta(p_i)-\mu_{c(i)}\]Unnormalized score, maximized with Newton steps; empty cells contribute zero. \(\theta\) collects the pose parameters.KEY IDEAA Gaussian summarizes the target points in each cell. This removes raw point matching, not association: each transformed point still selects a cell.Covariance regularization prevents singular inverses; one Gaussian can blur mixed surfaces.TRADE-OFFSThe hard-cell objective is piecewise analytic and can jump at cell boundaries. Newton derivatives hold only while cell assignments are unchanged.Shifted grids reduce artifacts without guaranteeing continuity. Coarse-to-fine helps; it is not globally reliable.
12 / 2106 · RUNG FOUR · EXPERIMENTNDT: match against a Gaussian field.Fix the rotation with the slider, then let a direct search climb the score in translation.
13 / 2107 · BEYOND HARD MATCHESWhat should replace correspondences?Commit to one match, average over candidates, or compare whole distributions.HARD · COMMITICP familyReassign nearest neighbours, then fit. Smooth for fixed pairs; assignment switches create kinks. Indexed search is often \(O(M\log N)\); the browser uses brute force.SOFT · AVERAGECPD · FilterRegMixture responsibilities express alternatives. Exact EM never decreases a fixed model’s likelihood; schedules and approximate steps need separate care. Gaussian filtering can accelerate the sums.DISTRIBUTIONS · COMPAREGMMReg · MMD-RegCompare mixture densities or kernel mean embeddings without discrete pair assignments. NDT differs: it selects grid cells and need not be globally smooth.As \(\sigma\to0\), the nearest component dominates for an inlier; with positive clutter weight, clutter may instead take all the mass.
14 / 2107 · SOFT CORRESPONDENCES · ICPD: registration as mixture fitting.Gaussians ride on the transformed source points; target points are the observations.E-STEP: RESPONSIBILITIES WITH A CLUTTER TERM\[P(m\mid x_n)=\frac{g_{mn}}{\sum_{k=1}^{M}g_{kn}+c},\qquad g_{mn}=\exp\!\Big(-\frac{\lVert x_n-T(y_m)\rVert^2}{2\sigma^2}\Big)\]\(c=(2\pi\sigma^2)^{d/2}\,\tfrac{w}{1-w}\,\tfrac{M}{V}\) for clutter density \(1/V\) (the paper’s \(1/N\) gives \(M/N\)). CPD letters: \(y_m\) source, \(x_n\) target.KEY IDEAThe E-step normalizes each observation’s responsibilities, clutter included. The M-step is a weighted Procrustes fit.The paper’s “rigid” CPD already estimates a scale, \(T(y)=sRy+t\); fix \(s=1\) for strictly rigid motion.WHAT STANDS OUTThe variance has a closed-form update but need not shrink every step; this is not deterministic annealing.A naive E-step costs \(O(MN)\). Blocked sufficient sums avoid storing the full matrix; fast Gauss transforms accelerate it.
15 / 2107 · SOFT CORRESPONDENCES · IIFilterReg: the E-step becomes a filter.Reverse the mixture: Gaussians sit on the fixed cloud, and the moving points query it.FILTERED MOMENTS FOR EACH MOVING POINT\[M^0_i=\sum_j\mathcal N\big(Tp_i;\,q_j,\sigma^2 I\big),\qquad M^1_i=\sum_j\mathcal N\big(Tp_i;\,q_j,\sigma^2 I\big)\,q_j\]Soft target \(M^1_i/M^0_i\); confidence from \(M^0_i\) against an outlier constant. The M-step is a local, twist-based Gauss–Newton step.\(\sigma^2\)may be optimized analytically (Section 3.3)KEY IDEABecause the fixed cloud carries the mixture, the filter index can be built once and reused while the bandwidth stays fixed.FilterReg uses a customized permutohedral lattice and can add features or point-to-plane residuals.THE TRADEThe variance update is not lost: Section 3.3 permits analytic optimization, at the cost of rebuilding the filter when the bandwidth changes.Filtering is approximate; exact-EM monotonicity does not automatically transfer to a filtered, linearized step.
16 / 2108 · CORRESPONDENCE-FREEMMD-Reg: clouds as distributions.Compare feature means of the two clouds: no E-step, no discrete pairs.KERNEL MEAN EMBEDDINGS WITH RANDOM FEATURES\[\mathrm{MMD}^2(P,Q)=\lVert\mu_P-\mu_Q\rVert_{\mathcal H}^2\;\approx\;F(\theta)=\Big\lVert\frac1M\sum_i z(T_\theta p_i)-\frac1N\sum_j z(q_j)\Big\rVert^2\]\(k(x,y)\approx z(x)^{\mathsf T}z(y)\) with \(D\) Gaussian frequencies, i.e. \(2D\) sine/cosine features; linear cost in the number of points for fixed \(D\).KEY IDEARegistration becomes nonlinear least squares on a \(2D\)-dimensional residual.Finite random features approximate a characteristic kernel; the finite embedding need not identify a distribution uniquely.WHAT IT BUYS · WHAT IT COSTSSmooth but nonconvex. Differentiating the selected optimum by the implicit function theorem needs an isolated solution with a nonsingular pose Hessian.Partial overlap, density imbalance and outliers can shift the optimum; learned weights may mitigate, not remove, these effects.
17 / 2109 · COMPARISONRepresentations and implementation choices.Costs describe computational routes, not universal lower bounds.
18 / 2109 · EVALUATIONMeasure both rotation and translation.Planar teaching scenes, arbitrary world units, configurable noise, outliers, rotation and offset. No universal ranking.RUN ITUse the companion article’s Benchmark 25 seeds button.Seeds \(40+13k,\ k=0,\ldots,24\); 70 steps per solver. Same clouds and local starts; RANSAC ignores initialization.REPORT BOTH ERRORSRotation error (RRE) and translation error (RTE).Joint success: \(\mathrm{RRE}<5^\circ\) and \(\mathrm{RTE}<0.2\) world units.CHANGE ONE THINGVary noise, outliers and starting pose one at a time, so each failure has a single cause.WHAT IT IS NOTThese toy solvers are not official paper implementations. A low objective is not ground truth, a small pose step is not success, and an iteration count is not runtime.
19 / 2110 · IN PRACTICEInitialize, refine, then independently verify.Global proposal, local refinement and verification are separate jobs.1 · PROPOSE AN INITIAL POSEFeatures + RANSAC, a learned model, or an odometry motion prediction. No proposal is automatically basin-safe.▶2 · REFINE, THEN VERIFYICP, GICP or NDT refine locally. Then check overlap, geometry, motion consistency and independent support.A DIFFERENT ROUTE · LEARNED FLOWRAP treats registration as conditional generation: a learned point-wise velocity field transports points to a registered scene, with rigidity enforced at test time and a rigid pose read out. It needs no initial pose, but that is not a global correctness guarantee.The companion article’s small planar MLP is an analogy, not RAP or its evaluation.VerifyINITIALIZATION-FREE ≠ FAILURE-FREE
20 / 2110 · TAKEAWAYSWhat the ladder teaches.Four distinctions to keep when reading any registration paper.1 · SEPARATE MODEL FROM OPTIMIZERFixed pairs, soft associations, point-to-cell scores and distribution distances encode different assumptions. Newton, EM and LM solve different subproblems.2 · KNOBS ARE NOT INTERCHANGEABLEGates select pairs; cell size changes geometry; \(\sigma\) and \(\ell\) change interactions. Coarse-to-fine can help, but these controls do different things.3 · SMOOTH OBJECTIVE ≠ DIFFERENTIABLE SOLUTIONNearest-neighbour costs have kinks; hard-grid NDT can jump. Smooth MMD still needs a nonsingular Hessian for a local solution derivative.4 · STOPPING IS NOT SUCCESSValidate rotation and translation in simulation. On real data, check overlap, conditioning, motion consistency and independent evidence.1976 KABSCH · 1981 RANSAC · 1987 ARUN · 1992 ICP & POINT-TO-PLANE · 2003 NDT · 2009 GICP · 2010 CPD · 2019 FILTERREG · 2025 RAP · 2026 MMD-REG
21 / 21FRAME REGISTRATION / EXTENSIONSContinue beyond the slidesExtended explanations, worked examples, and supporting material.Extended notes & interactive examples →Explore the objectives, assumptions, worked examples, and registration experiments in more detail.← All topicsFrame Registration · Bai Liping{{page}} / {{pages}}
