12/7/2001 CS 461, Copyright G.D. HagerComputer Vision, Week 11Professor Hagerhttp://www.cs.jhu.edu/~hager12/7/2001 CS 461, Copyright G.D. HagerOutline for TodayObject recognition overviewImage-based object recognition12/7/2001 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/7/2001 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/7/2001 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/7/2001 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: ??12/7/2001 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 view12/7/2001 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 images12/7/2001 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/7/2001 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*j12/7/2001 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/7/2001 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.12/7/2001 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/7/2001 CS 461, Copyright G.D. HagerAn example: input images12/7/2001 CS 461, Copyright G.D. HagerAn example: basis images12/7/2001 CS 461, Copyright G.D. HagerAn example: surfaces of first 3 coefficients12/7/2001 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/7/2001 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.12/7/2001 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/7/2001 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:12/7/2001 CS 461, Copyright G.D. HagerWe Interpret Line Drawings As 3D• We have strong intuitions about line drawings of simple geometric figures:– We can detect possible 3D objects (although our information is coming from a 2D line drawing).– We can detect the convexity or concavity of lines in the drawing.– If a line is convex, we have