A decoder decodes compressed video data wherein nonkey frames are decoded with reference to other frames from the video data that are reference frames. The decoder generates at least a part of a segmentation of the reference frames for use in decoding nonkey frames. A nonkey frame is regenerated using kinetic information about the current frame and the reference frame segmentation. Kinetic information might include segment translation information. Where the segmentation used in encoding the compressed video data can vary among a plurality of segmentation schemes, the decoder determines which segmentation scheme is used from selection indications in the compressed video data or from previously decoded video data. The decoder might also use partial segmentation information, segmentation hints, partial segment canonical information and/or canonical hints in its segmentation process. The decoder might also process segment-related metadata extracted the compressed video data.