计算机视觉的线性代数引物

1 .Linear Algebra Primer Professor Fei-Fei Li Stanford Vision Lab 23-Sep-14 1 Another, very in-depth linear algebra review from CS229 is available here: http:// cs229.stanford.edu/section/cs229-linalg.pdf And 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

2 .Outline Vectors and matrices Basic Matrix Operations Special Matrices Transformation Matrices Homogeneous coordinates Translation Matrix inverse Matrix rank Singular Value Decomposition (SVD) Use for image compression Use for Principal Component Analysis (PCA) Computer algorithm 23-Sep-14 2

3 .Outline Vectors and matrices Basic Matrix Operations Special Matrices Transformation Matrices Homogeneous coordinates Translation Matrix inverse Matrix rank Singular Value Decomposition (SVD) Use for image compression Use for Principal Component Analysis (PCA) Computer algorithm 23-Sep-14 3 Vectors and matrices are just collections of ordered numbers that represent something: movements in space, scaling factors, pixel brightnesses , etc. We’ll define some common uses and standard operations on them.

4 .Vector A column vector where A row vector where denotes the transpose operation 23-Sep-14 4

5 .Vector We’ll default to column vectors in this class You’ll want to keep track of the orientation of your vectors when programming in MATLAB You can transpose a vector V in MATLAB by writing V’ . (But in class materials, we will always use V T to indicate transpose, and we will use V’ to mean “V prime”) 23-Sep-14 5

6 .Vectors have two main uses Vectors can represent an offset in 2D or 3D space Points are just vectors from the origin 23-Sep-14 6 Data (pixels, gradients at an image keypoint , etc ) can also be treated as a vector Such vectors don’t have a geometric interpretation, but calculations like “distance” can still have value

7 .Matrix A matrix is an array of numbers with size by , i.e. m rows and n columns. If , we say that is square.   23-Sep-14 7

8 .Images 23-Sep-14 8 MATLAB represents an image as a matrix of pixel brightnesses Note that matrix coordinates are NOT Cartesian coordinates. The upper left corner is [ y,x ] = (1,1) =

9 .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 brightnesses Stored as an m × n × 3 matrix 23-Sep-14 9 =

10 .Basic Matrix Operations We will discuss: Addition Scaling Dot product Multiplication Transpose Inverse / pseudoinverse Determinant / trace 23-Sep-14 10

11 .Matrix Operations Addition Can only add a matrix with matching dimensions, or a scalar. Scaling 23-Sep-14 11

12 .Matrix Operations Inner product (dot product) of vectors Multiply corresponding entries of two vectors and add up the result x·y is also |x|| y|Cos ( the angle between x and y ) 23-Sep-14 12

13 .Matrix Operations Inner product (dot product) of vectors If B is a unit vector, then A·B gives the length of A which lies in the direction of B 23-Sep-14 13

14 .Matrix Operations Multiplication The 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 23-Sep-14 14

15 .Matrix Operations Multiplication example: 23-Sep-14 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.

16 .Matrix Operations Powers By convention, we can refer to the matrix product AA as A 2 , and AAA as A 3 , etc. Obviously only square matrices can be multiplied that way 23-Sep-14 16

17 .Matrix Operations Transpose – flip matrix, so row 1 becomes column 1 A useful identity: 23-Sep-14 17

18 .Determinant returns a scalar Represents area (or volume) of the parallelogram described by the vectors in the rows of the matrix For , Properties: 23-Sep-14 18 Matrix Operations

19 .Trace Invariant to a lot of transformations, so it’s used sometimes in proofs. (Rarely in this class though.) Properties: 23-Sep-14 19 Matrix Operations

20 .Special Matrices Identity matrix I Square matrix, 1’s along diagonal, 0’s elsewhere I ∙ [another matrix] = [that matrix] Diagonal matrix Square matrix with numbers along diagonal, 0’s elsewhere A diagonal ∙ [ another matrix] s cales the rows of that matrix 23-Sep-14 20

21 .Special Matrices Symmetric matrix Skew-symmetric matrix 23-Sep-14 21

22 .Outline Vectors and matrices Basic Matrix Operations Special Matrices Transformation Matrices Homogeneous coordinates Translation Matrix inverse Matrix rank Singular Value Decomposition (SVD) Use for image compression Use for Principal Component Analysis (PCA) Computer algorithm 23-Sep-14 22 Matrix multiplication can be used to transform vectors. A matrix used in this way is called a transformation matrix.

23 .Transformation Matrices can be used to transform vectors in useful ways, through multiplication : x’= Ax Simplest is scaling: (Verify to yourself that the matrix multiplication works out this way) 23-Sep-14 23

24 .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 frame’s x axis, component in direction of y axis] 23-Sep-14 24

25 .Rotation So to rotate it we must produce this vector: [component in direction of new x axis, component in direction of new y axis] We can do this easily with dot products! New x coordinate is [original vector] dot [the new x axis] New y coordinate is [ original vector] dot [the new y axis] 23-Sep-14 25

26 .Rotation Insight: this is what happens in a matrix*vector multiplication Result x coordinate is [original vector] dot [matrix row 1] So matrix multiplication can rotate a vector p: 23-Sep-14 26

27 .Rotation Suppose we express a point in a coordinate system which is rotated left If we use the result in the same coordinate system, we have rotated the point right 23-Sep-14 27 Thus, rotation matrices can be used to rotate vectors. We’ll usually think of them in that sense-- as operators to rotate vectors

28 .2D Rotation Matrix Formula Counter-clockwise rotation by an angle  P x y’ P’  x’ y 23-Sep-14 28

29 .Transformation Matrices Multiple transformation matrices can be used to transform a point: p’=R 2 R 1 S p The effect of this is to apply their transformations one after the other, from right to left . In the example above, the result is ( R 2 (R 1 (S p))) The result is exactly the same if we multiply the matrices first, to form a single transformation matrix: p ’=(R 2 R 1 S) p 23-Sep-14 29