Abstract

Finding the relationship between two coordinate systems by using pairs of measurements of the coordinates of a number of points in both systems is a classic photogrammetric task. The solution has applications in stereophotogrammetry and in robotics. We present here a closed-form solution to the least-squares problem for three or more points. Currently, various empirical, graphical, and numerical iterative methods are in use. Derivation of a closed-form solution can be simplified by using unit quaternions to represent rotation, as was shown in an earlier paper [ J. Opt. Soc. Am. A 4, 629 ( 1987)]. Since orthonormal matrices are used more widely to represent rotation, we now present a solution in which 3 × 3 matrices are used. Our method requires the computation of the square root of a symmetric matrix. We compare the new result with that obtained by an alternative method in which orthonormality is not directly enforced. In this other method a best-fit linear transformation is found, and then the nearest orthonormal matrix is chosen for the rotation. We note that the best translational offset is the difference between the centroid of the coordinates in one system and the rotated and scaled centroid of the coordinates in the other system. The best scale is equal to the ratio of the root-mean-square deviations of the coordinates in the two systems from their respective centroids. These exact results are to be preferred to approximate methods based on measurements of a few selected points.

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. C. C. Slama, C. Theurer, S. W. Henrikson, eds., Manual of Photogrammetry (American Society of Photogrammetry, Falls Church, Va., 1980).
  2. P. R. Wolf, Elements of Photogrammetry (McGraw-Hill, New York, 1974).
  3. S. K. Gosh, Theory of Stereophotogrammetry (Ohio State U. Bookstores, Columbus, Ohio, 1972).
  4. B. K. P. Horn, Robot Vision (MIT Press, Cambridge, Mass.; McGraw-Hill, New York, 1986).
  5. E. H. Thompson, “An exact linear solution of the problem of absolute orientation,” Photogrammetria 15(4), 163–179 (1958).
  6. G. H. Schut, “On exact linear equations for the computation of the rotational elements of absolute orientation,” Photogrammetria 16(1), 34–37 (1960).
  7. B. K. P. Horn, “Closed-form solution of absolute orientation using unit quaternions,”J. Opt. Soc. A 4, 629–642 (1987).
    [CrossRef]
  8. H. L. Oswal, S. Balasubramanian, “An exact solution of absolute orientation,” Photogramm. Eng. 34, 1079–1083 (1968).
  9. C. Eckart, G. Young, “The approximation of one matrix by another of lower rank,” Psychometrika 1, 211–218 (1936).
    [CrossRef]
  10. B. F. Green, “The orthogonal approximation of an oblique structure in factor analysis,” Psychometrika 1, 429–440 (1952).
    [CrossRef]
  11. W. A. Gibson, “On the least-squares orthogonalization of an oblique transformation,” Psychometrika 27, 193–195 (1962).
    [CrossRef]
  12. R. M. Johnson, “On a theorem stated by Eckart and Young,” Psychometrika 28, 259–263 (1963).
    [CrossRef]
  13. P. H. Schönemann, “A generalized solution of the orthogonal procrustes problem,” Psychometrika 31, 1–10 (1966).
    [CrossRef]
  14. N. Cliff, “Orthogonal rotation to congruence,” Psychometrika 31, 33–42 (1966).
    [CrossRef]
  15. P. H. Schönemann, Robert M. Carroll, “Fitting one matrix to another under choice of a central dilation and a rigid motion,” Psychometrika 35, 169–183 (1970).
    [CrossRef]
  16. J. L. Farrell, J. C. Stuelpnagel, “Problem 65-1: a least squares estimated of satellite attitude,”SIAM Rev. 8, 384–386 (1966).
    [CrossRef]
  17. S. Arun, T. S. Huang, S. D. Blostein, “Least-squares fitting of two 3-D point sets,” Tech. Note ISP-81 (Coordinated Science Laboratory, University of Illinois, Urbana, Ill., 1986); submitted toIEEE Trans. Patt. Anal. Machine Intell.
  18. J. H. Stuelpnagel, “On the parameterization of the three-dimensional rotation group,”SIAM Rev. 6, 422–430 (1964).
    [CrossRef]
  19. G. A. Korn, T. M. Korn, Mathematical Handbook for Scientists and Engineers (McGraw-Hill, New York, 1968).
  20. G. Birkhoff, S. MacLane, A Survey of Modern Algebra (Macmillan, New York1953).
  21. P. H. Winston, B. K. P. Horn, LISP (Addison-Wesley, Reading, Mass., 1984).
  22. P. R. Halmos, Finite Dimensional Vector Spaces, 2nd ed. (Van Nostrand, Princeton, N.J., 1958).

