New techniques for clustering, selection of number of histogram bins, and estimation of quantiles of pairwise distances

Abstract

The emulation of Gestalt Laws was required for a proposed knowledge-based inference driven vision system. Emulating the Proximity gestalt law required a clustering technique that worked without: (a) the need for any input parameters that would govern the number of clusters detected; and (b) without any preference for a given cluster shape. A watershed algorithm based clustering technique due to Bicego et. al. satisfies the aforementioned requirements. However, their algorithm's performance is degraded due to experimentally tuned internal parameters. An improved clustering technique was developed without the need for any such internal parameters by employing the concept of scale. Two implementations have been provided for the proposed clustering algorithm. A drawback affecting the proposed clustering algorithm's performance was also discovered. A diagnostic procedure that recommends whether or not the clustering algorithm's output should be accepted has been provided as an addendum.

While working on the problem of automatic scale detection for the clustering technique, certain analytical and computational difficulties were encountered while attempting to: (a) compute quantiles of pairwise distances for use in the calculation of Qn; and (b) construction of histograms for evaluating Entropy. A new method to estimate quantiles of pairwise distances was developed. Performance comparisons with other existing methods showed that the proposed method is: faster and more accurate than other estimation methods; and faster than other selection methods. A new method to select the number of bins for constructing a histogram was developed. Performance comparisons with existing methods showed that the proposed method produces visually appealing histograms that capture shape features of underlying distribution to a finer detail without admitting excessive noise.