[Insight-users] ICP with kd-trees

Fri Aug 9 14:31:06 EDT 2013

Also, FYI, other point set metrics exist in the toolkit including

https://github.com/Kitware/ITK/blob/master/Modules/Registration/Metricsv4/include/itkJensenHavrdaCharvatTsallisPointSetToPointSetMetricv4.h
https://github.com/Kitware/ITK/blob/master/Modules/Registration/Metricsv4/include/itkExpectationBasedPointSetToPointSetMetricv4.h

NIck

On Aug 9, 2013, at 1:06 PM, Ramón Casero Cañas <rcasero at gmail.com> wrote:

> 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/8bfe9ccd/attachment.htm>