Multiple circle detection based on center-based clustering

摘要

The multiple circle detection problem has been considered in the paper on the basis of given data point set A is contained in K~2. It is supposed that all data points from the set A 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, 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.