There is a lot of literature on this field, also some source code, but I did not find a systematic comparison of the different methods with source included, for later usage in own implementations. What does it mean to "align" (register, stitch) point clouds? The ICP algorithm is used to align (stitch, register) point clouds taken from different angles to a single 3D point cloud. In 2D this problem is well known and solved, lots of programs can "stitch" photos taken from different angles together to form a panorama photo.īrief description of the Iterative Closest Point method It means to match one 2D or 3D point cloud (source cloud) into another (target cloud). This is efficiently done by a “k-d tree” search algorithmĬalculate a transformation (combination of rotation, translation and scaling) Problem Statement: Match one point cloud (source) into another one (target):įor each point in the source point cloud, find the closest point in the target point cloud. This is done by minimizing a mean squared error cost function, as described in references. an eigenvalue system or using quaternion maths, which is on the level of higher college math. Transform the source points using the obtained transformation. Check if the clouds match on a desired threshold.Mathematical background of the different ICP methods discussed There are lots of different ICP methods implemented in hundreds of publications. The difference between them can be categorized regarding the 4 steps of the ICP methods (see the 4 points in "Brief Description of the ICP method").ġ. Different algorithms for finding the point correspondance between source and target. If one assumes that there are N points in the source and N points in the target cloud, a "brute force" method requires N*N operations, which is very slow. A k-d tree does this work in (N ln N) operations. There are also Octree or other variants, with basically the same speed.Ģ. Different way of calculating the transformation between two point cloudsįor rigid (translation, rotation) and affine (scaling) transformations, most methods use the mathematically driven solution, since the affine transformations has a mathematically closed solution. a method using orthonormal matrices methods see a SVD (Singular Value Decomposition) method used first proposed in, used also in and and This has been proven ( in the article of reference ) to be basically equivalent to others methods like: probabilistic methods (like Monte Carlo).įor the rotation and translation, the original ICP article of Horn proposes a quaternion method. There is however a difference regarding scale transformations. The original ICP method from 1987 did not include scale transformations, but Horn added this in his publication from 1988. In real world the scale transformations is important, just imagine that you have a point cloud from one angle, then move towards the target to take the second point cloud. In the code I implemented, there are four different methods to include scaling This is basically a scale transformation.Ī somewhat comprehensible discussion of scale transformations is done in and.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |