1CSE152, Spr 06 Intro Computer VisionRecognition IIIntroduction to Computer VisionCSE 152Lecture 20CSE152, Spr 06 Intro Computer VisionAnnouncements• Assignment 4: Due date extended – Electronic submission: Sunday, June 11, 6:00 PM.– Hardcopy: Monday, June 12, 6:00 PM • Read: Trucco & Verri, Chapter 10 on recognition• Final Exam: Thursday, 6/15, 8:00AMCSE152, Spr 06 Intro Computer VisionRecognitionGiven a database ofobjects and an imagedetermine what, if anyof the objects are present in the image.CSE152, Spr 06 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 06 Intro Computer VisionA Rough Recognition SpectrumAppearance-BasedRecognition(Eigenface, Fisherface)Local Features +Spatial Relations3-DModel-BasedRecognitionGeometricInvariantsImageAbstractions/ Volumetric PrimitivesShape ContextsFunctionAspect GraphsIncreasing GeneralityCSE152, Spr 06 Intro Computer VisionSketch of a Pattern Recognition ArchitectureFeatureExtractionClassificationImage(window)ObjectIdentityFeature Vector2CSE152, Spr 06 Intro Computer VisionExample: Face Detection• Scan window over image.• Classify window as either:– Face– Non-faceClassifierWindowFaceNon-faceCSE152, Spr 06 Intro Computer VisionSketch of a Pattern Recognition ArchitectureFeatureExtractionClassificationImage(window)ObjectIdentityFeature VectorClassificationImage(window)ObjectIdentityFeature VectorNearestNeighborFeatureExtractionClassificationImage(window)ObjectIdentityFeature VectorPCANearestNeighborCSE152, Spr 06 Intro Computer VisionImage as a Feature Vector• Consider an n-pixel image (window) to be a point in an n-dimensional space, x ∈ Rn.• Each pixel value is a coordinate of x.x1x2x3CSE152, Spr 06 Intro Computer VisionSimplest Recognition Scheme••RRjjis an image.••c(Rc(Rjj, I) , I) is Euclidean distance.Nearest NeighborClassifierx1x2x3RR11RR22IICSE152, Spr 06 Intro Computer VisionSketch of a Pattern Recognition ArchitectureFeatureExtractionClassificationImage(window)ObjectIdentityFeature VectorClassificationImage(window)ObjectIdentityFeature VectorNearestNeighborFeatureExtractionClassificationImage(window)ObjectIdentityFeature VectorPCANearestNeighborCSE152, Spr 06 Intro Computer VisionDimensionality Redcution: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?3CSE152, Spr 06 Intro Computer VisionEigenfaces: Principal Component Analysis (PCA)Some details: Use Singular value decomposition, “trick” described in appendix of text to compute basis when n<<dCSE152, Spr 06 Intro Computer VisionPCA ExampleFirst Principal ComponentDirection of Maximum Variancev1μv2MeanCSE152, Spr 06 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 to Eigenspace.2. Perform classification to the projected training images.CSE152, Spr 06 Intro Computer VisionEigenfaces: Training Images[ Turk, Pentland 91CSE152, Spr 06 Intro Computer VisionEigenfacesMean ImageBasis ImagesCSE152, Spr 06 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 Eigenvectors3. [However HW 4, the images are small enough that the direct Eigenvalueapproach will work.]4CSE152, Spr 06 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 06 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 us 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 d<= r, the first d column of U provide the best d-dimensional basis for columns of A in least squares sense.CSE152, Spr 06 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 the mean image μ from each input image, create the data matrix A, and perform (thin) SVD on the data matrix.[][]TTnnniTiiAAaaaaaaaa ==∑=LL21211Tiniixxn)()(11μμrrrr−−=Σ∑=CSE152, Spr 06 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 06 Intro Computer VisionAlternative projectionsCSE152, Spr 06 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