[Fwd: Re: [Insight-users] point cloud registration]

Fri Jul 29 14:25:33 EDT 2005

Hi Dennis,

There are a great amount of papers
that address the registration problem
for points clouds-points clouds or
points clouds-triangle mesh (or surface)
registration. Only make a googling search
by "3d range image registration" or simply
take the Bels and Mckay's proposal (1992).

With respect to your questions:

1.- For points clouds-triangle mesh registration,
the only thing you need is to compute the distance
from a particular point-matching. It can be done
as suggested Luis by using a distance map or
computing the distance from a given point of the
cloud to the surface (I don't know if ITK can
perform it)

2.- For points clouds-points clouds registration,
you can compute the closest point task by means
a Distance map or with a spacial index structure
as the kd-tree.

The main thing that you should take into account
when working with ICP methods is that there are
some drawbacks which it fall in local minima or
achieves bad results:

1.- One of both images (point clouds, surfaces,
etc.) must be a subset of the other.

2.- It can not operate with non normally
distributed observations, as occurs in your
points clouds-points clouds instance.

Regards.

Jose.

Luis Ibanez
>
> Hi Dennis,
>
> I would suggest you to use only the points
> from the triangular mesh, unless the triangles
> are very large compared to the density of points
> in the other set.
>
> If the density of points in the other set is
> higher then you may want to apply subdivision
> on the triangular mesh in order to bring both
> meshes to similar densities.
>
> In practice, it all depends on the shape of
> the triangular mesh and the point cloud.
> If they have fairly characteristic shapes,
> you may be able to register them using ICP
> despite the difference in point density.
>
>
> If you really really really want to use the
> mesh information, you can first rasterize
> the mesh (assuming that it is a closed surface),
> and compute the signed distance to the binary
> mask that results from the rasterization.
> Then you use that Distance map and the point
> cloud as the two datasets to be registered.
>
>
>    Regards,
>
>
>       Luis
>
>
>
> ---------------------
> Dennis Wenzel wrote:
>> Hello Luis,
>>
>> But to answer the first two questions...
>>
>> Can I use ITK to register a triangle mesh and an arbitrary set of
>> points?
>>
>> Will the ICP algorithm work for two points sets of the same surface in
>> which there is no implied correspondence between points in the two sets?
>>
>> Thanks...
>>
>> Dennis
>>
>> ----- Original Message ----- From: "Luis Ibanez"
>> <luis.ibanez at kitware.com>
>> To: <wenzeld at att.net>
>> Cc: <insight-users at itk.org>
>> Sent: Wednesday, July 27, 2005 9:43 AM
>> Subject: Re: [Insight-users] point cloud registration
>>
>>
>>>
>>> Hi Wenzeld,
>>>
>>> You may want to read the description of this
>>> problem in the ITK Software Guide
>>>
>>>    http://www.itk.org/ItkSoftwareGuide.pdf
>>>
>>>
>>> That describes the ICP examples in Examples/Patented.
>>>
>>> ICP is the method that you may want to use in this case.
>>>
>>>
>>> You are right in your observation that the examples in
>>> this directory do not use any of the classes in the main
>>> Patented directory. The reason is that thanks to the
>>> modularity of the ITK Registration Framework, you can
>>> "build" ICP by putting together ITK components.
>>>
>>>
>>> In practice,
>>> the recipe for "ICP" includes the
>>> following ingredients:
>>>
>>>   1) Sum of Squared Distances Metric
>>>   2) An optimizer (usually Levenberg-Marquardt)
>>>   3) A search for nearest points
>>>
>>> Option (3) can be solved implicity with the help of
>>> a distance map, as illustrated in the examples of
>>> the ITK Software Guide.
>>>
>>> The "issue" with the ICP examples is that they are using
>>> fairly common algorithmic compontes as the ones listed
>>> above. Individually, they are not patented (as far as we
>>> know), but when you put them together in the particular
>>> combination described in the examples then you have an
>>> equivalent to ICP.
>>>
>>> This is just another instance of how shamefully the
>>> intellectual property system obstructs the advancement
>>> of science and technology in the foolish quest for
>>> individual profit, most of the time at the expense of
>>> ideas that are... not that bright.
>>>
>>> The US patent office awards patents for "human genes",
>>> as well as for the "peanut-butter and jelly sandwich".
>>>
>>> You will find an intersting discussion on intellectual
>>> property in the book:
>>>
>>> "The Future of Ideas" by Lawrence Lessig
>>> http://www.amazon.com/exec/obidos/tg/detail/-/0375726446/qid=1122475215/sr=8-1/ref=pd_bbs_sbs_1/104-7198053-7029550?v=glance&s=books&n=507846
>>>
>>>
>>>
>>> BTW, The patent for ICP is held by General Motors.
>>>
>>>
>>>
>>> Regards,
>>>
>>>
>>>   Luis
>>>
>>>
>>> ------------------------
>>> wenzeld at att.net wrote:
>>>
>>>> I am a little familiar with ITK.  I am curious about if, and how, the
>>>> following can be done using ITK.  (I can read the documentation to
>>>> understand the details; I just need to know if it is possible and
>>>> generally which class(es) to use.)
>>>>
>>>> 1. I have a triangle mesh surface (not closed) and a 3D point cloud
>>>> of points.  The cloud of points is acquired by a human using an
>>>> arbitrary traversal across the surface using a Microscribe
>>>> digitizer.  How can the 3D point cloud be registered to the triangle
>>>> mesh surface?  I only need to register using rotations, translations,
>>>> and scale.
>>>>
>>>> 2. In another scenario, I have two 3D point clouds (and no triangle
>>>> mesh surface) which I need to register to each other.  These point
>>>> clouds are acquired at separate points in time (e.g., days apart) and
>>>> perhaps even by seperate humans using the digitizer which means their
>>>> scanning patterns may be different.  So, there is no correspondence
>>>> between points, at least in the order in which they were digitized.
>>>> Is the ICP (iterative closest point) algorithm appropriate for this
>>>> pointset-to-pointset registration?  If not, does one of the point
>>>> sets have to be converted into a triangle mesh (if so, how is that
>>>> done)?
>>>>
>>>> 3. If the ICP algorithm is to be used in response to issue number 2
>>>> above, then how is the fact that the ICP example in the
>>>> "examples/patented" folder need to be addressed?  I did not see that
>>>> any of the classes in the "code/patented" folder were being used by
>>>> this example.  So, what issues, if any, are there in using this
>>>> algorithm?
>>>>
>>>> Thanks...
>>>>
>>>> Dennis Wenzel
>>>> _______________________________________________
>>>> Insight-users mailing list
>>>> Insight-users at itk.org
>>>> http://www.itk.org/mailman/listinfo/insight-users
>>>>
>>>>
>>>
>>
>>
>>
>
> _______________________________________________
> Insight-users mailing list
> Insight-users at itk.org
> http://www.itk.org/mailman/listinfo/insight-users
>