Estimating 3-D rigid body transformations: a comparison of ...

1 Machine Vision and Applications (1997) 9: 272 290 Machine Vision andApplicationsc Springer-Verlag 1997 Estimating 3-D rigid body transformations: a comparisonof four major Eggert1, A. Lorusso2, Fisher31 Department of Computer Science, University of New Haven, West Haven, CT 06516, USA, e-mail: of Artificial Intelligence, University of Edinburgh, Edinburgh EH1 2QL, Scotland, UK, e-mail: of Artificial Intelligence, University of Edinburgh, Edinburgh EH1 2QL, Scotland, UK, e-mail: common need in machine vision is to com-pute the 3-D rigid body transformation that aligns two setsof points for which correspondence is known. A compara-tive analysis is presented here of four popular and efficientalgorithms, each of which computes the translational and ro-tational components of the transform in closed form, as thesolution to a least squares formulation of the problem. Theydiffer in terms of the transformation representation used andthe mathematical derivation of the solution, using respec-tively singular value decomposition or eigensystem compu-tation based on the standard [R,T] representation, and theeigensystem analysis of matrices derived from unit and dualquaternion forms of the transform.

2 This comparison presentsboth qualitative and quantitative results of several experi-ments designed to determine (1) the accuracy and robust-ness of each algorithm in the presence of different levels ofnoise, (2) the stability with respect to degenerate data sets,and (3) relative computation time of each approach underdifferent conditions. The results indicate that under ideal data conditions (no noise) certain distinctions in accuracyand stability can be seen. But for typical, real-world noiselevels, there is no difference in the robustness of the finalsolutions (contrary to certain previously published results).Efficiency, in terms of execution time, is found to be highlydependent on the computer system words:Motion analysis 3-D rigid transformations Pose estimation1 IntroductionDetermining the relationship between two coordinate sys-tems through the use of sets of corresponded feature mea-surements is known as theabsolute orientation numerous applications in the areas of photogrammetry,robotics (constructing world models), object motion analysis,relating a camera coordinate system to others (the hand-eyetransform), as well as Estimating the position and orientationof a recognized object (pose estimation).

3 Correspondence to: EggertA recent survey by Sabata and Aggarwal (1991) lists alarge number of methods that have been developed to com-pute the 3-D rigid body transformation between two setsof corresponded features. These techniques are categorizedbased on feature type (surfaces, lines or points) and generalsolution method (iterative vs closed form). Point featuresare the most commonly used in practice. Closed form so-lutions are generally superior to iterative methods, in termsof efficiency and robustness, because the latter suffer fromthe problems of not guaranteeing convergence, becomingtrapped in local minima of the error function and requir-ing a good starting estimate. For these reasons, this pa-per compares only a subset of the approaches mentionedin the indicated survey:closed formsolutions involving cor-respondedpointsets.

4 The problem of determining point cor-respondence, itself an active research area, is not popular and efficient solutions are compared in thispaper. These differ according to the representations used forthe transformation components, and in the ways they mini-mize a criterion function. The first solution was developedby Arun et al. (1987) and is based on computing thesin-gular value decomposition(SVD) of a matrix derived fromthe standard [R,T] representation. A similar approach, butbased on exploiting theorthonormalproperties of the ro-tation matrix, computes theeigensystemof a different de-rived matrix, as presented by Horn et al. (1988). The thirdalgorithm, also developed by Horn (1987), involves com-puting the eigensystem of a matrix related to representingthe rotational component as aunit quaternion. Yet anothereigensystem is analyzed when the translation and rotationcomponents are represented usingdual quaternions, as pre-sented in the fourth technique by Walker et al.

5 (1991).The comparison conducted here consists of three , the absoluteaccuracyof each algorithm is determinedusing ground truth under noiseless conditions, and thenro-bustnessis measured as the coordinates of correspondingpoints are corrupted with increasing amounts of noise. Sec-ond, thestabilityof the algorithms is quantified by findingthe breakdown limits as the original 3-D point sets degen-erate into such forms as a plane, a line and a single , the relativeefficiencyof the algorithms, in terms of273actual execution time, is reported for the above based on these results should make the choiceof an appropriate algorithm for a given application easierand more Previous comparisonsThe review by Sabata and Aggarwal (1991), while quitebroad in the number of techniques described, unfortunatelyonly presents a qualitative summary and comparison of thesetechniques (also, the dual quaternion method was devel-oped after this survey).

