search

richardos / icp

A Python implementation of the Iterative Closest Point algorithm
MIT License
105 stars 11 forks source link

Help: How do you determine the distance threshold and point pairs! #2

Open Jiaxin-lim opened 3 years ago

Jiaxin-lim commented 3 years ago

Hi, i hope you can help me understand this better.

How do you determine the how much values the distance threshold and point pairs should be?

I had tried running it with 2 different distance threshold, 20 and 40. For 2 point clouds that only differs in rotation and translation, i am able to get a acceptable convergence (see below).

image

However, when i were to use point clouds that has a different size, rotation and translation the ICP convergence is unacceptable for a distance threshold of 40 compared to distance threshold of 20.

Distance Threshold - 20 image

Distance Threshold - 40 image

richardos commented 3 years ago

I may not answer this question very accurately, because I haven't touched this subject for a very long time. At first, there can be no rule for the thresholds determination, as they depend on the specific problem, e.g. how far your point clouds could be from each other at their initial position (related to distance_threshold), the total number of points each point cloud has or expected to have (related to point_pairs_threshold), the unit of distance, etc.

Nevertheless, this version of the algorithm cannot work very accurately when the two point clouds differ a lot in terms of scaling. For point clouds that only differ in rotation and translation the algorithm can easier converge to the global minimum (the initial position plays important role of course). This is not the case when we have size differences, where the algorithm may converge to a local minimum and the quality of the result will depend not only on the threshold parameters but also on the initial position of the points.

In general, you can try to introduce some techniques that will escape local minima and try to converge to the global one, like simulated annealing for example.

Jiaxin-lim commented 3 years ago

Hi @richardos

Could you kindly help me understand better on the points_pairs_threshold? As i am playing around with this threshold along with distance_threshold. I found that the point cloud can still be merged together as long as there is a single pair found (I'd set point_pairs_threshold=0) based on the distance_threshold. So how do you actually determine how many points pair i should have in my structure to determine it will be a robust/good convergence?

Thank you.

richardos commented 3 years ago

As I wrote above, I don't think that there is any rule for this. Nevertheless, if you make some experiments you may come up with a heuristic formula that will most probably depend on the number of points and the expected initial divergence between your point clouds.