An approach for image segmentation is presented. Images are first preprocessed using multiscale simplification by nonlinear diffusion. Subsequently image segmentation of the resulting smoothed images is carried out. The actual segmentation step is based on the estimation of the Eigenvectors and Eigenvalues of a matrix derived from both the total dissimilarity and the total similarity between different groups of pixels in the image. This algorithm belong to the class of spectral methods, specifically, the Nystron extension introduced by Fowlkes et al in . Stability analysis of the approximation of the underlying spectral partitioning is presented. Modifications of Fowlkes technique are proposed to improve the stability of the algorithm. The proposed modifications include a criterion for the selection of the initial sample and numerically stable estimations of ill-posed inverse matrices for the solution of the underlying mathematical problem. Results of selected computer experiments are reported to validate the superiority of the proposed approach when compared with the technique proposed in .© (2005) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.