IEEE Transactions on Pattern Analysis and Machine Intelligence

A generic grouping algorithm and its quantitative analysis

View publication


This paper presents a generic method for perceptual grouping and an analysis of its expected grouping quality. The grouping method is fairly general: It may be used for the grouping of various types of data features and to incorporate different grouping cues operating over feature sets of different sizes. The proposed method is divided into two parts: constructing a graph representation of the available perceptual grouping evidence and then finding the best partition of the graph into groups. The first stage includes a cue enhancement procedure which integrates the information available from multifeature cues into very reliable bifeature cues. Both stages are implemented using known statistical tools such as Wald's SPRT algorithm and the Maximum Likelihood criterion. The accompanying theoretical analysis of this grouping criterion quantifies intuitive expectations and predicts that the expected grouping quality increases with cue reliability. It also shows that investing more computational effort in the grouping algorithm leads to better grouping results. This analysis which quantifies the grouping power of the Maximum Likelihood criterion is independent of the grouping domain. To our best knowledge such an analysis of a grouping process is given here for the first time. Three grouping algorithms in three different domains are synthesized as instances of the generic method. They demonstrate the applicability and generality of this grouping method. ©1998 IEEE.