11/30/2001 CS 461, Copyright G.D. HagerComputer Vision, Week 12Professor Hagerhttp://www.cs.jhu.edu/~hager11/30/2001 CS 461, Copyright G.D. HagerOutline for This WeekObject recognition finish upPose estimation in 2D and 3D11/30/2001 CS 461, Copyright G.D. HagerProject issues• For Monday (I’ll round up), submit:– matlab functions plus script that execute on simulated data (also supplied to us)– Short write-up describing progress• If you are having trouble, come and see us now!11/30/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 view11/30/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 images11/30/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:11/30/2001 CS 461, Copyright G.D. HagerConvexity Labeling Conventions1. A line labeled plus (+) indicates that the corresponding edge is convex ;2. A line labeled minus (-) indicates that the corresponding edge is concave;3. An arrow indicates an occluding edge. To its right is the body for which the arrow line provides an edge. On its left is space.(liberally borrowed from Embick and Marcus)11/30/2001 CS 461, Copyright G.D. HagerThe Top Three Levels of a Search TreeA1 A3A2A1L1A1L5A2L3A3L6(liberally borrowed from Embick and Marcus)11/30/2001 CS 461, Copyright G.D. HagerInterpretation Trees: Basic Idea• Given: – A (usually 3D geometric) model, we a set of features and definedrelationships between features F1, F2, ... Fn• unary: e.g. length range• binary: e.g. distance range• trinary: e.g. angle between triples of points– An observed set of features f1, f2, .... fm•Compute:– all possible matches between model features and observed features which respect the given constraints.11/30/2001 CS 461, Copyright G.D. HagerConstraints: Examples• Length (line)–| F2,2| = d2,2, ....• Distance (line to line)– |F_{2,2} – F_{2,1}| = [dmin_{2,1},dmax_{2,1}]• Distance (vertex to line)– |F_{2,3} – v_{2,1}| = [dmin_{2,3},dmax_{2,3}]• Angle (line to line)– |F_{2,2} . F_{2,1}| = a_{2,1}• Area (face)– ......F2,3F2,2F2,1v2,111/30/2001 CS 461, Copyright G.D. HageranglesF1 F2 F3 F4 F5 F6F1 0 3π/20 3π/2 π π/2F2 π/2 0 π/2 0 3π/2 πF3 0 3π/20 3π/2 π π/2F4 π/2 0 π/2 0 3π/2πF5 π π/2 π π/2 0 3π/2F6 3π/2 π 3π/2π π/2 0anglesf1 f2 f3f1 0 π/2 πf2 3π/2 0 π/2f3 π 3π/2 0distancef1 f2 f3f1 [0,1] [1,5] [1,2]f2 [1,5] [0,1] [1,5]f3 [1,2] [1,5] [0,1]distanceF1 F2 F3 F4 F5 F6F1 [0,1] [0,5] [4,8] [5,13] [9,13] [0,10]F2 [0,5] [0,4] [0,5] [1,10] [1,10] [1,10]F3 [4,8] [0,5] [0,1] [0,2] [1,5] [1,8]F4 [5,13] [1,10] [0,2] [0,1] [0,5] [4,13]F5 [9,13] [1,10] [1,5] [0,5] [0,4] [0,13]F6 [0,10] [1,10] [1,8] [4,13] [0,13] [0,9]F1F2F3F4F5F6f3f2f111/30/2001 CS 461, Copyright G.D. HagerInterpretation Tree: a 2D ExampleF1,1F2,1F1,4F1,3F1,2F2,3F2,2f3f2f1f1F1,1F1,2. . . .F2,2F2,1f2F1,2f2F1,3. . . .Xf2F2,2XXf3F2,311/30/2001 CS 461, Copyright G.D. HagerInterpretation Tree: Wild CardsF1,1F2,1F1,4F1,3F1,2F2,3F2,2f3f2f1f1F1,1F1,2. . . .F2,2F2,1f2F1,2f2F1,3. . . .Xf2F2,2XXf3F2,3f4f4* Allows a match to anything11/30/2001 CS 461, Copyright G.D. HagerAn IT AlgorithmIT(Open,Maxsize,Interp) While (Open ¬= {})pop X = (fj,mk) from Openif (leaf(X))if (verify({X,Interp}))save {X,Interp};Maxsize = size({X,Interp});elseif (consistent (X,anc(X)) & min(N-j,M-length(path(X))) >= Maxsizeadd X to Interpadd {(fj+1,mi); minot on path(X)} to OpenMaxsize = IT(Open,Maxsize)return MaxsizeIT({(null,null)},0)11/30/2001 CS 461, Copyright G.D. HagerLimitations of ITs• Fundamentally, a combinatorial approach to matching• If *s are allowed (and they must be), increases the combinatorics, and also increases ambiguity – how many *’d features should we included in an interpretation– is fewer *’d feature necessarily better• Unary or Binary constraints are not enough to always generate a unique or consistent match• Depends on Euclidean invariants (at least as presented)11/30/2001 CS 461, Copyright G.D. HagerInvariantsBasic definitions:features ftransformations TI is an invariant if I(f) = I(T f) for all TExamples:f are pairs of points, T is translation, I(p1,p2) = p1-p2f are pairs of points, T is homogeneous transform I(p1,p2) = p1· p2These are example of Euclidean invariantsIf T is a projective transformation, then I is a projective invariantIf points are on a plane, then k p = k (u,v,1)’= T P = T (X,Y,1)’T is a 3x3 projective transformationIn particular, this describes the mapping from points on a plane in theworld to points in the image plane.11/30/2001 CS 461, Copyright G.D. HagerProjective Invariants• Assumptions:– consider only scalar algebraic invariants– objects have planar surfaces containing points or contours– contours contain arcs of conics and straight lines• Basic Idea:– Given an object, compute set of invariant values (learning phase)– Given a scene, compute all possible invariants from extracted features and choose maximally consistent objects– Verify from set of most plausible hypotheses11/30/2001 CS 461, Copyright G.D. HagerExample Invariantsx1x2 x3x4Cross-ratioc(x1,x2,x3,x4) = d(1,2)d(3,4)/(d(1,3)d(2,4))Five coplanar lines (equiv. 5 coplanar pts)let libe (a,b,c) s.t. a x + b y + c z = 0I1= |M431||M521|/|M421||M531|I2= |M421||M531|/|M432||M521|where Mi,jk= [li,lj,lk} and | | denotes determinant11/30/2001 CS 461, Copyright G.D. HagerConic InvariantsA planar conic is just a x^2 + b xy + c y^2 +d x + e y + f = 0orequivalently, p’ C p = 0Given two coplanar conics C_1 and C_2 s.t. |C_1| = |C_2| = An interesting exercise is to show this is true ....11/30/2001 CS 461, Copyright G.D. HagerInvariant Learning• For each object (and each different planar view)– for each of two views• choose feature groups (lines or conics) for which invariants are defined; call