Segment-based encoding system using segment hierarchies

• US 20030123545A1
• Filed: 01/07/2003
• Published: 07/03/2003
• Est. Priority Date: 04/17/1999
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Pulsent Corp.
• Inventors: Prakash, Adityo, Fodor, Eniko
• Granted Patent: US 7,085,319 B2
• Time in Patent Office: Days
• US Class Current: 375/240.08
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/52 by predictive encoding
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

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.

Claims

1. A method of 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 method comprising:

encoding a first reference frame;

segmenting the first reference frame into a first set of segments;

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;

matching segments of the hierarchy of segments to pixels of a nonkey frame;

encoding into the compressed video data a representation of the nonkey frame according to results of the step of matching.

2. The method of claim 1, further comprising encoding into the compressed video data a representation of the hierarchy of segments, for use in decoding the nonkey frame.

3. The method of claim 1, further comprising steps of segmenting the first reference frame into a third set of segments.

4. The method of claim 1, wherein segmenting the first reference frame into a second set of segments 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 method 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 method of claim 4, wherein the grouping of segments is performed based on boundaries of segments of the first set of segments.

7. The method of claim 4, further comprising steps of segmenting 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 method of claim 1, wherein segmenting the first reference frame into a second set of segments 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 method 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 method of claim 8, further comprising steps of segmenting 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 method of claim 1, further comprising encoding 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 method of claim 1, wherein the hierarchy of segments is usable for editing one or more frames.

13. The method of claim 1, wherein the hierarchy of segments is usable for formatting one or more frames.

14. The method of claim 1, wherein the hierarchy of segments is usable for compressing one or more frames.

15. The method of claim 1, wherein the hierarchy of segments is usable for associating metadata with elements of the frame.

16. The method of claim 1, wherein the hierarchy of segments is usable for coding one or more of motion, residue or other kinetic information.