Method and Apparatus for Generating CLUT-format Video Images

1. Field of the Invention

The present invention relates to video imagery, and, in particular, to methods and apparatuses for generating CLUT-format video images from three-component video data.

2. Description of the Related Art

It is desirable to display real-time motion video on personal computer (PC) systems. In conventional digital video systems, each picture element (i.e., pixel or pel) of a video image is represented by three multi-bit values. For example, in YUV-format systems, each pixel is represented by three 8-bit parameters Y, U, and V. The values of Y, U, and V for a pixel correspond to the color of the pixel.

Theoretically, since each 8-bit parameter Y, U, and V can have 2.sup.8 or 256 different values, there are 2.sup.24 or 16,777,216 possible combinations of Y, U, and V in YUV format. Most of these combinations, however, either do not correspond to real colors or are not needed to satisfy typical fidelity requirements for video imagery.

To display video images on PC systems, the YUV data for each pixel may be converted to a color look-up table (CLUT) index value. The CLUT is a palette that contains a defined set of colors for display on the PC system. For example, a CLUT may contain 2.sup.8 or 256 different colors. Since video imagery in YUV format typically contains more than 256 different colors, converting the three 8-bit YUV image data to single 8-bit CLUT index values involves selecting CLUT colors that are "close" to the actual YUV colors.

When displaying video imagery on PC systems having a limited number of CLUT palette colors, color fidelity may be improved by dithering. Dithering involves the "mixing" at the pixel-to-pixel level of different colors from the CLUT palette to give the subjective look of a color closer to the actual YUV color.

It is also desirable, in a PC system for displaying real-time motion video, to store the video data efficiently and to process and display the data sufficiently fast to present the look of real-time motion. To reduce data storage requirements, digital video image data may be stored in a subsampled format. For example, in YUV-9 format, each four-pixel-by-four-pixel subimage of each video image is represented by sixteen 8-bit Y values (i.e., one Y value for each of the sixteen pixels in the subimage), only one 8-bit U value, and only one 8-bit V value. Similarly, in YUV-12 format, each two-pixel-by-two-pixel subimage is represented by four Y values, one U value, and one V value.

It is therefore an object of the present invention to provide methods and apparatuses for generating CLUT-format video images on PC systems.

It is another object of the present invention to convert three-component video data into CLUT format.

It is another object of the present invention to generate dithered video images.

It is another object of the present invention to generate CLUT-format video images from subsampled video data.

It is a specific object of the present invention to convert subsampled video data in YUV-9 or YUV-12 format to full-resolution, dithered, CLUT-format video data with sufficient speed and quality to display real-time motion video on PC systems.

Further objects of this invention will become apparent from the detailed description of a preferred embodiment which follows.

The present invention is a method and apparatus for generating a video image. According to a preferred embodiment of the present invention, full-resolution three-component video data corresponding to the video image are provided and processed to generate N-bit index data for a lookup table. M-bit CLUT index data are then generated in accordance with the lookup table and the N-bit index data, where M is less than N. The video image is then generated in accordance with the M-bit CLUT index data.

Other objects, features, and advantages of the present invention will become more fully apparent from the following detailed description of the preferred embodiment, the appended claims, and the accompanying drawings in which FIG. 1 is a block flow diagram of the processing of a video image generation system according to a preferred embodiment of the present invention.

FIG. 2 is a block diagram of the video image generation system of FIG. 1.

The present invention is a method and apparatus for generating CLUT-format video images from full-resolution three-component video data. Full-resolution video data have three component values for each pixel. The full-resolution, three-component video data are processed to generate for each image pixel an index value for a lookup table. The lookup table, which maps from the index values to CLUT index values, is used to convert the index data to full-resolution CLUT-format video data. The video images may then be generated using the CLUT-format data.

According to preferred embodiments of the present invention, the full-resolution, three-component video data are generated by upsampling subsampled three-component video data either by replication or by interpolation. The subsampled video data may be in either YUV-9 or YUV-12 format. The index data are generated by: (1) adding ordered (or alternatively random) noise to the full-resolution data, (2) truncating the three "noisy" components, and (3) combining the truncated "noisy" components to form a single index value for each pixel. Under this preferred embodiment, dithered video images may be generated.

Referring now to FIG. 1, there is shown a block flow diagram of the processing of a video image generation system 100 according to a preferred embodiment of the present invention. System 100 receives subsampled three-component video data and converts that data to generate CLUT-format video images.

More particularly, means 102 of system 100 receives three-component video data in subsampled YUV-9 format (having one 8-bit U value, one 8-bit V value, and sixteen 8-bit Y values for every (4.times.4) subimage of every video image). Means 102 upsamples the subsampled data to generate full-resolution, three-component video data. Means 102 performs this upsampling preferably by replicating the U and V data, that is, by copying each U and V value fifteen times so that each pixel of each (4.times.4) subimage has values for Y, U, and V.

In an alternative preferred embodiment, means 102 upsamples the subsampled data by interpolating between U values and between V values to "fill in" the subimages. While such interpolation may produce images of higher quality than images generated by replication, replication is faster than interpolation.

