Adaptive fuzzy c-shells clustering and detection of ellipses

Several generalizations of the fuzzy c-shells (FCS) algorithm are presented for characterizing and detecting clusters that are hyperellipsoidal shells. An earlier generalization, the adaptive fuzzy c-shells (AFCS) algorithm, is examined in detail and is found to have global convergence problems when the shapes to be detected are partial. New formulations are considered wherein the norm inducing matrix in the distance metric is unconstrained in contrast to the AFCS algorithm. The resulting algorithm, called the AFCS-U algorithm, performs better for partial shapes. Another formulation based on the second-order quadrics equation is considered. These algorithms can detect ellipses and circles in 2D data. They are compared with the Hough transform (HT)-based methods for ellipse detection. Existing HT-based methods for ellipse detection are evaluated, and a multistage method incorporating the good features of all the methods is used for comparison. Numerical examples of real image data show that the AFCS algorithm requires less memory than the HT-based methods, and it is at least an order of magnitude faster than the HT approach.