Rigid and Articulated Point Registration with Expectation Conditional Maximization

Radu Horaud; Florence Forbes; Manuel Yguel; Guillaume Dewaele; Jian Zhang

Source-linked AI summary

Rigid and Articulated Point Registration with Expectation Conditional Maximization

Radu Horaud, Florence Forbes, Manuel Yguel, Guillaume Dewaele, Jian Zhang

arXiv:2012.05191v1Dec 9, 2020cs.CV

TL;DR

The paper tackles rigid and articulated shape matching when point correspondences are unknown and data may contain noise or outliers. It formulates registration probabilistically and introduces ECMPR with general covariance models, SDP-based rigid parameter estimation, articulated extension, and a uniform outlier component. The reported analyses and experiments show robust behavior, with anisotropic covariances outperforming isotropic ones and ECMPR generally outperforming ICP.

Problem
Rigid and articulated shape matching requires estimating registrations with unknown correspondences, while existing articulated approaches may only weakly satisfy kinematic constraints and inverse-kinematic optimization requires proper initialization.
Method
ECMPR models transformed model points as Gaussian-mixture centers, uses conditional maximization with general anisotropic covariances, estimates rigid parameters through SDP relaxation, and incrementally extends registration to articulated shapes.
Results
ECMPR-rigid behaves robustly under anisotropic Gaussian noise and outliers, anisotropic covariances outperform isotropic covariances, and ECMPR generally performs better than ICP.
Takeaways & Limitations
The approach provides robust rigid registration and supports articulated registration while enforcing kinematic constraints exactly through incremental rigid alignment.

Abstract

from arXiv · show

This paper addresses the issue of matching rigid and articulated shapes through probabilistic point registration. The problem is recast into a missing data framework where unknown correspondences are handled via mixture models. Adopting a maximum likelihood principle, we introduce an innovative EM-like algorithm, namely the Expectation Conditional Maximization for Point Registration (ECMPR) algorithm. The algorithm allows the use of general covariance matrices for the mixture model components and improves over the isotropic covariance case. We analyse in detail the associated consequences in terms of estimation of the registration parameters, and we propose an optimal method for estimating the rotational and translational parameters based on semi-definite positive relaxation. We extend rigid registration to articulated registration. Robustness is ensured by detecting and rejecting outliers through the addition of a uniform component to the Gaussian mixture model at hand. We provide an in-depth analysis of our method and we compare it both theoretically and experimentally with other robust methods for point registration.

I. INTRODUCTION, RELATED WORK, AND CONTRIBUTIONS

The paper formulates point registration as probabilistic maximum-likelihood estimation with missing correspondences, then develops ECMPR for rigid and articulated alignment, anisotropic covariances, and outlier rejection.

Problem and related work: Point registration jointly estimates point correspondences and the transformation aligning two point sets.Existing approaches include ICP, soft assignment, and probabilistic methods.
Problem and related work: Gaussian-mixture registration recasts point-to-point assignments as missing data estimated with EM, but prior EM-like methods may not achieve true maximum likelihood.Some formulations do not estimate covariances or approximate the nonlinear M-step.
ECMPR: ECMPR replaces EM’s coupled M-step with conditional maximization steps suited to jointly estimating registration parameters and covariances.The method is formally based on the expected complete-data log-likelihood.
Anisotropic covariance model: For anisotropic covariances, the paper transforms rigid alignment into constrained quadratic optimization and solves it using semi-definite positive relaxation.This makes the otherwise non-closed-form optimization tractable.
Articulated registration: The articulated method incrementally applies rigid alignment along constrained kinematic chains, enforcing joint constraints exactly rather than a posteriori.The method is illustrated on a hand model with 16 parts, 5 kinematic chains, and 27 degrees of freedom.
Robustness: A uniform mixture component provides built-in outlier handling without adding free parameters to the maximization step or changing ECM’s general convergence structure.The approach differs from robust losses and trimmed-subset methods used with ICP.

II. PROBLEM FORMULATION

The paper formulates point registration as maximum-likelihood estimation in a Gaussian mixture with transformation-constrained means and hidden point correspondences. Because registration parameters and covariances are coupled, it replaces standard EM with conditional minimization steps in ECM.

