Can the ICP iteration be stopped once convergence is achieved?

[Jiaxin-lim]

Hi,

Since the convergence of data is reached before 5 iteration, can it be stopped to improved to computational time since the data had already been converge. If so, how do you suggest in doing this?

[niosus]

Hello @Jiaxin-lim
This is generally a good question and the answer is not that easy. Basically, yes, you would want to stop the iterations when ICP converges and in simple cases, you can just put a very small threshold on the objective function or the transformation values. In practice, however this is not trivial:

1. The main problem is to decide "what is small enough". This depends on the application and your function. I believe, usually, people add a threshold on transformation values and if these don't change, they believe that ICP has converged.
2. When using smth like KD-tree to speed up the search for the correspondences, these become non-deterministic, as such a search does not guarantee to always give the exact same result. This kills the convergence guarantee of the ICP algorithm, making it essentially never completely stop the iterations.

[Jiaxin-lim]

Hi Sir,
I understand on setting a threshold to stop the iteration after convergence has been achieved based on the threshold. However, i am not too sure where it should be added in the algorithm. You mentioned setting it at the transformation values (i assume that it is the rotation and translation) but how do i go about doing it as i am relatively new to the whole programming and ICP.

Also for (2), if a threshold is set, won't the iteration be stopped even with the implementation of KD-tree?

If you don't mind, can i have your contact where we can discuss more and seek your help in this matter? it would be a great help for my research! Thank you.

[magicbycalvin]

@Jiaxin-lim

Assuming you're talking about the icp.ipynb file, the different ICP functions all have a for loop which iterates over the desired number of iterations. If I were to include a stopping condition, I would insert it at the end of the for loop and break out of the loop if the stopping criteria are met. However, as stated above, determining a good stopping condition is not trivial. In fact, stopping conditions for many different types of optimization methods remain to be an open area of research.

A really simple stopping condition would be to save the previous chi value and compare the current value to it. If the current value decreases by less than some threshold, stop, i.e.,

if last_chi - chi < threshold: break # stopping criterion met.

Of course, many other methods exist as well. For example, you could take the average of the previous chi values in order to compensate for possible noise. Or you could require that the chi value doesn't decrease below a certain threshold for several iterations before deciding to break. You can also design other metrics such as the cross-covariance shown in the SVD example and use the above techniques to pick when to stop.

Depending on what your goal is, picking a good stopping condition may be absolutely vital or it may give negligible results. As it is a part of your research, I would recommend reading at least a paper or two on the subject to help you better understand the mechanisms at play and to see what techniques exist.

[niosus]

@magicbycalvin thanks for answering the question for me! 👍 A really-really good answer, I wouldn't put it better myself (probably slightly worse realistically speaking 😆)