1987

B. K. P. Horn, “Closed-form solution of absolute orientation using unit quaternions,”J. Opt. Soc. A 4, 629–642 (1987).
[CrossRef]

1970

P. H. Schönemann, Robert M. Carroll, “Fitting one matrix to another under choice of a central dilation and a rigid motion,” Psychometrika 35, 169–183 (1970).
[CrossRef]

1968

H. L. Oswal, S. Balasubramanian, “An exact solution of absolute orientation,” Photogramm. Eng. 34, 1079–1083 (1968).

1966

P. H. Schönemann, “A generalized solution of the orthogonal procrustes problem,” Psychometrika 31, 1–10 (1966).
[CrossRef]

N. Cliff, “Orthogonal rotation to congruence,” Psychometrika 31, 33–42 (1966).
[CrossRef]

J. L. Farrell, J. C. Stuelpnagel, “Problem 65-1: a least squares estimated of satellite attitude,”SIAM Rev. 8, 384–386 (1966).
[CrossRef]

1964

J. H. Stuelpnagel, “On the parameterization of the three-dimensional rotation group,”SIAM Rev. 6, 422–430 (1964).
[CrossRef]

1963

R. M. Johnson, “On a theorem stated by Eckart and Young,” Psychometrika 28, 259–263 (1963).
[CrossRef]

1962

W. A. Gibson, “On the least-squares orthogonalization of an oblique transformation,” Psychometrika 27, 193–195 (1962).
[CrossRef]

1960

G. H. Schut, “On exact linear equations for the computation of the rotational elements of absolute orientation,” Photogrammetria 16(1), 34–37 (1960).

1958

E. H. Thompson, “An exact linear solution of the problem of absolute orientation,” Photogrammetria 15(4), 163–179 (1958).

1952

B. F. Green, “The orthogonal approximation of an oblique structure in factor analysis,” Psychometrika 1, 429–440 (1952).
[CrossRef]

1936

C. Eckart, G. Young, “The approximation of one matrix by another of lower rank,” Psychometrika 1, 211–218 (1936).
[CrossRef]

Arun, S.

S. Arun, T. S. Huang, S. D. Blostein, “Least-squares fitting of two 3-D point sets,” Tech. Note ISP-81 (Coordinated Science Laboratory, University of Illinois, Urbana, Ill., 1986); submitted toIEEE Trans. Patt. Anal. Machine Intell.

Balasubramanian, S.

H. L. Oswal, S. Balasubramanian, “An exact solution of absolute orientation,” Photogramm. Eng. 34, 1079–1083 (1968).

Birkhoff, G.

G. Birkhoff, S. MacLane, A Survey of Modern Algebra (Macmillan, New York1953).

Blostein, S. D.

S. Arun, T. S. Huang, S. D. Blostein, “Least-squares fitting of two 3-D point sets,” Tech. Note ISP-81 (Coordinated Science Laboratory, University of Illinois, Urbana, Ill., 1986); submitted toIEEE Trans. Patt. Anal. Machine Intell.

Carroll, Robert M.

P. H. Schönemann, Robert M. Carroll, “Fitting one matrix to another under choice of a central dilation and a rigid motion,” Psychometrika 35, 169–183 (1970).
[CrossRef]

Cliff, N.

N. Cliff, “Orthogonal rotation to congruence,” Psychometrika 31, 33–42 (1966).
[CrossRef]

Eckart, C.

C. Eckart, G. Young, “The approximation of one matrix by another of lower rank,” Psychometrika 1, 211–218 (1936).
[CrossRef]

Farrell, J. L.

J. L. Farrell, J. C. Stuelpnagel, “Problem 65-1: a least squares estimated of satellite attitude,”SIAM Rev. 8, 384–386 (1966).
[CrossRef]

