RE: [Algorithms] Best fit rigid body rotation for a set of points

[<Sim...@po...>]

If you're after the principal eigenvalue/vector (assuming there is a unique=
 one) you could always use the "repeatedly square the matrix" approach. I u=
se this in a texture compressor (with a 4x4 (i.e. RBGA) matrix) and it seem=
s converge quite rapidly.=0D=0A=20=0D=0ASimon=0D=0A=20=0D=0A=0D=0A-----Orig=
inal Message-----=0D=0AFrom: gda...@li... =
[mailto:gda...@li...]On Behalf Of Bill Bax=
ter=0D=0ASent: 02 May 2005 10:29=0D=0ATo: gda...@li...urcefor=
ge.net=0D=0ASubject: Re: [Algorithms] Best fit rigid body rotation for a se=
t of points=0D=0A=0D=0A=0D=0AThanks Alex, glad to see I wasn't wrong about =
you "mocap dudes" being on top of this stuff. :-)=0D=0A=0D=0AThat's a great=
 reference.  Compares 4 different methods in detail, including the Horn's m=
ethod Peter-Pike mentioned.  Now that I look more closely, the tricky part =
of this Horn's method is that it requires finding the most positive root of=
 a quartic equation (to find the most positive eigenvalue of a 4x4 matrix),=
 and Horn doesn't really offer any suggestions for doing that other than to=
 remark that closed form solutions exist.  However, if I read it right it l=
ooks like you know that the eigenvalues of this matrix are all real and all=
 have magnitude <1.  So given that, it seems like Newton's method starting =
from lambda=3D1 would converge pretty quickly to the most positive root.=0D=
=0A=0D=0AAnyway, according the ref you linked to, Horn's orthonormal matrix=
 based method is the fastest for smallish data sets, which is what I'm afte=
r.=0D=0A=0D=0A--Bill=0D=0A=0D=0A=0D=0AOn 5/2/05, Alex Mohr < amohr@cs.wisc.=
edu> wrote:=20=0D=0A=0D=0AJoining late, so I apologize if this is repeating=
 but this may be=0D=0Auseful:=0D=0A=0D=0Ahttp://www.cs.duke.edu/researchers=
