Color Conversion Using 4.5 Bit Palette

1. Field of the Invention

The present invention relates to signal processing, and, in particular, to computer-implemented methods and apparatus for encoding and decoding color video signals.

2. Description of the Related Art

This invention relates to color video transmissions between two or more nodes, wherein each node is a computer system communicating with other nodes over a selected transmission medium. Because transmission media typically have finite bandwidths, in order to provide color video transmissions of satisfactory quality, each computer system preferably compresses in real time the video signals corresponding to the local participant and transmits the resulting compressed signals to the systems of the remote participants. Each system also preferably receives and decompresses compressed signals from the systems of the remote participants to display the decompressed video signals locally.

What are needed are color video encoding and decoding methods than can be implemented in real time on computer systems to generate compressed video signals that can be transmitted under practical bandwidth constraints and then be decompressed in real time by the receiving systems to provide satisfactory video transmissions.

It is accordingly an object of this invention to overcome the disadvantages and drawbacks of the known art and to provide improved computer-implemented methods and apparatus systems for color conversion of compressed and decompressed video signals to provide satisfactory color video transmissions between computer systems communicating via limited-bandwidth connections.

Further objects and advantages of this invention will become apparent from the detailed description of preferred embodiments which follow.

The present invention comprises a computer-implemented process and apparatus for efficient conversion of color video signals. The most significant bits (MSBs) of YUV data are masked off and converted into a single index that allows for the number of colors needed in a standard display format such as VGA. The Y MSBs are scaled down by a fractional factor prior to the formation of the index so as to save computer memory space that would otherwise be wasted. In a preferred embodiment, relatively low-noise temporally-changing dithering is applied to the Y values of full-sampled YUV data prior to color conversion.

FIG. 1 depicts an RGB color cube.

FIG. 2 shows an RGB color cube on end contained within a YUV color cube.

FIG. 3 shows a typical scale of the allowed values of luminance.

FIG. 4 shows a typical computer-implemented digital video encoding and transmitting system.

FIG. 5 shows a typical digital video receiving and decoding and display system.

Referring now to FIG. 1, therein depicted is a Red-Green-Blue (RGB) color cube. The various nodes depicted show the resulting colors that occur when the system's colors are mixed. If the values of Red, Green, and Blue are each represented by an 8-bit binary word, then there will be 2.sup.8 =256 different levels of each of these colors ranging from zero (black) to 255 (brightest Red, brightest Green, and brightest Blue respectively), thus allowing for a total of (255.times.255.times.255) different colors to be represented| A useful technique is to turn this cube up so that it stands on a "U-V plane" on the "black" corner with the "white" corner pointing vertically up from the "U-V plane" with the vertical axis extending upward between the "black" and "white" corners and being situated in the middle of a larger "YUV" cube as depicted in FIG. 2. In this manner, a linear transformation can be made between the points in the RGB cube and the corresponding points in the YUV cube. Using this approach, the "Y" values represent "luminance" (i.e. degree of brightness, from black (no color) to "white" (all colors). The "U" and "V" values then represent the "chroma" (i.e. hue) of the colors. It is to be noted that this conversion is "inefficient," in that the RGB cube fills only about 20% of the volume of the YUV cube. The values of Y, U, and V outside the RGB cube do not represent any actual color that can be reproduced by the system.

