Finding Correspondences between Shapes

• How do we find corresponding points?

• Well if we already had the transformation to align the shapes, then we could just look up correspoinding points, but this is what we are trying to find…

• We can solve it with Iterative Closest Points (If starting position is close enough)

• If starting positions are not close we have some options:

Exhaustive Search #

• Sample the space of all possible aligments
• Find alignment at which models are closest
• refine with ICP
• will be really slow
• intractable for large degrees of freedom (non-rigid deformations)

Normalization #

• Center all shapes at the origin and use PCA to find the principal directions

• Works only for handful of initial configurations

• Works well for complete shapes with no noise

• Possible problems:

  • Axes aligned the wrong way:

    

  • Unstable axes

    

  • Partial Similarity

    

Random Sampling #

• Similar to exhaustive search but sample the space of possible alignments a bit smarter
• Iterate:
  • Pick random pair of (3 for rigid) points on both shapes
  • Estimate alignment, and check for error

Invariant features #

• Try to identify salient feature points on each shape
• Establish correspondence between them
• Align using correspondences