Numerical aspects of spectral segmentation on polygonal grids

We present an implementation of the Normalized Cuts method for the solution of the image segmentation problem on polygonal grids. We show that in the presence of rounding errors the eigenvector corresponding to the k-th smallest eigenvalue of the generalized graph Laplacian is likely to contain more than k nodal domains. It follows that the Fiedler vector alone is not always suitable for graph partitioning, while the eigenvector subspace, corresponding to just a few of the lowest eigenvalues, contains sufficient information needed for obtaining meaningful segmentation. At the same time, the eigenvector corresponding to the trivial solution often carries nontrivial information about the nodal domains in the image and can be used as an initial guess for the Krylov subspace eigensolver. We show that proposed algorithm performs favorably when compared to the Multiscale Normalized Cuts and Segmentation by Weighted Aggregation.