/artificial_intelligence/temp/eggert_rigid_body_transformations.pdf  <http:=
//www.cs.duke.edu/researchers/artificial_intelligence/temp/eggert_rigid_bod=
y_transformations.pdf>=20=0D=0A=0D=0AGenerally, I believe you should be abl=
e to get away with nothing more=0D=0Aannoying than doing an SVD.=0D=0A=0D=0A=
Alex=0D=0A=0D=0A=0D=0A>Great, that looks like exactly what I was after. I f=
igured vision folks or=0D=0A>mocap dudes among others must have run into th=
e same problem, but the search=20=0D=0A>terms I tried were all turning up b=
ubkis.=0D=0A>=0D=0A>With the info in the paper you linked to I was able to =
find the Horn paper=0D=0A>here:=0D=0A>  <http://people.csail.mit.edu/u/b/bk=
ph/public_html/papers/Absolute-OPT.pdf> http://people.csail.mit.edu/u/b/bkp=
h/public_html/papers/Absolute-OPT.pdf=0D=0A>=0D=0A>And I found this useful =
overview of a variety of similar techniques.=0D=0A>  <http://www.cs.duke.ed=
u/~jeffp/triseminar/absolute-orientation.pdf> http://www.cs.duke.edu/~jeffp=
/triseminar/absolute-orientation.pdf=0D=0A>=0D=0A>Thanks!=0D=0A>--bb=0D=0A>=0D=
=0A>On 5/1/05, Peter-Pike Sloan < pp...@wi...  <mailto:pp=
sl...@wi...> > wrote:=0D=0A>>=0D=0A>> Google for "procruste=
s method", this can be done without resorting to=0D=0A>> non-linear optimiz=
ation... I think in the vision community they call it=0D=0A>> "horns method=
", or something like that (some late 80's vision paper.) Here's=20=0D=0A>> =
a paper that deals with it:=0D=0A>>=0D=0A>> http://www.photogrammetry.ethz.=
ch/general/persons/devrim/LS3D_04WS_Dresden.pdf  <http://www.photogrammetry=
=2Eethz.ch/general/persons/devrim/LS3D_04WS_Dresden.pdf>=20=0D=0A>>   -Pete=
r-Pike=0D=0A>>=0D=0A>>  ------------------------------=0D=0A>> *From:* gdal=
gor...@li... [mailto:=20=0D=0A>> gdalgorithms-=
lis...@li...] *On Behalf Of *Bill Baxter=0D=0A>> *Sent:=
* Saturday, April 30, 2005 4:47 PM=0D=0A>> *To:* gda...@li...=
urceforge.net=0D=0A>> *Subject:* [Algorithms] Best fit rigid body rotation =
for a set of points=0D=0A>>=0D=0A>> Does anyone know an algorithm for deter=
mining the rigid body=20=0D=0A>> transformation that best fits the motion o=
f a set of N points=3F=0D=0A>>=0D=0A>> I.e. given a set of initial points p=
0 p1 ... pN, and their locations after=0D=0A>> some motion, q0 q1 ... qN, I=
 want to find the rigid body transformation T(x)=20=0D=0A>> (rotation and t=
ranslation only) that minimizes:=0D=0A>> Sum[i=3D0...N] ( || T(pi) - qi ||^=
2 )=0D=0A>>=0D=0A>> The only thing I can think of is to treat it as a gener=
ic nonlinear=0D=0A>> optimization problem, but it just seems like there sho=
uld be something more=20=0D=0A>> efficient than that.=0D=0A>>=0D=0A>>=0D=0A=
>> --Bill=0D=0A>>=0D=0A>>=0D=0A=0D=0A--------------------------------------=
-----------------=0D=0AThis SF.Net email is sponsored by: NEC IT Guy Games.=
=20=0D=0AGet your fingers limbered up and give it your best shot. 4 great e=
vents, 4=0D=0Aopportunities to win big! Highest score wins.NEC IT Guy Games=
=2E Play to=0D=0Awin an NEC 61 plasma display. Visit http://www.necitguy.co=
m/=3Fr=3D20=0D=0A_______________________________________________=0D=0AGDAlg=
orithms-list mailing list=0D=0AG...@li...=20=0D=
=0Ahttps://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=0D=0AArch=
ives:=0D=0Ahttp://sourceforge.net/mailarchive/forum.php=3Fforum_id=3D6188=0D=
=0A=0D=0A=0D=0A=0D=0A=0D=0A******************=0D=0AThis e-mail has been sen=
t from Imagination Technologies Limited.=0D=0APowerVR, Metagence, Ensigma a=
nd PURE Digital are divisions=0D=0Aof Imagination Technologies Limited.=0D=0A=0D=
=0AThe information contained in this e-mail, including any attachment,=0D=0A=
is confidential and may be legally privileged.  It is intended solely=0D=0A=
for the addressee(s) and access to this e-mail by anyone else is=0D=0Aunaut=
horised.  If you are not the intended recipient, any disclosure,=0D=0Acopyi=
ng or distribution or use of the information contained in this=20=0D=0Ae-ma=
il, is prohibited and may be unlawful.  If you have received this=0D=0Ae-ma=
il in error, please notify the sender by return e-mail and then=0D=0Adelete=
 it from your system.=0D=0A=0D=0AInternet communications cannot be guarante=
ed to be secure,=0D=0Aerror or virus-free.  The sender does not accept liab=
ility for any errors=0D=0Aor omissions which arise as a result.=0D=0A=0D=0A=
Any views expressed in this message are those of the author, except=0D=0Awh=
ere the author specifies and, with authority, states them to be the=0D=0Avi=
ews of Imagination Technologies Limited.=0D=0A