斯坦福机器视觉

LinearAlgebraPrimerProfessorFei-FeiLiStanfordVisionLab22-Apr-231Another,veryin-depthlinearalgebrareviewfromCS229isavailablehere:http://AndavideodiscussionoflinearalgebrafromEE263ishere(lectures3and4):http://OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm22-Apr-232OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm22-Apr-233Vectorsandmatricesarejustcollectionsoforderednumbersthatrepresentsomething:movementsinspace,scalingfactors,pixelbrightnesses,etc.We’lldefinesomecommonusesandstandardoperationsonthem.VectorAcolumnvectorwhereArowvectorwheredenotesthetransposeoperation22-Apr-234VectorWe’lldefaulttocolumnvectorsinthisclassYou’llwanttokeeptrackoftheorientationofyourvectorswhenprogramminginMATLABYoucantransposeavectorVinMATLABbywritingV’.(Butinclassmaterials,wewillalwaysuseVTtoindicatetranspose,andwewilluseV’tomean“Vprime”)22-Apr-235VectorshavetwomainusesVectorscanrepresentanoffsetin2Dor3DspacePointsarejustvectorsfromtheorigin22-Apr-236Data(pixels,gradientsatanimagekeypoint,etc)canalsobetreatedasavectorSuchvectorsdon’thaveageometricinterpretation,butcalculationslike“distance”canstillhavevalueMatrix

22-Apr-237Images22-Apr-238MATLABrepresentsanimageasamatrixofpixelbrightnessesNotethatmatrixcoordinatesareNOTCartesiancoordinates.Theupperleftcorneris[y,x]=(1,1)=ColorImagesGrayscaleimageshaveonenumberperpixel,andarestoredasanm×nmatrix.Colorimageshave3numbersperpixel–red,green,andbluebrightnessesStoredasanm×n×3matrix22-Apr-239=BasicMatrixOperationsWewilldiscuss:AdditionScalingDotproductMultiplicationTransposeInverse/pseudoinverseDeterminant/trace22-Apr-2310MatrixOperationsAdditionCanonlyaddamatrixwithmatchingdimensions,orascalar.Scaling22-Apr-2311MatrixOperationsInnerproduct(dotproduct)ofvectorsMultiplycorrespondingentriesoftwovectorsandadduptheresultx·yisalso|x||y|Cos(theanglebetweenxandy)22-Apr-2312MatrixOperationsInnerproduct(dotproduct)ofvectorsIfBisaunitvector,thenA·BgivesthelengthofAwhichliesinthedirectionofB22-Apr-2313MatrixOperationsMultiplicationTheproductABis:Eachentryintheresultis(thatrowofA)dotproductwith(thatcolumnofB)Manyuses,whichwillbecoveredlater22-Apr-2314MatrixOperationsMultiplicationexample:22-Apr-2315Eachentryofthematrixproductismadebytakingthedotproductofthecorrespondingrowintheleftmatrix,withthecorrespondingcolumnintherightone.MatrixOperationsPowersByconvention,wecanrefertothematrixproductAAasA2,andAAAasA3,etc.Obviouslyonlysquarematricescanbemultipliedthatway22-Apr-2316MatrixOperationsTranspose–flipmatrix,sorow1becomescolumn1Ausefulidentity:22-Apr-2317DeterminantreturnsascalarRepresentsarea(orvolume)oftheparallelogramdescribedbythevectorsintherowsofthematrixFor,Properties:22-Apr-2318MatrixOperationsTraceInvarianttoalotoftransformations,soit’susedsometimesinproofs.(Rarelyinthisclassthough.)Properties:22-Apr-2319MatrixOperationsSpecialMatricesIdentitymatrixISquarematrix,1’salongdiagonal,0’selsewhereI

∙

[anothermatrix]=[thatmatrix]DiagonalmatrixSquarematrixwithnumbersalongdiagonal,0’selsewhereAdiagonal∙

