Segmenting encoding system with image segmentation performed at a decoder and encoding scheme for generating encoded data relying on decoder segmentation

• US 20030035484A1
• Filed: 03/20/2002
• Published: 02/20/2003
• Est. Priority Date: 04/17/2000
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Pulsent Corp.
• Inventors: Prakash, Adityo, Fodor, Eniko
• Granted Patent: US 6,888,894 B2
• Time in Patent Office: Days
• US Class Current: 375/240.25
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• 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/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/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

Abstract

An encoder includes a segmenter that segments a reference frame, assigning some or all of the pixels of the reference frame to segments based on pixel color values and/or pixel location. A kinetic information generator generates kinetic information that relates regions of a nonkey frame to segments of the reference frame as indicated by the segmentation. A decoder includes its own segmenter that segments at least a part of the reference frame extracted from the compressed video data, thereby eliminating the need for the encoder to include all of the segmentation in the compressed video data. The decoder includes a nonkey frame generator that regenerates a nonkey frame using kinetic information about the nonkey frame from the compressed video data and using at least a part of the segmentation of the reference frame generated by the decoder'"'"'s segmenter. The encoder segmentation and decoder segmentation can be the same or different.

Claims

1. 1. An encoding system, wherein an encoder encodes uncompressed video data to form compressed video data and a decoder decodes the compressed video data to form at least an approximation of the uncompressed video data, and wherein the video data comprises a sequence of a plurality of image frames comprising key frames and nonkey frames, the encoding system comprising:

an encoder comprising;

a) a segmenter that generates a segmentation of a reference frame, wherein a reference frame is a frame having content that is used in encoding a nonkey frame and wherein the segmentation is an assignment of some or all of the pixels of the reference frame to segments based on at least one of pixel color values of the pixels and location of the pixels in the reference frame;

b) a kinetic information generator that generates kinetic information that relates regions of a nonkey frame to segments of the reference frame as indicated by the segmentation generated by the segmenter; and

c) compressed video data outputter that outputs compressed video data including at least compressed key frames and the kinetic information; and

a decoder comprising;

a) a segmenter that generates at least a part of a segmentation of a reference frame extracted from the compressed video data; and

b) a nonkey frame generator that regenerates a nonkey frame using kinetic information about the nonkey frame from the compressed video data and using at least a part of the segmentation of the reference frame generated by the decoder'"'"'s segmenter.

2. The encoding system of claim 1, wherein the segmentation done by the encoder for a given reference frame is exactly the same as the segmentation done by the decoder for that given reference frame.

3. The encoding system of claim 1, wherein the compressed video data encodes at least one reference frame such that the encoding of the frame is not lossless and wherein the segmentation done by the encoder is of a reconstruction of the compressed version of the reference frame in place of the original reference frame.

4. The encoding system of claim 1, wherein the compressed video data encodes at least one reference frame losslessly and wherein the segmentation done by the encoder is of the original reference frame.

5. The encoding system of claim 1, wherein the kinetic information for a frame includes data elements associated with segments, for use in decoding other frames.

6. The encoding system of claim 5, wherein the kinetic information represents changes between a reference frame already available to the decoder and a current frame being decoded by the decoder.

7. The encoding system of claim 1, wherein the encoder encodes the video data using a plurality of segmentation schemes.

8. The encoding system of claim 7, wherein the encoded video data includes an indication of which of a plurality of segmentation schemes is used.

9. The encoding system of claim 8, wherein the indication of which of a plurality of segmentation schemes comprises frame-by-frame indications.

10. The encoding system of claim 7, wherein the decoder includes logic to deduce which of a plurality of segmentation schemes was used for a given reference frame from other data extracted from the compressed video data.

11. The encoding system of claim 7, wherein the decoder and encoder select the same segmentation scheme and the selection of segmentation scheme is based on image content.

12. The encoding system of claim 7, wherein the decoder and encoder select the same segmentation scheme and the selection of segmentation scheme is based on image content and on hints provided by the encoder in the compressed video data as to which selection the encoder made.

13. The encoding system of claim 1, wherein the compressed video data includes partial segmentation information.

14. The encoding system of claim 1, wherein the compressed video data includes segmentation hints.

15. The encoding system of claim 14, wherein the segmentation hints include indications of differences between a segmentation of a reference frame and a segmentation of a reconstructed nonlossless compression of the reference frame, thereby allowing the decoder to reconstruct and use a segmentation of the uncompressed reference frame.

16. The encoding system of claim 14, wherein the segmentation hints are usable by the decoder to partially or fully synchronize the decoder segmentation to the encoder segmentation.

17. The encoding system of claim 1, wherein the compressed video data includes partial segment canonical information, wherein canonical information indicates an ordering of elements.

