System and Method of Generating Compressed Video Graphics Images

The present invention relates to computer graphics systems for generating video images.

Computer animation is a term used to describe any application in which a computer aids in the generation and manipulation of a sequence of changing images. Computer animation is widely used in industry, science, manufacturing, entertainment, advertising and education. Examples of computer animation applications are computer aided design (CAD), flight simulation and video games.

Certain high performance interactive graphics systems, such as computer workstations, flight simulators and other types of video systems, require complex three-dimensional (3-D) rendering programs to generate realistic two-dimensional (2-D) images of animated 3-D graphics scenes. Essentially, the task of a rendering program is to transform a 3-D geometric model, stored as a computational representation of objects, into a 2-D image displayable on a computer display.

The relative positions of image components create a perspective for the viewer, and the appearance of three dimensions. Successive 2-D image frames create the illusion of movement within the reproduced scene. Many times these 2-D images are used in applications which also require interactivity by the user. For many of these interactive applications, computer animation having real-time response is highly desirable.

For example, with the advent of interactive television systems comes the desire to provide services, such as video games, which allow the subscriber to interact with the system or other subscribers to the system. Because each subscriber can interact with the system independently from other subscribers, each subscriber's perspective of the generated image sequences is different. The subscriber's perspective may be dependent on factors, such as the position and direction of view in which a subscriber is looking, the type of screen on which the images are displayed, the degree of action portrayed by the images and the number of subscribers interacting with the particular application. As such, a separate set of video signals must be generated for each subscriber which accurately represents the particular subscriber's perspective of the images. Using current technology, a graphics generator and a separate video encoder would be used to generate each set of video signals.

The costs involved in providing each subscriber with his own graphics generator and video encoder are economically unattractive. Another concern is the latency of the system. Latency is the time required for the system to begin display of the desired video signal once the user input is received. Latency is caused by certain functions performed by the video encoder, such as motion approximation, prediction error computations, and buffer size requirements, which comprise a large percentage of the amount of time required to encode the images of the 3-D models. If the latency is too great, real time response is not possible. It would be desirable to reduce the latency and cost of the system by providing an interactive system which is capable of generating compressed video signals without requiring a separate graphics generator and video encoder for each subscriber.

The present invention is directed to such an interactive system. We have recognized that some of the rendering functions conventionally performed by a graphics generator and the encoding functions conventionally performed by a video encoder can be combined in a hybrid system which is capable of computing and encoding information during the rendering of the image frames needed to generate compressed video signals.

In accordance with the present invention, a hybrid system for synthesizing a compressed video bitstream from a dynamic 3-D model has been realized. 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.

By determining the type of video encoding to be performed on each region within an image frame during the rendering of the region, the latency of the system is significantly reduced. The approximation techniques traditionally performed by the video encoder used to determine the type of encoding to be performed are computationally intensive. Since these computations are now part of the rendering process, the latency in the overall system is reduced, and more importantly, the overall system hardware complexity is also reduced which reduces the cost of the system.

The hybrid system also allows for the creation of a centralized interactive graphics system which is capable of remotely generating images of 3-D scenes on each viewer's screen. A centralized system also reduces costs by timesharing the hardware among all of the subscribers.

FIG. 1 illustrates a schematic diagram of a video system implemented in accordance with an illustrative embodiment of the present invention.

FIG. 2 illustrates a block diagram of the centralized interactive graphics system of FIG. 1.

FIG. 3 illustrates a block diagram of the hybrid renderer engine of FIG. 2.

FIG. 4 is a flow chart illustrating the functions performed by the centralized interactive graphics system of FIG. 1.

FIG. 5 illustrates two objects contained within a single image frame.

FIG. 6 illustrates a schematic diagram of sequential video frames on which temporal correlation measurements are performed.

FIG. 7 illustrates a pair of sequential image blocks and the model motion vectors and block-based motion vector associated therewith.

FIG. 8 illustrates an overlay of a current image block over a section of four image blocks from a previous image frame.

FIG. 9 illustrates a block diagram of the video encoder of the video system of FIG. 1.

FIG. 10 illustrates a block diagram illustrating the computer architecture for the centralized interactive graphics system of FIG. 2.

A general overview of a video system 10 incorporating the principles of an illustrative embodiment of the present invention is illustrated in FIG. 1. A plurality of display devices, illustratively television receivers 12, are connected to network 14 by means of a cable 16. A set-top box (not shown) may be associated with each television 12 for transmitting and receiving instructions via the network 14. A centralized interactive graphics system (CIGS) 18, also associated with network 14, is capable of generating computer graphics.

