Simultaneous Covariance Driven Correspondence (CDC) and Transformation Estimation in the Expectation Maximization Framework

This page gives a high level overview of our research on Covariance Driven Correspondences (CDC). For more details, please refer to our article published in CVPR 2007 proceedings.

Contents


Overview

  • Novel registration algorithm, that depends fundamentally on the estimation of uncertainty in point correspondences
  • Uncertainty derived from the covariance matrices of the individual point locations and from the covariance matrix of the estimated transformation parameters
  • Robust objective function and an EM-like algorithm to simultaneously estimate the transformation parameters, their covariance matrix, and the likely correspondences
  • No annealing schedule nor an explicit outlier process needed
  • Broader domain of convergence than the Iterative Closest Point (ICP) algorithm and is more robust to missing or extraneous structures in the data than Robust Point Matching (RPM) [1]

Introduction

Iterative closest point (ICP) algorithm starts from an initial estimate of the transformation parameters, uses this to generate an initial set of correspondences, re-estimates the parameters, and iterates.

Problem of standard ICP (illustrated in Figure 1)

  • for moving points (red circles) along the horizontal line of the 'H', the closest fixed points (blue crosses) are along one of the two vertical lines
  • noise in the locations and surface normals of points along the sides of the 'H' produces constraints that resist changes in the transformation

Figure 1: Difficulties in correspondence estimation and alignment of two 'H' shapes. Points on the moving 'H' are shown as red circles, while points on the fixed 'H' are shown blue x's. In (a), ICP correspondences are shown for points on the cross-bar of the 'H' as red line segments. These mismatches prevent ICP from properly aligning the shapes. When alignment uncertainty is properly accounted for (b) these same points preferentially establish correspondence with points on the opposing cross-bar.

CDC introduction: ICP fails CDC introduction: alignment uncertainty

Robust Point Matching Algorithm (RPM) [1] starts by initially considering all possible matches, and then, using an annealing schedule, gradually moves toward unique correspondences as the transformation is refined.

Problem of RPM

  • works poorly, when there are missing or extraneous structures (Figure 2(a))
  • in the early stages of its computation RPM tends toward aligning the centers of mass of the points, producing a bias in the estimate when there are extraneous structures that can not be overcome in later stages of the computation

Figure 2: (a) The extra lengths at the top of the red 'H' and the red outliers prevent RPM [1] from properly aligning these two shapes. The CDC correspondence uncertainties --- the initial uncertainties are in (b) ---eventual narrow as the algorithm converges, allowing it to ignore incorrect correspondences due to these extraneous structures.

Problem of RPM: noisy shapes
CDC uncertainties

CDC fixes the problems

  • uncertainty in the transformation estimate produces uncertainty in the mapped point positions that is predominantly in the vertical direction which allows correspondences between points on the crossbars of the two H's to be preferentially established
  • correspondences between points along the two sides of the 'H' indicate large uncertainty in the vertical direction so they do not work against the changes in the transformation

Covariance of the Alignment Error

Alignment Error
          Alignment error

Covariance of a Correspondence
          Covariance of a Correspondence

Residual
          Residual

Error
          Error

Robust Objective Function

Distribution of Error
          Distribution of Error

Log Likelihood
          Log Likelihood

Robust Function
          Robust Function

where
          Beaton-Tukey robust function ......Constant Multiplied Beaton-Tukey
          Competitive weights ......Competitive Weights
          Robust weights ......Robust Weights

Figure 3: Robust function and robust weight function.

Beaton-Tukey robust function and robust weight function

Algorithm Outline

Starting from an initial transformation parameter vector Initial parameters, the point sets Moving points and Fixed points, and the point covariances:

  1. Compute an initial estimate of transformation parameter covariance matrix Parameter covariance.
  2. Iterate until convergence
    • (a) Recompute the weights Weights for all correspondences keeping Parameter estimate and fixed.
    • (b) Update the parameter estimate Parameter estimate holding Covariance estimate and Weights fixed.
    • (c) Recompute the weights Weights as in Step 2(a).
    • (d) Update the covariance matrix estimate Covariance estimate holding Parameter estimate and Weights fixed.

Results

Example of alignment of two H-like shapes:

  1. Initial transformation and matches
  2. Initial covariance estimate
  3. Covariance estimate after a few iterations
  4. Most uncertainty in vertical direction
  5. Lower uncertainty of the parameter estimate
  6. Fully aligned

Figure 4: Example of aligning two H shapes using a similarity transformation. Correspondence covariance matrices Sij are shown as oriented uncertainty ellipses. The initial alignment and CDC covariances are shown in (a). Frames (b) through (d) illustrate intermediate results, ending in convergence.

