[PDF] Least-Squares Rigid Motion Using SVD by Olga Sorkine-Hornung

View - Download Least-Squares Rigid Motion Using SVD by Olga Sorkine-Hornung

Previous PDF

Next PDF

Least-Squares Rigid Motion Using SVD

Olga Sorkine-Hornung and Michael Rabinovich

Department of Computer Science, ETH Zurich

January 16, 2017Abstract

This note summarizes the steps to computing the best-tting rigid transformation that aligns two sets of corresponding points. Keywords:Shape matching, rigid alignment, rotation, SVD1 Problem statement LetP=fp1;p2;:::;pngandQ=fq1;q2;:::;qngbe two sets of corresponding points inRd. We wish to nd a rigid transformation that optimally aligns the two sets in the least squares sense, i.e., we seek a rotationRand a translation vectortsuch that (R;t) = argmin

R2SO(d);t2Rdn

X i=1w ik(Rpi+t)qik2;(1) wherewi>0 are weights for each point pair. In the following we detail the derivation ofRandt; readers that are interested in the nal recipe may skip the proofs and go directly Section 4.

2 Computing the translation

AssumeRis xed and denoteF(t) =Pn

i=1wik(Rpi+t)qik2. We can nd the optimal translation by taking the derivative ofFw.r.t.tand searching for its roots: 0 = @F@t=nX i=12wi(Rpi+tqi) = = 2t nX i=1w i! + 2R nX i=1w ipi! 2nX i=1w iqi:(2)

Denote

p=P n i=1wipiP n i=1wi;q=P n i=1wiqiP n i=1wi:(3) 1

By rearranging the terms of (2) we get

t=qRp:(4) In other words, the optimal translationtmaps the transformed weighted centroid ofPto the weighted centroid ofQ. Let us plug the optimaltinto our objective function: n X i=1w ik(Rpi+t)qik2=nX i=1w ikRpi+qRpqik2= (5) nX i=1w ikR(pip)(qiq)k2:(6) We can thus concentrate on computing the rotationRby restating the problem such that the translation would be zero: x i:=pip;yi:=qiq:(7)

So we look for the optimal rotationRsuch that

R= argmin

R2SO(d)n

X i=1w ikRxiyik2:(8)

3 Computing the rotation

Let us simplify the expression we are trying to minimize in (8): kRxiyik2= (Rxiyi)T(Rxiyi) = (xTiRTyTi)(Rxiyi) = =xTiRTRxiyTiRxixTiRTyi+yTiyi= =xTixiyTiRxixTiRTyi+yTiyi:(9) We got the last step by remembering that rotation matrices implyRTR=I(Iis the identity matrix). Note thatxTiRTyiis a scalar:xTihas dimension 1d,RTisddandyiisd1. For any scalar awe trivially havea=aT, therefore x

TiRTyi= (xTiRTyi)T=yTiRxi:(10)

Therefore we have

kRxiyik2=xTixi2yTiRxi+yTiyi:(11) Let us look at the minimization and substitute the above expression: argmin

R2SO(d)n

X i=1w ikRxiyik2= argmin

R2SO(d)n

X i=1w i(xTixi2yTiRxi+yTiyi) = = argmin

R2SO(d)

nX i=1w ixTixi2nX i=1w iyTiRxi+nX i=1w iyTiyi! = argmin

R2SO(d)

2nX i=1w iyTiRxi! :(12) 2 2 6 664w
1 w 2... w n3 7 7752
6

664|yT1|

|yT2| |yTn|3 7 7752
4 R3 52

4j j j

x

1x2:::xn

j j j3 5 2 6

664|w1yT1|

|w2yT2| |wnyTn|3 7 7752

4j j j

Rx1Rx2::: Rxn

j j j3 5 =2 6 664w

1yT1Rx1

w

2yT2Rx2...

wnyTnRxn3 7 775

Figure 1: Schematic explanation of

Pn i=1wiyTiRxi= tr(WYTRX).

The last step (removing

Pn i=1wixTixiandPn i=1wiyTiyi) holds because these expressions do not depend onRat all, so excluding them would not aect the minimizer. The same holds for multiplication of the minimization expression by a scalar, so we have argmin

R2SO(d)

2nX i=1w iyTiRxi! = argmax

R2SO(d)n

X i=1w iyTiRxi:(13)

We note that

nX i=1w iyTiRxi= tr WYTRX ;(14) whereW= diag(w1;:::;wn) is annndiagonal matrix with the weightwion diagonal entryi; Yis thednmatrix withyias its columns andXis thednmatrix withxias its columns. We remind the reader that the trace of a square matrix is the sum of the elements on the diagonal: tr(A) =Pn i=1aii. See Figure 1 for an illustration of the algebraic manipulation. Therefore we are looking for a rotationRthat maximizes trWYTRX. Matrix trace has the property tr(AB) = tr(BA) (15) for any matricesA;Bof compatible dimensions. Therefore tr WYTRX = tr (WYT)(RX) = tr RXWYT :(16) Let us denote thedd\covariance" matrixS=XWYT. Take SVD ofS:

