CSE152, Spr 07 Intro Computer VisionRecognition IIIntroduction to Computer VisionCSE 152Lecture 19CSE152, Spr 07 Intro Computer VisionAnnouncements• HW 4 assigned due friday• It does not require a lot of coding, but doesrequire understandingOrder of material changed – we’ll first cover recognition so that you’re prepared for assignment. Then return to motion.• Final Exam: Wed, 6/13, 3:00PMCSE152, Spr 07 Intro Computer VisionRecognitionGiven a database ofobjects and an imagedetermine what, if anyof the objects are present in the image.CSE152, Spr 07 Intro Computer VisionObject Recognition: The ProblemGiven: A database D of “known” objects and an image I:1. Determine which (if any) objects in D appear in I2. Determine the pose (rotation and translation) of the objectSegmentation(where is it 2D)Recognition(what is it)Pose Est.(where is it 3D)WHAT AND WHERE!!!CSE152, Spr 07 Intro Computer VisionRecognition Challenges• Within-class variability– Different objects within the class have different shapes or different material characteristics–Deformable–Articulated– Compositional• Pose variability: – 2-D Image transformation (translation, rotation, scale)– 3-D Pose Variability (perspective, orthographic projection)• Lighting– Direction (multiple sources & type)–Color– Shadows• Occlusion – partial• Clutter in background -> false positivesCSE152, Spr 07 Intro Computer VisionSketch of a Pattern Recognition ArchitectureFeatureExtractionClassificationImage(window)ObjectIdentityFeature VectorCSE152, Spr 07 Intro Computer VisionExample: Face Detection• Scan window over image.• Search over position & scale.• Classify window as either:–Face– Non-faceClassifierWindowFaceNon-faceCSE152, Spr 07 Intro Computer VisionImage as a Feature Vector• Consider an n-pixel image to be a point in an n-dimensional space, x Rn.• Each pixel value is a coordinate of x.∈x1x2x3CSE152, Spr 07 Intro Computer VisionNearest Neighbor Classifier{ { RRjj} } are set of training images.x1x2x3RR11RR22II),(minarg IRdistIDjj=CSE152, Spr 07 Intro Computer VisionEigenfaces: Linear Projection•An n-pixel image x∈Rncan be projected to a low-dimensional feature space y∈Rmbyy = Wxwhere W is an m by n matrix.• Recognition is performed using nearest neighbor in Rm.• How do we choose a good W?CSE152, Spr 07 Intro Computer VisionEigenfaces: Principal Component Analysis (PCA)CSE152, Spr 07 Intro Computer VisionPCA ExampleFirst Principal ComponentDirection of Maximum Variancev1μv2MeanCSE152, Spr 07 Intro Computer VisionEigenfaces• Modeling1. Given a collection of n labeled training images,2. Compute mean image and covariance matrix.3. Compute k Eigenvectors (note that these are images) of covariance matrix corresponding to k largest Eigenvalues. (Or perform using SVD!!)4. Project the training images to the k-dimensional Eigenspace.• Recognition1. Given a test image, project vectorized image to Eigenspace.2. Perform classification to the projected training images.CSE152, Spr 07 Intro Computer VisionEigenfacesMean ImageBasis ImagesCSE152, Spr 07 Intro Computer VisionFace detection using “distance to face space”• Scan a window ωacross the image, and classify the window as face/not face as follows:• Project window to subspace, and reconstruct as described earlier.•Compute distance between ω and reconstruction.•Local minima of distance over all image locations less than some treshold are taken as locations of faces. •Repeat at different scales.•Possibly normalize windows intensity so that |ω| = 1.CSE152, Spr 07 Intro Computer VisionAnd important footnote: Don’t really implement PCA this way!Why?1. How big is Σ? • n by n where n is the number of pixels in an image!!2. You only need the first k EigenvectorsCSE152, Spr 07 Intro Computer VisionSingular Value Decomposition• Any m by n matrix A may be factored such thatA = UΣVT[m x n] = [m x m][m x n][n x n]• U: m by m, orthogonal matrix– Columns of U are the eigenvectors of AAT• V: n by n, orthogonal matrix, – columns are the eigenvectors of ATA• Σ: m by n, diagonal with non-negative entries (σ1, σ2, …, σs) with s=min(m,n) are called the called the singular values– Singular values are the square roots of eigenvalues of both AATand ATA & Columns of U are corresponding Eigenvectors!!– Result of SVD algorithm: σ1 ≥σ2 ≥ … ≥σsCSE152, Spr 07 Intro Computer VisionSVD Properties• In Matlab [u s v] = svd(A), and you can verify that: A=u*s*v’• r=Rank(A) = # of non-zero singular values.• U, V give an orthonormal bases for the subspaces of A:–1st r columns of U: Column space of A–Last m - r columns of U: Left nullspace of A–1st r columns of V: Row space of A–1st n - r columns of V: Nullspace of A• For some d where d ≤r, the first d column of U provide the best d-dimensional basis for columns of A in least squares sense.CSE152, Spr 07 Intro Computer VisionThin SVD• Any m by n matrix A may be factored such thatA = UΣVT[m x n] = [m x m][m x n][n x n]• If m>n, then one can view Σ as:•Where Σ’=diag(σ1, σ2, …, σs) with s=min(m,n), and lower matrix is (n-m by m) of zeros.• Alternatively, you can write:A = U’Σ’VT• In Matlab, thin SVD is:[U S V] = svds(A)⎥⎦⎤⎢⎣⎡∑0'This is what you should use!!CSE152, Spr 07 Intro Computer VisionPerforming PCA with SVD• Singular values of A are the square roots of eigenvalues of both AATand ATA & Columns of U are corresponding Eigenvectors• And • Covariance matrix is:• So, ignoring 1/n subtract mean image μ from each input image, create data matrix, and perform thin SVD on the data matrix.[][]TTnnkiTiiAAaaaaaaaa ==∑=LL21211Tikiixxn)()(11μμrrrr−−=Σ∑=CSE152, Spr 07 Intro Computer VisionAlternative projectionsCSE152, Spr 07 Intro Computer VisionFisherfaces: Class specific linear projectionP. Belhumeur, J. Hespanha, D. Kriegman, Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection, PAMI, July 1997, pp. 711--720.•An n-pixel image x∈Rncan be projected to a low-dimensional feature space y∈Rmbyy = Wxwhere W is an n by m matrix.• Recognition is performed using nearest neighbor in Rm.• How do we choose a good W?CSE152, Spr 07 Intro Computer VisionPCA & Fisher’s Linear Discriminant • Between-class scatter• Within-class scatter• Total scatter•Where– c is the number of classes– μiis the mean of class χi–| χi| is number of samples