Power Spectral Clustering

• Published in: Journal of mathematical imaging and vision 2020-11, Vol.62 (9), p.1195-1213
• Main Authors: Challa, Aditya, Danda, Sravan, Sagar, B. S. Daya, Najman, Laurent
• Format: Article
• Language: English
• Subjects: Algorithms; Applications of Mathematics; Clustering; Combinatorial analysis; Computer Science; Computer Vision and Pattern Recognition; Graph theory; Image processing; Image Processing and Computer Vision; Image segmentation; Machine Learning; Mathematical Methods in Physics; Signal,Image and Speech Processing; Spectra
• ISSN: 0924-9907; 1573-7683
• DOI: 10.1007/s10851-020-00980-7

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 ( n 3 / 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 ( n log ( 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.