In operation, network 14 processes incoming requests from subscribers for services which may include interactive graphics services such as, for example, video games. The network 14 retrieves the requested video game from CIGS 18. The game is transmitted over cable 16 to the set-top box associated with the television receiver 12 of the subscriber requesting the video game. An input device 24, such as an air mouse, associated with each subscriber's television receiver 12 transmits instructions to the network 14 regarding the progression of the game.

FIG. 2 shows CIGS 18 in more detail. In a multiuser game, a common database 225 is shared among the users and changes to the database 225 by each user are incorporated into the common database 225. This view-independent processing is shared among the users to reduce cost and latency in contrast with updating separate databases for each user. CIGS 18 includes a graphics engine front end 205, a hybrid rendering engine 210 and a video encoder backend 215 for each user. The graphics engine front end 205 generates data structures required for creating a particular 3-D scene. Each data structure comprises a group of mathematically described objects which are defined by points, lines, polygons and three dimensional solids. Using techniques well known in the art, details relating to each object's shape, texture and color values can also be defined. Each object, in turn, is defined, relative to the other objects contained in the 3-D scene, by a matrix which includes information regarding rotation, scaling, shearing and translation. The processes performed by the graphics engine front end 205 are described in Computer Graphics: Principles and Practice, James D. Foley, et al., Addison Wesley, 1990.

The hybrid rendering engine 210 performs conditional rendering on the 3-D objects, that is, transforming the data representing 3-D objects to data representing 2-D images. The 2-D images are incorporated into an image sequence which is comprised of a plurality of successive image frames which represent an animated 3-D scene. Adjacent image frames tend to be highly correlated due to small changes in object position and camera position during one frame time. Each image frame is comprised of a plurality of subunits or pixels. Each image frame is also subdivided into a plurality of image blocks each containing a predetermined number of pixels, e.g., 16.times.16 pixels.

Motion vectors are generated for each image block which represent the projected direction of motion for any image of an object represented in the current image block and therefore predict the position of the image of the object in a subsequent image frame. Texture complexities which define spatial frequency energy associated with each region are also determined. The motion vectors and texture complexities for each image block are used to compute a prediction error which is accumulated over successive image frames. The prediction error is used to determine the type of encoding performed on each image block in successive image frames as will be described in detail hereinafter. Once the hybrid rendering engine 210 has determined the type of encoding to be performed on a successive image block, the decision is transmitted to the video encoder back end 215 which encodes the motion vector or image block and transmits the encoded motion vector or image block to the television receiver 12 of FIG. 1.

The architecture for the system in FIG. 2 includes general and special purpose processors as illustrated in FIG. 10. Parallel general purpose processors are used to compute the model transformations, motion vectors, coding mode decisions and rate control parameters. High speed special purpose processors or ASIC's are used to perform scan conversion of textured polygons, DCT, DCT coefficient quantization and variable length coding, and data formatting of the coded video. The special purpose processing can reside on the system bus of a general purpose multiprocessor host computer 1010 with a separate digital video interface located between a scan converter 1015 and video encoder 1020.

Referring to FIGS. 3 and 4, the hybrid rendering engine 210 will be described in more detail. Low resolution rendering 305 is performed on the 3-D objects which includes applying a perspective transformation to the 3-D objects in which the objects undergo a series of mathematical transformations, as described below. The perspective transformation orients the objects in space relative to the viewer, scales the objects to the proper size, adjusts for perspective foreshortening, and clips the objects to the desired display volume (step 410). Also included in the transformations are surface details which simulate color and texture, and shading details to simulate reflections of light. By performing these transformations, a mapping definition is derived for each object to produce a 2-D image.

In general, each object, as defined by a given image frame, comprises a set of discrete points, each point comprising x,y,and z coordinates. Each image sequence represents the movement of objects in successive image frames. Prior to generating each successive image frame, a temporal interframe correlation 310 is determined with respect to the position of each object contained in a current image frame relative to its position in the previous image frame (step 415). The temporal correlation is determined by the motion of each of the objects and the interframe visibility of the object. The information obtained from the temporal correlations is used for the encoding decision 315 which will be described in detail hereinafter.

Intraframe visibility of an object depends firs fly upon whether there is an overlap of the x,y coordinate positions of the images of one or more objects within the image frame. If there is an overlap of the x,y coordinates, illustratively the position of the z coordinate for the image of each object is considered to determine the visibility of the images of each of the objects. In an image space representation, the z coordinate corresponds to depth. An image of an object having a greater z coordinate and, hence a greater depth, will be obscured by the image of an object having a smaller z coordinate if the images have overlap in x and y coordinates. In such a case, the image of the object having the smaller z coordinate at least partially blocks the view of the image of the other object. Alternatively, the objects can be drawn in a lower to higher priority ordering with higher priority objects being overwritten on lower priority objects. Generally higher priority objects represent "near" objects and lower priority objects represent "far" objects. Such a situation is illustrated in FIG. 5.

