PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Alignment of Multiple Point Sets with Batch and Incremental Expectation-Maximization

Georgios Evangelidis, Radu Horaud

arXiv:1609.01466v2cs.CV

TL;DR

The paper addresses biased and error-prone pairwise approximations for registering multiple noisy, outlier-contaminated point sets. It jointly models all points with a central Gaussian mixture and derives batch and incremental EM algorithms for alignment. The method is reported as more robust to outliers than several pairwise methods and is validated on simulated and depth-sensor data, with potential for surface reconstruction and depth-data fusion.

  • Problem

    Multiple-set registration is often approximated by pairwise methods that privilege a model set, allowing noise and outliers to bias alignment.

  • Method

    The method treats all points as samples from one Gaussian mixture and uses batch or incremental EM to estimate mixture parameters and rigid transformations jointly.

  • Results

    The proposed method is more robust to outliers than ICP, SimReg, CPD, and GMMReg in the reported experiments, with successful registration under densely present outliers.

  • Takeaways & Limitations

    The mixture means provide a registered scene model, supporting surface reconstruction and effective fusion of depth data.

Abstract

from arXiv · show

This paper addresses the problem of registering multiple point sets. Solutions to this problem are often approximated by repeatedly solving for pairwise registration, which results in an uneven treatment of the sets forming a pair: a model set and a data set. The main drawback of this strategy is that the model set may contain noise and outliers, which negatively affects the estimation of the registration parameters. In contrast, the proposed formulation treats all the point sets on an equal footing. Indeed, all the points are drawn from a central Gaussian mixture, hence the registration is cast into a clustering problem. We formally derive batch and incremental EM algorithms that robustly estimate both the GMM parameters and the rotations and translations that optimally align the sets. Moreover, the mixture's means play the role of the registered set of points while the variances provide rich information about the contribution of each component to the alignment. We thoroughly test the proposed algorithms on simulated data and on challenging real data collected with range sensors. We compare them with several state-of-the-art algorithms, and we show their potential for surface reconstruction from depth data.

I. INTRODUCTION

Multiple point-set registration is often approximated through pairwise alignment, but sequential and reference-based strategies accumulate drift, bias results, and lack closed-loop information. The paper instead jointly models all sets with one Gaussian mixture and derives batch and incremental EM algorithms that accommodate noise, outliers, and unequal set sizes.

  • Motivation: Pairwise approximations suffer from drift accumulation, reference-set bias, and missing closed-loop constraints.Sequential methods accumulate chain-based error, while one-versus-all methods are governed by a single reference set.
  • Proposed approach: The proposed generative approach jointly registers all sets by treating their points as samples from one Gaussian mixture and solving a clustering problem with EM.Both mixture parameters and set-specific transformations are estimated through maximum likelihood.
  • Contributions: Batch and incremental EM variants support point sets with different cardinalities and contamination by noise and outliers.The incremental method is more efficient for adding sets but can be less accurate than batch EM.
  • Proposed approach: The formulation treats all point sets equally rather than tying mixture means to one noisy or outlier-contaminated model set.The free mixture means also serve as a reconstructed scene model.
  • Evaluation: The paper evaluates the approach against recent methods on novel datasets and benchmarks, including depth-camera data and potential depth-data fusion.The article also expands discussion of initialization, behavior, complexity, and method advantages.

III. PROBLEM FORMULATION

