::  Intro  ::  k-d Trees  ::  Similarity k-d Trees  ::  Building a 2d Tree  ::  Point Set Matching  ::  Applet  ::  jGL  ::

Robust Point Pattern Matching in 3D

Point pattern matching has been extensively studied and has many applications. The paper "Using k-d Trees for Robust 3D Point Pattern Matching" by Li and Holstein propose to use k-d trees to solve problems in marker-based optical motion capture (MoCap).

Movies with 3D animated character and computer games need to have realistic motion of humanoid body to animate their characters. Although, faking the character motion is possible with software such as "character studio" in 3DS Max, it is not as realistic and we can usually tell the difference between a real motion capture from a person and an algorithm based walk.

Other domains such as sports studies and clinical gait analysis absolutely need real and accurate motion of a person.

With MoCap, the motion of markers attached to a human subject is recorded as motion of 3D points in space. The problem is that each point has to be manually labeled which can be costly in a commercial situation. Using s k-d tree, it is possible to automatically label points. The points of a reference subject in a specified pose have to be manually labeled once, but from this reference pose, it is possible to automatically label the points set of another human subject in the same pose by matching points with the reference subject. We will refer to the points on the reference subject as the model set, and to the points of the other human subject as the match set.

Human subject with reflective markers


k-d Trees
Similarity k-d Trees
Building a 2d Tree
Point Set Matching




Website created by Philippe Kuenzle (email) and Michel Langlois (email)
COMP 644: Pattern Recognition
Instructor: Godfried Toussaint, Teaching Assistant: Greg Aloupis
School of Computer Science, McGill University, Montreal, Winter 2004