On the Use of Interval Arithmetic in Geometric Branch-and-Bound Algorithms

Thomas Breuel

In: Pattern Recognition Letters (PRL) Accepted for publication in it Pattern Recognition Letters 24 9-10 Pages 1375-1384 Elsevier 6/2003.


Branch and bound methods have become established methods for geometric matching over the last decade. This paper presents techniques that improve on previous branch and bound methods in two important ways: they guarantee reliable solutions even in the presence of numerical roundoff error, and they eliminate the need to derive bounding functions man- ually. These new techniques are compared experimentally with recognition-by-alignment and previous branch and bound techniques on geometric matching problems. Novel meth- ods for non-linear baseline finding and globally optimal robust linear regression using these techniques are described.

IntervalArithB+Bpatrec.pdf (pdf, 940 KB)

German Research Center for Artificial Intelligence
Deutsches Forschungszentrum für Künstliche Intelligenz