A. Mathematical notations: The paper represents observed and model data as two sets of 3-D points, with model points transformed by rigid or articulated parameters Θ.Rigid registration uses a 3×3 rotation matrix R and a 3×1 translation vector t.
A. Mathematical notations: The registration parameters are Θ, while an asterisk denotes an optimal parameter value, ⊤ denotes transpose, and Mahalanobis distance uses a symmetric positive definite covariance matrix.The squared Mahalanobis distance is (X−Y)⊤Σ^-1(X−Y).
B. Point registration, maximum likelihood, and EM: Point registration fits a Gaussian mixture to observations Y while constraining each Gaussian mean to a transformed model point µ(Xi; Θ).Each component has mean µi and covariance Σi; unlike standard mixtures, the means are controlled by registration parameters.
B. Point registration, maximum likelihood, and EM: The observed-data log-likelihood depends jointly on Θ and the covariance matrices Σ1,…,Σn.The constrained means encode prior knowledge about the transformation between the point sets.
B. Point registration, maximum likelihood, and EM: Unknown assignments of observations to model points or an outlier class are treated as hidden variables, making direct likelihood maximization intractable.The complete data consist of observed points Y and hidden assignments Z.
B. Point registration, maximum likelihood, and EM: Standard EM alternates expectations and maximization for incomplete-data maximum likelihood and converges to a local maximum of the expected complete-data log-likelihood.Maximizing that expected criterion also maximizes the observed-data log-likelihood.
C. The proposed method: For point registration, ECM replaces EM by conditionally maximizing over registration parameters and then covariance matrices.The algorithm initializes parameters, computes posterior probabilities in an E-step, performs two CM-steps, and checks convergence.
C. The proposed method: The ECM procedure repeats initialization, posterior computation, conditional parameter updates, and convergence checking.The registration update conditions on current covariances, while the covariance update conditions on newly estimated registration parameters.

III. POINT REGISTRATION AND GAUSSIAN MIXTURES

The paper formulates point registration as maximum-likelihood estimation with hidden correspondences in a Gaussian mixture model. ECMPR alternates conditional maximization steps while modeling anisotropic covariances and rejecting outliers through a uniform component.

Probabilistic model: Unknown point correspondences are treated as hidden variables, with each observation assigned to a Gaussian component centered at a transformed model point or to a uniform outlier class.The mixture uses Gaussian likelihoods for inlier assignments and a uniform distribution over the 3-D working volume for outliers.
Outlier modeling: The model specializes mixture priors for point registration and includes an explicit outlier prior and posterior probability within the Gaussian-uniform mixture.The outlier component is parameterized using the working-space volume and the local volume around model points.
ECMPR formulation: ECMPR replaces the standard EM M-step with conditional maximization steps because registration means are constrained by transformation parameters and coupled to covariance estimation.The constrained means involve rotation matrices, making simultaneous optimization of all model parameters difficult.
Covariance handling: The anisotropic formulation can encounter covariance singularities when a Gaussian component collapses onto a data point, so the method regularizes covariances by adding εI.The perturbation slightly enlarges each covariance while preserving the associated ellipsoid’s eccentricity and orientation.
Posterior updates: Posterior-weighted virtual observations convert the many-to-one assignment model into a one-to-one structure between each virtual observation and its corresponding model point.Each virtual observation is formed from a normalized posterior-weighted sum of observed points, facilitating subsequent rigid and articulated registration optimization.

V. RIGID POINT REGISTRATION

For rigid objects, the registration objective is optimized over translation and rotation under the rotation matrix’s orthonormality and determinant constraints. Translation is obtained directly, leaving a constrained rotation minimization.

Rigid objective: Rigid registration assumes model points lie on a single rigid object, so the general point-registration criterion specializes to a rigid transformation.The rigid-object assumption is inserted into the previously derived objective.
Translation estimation: The translation parameters are estimated by differentiating the objective with respect to the 3-D translation vector and setting the derivatives to zero.Substituting the resulting translation into the objective produces a criterion depending on the rotation parameters.
Rotation estimation: Rotation estimation minimizes the resulting criterion subject to RR^⊤ = I and |R| = +1.These constraints enforce an orthonormal, proper rotation matrix.

A. Isotropic covariance model

With isotropic covariance matrices, the rigid-registration objective simplifies because Mahalanobis distance becomes Euclidean distance. This is the conventional setting for most existing registration methods and permits closed-form rotation estimation.

Isotropic model: Isotropic covariance sets each component covariance to Σ_i = σ_i^2 I_3.Under this assumption, the covariance has the same variance in all spatial directions for each component.
Objective simplification: The isotropic criterion is simpler because the Mahalanobis distance reduces to Euclidean distance.This removes directional weighting from the rigid-registration objective.
Relation to prior methods: Most existing point-registration methods use isotropic covariance, whose rotation minimizer can be estimated in closed form.The cited closed-form approaches apply to the simplified isotropic objective.

