The current application is directed to flexible methods for motion-vector-based encoding of macroblocks within video frames. The flexible methods for encoding video-frame macroblocks provide for segmentation of a video-frame block and encoding the segmented video-frame block by a segmented-block motion vector that includes a reference to a segmentation-defining region of a segmentation map and that also includes references to sources of intensity-and-color data for each segment. Segmented-block motion vectors provide for flexible segmentation-based encoding of video-frame blocks without sacrificing the coding efficiencies attendant with conventional motion-vector-based video encoding.