[Insight-users] KD Tree Search Question...

[Tuhin Sinha]

Hello insight-users,

I have a quick question about the KdTree implementation in ITK.  I have
started using the KdTree in ITK to help speed up nearest-neighbor
searches in high-dimensional spaces (D > ~500).  In the process of
testing the KdTree, I noticed that for a k-nearest-neighbor search: 1)
the nearest-neighbors are not returned in any specific order, and 2)
_sometimes_ the query point itself (which is guaranteed to be in the
KdTree) is returned as a nearest-neighbor.

The first observation is not a big issue, but the second one is
problematic for my specific needs.  I would like to enforce some
consistency in the behavior of the KdTree in terms of the returned
nearest-neighbors; either give me the query point every time or never.

  Does the behavior I am getting from the KdTree correlate with what the
developers intended?  That is, if one query's a KDTree in ITK with a
point that is in the KDTree what should be the returned
nearest-neighbor, itself or it's closest neighbor?  In my testing a
1-neighbor search yeilds both results; sometimes I get the query point,
and sometimes I don't.  Is the end-user supposed to enforce some sort of
redundancy checking of the returned nearest neighbors for KD searches in
ITK? Or, do I have a bug in my code?  I am running ITK 2.4 under Linux.

Thanks,
-- 
Tuhin K. Sinha, Ph.D.
Institute of Imaging Science
Department of Radiology and Radiological Sciences
Vanderbilt University
Medical Center North,  Suite R-1302
Nashville, TN 37232-2310