[Insight-developers] ICP patent thoughts

[Miller, James V (Research)]

Minimizing the Sum of distance^4 is HIGHLY non-robust.  The effect will be
that the points with the highest mismatch will dominate the metric. So the
alignment is will be largely based on the most mismatched point as opposed 
to the "average match" of the closest matched points. You basically are 
losing the statistical efficiency of the closest matched points.

The whole motivation of robust loss functions (and robust statistics) is to 
drop the influence of the highest mismatches (residuals).  For instance,
some 
robust loss functions start out quadratic then transition to linear just to 
slow down the influence of the largest residuals. Some robust functions,
clamp
the large residuals so part a certain residual value, all residuals have the

same penalty.

I wouldn't worry about the speed penalty of the sqrt. I'd be in favor of
switching the default. I'll take robustness over speed.  When comparing
points
the square of the distances can be used, but I would sqrt the values before
putting them in the vector.

Again, when a distance map is not being used, a spatial search structure
will
speed up the distance measurements much more than an extra sqrt will slow
them
down.

Jim





-----Original Message-----
From: Luis Ibanez [mailto:luis.ibanez at kitware.com]
Sent: Monday, October 04, 2004 11:39 AM
To: Miller, James V (Research)
Cc: Insight-developers (E-mail)
Subject: Re: [Insight-developers] ICP patent thoughts



I agree with your suggestion of using a more robust measure
for the points. In fact, that will result in an improvement
for the performance of the algorithm, since during the initial
iterations of ICP, almost all the correspondances are wrong.
Meaning that the closest point *are not* the appropriate corres-
ponding points, at least not at the beginning of a typical
registration.

Using something like the mean distance from the K closest points
could be as arbirarly good as using the distance to the closest
point.

Just for the record, The current metric is (by default) returning a
*vector* with the *squares* of the distances between the points. 
Technically, this is like minimizing the Sum of distances^4 between
the points. Julien did this in order to speed up the metric computation
since it avoids the sqrt() computation. The flag "ComputeSquareDistance"
forces the Metric to compute a vector of Euclidean distances.


   Luis


-------------------
Miller, James V (Research) wrote:

> I thought about this further this weekend. I am really starting to like 
> the "bullets" and "gun" analogy. 
>  
> Iterative closest point is implemented in ITK as a metric.  All this 
> metric does is return a vector of the distances between the points in 
> the moving set to the fixed set. There is actually nothing "iterative" 
> about the metric.  It merely measures a set of distances and returns a 
> vector of distances (one distance for each point in the moving set). 
> This class
> could be renamed "ClosestPointMetric" to make this even clearer.
>  
> (By the way, if a distance map is not being used, the metric should 
> use some sort of spatial search data structure (grids, kd-trees, etc.)  
> as opposed to a linear search of the container.)
>  
> The output from the ClosestPointMetric can be used for a variety of 
> algorithms.  ICP is one. Collision detection for a surgical application 
> is another. So I think the metric is more general than ICP.
>  
> This being said, the examples/tests that put all the pieces together to 
> form an ICP algorithm may have to be modified.  This all hinges on the 
> interpretation of what if covered by the patent. The ICP examples/tests 
> may have to be moved into a patented directory. They may have to be 
> removed if we cannot obtain the appropriate permissions.
>  
> Again, we may be able to avoid almost all the issues with ICP, if the 
> ClosestPointMetric did not return euclidean distances but instead return 
> weighted euclidean distances using some robust weight function.
>  
>  
> 
> *Jim Miller*
> */_____________________________________/*
> /Visualization & Computer Vision//
> /GE Research/
> /Bldg. KW, Room C218B/
> /P.O. Box 8, Schenectady NY 12301/
> 
> //_millerjv at research.ge.com <mailto:millerjv at research.ge.com>_/
> 
> /_james.miller at research.ge.com_/
> /(518) 387-4005, Dial Comm: 8*833-4005, /
> /Cell: (518) 505-7065, Fax: (518) 387-6981/
> 
>  
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Insight-developers mailing list
> Insight-developers at itk.org
> http://www.itk.org/mailman/listinfo/insight-developers