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?

2 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)arecalledgener atorsinthisdo 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)

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! 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)!)

4 +( 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.

5 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).

6 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.

7 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)).Therearethussixgeneratorsofthealgebr a: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!

8 ( 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)!) +( 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.

9 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!

10 2 +13! 3 + (104)=I+(0 0)+12!( 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.