The problem is to estimate rigid transformations for multiple point sets assumed to arise from a shared Gaussian mixture. The formulation uses EM to jointly estimate transformations and mixture parameters while incorporating an outlier component and isotropic-covariance restrictions for closed-form updates.

  • III. PROBLEM FORMULATION: Each point set V_j contains N_j three-dimensional points, and rigid transformations map all sets into a common model-centered coordinate frame.The transformation is φ_j(v_ji)=R_jv_ji+t_j, with rotation R_j and translation t_j.
  • III. PROBLEM FORMULATION: The objective estimates M data-set-to-model transformations under the assumption that all observations are generated by the same mixture model.The mixture includes component means, covariance matrices, mixing coefficients, and a uniform distribution for outliers.
  • III. PROBLEM FORMULATION: The parameter γ controls the outlier-to-inlier proportion through the uniform component.Its choice balances the expected proportions of outliers and inliers.
  • III. PROBLEM FORMULATION: EM introduces hidden assignments Z_ji indicating which mixture component generated each observation and maximizes the expected complete-data log-likelihood.The E-step computes posterior assignments, while subsequent updates optimize the model parameters.
  • IV. BATCH REGISTRATION: Isotropic covariances Σ_k=σ_kI_3 are imposed because they yield closed-form maximization updates for all model parameters.The paper states that non-isotropic covariances require more complex convex optimization without significant accuracy gains.
  • IV. BATCH REGISTRATION: Rotation estimation is constrained by orthonormality and unit determinant conditions for every set.These constraints ensure each R_j is a valid rotation matrix.
  • IV. BATCH REGISTRATION: The batch algorithm augments standard Gaussian-mixture M-steps with estimation of each set’s rigid transformation parameters.JRMPC-B alternates transformation estimation and mixture-parameter estimation in a conditional-maximization procedure without requiring prior rough transformations.

A. E-step

The E-step computes posterior probabilities that each transformed observation belongs to each Gaussian component, while the uniform component captures outlier probability. These responsibilities are evaluated using the previous iteration’s parameters.

  • A. E-step: The E-step assigns each point a posterior probability of belonging to mixture component k.The posterior represents the probability that the observation is associated with a component, such as an inlier cluster.
  • A. E-step: The uniform-mixture term γ/[h(γ+1)] accounts for the outlier component in the posterior calculation.This term incorporates the uniform distribution into component-assignment probabilities.
  • A. E-step: The outlier posterior is the residual probability after summing the K Gaussian-component posteriors.It is given by α_ji,K+1=1−Σ_k α_jik.
  • A. E-step: At iteration q, responsibilities are computed from the posterior expression using the parameter set Θ^(q−1).This is the E-step’s dependence on the preceding EM iterate.

B. M-rigid-step

The M-rigid-step estimates each set’s rotation and translation independently by aligning the GMM means with weighted virtual points derived from that set.

  • B. M-rigid-step: The rigid transformation parameters are estimated independently for each point set while maximizing the objective with current GMM parameters.The resulting constrained minimization has a closed-form weighted solution.
  • B. M-rigid-step: Each point set is represented by K weighted virtual points, one per mixture component, and aligned to the GMM means.The virtual points are weighted averages of points assigned to each component.
  • B. M-rigid-step: The method supports point sets with different cardinalities because K is chosen independently of each set’s number of points.This differs from pairwise methods that assume similar cardinalities.

C. M-GMM-step

The M-GMM-step updates the mixture parameters after rigid transformations are estimated, using standard optimization for means and covariances and constrained optimization for priors.

  • C. M-GMM-step: Given rigid transformations and posterior probabilities, standard optimization computes the optimal mixture means and covariances.
  • C. M-GMM-step: A small scalar ϵ is introduced to avoid singularities when estimating the mixture parameters.
  • C. M-GMM-step: The mixture priors are optimized with a Lagrange multiplier enforcing their normalization constraint.The resulting optimization yields the prior update.
  • C. M-GMM-step: When the uniform-component weight γ approaches zero, the corresponding η approaches N, matching the stated special case.

D. Algorithm Analysis

The batch algorithm has linear complexity in the total number of points for fixed mixture size, whereas exhaustive pairwise registration is substantially more expensive; joint registration also treats sets symmetrically.

  • D. Algorithm Analysis: O(¯NMK) is the batch algorithm’s typical complexity, with K the mixture size and ¯N the average point-set cardinality.The leading complexity is O(NK), and K may be below, near, or above ¯N depending on the data.
  • D. Algorithm Analysis: O(¯N^2M^2) operations are required in principle when pairwise registration evaluates all point-to-point distances across set pairs.Data structuring can reduce this cost.
  • D. Algorithm Analysis: Joint registration places all point sets on an equal footing by casting alignment as clustering rather than assigning one set as model and another as data.
  • D. Algorithm Analysis: In pairwise probabilistic registration, noisy points or outliers in the model-dependent set can propagate into poor mixture means.The joint formulation instead uses free mixture parameters rather than means tied directly to rigid parameters.
  • D. Algorithm Analysis: The batch method requires at least two sets with three overlapping points and scales linearly with the number of sets when K is fixed.This motivates an incremental version for large collections.

