Temporally Dissolved Dithering

This invention relates to digital video image processing, and more particularly to dithering in conversion of image data from a YUV-like format to an RGB format.

In color conversion systems, such as those used to convert from YUV9 to RGB8, the source data format contains more precision than the destination format. An example of this concept is depicted in FIG. 1, which shows an entire color conversion process going from YUV24 to YUV9 to CLUT8 (i.e., RGB8) and then to RGB24 for display. In particular, therein is depicted the mapping from YUV9 to RGB8, wherein large groups of YUV9 colors all become particular RGB8 colors. These 256 RGB8 colors then are converted via the CLUT (Color Look Up Table) into the 256 particular RGB 24 values picked by the designer of the CLUT a priori.

In the conversion from YUV24 to YUV9, an undesirable reproduction artifact can be introduced into the image due to the fact that single U and V values are used, for example, for 4.times.4 groups of 16 Y values. In common practice, these artifacts are eliminated or at least reduced either by use of various interpo-lation techniques on the U and V values within the 4.times.4 groups.

Similarly, in the conversion from YUV9 to RGB8, another undesirable reproduction artifact known as "contouring" can occur. For example, when large areas of the image have only slight variations in color, those areas will be represented by only one of the 256 RGB8 colors, and the reproduced image can have distinct noticeable contours outlining those areas. Contouring is associated with the ability of the human visual system to perceive small changes in image intensity in areas of an image that have low spatial variation in image intensity. If an insufficient number of bits is used to represent intensities in such areas, the human visual system perceives the changes in intensity as happening in steps and not in a continuous manner. It is well known that one way to eliminate these contours is to use dithering of "near neighborhood" RGB8 colors. This is typically done using a fixed dithering matrix at amplitudes less than the step size of the Y intensity quantization being used on the Y values of each 4.times.4 block of pixels in a video frame.

Unfortunately, using a fixed dithering matrix can result in another undesirable artifact of "graininess" in the reproduced image. It is therefore desirable to have a method for eliminating this perceived graininess.

In order to reproduce a more natural appearing image, the dithering matrix is changed frame by frame. In this manner the same amount of dithering is accomplished with each frame, but different dithering patterns are used sequentially in time so that the tendency for perceivable graininess to occur is greatly reduced. By picking the value used for the dithering matrices artfully, the system designer can cause the time-averaged dither intensity at any and all pixel locations on a screen to be zero. This has the effect of "dissolving" any graininess artifacts observed--hence the name Temporally Dissolved Dithering (TDD).

FIG. 1 depicts one example of a digital color conversion process.

FIG. 2 shows a conventional dithering intensity vs. time graph.

FIG. 3 shows the time averaging-to-zero effect of Temporally Dissolved Dithering.

FIG. 4 shows a typical digital video transmission system suitable for employing Temporally Dissolved Dithering.

FIG. 5 depicts a typical digital video frame.

FIG. 6 depicts a 4.times.4 block in a digital video frame such as shown in FIG. 5.

In a preferred embodiment of Applicant's invention, dithering is applied to 4.times.4 blocks of pixels sequentially throughout a frame of digital video YUV9 data. FIG. 5 shows such a frame divided into 30 bands and 40 columns of such 4.times.4 blocks of pixels. The first block of such a frame is depicted in FIG. 6. In the original YUV9 format, there is a separate 8 bit Y value and a single (and same) 8 bit U value and a single (and same) 8 bit V value for each pixel P.sub.11 -P.sub.44. In other words, the Y values (which represent the intensity, i.e. "brightness") can be different for all 16 pixels in the block, but the U values are the same for all 16 pixels in the block, and the V values are the same for all 16 pixels in the block (wherein U and V taken together represent the hue of the pixels in the block). So any given block in the frame can have one of 2.sup.16 different hues and each pixel in a block can have 2.sup.8 different intensity levels, thus allowing for a total of 2.sup.24 different possible "colors" for each pixel in a block.

In order to convert from all these possible colors down to a palette of 2.sup.8 colors in an 8 bit color look up table ("CLUT8"), it is necessary to choose some combination for reduced quantization of the original Y, U, and V values. One typical choice is to pick 2.sup.5 possible Y values (i.e. 2.sup.5 different possible intensities) and 2.sup.3 possible combinations of U and V values (i.e. 2.sup.3 =8 different hues). This means that the quantization of the Y values has been changed from unit steps (i.e. 0-255 in steps of 1) to 32 steps of eight (i.e. 0-255 in steps of 8), and the hue quantization has been changed from 2.sup.16, in steps of 1, to a total of 8 increments (i.e. 8 different hues) picked by the system designer.

