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
• Introduction
• Covariance of the Alignment Error
• Algorithm Outline
• Results
• Summary
• Bibliography

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.

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.

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
          

Covariance of a Correspondence
          

Residual
          

Error
          

Robust Objective Function

Distribution of Error
          

Log Likelihood
          

Robust Function
          

where
           ......Constant Multiplied Beaton-Tukey
           ......Competitive Weights
           ......Robust Weights

Figure 3: Robust function and robust weight function.

Algorithm Outline

Starting from an initial transformation parameter vector , the point sets and , and the point covariances:

1. Compute an initial estimate of transformation parameter covariance matrix .
2. Iterate until convergence
   • (a) Recompute the weights for all correspondences keeping and fixed.
   • (b) Update the parameter estimate holding and fixed.
   • (c) Recompute the weights as in Step 2(a).
   • (d) Update the covariance matrix estimate holding and 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.

(1)	(2)
(3)	(4)
(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.

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.

(a)	(b)
(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).

(a) Noisy shapes	(b) Structural changes
(c) RPM alignment	(d) RPM alignment
(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.

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

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.

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.

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.
   abstract bibtex

   This paper proposes a new registration algorithm, Covariance Driven Correspondences (CDC), that depends fundamentally on the estimation of uncertainty in point correspondences. This uncertainty is derived from the covariance matrices of the individual point locations and from the covariance matrix of the estimated transformation parameters. Based on this uncertainty, CDC uses a robust objective function and an EM-like algorithm to simultaneously estimate the transformation parameters, their covariance matrix, and the likely correspondences. Unlike the Robust Point Matching (RPM) algorithm, CDC requires neither an annealing schedule nor an explicit outlier process. Experiments on synthetic and real images using a polynomial transformation models in 2D and in 3D show that CDC has a broader domain of convergence than the well-known Iterative Closest Point (ICP) algorithm and is more robust to missing or extraneous structures in the data than RPM.

   @inproceedings{sofka:cvpr07,
     author = {Sofka, Michal and Yang, Gehua and V.\ Stewart, Charles},
     title = {Simultaneous Covariance Driven Correspondence
                       ({CDC}) and Transformation Estimation in the
                       Expectation Maximization},
     booktitle = {Proceedings of the IEEE Conference on Computer Vision
                       and Pattern Recognition (CVPR)},
     month = "18--23~" # jun,
     address = {Minneapolis, MN, USA},
     year = {2007},
     url = {http://www.sofka.com/projects/cdc/},
     annote = {}
   }
   

   
   

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.