Self-organization in vision: Stochastic clustering for image segmentation,perceptual grouping, and image database organization

We present a stochastic clustering algorithm which uses pairwise similarity of elements and show how it can be used to address various problems in com puter vision, including the low-level image segmentation, mid-level percept ual grouping, and high-level image database organization. The clustering pr oblem is viewed as a graph partitioning problem, where nodes represent data elements and the weights of the edges represent pairwise similarities. We generate samples of cuts in this graph, by using Karger's contraction algor ithm, and compute an "average" cut which provides the basis for our solutio n to the clustering problem. The stochastic nature of our method makes it r obust against noise, including accidental edges and small spurious clusters . The complexity of our algorithm is very low: O(\E \ log(2) N) for N objec ts, \E \ similarity relations, and a fixed accuracy level. In addition, and without additional computational cost, our algorithm provides a hierarchy of nested partitions. We demonstrate the superiority of our method for imag e segmentation on a few synthetic and real images, both B&W and color. Our other examples include the concatenation of edges in a cluttered scene (per ceptual grouping) and the organization of an image database for the purpose of multiview 3D object recognition.