CSE152, Spr 07 Intro Computer VisionRecognition IIntroduction to Computer VisionCSE 152Lecture 19CSE152, Spr 07 Intro Computer VisionAnnouncements• HW 4 assigned.• 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 of objects and an image determine what, if any of the objects are present in the image.CSE152, 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 VisionFaceCamelBugHuman/FelixQuadrupedBarbaraSteeleProblem:Recognizing instancesRecognizing categoriesCSE152, 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 VisionA Rough Recognition SpectrumAppearance-BasedRecognition(Eigenface, Fisherface)Local Features +Spatial Relations3-DModel-BasedRecognitionGeometricInvariantsImageAbstractions/ Volumetric PrimitivesShape ContextsFunctionAspect GraphsIncreasing GeneralityCSE152, Spr 07 Intro Computer VisionAppearance-Based Vision:A Pattern Classification Viewpoint1. Feature Space + Nearest Neighbor2. Dimensionality Reduction3. Bayesian Classification4. Appearance ManifoldsCSE152, 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 VisionPattern Classification Summary• Supervised vs. Unsupervised: Do we have labels?• Supervised– Nearest Neighbor – Bayesian• Plug in classifier• Distribution-based• Projection Methods (Fisher’s, LDA)– Neural Network– Support Vector Machine– Kernel methods• Unsupervised– Clustering– Reinforcement learningCSE152, 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 VisionComments• Sometimes called “Template Matching”• Variations on distance function (e.g. L1, robust distances)• Multiple templates per class- perhaps many training images per class.• Expensive to compute k distances, especially when each image is big (N dimensional).• May not generalize well to unseen examples of class.• No worse than twice the error rate of the optimal classifier -- if enough training samples• Some solutions:– Bayesian classification– Dimensionality reductionCSE152, 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 VisionEigenfaces: Training Images[ Turk, Pentland 91]CSE152, Spr 07 Intro Computer VisionEigenfacesMean ImageBasis ImagesCSE152, Spr 07 Intro Computer VisionBasis Images for Variable