S=UVT:(17)

Now substitute the decomposition into the trace we are trying to maximize: tr RXWYT = tr(RS) = tr RUVT = tr VTRU :(18) The last step was achieved using the property of trace (15). Note thatV,RandUare all orthogonal matrices, soM=VTRUis also an orthogonal matrix. This means that the columns ofMare orthonormal vectors, and in particular,mTjmj= 1 for eachM's columnmj. Therefore all entriesmijofMare1 in magnitude:

1 =mTjmj=dX

i=1m

2ij)m2ij1) jmijj 1:(19)

3 So what is the maximum possible value fortr(M)? Remember that is a diagonal matrix with non-negative values1;2;:::;d0 on the diagonal. Therefore: tr(M) =

12...d!

m11m12::: m1dm21m22::: m2d............md1md2::: mdd! =dX i=1 imiidX i=1 i:(20) Therefore the trace is maximized ifmii= 1. SinceMis an orthogonal matrix, this means that

Mwould have to be the identity matrix!

I=M=VTRU)V=RU)R=V UT:(21)

Orientation rectication.The process we just described nds the optimalorthogonalma- trix, which could potentially contain re ections in addition to rotations. Imagine that the point setPis a perfect re ection ofQ. We will then nd that re ection, which aligns the two point sets perfectly and yields zero energy in (8), the global minimum in this case. However, if we

restrict ourselves to rotations only, there might not be a rotation that perfectly aligns the points.

Checking whetherR=V UTis a rotation is simple: if det(V UT) =1 then it contains a re ection, otherwise det(V UT) = +1. Assume det(V UT) =1. RestrictingRto a rotation is equivalent to restrictingMto a re ection. We now want to nd a re ectionMthat maximizes: tr(M) =1m11+2m22+:::+dmdd=:f(m11;:::;mdd):(22) Note thatfonly depends on the diagonal ofM, not its other entries. We now consider themii's as variables (m11;:::;mdd). This is the set of all diagonals of re ection matrices of ordern. Surprisingly, it has a very simple structure. Indeed, a result by A. Horn [1] states that the set of all diagonals of rotation matrices of ordernis equal to the convex hull of the points (1;:::;1) with an even number of coordinates that are1. Since any re ection matrix can be constructed by inverting the sign of a row of a rotation matrix and vice versa, it follows that the set we are optimizing on is the convex hull of the points (1;:::;1) with anunevennumber of1's. Since our domain is a convex polyhedron, the linear functionfattains its extrema at its vertices. The diagonal (1;1;:::;1) is not in the domain since it has an even number of1's (namely, zero), and therefore the next best shot is (1;1;:::;1;1): tr(M) =1+2+:::+d1d:(23) This value is attained at a vertex of our domain, and is larger than any other combination of the form (1;:::;1) except (1;1;:::;1), becausedis the smallest singular value. To summarize, we arrive at the fact that if det(V UT) =1, we need

M=VTRU=0

@1

1...111

A )R=V0 @1

1...111

A

UT:(24)

We can write a general formula that encompasses both cases, det(V UT) = 1 and det(V UT) =1: R=V0 B @1 1...1 det(V UT)1 C

AUT:(25)

4

4 Rigid motion computation { summary

Let us summarize the steps to computing the optimal translationtand rotationRthat minimize n X i=1w ik(Rpi+t)qik2:

1. Compute the weighted centroids of both point sets:

p=P n i=1wipiP n i=1wi;q=P n i=1wiqiP n i=1wi:

2. Compute the centered vectors

x i:=pip;yi:=qiq; i= 1;2;:::;n:

3. Compute theddcovariance matrix

S=XWYT;

whereXandYare thednmatrices that havexiandyias their columns, respectively, andW= diag(w1;w2;:::;wn).

4. Compute the singular value decompositionS=UVT. The rotation we are looking for is

then R=V0 B @1 1...1 det(V UT)1 C AUT:

5. Compute the optimal translation as

t=qRp:

Acknowledgments

We are grateful to Julian Panetta, Zohar Levi and Mario Botsch for their help with improving this note.

References

[1] A. Horn,Doubly stochastic matrices and the diagonal of a rotation matrix. Amer. J. Math.

76:620{630 (1954).

5quotesdbs_dbs19.pdfusesText_25

[PDF] exercice pagination mémoire

[PDF] pagination mémoire virtuelle

[PDF] difference entre pagination et segmentation

[PDF] conversion adresse logique adresse physique

[PDF] pagination et segmentation pdf

[PDF] pagination systeme d'exploitation

[PDF] telecharger un livre de grammaire pdf

[PDF] larousse conjugaison pdf

[PDF] telecharger larousse difficultés grammaticales pdf

[PDF] larousse grammaire francais

[PDF] larousse orthographe pdf

[PDF] larousse livre de bord orthographe pdf

[PDF] introduction grammaire generative

[PDF] chomsky théorie

[PDF] chomsky linguistique pdf