[Insight-users] ICP with kd-trees

[Nick Tustison]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20130809/a9814df7/attachment.htm>