V. INCREMENTAL REGISTRATION

JRMPC-I aligns each newly added set to the mixture learned from previously registered sets, updating mixture parameters without revising earlier transformations. It reduces computational cost but depends on initialization and does not grow the mixture model.

  • V. INCREMENTAL REGISTRATION: JRMPC-I aligns a new point set with previously registered sets while retaining their transformations and initializing from existing mixture parameters.The new set’s rotation and translation require separate initialization.
  • V. INCREMENTAL REGISTRATION: Initialization with the previous transformation is a stated option for smoothly moving RGB-D sequences, while more general cases use the paper’s broader initialization strategy.
  • V. INCREMENTAL REGISTRATION: The incremental M-rigid-step computes the new set’s rotation and translation in closed form against GMM means learned from earlier sets.
  • V. INCREMENTAL REGISTRATION: The incremental M-GMM-step updates mixture means, covariances, and priors after integrating the new set.
  • V. INCREMENTAL REGISTRATION: JRMPC-I’s convergence depends on initialization, does not increase the number of mixture components as nonoverlapping sets arrive, and is intended for efficiency.For many sets, the paper recommends a temporally hierarchical scheme to address memory requirements.

VI. INITIALIZATION

Initialization uses overlap-aware pose estimates and empirical mixture settings, with high initial variances helping EM converge quickly. The component count is chosen from set cardinality, overlap, and data density.

  • VI. INITIALIZATION: Initialization assumes sufficient joint overlap, using centroid or median differences for translations and identity or rough pairwise alignment for rotations.Centroid differences are preferred when overlap is sufficient; median differences handle strong artifacts, while pairwise registration helps when many pairs do not overlap.
  • VI. INITIALIZATION: High initial variances produce very good results and quickly converge to final values, while mixture means can start from one point set or a surrounding sphere.Rough pre-alignment can also initialize means by resampling the registered set and variances so each cluster covers enough points.
  • VI. INITIALIZATION: K = N̄ is suggested for similarly sized sets, with smaller K for highly overlapping sets and larger K for many non-overlapping sets.The number of components depends on the data and application rather than a fixed rule.
  • VI. INITIALIZATION: K ≪ N̄ yields excellent alignment with dense depth-sensor data.

VII. EXPERIMENTS

Experiments benchmark the proposed registration against pairwise and joint methods on synthetic 3D models and range-sensor data. The method is robust to outliers, offers strong indirect-registration accuracy, and supports outlier-free model reconstruction.

  • VII. EXPERIMENTS: Experiments cover public Stanford 3D models plus time-of-flight and structured-light Kinect data, including tests against pairwise and recent joint-registration methods.
  • 1) Comparison with pairwise registration algorithms:: The benchmark compares JRMPC with ICP, CPD, ECMPR, GMMReg, seqICP, and SimReg using RMSE of rotation parameters averaged over the sets.Baselines use one-versus-all registrations except SimReg, which considers overlapping pairs; GMMReg and SimReg receive favorable initialization conditions.
  • 1) Comparison with pairwise registration algorithms:: The proposed method is more robust to outliers than the baselines, succeeding even when outliers are densely present across Lucy, Bunny, and Armadillo.Fig. 2 reports final log-RMSE over 100 realizations and all views, while convergence curves use SNR = 10dB and 20% outliers.
  • 1) Comparison with pairwise registration algorithms:: The proposed scheme provides the lowest error and the most symmetric solution for indirect mappings between point sets.Table I reports rotation errors for V2 → V3 and V3 → V4 together with their standard deviation under SNR = 10db and 30% outliers.
  • 1) Comparison with pairwise registration algorithms:: Across rotation angles from −90o to 90o, the method achieves the widest and shallowest acceptable-error basin for Lucy and competes with GMMReg for Armadillo.The comparison uses average RMSE over 50 realizations with SNR = 20dB and 30% outliers.
  • 1) Comparison with pairwise registration algorithms:: The method reconstructs an outlier-free model while its estimated variances identify the majority of outlying points.Fig. 4 follows GMM-mean estimates over 5, 15, and 30 iterations and shows registration before and after removing bad points.

