THE ADAPTATION OF THE k-MEANS ALGORITHM TO SOLVING THE MULTIPLE ELLIPSES DETECTION PROBLEM BY USING AN INITIAL APPROXIMATION OBTAINED BY THE DIRECT GLOBAL OPTIMIZATION ALGORITHM

摘要

We consider the multiple ellipses detection problem on the basis of a data points set coming from a number of ellipses in the plane not known in advance, whereby an ellipse E is viewed as a Mahalanobis circle with center S, radius r, and some positive definite matrix sigma. A very efficient method for solving this problem is proposed. The method uses a modification of the k-means algorithm for Mahalanobis-circle centers. The initial approximation consists of the set of circles whose centers are determined by means of a smaller number of iterations of the DIRECT global optimization algorithm. Unlike other methods known from the literature, our method recognizes well not only ellipses with clear edges, but also ellipses with noisy edges. CPU-time necessary for running the corresponding algorithm is very short and this raises hope that, with appropriate software optimization, the algorithm could be run in real time. The method is illustrated and tested on 100 randomly generated data sets.