Segment-based encoding system using segment hierarchies

Abstract

Video data is compressed using segmentation of reference frames where the segmentation results in a hierarchy of segments. The hierarchy can be generated bottom-up, where a first set of segments is generated and then a second set of segments generated by grouping segments of the first set, based on pixel value and/or segment boundaries. The hierarchy can be generated top-down, where a first set is generated and then a second set is generated by dividing up segments of the first set, based on pixel value and/or segment boundaries. The hierarchy can be included in the compressed video data or omitted such that a decoder would have to independently generate it. The hierarchy can be two or more levels. The hierarchy can be used for editing, formatting and/or compressing frames, as well as associating metadata with elements of the frame and coding motion, residue or other kinetic information.

1 . An apparatus for encoding uncompressed video data to form compressed video data, wherein the video data comprises a plurality of image frames including a set of reference frames and a set of nonkey frames, wherein the set of nonkey frames are encoded with reference at least to a segmentation of at least one of the image frames in the set of reference frames, and further wherein the segmentation is an assignment of some or all of the pixels of the reference frame to at least one segment based on at least one of a color value or a location of the pixels in the reference frame, the apparatus comprising: 
 a frame compressor configured to encode a first reference frame;    a segmenter configured to segment the first reference frame into a first set of segments and to segment the first reference frame into a second set of segments, wherein the first set and second set form a hierarchy of segments and each segment encloses a simply connected set of pixels of the first reference frame;    a matcher configured to match segments of the hierarchy of segments to pixels of a nonkey frame; and    an output scheduler configured to encode into the compressed video data a representation of the nonkey frame according to motion vectors from the matcher.    
     
     
         2 . The apparatus of  claim 1 , wherein the output scheduler further encodes into the compressed video data a representation of the hierarchy of segments, for use in decoding the nonkey frame.  
     
     
         3 . The apparatus of  claim 1 , wherein the segmenter is further configured to segment the first reference frame into a third set of segments.  
     
     
         4 . The apparatus of  claim 1 , wherein segmenting the first reference frame into a second set of segments by the segmenter comprises grouping segments from the first set of segments such that each segment of the second set of segments comprises one or more segments from the first set of segments.  
     
     
         5 . The apparatus of  claim 4 , wherein the grouping of segments is performed based on pixel color values of pixels in segments of the first set of segments.  
     
     
         6 . The apparatus of  claim 4 , wherein the grouping of segments is performed based on boundaries of segments of the first set of segments.  
     
     
         7 . The apparatus of  claim 4 , wherein the segmenter is further configured to segment the first reference frame into a third and subsequent sets of segments wherein segments at each level of the hierarchy of segments are groupings of segments of its immediately prior level.  
     
     
         8 . The apparatus of  claim 1 , wherein segmenting the first reference frame into a second set of segments by the segmenter comprises dividing segments from the first set of segments into one or more segment of the second set of segments such that each segment of the first set of segments comprises one or more segments from the second set of segments.  
     
     
         9 . The apparatus of  claim 8 , wherein the division of segments is performed based on a color value of pixels in segments of the first set of segments.  
     
     
         10 . The apparatus of  claim 8 , wherein the segmenter is further configured to segment the first reference frame into a third set of segments wherein segments at each level of the hierarchy of segments are divisions of segments of its immediately prior level.  
     
     
         11 . The apparatus of  claim 1 , wherein the output scheduler is further configured to encode the compressed video data without a complete representation of the hierarchy of segments, such that a decoder would have to independently generate at least a portion of the hierarchy of segments.  
     
     
         12 . The apparatus of  claim 1 , wherein the hierarchy of segments is usable for editing one or more frames.  
     
     
         13 . The apparatus of  claim 1 , wherein the hierarchy of segments is usable for formatting one or more frames.  
     
     
         14 . The apparatus of  claim 1 , wherein the hierarchy of segments is usable for compressing one or more frames.  
     
     
         15 . The apparatus of  claim 1 , wherein the hierarchy of segments is usable for associating metadata with elements of the frame.  
     
     
         16 . The apparatus of  claim 1 , wherein the hierarchy of segments is usable for coding one or more of motion, residue or other kinetic information.  
     
     
         17 . An encoder for encoding uncompressed video data to form compressed video data, wherein the video data comprises a plurality of image frames including a set of reference frames and a set of nonkey frames, wherein the set of nonkey frames are encoded with reference at least to a segmentation of at least one of the image frames in the set of reference frames, and further wherein the segmentation is an assignment of some or all of the pixels of the reference frame to at least one segment based on at least one of a color value or a location of the pixels in the reference frame, the encoder comprising: 
 means for encoding a first reference frame;    means for segmenting the first reference frame into a first set of segments and for segmenting the first reference frame into a second set of segments, wherein the first set and second set form a hierarchy of segments and each segment encloses a simply connected set of pixels of the first reference frame;    means for matching segments of the hierarchy of segments to pixels of a nonkey frame;    means for encoding into the compressed video data a representation of the nonkey frame according to results of the means for matching.    
     
     
         18 . The encoder of  claim 17 , wherein the means for encoding encodes into the compressed video data a representation of the hierarchy of segments, for use in decoding the nonkey frame.  
     
     
         19 . The encoder of  claim 17 , wherein the means for segmenting segments the first reference frame into a third set of segments.  
     
     
         20 . The encoder of  claim 17 , wherein segmenting the first reference frame into a second set of segments by the means for segmenting comprises grouping segments from the first set of segments such that each segment of the second set of segments comprises one or more segments from the first set of segments.