System and method of generating compressed video graphics images

• US 5,742,289 A
• Filed: 08/16/1996
• Issued: 04/21/1998
• Est. Priority Date: 04/01/1994
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Petajan, Eric David, Naylor, Bruce F.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US08/689,962
• Time in Patent Office: 613 Days
• Field of Search: 395/152, 395/119, 395/173, 348/400, 348/401, 348/402, 348/407, 348/413, 348/414, 348/416, 348/417, 348/669, 345/419, 345/473
• US Class Current: 345/419
• CPC Class Codes: A63F 2300/409 Data transfer via television network
• CPC Class Codes: A63F 2300/538 for performing operations on behalf of the game client, e.g. rendering
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/159 Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

In a hybrid system for synthesizing a compressed video bitstream from a dynamic 3-D model, the video bitstream represents an image sequence comprised of a plurality of image frames which are sequential in time and in which each image frame is partitioned into a set of regions. Motion vectors are generated for each region within a current image frame which represent the dynamic 3-D model. A prediction error is computed for each region based on the generated motion vectors. The type of encoding to be performed on each region in a succeeding image frame is determined based on the value of the prediction error. Each region in the succeeding image frame is encoded as indicated by the determined encoding type.

Claims

1. A hybrid system for synthesizing a compressed video bitstream from a dynamic 3-D model said video bitstream representing an image sequence comprised of a plurality of image frames which are sequential in time, each image frame being partitioned into a set of nonoverlapping contiguous regions, each block of said image frame being encoded as indicated by a predictive encoding type, the system comprising:

means for performing low resolution rendering upon the 3-D objects which compose the 3-D model to derive a mapping definition for each object and to thereby produce a 2-D image frame and to partition each image frame of a time sequence of frames into a set of regions;

means for generating motion vectors for at least one region within a current image frame, said motion vectors representing a projected direction of motion for the dynamic 3-D model;

means for computing a prediction error value for said at least one region based on the generated motion vectors;

means for determining a type of predictive encoding to be performed on said at least one region in a succeeding image frame based on the value of the prediction error; and

means for encoding said at least one region in the succeeding image frame as indicated by the determined predictive encoding type.

2. The system according to claim 1 wherein said at least one region is a rectangular block and wherein said step of generating motion vectors for each at least one rectangular block comprises:

means for receiving a dynamic 3-D model;

means for computing model motion vectors from the dynamic 3-D model for each block within a current image frame; and

means for generating block-based motion vectors for each block of the image frame, said block-based motion vectors approximating said model motion vectors.

3. The system according to claim 2 wherein the model motion vectors are sampled at a resolution lower than the display resolution.

4. The system according to claim 3 wherein said means for generating said block-based motion vectors to approximate the model motion vectors further comprises:

means for determining a weighted average of the model motion vectors contained within each block of the image frame; and

means for representing the weighted averaged model motion vectors by a single block-based motion vector.

5. The system according to claim 4 wherein the weighted averaging of the model motion vectors within a given block is a function of the area and texture complexity of each region within the block having homogeneous motion.

6. The system according to claim 2 wherein said predictive encoding type includes predictive interblock encoding.

7. The system according to claim 6 wherein said predictive interblock encoding is bidirectional.

8. A method of synthesizing a compressed video bitstream from a dynamic 3-D model, said video bitstream representing an image sequence comprised of a plurality of image frames which are sequential in time, each image frame being partitioned into a set of non-overlapping contiguous regions, each block of said image frame being encoded as indicated by a predictive encoding type, the method comprising the steps of:

performing low resolution rendering upon the 3-D objects which compose the 3-D model to derive a mapping definition for each object and to thereby produce a 2-D image frame;

partitioning each image frame of a time sequence of frames into a set of regions;

generating motion vectors for at least one region within a current image frame, said motion vectors representing a projected direction of motion for the dynamic 3-D model;

computing a prediction error value for said at least one region based on the generated motion vectors;

determining a type of predictive encoding to be performed on said at least one region in a succeeding image frame based on the value of the prediction error; and

encoding said at least one region in the succeeding image frames as indicated by the determined predictive encoding type.

9. The method according to claim 8 wherein said at least one region is a rectangular block, and wherein the step of generating motion vectors for each at least one rectangular block of a current image frame comprises the steps of:

receiving a dynamic 3-D model;

generating block-based motion vectors for each block of the image frame, said block-based motion vectors approximating said model motion vectors.

10. The method according to claim 9 wherein said step of generating the block-based motion vectors to approximate the model motion vectors comprises the steps of:

determining a weighted average of the model motion vectors contained within each block of the image frame; and

representing the weighted averaged model motion vectors by a single block-based motion vector.

11. The method according to claim 10 wherein said predictive encoding type includes predictive interblock encoding.

12. The method according to claim 11 wherein said predictive interblock encoding is bidirectional.

13. The method according to claim 11 further comprising the steps of:

computing prediction errors associated with each block-based motion vector; and

accumulating the prediction errors over a plurality of image frames.

14. The system according to claim 13 wherein said encoding means further comprises:

means for comparing said accumulated prediction errors to a threshold; and

means for synthesizing a block associated with a particular accumulated prediction error if the particular accumulated prediction error exceeds the threshold.

15. The system according to claim 14 further comprising:

means for controlling a rate at which the block is synthesized by adjusting the threshold.

16. A system for synthesizing an image sequence from a dynamic 3-D model, said image sequence comprised of a plurality of image frames which are sequential in time, each image frame being partitioned into a set of contiguous rectangular blocks, the system comprising:

means for receiving a dynamic 3-D geometric model;

