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


We have a model set and a similarly distributed match set. We also show the k-d tree yielded by this model set, as well as the space partition it generates.

We will build another tree with exactly the same structure, using the construction information at each interior node of the model tree, and partition the match point set accordingly. Thus, referring to the root information (y,3), we split the match data set with respect to a line perpendicular to the y-axis, and take the points with the three smallest y-coordinate to the left child-node. The remaining points are stored in the right child-node.

So far our new match tree looks as follows:

In this way, we split the subset at each interior node hierarchically, until we meet leaf nodes that include just one point.

To continue with our example, at the left child-node, split the subset according to the corresponding model tree node information (x, 2), indicating x-perpendicular line partitioning, and among (P1, P2, P3) take the 2 points with smallest x-coordinate to the left leaf, the remaining points being stored on the right:

Finally, the last remaining model tree node dictates to take the point from (P1, P2) with the least y-coordinate to the left child-node (in this case P2, as a leaf), and the other point to the right leaf:

All that remains is to perform the actual matching of the two point sets. We traverse both trees simulataneously, matching corresponding pairs of leaves. In this case it is clear that Pi from the model set will be correctly matched with Pi from the match set (for i=1 to 4), since the model tree and the match tree are exactly identical.

The next section shows a Java applet that performs this algorithm.







 

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

 

 

 


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