In marker-based motion capture applications, one
desirable property that a space-partitioning data structure (such as a
k-d tree) should possess is invariance to certain transformations of the
point set.
We will say more about this in the section on point set matching, but
basically this is because ideally we would like two k-d trees generated
on two different but similarly distributed point sets to be as similar
as possible.
Most variants of k-d trees are robust to affine transformations (such as
rotation or translation) of rigid objects, but in MoCap this is not
quite enough. Consider human legs, and take as model set the set of
markers on these legs in fully extended position.
Now bend the knees a little, and take this new point set as the match
set.
|
|
|
The
model set: extended legs
|
The
match set: slightly bent legs
|
This transformation is not affine, and furthermore legs are not a
perfectly rigid object (such as a box for example). If we hope to match
these two point sets correctly, we need a variant of k-d trees that is
robust to such point set distribution errors and to such non rigidity.
One flavor of k-d trees that proves useful in such MoCap applications
is the Similarity k-d Tree.
Contrary to the k-d tree seen in the previous section, where at least
one data point lay on each chosen hyperplane, this tree partitions the
space in such a way that data points lie far from the chosen
hyperplanes.
Next we show how to build a similarity 2d
tree.
