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

《斯坦福机器视觉ppt课件.pptx》由会员分享，可在线阅读，更多相关《斯坦福机器视觉ppt课件.pptx（77页珍藏版）》请在三一办公上搜索。

1、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/s

2、ee/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 An

3、alysis (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)Compute

4、r 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 transp

5、ose 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 us

6、e 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

7、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 coor

8、dinates. 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:AdditionScal

9、ingDot 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 vecto

10、rs 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 entr

11、y 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 co

12、rresponding 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-N

13、ov-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.)Properti

14、es:,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 Matrice

15、s,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 (P

16、CA)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 t

17、he 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

18、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 h

19、appens 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 rota

20、ted 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

21、 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 matri

22、x: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

23、” 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 ma

24、trix 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 coor

25、dinate, 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

26、-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,4

27、0,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) u

28、nit 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 transfor

29、mation 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

30、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,I

31、nverse,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 wi

32、th 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 the

33、m!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 ret

34、urn 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 coordinatesTra

35、nslationMatrix 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

36、 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

37、, 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 rankColu

38、mn 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,M

39、atrix 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 exis

40、tInverse 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

41、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

42、 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.

43、 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 rotati

44、on 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,We

45、ve 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 ge

46、ts 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 build

47、ing 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 f

48、irst 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 th

49、at 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,Prin

50、cipal 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