Power Spectral Clustering
- PDF / 4,088,198 Bytes
- 19 Pages / 595.276 x 790.866 pts Page_size
- 34 Downloads / 214 Views
Power Spectral Clustering Aditya Challa1
· Sravan Danda2 · B. S. Daya Sagar2 · Laurent Najman3
Received: 22 March 2019 / Accepted: 23 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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(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. Keywords Spectral clustering · Γ -convergence · MST-based clustering · Multiscale combinatorial grouping · Image segmentation
1 Introduction Spectral clustering has been widely popular due to its usage in image segmentation [32]. It plays an important role in globalizing local information in the recent state-of-the-art method for segmentation—multiscale combinatorial grouping [29]. Although convolution neural networks form the current stateof-the-art for image segmentation [24], this can be attributed to the availability of huge labelled datasets. There exists domains where data is not easy to obtain, such as hyperspectral image datasets, where unsupervised techniques can
B
Aditya Challa [email protected] Sravan Danda [email protected] B. S. Daya Sagar [email protected]; [email protected] Laurent Najman [email protected]
1
Department of Computer Science and Automation, Indian Institute of Science, CV Raman Rd, Bengaluru, Karnataka 560012, India
2
Systems Science and Informatics Unit, Indian Statistical Institute, 8th Mile Mysore Road, Bangalore, India
3
LIGM, Univ. Gustave Eiffel, CNRS, ESIEE Paris, 77454 Marne-la-Vallée, France
be very useful. In methods such as those described in [35], even after using convolution neural nets, spectral clustering is used as the last step for segmentation. An overview of spectral clustering procedures can be found in [38]. One of the reasons for the popularity of the spectral clustering procedure is its ability to detect nonconvex clusters. Spectral clustering method proceeds by constructing an edge-weighted graph from the data and use the eigenvectors of the Laplacian of the graph. However, the calculation of the eigenvectors is computationally expensive, and is prone to errors. Several efforts were made to increase the speed and accuracy of the spectral
Data Loading...
