Face Recognition and Feature SubspacesObject recognitionFace detection and recognitionApplications of Face RecognitionSlide 5Slide 6Consumer application: iPhoto 2009Slide 8Slide 9Starting idea of “eigenfaces”The space of all face imagesSlide 12Principal Component Analysis (PCA)Principal Component AnalysisImplementation issueEigenfaces (PCA on face images)Eigenfaces exampleSlide 18Visualization of eigenfacesRepresentation and reconstructionSlide 21ReconstructionSlide 25NoteRecognition with eigenfacesPCALimitationsSlide 31A more discriminative subspace: FLDSlide 34Slide 35Slide 36Slide 37Slide 38Slide 39Recognition with FLDSlide 41Slide 42Large scale comparison of methodsFVRT ChallengeSlide 46Slide 47Slide 48Face recognition by humansSlide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 59Things to rememberNext classFace Recognition and Feature SubspacesComputer VisionCS 543 / ECE 549 University of IllinoisDerek Hoiem03/09/10Some slides from Lana Lazebnik, Silvio Savarese, Fei-Fei LiObject recognitionLast Class•Object instance recognition: focus on localization of miscellaneous objectsThis class•Face recognition: focus on distinguishing one face from another•Feature subspaces: PCA and FLD•Look at results from recent vendor test•Look at interesting findings about human face recognitionFace detection and recognitionDetection Recognition“Sally”Applications of Face Recognition•Digital photographyApplications of Face Recognition•Digital photography•SurveillanceApplications of Face Recognition•Digital photography•Surveillance•Album organizationConsumer application: iPhoto 2009http://www.apple.com/ilife/iphoto/Consumer application: iPhoto 2009•Can be trained to recognize pets!http://www.maclife.com/article/news/iphotos_faces_recognizes_catsConsumer application: iPhoto 2009•Things iPhoto thinks are facesStarting idea of “eigenfaces”1. Treat pixels as a vector2. Recognize face by nearest neighborxnyy ...1xy Tkkk argminThe space of all face images•When viewed as vectors of pixel values, face images are extremely high-dimensional–100x100 image = 10,000 dimensions–Slow and lots of storage•But very few 10,000-dimensional vectors are valid face images•We want to effectively model the subspace of face imagesThe space of all face images•Eigenface idea: construct a low-dimensional linear subspace that best explains the variation in the set of face imagesPrincipal Component Analysis (PCA)•Given: N data points x1, … ,xN in Rd•We want to find a new set of features that are linear combinations of original ones: u(xi) = uT(xi – µ)(µ: mean of data points)•Choose unit vector u in Rd that captures the most data varianceForsyth & Ponce, Sec. 22.3.1, 22.3.2Principal Component Analysis•Direction that maximizes the variance of the projected data:Projection of data pointCovariance matrix of dataThe direction that maximizes the variance is the eigenvector associated with the largest eigenvalue of ΣNN1/N(show on board)Maximizesubject to ||u||=1Implementation issue •Covariance matrix is huge (N2 for N pixels)•But typically # examples << N•Simple trick–X is matrix of normalized training data–Solve for eigenvectors u of XXT instead of XTX–Then XTu is eigenvector of covariance XTX–May need to normalize (to get unit length vector)Eigenfaces (PCA on face images)1. Compute covariance matrix of face images2. Compute the principal components (“eigenfaces”)–K eigenvectors with largest eigenvalues3. Represent all face images in the dataset as linear combinations of eigenfaces–Perform nearest neighbor on these coefficientsM. Turk and A. Pentland, Face Recognition using Eigenfaces, CVPR 1991Eigenfaces example•Training images•x1,…,xNEigenfaces exampleTop eigenvectors: u1,…ukMean: μVisualization of eigenfacesPrincipal component (eigenvector) ukμ + 3σkukμ – 3σkukRepresentation and reconstruction•Face x in “face space” coordinates:=Representation and reconstruction•Face x in “face space” coordinates:•Reconstruction:= +µ + w1u1+w2u2+w3u3+w4u4+ …=^x =P = 4P = 200P = 400ReconstructionAfter computing eigenfaces using 400 face images from ORL face databaseEigenvalues (variance along eigenvectors)NotePreserving variance (minimizing MSE) does not necessarily lead to qualitatively good reconstruction.P = 200Recognition with eigenfacesProcess labeled training images•Find mean µ and covariance matrix Σ•Find k principal components (eigenvectors of Σ) u1,…uk•Project each training image xi onto subspace spanned by principal components:(wi1,…,wik) = (u1T(xi – µ), … , ukT(xi – µ))Given novel image x•Project onto subspace:(w1,…,wk) = (u1T(x – µ), … , ukT(x – µ))•Optional: check reconstruction error x – x to determine whether image is really a face•Classify as closest training face in k-dimensional subspace^M. Turk and A. Pentland, Face Recognition using Eigenfaces, CVPR 1991PCA•General dimensionality reduction technique•Preserves most of variance with a much more compact representation–Lower storage requirements (eigenvectors + a few numbers per face)–Faster matching•What are the problems for face recognition?LimitationsGlobal appearance method: not robust to misalignment, background variationLimitations•The direction of maximum variance is not always good for classificationA more discriminative subspace: FLD•Fisher Linear Discriminants  “Fisher Faces”•PCA preserves maximum variance•FLD preserves discrimination–Find projection that maximizes scatter between classes and minimizes scatter within classesReference: Eigenfaces vs. Fisherfaces, Belheumer et al., PAMI 1997Comparing with PCAComparing with PCAVariables•N Sample images: •c classes:•Average of each class: •Average of all data: Nxx ,,1 c,,1ikxkiixN1NkkxN11Scatter Matrices•Scatter of class i:  TikxikixxSikciiWSS1  ciTiiiBNS1•Within class scatter:•Between class scatter:Illustration2S1SBS21SSSWx1x2Within class scatterBetween class scatterMathematical Formulation•After projection–Between class scatter–Within class scatter•Objective•Solution: Generalized Eigenvectors•Rank of Wopt is limited–Rank(SB) <= |C|-1–Rank(SW) <= N-CkTkxWy WSWSBTB~WSWSWTW~WSWWSWSSWWTBTWBoptWWmax arg~~max arg miwSwSiWiiB,,1