• Calendar

November 16, Tuesday
12:00 – 14:00

We introduce a fast, Multiscale algorithm for clustering, based on a fast segmentation algorithm introduced by Sharon, Brandt and Basri (Sharon et al., 2000).

It finds an approximate solution to normalized cut measures in a weighted graph, in a time that is linear in the number of edges in the graph, and yields a hierarchical decomposition of the graph into clusters at all scales. The algorithm detects the clusters by applying a process of recursive coarsening in which the same minimization problem is represented with fewer and fewer variables producing an irregular pyramid. Each node in the pyramid represents an aggregate of fine nodes, thus the pyramid yields the complete hierarchy of clusters at all scales. The coarsening procedure yields an easy platform to compute additional internal statistics of the emerging intermediate level clusters. These additional measurements are used during the aggregation, and also in a top-down manner in the higher level clustering.

In this talk I will present the algorithm, as well as show its capabilities on real data from computer vision, graphics, and biology.

Joint work with Eitan Sharon, Meirav Galun and Achi Brandt