18. The encoding system of claim 1, wherein the compressed video data includes canonical hints useable by the decoder to partially or fully synchronize a decoder canonicalization to an encoder canonicalization.

19. The encoding system of claim 1, wherein the reference frame is a key frame, decodable without reference to other frames.

20. The encoding system of claim 1, wherein the reference frame is a nonkey frame.

21. The encoding system of claim 1, wherein a reference frame and a nonkey frame that is decoded with reference to the reference frame have a relative order in a video sequence wherein the reference frame is earlier in the sequence than the current frame.

22. The encoding system of claim 1, wherein a reference frame and a nonkey frame that is decoded with reference to the reference frame have a relative order in a video sequence wherein the reference frame is later in the sequence than the current frame.

23. The encoding system of claim 1, wherein the encoder further comprises a residue coder that codes residue data based on segment-by-segment residues.

24. The encoding system of claim 23, wherein the residue data is coded at the encoder based at least in part on segmentation information available to the decoder from previously coded frames.

25. The encoding system of claim 1, wherein the compressed video data includes metadata associated with segments.

26. An encoder that encodes uncompressed video data to form compressed video data, wherein the video data comprises a sequence of a plurality of image frames comprising key frames and nonkey frames, the encoder comprising:

a segmenter that generates a segmentation of a reference frame, wherein a reference frame is a frame having content that is used in encoding a nonkey frame and wherein the segmentation is an assignment of some or all of the pixels of the reference frame to segments based on at least one of pixel color values of the pixels and location of the pixels in the reference frame;

a kinetic information generator that generates kinetic information that relates regions of a nonkey frame to segments of the reference frame as indicated by the segmentation generated by the segmenter; and

compressed video data outputter that outputs compressed video data including at least compressed key frames and the kinetic information with an assumption that a decoder can decode the compressed video data with at least partial segmentation of reference frames being done by the decoder.

27. The encoder of claim 26, wherein the compressed video data includes partial segmentation information.

28. The encoder of claim 26, wherein the compressed video data includes segmentation hints.

29. The encoder of claim 28, wherein the segmentation hints include indications of differences between a segmentation of a reference frame and a segmentation of a reconstructed nonlossless compression of the reference frame, thereby allowing a decoder to reconstruct and use a segmentation of the uncompressed reference frame.

30. The encoder of claim 28, wherein the segmentation hints are usable by a decoder to partially or fully synchronize a decoder segmentation to the encoder segmentation.

31. The encoder of claim 26, wherein the compressed video data encodes at least one reference frame such that the encoding of the frame is not lossless and wherein the segmentation done by the encoder is of a reconstruction of the compressed version of the reference frame in place of the original reference frame.

32. The encoder of claim 26, wherein the compressed video data encodes at least one reference frame losslessly and wherein the segmentation done by the encoder is of the original reference frame.

33. The encoder of claim 26, wherein the kinetic information for a frame includes data elements associated with segments, for usable in decoding other frames.

34. The encoder of claim 26, wherein the encoder encodes the video data using a plurality of segmentation schemes.

35. The encoder of claim 34, wherein the encoded video data includes an indication of which of a plurality of segmentation schemes is used.

36. The encoder of claim 35, wherein the indication of which of a plurality of segmentation schemes comprises frame-by-frame indications.

37. The encoder of claim 35, wherein the encoder includes logic to select a segmentation scheme is based on image content.

38. The encoder of claim 26, wherein the compressed video data includes partial segmentation information.

39. The encoder of claim 26, wherein the compressed video data includes partial segment canonical information, wherein canonical information indicates an ordering of elements.

40. The encoder of claim 26, wherein the compressed video data includes canonical hints useable by a decoder to partially or fully synchronize a decoder canonicalization to an encoder canonicalization.

41. The encoder of claim 26, wherein the reference frame is a key frame, decodable without reference to other frames.

42. The encoder of claim 26, wherein the reference frame is a nonkey frame.

43. The encoder of claim 26, wherein a reference frame and a nonkey frame that is encoded with reference to the reference frame have a relative order in a video sequence wherein the reference frame is earlier in the sequence than the current frame.

44. The encoder of claim 26, wherein a reference frame and a nonkey frame that is encoded with reference to a reference frame have a relative order in a video sequence wherein the reference frame is later in the sequence than the current frame.

45. The encoder of claim 26, wherein the encoder further comprises a residue coder that codes residue data based on segment-by-segment residues.

46. The encoder of claim 45, wherein the residue data is coded at the encoder based at least in part on segmentation information available to a decoder from previously coded frames.

47. The encoder of claim 26, wherein the compressed video data includes metadata associated with segments.