The application of graph theoretic methods to unsupervised image partitioning has been a very active field of research recently. For weighted graphs encoding the (dis)similarity structure of locally extracted image features, unsupervised segmentations of images into coherent structures can be computed in terms of extremal cuts of the underlying graphs. In this context, we focus on the normalized cut criterion and a related recent convex approach based on semidefinite programming. As both methods soon become computationally demanding with increasing graph size, an important question is how the computations can be accelerated. To this end, we study an SVD approximation method in this paper which has been introduced in a different clustering context. We apply this method, which is based on probabilistic sampling, to both segmentation approaches and compare it with the Nyström extension suggested for the normalized cut. Numerical results confirm that by means of the sampling-based SVD approximation technique, reliable segmentations can be computed with a fraction (less than 5%) of the original computational cost.
Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)
Search Authors in