Optimal circle fitting via branch and bound

Abstract

We examine the problem of fitting a circle to a set of noisy measurements of points from the circle's circumference, assuming independent, identically distributed Gaussian measurement errors. We propose an algorithm based on branch and bound to obtain the maximum likelihood estimate and show that this algorithm obtains the optimal estimate. We examine the rate of convergence and determine the computational complexity of the proposed algorithm. We also provide timings and compare them to those of existing techniques for circle fitting proposed in the literature. Finally, we demonstrate that our algorithm is statistically efficient by comparing our results to the Cramer-Rao lower bound.