Solving Geometric Matching Problems using Interval Arithmetic Optimization

August 23, 2004
Thomas Breuel | Technical University of Kaiserslautern

I describe how global optimization methods based on interval arithmetic can be used for solving a variety of problems in computational geometry, including the detection of parametric geometric primitives, geometric point matching, and maximum empty rectangle problems. These techniques can be viewed as extensions of previous work on branch-and-bound based geometric matching techniques, but they are applicable to a wider range of problems, guarantee reliable solutions even in the presence of numerical roundoff errors, and permit the use of better optimization strategies. I discuss some applications of these techniques to geometric problems arising in document layout analysis.

Speaker Details

Dr. Breuel is professor of computer science at the Technical University of Kaiserslautern Computer Science Department and head of the Image Understanding and Pattern Recognition (IUPR) research group at the DFKI. His research group works in the areas of image understanding, document imaging, computer vision, and pattern recognition.Previously, Dr. Breuel has worked as a researcher at Xerox PARC, the IBM Almaden Research Center, IDIAP, Switzerland, as well as a consultant to the US Bureau of the Census. He is an alumnus of the Massachusetts Institute of Technology and Harvard University.Please go to www.iupr.org for more information.