If Y, U, and V are each represented by separate 8-bit binary numbers, then we see that much of the YUV "space" is wasted (i.e. not used). If we truncate each of these 8-bit words down to only the three most significant bits, then there would result a YUV three-dimensional grid having only 8 Y levels (equally-spaced to include 0 at the low end and 224 at the high end), 8 U levels (also similarly equally-spaced), and 8 V levels (also similarly equally-spaced). These would include a total of 512 possible coordinants (i.e. "points") within the YUV cube, but only about 100 of these points would lie within the RGB cube. So this would allow only for about a 100-color "palette" which is much less than is needed for a standard "VGA" 256 color system. Another possibility would be to not truncate the Y word as much as we truncate the U and V values. So, for example, using the four most significant bits (MSBs) of Y, and the three MSBs of U and V respectively, would allow for 16 levels of brightness and 8 levels of U and 8 levels of V for a total of 1024 "points". Only about 20% of these lie within the RGB cube, yielding only about 200 colors which is still too few for a standard VGA system. In the alternative, using the 5 MSBs of Y and the 3 MSBs of U and the 3 MSBs of V results in 2048 "points", with about 400 of them lying within the RGB cube. This is too many for the standard VGA system. Furthermore, the full scale for Y is not used for normal colors. In particular, as is shown in FIG. 3, the "standard" Y values used range between 16 and 235 for a total of 220 possible values, in order to provide for the possibility of "overshoot" in both the bright and dark directions. So even allowing for Y overshoot, the Y.sub.5 U.sub.3 V.sub.3 arrangement provides for about 330 different colors, which is too many| What we are seeking is an arrangement that allows for a 240 color video palette (with 16 additional "standard" colors being "reserved" for graphics purposes). So what we need is something in between the Y.sub.5 U.sub.3 V.sub.3 and Y.sub.4 U.sub.3 V.sub.3 arrangements.

Applicant has discovered a simple but elegant technique for "splitting the difference" and using only as much space in the hardware memory as is actually needed in order to accomplish the goal of a 240 color palette. An 11-bit word is used to represent the Y.sub.5 U.sub.3 V.sub.3 data. Using well-known masking or truncating techniques, the 24-bit YUV data is converted to an 11-bit word with the following format:

Since this arrangement provides for 330 colors, when only 240 are needed, the used "Y-space" can be restricted by using an encoding scheme that uses only the bottom 75% of the available y-space. For example, for an 11-bit word, then are 2.sup.11 =2048 possible values; but if all Y values are first multiplied by 3/4 prior to being encoded ›i.e. Y*=Y-(1/4)Y=(3/4)Y!, then only 1600 possible points can be encoded (i.e. 0-1599) where only 242 of these correspond to colors within the RGB cube. These 242 distinct colors can be mapped via a color look up table (CLUT) into a palette of 240 desired VGA colors as needed in a VGA display. The additional two colors can just be mapped as duplicates of two of the others as determined by the system designer. The remaining hardware memory space normally reserved for the points 1600-2047 can be used for some other purpose, such as storing microcode.

So, for example, consider the original Y, U, V values of Y=100, U=100, V=100. These would first be modified by scaling the Y valued down to Y*=75. So, in 8-bit binary words the Y*UV value becomes:

The next step is to "mask off" (i.e. truncate) and combine these into a W=Y*.sub.5 U.sub.3 V.sub.3 11-bit index format (using the five most significant digits of Y*, and the three most significant digits, respectively, of U and V). So, in this example,

It should be noted that this 11-bit word W allows for finer gradations in the variation of the brightness levels Y* of the colors than are used for the U and V chroma values (i.e. hues) of the colors. This is desirable, since the human eye is more sensitive to luminance "contouring" than it is to chroma contouring The problem of contouring arises due to the fact that the original 256 fine gradations in each of the Y, U, and V values are now changed to 32 brightness levels Y (in "steps of 8" of the original gradations) and 8 chroma levels in each of U and Y (in "steps of 32" of the original gradations). It is therefore desirable to dither the luminance (Y) values with dither matrices having lower noise amplitudes than would corresponding dither matrices for the U and V values. For example, dither matrices having only 16 different levels (e.g. 0-15) of the original gradations would be enough to change any Y* value by an amount of up to two "steps of 8", which is quite adequate to provide excellent contour reduction, while at the same time avoiding undesirable "dithering noise artifacts." The U and the V values would require significantly larger noise amplitudes in the dither matrices in order to be effective. An example of suitable Y dither matrices for 4.times.4 blocks of pixels are the following:

If these dither matrices are applied sequentially in time to the same pixel locations in consecutive frames, the observer's eyes will serve as a "temporal integrator" to help to smooth out the "grainy" dithering artifacts that otherwise tend to occur. So, for example, these matrices could be used alternately in time as follows:

