1Template Matching – Rigid Motion• Find transformation to align two images.• Focus on geometric features– (not so much interesting with intensity images)– Emphasis on tricks to make this efficient.Problem Definition• An Image is a set of 2D geometric features, along with positions.• An Object is a set of 2D/3D geometric features, along with positions.• A pose positions the object relative to the image.– 2D Translation; 2D translation + rotation; 2D translation, rotation and scale; planar or 3D object positioned in 3D with perspective or scaled orth.• The best pose places the object features nearest the image features2Two parts to the problem• Definition of cost function.• Search method for finding best pose.1. Can phrase this as search among poses.2. Or as search among correspondences3. There are connections between two.Example3Cost Function• We look at this first, since it defines the problem.• Again, no perfect measure;– Trade-offs between veracity of measure and computational considerations.• One-to-one vs. many-to-one• Bounded error vs. metricExample: Chamfer MatchingMany-to-one, distanceidFor every edge point in the transformed object, compute the distance to the nearest image edge point. Sum distances.||),||||,,||||,,min(||211 miiniiqpqpqp 4Main Feature:• Every model point matches an image point.• An image point can match 0, 1, or more model points.Variations• Sum a different distance– f(d) = d2– or Manhattan distance.– f(d) = 1 if d < threshold, 0 otherwise.– This is called bounded error.• Use maximum distance instead of sum.– This is called: directed Hausdorff distance.• Use other features– Corners.– Lines. Then position and angles of lines must be similar.• Model line may be subset of image line.5Other comparisons• Enforce each image feature can match only one model feature.• Enforce continuity, ordering along curves.• These are more complex to optimize.Pose Search: Standard Optimization Heuristics• Brute force search with dense sampling.• Random starting point + gradient descent.– Multiple random starting points– Stochastic gradient descent• Any other optimization method you can think of.6Clever Idea 1: Chamfer Matching with the Distance Transform000000011111111111111222222222222 333333334Example: Each pixel has (Manhattan) distance to nearest edge pixel.D.T. Adds Efficiency• Compute once.• Fast algorithms to compute it.• Makes Chamfer Matching simple.7000000011111111111111222222222222 333333334Then, try all translations of model edges. Add distances under each edge pixel. That is, correlate edges with Distance TransformComputing Distance Transform• It’s only done once, per problem, not once per pose.• Basically a shortest path problem.• Simple solution passing through image once for each distance.– First pass mark edges 0. – Second, mark 1 anything next to 0, unless it’s already marked. Etc….• Actually, a more clever method requires 2 passes.8Chamfer Matching Complexity• Brute force approach: for each pose, compare each model point to every image point. O(pnm). p = number poses, n = number of image points, m = number of model points.• With distance transform: compute D.T., then for every pose, sum value under each model edge. O(s + pm). s = number of pixels, which is about same as p. Clever Idea 2: Ransac• Match enough features in model to features in image to determine pose. • Examples:– match a point and determine translation.– match a corner and determine translation and rotation.– Points and translation, rotation, scaling?– Lines and rotation and translation?9(Forsyth & Ponce)10Complexity • Suppose model has m points and image has n points. There are nm matches.When we match a model point, there is a 1/n probability this match is right.If we match k model points, probability all are right is approximately (1/n)k.If we repeat this L times, probability that at least one pose is right is:Lkn)11(1 Figure from “Object recognition using alignment,” D.P. Huttenlocher and S. Ullman, Proc. Int. Conf. Computer Vision, 1986, copyright IEEE, 198611The Hough Transform for Lines• A line is the set of points (x, y) such that: y = mx + b• For any (x, y) there is a line in (m,b) space describing the lines through this point. Just let (x,y) be constants and m, b be unknowns.• Each point gets to vote for each line in the family; if there is a line that has lots of votes, that should be the line passing through the pointsMechanics of the Hough transform• Construct an array representing m, b• For each point, render the line y=mx+b into this array, adding one at each cell• Questions– how big should the cells be? (too big, and we cannot distinguish between quite different lines; too small, and noise causes lines to be missed) • How many lines?– count the peaks in the Hough array• Who belongs to which line?– tag the votes• Can modify voting, peak finding to reflect noise.• Big problem if noise in Hough space different from noise in image space.12Generalized Hough TransformSome pros and cons• Run-time for line finding– Complexity of RANSAC n*n*n– Complexity of Hough n*d13Error behavior• Hough handles error with buckets. This gives a larger set of lines consistent with point, but ad-hoc.• Ransac handles error with threshold. Well-motivated for error in other points, but not for error in first 2 points.– But works if we find some 2 points w/ low error.• Error handling sloppy -> clutter bigger problem.• Many variations to handle these issues.Pose: Generalized Hough Transform• Like Hough Transform, but for general shapes.• Example: match one point to one point, and for every rotation of the object its translation is determined.• Example: match enough features to determine pose, then vote for best pose.14Correspondence: Interpretation Tree Search• Represent all possible sets of matches as exponential sized tree.• Each node involves another match• Wildcard allowed for no matches.• Prune tree when set of matches incompatible (this seems to imply bounded error).• Trick: some fast way of evaluating compatability.• Trick: different tree search algorithms. Best first. A*….2D Euclidean Transformation• Check pairwise compatibility– Fast– Conservative testamn15Cass: Correspondence pose duality• Suppose we match two features with bounded error.– There is a set