Multiple circle detection based on center-based clustering

• Adaptation of the k-means algorithm is used by circle-centers.
• Incremental algorithm for searching for a globally optimal k-partition is proposed.
• A few known indexes for determining a number of clusters in partition are adopted.
• Hausdorff distance between two circles is adopted.

The multiple circle detection problem has been considered in the paper on the basis of given data point set A⊂R2A⊂R2. It is supposed that all data points from the set AA come from k   circles that should be reconstructed or detected. The problem has been solved by the application of center-based clustering of the set A,A, i.e. an optimal k-partition is searched for, whose clusters are determined by corresponding circle-centers. Thereby, the algebraic distance from a point to the circle is used. First, an adaptation of the well-known k-means algorithm is given in the paper. Also, the incremental algorithm for searching for an approximate globally optimal k-partition is proposed. The algorithm locates either a globally optimal k-partition or a locally optimal k-partition close to the global one. Since optimal partitions with 2, 3, … clusters are determined successively in the algorithm, several well-known indexes for determining an appropriate number of clusters in a partition are adopted for this case. Thereby, the Hausdorff distance between two circles is used and adopted. The proposed method and algorithm are illustrated and tested on several numerical examples.