FIG. 5 illustrates images of two objects 505, 510 displayed within an image frame 515. Part of image 510 is illustrated by a dashed line to indicate that the view of image 510 is partially obstructed by image 505. The dashed line also signifies that while both image 505 and image 510 have the same x and y coordinates within that defined area, image 510 has a greater z coordinate than image 505.

FIG. 6 illustrates the motion of the image 605 of an object in two successive image frames 610, 615. A matrix Mt.sub.1 is used to represent the position of the image 605 in the first frame 610 at time t=1. A second matrix Mt.sub.2 is used to represent the position of the image 605 in the second frame 615 at time t=2. Each matrix defines the transformation of the original object with respect to rotation, translation, scaling and shearing. A surface point 620 of the image 605 in the second frame 615 is correlated to the frame position in the first frame 610. A determination is made of whether the surface point 620 is positioned in the same corresponding frame position in the first frame 610 using the following equation:

where

P.sub.t1 =surface point of image at t=1

P.sub.t2 =surface point of image at t=2

M.sub.t2.sup.-1 =inverse of matrix used to represent image at t=2.

M.sub.t1 =matrix used to represent image at t=1.

proj=division by homogeneous coordinate W

Interframe visibility is an important component in determining temporal correlation. Interframe visibility is confirmed if an ID number associated with P.sub.t1 equals an ID number associated with P.sub.t2. If the surface point 620 is the same thereby signifying movement of an object 605, the difference in x and y coordinate position is determined. The temporal correlation of a number of surface points contained in frame 615 relative to corresponding surface points contained in frame 610 are determined in the same manner.

If a portion of an image of an object is visible in the current image frame but obstructed in the previous image frame, temporal correlation of the surface points is not defined. In such a case, the pixels representing that portion of the image would soon have to be synthesized from the original 3-D model to avoid visible error. However, in the case where an image of an object is visible both in the current image frame and the previous image frame, the movement of the image in a subsequent image frame can be approximated using motion vectors (step 420). Motion vectors can be generated from the temporal correlations for each surface point of the image. The motion vectors approximate the direction and rate of movement in a subsequent image frame.

Model motion vectors are generated for each image block by sampling a number of the pixels contained in the block for a given image frame. The image block is illustratively a 16.times.16 pixel block. If the model motion vectors indicate that the image block represents a homogeneous region, i.e., that the model motion vectors are generally pointing in the same direction, the model motion vectors are averaged and the dominant vector, also referred to as the block-based motion vector, is used to represent the block. The number of pixels sampled in each block is determined by balancing considerations of computational efficiency and block-based motion vector accuracy.

As illustrated in FIG. 7, if model motion vectors 720 for an image block 705 indicate that the block 705 contains more than one homogeneous region 710 and 715, the model motion vectors 720 are weighted based on the size of each region 710 and 715 and the texture complexity in each region 710 and 715 using the following relationship:

where

S.sub.r =score for region r

A.sub.r =area of region r

T.sub.r =texture complexity associated with each region r

M.sub.r =degree of motion vector similarity within region r ##EQU1##

The model motion vectors 720 for each region 710 and 715 are averaged to obtain a region motion vector 725 and 730. A score S.sub.r is obtained for each region motion vector 725 and 730 using the above equation. The region motion vector within the 16.times.16 block which receives the highest score is determined to be the block based motion vector 740.

Once the block based motion vectors are generated for each image block contained in the image frame, a prediction error is computed for each block from the block based motion vector error (step 425 of FIG. 4). The prediction error for each block is computed based on the following relationship: ##EQU2## where PE.sub.b =prediction error for a given block

T.sub.r =texture complexity of region r

MV.sub.model =model motion vector

MV.sub.block =value of block-based motion vector

Typically, an image block for a current image frame overlaps four image blocks of a previous image frame as illustrated in FIG. 8. Current image block 810 overlaps previous image blocks 815, 820, 825 and 830. In order to determine the accumulated prediction error for current image block 810, a weight w.sub.1, w.sub.2, w.sub.3 and w.sub.4 is associated with the portion of the current image block 810 overlapping previous image blocks 815, 820, 825 and 830 respectively. The prediction error p.sub.1, p.sub.2, p.sub.3 and p.sub.4 computed for each previous image block 815, 820, 825 and 830 is multiplied by the respective weight to determine the prediction error for the current image block 810 in the following manner:

where

P.sub.i =prediction error for current image block

w.sub.1 +w.sub.2 +w.sub.3 +w.sub.4 =1 (normalized)

The total prediction error for the image block 810 in the current image frame is the sum of P.sub.i and PE.sub.b.

