Lie Groups for 2D and 3D Transformations

1 LieGroupsfor2 Dand3 DTransformationsEthanEadeUp datedMay20,2017*1 Intro ductionThisdo ologicalgroupthatisalsoasmo othmanifold,withsomeotherniceprop ciatedwitheveryLiegroupisaLiealgebra,whi chisavectorspacediscussedb ortantly,aLiegroupanditsLiealgebraareint imatelyrelated,allowingcalculationsinone tob emapp cumentdo esnotgivearigorousintro ductiontoLiegroups,nordo esattempttoprovideenoughinformationthatt heLiegroupsrepresentingspatialtransforma tionscanb eemployedusefullyinrob (3)3 DRotations33 DrotationmatrixSE(3)3 DRigidtransformations6 Lineartransformationonhomogeneous4-vecto rsSO(2)2 DRotations12 DrotationmatrixSE(2)2 DRigidtransformations3 Lineartransformationonhomogeneous3-vecto rsSim(3)3 DSimilaritytransformations(rigidmotion+s cale)7 Lineartransformationonhomogeneous4-vecto rsForeachofthesegroups,therepresentation isdescrib ed,andtheexp oticsorcomputervision?Manyproblemsinrob ,*Added erentiationof/bygroupelementp ecomp osed,inverted,di erentiatedandinterp ciatedmachineryaddressalloftheseop erations,anddosoinaprincipledway,sothato nceintuitionisdevelop ed,itcanb efollowedwithcon ertiesEveryLiegrouphasanasso ciatedLiealgebra, ,theLiealgebraisavectorspacegeneratedbyd i erentiatingthegrouptrans-formationsalong chosendirectionsinthespace, ,thoughtangentvectorsundergoaco (andthusofthetangentspace)

2 Arecalledgeneratorsinthisdo ortantly,thetangentspaceasso ciatedwithaLiegroupprovidesan optimal spaceinwhichtorepresentdi ,velo cities,Jacobians, optimal spaceinwhichtorepresentdi erentialquantitiesb ecause Thetangentspaceisavectorspacewiththesame dimensionasthenumb erofdegreesoffreedomofthegrouptransforma tions Theexp onentialmapconvertsanyelementofthetangen tspaceexactlyintoatransformationinthegro up Theadjointlinearlyandexactlytransformsta ngentvectorsfromonetangentspacetoanother Theadjointprop ertyiswhatensuresthatthetangentspacehast hesamestructureatallp ointsonthemanifold,b ecauseatangentvectorcanalwaysb edb ,3 Drigidtransfor-mationshavetheactionofrot atingandtranslatingp (3) ,SO(3), ositionandinversioninthegroupcorresp ,inversionisequivalenttotransp SO(3)(1)R 1=RT(2)2 TheLiealgebra,so(3),isthesetof3 (3)corresp ondtothederivativesofrotationaroundtheea chofthestandardaxes,evaluatedattheidenti ty:G1= 0 0 00 0 10 1 0 , G2= 0 0 10 0 0 1 0 0 , G3= 0 1 01 0 00 0 0 (3)Anelementofso(3)isthenrepresentedasal inearcombinationofthegenerators: R3(4) 1G1+ 2G2+ 3G3 so(3)(5)Wewillsimplywrite so(3)asa3-vectoroftheco e cients,anduse torepresentthecorre-sp onentialMapTheexp onentialmapthattakesskewsymmetricmatrice storotationmatricesissimplythematrixexp onentialoveralinearcombinationofthegener ators:exp ( ) exp 0 3 2 30 1 2 10 (6)=I+ +12!