Gibson, W. A.

W. A. Gibson, “On the least-squares orthogonalization of an oblique transformation,” Psychometrika 27, 193–195 (1962).
[CrossRef]

Gosh, S. K.

S. K. Gosh, Theory of Stereophotogrammetry (Ohio State U. Bookstores, Columbus, Ohio, 1972).

Green, B. F.

B. F. Green, “The orthogonal approximation of an oblique structure in factor analysis,” Psychometrika 1, 429–440 (1952).
[CrossRef]

Halmos, P. R.

P. R. Halmos, Finite Dimensional Vector Spaces, 2nd ed. (Van Nostrand, Princeton, N.J., 1958).

Horn, B. K. P.

B. K. P. Horn, “Closed-form solution of absolute orientation using unit quaternions,”J. Opt. Soc. A 4, 629–642 (1987).
[CrossRef]

B. K. P. Horn, Robot Vision (MIT Press, Cambridge, Mass.; McGraw-Hill, New York, 1986).

P. H. Winston, B. K. P. Horn, LISP (Addison-Wesley, Reading, Mass., 1984).

Huang, T. S.

S. Arun, T. S. Huang, S. D. Blostein, “Least-squares fitting of two 3-D point sets,” Tech. Note ISP-81 (Coordinated Science Laboratory, University of Illinois, Urbana, Ill., 1986); submitted toIEEE Trans. Patt. Anal. Machine Intell.

Johnson, R. M.

R. M. Johnson, “On a theorem stated by Eckart and Young,” Psychometrika 28, 259–263 (1963).
[CrossRef]

Korn, G. A.

G. A. Korn, T. M. Korn, Mathematical Handbook for Scientists and Engineers (McGraw-Hill, New York, 1968).

Korn, T. M.

G. A. Korn, T. M. Korn, Mathematical Handbook for Scientists and Engineers (McGraw-Hill, New York, 1968).

MacLane, S.

G. Birkhoff, S. MacLane, A Survey of Modern Algebra (Macmillan, New York1953).

Oswal, H. L.

H. L. Oswal, S. Balasubramanian, “An exact solution of absolute orientation,” Photogramm. Eng. 34, 1079–1083 (1968).

Schönemann, P. H.

P. H. Schönemann, Robert M. Carroll, “Fitting one matrix to another under choice of a central dilation and a rigid motion,” Psychometrika 35, 169–183 (1970).
[CrossRef]

P. H. Schönemann, “A generalized solution of the orthogonal procrustes problem,” Psychometrika 31, 1–10 (1966).
[CrossRef]

Schut, G. H.

G. H. Schut, “On exact linear equations for the computation of the rotational elements of absolute orientation,” Photogrammetria 16(1), 34–37 (1960).

Stuelpnagel, J. C.

J. L. Farrell, J. C. Stuelpnagel, “Problem 65-1: a least squares estimated of satellite attitude,”SIAM Rev. 8, 384–386 (1966).
[CrossRef]

Stuelpnagel, J. H.

J. H. Stuelpnagel, “On the parameterization of the three-dimensional rotation group,”SIAM Rev. 6, 422–430 (1964).
[CrossRef]

Thompson, E. H.

E. H. Thompson, “An exact linear solution of the problem of absolute orientation,” Photogrammetria 15(4), 163–179 (1958).

Winston, P. H.

P. H. Winston, B. K. P. Horn, LISP (Addison-Wesley, Reading, Mass., 1984).

Wolf, P. R.

P. R. Wolf, Elements of Photogrammetry (McGraw-Hill, New York, 1974).

Young, G.

C. Eckart, G. Young, “The approximation of one matrix by another of lower rank,” Psychometrika 1, 211–218 (1936).
[CrossRef]

J. Opt. Soc. A

B. K. P. Horn, “Closed-form solution of absolute orientation using unit quaternions,”J. Opt. Soc. A 4, 629–642 (1987).
[CrossRef]

Photogramm. Eng.

H. L. Oswal, S. Balasubramanian, “An exact solution of absolute orientation,” Photogramm. Eng. 34, 1079–1083 (1968).

Photogrammetria

