PCA-based Object RecognitionTextbook: T&V Section 10.4Slide material:Octavia Camps, PSUS. Narasimhan, CMUTemplate MatchingObjects can be represented by Objects can be represented by storing sample images or storing sample images or ““templatestemplates””Stop sign templateStop sign templateHypotheses fromTemplate Matching••Place the template at every Place the template at every location on the given image.location on the given image.••Compare the pixel values in Compare the pixel values in the template with the pixel the template with the pixel values in the underlying region values in the underlying region of the image.of the image.••If a If a ““goodgood””match is found, match is found, announce that the object is announce that the object is present in the image.present in the image.••Possible measures are: SSD, Possible measures are: SSD, SAD, CrossSAD, Cross--correlation, correlation, Normalized CrossNormalized Cross--correlation, correlation, max difference, etc.max difference, etc.Limitations of Template Matching• If the object appears scaled, rotated, or skewed on the image, the match will not be good.Solution:• Search for the template and possible transformations of the template:Not very efficient! (but doable Not very efficient! (but doable ……))Using Eigenspaces• The appearance of an object in an image depends on several things:– Viewpoint– Illumination conditions– Sensor– The object itself (ex: human facial expression)• In principle, these variations can be handled by increasing the number of templates.Eigenspaces: Using multiple templates•Observation: while each template is different, there exist many similarities between the templates.••The number of templates can grow very fast!The number of templates can grow very fast!••We need:We need:••An efficient way to store templatesAn efficient way to store templates••An efficient way to search for matchesAn efficient way to search for matchesEfficient Image StorageToy Example: Images with 3 pixelsToy Example: Images with 3 pixelsConsider the following 3x1 templates:Consider the following 3x1 templates:1122332244664488121233669955101015156612121818If each pixel is stored in a byte, we need 18 = 3 x 6 bytesIf each pixel is stored in a byte, we need 18 = 3 x 6 bytesEfficient Image StorageLooking closer, we can see that all the images are very Looking closer, we can see that all the images are very similar to each other: they are all the same image, scaled similar to each other: they are all the same image, scaled by a factor:by a factor:1122334488121233669955101015156612121818= 1 *= 1 *112233= 4 *= 4 *112233= 3 *= 3 *112233= 5 *= 5 *112233= 6 *= 6 *224466= 2 *= 2 *112233112233Efficient Image Storage1122334488121233669955101015156612121818= 1 *= 1 *112233= 4 *= 4 *112233= 3 *= 3 *112233= 5 *= 5 *112233= 6 *= 6 *224466= 2 *= 2 *112233112233They can be stored using only 9 bytes (50% savings!):They can be stored using only 9 bytes (50% savings!):Store one image Store one image (3 bytes)(3 bytes)+ the multiplying constants + the multiplying constants (6 bytes)(6 bytes)Geometrical Interpretation:Consider each pixel in the image as a coordinate in a Consider each pixel in the image as a coordinate in a vector space. Then, each 3x1 template can be thought of vector space. Then, each 3x1 template can be thought of as a point in a 3D space:as a point in a 3D space:p1p1p2p2p3p3But in this example, all the points happen to belong to a But in this example, all the points happen to belong to a line: a 1D subspace of the original 3D space.line: a 1D subspace of the original 3D space.Geometrical Interpretation:Consider a new coordinate system where one of the axes Consider a new coordinate system where one of the axes is along the direction of the line:is along the direction of the line:p1p1p2p2p3p3In this coordinate system, every image has In this coordinate system, every image has only oneonly onenonnon--zero coordinate: zero coordinate: we we onlyonlyneed to store the direction of the line need to store the direction of the line (a 3 bytes image)(a 3 bytes image)and the and the nonnon--zero coordinate for each of the images zero coordinate for each of the images (6 bytes).(6 bytes).Linear Subspaces• Classification can be expensive– Must either search (e.g., nearest neighbors) or store large probability density functions.• Suppose the data points are arranged as above– Idea—fit a line, classifier measures distance to lineconvert x into v1, v2coordinatesWhat does the v2coordinate measure?What does the v1coordinate measure?- distance to line- use it for classification—near 0 for orange pts- position along line- use it to specify which orange point it isDimensionality Reduction• Dimensionality reduction– We can represent the orange points with onlytheir v1coordinates• since v2coordinates are all essentially 0– This makes it much cheaper to store and compare points– A bigger deal for higher dimensional problemsLinear SubspacesConsider the variation along direction vamong all of the orange points:What unit vector v minimizes var?What unit vector v maximizes var?Solution:v1is eigenvector of A with largest eigenvaluev2is eigenvector of A with smallest eigenvaluePrincipal Component Analysis(PCA)• Given a set of templates, how do we know if they can be compressed like in the previous example?– The answer is to look into the correlation between the templates– The tool for doing this is called PCAPCA TheoremLet xLet x11xx22……xxnnbe a set of n Nbe a set of n N22x 1 vectors and let x be x 1 vectors and let x be their average:their average:Note:Note:Each N x N image template can be represented Each N x N image template can be represented as a Nas a N22x 1 vector whose elements are the template x 1 vector whose elements are the template pixel values.pixel values.PCA TheoremLet X be the NLet X be the N22x n matrix with columns xx n matrix with columns x1 1 --x, xx, x22––x,x,……xxnn––x :x :Note:Note:subtracting the mean is equivalent to translating subtracting the mean is equivalent to translating the coordinate system to the location of the mean.the coordinate system to the location of the mean.PCA TheoremLet Q = X XLet Q = X XTTbe the Nbe the N22x Nx N22matrix:matrix:Notes:Notes:1.1.Q is square Q is square 2.2.Q is symmetricQ is symmetric3.3.Q is the Q is the covariancecovariancematrix [matrix [akaakascatter matrix]scatter