The problem is considered of matching two sets of points in \(R^n\), by translation and rotation. There are many applications, for example in geodesy, computer vision and in the assessment of manufactured parts. When the matching criterion is least squares, there is a well known solution process based on the singular value decomposition of an \(n \times n\) matrix. Here we consider the use of the \(l_1\) norm, which may be more appropriate than least squares in the context of wild points in the data. An algorithm is developed, and is illustrated by some examples for the case \(n=3\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
H. Chui and A. Rangarajan, A new algorithm for non-rigid point matching, IEEE Conference on Computer Vision and Pattern Recognition (CVPR) II (2000) 44–51.
G.H. Golub and C.F. Van Loan, Matrix Computations (Johns Hopkins University Press, 1989).
R.J. Hanson and M.J. Norris, Analysis of measurements based on the Singular Value Decomposition, SIAM J Sci. Stat. Comp. 2 (1981) 363–373.
W. Murray and M.L. Overton, A projected Lagrangian algorithm for nonlinear \(l_1\) optimization, SIAMJ. Sci. Stat. Comp. 2 (1981) 207–214.
H. Späth, Identifying spatial point sets, Math. Comm. 8 (2003) 69–75.
H. Späth, A numerical method for determining the spatial HELMERT transformation in the case of different scale factors, Z. Vermess.wes. 129 (2004) 255–257.
H. Späth, Fitting affine and orthogonal transformations between two sets of points, Math. Comm. 9 (2004) 27–34.
G.A. Watson, Approximation Theory and Numerical Methods (Wiley, Chichester 1980).
G.A. Watson, An approximation problem in the analysis of measurements, in Approximation Theory VIII, Vol. 1: Approximation and Interpolation, eds. C.K. Chui and L.L. Schumaker (World Scientific, Singapore, 1995).
G.A. Watson, On the Gauss–Newton method for \(l_1\) orthogonal distance regression, IMA J. Num. Anal. 22 (2002) 345–357.
D. Zwick, A planar minimax algorithm for analysis of co-ordinate measurements, Adv. Comput. Math. 2 (1994) 375–391.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Al-Subaihi, I., Watson, G.A. An algorithm for matching point sets using the \(l_1\) norm. Numer Algor 41, 203–217 (2006). https://doi.org/10.1007/s11075-005-9004-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-005-9004-4