B. Anisotropic covariance model

The anisotropic-covariance formulation converts rigid registration into a constrained quadratic optimization problem and uses SDP relaxation to estimate rotation within ECMPR-rigid.

B. Anisotropic covariance model: The general-covariance formulation represents rotation as r = vec(R) and introduces the rank-one positive symmetric matrix ρ = rr⊤.These variables encode the rotation and its lifted quadratic representation.
B. Anisotropic covariance model: Expanding the registration criterion yields a quadratic minimization in r subject to orthogonality constraints r⊤∆_klr = δ_kl.The matrices ∆_kl encode the constraints implied by RR⊤ = I.
B. Anisotropic covariance model: SDP relaxation replaces the nonconvex rank-one condition with semidefinite positivity, producing a convex optimization problem.The lifted quadratic form is expressed using the matrix dot-product ⟨A, ρ⟩.
B. Anisotropic covariance model: The relaxed solution provides an initial rotation estimate for a standard nonlinear optimizer in the anisotropic-covariance case.ECMPR-rigid then estimates translation and covariances using current posteriors and the updated transformation parameters.
B. Anisotropic covariance model: ECMPR-rigid iterates posterior evaluation, parameter updates, covariance estimation, convergence testing, and MAP classification of inliers and outliers.Initialization uses the identity rotation and zero translation.

3) CM-steps:

The articulated formulation models motion as a chain of constrained rigid transformations and estimates its parts incrementally, while the rigid procedure handles assignments and parameter updates.

3) CM-steps:: The rigid CM-step estimates rotation using SDP relaxation, translation from the updated rotation, and covariances from current posteriors and transformation parameters.Convergence is checked by comparing successive rotations before MAP classification.
A. The kinematic model: An open articulated chain contains rigid parts linked by constrained motions, while the root part may undergo six-degree-of-freedom free motion.The links may have one, two, or three rotational degrees of freedom.
A. The kinematic model: Articulated registration is difficult because each part’s motion depends on kinematic parameters and the root-part motion, creating a nonlinear inverse-kinematic problem.Such problems are generally solved iteratively and require proper initialization.
3) CM-steps:: The root registration example converged after 25 iterations, followed by 13, 13, and 4 iterations for the remaining three rigid parts.The figure shows successive registration of the root and then the unmatched data for each additional part.
A. The kinematic model: The ECMPR-articulated algorithm estimates free and kinematic parameters incrementally by applying ECMPR-rigid to one rigid part at a time.This avoids simultaneous estimation of all kinematic parameters from part associations.

B. The pose of an articulated shape

For articulated registration, virtual observations and posterior weights reduce each part’s conditional update to a rigid-registration problem along the kinematic chain.

B. The pose of an articulated shape: Each model part has associated model points, while virtual observations and weights are computed from current posterior probabilities.These quantities supply the weighted observations used by the rigid-registration criterion.
B. The pose of an articulated shape: The same criterion registers the root part freely and registers each subsequent part conditioned on the preceding articulated pose.The conditional structure follows the chain of rigid transformations.
B. The pose of an articulated shape: After substitutions, minimizing the part-specific objective yields the parameters of Q_p when the preceding transformation T_{p−1} is known.This minimization is equivalent to minimizing the original rigid-registration criterion.
B. The pose of an articulated shape: The articulated algorithm first registers the root with all data, classifies inliers and outliers, removes root inliers, and then registers each remaining part sequentially.Thus, observations are partitioned through the registration process rather than requiring an observation partition beforehand.

VII. EXPERIMENTAL RESULTS

Experiments evaluate ECMPR-rigid and ECMPR-articulated under varied initialization, noise, outlier, and covariance conditions, including stereo registration and hand tracking.