3 2 +13! 3 + (7)Writingthetermsinpairs,wehave:exp ( ) =I+ i=0[ 2i+1 (2i+ 1)!+ 2i+2 (2i+ 2)!](8)Nowwecantakeadvantageofaprop ertyofskew-symmetricmatrices: 3 = ( T ) (9)Firstextendthisidentitytothegeneralca se: 2 T (10) 2i+1 = ( 1)i 2i (11) 2i+2 = ( 1)i 2i 2 (12)Nowwecanfactortheexp onentialmapseriesandrecognizetheTaylorex pansionsintheco e cients:3exp ( ) =I+( i=0( 1)i 2i(2i+ 1)!) +( i=0( 1)i 2i(2i+ 2)!) 2 (13)=I+(1 23!+ 45!+ ) +(12! 24!+ 46!+ ) 2 (14)=I+(sin ) +(1 cos 2) 2 (15)Equation15isthefamiliarRo onentialmapyieldsarotationby radiansaroundtheaxisgivenby .PracticalimplementationoftheRo driguesformulashouldusetheTaylorexpansio nsoftheco e cientsofthesecondandthirdtermswhen onentialmapcanb einvertedtogivethelogarithm,goingfromSO( 3)toso(3):R SO(3)(16) = arccos(tr(R) 12)(17)ln (R) = 2 sin (R RT)(18)Thevector isthentakenfromtheo -diagonalelementsofln (R).Again,theTaylorexpansionoftheco e cient 2 sin shouldb eusedwhen , ,theadjointiswrittenAdjX: so(3),R SO(3)(19)R exp ( ) = exp (AdjR ) R(20)Theadjointcanb , :exp (AdjR ) =R exp ( ) R 1(21)Then,withoutlossofgenerality,let =t v,fort R,anddi erentiatebytatt= 0:4ddt t=0exp (AdjR t v) =ddt t=0[R exp (t v) R 1](22)ddt t=0[I+ (AdjR t v) +O(t2)]=R ddt t=0[I+ (t v) +O(t2)] R 1(23)(AdjR v) =R v R 1= (Rv) (24)= AdjR=R(25)InthecaseofSO(3), moves erentiatingtheactionofSO(3)onR3 ConsiderR SO(3)andx :y=f(R,x) =R x(26)Thendi erentiationbythevectorisstraightforward, asfislinearinx: y x=R(27)Di erentiationbytherotationparametersisp erformedbyimplicitlyleftmultiplyingthero tationbytheexp onentialofatangentvectoranddi erentiatingtheresultingexpressionaroundt hezerop ductbythegenerators.

4 Y R= | =0(exp ( ) R) x(28)= | =0exp ( ) (R x)(29)= | =0exp ( ) y(30)=(G1yG2yG3y)(31)= y (32) erentiatingagroup-valuedfunctionbyanargu mentinthegroupConsideraLiegroupGandafunc tionf:G ,butbyintro ducingtangentspacep erturbationsontheargumentandresult,wecan usethedi erentationnotationasashorthandforthemapp ingfrominputtooutputp erturbations:exp ( ) f(g) =f(exp ( ) g)(33) f g | =0(34) anddi erentiatingyieldsanexplicitformulaforthe di erentialoftheoutputp erturbation bytheinputp erturbation : = log(f(exp ( ) g) f(g) 1)(35) f g log(f(exp ( ) g) f(g) 1) | =0(36) ducesalinearmappingfromleft-tangent-spac ep erturbationsoftheargumenttoleft-tangent- spacep ected,applyingthisdi erentiationshorthandtotheidentityfunctio nf(g) = cedure,considerapro ductofelementsinG= SO(3)bythesecondfactorR0:R2=f(R0) R1 R0(37)First,theinputandoutputp erturbationsinthetangentspaceso(3) ( ) R2=R1 exp ( ) R0(38)Di erentationof bytheinputp erturbation isp erformedaround = R2 R0 log((R1 exp ( ) R0) (R1 R0) 1) | =0(39)= | =0[log((exp(AdjR1 ) R1 R0) (R1 R0) 1)](40)= | =0[log(exp(AdjR1 ))](41)= | =0[AdjR1 ](42)= AdjR1(43)=R1(44) (3) deGaussiandistributionsover3 Drotationsbyrepresentingthemeanwithanele mentofSO(3)andthecovarianceasaquadraticf ormovertangentvectorsinso(3).

