112/3/2003 CS 461, Copyright G.D. HagerObject Recognition TechniquesProfessor Hagerhttp://www.cs.jhu.edu/~hager12/3/2003 CS 461, Copyright G.D. HagerProblems of Computer Vision: RecognitionGiven a database of objects and an image determine what, if any of the objects are present in the image.212/3/2003 CS 461, Copyright G.D. HagerProblems of Computer Vision: RecognitionGiven a database ofobjects and an imagedetermine what, if anyof the objects are present in the image.12/3/2003 CS 461, Copyright G.D. HagerProblems of Computer Vision: RecognitionGiven a database ofobjects and an imagedetermine what, if anyof the objects are present in the image.312/3/2003 CS 461, Copyright G.D. HagerObject 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)The object recognition conundrumPose Est.(where is it 3D)12/3/2003 CS 461, Copyright G.D. HagerObject Recognition Issues:• How general is the problem?– 2D vs. 3D– range of viewing conditions– available context– segmentation cues• What sort of data is best suited to the problem?– local 2D features– 3D surfaces– images• How many objects are involved?– small: brute force search– large: ??412/3/2003 CS 461, Copyright G.D. HagerObject Recognition Approaches• Interpretation trees:– use features– compute “local constraints”• Invariants:– use features– compute “global indices” that do not change over viewing conditions• Image-based:– store information about every possible view• intensities•histograms• Semi-local:– use features– use stable (but not invariant) measures on groups of features to index views12/3/2003 CS 461, Copyright G.D. HagerImage-based Object RecognitionAn observation:If we have seen an object from every viewpoint and under all lighting conditions, then object recognition is “simply” a table lookup in the space of 2D imagesAnother way to view it:Consider an image as a point in a spaceConsider now all points generated as aboveThen, an object is some “surface” in the spaceof all images512/3/2003 CS 461, Copyright G.D. HagerImage-based Object RecognitionAn observation:If we have seen an object from every viewpoint and under all lighting conditions, then objectrecognition is simply a table lookup (given segmentation)The problem is:Images are bigViewing conditions are infiniteComputers are finiteObjects are surrounded by other objectsTherefore:We need to compress the dataWe need to keep the search simpleWe need a means of segmenting out potential objects128x128 image = 214 bytes/image128 directions, 16 illuminants = 211 casesTherefore, 225bytes of storage: 32 Mb/object12/3/2003 CS 461, Copyright G.D. HagerImage-based Object Recognition• How should we compare objects?– recall image cross-correlationc(I1,I2) = 1/K sumi,jI1(i,j) I2(i,j) = 1/K vec(I1) • vec(I2)• But, we don’t want brightness or contrast to enter in, so define–I* = vec((I –uI)/||I – uI||) (think of this as a zero-mean, unit norm vector)• And then, an interesting fact:– let X = [I*1, I*2, ..., I*N]–let eibe the eigenvectors of XXt (or the singular values of X)– then I*j= sumj<Ngi,jejwhere gij= ei• I*j612/3/2003 CS 461, Copyright G.D. HagerImage-based Object Recognition• In practice, we don’t need all of the eigenvectors (there are atmost N), so– let X = [I*1, I*2, ..., I*N]–let eibe the eigenvectors of XXt– then I*j~sum j<k, gi,jejwhere gij= ei• I*j and k << N• Finally, note that (letting E be the matrix of eigenvectors)|| I*1-I*2 || = || E g1–E g2 || = (E g1–E g2)t (E g1–E g2)= (g1 –g2)tEtE (g1 –g2)= || g1-g2 ||• Thus, we can represent images in terms of a low (k) dimensional vector g12/3/2003 CS 461, Copyright G.D. HagerImage-based Object Recognition: Assumptions1. Each image contains only one object2. Objects are imaged by a fixed camera under weak perspective3. Images are normalized in size so that the image is the minimum frame enclosing the object.4. The energy of the pixel values in the image is normalized to 1.5. The object is completely visible and unoccluded in all images.712/3/2003 CS 461, Copyright G.D. HagerImage-based Object Recognition: Learning• Gather up all of the images of all objects under all viewing conditions:– segment to contain just the object; sample to common size– subtract the mean of the result from each image– normalize 0 mean images to unit norm– gather all resulting images into a matrix M (for models)• Compute the eigenvalues and eigenvectors of M Mt– we can use SVD to do this!• Retain the k eigenvectors with the largest associated eigenvalues– Usually, choose k such that ,k/ ,1 < where is small (e.g. .05).– Call the resulting matrix E (for eigenvalue projection).• Store a vectors Co = {goi = EtI0i } for each image i of object o12/3/2003 CS 461, Copyright G.D. HagerAn example: input images812/3/2003 CS 461, Copyright G.D. HagerAn example: basis images12/3/2003 CS 461, Copyright G.D. HagerAn example: surfaces of first 3 coefficients912/3/2003 CS 461, Copyright G.D. HagerImage-based Object Recognition: Identification• Prepare image– segment object from background– resample to be same size as model images– subtract model mean– normalize to unit norm• Compute g* = E I where I is the result of the previous step• Locate argmino ming C|| g – g*||– there are faster techniques (e.g. k-d trees) for doing this• Return O as the identification of the object– as a side effect, return the pose (and lighting if desired) of the object12/3/2003 CS 461, Copyright G.D. HagerAn Example• Columbia SLAM system:– can handle databases of 100’s of objects– single change in point of view– uniform lighting conditionsCourtesy Shree Nayar, Columbia U.1012/3/2003 CS 461, Copyright G.D. HagerImage-based Object Recognition: Limitations• Hard to get all of the samples needed.• Better for Lambertian; less so for specular objects• Assumes a constant background or good segmentation12/3/2003 CS 461, Copyright G.D. HagerConstraint-Based Approaches• Use constraints available on image features to recognize it• A good starter is the Huffman and Clowes line interpretation algorithm:1112/3/2003 CS 461, Copyright G.D. HagerWe Interpret Line Drawings As 3D• We have strong intuitions about line drawings of simple