In practice, the reduced quantization of Y values can (and often does) result in the phenomenon called "contouring" in the resulting color image. This contouring artifact amounts to plateaus of a given color appearing on the image with distinct outlines for the boundaries of the plateaus. This give an unrealistic "cartoon" effect to the image that is very distracting to a human observer.

One known approach for removing this contouring effect caused by the reduced quantization of the Y values is to "dither" these Y values block by block with a 4.times.4 dithering matrix that "modulates" the Y values pixel by pixel so that the contours disappear. So, for example, for Y values quantized in steps of 8, in accordance with known practice, one might use the following dither pattern: ##EQU1## As is known in the art, this dither pattern would be used for each 4.times.4 block of each frame, frame after frame. This produces another artifact known as "graininess" in the resulting image, but it does eliminate the contouring problem.

Applicant has discovered a technique for eliminating both graininess and contouring! Instead of using the same dithering matrix for each successive frame, different dithering matrices are used frame by frame sequentially in time in a pattern that averages out to zero dithering intensity averaged over time for each pixel location (while actually introducing some dithering for each Y value for each pixel location in each successive frame). This requires the use of multiple dither matrices specially chosen and applied over time to achieve the above-described zeroing (or "dissolving") effect. To wit, for the dither matrix D given above, one could accomplish the desired effect by using three additional dither matrices as follows: ##EQU2##

The reader will note by careful perusal of these four matrices that the average dithering value at any particular pixel location for these four matrices taken together is zero! It is also important to note that for these four numbers (+3, +1, -1, -3), there are (4!=24) different possible arrangements (i.e. permutations) for choosing the first row of the first of four matrices picked, (3!=6) permutations for the first row of the second of four matrices picked, (2!=2) permutations for the first row of the third of four matrices picked, and only one way to pick the first row of the fourth of four matrices picked. Thus the system designer has significant flexibility in picking suitable dithering matrices to implement the invention.

The dither matrices D, D1, D2, and D3 are then applied to each block of sequential frames of data in a repeating pattern frame by frame such as: (D, D1, D2, D3, D2, D1, D, D.sub.1, D.sub.2, - - - ) so that over time (i.e., as the frames are displayed sequentially in time) the time-averaged dither value at any pixel location is zero. This results in elimination of the graininess artifact of the prior art, while at the same time removing the undesirable contour lines from the displayed image.

The effect of use of the invention is demonstrated in FIGS. 2 and 3, wherein it is shown that conventional dithering results in an overall non-zero dithering bias, whereas TDD averages out to a zero dithering bias over time.

A typical digital video transmission system suitable for implementing the instant invention is shown in FIG. 4. The components shown are all known well to those skilled in the art, and can be implemented with standard equipment available from a variety of suppliers. Analog video source 400 transmits an analog video signal to a digitizer/processor/compressor 401 wherein the method of the instant invention is used as the digitized data is being processed. It is a "simple matter of programming" for one skilled in the art to write a program (suitable for the particular processor used) that accomplishes the method of the instant invention using the following example process:

GIVEN: a dither matrix D having N distinct dither levels.

CONSTRUCTION: Construct N-1 permutations of the given dither matrix D by successively cycling through the N dither levels at each location in the matrix. Denote these dither patterns by D1, D2, - - - , D(N-1).

APPLICATION PROCEDURE: For a given video frame numbered K in the video sequence,

IF (K div N) is even {apply dither pattern D (K modulo N)}

ELSE {apply dither pattern D (N-(K modulo N))}.

Once the desired implementation of TDD is accomplished, the data can be stored in memory 402 (optional) and later sent to transmitter 403 which sends the data along digital transmission path 404 to receiver 405 which in turn sends the data through decompressor/processor/digital-to-analog converter 406 and on to memory 407 (optional) for later viewing on video display 408. The implementation of the invention takes relatively little processing time (in addition to conventional dithering) but the resultant easily-recognizable image improvement is quite significant.

Although specific examples have been given above, Applicant's invention is not at all limited to these examples, but rather is defined by the appended claims and their fair equivalents.