Lecture 3: Variable signalP. PeronaCalifornia Institute of TechnologyEE/CNS148 - Spring 20051 IntroductionIn Lecture 2 we have learned ab out matched filtering. We made a number ofhypotheses, including that the ‘signal’ is constant, even if it is possibly corruptedby noise.Two questions arise: how do we estimate the signal from noisy examples?(Simple answer: average the examples). What do we do when the signal is notconstant? The answer to this second question is more complicated and dependson the source of variability.There are many reasons why the signal may not be constant:1. The object is rotated/translated in space so that its image appears rotatedand scaled in the image plane.2. The object is in a different p osition in the image.3. The object (class) is inherently non-constant (e.g. cars, human faces).4. The lighting conditions change.5. There is occlusion.In this lecture we learn a te chnique, principal component analysis (PCA),that allows us to account for changes in the object appearance that are due tochanges in lighting, and some limited amount of intrinsic variation (e.g. faces).In future lectures we will learn how to handle large amounts of intrinsicvariation (e.g. cars), occlusion and rotations in depth (i.e. not around theoptical axis of the camera) using deformable models.Variations in orientation around the optical axis of the came ra (i.e. causinga rotation of the image of the object in the image plane), translation and scalewill b e handled ‘brute force’, i.e. the training images will have to be normal-ized (translated, rotated, stretched) by hand so that the training examples arealigned one to the other and the process of object detection and recognitionwill have to be performed on different copies of the images: rotated and scaledversions of the original image. We have encountered one example of such ‘bruteforce’ detection in Lecture 2 when we used convolution to dete ct the presenceof an object in an unknown location.12 Example 1: Signal variability as an effect ofilluminationThe Lambertian reflectance model, which is valid for certain matte surfaces (e.g.chalk) says that the image I(x, y) of a surface z(x, y) is given by:I(x, y) = < n(x, y), l > (1)n(x, y)T=h∂z∂x,∂z∂y, 1i(q∂z∂x)2+ (∂z∂y)2+ 1(2)Where x and y are the coordinates in the image plane, also corresponding to apoint on the visible surface of the object. n(x, y) is the normal vector to thesurface of the object in the location x, y, and l is the vector that from the samepoint x, y of the surface points towards the light source (the norm of l encodesfor the product of the energy emitted by the light source and the albedo of thesurface).If the light source is a point far from the surface of the object, then l isapproximately constant. We will make this approximation.So: depending on the direction of the light source l we will obtain differentimages even if the scene (i.e. n(x, y)) does not change. We m ay write thisdependency of I from l using the notation I(x, y; l). In principle, since there areinfinite pos itions for the light source we may obtain infinite different images.However, it is possible to show that all these images in the Lambertian casetake a 3-dimensional space.In fact: l is a 3-vector (it has x, y, z components) and therefore it may bewritten as the linear c ombination of three basis vectors: l = α1l1+ α2l2+ α3l3.Therefore I may be written as the linear combination of three ‘basis’ images:I(x, y; l) =Xi= 13αi< n(x, y), li>=Xi= 13αiIi(x, y) (3)Ii(x, y) = < n(x, y), li> (4)where the basis images Iiare images obtained under the lighting li. (See A.Shashua’s article for more details [?]).If the signal may be represented in a 3-dimensional space we may hope tobe able to extend the matched filtering idea by using 3 filters instead of one.More on this later.Is the Lambertian approximation reasonable? There are obvious situationswhere the approximation is clearly not valid. The most obvious ones are :1. Cast shadows and self-shadows are areas of the surface that cannot‘see’ the light source. In other terms, the norm of l goes to zero andtherefore l is not constant any longer.2. Specularities are regions where the surface behaves like a mirror, not likea matte surface. In those places the brightness of the image I depends on2the position of the camera (or the eye) and not only on the position of thelight s ource.3. Close-by light source: in this case l is not constant on the surface.3 Principal component analysisHow can we find out whether a given object produces images that are approxi-mately in 3-space, or whether many more dimensions are necessary?Supp ose that one could only use one kernel, then one would pick the kernelthat maximizes the average product with the observed signals si:k = arg maxkXi< k, si>2= kTSSTkwhere S = [s1. . . sN](here, for simplicity of notation, we think of both k and the sias column vectors).Now notice that A = SSTis a positive semidefinite symmetric matrix.Therefore its eigenvalues are real and semipositive and its eigenvectors are anorthonormal set. Call uithe set of eigenvectors of A (equivalently, they are theleft-eigenvectors of S, and call σithe corresponding eigenvalues. Suppose thatthey are sorted in descending order of magnitude. Then A may be expressed interms of the basis formed by the uiand the maximization has a simple solution:A = SST=XiσiuiuTik = arg maxkkTAk = u1and maxkkTAk = σ1kkk2= σ1Supp ose that we allowed k to belong to a r-dimensional space with r << N .Then the solution would be ki= ui.This procedure is called principal component analysis (or, equivalently, sin-gular value decomposition, check out the svd() function in Matlab) to selectsuitable subspace.4 Representation error and classification errorLet’s briefly go back to the principal components analysis. The representa-tion of the signal is as good as the norm of the first principal values used (seecalculations in class).It has to be remarked that the classification error is not necessarily pro-portional to the representation error - this will be further explored in Lecture4.35 When multidimensional filtering is not suffi-cientConsider the example shown in class (see lecture3.m). The signal is c omposedof two ‘blips’ with variable height and variable mutual position. Observe thatwhen the mutual position of the two blips is highly variable the principal com-ponents (the singular values of the matrix composed of examples) decrease