As successive image frames are generated, the prediction errors for each image block are accumulated. If the accumulated prediction error for a given image block is below a predefined threshold, the block based motion vector for that image block is transmitted to the video encoder back end 215 of FIG. 2 which constructs the image block from the block based motion vector as described below (step 440 of FIG. 4). If the accumulated prediction error is above the predetermined threshold, the next image block is generated by the video encoder back end 215 which encodes the block as described below (step 435). In this case, the prediction error for this block is set to zero for the purpose of prediction error accumulation in the next frame.

In preferred embodiments, the video encoder back end 215 follows the MPEG (Coding of Moving Pictures and Associated Audio) standard which is well known in the art and is described in Video Draft Editing Committee, "Generic Coding of Moving Pictures and Associated Audio," Recommendation H.262, ISO/IEC 13818-2, Committee Draft for Video, Seoul, November 1993 and "ISO CD 11172-2: Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbits/s," November 1991. The MPEG standard encoding incorporates predictive encoding techniques which include the use of both intrablock and interblock coding techniques in combination with the discrete cosine transform, adaptive coefficient quantization, run length encoding and statistical or Huffman encoding. Intrablock encoding does not use temporal prediction (motion compensation) but only uses information contained in the current frame to encode a given image block. Interframe encoding is the generation of encoded block data from, for example, the differences between information from a current source block and a block predicted from prior blocks. The MPEG standard incorporates two basic types of interblock encoding. The first develops predictive blocks, referred to as "P" blocks, from the current block and a prior block. The second develops bidirectionally predictive blocks, referred to as "B" blocks, from the current block and a prior or a subsequent block. Blocks which are intrablock encoded are referred to as "I" blocks. Other types of predictive encoding techniques may be employed by the video encoder back end 215 without departing from the scope and spirit of the present invention.

In accordance with the present invention, the MPEG encoding is determined on a block by block basis, where each block has the dimensions of 16.times.16 pixels. As such, I blocks, P blocks, and B blocks can be generated based on the prediction error determination of the graphics generator. When the accumulated prediction error falls below the threshold as described above, the current block is copied from the previous frame using the block based motion vector. In the case of B blocks, the motion vector can refer to a past or future frame, or both with averaging. Accordingly, the video encoder back end 215 generates P block or B blocks based on the transmitted motion vectors. When the accumulated prediction error is above the threshold, the video encoder back end generates an I block and the accumulated prediction error is set to zero.

The rate at which I-blocks are generated is limited by the capacity of the renderer and by the maximum bit-rate allowed for the transmission of coded video. This necessitates the use of a rate control mechanism which limits the number of I-blocks per frame. Typically the I-block rate is periodically monitored during a frame time and the PE threshold is adjusted to achieve a target I-block rate. The I-block rate and threshold are further adjusted down and up respectively if the coded video buffer becomes too full.

FIG. 9 illustrates the video encoder back end 215 of FIG. 2 in more detail. The video encoder back end 215 generally performs the same encoding functions as is performed in a conventional video encoder once the encoding type decision for each image block has been determined. A discrete cosine transform (DCT) circuit 905 develops sets of 8.times.8 frequency domain coefficients. Adaptive quantizer 910 quantizes the transformed coefficients. A formatter 915 performs variable length encoding of the generated DCT coefficients thereby producing variable length encoded codewords. The codewords are then formatted with the appropriate header information in order to facilitate decoding by the receiver. The motion vector information is also received by the formatter 915. The coded data is transmitted to bit buffer 920 which transmits the encoded data to television receiver 12. Each of the elements of the video encoder back end 215 are described more fully in commonly assigned U.S. Pat. No. 5,144,423 issued to Knauer et. al. on Sep. 1, 1992, and incorporated herein by reference.

Additional coding and rendering efficiency can be obtained by approximating the effect of changes in illumination or shading, or partial occlusion of a region with a partially transparent object. Changes in shading can be approximated by adding or subtracting from the lowest order or 0,0 DCT coefficient for a given block of luminance DCT coefficients. Changes in the color of illumination require that both luminance and chrominance 0,0 coefficients be offset. The effect of this is to offset the average value of the corresponding blocks of pixels. The effect of partial occlusion by a non-textured and partially transparent object can be approximated by applying an offset to both luminance and chrominance 0,0 DCT coefficients.

By determining the type of video encoding to be performed on each region within an image frame during the rendering of the legion and using block-based motion vectors to compute prediction error, the latency of the system is significantly reduced. The approximation techniques traditionally performed by the video encoder used to determine the type of encoding to be performed are computationally intensive. Since these computations are now part of the rendering process, the latency in the overall system is reduced, and more importantly the overall system hardware complexity is reduced which lowers the cost of the system.

It will be appreciated that those skilled in the art will be able to devise numerous and various alternative arrangements which, although not explicitly shown or described herein, embody the principles of the invention and are within its scope and spirit.