[Insight-developers] point locator for kd tree

[Luis Ibanez]

Hi Nick,

Thanks for preparing the patch.
http://review.source.kitware.com/#change,1765

The review now has comments for a couple of
suggested changes/fixes.


    Thanks


          Luis


-----------------------
On Wed, Jun 1, 2011 at 3:50 PM, Nicholas Tustison <ntustison at gmail.com> wrote:
> Thanks Luis.  Fortunately, that's the version with which I started.  I added
> a little error checking.  I added a couple functions to augment the
> Search() functions already defined in the class.  I also fitted it to use
> the PointsContainer as opposed to the PointSet.  The template
> parameters mirror the BoundingBox class which I thought was  a good
> model.  Currently, I'm finishing the last of the debugging.  The bounding
> box was fairly entrenched within the Mesh object and its derivatives and
> so that took some time to modify.
>
>
> On Jun 1, 2011, at 3:30 PM, Luis Ibanez wrote:
>
>> Hi Nick,
>>
>> The most recent version of the code is in
>> the NAMIC Sandbox:
>>
>> http://svn.na-mic.org/NAMICSandBox/trunk/QuadEdgeMeshRigidRegistration/Source/
>>
>> Wen Li (University of Iowa) made many improvements
>> in the code, after the initial papers were submitted to
>> the Insight Journal.
>>
>>
>>
>>      Luis
>>
>>
>> -----------
>> On Tue, May 31, 2011 at 6:13 PM, Nicholas Tustison <ntustison at gmail.com> 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
>>>
>>>
>
>