ICCV 2003 Short Course

Efficient algorithms for matching

Instructors: Dan Huttenlocher(Cornell University) and Phil Torr (Microsoft Research Ltd).

Duration: 3.5 hours

Course Content

This course will provide an introduction into some practically useful techniques for matching of sets of features, points, or lines. Matching is fundamental to the solution of many problems in vision, including the recovery of structure and motion, and object recognition. We shall outline matching strategies where there is a strong parametric transformation relating the two sets of images, and when the transformation is slightly weaker, e.g., only imposing local smoothness.

1. Matching features with strong parametric models using random sampling, a review of 23 years of RANSAC fun!
   • RANSAC: Comparison with other robust algorithms, work of Torr on feature matching with F.
   • LMS: Work of Zhang on epipolar geometry estimation, to bucket or not? Relation to Hausdorff, rank or chamfer the error? Relation to computational geometry.
   • MINPRAN.
   • MLESAC/MAPSAC, a Bayesian cost function, matcher, and optimizer.
   • Work of Tordoff on jump out and improvements on matching.
   • Work of Matas et al.: Randomized RANSAC, Hi Lo RANSAC.
2. InterMezzo ICP
   • Definition.
   • Outliers a problem, so look at work of Fitzgibbon.
3. Distance transforms for matching point and line features
   • Definition of distance transform: Distance at each location to nearest "distinguished" point. Formulation as min distance. Relationship to Voronoi diagrams and Delaunay triangulations.
   • Chamfer and Hausdorff distances: How to compute them. Computational speedups. Hausdorff, maximally separating hyperplanes and perceptron learning algorithm. Pros and cons of Chamfer vs. Hausdorff.
4. Applications of dynamic programming to matching
   • DP as applied to Markov Chains, e.g., snakes: Viterbi. Forward backward.
   • DP for articulated objects, pictorial objects.
   • DP for stereo.

Biographies

Dan Huttenlocher received his bachelors degree from the University of Michigan, and his masters and doctoral degrees from M.I.T. He has been a faculty member in the Computer Science department at Cornell University since 1988, where he currently holds a joint appointment with the Johnson Graduate School of Management. His research interests are in computer vision, geometric algorithms, electronic collaboration tools, financial trading systems, and the principles of software development. In addition to teaching and research, Dr. Huttenlocher has considerable experience managing software-development efforts in corporate and academic settings. He is chief technical officer of Intelligent Markets, a provider of advanced trading systems. He also spent more than ten years at Xerox PARC, directing work that led to the ISO JBIG2 image-compression standard, and serving as part of the senior management team.

Philip Torr graduated from Southampton with a degree in mathematics and obtained a DPhil from Oxford in Engineering (Computer Vision). After more fun as a postdoc in the robotics research group he was given the Marr Prize for work on matching. He then moved to Microsoft Research in Redmond where he worked for two years before moving to Microsoft Research in Cambridge (UK) to help establish the lab. After six highly enjoyable years at Microsoft he plans to return to academia to set up a new vision research lab at Oxford Brookes University in Oxford England and welcomes and encourages all eager potential PhD students or postdocs to email him now!