2D point cloud registration success probability

Question

I am trying to implement localisation by storing images from a camera and their accompanying point clouds from a 2D lidar during mapping. During localisation I then use image matching to suggest the closest image and perform ICP on the point cloud to find the relative pose to where the original image was taken. My problem is that the best matching image is not always correct so I want to use the top say 5 images and see which one's point cloud aligns the best and if any of the alignments are any good at all. Unfortunately I have not been able to find any way of evaluating how good a point cloud registration is. Currently I am using the LibPointMatcher library and the best that it can provide is a residual error after alignment but some rough testing seems to suggest that this does not really help to determine if an alignment failed or not and does not seem to help with comparing the relative quality of different alignments either.

It is my understanding that there are algorithms such as Monte Carlo localisation/particle filter that can localise quite well using just 2D lidar scans. From my understanding of how they work they, they need to rank how likely each particle is after obtaining a lidar scan based on how well the current scan aligns with what would be expected given said particle's pose and the current map. Now obviously I am not actually building a point cloud map from which I am then calculating the expected points from each particle, but I think that my approach still amounts to something similar in that I also need to rank how likely it is that the current point cloud correlates with what was expected. Unfortunately, I have not been able to figure out how these Monte Carlo systems derive such an alignment probability.

Any suggestions on how I can rank the relative success of 2D point clouds registrations and preferably also identify alignments that were complete failures would be greatly appreciated.

Answer 1

Matching point clouds can be very tricky. It is kind of a needle-in-a-haystack type of problem when you don't have an initial guess at the correspondence. As you found, if the point clouds are very different there really isn't a great way to quantify the similarity. This holds even if the two scans are similar (or even the same!) but have very different orientations.

Algorithms like Iterative Closest Point (ICP) (which LibPointMatcher uses) requires the two point clouds to be closely aligned to begin with. Only then can it find the correspondence between the two and also produce a reasonable residual.

Particle filter localization with 2D lidar scans works quite well because you are simply matching one scan with the next in time so they are very similar to begin with. The robot hasn't moved very much between scans, and you have other sensors like wheel odometry and an Inertial Measurement Unit (IMU) so you have a good guess for the alignment. Furthermore, particle filters use a large population of points surrounding the hypothesized new location of the robot. Each point has its own translation and rotation from the original point, and does its own scan matching to determine a score.

I don't think a particle filter will work for you in this situation, but you can use some of its methods. If you have two different scans and no prior knowledge of the correspondence between them, you will need to try many different random translations and rotations. I can't say how many, that is entirely dependent on your application, time constraints, etc. But hopefully you will have some heuristics to be able to narrow the search space.