[Insight-users] ICP with kd-trees

[Ramón Casero Cañas]

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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20130809/8423e42a/attachment.htm>