The dithering can be done before or after the above-described color conversion technique is employed. Applicant's laboratory simulations have shown that doing the dithering before the above-described color conversion step gives preferred results (i.e. reduced noticeable artifacts). Computer-implemented techniques for applying a dithering matrix to a block of pixel data are well-known to those skilled in the art. See, for example, "Digital Pictures, Representation and Compression," Plenum Press, 1988, by Netravali & Haskell.

All the above-described techniques can be implemented by well known encoding and decoding computer apparatus as depicted in FIGS. 4 and 5.

Referring now to FIG. 4, there is shown a computer-based encoding system 100 for encoding video image signals, according to a preferred embodiment of the present invention. Analog-to-digital (A/D) converter 102 of encoding system 100 receives analog video image signals from a video source. The video source may be any suitable source of analog video image signals such as a video camera or VCR for generating local analog video image signals or a video cable or antenna for receiving analog video image signals from a remote source. A/D converter 102 decodes (i.e., separates the signal into constituent components) and digitizes each frame of the analog video image signals into digital image component signals (e.g., in a preferred embodiment, Y, U, and V component signals).

Capture processor 104 receives, captures, and stores the digitized component signals as subsampled video images in memory device 112 via bus 108. Each subsampled video image is represented by a set of two-dimensional component planes or pixel bit maps, one for each component of the digitized video image signals. In a preferred embodiment, capture processor 104 captures video image signals in a YUV9 or YUV4:1:1 format, in which every (4.times.4) block of pixels of the Y component plane corresponds to a single pixel in the U component plane and a single pixel in the V component plane.

Pixel processor 106 accesses captured bitmaps from memory device 112 via bus 108 and generates encoded image signals that represent one or more of the captured video images. Depending upon the particular encoding method implemented, pixel processor 106 applies a sequence of compression techniques to reduce the amount of data used to represent the information in each image. The compression method of motion estimation in accordance with the present invention will be further described below. The encoded image may then be stored to memory device 112 via bus 108 for transmission to host processor 116 via bus 108, bus interface 110, and system bus 114 for storage in host memory 126. Pixel processor 106 also may contain local memory 130, which is a tightly-coupled on-chip memory suitable for locally storing a number of pixels and other data. Those skilled in the art will appreciate that system bus 114 and bus 108 may be merged into the same system bus 114. It will further be understood that host processor 116 may in alternative preferred embodiments perform the functions of pixel processor 106 described herein. Similarly, in alternative preferred embodiments a general memory device such as host memory 126 or memory device 112 may perform the functions of local memory 130 described herein.

Host processor 116 may transmit the encoded image to transmitter 118 for real-time transmission to a remote receiver (not shown in FIG. 4), store the encoded image to mass storage device 120 for future processing, or both. In addition, digital-to-analog converter 122 may receive and convert digital image signals to analog image signals for display in one or more windows on monitor 124. These image signals may correspond, for example, to raw captured video images or companded video images (i.e., the results of compressing and decompressing selected captured video images).

Referring now to FIG. 5, there is shown a computer-based decoding system 200 for decoding the image signals encoded by encoding system 100 of FIG. 4, according to a preferred embodiment of the present invention. Host processor 208 of decoding system 200 receives encoded image signals via system bus 206 that were either stored in mass storage device 212 or received by receiver 210 from a remote transmitter, such as transmitter 118 of FIG. 1. The host processor 208 temporarily stores the encoded image signals in host memory 214.

Host processor 208 decodes the encoded image signals and scales the decoded image signals for display. Decoding the encoded image signals involves undoing the compression processing implemented by pixel processor 106 of encoding system 100 of FIG. 4. Scaling the decoded image signals involves upsampling the U and V component signals to generate full-sampled Y, U, and V component signals in which there is a one-to-one-to-one correspondence between Y, U, and V pixels in the scaled component planes. Scaling may also involve scaling the component signals to a display size and/or resolution different from the image signals as original captured. Host processor 208 then stores the scaled decoded image signals to host memory 214 for eventual transmission to digital-to-analog (D/A) converter 202 via system bus 206. D/A converter converts the digital scaled decoded image signals to analog image signals for display on monitor 204.