means for performing low resolution rendering upon the 3-D objects which compose the 3-D model to derive a mapping definition for each object and to thereby produce a 2-D image frame and to partition each image frame of a time sequence of frames into a set of regions;

means for computing model motion vectors from the dynamic 3-D model;

means for approximating said model motion vectors using block-based motion vector; and

means for accumulating the prediction errors over a plurality of image frames.

17. The system according to claim 16 wherein the model motion vectors are sampled at a resolution lower than the display resolution.

18. The system according to claim 17 wherein said means for approximating model motion vectors further comprises:

means for determining a weighted average of model motion vectors contained within each block of the image frame; and

means for representing the weighted averaged model motion vectors by a single block-based motion vector.

19. The system according to claim 18 wherein the weighted averaging of the model motion vectors within a given block is a function of the area and texture complexity of region within the block having each homogeneous motion.

20. The system according to claim 16 wherein said accumulating means further comprises:

means for determining an area-weighted average of the prediction errors for each block.

21. The system according to claim 20 further comprising:

means for approximating a change in illumination of a given block by adjusting a set of 0,0 DCT coefficients.

22. The system according to claim 20 further comprising:

means for approximating a partial occlusion of a block with a partially transparent nontextural block by adjusting a set of 0,0 DCT coefficients.

23. A method of synthesizing an image sequence from a dynamic 3-D model, said image sequence comprised of a plurality of image frames which are sequential in time, each image frame being partitioned into a set of contiguous rectangular blocks, the method comprising the steps of:

receiving a dynamic 3-D geometric model;

performing low resolution rendering upon the 3-D objects which compose the 3-D model to derive a mapping definition for each object and to thereby produce a 2-D image frame;

partitioning each image frame of a time sequence of frames into a set of regions;

computing model motion vectors from the dynamic 3-D model;

approximating the model motion vectors using block-based motion vectors, said approximation comprising the steps of;

determining a weighted average of model motion vectors using block-based motion vectors, said approximation comprising the steps of;

determining the weighted average of model motion vectors contained within each block of the image frame; and

representing the weighted averaged model motion vectors by a single block-based motion vector.

24. The method according to claim 23 further comprising the steps of:

computing prediction errors associated with each block-based motion vector, and

accumulating the prediction errors over a plurality of image frames.

25. The method according to claim 24 wherein said step of accumulating prediction errors further comprising the step of:

determining an area-weighted average of the prediction errors for each block.

26. The method according to claim 25 further comprising the step of:

approximating a change in illumination of a given block by adjusting a set of 0,0 DCT coefficients.

27. The method according to claim 25 further comprising the step of:

approximating a partial occlusion of a block with a partially transparent nontextural block by adjusting a set of 0,0 DCT coefficients.

28. The method according to claim 27 further comprising the steps of:

determining a type of predictive encoding to be performed on each block in succeeding image frame based on a prediction error value; and

encoding each block in the succeeding image frame as indicated by the determined predictive encoding type.

29. The method according to claim 28 further comprising the steps of:

comparing said accumulated prediction errors to a threshold; and

synthesizing a block associated with a particular accumulated prediction error if the particular accumulated prediction error exceeds the threshold.

30. The method according to claim 29 further comprising the step of:

controlling a rate at which the block is synthesized by adjusting the threshold.

31. A method of synthesizing a compressed video bitstream from a dynamic 3-D model, said video bitstream representing an image sequence comprised of a plurality of image frames which are sequential in time, each image frame being partitioned into a set of contiguous rectangular blocks, the method comprising the steps of:

receiving a dynamic 3-D geometric mode;

performing low resolution rendering upon the 3-D objects which compose the 3-D model to derive a mapping definition for each object and to thereby produce a 2-D image frame;

partitioning each image frame of a time sequence of frames into a set of regions;

computing model motion vectors from the dynamic 3-D model;

approximating model motion vectors using block-based motion vectors;

computing prediction errors associated with each block-based motion vector;

accumulating the prediction errors over a plurality of image frames;

comparing said accumulated prediction errors to a threshold;

synthesizing a block associated with a particular accumulated prediction error if the particular accumulated prediction error exceeds the threshold;

generating a block associated with a particular accumulated prediction error which is less than the threshold from a block from a previous image frame; and

transmitting the synthesized blocks to a video encoded.

32. The system according to claim 31 further comprising:

means for controlling a rate at which the block is synthesized by adjusting the threshold.

33. A centralized interactive graphics system, comprising:

a common database of dynamic 3-D images shared among users so that changes to the database by each user are incorporated into the common database;

a plurality of graphics engine front ends connected to receive 3-D image data from said common database and to generate data structures for creating a particular 3-D scene;

respective hybrid rendering engines connected to said graphics engine front ends to perform low resolution rendering and to determine whether an image block within an image frame is to be encoded as a motion block or an image vector and the type of encoding to be used for said data structures; and

respective video encoder back ends connected to said hybrid rendering engines to encode the motion vector or the image block and transmit the encoded motion vector or the image block.

34. The graphics system of claim 33, wherein said hybrid rendering engine comprises:

means for performing low resolution rendering upon the 3-D objects which compose the 3-D model to derive a mapping definition for each object and to there by produce a 2-D image frame and to partition each image frame of a time sequence of frames into a set of regions;

means for generating motion vectors for at least one region within a current image frame, said motion vectors representing a projected direction of motion for the dynamic 3-D model;

means for computing a prediction error value for said at least one region based on the generated motion vectors;

means for determining a type of predictive encoding to be performed on said at least one region in a succeeding image frame based on the value of the prediction error; and

means for encoding said at least one region in the succeeding image frame as indicated by the determined predictive encoding type.