[Mne_analysis] ICP algorithm

[Matti Hamalainen]

On Dec 3, 2008, at 6:18 PM, Megan Schendel wrote:

> Hi,
> I am curious about the algorthim used for ICP alignment in coordinate
> alignment between scalp surface and digitizer data.

Hi,

Here is the reference that explains it all:

A method for registration of 3-D shapes

Besl, P.J.; McKay, H.D.

Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume 14, Issue 2, Feb 1992 Page(s):239 - 256

Digital Object Identifier   10.1109/34.121791

Summary:The authors describe a general-purpose, representation- 
independent method for the accurate and computationally efficient  
registration of 3-D shapes including free-form curves and surfaces.  
The method handles the full six degrees of freedom and is based on the  
iterative closest point (ICP) algorithm, which requires only a  
procedure to find the closest point on a geometric entity to a given  
point. The ICP algorithm always converges monotonically to the nearest  
local minimum of a mean-square distance metric, and the rate of  
convergence is rapid during the first few iterations. Therefore, given  
an adequate set of initial rotations and translations for a particular  
class of objects with a certain level of `shape complexity', one can  
globally minimize the mean-square distance metric over all six degrees  
of freedom by testing each initial registration. One important  
application of this method is to register sensed data from unfixtured  
rigid objects with an ideal geometric model, prior to shape  
inspection. Experimental results show the capabilities of the  
registration algorithm on point sets, curves, and surfaces


Summarizing:

Step 1: On the MRI-based triangulated head surface, determine the  
closest point to each of the head-surface points digitized before the  
MEG acquisition. Note that these closest points are not necessarily at  
the vertices of the triangulation but may be on the triangular faces  
or on the sides of the triangles as well.

Step 2: Compute the linear transformation (translation and rotation)  
which brings the digitized points as close as possible to the closest  
points on the head surface, determined in Step 1. This linear  
transformation is computed by first aligning the centers of mass of  
the two point sets and then solving the orthogonal Procrustes problem  
(see, http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem) to  
find the optimal rotation.

Step 3: Compute squared sum of distances between the corresponding  
points in the the aligned point sets.

Step 4: Compare this distance to the one obtained in the previous  
iteration. If converged, exit, otherwise, goto Step 1.


I hope this helps.

- Matti