[anothermatrix]scalestherowsofthatmatrix22-Apr-2320SpecialMatricesSymmetricmatrixSkew-symmetricmatrix22-Apr-2321OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm22-Apr-2322Matrixmultiplicationcanbeusedtotransformvectors.Amatrixusedinthiswayiscalledatransformationmatrix.TransformationMatricescanbeusedtotransformvectorsinusefulways,throughmultiplication:x’=AxSimplestisscaling:(Verifytoyourselfthatthematrixmultiplicationworksoutthisway)22-Apr-2323RotationHowcanyouconvertavectorrepresentedinframe“0”toanew,rotatedcoordinateframe“1”?Rememberwhatavectoris:[componentindirectionoftheframe’sxaxis,componentindirectionofyaxis]22-Apr-2324RotationSotorotateitwemustproducethisvector:[componentindirectionofnewxaxis,componentindirectionofnewyaxis]Wecandothiseasilywithdotproducts!Newxcoordinateis[originalvector]dot[thenewxaxis]Newycoordinateis[originalvector]dot[thenewyaxis]22-Apr-2325RotationInsight:thisiswhathappensinamatrix*vectormultiplicationResultxcoordinateis[originalvector]dot

[matrixrow1]Somatrixmultiplicationcanrotateavectorp:22-Apr-2326RotationSupposeweexpressapointinacoordinatesystemwhichisrotatedleftIfweusetheresultinthesamecoordinatesystem,wehaverotatedthepointright22-Apr-2327Thus,rotationmatricescanbeusedtorotatevectors.We’llusuallythinkoftheminthatsense--asoperatorstorotatevectors2DRotationMatrixFormulaCounter-clockwiserotationbyananglePxy’P’x’y22-Apr-2328TransformationMatricesMultipletransformationmatricescanbeusedtotransformapoint:

p’=R2R1SpTheeffectofthisistoapplytheirtransformationsoneaftertheother,fromrighttoleft.Intheexampleabove,theresultis

(R2(R1(Sp)))Theresultisexactlythesameifwemultiplythematricesfirst,toformasingletransformationmatrix:

p’=(R2R1S)p22-Apr-2329HomogeneoussystemIngeneral,amatrixmultiplicationletsuslinearlycombinecomponentsofavectorThisissufficientforscale,rotate,skewtransformations.Butnotice,wecan’taddaconstant!22-Apr-2330HomogeneoussystemThe(somewhathacky)solution?Sticka“1”attheendofeveryvector:Nowwecanrotate,scale,andskewlikebefore,ANDtranslate(notehowthemultiplicationworksout,above)Thisiscalled“homogeneouscoordinates”22-Apr-2331HomogeneoussystemInhomogeneouscoordinates,themultiplicationworksoutsotherightmostcolumnofthematrixisavectorthatgetsadded.Generally,ahomogeneoustransformationmatrixwillhaveabottomrowof[001],sothattheresulthasa“1”atthebottomtoo.22-Apr-2332HomogeneoussystemOnemorethingwemightwant:todividetheresultbysomethingForexample,wemaywanttodividebyacoordinate,tomakethingsscaledownastheygetfartherawayinacameraimageMatrixmultiplicationcan’tactuallydivideSo,byconvention,inhomogeneouscoordinates,we’lldividetheresultbyitslastcoordinateafterdoingamatrixmultiplication22-Apr-23332DTranslationtPP’22-Apr-233422-Apr-23352DTranslationusingHomogeneousCoordinatesPxytxtyP’ttPScalingPP’22-Apr-2336ScalingEquationPxysxxP’sy

y22-Apr-2337PP’=S∙PP’’=T∙P’P’’=T∙P’=T∙(S∙P)=T∙S∙P=A∙

PScaling&TranslatingP’’22-Apr-2338Scaling&TranslatingA22-Apr-2339Translating&Scaling

