[Insight-developers] point locator for kd tree
Nicholas Tustison
ntustison at gmail.com
Wed Jun 1 10:18:37 EDT 2011
Thanks, Brad, for the information. It's certainly relevant. What I'm working on
is refactoring the point set metrics. I've rewritten the point set metric base
class and the euclidean point set metric class. I also have a couple of other
point set metrics that Brian and I have published on as well as a parameterized
curve matching metric. For the point set metrics, we really need a way of
speeding up metric calculation and the kd-tree has been a good route for us.
Do you think it would be possible to make the statistics kd tree thread safe for
read-only operations? It would certainly be worth the investment for me to
get it working in a thread-safe manner.
On Jun 1, 2011, at 10:04 AM, Bradley Lowekamp wrote:
> 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/c2a9dc4c/attachment.htm>
More information about the Insight-developers
mailing list