VII. EXPERIMENTAL RESULTS: The experiments assess initialization, Gaussian noise, outliers, and anisotropic versus isotropic covariances, using simulated and real data.ECMPR-rigid is compared with TriICP and ICP, while ECMPR-articulated is tested on articulated and hand-tracking data.
A. Experiments with ECMPR-rigid: The simulated rigid experiments use 15 model points, 25 observations, 15 inliers, and 10 uniformly distributed outliers.Inliers are transformed from model points and corrupted by noise.
A. Experiments with ECMPR-rigid: ECMPR-rigid is initialized with identity rotation, zero translation, and large variances, whereas TriICP uses random sampling to address ICP’s initialization sensitivity.The paper notes that ICP can converge quickly yet become trapped in a local minimum.
A. Experiments with ECMPR-rigid: 1,000 trials per rotation angle measure correct matches and relative rotation and translation errors under anisotropic noise and outliers.Figure 4 reports means and standard deviations as the ground-truth rotation varies from 0° to 180°.
A. Experiments with ECMPR-rigid: ECMPR-rigid behaves robustly with high-amplitude anisotropic noise and outliers, and anisotropic covariances outperform isotropic covariances in parameter estimation and correct assignments.Reported rotation and translation errors are consistent with the noise level.
A. Experiments with ECMPR-rigid: On stereo data, both ECMPR-rigid and ICP correctly estimate the rotation, with translation and minimization errors summarized in Table II.The reconstructed sets contain 223 model points and 249 data points from two walking-person stereo pairs.
B. Experiments with ECMPR-articulated: The hand model contains five kinematic chains, 16 rigid parts, and 27 degrees of freedom, and ECMPR-articulated is tested with simulated and real data.The model includes a shared palm root and phalangeal parts.
B. Experiments with ECMPR-articulated: Joint-limit constraints are not implemented in the reported hand-tracking experiments, although the convex framework can incorporate them without affecting convexity.Consequently, the demonstrated solutions correspond exactly to the unconstrained formulation.

CORRECT ROTATION. ICP FAILED TO ESTIMATE THE CORRECT

The simulated and real-data experiments evaluate ECMPR for articulated hand registration, showing strong performance with outliers while also exposing sensitivity to covariance initialization.

Simulated experiments: Improper covariance initialization caused ECMPR to fail to estimate all kinematic parameters correctly in one simulated sequence.The corresponding angle trajectories showed both good and bad estimates depending on covariance initialization.
Simulated experiments: The simulated experiments produced very good results, and varying outlier percentages barely affected registration.They also confirmed the importance of anisotropic covariance modeling and covariance initialization.
Real-data experiments: Real stereo sequences contained 500 to 1000 reconstructed points per frame and substantial anisotropic depth noise.The experiments covered grasping motions and rotation around an axis roughly parallel to the image plane.
Real-data experiments: 250 inliers per frame were selected on average, approximately matching the 240 model points, while remaining observations were assigned to the outlier class.The rejection mechanism did not require advance knowledge of the outlier percentage.
Tracking conditions: Articulated tracking must bootstrap assignments when occlusion makes previously registered model points disappear and new ones appear.Re-initializing the covariance matrix at every time step was crucial to successful tracking.

VIII. CONCLUSIONS

The paper formulates rigid and articulated point registration probabilistically and develops ECMPR with anisotropic covariances, robust outlier handling, and articulated extensions. It reports better overall performance than ICP while identifying computational efficiency as future work.

Probabilistic formulation: The paper casts point registration as maximum likelihood estimation with hidden correspondences and derives an ECM variant maximizing expected complete-data log-likelihood.Replacing each M-step with conditional maximization steps preserves maximization of the observed-data likelihood.
ECMPR model: ECMPR fits model points as Gaussian-mixture component centers and permits each component to have its own anisotropic covariance.The asymmetric treatment of data and model points supports varying observation counts and robust parameter estimation.
Robustness: A uniform mixture component provides built-in outlier rejection for noisy data without requiring the outlier proportion in advance.This differs from approaches based on nonlinear losses or random sampling.
Optimization: Semi-definite positive relaxation converts the nonconvex anisotropic rotation problem into a constrained quadratic optimization problem for practical solution.The general covariance model prevents use of the closed-form rotation solution available in the isotropic case.
Articulated registration: The rigid algorithm is applied incrementally to articulated registration through a kinematic representation suited to point registration.The construction iteratively handles the rigid parts of the articulated chain.
Conclusions: ECMPR generally performs better than ICP, with lower sensitivity to initialization and greater robustness to outliers.The authors identify more efficient E-step implementations, including CEM and KD-trees, as future work.

APPENDIX EXPANSION OF A AND b IN EQ. (32)

The appendix expands the matrix A and vector b used in the optimization formulation and recalls the Kronecker-product and vectorization operations needed for that expansion.

Expansion of A and b: Expanding equation (28), substituting the optimal translation from equation (27), and rearranging terms yields the 9×9 matrix A and 9×1 vector b.These expressions support the optimization formulation referenced in the appendix.
Kronecker product: The appendix defines the Kronecker product for an m × n matrix or vector A and a p × q matrix or vector B as an mp × nq matrix or vector.Its block entries are formed by multiplying each element of A by the full matrix B.
Vectorization: The vectorization operation vec(A) returns an mn × 1 vector.The appendix introduces this operation alongside the Kronecker-product definition.