Efficient algorithms for finding the centers of conics and quadrics in noisy data

摘要

We present efficient algorithms for finding the centers of conics and quadrics of known parameters in noisy or scarce data. The problem arises in applications where a conic or quadric of known parameters, such as a circle of known radius, is extracted from a scene or part. Common applications include locating an object in a noisy scene, and determining the correspondence between a manufactured part and its intended shape. Although the original problem is nonlinear and usually requires an iterative method for its solution, we reduce it to the well-known problem of minimizing a nonhomogeneous quadratic expression on the unit sphere. In the case of closed conics and quadrics, such as circles, ellipses, spheres, and ellipsoids, we obtain the solution in just one iteration and no starting estimate is required. Furthermore, we prove that the solution obtained by our method is the global minimum solution to the problem. For hyperbolas and hyperboloids, we describe a Gauss-Seidel algorithm, for which we give a Lyapunov type proof of convergence. We also describe an initialization algorithm to obtain starting estimates close to the global minimum solution. Furthermore, every iteration of this algorithm satisfies all constraints. We give numerical results showing a rapid convergence of the algorithm in just two iterations. We apply our method in a metrology application to accurately determine the cutting radius of a tool. We compare the results of our method in just one iteration for closed conics and two iterations for hyperbolas, against multiple iterations of Newton's method. Our comparison suggests that they are similar.