!=Scaling&Translating22-Apr-2340RotationPP’22-Apr-2341RotationEquationsCounter-clockwiserotationbyananglePxy’P’x’y22-Apr-2342RotationMatrixPropertiesTransposeofarotationmatrixproducesarotationintheoppositedirectionTherowsofarotationmatrixarealwaysmutuallyperpendicular(a.k.a.orthogonal)unitvectors(andsoareitscolumns)22-Apr-2343PropertiesA2Drotationmatrixis2x2Note:Rbelongstothecategoryofnormalmatricesandsatisfiesmanyinterestingproperties:22-Apr-2344Rotation+Scaling+TranslationP’=(TRS)P22-Apr-2345Thisistheformofthegeneral-purposetransformationmatrixOutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm22-Apr-2346TheinverseofatransformationmatrixreversesitseffectGivenamatrixA,itsinverseA-1

isamatrixsuchthatAA-1=A-1A=IE.g.Inversedoesnotalwaysexist.IfA-1exists,Aisinvertibleornon-singular.Otherwise,it’ssingular.Usefulidentities,formatricesthatareinvertible:22-Apr-2347InversePseudoinverseSayyouhavethematrixequationAX=B,whereAandBareknown,andyouwanttosolveforXYoucoulduseMATLABtocalculatetheinverseandpremultiplybyit:A-1AX=A-1B→X=A-1BMATLABcommandwouldbeinv(A)*BButcalculatingtheinverseforlargematricesoftenbringsproblemswithcomputerfloating-pointresolution(becauseitinvolvesworkingwithverysmallandverylargenumberstogether).Or,yourmatrixmightnotevenhaveaninverse.22-Apr-2348MatrixOperationsPseudoinverseFortunately,thereareworkaroundstosolveAX=Binthesesituations.AndMATLABcandothem!Insteadoftakinganinverse,directlyaskMATLABtosolveforXinAX=B,bytypingA\BMATLABwilltryseveralappropriatenumericalmethods(includingthepseudoinverseiftheinversedoesn’texist)MATLABwillreturnthevalueofXwhichsolvestheequationIfthereisnoexactsolution,itwillreturntheclosestoneIftherearemanysolutions,itwillreturnthesmallestone22-Apr-2349MatrixOperationsMATLABexample:22-Apr-2350MatrixOperations>>x=A\Bx=1.0000-0.5000OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm22-Apr-2351Therankofatransformationmatrixtellsyouhowmanydimensionsittransformsavectorto.LinearindependenceSupposewehaveasetofvectorsv1,…,vnIfwecanexpressv1asalinearcombinationoftheothervectorsv2…vn,thenv1islinearlydependentontheothervectors.Thedirectionv1canbeexpressedasacombinationofthedirectionsv2…vn.(E.g.v1=.7

v2-.7

v4)Ifnovectorislinearlydependentontherestoftheset,thesetislinearlyindependent.Commoncase:asetofvectorsv1,…,vnisalwayslinearlyindependentifeachvectorisperpendiculartoeveryothervector(andnon-zero)22-Apr-2352LinearindependenceNotlinearlyindependent22-Apr-2353LinearlyindependentsetMatrixrankColumn/rowrankColumnrankalwaysequalsrowrankMatrixrank22-Apr-2354MatrixrankFortransformationmatrices,theranktellsyouthedimensionsoftheoutputE.g.ifrankofAis1,thenthetransformation

p’=Ap

mapspointsontoaline.Here’samatrixwithrank1:22-Apr-2355Allpointsgetmappedtotheliney=2xMatrixrankIfanmxmmatrixisrankm,wesayit’s“fullrank”Mapsanmx1vectoruniquelytoanothermx1vectorAninversematrixcanbefoundIfrank<m,wesayit’s“singular”Atleastonedimensionisgettingcollapsed.NowaytolookattheresultandtellwhattheinputwasInversedoesnotexistInversealsodoesn’texistfornon-squarematrices22-Apr-2356OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm22-Apr-2357SVDisanalgorithmthatrepresentsanymatrixastheproductof3matrices.Itisusedtodiscoverinterestingstructureinamatrix.SingularValueDecomposition(SVD)Thereareseveralcomputeralgorithmsthatcan“factor”amatrix,representingitastheproductofsomeothermatricesThemostusefuloftheseistheSingularValueDecomposition.RepresentsanymatrixAasaproductofthreematrices:UΣVTMATLABcommand:[U,S,V]=svd(A)22-Apr-2358SingularValueDecomposition(SVD)

