Transcription of Homography Estimation - University of California, San Diego
1 ComputerVisionICSE252A,Winter2007 DavidKriegmanHomography Estimation , wecanwritethetransformationofpointsin3 Dfromcamera1 tocamera2 as:X2=HX1X1;X22R3(1)Intheimageplanes,usi nghomogeneouscoordinates,wehave 1x1=X1; 2x2=X2;therefore 2x2=H 1x1(2)Thismeansthatx2is equaltoHx1uptoa scale(duetouniversalscaleambiguity).Note thatx2 Hx1is it is knownthatsomepointsalllieina planeinanimage1, theimagecanberecti EstimationTo estimateH, westartfromtheequationx2 Hx1. Writtenelementbyelement,inhomogenouscoor dinateswegetthefollowingconstraint:24x2y 2z235=24H11H12H13H21H22H23H31H32H333524x 1y1z135,x2=Hx1(3)Ininhomogenouscoordinat es(x02=x2=z2andy02=y2=z2),x02=H11x1+H12y 1+H13z1H31x1+H32y1+H33z1(4)y02=H21x1+H22 y1+H23z1H31x1+H32y1+H33z1(5)Withoutlosso fgenerality, setz1= 1 andrearrange:x02(H31x1+H32y1+H33) =H11x1+H12y1+H13(6)y02(H31x1+H32y1+H33) =H21x1+H22y1+H23(7)We wanttosolve forH.
2 Eventhoughtheseinhomogeneousequationsinv olve thecoordinatesnonlinearly, thecoef cientsofHappearlinearly. Rearrangingequations6 and7 weget,aTxh=0(8)aTyh=0(9) purerotation,everyscenepointcanbethought ofaslyingona planeat in (H11; H12; H13; H21; H22; H23; H31; H32; H33)T(10)ax=( x1; y1; 1;0;0;0; x02x1; x02y1; x02)T(11)ay=(0;0;0; x1; y1; 1; y02x1; y02y1; y02)T:(12)Givena willfrequentlyencounterproblemsoftheform Ax=0(15) is similarinappearancetotheinhomogeneouslin earleastsquaresproblemAx=b(16)inwhichcas ewesolve forxusingthepseudoinverseorinverseofA. Thiswon't it usingSingularValueDecomposition(SVD).Sta rtingwithequation13fromtheprevioussectio n,we rstcomputetheSVDofA:A=U V>=9Xi=1 iuiv>i(17)WhenperformedinMatlab,thesingu larvalues iwillbesortedindescendingorder, so 9: If thehomographyisexactlydetermined, then 9= 0, andthereexistsa homographythat tsthepointsexactly.
3 If thehomographyisoverdetermined, then 9 0. Here 9representsa residual orgoodnessof t. We the rightsingularvector (acolumnfromV) whichcorrespondstothesmallestsingularval ue, 9. Thisis thesolution,h, whichcontainsthecoef cientsofthehomographymatrixthatbest reshapehintothematrixH, andformtheequationx2 , thesumsquarederrorcanbewrittenas,f(h)=12 (Ah 0)T(Ah 0)(18)f(h)=12(Ah)T(Ah)(19)f(h)=12hTATAh: (20)2 Takingthederivative offwithrespecttohandsettingtheresulttoze ro,wegetddhf= 0=12 ATA+ (ATA)T h(21)0=ATAh:(22)Lookingat theeigen-decompositionofATA, weseethathshouldequaltheeigenvectorofATA thathasaneigenvalueofzero(or, inthepresenceofnoisetheeigenvalueclosest tozero).
4 Thisresultis identicaltotheresultobtainedusingSVD,whi chis easilyseenfromthefollowingfact,Fact1 Givena matrixAwithSVDdecompositionA=U VT, thecolumnsofVcorrespondtotheeigenvectors