After means 102 upsamples the subsampled data, means 104 adds ordered noise to the full-resolution, three-component data. The purpose of adding noise is to produce dithered video images. In a preferred embodiment, means 102 adds noise by adding (2.times.2) dither matrices D.sub.u and D.sub.v to the U and V data, respectfully, such that: ##EQU1## For example, adding noise to a (4.times.4) sub image having U values: ##EQU2## becomes: ##EQU3## and having V values: ##EQU4## becomes: ##EQU5##

After means 104 adds noise to the U and V data, means truncates the 8-bit Y, U, and V data for each pixel and combines the truncated data to form a single 13-bit index value I, where the four most significant bits (MSB's) of I are the four MSB's of the "noisy" V value, the next four bits of I are the four MSB's of the "noisy" U value, and the five least significant bits (LSB's) of I are the five MSB's of the Y value.

The 13-bit index I is the index for a lookup table that preferably maps from the 13-bit index data to standard 8-bit CLUT index data used to generate video images on PC systems. Means 108 uses the values of index I generated by means 106 to access the lookup table to retrieve an 8-bit CLUT index value for each pixel. Means 110 uses these CLUT-format data to generate one or more video images on a PC system display. This processing is performed for each (4.times.4) subimage of each video image in the sequence of video images to be displayed.

Image generation system 100 is preferably implemented in assembly language code running on a general programmable central processing unit (CPU), such as an Intel 486 processor.

The lookup table is preferably generated off-line. The lookup table contains 2.sup.13 or 8192 entries corresponding to the 8192 possible 13-bit index values I=(i.sub.12 i.sub.11 i.sub.10 i.sub.9 i.sub.8 i.sub.7 i.sub.6 i.sub.5 i.sub.4 i.sub.3 i.sub.2 i.sub.1 i.sub.0). The entry for each index value I corresponds to one of the 256 index values for an 8-bit CLUT table. As described above, the first four bits of I correspond to V data, the second four bits correspond to U data, and the last five bits correspond to Y data. To generate the lookup table, the data for each possible index value I are separated and normalized into 8-bit Y.sub.norm, U.sub.norm, and V.sub.norm values, such that: ##EQU6##

The entry for each 13-bit index value I is preferably the CLUT index value that corresponds to the color that is "closest" to the normalized YUV data for that index value I. The "closest" CLUT color for a particular index value I may be found by sequentially comparing its normalized YUV data Y.sub.norm, U.sub.norm, and V.sub.norm to all 256 CLUT colors and selected the "closest" color.

When means 104 adds noise to U and V data to generate dithered images, overflow may occur if the U or V values are close to 255. For example, if U=241=(1 1 1 1 0 0 0 1), then the addition of an ordered-noise value of 16 or (0 0 0 1 0 0 0 0) causes the 8-bit U value to overflow, leaving (0 0 0 0 0 0 0 1). To avoid erroneous dithering resulting from such overflow, the lookup table is preferably generated taking overflow into account. A "distance" D between the normalized YUV data Y.sub.norm, U.sub.norm and V.sub.norm for a particular index value I and a CLUT color Y.sub.clut, U.sub.clut, and V.sub.clut is defined according to Equation (3) below: ##EQU7## where min returns the smallest of the four square-root expressions. The distance D is used to select the "closest" CLUT color for each of the 8192 possible index values I when generating the lookup table. Those skilled in the art will understand that use of Equation (3) is equivalent to considering UV-space to be a torus rather than a plane.

Referring now to FIG. 2, there is shown a block diagram of a video image generation system that implements the processing of FIG. 1, according to a preferred embodiment of the present invention. Means 202 receives and upsamples subsampled YUV video data to generate full-resolution YUV video data. Means 204 adds dither noise to the full-resolution YUV video data to generate dithered YUV video data. Means 206 truncates the dithered Y,U,V components to 5,4,4 bits, respectively. Means 208 combines the truncated Y,U,V components to generate 13-bit indices to a lookup table. Means 210 accesses the lookup table using the 13-bit indices to generate 8-bit CLUT indices. Means 212 uses the 8-bit CLUT indices to generate video images.

Those skilled in the art will also understand that alternative preferred embodiments of video image generation system 100 fall within the scope of the present invention. For example, other forms of ordered noise, or even random noise, may be added to the full-resolution, three-component data to produce dithered video images. Similarly, the sizes of the lookup table and the CLUT table may vary. Those skilled in the art will understand that a preferred embodiment of the present invention has a lookup table that is larger than the CLUT table used to generate the video images. As such, the index I preferably has more bits than the CLUT index.

In addition, video image generation systems according to the present invention may be designed to generate video images from video data in formats other than the subsampled YUV-9. For example, systems may be designed to process full-resolution YUV data, subsampled video data in YUV-12 or YUV-16 formats, or various subsampled or full-resolution RGB formats.

It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the principle and scope of the invention as expressed in the following claims.