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


Remarks and Usage

  • First Mode: Model Set Edition

    In this mode we construct the model point set, in red.

      In 2D In 3D
    To add a point Click anywhere on the canvas Fill the 3 boxes in the right panel and click Add (use coordinates ranging from -200 to 200 in each dimension)
    To remove a point Click on a point while pressing Ctrl Select it from the list in the right panel and click Delete
    To move a point Click on a point and drag-and-drop it Delete & add...
    To move the whole point set Use the three sliders in the right panel Use the six sliders in the right panel

  • Second Mode: Match Set Generation
    "Random Match Set" Choose a degree of perturbation between 0 and 40 (default is 10), and click on the button. This applies a non affine transformation to the red model set, generating a random blue match set. One remark: be patient the first time you click it, for some reason it takes a few seconds to generate (but just the first time).
    "Show matchings" This checkbox is only available when valid model set and match set are present in the canvas. This checkbox shows/hides the matchings between the model set and the match set. We don't show the similarity k-d tree here, but the algorithm used is exactly the one described on this web site. Correct matchings are shown in orange and incorrect ones in dark gray. It's interesting to generate a model set that is bunched up together, then generating a succession of match sets and looking at the matchings in each case. We get a good idea of how often the algorithm makes mistakes.
    "Show hyperplanes" This checkbox is only available when valid model set and match set are present in the canvas. This checkbox shows/hides the hyperplanes that divide the space given the specified model set. One possible mistake is to assume that model and match points are matched together if they lie in the same cell. This in fact is NOT how the algorithm works (see previous sections), but it is interesting nonetheless to observe how robust the partition is to small movements of the points (i.e. it stays the same).
Reference for this website

Li, Baihua, and Holstein, Horst, Using k-d Trees for Robust 3D Point Pattern Matching, Proceedings of the Fourth International Conference on 3-D Digital Imaging and Modeling, October 10th, 2003, pp. 95-102







 

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