6 Quantitative results which wouldhelp answer the question, Which is the best? , were notgiven. However, in the defining papers of these approachesthere appear certain quantitative results and qualitative as-sessments of accuracy and speed, including the et al. observed that the computer time require-ments for the SVD and (unit) quaternion algorithms are com-parable (1987, p. 700). In a paper not directly related to anyof the methods, Zhang implemented both of the quaternionalgorithms and found that they yield exactly the same mo-tion estimate (1994, p. 124). Also, he found these two tech-niques to be more efficient than an iterative technique basedon the extended Kalman filter that he developed. Finally,Walker et al. stated that the two algorithms produce thesame rotation errors .. for the translation errors, the DQ al-gorithm exhibits better performance than the SVD (1991, p.)

7 364). The thorough and unbiased comparisonpresented here will clarify, extend (and even refute) someof these previous Descriptions of the algorithmsEach of the four algorithms computes the solution to a sim-ilar problem, which can be described as follows. Assumethat there exist two corresponded point setsfmigandfdig,i= N, such that they are related by:di=Rmi+T+Vi(1)whereRis a standard 3 3 rotation matrix,Tis a 3-Dtranslation vector andVia noise vector. Solving for the op-timal transformation [ R, T] that maps the setfmigontofdigtypically requires minimizing aleast squares error criteriongiven by: 2=N i=1kdi Rmi Tk2(2)It is true that if outliers exist in the data set (throughincorrect correspondences), this least squares solution is notoptimal and other techniques should be used (Meer et ). However, for the remainder of this paper we assumeonly correct correspondences the following sections, the basic steps involved inminimizing Eq.

8 2 are listed for each method in a commonframework. This includes exactly how the rotation and trans-lation components of the transformation are represented andcomputed, as well as any special cases that must be consid-ered for a complete solution. (For complete derivations ofeach technique, the reader is invited to consult the appropri-ate paper.) The singular value decomposition of a matrixThis first method was developed by Arun et al. (1987), andwas originally designed to explicitly minimize Eq. transformation representationFor this approach, the rotation is represented using a standard3 3 orthonormal matrix. Translation is a 3-D vector, as inEq. Calculating rotationAs a consequence of the least-squares solution to Eq. 2, thepoint setsfdigandfmigshould have the same this constraint a new equation can be generated. Bydefining: d=1NN i=1didci=di d m=1NN i=1mimci=mi m(3)Eq.

9 2 can be rewritten and reduced to: 2=N i=1kdci Rmcik2=N i=1(dTcidci+mTcimci 2dTci Rmci)(4)This equation is minimized when the last term is maximized,which is equivalent to maximizing Trace( RH), whereHisa correlation matrix defined by:H=N i=1mcidTci(5)If the singular value decomposition ofHis given byH=U VT, then the optimal rotation matrix, R, that maximizesthe desired trace is R=VUT(6)Note: minimizing Eq. 4 is also known as theorthogonal Pro-crustes problem, the SVD-based solution of which has beenknown for some time (Schonemann 1966). [It has also beenshown by Goryn and Hein (1995) that the above solutionholds in the case where both the model and data points havebeen corrupted by noise.] Calculating translationThe optimal translation aligns the centroid of the setfdigwith the rotated centroid of the setfmigas mentioned ear-lier. That is T= d R m(7) Special casesWhen the determinant of Ris +1, all is well.

10 However, whenthe two point sets are planar, or large amounts of noise exist,the determinant of Rmay become 1, indicating a reflectionrather than a rotation has been computed. In this case thedesired rotation can be found as R=V0UT, where thematrixV0=[v1,v2, v3] is formed from the columns ofV,withv3being the column that corresponds to the singularvalue ofHthat is special case has also been treated in alternativederivations by Umeyama (1991) and Kanatani (1994). Herethe optimal rotation is expressed as: R=U 11det(UVT) VT(8)None of the algorithms are suitable for use on linear orsingular point data A solution involving orthonormal matricesThe second algorithm is similar in nature to the first, butwas developed independently by Horn et al. (1988). As pre-sented in their paper, the error criterion function was slightlydifferent: 2=N i=1kdi s Rmi Tk2(9)including a scale factor, s, in the transformation .