Referring again to FIG. 4, encoding system 100 is preferably a general microprocessor-based personal computer (PC) system with a special purpose video-processing plug-in board. In particular, A/D converter 102 may be any suitable means for decoding and digitizing analog video image signals. Capture processor 104 may be any suitable processor for capturing digitized video image component signals as subsampled frames. Pixel processor 106 may be any suitable means for encoding subsampled video image signals, where the means is capable of implementing functions such as a forward discrete cosine transform and a motion estimation and block matching procedures as described in further detail below. Memory device 112 may be any suitable computer memory device and is preferably a dynamic random access memory (DRAM) device. Bus 108 may be any suitable digital signal transfer device and is preferably an Industry Standard Architecture (ISA) bus or Extended ISA (EISA) bus or a Peripheral Component Interface (PCI) bus. Bus interface 110 may be any suitable means for interfacing between bus 108 and system bus 114. In a preferred embodiment, A/D converter 102, capture processor 104, pixel processor 106, bus 108, bus interface 110, and memory device 112 are contained in a single plug-in board, such as an Intel.RTM. ActionMedia.RTM.-II board, capable of being added to a general microprocessor-based personal computer (PC) system.

Host processor 116 may be any suitable means for controlling the operations of the special-purpose video processing board and is preferably an Intel.RTM. general purpose microprocessor such as an Intel.RTM. 386, 486or Pentium.RTM. processor. Host memory 126 may be any suitable memory device used in conjunction with host processor 116 and is preferably a combination of random access memory (RAM) and read-only memory (ROM). System bus 114 may be any suitable digital signal transfer device and is preferably a PCI bus. Alternatively, system bus 114 may be an Industry Standard Architecture (ISA) bus or Extended ISA (EISA) bus. Mass storage device 120 may be any suitable means for storing digital signals and is preferably a computer hard drive. Transmitter 118 may be any suitable means for transmitting digital signals to a remote receiver and is preferably transmits digital signals over PSTN lines. Those skilled in the art will understand that the encoded video signals may be transmitted using any suitable means of transmission such as telephone line (PSTN or ISDN), RF antenna, local area network, or remote area network.

D/A converter 122 may be any suitable device for converting digital image signals to analog image signals and is preferably implemented through a personal computer (PC)-based display system such as a VGA or SVGA system. Monitor 204 may be any means for displaying analog image signals and is preferably a VGA monitor.

Referring now again to FIG. 5, decoding system 200 is preferably a general microprocessor-based personal computer (PC) system similar to the basic PC system of encoding system 100. In particular, host processor 208 may be any suitable means for decoding and scaling encoded image signals and is preferably an Intel.RTM. general purpose microprocessor such as an Intel.RTM. 386, 486, or Pentium.RTM. processor. Host memory 214 may be any suitable memory device used in conjunction with host processor 116 and is preferably a combination of random access memory (RAM) and read-only memory (ROM). In an alternative preferred embodiment, decoding system 200 may also have a pixel processor similar to pixel processor 106 of FIG. 4 for decoding the encoded image signals and a display processor such as an Intel.RTM. i750.RTM. Display Processor for scaling the decoded image signals.

System bus 206 may be any suitable digital signal transfer device and is preferably an Industry Standard Architecture (ISA) bus or Extended ISA (EISA) bus. Mass storage device 212 may be any suitable means for storing digital signals and is preferably a CD-ROM device. Receiver 210 may be any suitable means for receiving the digital signals transmitted by transmitter 118 of encoding system 100. D/A converter 202 may be any suitable device for converting digital image signals to analog image signals and is preferably implemented through a personal computer (PC)-based display system such as a VGA or SVGA system. Monitor 204 may be any means for displaying analog image signals and is preferably a VGA monitor.

In a preferred embodiment, encoding system 100 of FIG. 4 and decoding system 200 of FIG. 5 are two distinct computer systems. In an alternative preferred embodiment of the present invention, a single computer system comprising all of the different components of systems 100 and 200 may be used to encode and decode video image signals. Those skilled in the art will understand that such a combined system may be used to display decoded video image signals in real-time during the capture and encoding of video signals to monitor the encoding processing.

Although preferred embodiments of the method and apparatus of the invention have been described in detail herein, Applicant's invention is not limited thereto, but rather is defined by the appended claims and their fair equivalents.