[ptx] kdTree Matching ...

[alexandre jenny]

Hi,

Let's face it, the kd-tree maching isn't so good as it should be (or
perhaps, there's something I didn't came up with). To illustrate a little
bit, let's have a 3 pictures panoramas :
(img1.jpg, img2.jpg and img3.jpg). Every picture has points in common with
the 2 others.
Now, there's 2 options to match the keys.

1. Build a big kd-tree with all the points in it. Algorithm : 
   For every key, look for the 3 nearest neightboor.
     Test for match (lowe test, d1>0.8*d2), store it.

   What does it need ? Imaging it's the case of a key in picture 1 which is
also in 2 and 3.
   This approach with only give one link, perhaps 1->2 or 1->3 but not both.
We miss some key matching by
   doing that ...

2. Build a kd-tree for every picture. Algorithm :
   For every key of picture i
     compare this key with keys in picture i+1..end 
       store nearest neightboor.

   This approach gives for every picture pair (i, j) the NN. But it gives
really too much match. It gives the same
   number of match for non matching picture as matching picture. But you
don't miss any.

I tried both ... The 1st is faster than second, of course. 

---
Another point is the fact that BBF is good but really misses offen the best
neightboor for the dimension of the
Search (128). So you will miss many key match.

Bye,
  Alexandre