A method and an apparatus for generating superpixels for a sequence of frames. A feature space of the sequence of frames is separated into a color subspace and a spatial subspace. A clustering is then performed in the spatial subspace on a frame basis. In the color subspace a clustering is performed on stacked frames. An erroneous temporal consistency of a superpixel associated to a frame is detected by performing a similarity check between a corresponding superpixel in one or more past frames and one or more future frames using two or more metrics. The affected superpixels is future frames are corrected accordingly.