Initial transformation and matches Initial covariance estimate
(1) (2)
Covariance estimate after a few iterations Most uncertainty in vertical direction
(3) (4)
Lower uncertainty of the parameter estimate Fully aligned
(5) (6)

Figure 5: Click to download a movie (~5MB) of aligning two H shapes using a similarity transformation. The movie shows progress from initialization to alignment.

Aligning shapes with CDC

Convergence analysis with different initializations

  • moving shape (red circles) initialized at the marked locations around a circle with five different orientations
  • green line segment indicates a location and orientation from which the algorithm converged correctly
  • red segment indicates a failure

Figure 6: Convergence analysis for two H shapes using ICP with normal distances (a), RPM (b), and the CDC algorithm proposed here (c). The moving shape (red circles) was initialized at the marked locations around a circle with five different orientations, shown by the orientations of the green/red line segments, at each location. A green line segment indicates a location and orientation from which the algorithm converged correctly, while a red segment indicates a failure.

Convergence ICP Convergence RPM
(a)(b)
Convergence CDC
(c)

The effect of noise and structural changes and the way RPM and CDC handles them.

Figure 7: Example of aligning two H shapes with noise (a) and structural (b). Robust Point Matching (RPM) fails because of the correspondences generated with extraneous structures (c),(d), while the proposed CDC algorithm locks onto the correct correspondences and correctly aligns the shapes (e),(f).

Noisy shapes Shapes with structural changes
(a) Noisy shapes(b) Structural changes
RPM alignment of noisy shapes RPM alignment of shapes with structural changes
(c) RPM alignment(d) RPM alignment
CDC alignment of noisy shapes CDC alignment of shapes with structural changes
(e) CDC alignment(f) CDC alignment

Dual-Bootstrap ICP Algorithm (DBICP) [1]

  • DBICP
    • (a) initial transforms accurate over a small region
    • (b) ICP estimation, refinement and region growth
    • (c) sophisticated set of decision criteria
  • 81% of initial estimates refined to an accurate transform
  • Step (b) based on CDC: correct alignment of 36% of the initializations that failed when using ICP

Figure 8: Images from different viewpoints aligned with CDC that failed with DBICP.

Image 1 Alignment of a pair with a viewpoint change
Image 2



Figure 9: Enlarging the region to include more matches during convergence of the CDC algorithm.

Aligning images with CDC, initialization Aligning images with CDC, uncertainty
Aligning images with CDC, correct matches Aligning images with CDC, convergence

3D Rigid Registration

  • Align scans with different viewpoints and pairs with different overlaps (more difficult than prerotating data to register against itself)
  • Initialize with identity transform
  • ICP aligned 9 scan pairs
  • CDC aligned 16, including the 9 ICP aligned
  • CDC failed on only two pairs with inter-scan rotation angle less than 80 degrees (failures: 56 and 59 degree rotations)
  • ICP failed on most pairs rotated by more than 45 degrees.

Figure 10: Example initial transformations (left column) and final CDC alignments (right column) on the Stanford bunny dataset (best seen in color). In both cases robust ICP using normal distance constraints failed to converge.

Bunny 090 ear back Bunny 090 ear back, CDC aligned
Bunny 000 chin Bunny 000 chin, CDC aligned
Bunny 315 chin Bunny 315 chin, CDC aligned



Figure 11: Click to download a movie (~16MB) of aligning two scans of the bunny. Notice the change of the resolution throught the alignment (uncertainty gets lower) and sliding into complete alignment.

Bunny alignement with CDC, movie

Summary

  • Uncertainty in correspondences drives matching and parameter estimation
  • Parameter covariance estimated as a free variable
  • Robust EM algorithm
  • Broader domain of convergence than ICP, local characteristic of ICP removed
  • Euclidean and normal distance ICP are special cases -> generalizing (replacing) ICP
  • More robust to noise and missing or extraneous structures than RPM

Publications and Further Reading

  1. Sofka, M., Yang, G., V. Stewart, C., 2007. Simultaneous Covariance Driven Correspondence (CDC) and Transformation Estimation in the Expectation Maximization. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Minneapolis, MN, USA.



Bibliography

[1] H. Chui, A. Rangarajan, J. Zhang, and C. M. Leonard. Unsupervised learning of an atlas from unlabeled point-sets. IEEE Pattern Analysis and Machine Intelligence., 26(2):160-172, 2004.

[2] G. Yang, C. V. Stewart, M. Sofka, and C.-L. Tsai. Registration of Challenging Image Pairs: Initialization, Estimation, and Decision. IEEE Pattern Analysis and Machine Intelligence, 23(11):1973-1989, November 2007.