TurboPixel (TP) is a powerful tool for image over-segmentation. It is fast and can yield a lattice-like structure of superpixel regions with uniform size. This paper presents a method to learn eigen-images from the image to be segmented. Such eigen-images are used to generate the evolution speed in the TP framework. The task is formulated as a problem of pixel clustering. Specifically, for the pixels in each local window, a linear transformation is introduced to map their color vectors to be the cluster indicator vectors. The errors under all such linear transformations are estimated and summed together to obtain an objective function, from which a global optimum is finally obtained. In this process, the eigen-images are constructed. Based on these eigen-images, multidimensional image gradient operator is defined to evaluate the gradient, which is supplied to the TP algorithm to obtain the final superpixel segmentations. The computational issues are discussed, and an image pyramid is introduced to speed up the computation. Comparative experiments illustrate the effectiveness of our method.