ROBUST CLUSTERING WITH APPLICATIONS IN COMPUTER VISION

A novel clustering algorithm based on the minimum volume ellipsoid (MVE) robust estimator recently introduced in statistics is proposed. The MVE estimator identifies the least volume region containing h percent of the data points. The clustering algorithm iteratively partitions the space into clusters without a priori information about their number. At each iteration, the MVE estimator is applied several times with values of h decreasing from 0.5. A cluster is hypothesised for each ellipsoid. The shapes of these clusters are compared with shapes corresponding to a known unimodal distribution by the Kolmogorov-Smirnov test. The best fitting cluster is then removed from the space, and a new iteration starts. Constrained random sampling keeps the amount of computation low. The clustering algorithm was successfully applied to several computer vision problems formulated in the feature space paradigm: multithresholding of gray level images, analysis of the Hough space, range image segmentation.