E. H. Thompson, “An exact linear solution of the problem of absolute orientation,” Photogrammetria 15(4), 163–179 (1958).

G. H. Schut, “On exact linear equations for the computation of the rotational elements of absolute orientation,” Photogrammetria 16(1), 34–37 (1960).

Psychometrika

C. Eckart, G. Young, “The approximation of one matrix by another of lower rank,” Psychometrika 1, 211–218 (1936).
[CrossRef]

B. F. Green, “The orthogonal approximation of an oblique structure in factor analysis,” Psychometrika 1, 429–440 (1952).
[CrossRef]

W. A. Gibson, “On the least-squares orthogonalization of an oblique transformation,” Psychometrika 27, 193–195 (1962).
[CrossRef]

R. M. Johnson, “On a theorem stated by Eckart and Young,” Psychometrika 28, 259–263 (1963).
[CrossRef]

P. H. Schönemann, “A generalized solution of the orthogonal procrustes problem,” Psychometrika 31, 1–10 (1966).
[CrossRef]

N. Cliff, “Orthogonal rotation to congruence,” Psychometrika 31, 33–42 (1966).
[CrossRef]

P. H. Schönemann, Robert M. Carroll, “Fitting one matrix to another under choice of a central dilation and a rigid motion,” Psychometrika 35, 169–183 (1970).
[CrossRef]

SIAM Rev.

J. L. Farrell, J. C. Stuelpnagel, “Problem 65-1: a least squares estimated of satellite attitude,”SIAM Rev. 8, 384–386 (1966).
[CrossRef]

J. H. Stuelpnagel, “On the parameterization of the three-dimensional rotation group,”SIAM Rev. 6, 422–430 (1964).
[CrossRef]

Other

G. A. Korn, T. M. Korn, Mathematical Handbook for Scientists and Engineers (McGraw-Hill, New York, 1968).

G. Birkhoff, S. MacLane, A Survey of Modern Algebra (Macmillan, New York1953).

P. H. Winston, B. K. P. Horn, LISP (Addison-Wesley, Reading, Mass., 1984).

P. R. Halmos, Finite Dimensional Vector Spaces, 2nd ed. (Van Nostrand, Princeton, N.J., 1958).

C. C. Slama, C. Theurer, S. W. Henrikson, eds., Manual of Photogrammetry (American Society of Photogrammetry, Falls Church, Va., 1980).

P. R. Wolf, Elements of Photogrammetry (McGraw-Hill, New York, 1974).

S. K. Gosh, Theory of Stereophotogrammetry (Ohio State U. Bookstores, Columbus, Ohio, 1972).

B. K. P. Horn, Robot Vision (MIT Press, Cambridge, Mass.; McGraw-Hill, New York, 1986).

S. Arun, T. S. Huang, S. D. Blostein, “Least-squares fitting of two 3-D point sets,” Tech. Note ISP-81 (Coordinated Science Laboratory, University of Illinois, Urbana, Ill., 1986); submitted toIEEE Trans. Patt. Anal. Machine Intell.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (2)

Fig. 1
Fig. 1

The coordinates of a number of points are measured in two coordinate systems. The transformation between the two systems can be found by using these measurements.

Fig. 2
Fig. 2

Three points can be used to define a triad. Such a triad can be constructed by using the left measurements. A second triad is then constructed from the right measurements. The required coordinate transformation can be estimated by finding the transformation that maps one triad into the other. This method does not use the information about each of the three points equally.

Equations (94)

Equations on this page are rendered with MathJax. Learn more.