UΣVT=AWhereUandVarerotationmatrices,andΣisascalingmatrix.Forexample:22-Apr-2359SingularValueDecomposition(SVD)Beyond2D:Ingeneral,ifAismxn,thenUwillbemxm,Σwillbemxn,andVTwillbenxn.(Notethedimensionsworkouttoproducemxnaftermultiplication)22-Apr-2360SingularValueDecomposition(SVD)UandVarealwaysrotationmatrices.Geometricrotationmaynotbeanapplicableconcept,dependingonthematrix.Sowecallthem“unitary”matrices–eachcolumnisaunitvector.ΣisadiagonalmatrixThenumberofnonzeroentries=rankofAThealgorithmalwayssortstheentrieshightolow22-Apr-2361SVD

ApplicationsWe’vediscussedSVDintermsofgeometrictransformationmatricesButSVDofanimagematrixcanalsobeveryusefulTounderstandthis,we’lllookatalessgeometricinterpretationofwhatSVDisdoing22-Apr-2362SVD

ApplicationsLookathowthemultiplicationworksout,lefttoright:Column1ofUgetsscaledbythefirstvaluefromΣ.Theresultingvectorgetsscaledbyrow1ofVTtoproduceacontributiontothecolumnsofA22-Apr-2363SVD

ApplicationsEachproductof(columniofU)∙(valueifromΣ)∙(rowiofVT)producesacomponentofthefinalA.22-Apr-2364+=SVD

ApplicationsWe’rebuildingAasalinearcombinationofthecolumnsof

UUsingallcolumnsofU,we’llrebuildtheoriginalmatrixperfectlyBut,inreal-worlddata,oftenwecanjustusethefirstfewcolumnsofUandwe’llgetsomethingclose(e.g.thefirstApartial,above)22-Apr-2365SVD

ApplicationsWecancallthosefirstfewcolumnsof

UthePrincipalComponentsofthedataTheyshowthemajorpatternsthatcanbeaddedtoproducethecolumnsoftheoriginalmatrixTherowsofVTshowhowtheprincipalcomponentsaremixedtoproducethecolumnsofthematrix22-Apr-2366SVD

ApplicationsWecanlookatΣtoseethatthefirstcolumnhasalargeeffect22-Apr-2367whilethesecondcolumnhasamuchsmallereffectinthisexampleSVD

Applications22-Apr-2368Forthisimage,usingonlythefirst10of300principalcomponentsproducesarecognizablereconstructionSo,SVDcanbeusedforimagecompressionPrincipalComponentAnalysisRemember,columnsof

UarethePrincipalComponentsofthedata:themajorpatternsthatcanbeaddedtoproducethecolumnsoftheoriginalmatrixOneuseofthisistoconstructamatrixwhereeachcolumnisaseparatedatasampleRunSVDonthatmatrix,andlookatthefirstfewcolumnsofUtoseepatternsthatarecommonamongthecolumnsThisiscalledPrincipalComponentAnalysis(orPCA)ofthedatasamples22-Apr-2369PrincipalComponentAnalysisOften,rawdatasampleshavealotofredundancyandpatternsPCAcanallowyoutorepresentdatasamplesasweightsontheprincipalcomponents,ratherthanusingtheoriginalrawformofthedataByrepresentingeachsampleasjustthoseweights,youcanrepresentjustthe“meat”ofwhat’sdifferentbetweensamples.Thisminimalrepresentationmakesmachinelearningandotheralgorithmsmuchmoreefficient22-Apr-2370OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm22-Apr-2371ComputerscancomputeSVDveryquickly.We’llbrieflydiscussthealgorithm,forthosewhoareinterested.Addendum:HowisSVDcomputed?Forthisclass:tellMATLABtodoit.Usetheresult.But,ifyou’reinterested,onecomputeralgorithmtodoitmakesuseofEigenvectorsThefollowingmaterialispresentedtomakeSVDlessofa“magicalblackbox.”ButyouwilldofineinthisclassifyoutreatSVDasamagicalblackbox,aslongasy