[Insight-users] ICP complexity

[Luis Ibanez]

Hi Felix,

Good point,

I should have specified that the order estimation was for
a single iteration only.

It is hard to anticipate how many iterations will be needed
for an ICP registration.

The number of iterations needed will depend on factors such as

   * The spatial configuration of points inside every set
   * The separation and relative orientation of both sets
   * The optimizer used and the setting of optimizer parameters


That being said,
Just to give an example,

The 2D example in

    Insight/Examples/Patented/IterativeClosestPoint1

when run with the files in Insight/Examples/Data:

IterativeClosestPoint1.exe
       IterativeClosestPointFixedPoints.txt
       IterativeClosestPointMovingPoints.txt

runs to convergence in 60 iterations.

while the 3D example

     Insight/Examples/Patented/IterativeClosestPoint2

when run as

IterativeClosestPoint2.exe
       IterativeClosestPointFixedPoints2.txt
       IterativeClosestPointMovingPoints2.txt

runs to convergence in about  2000 iterations.



     Regards,


        Luis



----------------------------------
bollen at ipk-gatersleben.de wrote:
> Hi Luis,
> 
> Yes, that sounds plausible, thanks for your remarks, I actually 
> considered reducing surface vertices with energy based remeshing.
> 
> But:
> 
> ICP as far as I understood ICP, a) and b) are iterated until 
> convercence, right? Do you have any notion how many iterations are to be 
> expected here?
> 
> Best Regards,
> 
> Felix.
> 
> 
> 
> Quoting Luis Ibanez <luis.ibanez at kitware.com>:
> 
>>
>> Hi Felix,
>>
>> The computation time should be in the order
>>
>> a) O(N*M) : For the section that search for nearest point
>>
>>                and
>>
>> b) O(N) for the section that computes the actual metric value
>>
>>
>>
>> Where
>>
>> N = number of points in the Fixed Point Set
>> M = number of points in the Moving Point Set
>>
>>
>> BTW: please not that ICP is not expected to be
>>      a symmetrical problem. Therefore, although
>>      selecting the set of points with the least
>>      number of points as the Fixed Point Set
>>      may give you faster computation, it may
>>      not necessarily give you the best registration.
>>
>>
>>    Regards,
>>
>>
>>       Luis
>>
>>
>> ----------------------
>> Felix Bollenbeck wrote:
>>
>>> Dear ITK User,
>>>
>>> I am currently working o a problem, involving a 3D correspondence 
>>> problem identical to the ICP setting.
>>>
>>> For further directions I have question regarding the complexity of 
>>> the (ITK) ICP algorithm:
>>>
>>> How does the computation time relate to the number of points roughly?
>>>
>>> Regards,
>>>
>>> Felix Bollenbeck.
>>>
>>
>>
> 
> 
> 
>