[Insight-developers] point locator for kd tree

[Luis Ibanez]

Hi Nick,

When the patch is approved with comments, we trust
that the author of the patch will address the comments
before merging.

It is a way of expediting the process. Typically this is
done for minor changes (e.g. typos, a const missing...)
that are easy to fix before merging, and that are not
controversial, and that therefore do not merit to go
through another round of reviews.

So, if you already addressed the comments, (of a
patch that was approved with comments pending)
please go ahead and merge it.


   Thanks


        Luis


------------------------------------------------------------------------------
On Fri, Jun 3, 2011 at 4:00 PM, Nick Tustison <ntustison at wustl.edu> wrote:
> Hi Luis,
> In general, when you approve of a patch on gerrit but
> also make suggested comments, do you need to
> approve of it again before merging after I've made
> another patch to address those comments?
> Thanks,
> Nick
>
> On Thu, Jun 2, 2011 at 3:07 PM, Luis Ibanez <luis.ibanez at kitware.com> wrote:
>>
>> 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
>> >>>
>> >>>
>> >
>> >
>
>