[Insight-developers] point locator for kd tree

[Bradley Lowekamp]

Hello Nick,


It looks like you already made the decision not to use the statistics KDTree. I just wanted to point out that the implementation found in ITK statistics is not thread safe when doing const read-only operations. It uses some internal muted variables for cacheing, so it's not vary obvious of this problem. Not sure what your plans are for this data structure, but I hope the algorithm you are writing is multi-threaded, and that would make the Statistics KDTree not suitable.

Brad

On May 31, 2011, at 6:13 PM, Nicholas Tustison wrote:

> Perfect.  That all makes sense.  I'll put the patch together using the 
> second option sometime later tonight (hopefully) and you can take 
> a look and make comments.  I plan on pulling your point locator 
> class from the IJ article  unless there's another version I should use.
> 
> 
> On May 31, 2011, at 6:06 PM, Luis Ibanez wrote:
> 
>> Hi Nick,
>> 
>> 
>> On Mon, May 30, 2011 at 1:23 PM, Nicholas Tustison <ntustison at gmail.com> wrote:
>>> Hi Luis,
>>> 
>>> I don't know if you saw my response to your code review but in case you
>>> hadn't, I wanted to raise some of the issues I mentioned there.  I really
>>> don't care what route we go, I just want to put something in place so I can
>>> potentially submit a couple of point set metrics before the release date.
>>> 
>>> I had seen your PointLocator2 class with the same functionality that I
>>> wanted, namely to be able to locate the nearest neighbors of a user-specified
>>> point within a given point set.  However, there were a couple of issues
>>> which led me to implement the point set location functionality within the
>>> point set itself.  Geometric information, in the form of the bounding box,
>>> is already being computed in the point set as requested by the user so
>>> adding the kd-tree does not seem incongruous.
>> 
>> 
>> Here are some more considerations:
>> 
>> The itkPointSet is in the Core/Common Module
>> The itkKdTree is in the Numerics/Statistics Module
>> 
>> 
>> Currently ITK-Common only depends on
>> 
>> * ITK-VNLInstantiation
>> * ITK-KWSys
>> 
>> 
>> To implement the closest point location in the
>> itkPointSet directly we would have to move the
>> KdTree and the KdTreeGenerator to Core/Common.
>> 
>> (your patch currently works because  the Tests in Common
>> can have additional dependencies beyond the ones of
>> the ITK-Common module itself. That however will not work
>> in an application).
>> 
>> 
>> ...relocating the classes is not impossible...
>> but it is something to keep in mind...
>> 
>> 
>> Implementing the closest point location in a
>> helper class enable us to put this class out
>> of Common and out of Statistics (if we want).
>> 
>> 
>> 
>>> Additionally, you already have the function FindClosestPoint() in the
>>> point set class, although it isn't implemented properly, and that's very similar
>>> to wanting the nearest N neighbors.  So if you look at my submission, I
>>> have
>>> 
>>> FindClosestPoint()
>>> FindClosetsNPoints()
>>> FindPointsWithinRadius()
>>> 
>>> all based on the kd-tree.
>>> 
>> 
>> 
>> Agree.
>> 
>> However, they don't have to be methods of the PointSet itself.
>> 
>> For example, the itkImage doesn't have a function that gives
>> your the index of pixel with the maximum value or minimum
>> value.
>> 
>> We implement such services in calculators.
>> 
>> DataObjects should be only "containers of data"
>> 
>> 
>>> Also, I believe the code entanglements that you mention is what led me to
>>> implement the VectorContainerToListSampleAdaptor class which seems a
>>> much better use of the data then the PointSetToListSampleAdaptor class
>>> which ignores everything in the point set class except for what is housed in the
>>> PointSetContainer class which is a VectorContainer type.
>>> 
>> 
>> I certainly agree.
>> 
>> for the purpose of the KdTree we only
>> need the point coordinates information.
>> 
>> Your adaptor is better suited for this goal.
>> 
>> 
>>> So, although what I propose is one possible solution, another solution would
>>> be to submit the PointSetLocator2 class (with a possible deletion of  the
>>> FindClosestPoint() function in the PointSet class?).   What are your thoughts
>>> in favoring one over the other?
>>> 
>> 
>> 
>> I would vote for this second option.
>> 
>> 
>> Namely:
>> 
>> 1) Add the PointSetLocator2 (renamed as PointSetLocator)
>>   Based on the KdTree.
>> 
>> 2) Adopt the use of your new Adaptor, so that the PointSet
>>   Locator focuses on the point coordinates.
>> 
>> 3) Put the computation of the PointSet Bounding box in the
>>   PointLocator or another helper class.
>> 
>> 4) Remove the FindClosestPoint() from the PointSet,
>>   and make it available in the PointLocator.
>> 
>>   Since the method was never functional in the PointSet,
>>   this is not a backward compatibility concern.
>> 
>> 
>> I'm happy to put such patch together,
>> or to assist you in doing so.
>> 
>> 
>>   Luis
> 
> _______________________________________________
> Powered by www.kitware.com
> 
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
> 
> Kitware offers ITK Training Courses, for more information visit:
> http://kitware.com/products/protraining.html
> 
> Please keep messages on-topic and check the ITK FAQ at:
> http://www.itk.org/Wiki/ITK_FAQ
> 
> Follow this link to subscribe/unsubscribe:
> http://www.itk.org/mailman/listinfo/insight-developers

========================================================
Bradley Lowekamp  
Lockheed Martin Contractor for
Office of High Performance Computing and Communications
National Library of Medicine 
blowekamp at mail.nih.gov

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/mailman/private/insight-developers/attachments/20110601/cbbebcf5/attachment.htm>