Power Spectral Clustering

Abstract

Spectral clustering is one of the most important image processing tools, especially for image segmentation. This specializes at taking local information such as edge weights and globalizing them. Due to its unsupervised nature, it is widely applicable. However, traditional spectral clustering is O(n3/2). This poses a challenge, especially given the recent trend of large datasets. In this article, we propose an algorithm by using ideas from Γ-convergence, which is an amalgamation of maximum spanning tree clustering and spectral clustering. This algorithm scales as O(nlog(n)) under certain conditions, while producing solutions which are similar to that of spectral clustering. Several toy examples are used to illustrate the similarities and differences. To validate the proposed algorithm, a recent state-of-the-art technique for segmentation—multiscale combinatorial grouping is used, where the normalized cut is replaced with the proposed algorithm and results are analyzed.