斯坦福机器视觉ppt课件.pptx

Linear Algebra Primer,Professor Fei-Fei LiStanford Vision Lab,11-Nov-22,1,Another, very in-depth linear algebra review from CS229 is available here:http:/cs229.stanford.edu/section/cs229-linalg.pdfAnd a video discussion of linear algebra from EE263 is here (lectures 3 and 4):http:/see.stanford.edu/see/lecturelist.aspx?coll=17005383-19c6-49ed-9497-2ba8bfcfe5f6,Outline,Vectors and matricesBasic Matrix OperationsSpecial MatricesTransformation MatricesHomogeneous coordinatesTranslationMatrix inverseMatrix rankSingular Value Decomposition (SVD)Use for image compressionUse for Principal Component Analysis (PCA)Computer algorithm,11-Nov-22,2,Outline,Vectors and matricesBasic Matrix OperationsSpecial MatricesTransformation MatricesHomogeneous coordinatesTranslationMatrix inverseMatrix rankSingular Value Decomposition (SVD)Use for image compressionUse for Principal Component Analysis (PCA)Computer algorithm,11-Nov-22,3,Vectors and matrices are just collections of ordered numbers that represent something: movements in space, scaling factors, pixel brightnesses, etc. Well define some common uses and standard operations on them.,Vector,A column vector whereA row vector where denotes the transpose operation,11-Nov-22,4,Vector,Well default to column vectors in this classYoull want to keep track of the orientation of your vectors when programming in MATLABYou can transpose a vector V in MATLAB by writing V. (But in class materials, we will always use VT to indicate transpose, and we will use V to mean “V prime”),11-Nov-22,5,Vectors have two main uses,Vectors can represent an offset in 2D or 3D spacePoints are just vectors from the origin,11-Nov-22,6,Data (pixels, gradients at an image keypoint, etc) can also be treated as a vectorSuch vectors dont have a geometric interpretation, but calculations like “distance” can still have value,Matrix,A matrix is an array of numbers with size by , i.e. m rows and n columns.If , we say that is square.,11-Nov-22,7,Images,11-Nov-22,8,MATLAB represents an image as a matrix of pixel brightnessesNote that matrix coordinates are NOT Cartesian coordinates. The upper left corner is y,x = (1,1),=,Color Images,Grayscale images have one number per pixel, and are stored as an m n matrix.Color images have 3 numbers per pixel red, green, and blue brightnessesStored as an m n 3 matrix,11-Nov-22,9,=,Basic Matrix Operations,We will discuss:AdditionScalingDot productMultiplicationTransposeInverse / pseudoinverseDeterminant / trace,11-Nov-22,10,Matrix Operations,AdditionCan only add a matrix with matching dimensions, or a scalar. Scaling,11-Nov-22,11,Matrix Operations,Inner product (dot product) of vectorsMultiply corresponding entries of two vectors and add up the resultxy is also |x|y|Cos( the angle between x and y ),11-Nov-22,12,Matrix Operations,Inner product (dot product) of vectorsIf B is a unit vector, then AB gives the length of A which lies in the direction of B,11-Nov-22,13,Matrix Operations,MultiplicationThe product AB is:Each entry in the result is (that row of A) dot product with (that column of B)Many uses, which will be covered later,11-Nov-22,14,Matrix Operations,Multiplication example:,11-Nov-22,15,Each entry of the matrix product is made by taking the dot product of the corresponding row in the left matrix, with the corresponding column in the right one.,Matrix Operations,PowersBy convention, we can refer to the matrix product AA as A2, and AAA as A3, etc.Obviously only square matrices can be multiplied that way,11-Nov-22,16,Matrix Operations,Transpose flip matrix, so row 1 becomes column 1A useful identity:,11-Nov-22,17,Determinant returns a scalarRepresents area (or volume) of the parallelogram described by the vectors in the rows of the matrixFor , Properties:,11-Nov-22,18,Matrix Operations,TraceInvariant to a lot of transformations, so its used sometimes in proofs. (Rarely in this class though.)Properties:,11-Nov-22,19,Matrix Operations,Special Matrices,Identity matrix ISquare matrix, 1s along diagonal, 0s elsewhereI another matrix = that matrixDiagonal matrixSquare matrix with numbers along diagonal, 0s elsewhereA diagonal another matrix scales the rows of that matrix,11-Nov-22,20,Special Matrices,Symmetric matrixSkew-symmetric matrix,11-Nov-22,21,Outline,Vectors and matricesBasic Matrix OperationsSpecial MatricesTransformation MatricesHomogeneous coordinatesTranslationMatrix inverseMatrix rankSingular Value Decomposition (SVD)Use for image compressionUse for Principal Component Analysis (PCA)Computer algorithm,11-Nov-22,22,Matrix multiplication can be used to transform vectors. A matrix used in this way is called a transformation matrix.,Transformation,Matrices can be used to transform vectors in useful ways, through multiplication: x= AxSimplest is scaling:(Verify to yourself that the matrix multiplication works out this way),11-Nov-22,23,Rotation,How can you convert a vector represented in frame “0” to a new, rotated coordinate frame “1”?Remember what a vector is: component in direction of the frames x axis, component in direction of y axis,11-Nov-22,24,Rotation,So to rotate it we must produce this vector: component in direction of new x axis, component in direction of new y axisWe can do this easily with dot products!New x coordinate is original vector dot the new x axisNew y coordinate is original vector dot the new y axis,11-Nov-22,25,Rotation,Insight: this is what happens in a matrix*vector multiplicationResult x coordinate is original vector dot matrix row 1So matrix multiplication can rotate a vector p:,11-Nov-22,26,Rotation,Suppose we express a point in a coordinate system which is rotated leftIf we use the result in the same coordinate system, we have rotated the point right,11-Nov-22,27,Thus, rotation matrices can be used to rotate vectors. Well usually think of them in that sense- as operators to rotate vectors,2D Rotation Matrix Formula,Counter-clockwise rotation by an angle ,P,x,y,P,x,y,11-Nov-22,28,Transformation Matrices,Multiple transformation matrices can be used to transform a point: p=R2 R1 S pThe effect of this is to apply their transformations one after the other, from right to left.In the example above, the result is (R2 (R1 (S p)The result is exactly the same if we multiply the matrices first, to form a single transformation matrix:p=(R2 R1 S) p,11-Nov-22,29,Homogeneous system,In general, a matrix multiplication lets us linearly combine components of a vectorThis is sufficient for scale, rotate, skew transformations.But notice, we cant add a constant! ,11-Nov-22,30,Homogeneous system,The (somewhat hacky) solution? Stick a “1” at the end of every vector:Now we can rotate, scale, and skew like before, AND translate (note how the multiplication works out, above)This is called “homogeneous coordinates”,11-Nov-22,31,Homogeneous system,In homogeneous coordinates, the multiplication works out so the rightmost column of the matrix is a vector that gets added.Generally, a homogeneous transformation matrix will have a bottom row of 0 0 1, so that the result has a “1” at the bottom too.,11-Nov-22,32,Homogeneous system,One more thing we might want: to divide the result by somethingFor example, we may want to divide by a coordinate, to make things scale down as they get farther away in a camera imageMatrix multiplication cant actually divideSo, by convention, in homogeneous coordinates, well divide the result by its last coordinate after doing a matrix multiplication,11-Nov-22,33,2D Translation,t,P,P,11-Nov-22,34,11-Nov-22,35,2D Translation using Homogeneous Coordinates,t,P,Scaling,P,P,11-Nov-22,36,Scaling Equation,P,x,y,sx x,P,sy y,11-Nov-22,37,P,P=SP,P=TP,P=T P=T (S P)= T S P = A P,Scaling & Translating,P,11-Nov-22,38,Scaling & Translating,A,11-Nov-22,39,Translating & Scaling != Scaling & Translating,11-Nov-22,40,Rotation,P,P,11-Nov-22,41,Rotation Equations,Counter-clockwise rotation by an angle ,P,x,y,P,x,y,11-Nov-22,42,Rotation Matrix Properties,Transpose of a rotation matrix produces a rotation in the opposite directionThe rows of a rotation matrix are always mutually perpendicular (a.k.a. orthogonal) unit vectors(and so are its columns),11-Nov-22,43,Properties,A 2D rotation matrix is 2x2,Note: R belongs to the category of normal matrices and satisfies many interesting properties:,11-Nov-22,44,Rotation+ Scaling +Translation,P= (T R S) P,11-Nov-22,45,This is the form of the general-purpose transformation matrix,Outline,Vectors and matricesBasic Matrix OperationsSpecial MatricesTransformation MatricesHomogeneous coordinatesTranslationMatrix inverseMatrix rankSingular Value Decomposition (SVD)Use for image compressionUse for Principal Component Analysis (PCA)Computer algorithm,11-Nov-22,46,The inverse of a transformation matrix reverses its effect,Given a matrix A, its inverse A-1 is a matrix such that AA-1 = A-1A = IE.g.Inverse does not always exist. If A-1 exists, A is invertible or non-singular. Otherwise, its singular.Useful identities, for matrices that are invertible:,11-Nov-22,47,Inverse,PseudoinverseSay you have the matrix equation AX=B, where A and B are known, and you want to solve for XYou could use MATLAB to calculate the inverse and premultiply by it: A-1AX=A-1B X=A-1BMATLAB command would be inv(A)*BBut calculating the inverse for large matrices often brings problems with computer floating-point resolution (because it involves working with very small and very large numbers together). Or, your matrix might not even have an inverse.,11-Nov-22,48,Matrix Operations,PseudoinverseFortunately, there are workarounds to solve AX=B in these situations. And MATLAB can do them!Instead of taking an inverse, directly ask MATLAB to solve for X in AX=B, by typing ABMATLAB will try several appropriate numerical methods (including the pseudoinverse if the inverse doesnt exist)MATLAB will return the value of X which solves the equationIf there is no exact solution, it will return the closest oneIf there are many solutions, it will return the smallest one,11-Nov-22,49,Matrix Operations,MATLAB example:,11-Nov-22,50,Matrix Operations, x = ABx = 1.0000 -0.5000,Outline,Vectors and matricesBasic Matrix OperationsSpecial MatricesTransformation MatricesHomogeneous coordinatesTranslationMatrix inverseMatrix rankSingular Value Decomposition (SVD)Use for image compressionUse for Principal Component Analysis (PCA)Computer algorithm,11-Nov-22,51,The rank of a transformation matrix tells you how many dimensions it transforms a vector to.,Linear independence,Suppose we have a set of vectors v1, , vnIf we can express v1 as a linear combination of the other vectors v2vn, then v1 is linearly dependent on the other vectors. The direction v1 can be expressed as a combination of the directions v2vn. (E.g. v1 = .7 v2 -.7 v4)If no vector is linearly dependent on the rest of the set, the set is linearly independent.Common case: a set of vectors v1, , vn is always linearly independent if each vector is perpendicular to every other vector (and non-zero),11-Nov-22,52,Linear independence,Not linearly independent,11-Nov-22,53,Linearly independent set,Matrix rank,Column/row rankColumn rank always equals row rankMatrix rank,11-Nov-22,54,Matrix rank,For transformation matrices, the rank tells you the dimensions of the outputE.g. if rank of A is 1, then the transformationp=Apmaps points onto a line. Heres a matrix with rank 1:,11-Nov-22,55,All points get mapped to the line y=2x,Matrix rank,If an m x m matrix is rank m, we say its “full rank”Maps an m x 1 vector uniquely to another m x 1 vectorAn inverse matrix can be foundIf rank m, we say its “singular”At least one dimension is getting collapsed. No way to look at the result and tell what the input wasInverse does not existInverse also doesnt exist for non-square matrices,11-Nov-22,56,Outline,Vectors and matricesBasic Matrix OperationsSpecial MatricesTransformation MatricesHomogeneous coordinatesTranslationMatrix inverseMatrix rankSingular Value Decomposition (SVD)Use for image compressionUse for Principal Component Analysis (PCA)Computer algorithm,11-Nov-22,57,SVD is an algorithm that represents any matrix as the product of 3 matrices. It is used to discover interesting structure in a matrix.,Singular Value Decomposition (SVD),There are several computer algorithms that can “factor” a matrix, representing it as the product of some other matricesThe most useful of these is the Singular Value Decomposition.Represents any matrix A as a product of three matrices: UVTMATLAB command: U,S,V=svd(A),11-Nov-22,58,Singular Value Decomposition (SVD),UVT = AWhere U and V are rotation matrices, and is a scaling matrix. For example:,11-Nov-22,59,Singular Value Decomposition (SVD),Beyond 2D:In general, if A is m x n, then U will be m x m, will be m x n, and VT will be n x n. (Note the dimensions work out to produce m x n after multiplication),11-Nov-22,60,Singular Value Decomposition (SVD),U and V are always rotation matrices. Geometric rotation may not be an applicable concept, depending on the matrix. So we call them “unitary” matrices each column is a unit vector. is a diagonal matrixThe number of nonzero entries = rank of AThe algorithm always sorts the entries high to low,11-Nov-22,61,SVD Applications,Weve discussed SVD in terms of geometric transformation matricesBut SVD of an image matrix can also be very usefulTo understand this, well look at a less geometric interpretation of what SVD is doing,11-Nov-22,62,SVD Applications,Look at how the multiplication works out, left to right:Column 1 of U gets scaled by the first value from .The resulting vector gets scaled by row 1 of VT to produce a contribution to the columns of A,11-Nov-22,63,SVD Applications,Each product of (column i of U)(value i from )(row i of VT) produces a component of the final A.,11-Nov-22,64,+,=,SVD Applications,Were building A as a linear combination of the columns of UUsing all columns of U, well rebuild the original matrix perfectlyBut, in real-world data, often we can just use the first few columns of U and well get something close (e.g. the first Apartial, above),11-Nov-22,65,SVD Applications,We can call those first few columns of U the Principal Components of the dataThey show the major patterns that can be added to produce the columns of the original matrixThe rows of VT show how the principal components are mixed to produce the columns of the matrix,11-Nov-22,66,SVD Applications,We can look at to see that the first column has a large effect,11-Nov-22,67,while the second column has a much smaller effect in this example,SVD Applications,11-Nov-22,68,For this image, using only the first 10 of 300 principal components produces a recognizable reconstructionSo, SVD can be used for image compression,Principal Component Analysis,Remember, columns of U are the Principal Components of the data: the major patterns that can be added to produce the columns of the original matrixOne use of this is to construct a matrix where each column is a separate data sampleRun SVD on that matrix, and look at the firs