[ptx] Question on BBF used in Brown's paper.

[Sebastian Nowozin]

Hi Xianyong Fang,


On Wed, Mar 31, 2004 at 04:58:48PM +0800, Xianyong Fang wrote:

> In Brown's paper:Recognising Panoramas, he used BBF algorihtm to search the
> KD tree. But when I check ANN(http://www.cs.umd.edu/~mount/ANN/), I find that
> there is another algorithm that seems to fulfil the same purpose. In ANN,that
> algorithm is called priority search which is based on Arya and Mount's
> paper:Approximate nearest neighbor queries in fixed dimensions.(In Proc. 4th
> ACM-SIAM Sympos. Discrete Algorithms,pp 271-280,1993). 

> In ANN's user manual, it writes:Whenever we arrive at a nonleaf node, we
> compute the distances from the query point to the cell of the two children.
> We enqueue the further child on a priority queue, sorted by distance, and
> then visit the closer child recursively. On arriving at a leaf node, we
> compute the distance to the points sorted in this node, and continue by
> dequeing the next item form the priority queue. 
 
First, let me say I have not read the ANN manual nor the code. But I
implemented the BBF algorithm and this is exactly the idea you described. I am
not sure if the order is like this (like enqueuing while traversing down),
maybe it also goes the reverse way by first finding the closest child and then
recursing up.


> I also check the original paper on BBF algorithm. According to my
> understanding, I find that these two algorithm have the same idea. 

> So does anybody can tell me where i am wrong here? 
 
I think you aren't wrong. If you want to implement BBF, maybe try not to make
the same mistakes I made while doing it. (in the autopano-sift package its in
KDTree.cs, although I am not sure its correct). The algorithm looks intuitively
and easy to implement, but for two reasons I found it quite difficult to get
right:

 - I used an implementation in C as a base that is not trivially recursive and
   does some work before and after the recursion. Therefore, if you plan for
   new features such as the BBF search, using such a non-trivial recursive as a
   base is maybe not a good idea.

 - Later, when BBF worked I wanted to have the k-nearest neighbour
   functionality, which required changes in both the plain kd-tree part and
   the BBF search part. The priority queue is global and has to be passed
   unchanged through the recursions.

So, just plan beforehand and not just finish each feature alone. :)

For the k-nearest neighbours I found the BBF performance to be decreasing until
it found k neighbours. But for the keypoint matching it is very helpful to have
the ratio of the first and second hit, as Brown and Lowe recommend.


> Xianyong

Zaijian,
Sebastian

-- 
nowozin at cs.tu-berlin.de --- http://user.cs.tu-berlin.de/~nowozin/