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.