Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Wednesday, October 12, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Micha Sharir (Tel Aviv Univ.)
The ICP algorithm is a simple heuristic technique for pattern matching under translation between two point sets A and B. It was proposed by Besl and McKay more than 10 years ago, and has been very successful in practice. However, its performance has never been rigorously analyzed before, and many basic questions remain open.
The technique keeps B fixed and translates A. At each step, it assigns to each point in (the current placement of) A its nearest neighbor in B. It then keeps this assignment fixed, and finds the translation t that minimizes, say, the sum of squared distances between the points of A and their neighbors in B. It then translates A by t, and repeats the procedure. Some points of A may now have new nearest neighbors in B; otherwise the process terminates.
In this talk I will present some partial results, obtained jointly with my Ph.D. student Esther Ezra, on the (worst-case) performance of the ICP algorithm. The problems are very challenging even for point sets on the line, let alone in the plane or in higher dimensions.
Automatic MiSe System Software Version 1.4803M | admin login