2) Comparison with joint registration algorithms:

On simulated multi-view data, the proposed joint-registration methods are compared with motion-averaging and fixed-match baselines under clean and noisy conditions. JRMPC-B is most accurate overall, while JRMPC-I remains sufficiently accurate and robust to noise.

  • Experimental setup: The simulated benchmark uses Bunny, Dragon, and Happy Buddha scans with known transformations, variable cardinalities, and rough pairwise-ICP pre-alignment.The evaluation also adds Gaussian noise but deliberately excludes outliers because initialization errors would make motion averaging fail.
  • Clean-data registration: The proposed algorithm and MATrICP achieve the most accurate clean-data registration, while JRMPC-I provides sufficient quality; JRMPC and MATrICP also yield very good reconstructions.MV-ICP fails because it uses fixed matches, and MAICP is less accurate.
  • Incremental behavior: JRMPC-I produces comparable reconstructions and successfully closes the loop, but its mixture components remain biased toward the initial sets.This bias may become problematic for long sequences.
  • Noisy-data registration: Under 25 dB Gaussian noise, even JRMPC-I outperforms motion-averaging methods because its GMM means are cleaned over time and its registration is more noise-robust.The noisy comparison is reported in Table III; noisy integrated-model illustrations are not meaningful.
  • Initialization and variance: Fixing the variance during initial JRMPC-B iterations yields better-distributed means and more accurate transformations when the sets are roughly aligned.The authors attribute this to the object skeleton carrying more informative points than the surface.

B. Real Data

On real depth data, JRMPC registers and fuses point clouds from TOF and Kinect sequences, including large numbers of sets from moving sensors. It produces accurate reconstructions and supports a hierarchical incremental scheme, while differing from SLAM in trajectory smoothness and evaluation protocol.

  • EXBI data: JRMPC accurately registers EXBI point clouds despite many outliers, producing an outlier-free reconstruction with only 450 components.Motion averaging cannot fully correct initialization misalignments; MATrICP is more robust than MAICP, while MVICP underperforms.
  • TUM dataset: JRMPC-I handles TUM sequences containing 570 and 2880 point sets using a hierarchical front-end/back-end scheme.The front-end builds outlier-free mean sets, and the back-end incrementally refines temporal windows with JRMPC-I and batch refinement.
  • Evaluation protocol: Translation RMSE is evaluated for all JRMPC frames, whereas competing SLAM methods are evaluated only on keyframes, and the cross-modality comparison is explicitly described as unfair.The reference SLAM methods use both RGB and depth and invoke several modules for localization.
  • Trajectory comparison: The proposed trajectories can contain local perturbations because JRMPC registers depth data model-to-frame without SLAM’s internal tracking and pose-graph optimization.Figure 10 shows final fr1/desk alignment against ground truth.

VIII. CONCLUSIONS

The paper formulates multiple point-set registration as fitting a shared Gaussian mixture while jointly estimating each set’s rigid transformation. Batch and incremental EM algorithms are validated on challenging depth data and show potential for effective depth-data fusion.

  • VIII. CONCLUSIONS: The method treats every point set equally by modeling all points as realizations of one GMM, with registration cast as clustering.The GMM means form an initially unknown registered point set while rotations and translations are estimated for each input set.
  • VIII. CONCLUSIONS: Batch EM jointly estimates GMM parameters and per-set rotations and translations, while incremental EM efficiently integrates new point sets.The algorithms were compared with several state-of-the-art methods on challenging depth-camera datasets.
  • VIII. CONCLUSIONS: Experiments show the proposed approach’s potential for effectively fusing depth data.The paper reports validation on challenging datasets gathered with depth cameras.
Loading 1609.01466v2…