[Insight-users] ICP with kd-trees
Ramón Casero Cañas
rcasero at gmail.com
Fri Aug 9 13:06:46 EDT 2013
Nope, I'm a fool.
itk::EuclideanDistancePointSetToPointSetMetricv4
has a line
PointIdentifier pointId =
this->m_MovingTransformedPointsLocator->FindClosestPoint( point );
https://github.com/Kitware/ITK/blob/master/Modules/Registration/Metricsv4/include/itkEuclideanDistancePointSetToPointSetMetricv4.hxx
I suppose this is an itk::PointsLocator: "This class accelerates the search
for the closest point to a user-provided point, by using constructing a
Kd-Tree structure for the PointSetContainer."
http://www.itk.org/Doxygen/html/classitk_1_1PointsLocator.html
So the functionality is already there, and I can just use the ITK class
directly.
Best regards,
Ramon.
On 9 August 2013 17:30, Ramón Casero Cañas <rcasero at gmail.com> wrote:
> Hi Nick,
>
> Thanks again. OK, so if I understand it correctly, your
> itk::ManifoldParzenWindowsPointSetFunction is an interpolator of a set of
> points. You used kd-trees to find nearest neighbours faster, but no metric
> class derived from itk::PointSetToPointSetRegistrationMethod was written.
>
> This is the class of metric that I need to pass to the registration
> algorithm.
>
> Basically, I think that the way forward for me is to rewrite itk::EuclideanDistancePointMetric,
> but using a kd-tree instead of the distance map, and PointLocator2
> instead of sampling the distance map, if that makes any sense.
>
> Best regards,
>
> Ramon.
>
>
>
>
> On 9 August 2013 16:36, Ramón Casero Cañas <rcasero at gmail.com> wrote:
>
>> Hi Nick,
>>
>> I hit send before receiving your reply. Many thanks, I'm starting to look
>> into your pointers and will report back.
>>
>>
>> Best regards,
>>
>> Ramon.
>>
>>
>> On 9 August 2013 16:24, Nick Tustison <ntustison at gmail.com> wrote:
>>
>>> HI Ramon,
>>>
>>> A couple years ago or so, I contributed the following to the Insight
>>> Journal
>>>
>>> http://www.insight-journal.org/browse/publication/317
>>>
>>> based on
>>>
>>> http://www.ncbi.nlm.nih.gov/pubmed/20937578
>>>
>>> We used kd-trees to speed up the point search. You can see this in
>>> the function where we use the kd-tree directory
>>>
>>>
>>> https://github.com/midas-journal/midas-journal-317/blob/master/Source/JHCT/itkManifoldParzenWindowsPointSetFunction.txx
>>>
>>> starting at line 63. Part of our ITKv4 registration refactoring included
>>> this work so these functions are part of the current repository albeit
>>> slightly modified and we ended up using the PointsLocator class
>>>
>>>
>>> ITK/Modules/Registration/Metricsv4/include/itkManifoldParzenWindowsPointSetFunction.hxx
>>>
>>> Nick
>>>
>>>
>>>
>>> On Aug 9, 2013, at 8:23 AM, Ramón Casero Cañas <rcasero at gmail.com>
>>> wrote:
>>>
>>> Dear all,
>>>
>>> I'm trying to build an Iterative Closest Point algorithm with ITK.
>>>
>>> I have googled advice on how it can be put together generally, and
>>> checked the three examples
>>>
>>> Insight/Examples/Registration/
>>> IterativeClosestPoint1.cxx
>>> IterativeClosestPoint2.cxx
>>> IterativeClosestPoint3.cxx
>>>
>>> recommended here
>>>
>>> http://www.itk.org/pipermail/insight-users/2004-June/009092.html
>>>
>>> These examples don't use kd-trees (the last ones uses a distance
>>> transform).
>>>
>>> I have also found an example of a kd-tree, that however doesn't use
>>> point sets
>>>
>>> http://www.itk.org/Wiki/ITK/Examples/Statistics/KdTree
>>>
>>> I found an "itkPointLocator2.h" class developed
>>> for itkQuadEdgeMeshRigidRegistration in the ITK journal. I downloaded it
>>> from a more up-to-date publication that makes use of it, "Mesh Similarity
>>> Calculator" by Li and Magnotta (2010)
>>>
>>> http://www.insight-journal.org/browse/publication/762
>>>
>>> What I don't know is how to extract a metric from said locator, to pass
>>> it to the registration object.
>>>
>>> This is the relevant part of the code I have so far
>>>
>>> <CODE>
>>> PointSetType::Pointer fixedPointSet = PointSetType::New();
>>> PointSetType::Pointer movingPointSet = PointSetType::New();
>>>
>>> // do something to read the points into the point sets
>>>
>>> // construct a Kd-tree structure for the reference point set, to
>>> // accelerate the search for closest point
>>> typedef itk::PointLocator2<PointSetType> PointLocatorType;
>>> PointLocatorType::Pointer locator = PointLocatorType::New();
>>>
>>> locator->SetPointSet(fixedPointSet);
>>> locator->Initialize(); // pre-compute the kd-tree structure
>>> </CODE>
>>>
>>> I think I could get the metric from the kd-tree with something like
>>>
>>> tree->GetDistanceMetric()
>>>
>>> but I cannot get the tree from the locator, can I?
>>>
>>>
>>> https://github.com/midas-journal/midas-journal-762/blob/master/QuadEdgeMeshRigidRegistration/Source/itkPointLocator2.h
>>>
>>> Is this just a matter of adding a GetKdTree() method to
>>> itkPointLocator2.h, or is there some better solution to this?
>>>
>>>
>>>
>>> Alternatively, if we not only have point sets at the input, but
>>> triangular meshes, it would be possible to compute shortest distances from
>>> the vertices of movingPointSet to a triangular mesh fixedTriMesh. This is
>>> efficient using an AABB tree (which can internally use a kd-tree), as in
>>> the CGAL library
>>>
>>>
>>> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/AABB_tree/Chapter_main.html
>>>
>>> but this probably requires a vast amount of work? Or would it be
>>> relatively easy to write a new metric PointToTriMesh for ITK that imports
>>> CGAL AABB trees? I'm asking because I have no idea of how involved writing
>>> a new Metric class would be.
>>>
>>>
>>> Best regards,
>>>
>>> Ramon.
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> --
>>> Dr. Ramón Casero Cañas
>>>
>>> Oxford e-Research Centre (OeRC)
>>> University of Oxford
>>> 7 Keble Rd
>>> Oxford OX1 3QG
>>>
>>> tlf +44 (0) 1865 610739
>>> web http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
>>> photos http://www.flickr.com/photos/rcasero/
>>> _____________________________________
>>> 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://www.kitware.com/products/protraining.php
>>>
>>> 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-users
>>>
>>>
>>>
>>
>>
>> --
>> Dr. Ramón Casero Cañas
>>
>> Oxford e-Research Centre (OeRC)
>> University of Oxford
>> 7 Keble Rd
>> Oxford OX1 3QG
>>
>> tlf +44 (0) 1865 610739
>> web http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
>> photos http://www.flickr.com/photos/rcasero/
>>
>
>
>
> --
> Dr. Ramón Casero Cañas
>
> Oxford e-Research Centre (OeRC)
> University of Oxford
> 7 Keble Rd
> Oxford OX1 3QG
>
> tlf +44 (0) 1865 610739
> web http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
> photos http://www.flickr.com/photos/rcasero/
>
--
Dr. Ramón Casero Cañas
Oxford e-Research Centre (OeRC)
University of Oxford
7 Keble Rd
Oxford OX1 3QG
tlf +44 (0) 1865 610739
web http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
photos http://www.flickr.com/photos/rcasero/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20130809/3f5d37c7/attachment.htm>
More information about the Insight-users
mailing list