A method and an apparatus for generating superpixels for a sequence of images. A cluster assignment generator generates a cluster assignment for a first image of the sequence of images, e.g. by clustering pixels of the first image into superpixels or by retrieving an initial cluster assignment for the first image and processing only contour pixels with regard to their cluster assignment. A label propagator initializes subsequent images based on a label propagation using backward optical flow. A contour pixel processor then processes only contour pixels with regard to their cluster assignment for subsequent images of the sequence of images.