[Insight-users] ICP with kd-trees

Fri Aug 9 11:35:16 EDT 2013

Thanks, Brad. Checking the snippet about the metric in your example, and
the error messages I get, I think there's a problem in that distance
metrics in kd-trees are different from PointSetToPointSetMetrics.

The kd-tree provides an

itk::Statistics::EuclideanDistanceMetric<TVector>

http://www.itk.org/Doxygen/html/classitk_1_1Statistics_1_1EuclideanDistanceMetric.html

while the registration algorithm requires an

itk::PointSetToPointSetMetric<TFixedPointSet, TMovingPointSet>
^
|
itk::EuclideanDistancePointMetric<TFixedPointSet, TMovingPointSet>

http://www.itk.org/Doxygen/html/classitk_1_1PointSetToPointSetMetric.html

Thus, this approach will not compile because of type mismatch

<WRONG>
  typedef itk::PointSetToPointSetRegistrationMethod<PointSetType,
    PointSetType> RegistrationType;

  RegistrationType::Pointer registration = RegistrationType::New();

  TreeType *tree = const_cast<TreeType
*>(locator->GetKdTree().GetPointer());

  registration->SetMetric(tree->GetDistanceMetric());
</WRONG>

Does anybody have any ideas on how to approach using itk::KdTree to
generate the metric of a point-to-point registration algorithm?

Best regards,

Ramon.

On 9 August 2013 13:32, Bradley Lowekamp <blowekamp at mail.nih.gov> wrote:

> Hello,
>
> I am not too familiar with this KDTree. But I recently added some indexing
> of the ITK Example in the doxygen, which includes cross linking between the
> examples and the class.
>
> The KdTreeGenerator:
>
>
> http://www.itk.org/Doxygen/html/classitk_1_1Statistics_1_1KdTreeGenerator.html
>
> is used in the KdTree example:
>
> http://www.itk.org/Doxygen/html/Statistics_2KdTree_8cxx-example.html
>
> I hope this gives  you some additional insights.
>
> Brad
>
> 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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20130809/eba25ad7/attachment.htm>