Optimality of Maximum Likelihood Estimation for GeometricFitting and the KCR Lower Bound
Kenichi Kanatani · 2005
Geometric fitting is one of the most fundamental problems of computer vision. In [8], the author derived a theoretical accuracy bound (KCR lower bound) for geometric fitting in general and proved that maximum likelihood (ML) estimation is statistically optimal. Recently, Chernov and Lesort [3] proved a similar result, using a weaker assumption. In this paper, we compare their formulation with the author’s and describe the background of the problem. We also review recent topics including semiparametric models and discuss remaining issues. 1. What Is the Problem? By geometric fitting, we mean fitting a geometric constraint to observed data and discerning the under-lying geometric structure from the coefficients of the fitted equation [8]. A large class of computer vision problems fall into this framework. The simplest ex-ample is to fit a parametric curve (e.g., a line, a circle, an ellipse, or a polynomial curve) in the form F (x;u) = 0 (1) to N points {(xα, yα)} in the image, where x = (x, y)> is the position vector, and u = (u1,..., up)> is the parameter vector. For noisy data {(xα, yα)}, no parameter u satis-fies F (xα;u) = 0 for all α = 1,..., N, so one often computes a u such that JLS = N∑ α=1 F (xα;u)2 → min. (2) This is called the least-squares (LS) method or alge-braic distance minimization. However, it is widely known that the solution has strong statistical bias. A better method known to yield higher accuracy is to regard the data {xα} as perturbed from their true positions {x̄α} which are exactly on the curve F (x;u) = 0 and to simultaneously estimate the true positions {x̄α} and the parameter u that maximize the statis-tical likelihood. If noise is subject to isotropic, in-dependent, and identical Gaussian distribution, this reduces to the minimization