This flashcard is just one of a free flashcard set. See all flashcards!

Assumption: Scanned patches have identical scale.
Goal: Find a rigid transformation (rotation and translation) for one of the patches to align it with the other.

Algorithm Overview
1. Initial alignment: Provided by the user
2. Matching: Find corresponding points in the two patches
3. Registration: Compute optimal translation and rotation
4. Repeat from step 2 until convergence.

Matching
Matching Strategy: Nearest Neighbor
For every vertex in patch , select the nearest neighbor vertex from patch .
Filtering: Remove those matchings where one vertex is a boundary vertex (since boundary vertices match to many points). Remove matchings with a high distance. Remove matchings with a high normal deviation.

Matching Strategy: Normal Piercing
From each vertex in patch , shoot a ray into normal direction. If this ray intersects with in point , add the correspondence .

Registration
Given a list of corresponding vertices
we want to find a transformation such that


Finding the translational part just amounts to shifting the center of gravity of the into that of the by adding an offset



We just assume this translational registration has already taken place and just focus on the rotational alignment:



The first and last term are independent of



Problem: Finding a solution for the rotation matrix requires finding 9 unknowns (of which 6 need to be constrained). Solution: Formulate the rotation as a quaternion (gives 4 unknowns with 1 additional constraint).









is a symmetric matrix. To compute a solution for , find the eigenvector to the largest eigenvalue. Normalize to obtain a rotation.