Spectral graph theoretic methods have recently shown great promise for the image segmentation. This paper focuses on the disadvantage that the similarity matrix and the Laplacian matrix constructed complex and waste of time in high resolution image segmentation, so presents a Nystrom method based on variance incremental to reduce the scale of the matrix. Then based on cosine similarity to attain similarity matrix, the use of traditional Gauss formula to artificial selection scale parameter is avoided. Lastly, experimental results on Berkeley image database show the validity of the algorithm.