# How does scan matching find overlapping regions in two scans?

I have been reading about scan matching and so far I have gathered that scan matching tries to find the transformation (rotation and translation) which leads to the best match between overlapping points of the two scans. My question is : what algorithms does it use to find the overlapping regions ? Any explanations or links to relevant papers are greatly appreciated.

The process you are referring to is called point cloud registration (or point matching). The goal of point cloud registration is find the spatial transformation that aligns two point clouds (i.e., sets of points). One of the most popular methods is iterative closest point (ICP), and many variants of ICP exist. Other methods exist as well such as robust point matching (RPM) and variants, but I am not familiar with RPM.

The basic ICP algorithm essentially works by matching closest points and minimizing the error between point matches to find the rotation and translation between point clouds. The process is then repeated after transforming the original point cloud.

Methods for ICP are provided in the Point Cloud Library (PCL), which is open source software for point cloud processing. Other software also includes implementation e.g., MATLAB, libpointmatcher. If you are interested in the theory, you can see the original ICP paper:

P. Besl, N. McKay "Method for Registration of 3-D Shapes" in IEEE Transactions of Pattern Analysis and Machine Intelligence, 1992.

• Thank you so much for the answer. Is the identification of which points to match also a part of ICP ? From your answer I realize that ICP finds the required transformation for the best match but does it identify the candidate points as well ? Jan 15 '20 at 18:46
• Yes. In ICP, the closest points are matched. So, p_i in cloud_1 is matched with p_j in cloud_2 where ||p_i-p_j|| is minimized. This seems odd, but the algorithm must be initialized in some way. As the algorithm iterates, the matches will change because the original point cloud is transformed in the final step. Jan 15 '20 at 19:03
• Thanks again. My question is how does it know p_i has to be matched with p_j and not some p_k in cloud_2. I understand that an initial guess has to be supplied to the optimization that ICP performs. Jan 15 '20 at 20:09
• I was answering that question. To find the correspondence of a point in cloud_1, you find the closest point to it in cloud_2. The correspondences will be very wrong to start with but after iterating more will become correct. Jan 15 '20 at 20:35
• Thanks for the clarification. Finally got it. It seems like that it tries to do this for every point in the point cloud. What if the point clouds have different number of points or do not overlap fully i.e. only a part of the scene overlaps ? Jan 15 '20 at 22:22