{ r l , i } , { r r , i } ,
r r = s R ( r l ) + r 0
R ( r l ) 2 = r l 2 ,
e i = r r , i s R ( r l , i ) r 0 .
i = 1 n e i 2 .
r ¯ l = 1 n i = 1 n r l , i , r ¯ r = 1 n i = 1 n r r , i .
r l , i = r l , i r ¯ l , r r , i = r r , i r ¯ r .
i = 1 n r l , i = 0 , i = 1 n r r , i = 0.
e i = r r , i s R ( r l , i ) r 0 ,
r 0 = r 0 r ¯ r + s R ( r ¯ l ) .
i = 1 n r r , i s R ( r l , i ) r 0 2 ,
i = 1 n r r , i s R ( r l , i ) 2 2 r 0 · i = 1 n r r , i s R ( r l , i ) 2 n r 0 2 .
r 0 = r ¯ r s R ( r ¯ l ) ;
e i = r r , i s R ( r l , i ) ,
i = 1 n r r , i s R ( r l , i ) 2 .
e i = r l , i ( 1 / s ) R T ( r r , i ) ,
e i = [ ( 1 / s ) ( r r , i ) R ( r l , i ) ] ,
i = 1 n ( 1 / s ) ( r r , i ) R ( r l , i ) 2 .
e i = 1 s r r , i s R ( r l , i ) .
1 s i = 1 n r r , i 2 2 i = 1 n r r , i · [ R ( r l , i ) ] + s i = 1 n r l , i 2 ,
1 s S r 2 D + s S l ,
S l = i = 1 n r r , l 2 , D = i = 1 n r r , i · [ R ( r l , i ) ] , S r = i = 1 n r r , i 2 .
( s S l 1 s S r ) 2 + 2 ( S l S r D ) .
s = ( i = 1 n r r , i 2 / i = l n r l , i 2 ) 1 / 2 .
i = l n r r , i · [ R ( r l , i ) ]
i = 1 n r r , i · [ R ( r l , i ) ] = i = 1 n ( r r , i ) T R ( r l , i ) .
a T R b = Tr ( R T a b T ) ,
Tr [ R T i = 1 n r r , i ( r l , i ) T ] = Tr ( R T M ) ,
M = i = 1 n r r , i ( r l , i ) T ,
M = [ S x x S x y S x z S y x S y y S y z S z x S z y S z z ] ,
S x x = i = 1 n x r , i x l , i , S x y = i = 1 n x r , i y l , i , ,
Tr ( R T M ) .
M = U S ,
S = ( M T M ) 1 / 2
U = M ( M T M ) 1 / 2
M T M = λ 1 u ˆ 1 u ˆ 1 T + λ 2 u ˆ 2 u ˆ 2 T + λ 3 u ˆ 3 u ˆ 3 T .
S = λ 1 u ˆ 1 u ˆ 1 T + λ 2 u ˆ 2 u ˆ 2 T + λ 3 u ˆ 3 u ˆ 3 T .
S 2 = λ 1 u ˆ 1 u ˆ 1 T + λ 2 u ˆ 2 u ˆ 2 T + λ 3 u ˆ 3 u ˆ 3 T = M T M ,
x T S x = λ 1 ( u ˆ 1 · x ) 2 + λ 2 ( u ˆ 2 · x ) 2 + λ 3 ( u ˆ 3 · x ) 2 > 0.
S 1 = ( M T M ) 1 / 2 = 1 λ 1 u ˆ 1 u ˆ 1 T + 1 λ 2 u ˆ 2 u ˆ 2 T + 1 λ 3 u ˆ 3 u ˆ 3 T ,
U = M S 1 = M ( M T M ) 1 / 2 .
det ( U ) = det ( M S 1 ) = det ( M ) det ( S 1 ) ,
U = M ( 1 λ 1 u ˆ 1 u ˆ 1 T + 1 λ 2 u ˆ 2 u ˆ 2 T ) ± u ˆ 3 u ˆ 3 T ,
U = M S + ± u ˆ 3 u ˆ 3 T ,
S + = 1 λ 1 u ˆ 1 u ˆ 1 T + 1 λ 2 u ˆ 2 u ˆ 2 T ,
Tr ( R T M ) = Tr ( R T U S ) ,
Tr ( R T U S ) = λ 1 Tr ( R T U u ˆ 1 u ˆ 1 T ) + λ 2 Tr ( R T U u ˆ 2 u ˆ 2 T ) + λ 3 Tr ( R T U u ˆ 3 u ˆ 3 T ) .
Tr ( R T U u ˆ i u ˆ i T ) = Tr ( u ˆ i T R T U u ˆ i ) = Tr ( R u ˆ i · U u ˆ i ) = ( R u ˆ i · U u ˆ i ) .
Tr ( R T U S ) λ 1 + λ 2 + λ 3 = Tr ( S ) ,
R = M ( M T M ) 1 / 2 .
U = M ( M T M ) 1 / 2 .
i = 1 3 j = 1 3 ( m i , j r i , j ) 2 = Tr [ ( M R ) T ( M R ) ] ,
Tr ( M T M ) 2 Tr ( R T M ) + Tr ( R T R ) .
Tr ( R T M ) .
M = i = 1 n r r , i ( r l , i ) T .
M n l = 0
r l , i · n l = 0
M n l = ( i = 1 n r r , i ( r l , i ) T ) n l = i = 1 n r r , i ( r l , i · n l ) = 0.
r r , i · n r = 0 ,
U = M ( M T M ) 1 / 2
i = 1 n ( r l , i ) T R ¯ r r , i
R ¯ = M T ( M M T ) 1 / 2 ,
R ¯ T = ( M M T ) 1 / 2 M .
R = M ( M T M ) 1 / 2 ,
[ M 1 ( M M T ) 1 / 2 M ] 2 = M 1 ( M M T ) M = M T M .
M 1 ( M M T ) 1 / 2 M = ( M T M ) 1 / 2 ,
R ¯ T = ( M M T ) 1 / 2 M = M ( M T M ) 1 / 2 = R .
det ( M T M λ I ) = 0 ,
[ S x x 2 + S y x 2 + S z x 2 S x x S x y + S y x S x y + S z x S z y S x x S x z + S y x S y z + S z x S z z S x y S x x + S y y S y x + S z y S z x S x y 2 + S y y 2 + S z y 2 S x y S x z + S y y S y z + S z y S z z S x z S x x + S y z S y x + S z z S z x S x z S x y + S y z S y y + S z z S z y S x z 2 + S y z 2 + S z z 2 ] .
( M T M λ i I ) u ˆ i = 0
M T M = [ a d f d b e f e c ] ,
det ( M T M λ I ) = 0
λ 3 + d 2 λ 2 + d 1 λ + d 0 + 0 ,
d 2 = a + b + c , d 1 = ( e 2 b c ) + ( f 2 a c ) + ( d 2 a b ) , d 0 = a b c + 2 d e f ( a e 2 + b f 2 + c d 2 ) .
d 2 = Tr ( M T M ) ,
d 2 = ( S x x 2 + S x y 2 + S x z 2 ) + ( S y x 2 + S y y 2 + S y z 2 ) + ( S z x 2 + S z y 2 + S z z 2 ) ,
d 0 = det ( M T M ) = [ det ( M ) ] 2
d 0 = [ ( S x x S y y S z z + S x y S y z S z x + S y x S x z S z y ) ( S x x S y z S z y + S y y S z x S x z + S z z S x y S y x ) ] 2 .
i = 1 n r r , i X r l , i 2
i = 1 n [ r r , i 2 2 r r , i · ( X r l , i ) + X r l , i 2 ] .
i = 1 n Tr [ r r , i ( r r , i ) T 2 r r , i ( r l , i ) T X T + X r l , i ( r l , i ) T X T ] = Tr ( X A l X T 2 M X T + A r ) ,
A l = i = 1 n r l , i ( r l , i ) T , A r = i = 1 n r r , i ( r r , i ) T
Tr ( X A l X T M X T X M T + M A l 1 M T ) + Tr ( A r M A l 1 M T ) .
Tr [ ( X A l M ) ( X M A l 1 ) T ] .
Tr [ ( X A l 1 / 2 M A l 1 / 2 ) ( X A l 1 / 2 M A l 1 / 2 ) T ] = X A l 1 / 2 M A l 1 / 2 2 .
X A l 1 / 2 = M A l 1 / 2
X = M A l 1 .
i = l n r l , i X ¯ r r , i 2 ,
X ¯ = M T A r 1 .
R = X ( X T X ) 1 / 2 = ( X X T ) 1 / 2 X ,
R ¯ = X ¯ ( X ¯ T X ¯ ) 1 / 2 = ( X ¯ X ¯ T ) 1 / 2 X ¯ .
M = U S , M A l 1 = U S
U S = U ( S A l ) .
S = S A l ,

Metrics