CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Least squares rigid body fitting of point-sets with unknown correspondences

Tapani Utriainen (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Göteborg : Chalmers University of Technology, 2010. ISBN: 978-91-7385-410-8.- 129 s.

The problem addressed here is: given points u_1,...,u_n and v_1,...,v_n, find a translation t, a rotation R, a scale factor s, and an one-to-one correspondence pi(), that minimize the least squares error: error = min_{t,R,s,pi} \sum_{i=1}^n ||s R u_i - v_{pi(i)} + t||_2^2 When the point-to-point correspondences are not known beforehand, and are to be determined as a part of the problem, no polynomial time algorithm with a performance guarantee has been described in the literature. This thesis proves that near-optimal solutions can be calculated in polynomial time for both two- and three-dimensional point-sets. In two dimensions this is done by transforming the problem to a vector-weighted bipartite matching problem (VWBM), and devising fully polynomial time approximation schemes (FPTAS) for it. It is discussed why an approximation scheme for a VWBM is not necessarily an approximation scheme for the two-dimensional point-matching problem. It is demonstrated that a global optimum for the two-dimensional problem can be computed in practice. In three dimensions, the problem of least squares fitting point-sets is transformed to an eigenvalue maximization problem. An FPTAS is presented for the eigenvalue maximization problem, but similiarily to the two-dimensional case, that FPTAS is not necessarily one for the 3-D point-matching problem. Further, it is demonstrated that the presented algorithms are able to calculate near-optimal solutions in practice.

Denna post skapades 2010-05-16. Senast ändrad 2013-09-25.
CPL Pubid: 121598