5 Moreprecisely,consideraGaussiandistribut iongivenbymeanR SO(3)andcovariance R3 : N(0, )(45)S= exp ( ) R(46) ositionofuncertainrotationsGiventwoGauss iandistributionsonrotation,wecancomp e(R0, 0)andtheotherb e(R1, 1).Thenthedistributionofrotationsby rsttransformingbyR0andthenbyR1isgivenby: (R1, 1) (R0, 0) =(R1 R0, 1+R1 0 RT1)(47) ecombinedinaBayesianmannertoyield(Rc, c)by rst ndingthedeviationb etweenthetwomeansinthetangentspace, (inversecovariance)adds,asusual: c=( 10+ 11) 1(48)= 0 0( 0+ 1) 1 0(49)v R1 R0(50)= ln(R1 R 10)(51)Rc= exp( c 11 v) R0(52) (3)Equation47couldb eusedasthedynamicsup dateinanextendedKalman lter(EKF),where(R0, 0)isthepriorstateand(R1, 1)isthedynamicmo dateforthecovarianceandEquation52istheme asurementup dateforthemean,assumingatrivialmeasureme ntJacobian(identitymatrix). ,theKalmangainKisde nedK 0( 0+ 1) 1(53)sothattheKalmanup datecanb ewritteninitsstandardform:Rc=R0 (K v)(54)= exp (K v) R0(55) c= (I K) 0(56)Lab ellingtheab oveinthestandardEKFframework,thestatecov arianceisgivenby 0andthemeasurementnoiseisgivenby , di (3) ,SE(3),iswellrepresentedbylineartransfor mationsonhomogeneousfour-vectors:R SO(3),t R3(57)C=(Rt01) SE(3)(58)Notethat,inanimplementation,onl yRandtneedtob eimplicitlyimp ,asinSO(3),meansthattransformationcomp ositionandinversionarecoincidentwithmatr ixmultiplicationandinversion:C1,C2 SE(3)(59)C1 C2=(R1t101) (R2t201)(60)=(R1R2R1t2+t101)(61)C 11=(RT1 RT1t01)(62)8 Thematrixrepresentationalsomakesthegroup actionon3Dp ointsandvectorsclear:x=(x y z w)T RP3( x'x R)C x=(Rt01) x(63)=(R(x y z)T+wtw)(64)Typically,w= 1,sothatxisaCartesianp ondsto ,enco dedwithw= 0, (3)isthesetof4 4matricescorresp ondingtodi erentialtranslationsandrotations(asinso( 3)).

6 Therearethussixgeneratorsofthealgebra:G1 = 0 0 0 10 0 0 00 0 0 00 0 0 0 , G2= 0 0 0 00 0 0 10 0 0 00 0 0 0 , G3= 0 0 0 00 0 0 00 0 0 10 0 0 0 ,G4= 0 0 0 00 0 1 00 1 0 00 0 0 0 , G5= 0 0 1 00 0 0 0 1 0 0 00 0 0 0 , G6= 0 1 0 01 0 0 00 0 0 00 0 0 0 (65)Anelementofse(3)isthenrepresentedbym ultiplesofthegenerators:(u )T R6(66)u1G1+u2G2+u3G3+ 1G4+ 2G5+ 3G6 se(3)(67)Forconvenience,wewrite(u )T se(3), onentialMapTheexp onentialmapfromse(3)toSE(3)isthematrixex p onentialonalinearcombinationofthegenerat ors: =(u ) se(3)(68)exp ( ) = exp( u00)(69)=I+( u00)+12!( 2 u00)+13!( 3 2 u00)+ (70)9 Therotationblo ckisthesameasforSO(3),butthetranslationc omp onentisadi erentp owerseries:exp( u00)=(exp ( )Vu01)(71)V=I+12! +13! 2 + (72) ,wesplitthetermsbyo ddandevenp owers,andfactorout:V=I+ i=0[ 2i+1 (2i+ 2)!+ 2i+2 (2i+ 3)!](73)=I+( i=0( 1)i 2i(2i+ 2)!)

7 +( i=0( 1)i 2i(2i+ 3)!) 2 (74)Theco e cientscanb eidenti edwithTaylorexpansions,yieldingaformulaf orV:V=I+(12! 24!+ 46!+ ) +(13! 25!+ 47!+ ) 2 (75)=I+(1 cos 2) +( sin 3) 2 (76)Thustheexp onentialmaphasaclosed-formrepresentation :u, R3(77) = T (78)A=sin (79)B=1 cos 2(80)C=1 A 2(81)R=I+A +B 2 (82)V=I+B +C 2 (83)exp(u )=(RVu01)(84)18 Forimplementationpurp oses,TaylorexpansionsofA,B,andCshouldb eusedwhen :10V 1=I 12 +1 2(1 A2B) 2 (85)Theln()functiononSE(3)canb eimplementedby rst ndingln(R) ,thencomputingu=V 1 (3)iscomputedfromthegenerators,justasinS O(3): =(u )T se(3), C=(Rt01) SE(3)(86)C exp ( ) = exp (AdjC ) Cexp (AdjC ) =C exp ( ) C 1(87)AdjC =C (6 i=1 iGi) C 1(88)=(Ru+t R R )(89)= AdjC=(Rt R0R) R6 6(90)Notethatmovingatangentvectorviathea djointmixestherotationcomp onentintothetranslationcomp (Rt01) SE(3)andx :y=f(C,x) =(Rt) (x1)(91)=R x+t(92)Thendi erentiationbythevectorisstraightforward, asfislinearinx.

8 Y x=R(93)JustaswithSO(3),di erentiationbythetransformationparameters isp erformedbyleftmultiplyingthepro ductbythegenerators(herewiththeirlastrow sremoved):11 y C=(G1y G6y)=(I y )(94)Again,di erentiationofapro ductoftransformationsistrivialgiventhead joint:C C1 C0(95) C C0= [C1 exp ( ) C0](96)= AdjC1(97)4SO(2):Rotationsin2 DspaceHavingtreatedSO(3),the2 DequivalentSO(3) ,SO(2), ositionandinversioninthegroupcorresp ,inversionisequivalenttotransp SO(2)(98)R 1=RT(99)TheLiealgebra,so(2),isthesetof2 (2)corresp ondstothederivativeof2 Drotation,evaluatedattheidentity:G=(0 11 0)(100)Anelementofso(2)isthenanyscalarmu ltipleofthegenerator: R(101) G so(2)(102)Wewillsimplywrite so(2),anduse torepresenttheskewsymmetricmatrix onentialMapTheexp onentialmapthattakesskewsymmetricmatrice storotationmatricesissimplythematrixexp onentialoveralinearcombinationofthegener ators:exp ( ) exp(0 0)(103)=I+ +12! 2 +13! 3 + (104)=I+(0 0)+12!

9 ( 200 2)+13!(0 3 30)(105)TheresultingelementsformtheTaylo rseriesexpansionofsin andcos :exp ( ) =(cos sin sin cos ) SO(2)(106)Thustheexp onentialmapyieldsarotationby onentialmapcanb einverted,goingfromSO(2)toso(2):R SO(2)(107)ln (R) = = arctan (R21,R11)(108) ,theadjointofSO(2) (2):Rigidtransformationsin2 DspaceThegroupSE(2)isthelower-dimensiona lanalogueofSE(3).Thegrouphasthreedimensi ons,corre-sp ,SE(2),isrepresentedbylineartransformati onsonhomogeneousthree-vectors:R SO(2),t R2(109)C=(Rt01) SE(2)(110)13 Notethat,inanimplementation,onlyRandtnee dtob ositionandinversionarecoincidentwithmatr ixmultiplicationandinversion:C1,C2 SE(2)(111)C1 C2=(R1t101) (R2t201)(112)=(R1R2R1t2+t101)(113)C 11=(RT1 RT1t01)(114)Thematrixrepresentationalsom akesthegroupactionon2Dp ointsandvectorsexplicit:x=(x y w)T RP2( x'x R)C x=(Rt01) x(115)=(R(x y)T+wtw)(116)Typically,w= 1,sothatxisaCartesianp ondsto ,enco dedwithw= 0, (2)isthesetof3 3matricescorresp ondingtodi :G1= 0 0 10 0 00 0 0 , G2= 0 0 00 0 10 0 0 , G3= 0 1 01 0 00 0 0 (117)Anelementofse(2)isthenrepresentedby linearcombinationsofthegenerators.

10 (u1u2 )T R3(118)u1G1+u2G2+ G3 se(2)(119)Forconvenience,wewrite(u )T se(2), onentialMapAsforallLiegroupsinthisdo cument,theexp onentialmapfromse(2)toSE(2)isthematrixex p o-nentialonalinearcombinationofthegenera tors: =(u ) se(2)(120)exp ( ) = exp( u00)(121)=I+( u00)+12!( 2 u00)+13!( 3 2 u00)+ (122)Therotationblo ckisthesameasforSO(2),butthetranslationc omp onentisadi erentp owerseries:exp( u00)=(exp ( )Vu01)(123)V=I+12! +13! 2 + (124)Wesplitthetermsbyo ddandevenp owers:V= i=0[ 2i (2i+ 1)!+ 2i+1 (2i+ 2)!](125)Twoidentities(easilycon rmedbyinduction)areusefulforcollapsingth eseries: 2i = ( 1)i 2i (1 00 1)(126) 2i+1 = ( 1)i 2i+1 (0 11 0)(127)Directapplicationoftheidentiesyie ldsareducedexpressionforVintermsofdiagon alandskew-symmetriccomp onents:V= i=0( 1)i 2i[1(2i+ 1)! (1 00 1)+ (2i+ 2)! (0 11 0)](128)=( i=0( 1)i 2i(2i+ 1)!) (1 00 1)+( i=0( 1)i 2i+1(2i+ 2)!) (0 11 0)(129)15 Theco e cientscanb eidenti edwithTaylorexpansions:V=(1 23!)