Color image segmentation draws a lot of attention recently. In order to improve efficiency of spectral clustering in color image segmentation, a novel two-stage color image segmentation method is proposed. In the first stage, we use vector gradient approach to detect color image gradient information, and watershed transformation to get the pre-segmentation result. In the second stage, Nystrom extension based spectral clustering is used to get the final result. To verify the proposed algorithm, it is applied to color images from the Berkeley Segmentation Dataset. Experiments show our method can bring promising results and reduce the runtime significantly.