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 aris es 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 determi ning the correspondence between a manufactured part and its intended s hape. Although the original problem is nonlinear and usually requires an iterative method for its solution, we reduce it to the well-known p roblem of minimizing a nonhomogeneous quadratic expression on the unit sphere. In the case of closed conics and quadrics, such as circles, e llipses, spheres, and ellipsoids, we obtain the solution in just one i teration and no starting estimate is required. Furthermore, we prove t hat 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 convergen ce. We also describe an initialization algorithm to obtain starting es timates close to the global minimum solution. Furthermore, every itera tion of this algorithm satisfies all constraints. We give numerical re sults showing a rapid convergence of the algorithm in just two iterati ons. We apply our method in a metrology application to accurately dete rmine the cutting radius of a tool. We compare the results of our meth od in just one iteration for closed conics and two iterations for hype rbolas, against multiple iterations of Newton's method. Our comparison suggests that they are similar. (C) 1997 Pattern Recognition Society.