=Paper= {{Paper |id=Vol-1710/paper35 |storemode=property |title=The Iterative Closest Points Algorithm and Affine Transformations |pdfUrl=https://ceur-ws.org/Vol-1710/paper35.pdf |volume=Vol-1710 |authors=Dmitrii Tihonkih,Artyom Makovetskii,Vladislav Kuznetsov |dblpUrl=https://dblp.org/rec/conf/aist/TihonkihMK16 }} ==The Iterative Closest Points Algorithm and Affine Transformations== https://ceur-ws.org/Vol-1710/paper35.pdf 
The Iterative Closest Points Algorithm and Affine Transformations

           Dmitrii Tihonkih1, Artyom Makovetskii1 and Vladislav Kuznetsov1
                   1
                       Chelyabinsk State University, Chelyabinsk, Russia

       sparsemind@gmail.com, artemmac@mail.ru, k.v.net@rambler.ru



Abstract. The problem of consistent aligning of 3D point data is known registration
task. The most popular registration algorithm is the Iterative Closest Point (ICP) algo-
rithm. One of the main steps of the ICP algorithm is matching. We find a matching in
at first time on the basis of the geometric similarity of individual groups of points. It
allows to get a good first approximation of the required transformation, even for big
angle rotations, translations, scaling and noisy data. The step of the error minimiza-
tion is performed for an arbitrary affine transformation.

Keywords: Iterative closest points (ICP), surface reconstruction, matching, error
minimization


1       Introduction
   The ICP (Iterative Closest Point) algorithm has become the dominant method for
aligning three dimensional models based purely on the geometry. The algorithm is
widely used for registering the outputs of 3D scanners, which typically only scan an
object from one direction at a time. The standard ICP starts with two point clouds and
an initial guess for their relative rigid-body transform, and iteratively refines the trans-
form by repeatedly generating pairs of corresponding points in the clouds and mini-
mizing an error metric. Generating the initial alignment may be done by a variety of
methods, such as tracking scanner position, identification and indexing of surface
features [1, 2], β€œspin-image” surface signatures [3], computing principal axes of scans
[4], exhaustive search for corresponding points [5, 6], or user input. In this paper, we
assume that a rough initial alignment is always available. In addition, we focus only
on aligning a single pair of clouds, and do not address the global registration problem
[7, 8, 9, 10]. Since the introduction of ICP by Chen and Medioni [11] and Besl and
McKay [12], many variants have been introduced on the basic ICP concept. We may
classify these variants as affecting one of six stages of the algorithm:

    1. Selection of some set of points in one or both clouds.
    2. Matching these points to samples in the other cloud.
    3. Weighting the corresponding pairs appropriately.
   4. Rejecting certain pairs based on looking at each pair individually or considering
the entire set of pairs.
  5. Assigning an error metric based on the point pairs.
  6. Minimizing the error metric (variational subproblem of the ICP).

   In this paper, we will look at variants for the categories 2 and 6. Our main focus is
on the accuracy of the final answer and the ability of ICP to reach the correct solution
for a difficult geometry. We consider affine transformation in ℝ! that holds the angles
between lines in the cloud of points. An algorithm of matching is inspirited by the
recent results of neurophysiology of vision [13]. Also we consider the ICP minimiz-
ing the error metric subproblem for the case of an arbitrary affine transformation. The
computer simulation section contains results of computational experiments based on
our matching and error minimizing approaches.


2       The matching procedure for sets 𝐗 and 𝐘

  Let 𝑋 = {π‘₯! , … , π‘₯!!! } be an set consist of π‘˜ points in ℝ! and π‘Œ = {𝑦! , … , 𝑦!!! }
be an set consist of 𝑛 points in ℝ! . Here we describe our approach for searching the
matching between 𝑋 and π‘Œ. Denote by (π‘₯! , 𝑦! ), π‘₯! ∈ 𝑋, 𝑦! ∈ π‘Œ the pair of correspond-
ing points. The goal of our procedure is representation of points from 𝑋 and π‘Œ as sets
of pairs. The first element of a pair belongs to 𝑋, the second element belongs to π‘Œ.
Note, that each point from 𝑋 and π‘Œ can be included to the set of pairs just one time.
At the beginning the set of pairs is empty. Let π‘š ∈ β„• be a number such that:

                                         3 ≀ π‘š ≀ min (𝑛, π‘˜).                        (1)

    Denote by 𝑖 a natural parameter.

    1. Consider the following subset 𝑋! of the 𝑋:

                               𝑋! = {π‘₯!βˆ— !!! , … , π‘₯!βˆ— !!! !!!! }.                   (2)

   2. Let 𝐢 be a closed piecewise linear curve in ℝ! that consist of π‘š line segments.
The 𝑗-th segment connects points π‘₯!βˆ— !!! !! and π‘₯!βˆ— !!! !!!! . If 𝑗 + 1 = π‘š then we
take index π‘š βˆ— 𝑖 βˆ’ 1 instead π‘š βˆ— 𝑖 βˆ’ 1 + 𝑗 + 1. Denote by 𝛼! a minimal flat angle
that is constructed by 𝑗-th and (𝑗 + 1)-th segments (with the similar agreement for the
case 𝑗 + 1 = π‘š). Let 𝑉! be a vector

                                       𝑉! = {𝛼! , … , 𝛼!!! },                       (3)

where elements Ξ±! , j = 0, … , m βˆ’ 1 are respective angles.

  3. Consider all possible combinations of m points in the set Y besides the points
that already included to the set of pairs. For an each combination we construct the
vector 𝑉 by the same way as in step 2.
  4. We choose a vector from the set of vectors of the step 3 such that distance be-
tween them and 𝑉! is minimal relatively the norm 𝐿! . Denote this vector as 𝑉! .
  5. We construct π‘š pairs of the points from 𝑉! and 𝑉! . Add this m pairs to the set of
pairs.
  6. If the number of remaining points in 𝑋 or π‘Œ less that π‘š then procedure termi-
nates. Else 𝑖 ≔ 𝑖 + 1 and go to step 1.

   We use this procedure only as first iteration on the ICP algorithm. Obtained after
the first iteration the transformation matrix and the translation vector are used for a
second iteration. In the next iterations we use the standard nearest neighbor approach
to find a match between the points.
   In the practical using of the ICP algorithm very often a set π‘Œ obtained from a set 𝑋
by a some geometrical transformation. The described above approach can good work
not for rigid transformation only but for sufficiently wide subset of the affine trans-
formations.


3       The ICP variational subproblem for an arbitrary affine
        transformation

   Let 𝑋 = {π‘₯! , … , π‘₯!!! } be a source point cloud and π‘Œ = {𝑦! , … , 𝑦!!! } be a destina-
tion point cloud in ℝ! . Suppose that the relationship between points in 𝑋 and π‘Œ is
done by such a way that for each point π‘₯! is calculated corresponding point 𝑦! . In
many works [11, 12, 14] the ICP algorithm is considered as a geometrical transfor-
mation for rigid objects mapping 𝑋 to π‘Œ:
                                          𝑅π‘₯! + 𝑑,                                    (4)

where 𝑅 is a rotation matrix, 𝑇 is a translation vector, 𝑖 = 0, … , 𝑛 βˆ’ 1. The S-ICP
algorithm [14] is a slightly different geometrical transformation given by

                                       𝑅𝑆π‘₯! + 𝑑,                                      (5)

where 𝑆 is a scaling matrix.
   The group 𝐸(3) of affine transformations in the dimension three has 12 generators.
It means that affine transformation in dimension three is a function of 12 variables.
Let us consider ICP variational problem for the case of an arbitrary affine transfor-
mation. Let 𝐽(𝐴, 𝑇) be the following function:
                                         !!!
                             𝐽 𝐴, 𝑇 =    !!! βˆ₯   𝐴 π‘₯! + 𝑑 βˆ’ 𝑦! βˆ₯! .                   (6)

    The ICP variational problem can be stated as follows:

                                     arg π‘šπ‘–π‘› 𝐽 𝐴, 𝑑 ,                                 (7)
                                     A,t
where
            π‘Ž!!       π‘Ž!"   π‘Ž!"       𝑑!        π‘₯!!        𝑦!!
        𝐴 = π‘Ž!"       π‘Ž!!   π‘Ž!" , 𝑑 = 𝑑! , π‘₯! = π‘₯!! , 𝑦! = 𝑦!! .                         (8)
            π‘Ž!"       π‘Ž!"   π‘Ž!!       𝑑!        π‘₯!!        𝑦!!

  One can be seen that

           !!!
𝐽 𝐴, 𝑑 =   !!!     ( π‘Ž!! π‘₯!! + π‘Ž!" π‘₯!! + π‘Ž!" π‘₯!! + 𝑑! βˆ’ 𝑦!! )! +
                 + ( π‘Ž!" π‘₯!! + π‘Ž!! π‘₯!! + π‘Ž!" π‘₯!! + 𝑑! βˆ’ 𝑦!! )! +
                 +( π‘Ž!" π‘₯!! + π‘Ž!" π‘₯!! + π‘Ž!! π‘₯!! + 𝑑! βˆ’ 𝑦!! )! .                          (9)

  Let new coordinates π‘₯!" be expressed through old coordinates π‘₯!" as follows:

                            !       !!!
              π‘₯!! = π‘₯!" βˆ’           !!! π‘₯!! , π‘˜ = 1, … ,3,          𝑖 = 1, … , 𝑛.       (10)
                            !

  Also for the points of the second cloud we can write

                                !    !!!
               𝑦!! = 𝑦!" βˆ’           !!! 𝑦!! , π‘˜ = 1, … ,3,          𝑖 = 1, … , 𝑛.      (11)
                                !

  Let us define coefficients 𝛼! , 𝛽! , 𝛾! , πœ‘! and πœ“! for 𝑖 = 1, … , 𝑛 as
                                             !!!            !!!
                         𝛼! = π‘₯!! βˆ’        ! ! !      βˆ’     !!! π‘₯!! π‘₯!! ,               (12)
                                           !!! !!

                                             !!!            !!!
                         𝛽! = π‘₯!! βˆ’        ! ! !      βˆ’     !!! π‘₯!! π‘₯!! ,               (13)
                                           !!! !!

                                            !!!           !!!
                        𝛾! = 𝑦!! βˆ’        ! ! !           !!! 𝑦!! π‘₯!! ,                 (14)
                                          !!! !!

                                              !!          !!!
                        πœ‘! = 𝛽! βˆ’          !      !       !!!       𝛽! 𝛼! ,             (15)
                                           !!! !!

                                            !!        !!!
                        πœ“! = 𝛾! βˆ’        !      !     !!!    𝛾! 𝛼! .                    (16)
                                         !!! !!


  Proposition. The elements of the first row of the matrix π΄βˆ— that minimizes 𝐽 are
computed as
                                         !!!
                                         !!! !!! ! !!" !!! ! !!" !!!          !!!
                             π‘Ž!! =                  !!! ! !                         ,   (17)
                                                    !!! !!

                                          !!!             !!!
                                          !!! !! !! !!!" !!! !! !!
                                π‘Ž!" =              !!! ! !                    ,         (18)
                                                   !!!  !


                                                !!!
                                                !!! !! !!
                                       π‘Ž!" =     !!! ! !        .                       (19)
                                                 !!!  !
   For the second and third rows of the matrix 𝐴 similar formulas can be easily de-
rived.


4       Computer simulation
   Let 𝑋 be the set consists of 80 points. The coordinates of points are randomly gen-
erated (by the uniform distribution). The values of all coordinates belong to the range
[0, . . . ,100]. The set π‘Œ is obtained from the set 𝑋 by the geometrical transformation
π‘Œ = 𝑅 βˆ— 𝑋 + 𝑑, where 𝑅 and 𝑑 are described below:

                                   0.5          0    0.866025
                            𝑅 = 0.866025        0      βˆ’0.5   ,                   (20)
                                    0           1        0


                                     𝑑T = 5     6   7 .                           (21)

    And each component of every point from the set π‘Œ is noised by the following way.

                                      𝑦!! ≔ 𝑦!! + 𝑛!! ,                           (22)

  Here 𝑛!! is uniformly distributed real number in the closed interval [0, 1], j is the
number of point, 𝑖 = {1, 2, 3}.
  Estimated using the our algorithm matrix 𝑅 and vector 𝑑:

                              0.49987          0.00001       0.86612
                       𝑅=     0.865925         0.00009      βˆ’0.500072 ,           (23)
                             βˆ’0.000027        0.999896      βˆ’0.000021


                          𝑑 T = 5.00281       6.0127      7.00388 .               (24)

   The standard approach based on nearest neighbor method implemented in the open
source library LIBICP (C++ Library for Iterative Closest Points Matching) gives the
following results:

                           0.4281353          0.0278281         0.9032861
                      𝑅 = βˆ’0.0109876          0.9996122        βˆ’0.0255878 ,       (25)
                           0.9036479          βˆ’0.0010301       βˆ’0.4282750


                      𝑑 T = βˆ’36.6521776        30.6680470       9.0428475 .       (26)



Fig. 1 shows initial sets 𝑋 and π‘Œ.
                         Fig. 1. Sets 𝑋 (yellow) and π‘Œ (blue).


Fig. 2 shows a set 𝑋 and a set π‘Œ = 𝑋 βˆ— 𝑅 + 𝑑. Where 𝑅 and 𝑑 is the result of the stand-
ard approach.




                         Fig. 2. Sets 𝑋 (yellow) and π‘Œ (blue).
Fig. 3 shows a set 𝑋 and a set π‘Œ = 𝑋 βˆ— 𝑅 + 𝑑. Where 𝑅 and 𝑑 estimated by our algo-
rithm after the first iteration.




                        Fig. 3. Sets 𝑋 (yellow) and π‘Œ (blue).




5      Conclusion
In this paper we considered matching and error minimizing steps of the ICP algo-
rithm. On the base of the obtained results, a new efficient algorithm for the sets
alignment was designed. The obtained results are illustrated with the help of computer
simulation.



Acknowledgments
The work was supported by Russian Science Foundation grant β„–15-19-10010.
References
 1. Faugeras, O. and Hebert, M., β€œThe Representation, Recognition, and Locating of 3-D Ob-
    jects,” Int. J. Robotic Res., Vol. 5, No. 3 (1986).
 2. Stein, F. and Medioni, G., β€œStructural Indexing: Efficient 3-D Object Recognition,” Trans.
    PAMI, Vol. 14, No. 2 (1992).
 3. Johnson, A. and Hebert, M., β€œSurface Registration by Matching Oriented Points,” Proc.
    3DIM (1997).
 4. Dorai, C., Weng, J. and Jain, A., β€œOptimal Registration of Object Views Using Range Da-
    ta,” Trans. PAMI, Vol. 19, No. 10 (1997).
 5. Chen, C., Hung, Y. and Cheng, J., β€œA Fast Automatic Method for Registration of Partially-
    Overlapping Range Images,” Proc. ICCV (1998).
 6. Chen, C., Hung, Y. and Cheng, J., β€œRANSAC-Based DARCES: A New Approach to Fast
    Automatic Registration of Partially Overlapping Range Images,” Trans. PAMI, Vol. 21,
    No. 11 (1999).
 7. Bergevin, R., Soucy, M., Gagnon, H. and Laurendeau, D., β€œTowards a General Multi-View
    Registration Technique,” Trans. PAMI, Vol. 18, No. 5 (1996).
 8. Stoddart, A. and Hilton, A., β€œRegistration of Multiple Point Sets,” Proc. CVPR (1996).
 9. Pulli, K., β€œSurface Reconstruction and Display from Range and Color Data,” Ph. D. Dis-
    sertation, University of Washington (1997).
10. Pulli, K., β€œMultiview Registration for Large Data Sets,” Proc. 3DIM (1999).
11. Chen, Y. and Medioni, G., β€œObject Modeling by Registration of Multiple Range Images,”
    Proc. IEEE Conf. on Robotics and Automation (1991).
12. Besl, P. and McKay, N., β€œA Method for Registration of 3-D Shapes,” Trans. PAMI, Vol.
    14, No. 2 (1992).
13. Petitot, J., β€œThe neurogeometry of pinwheels as a sub-Riemannian contact structure,” J.
    Physiology – Paris, 97, 265–309 (2003).
14. Langis, C., Greenspan, M. and Godin, G., "The parallel Iterative closest point algorithm,"
    Proc. IEEE Third International Conference 3-D Digital Imaging and Modeling, 195-204
    (2001).
15. Lowe, D. G., "Object recognition from local scale invariant features," Proc. 7th Interna-
    tional conference on Computer Vision, 2, 1150–1157 (1999).