WO2005084033A1

WO2005084033A1 - Error diffusion applied to digital video sample size reduction

Info

Publication number: WO2005084033A1
Application number: PCT/US2004/022785
Authority: WO
Inventors: Michael Wilson Bruns; James Torpin Whittlesey
Original assignee: Thomson Licensing SAS
Current assignee: Thomson Licensing SAS
Priority date: 2004-02-04
Filing date: 2004-07-15
Publication date: 2005-09-09
Anticipated expiration: 2006-08-04

Abstract

There is provided an error diffusing method for processing a digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, wherein m > n. The method includes the step of distributing a quantization error calculated with respect to at least one previously processed pixel sample to only at least one subsequently processed pixel sample, the quantization error corresponding to at least one error diffusion function.

Description

ERROR DIFFUSION APPLIED TO DIGITAL VIDEO SAMPLE SIZE REDUCTION

FIELD OF THE INVENTION The present invention generally relates to digital video and, more particularly, to an error diffusion method and apparatus for digital video sample size reduction that prevents visual artifacts.

BACKGROUND OF THE INVENTION In digital video processing or transmission, it is common for a video signal to be conveyed between functional blocks with different inherent sample sizes. For example, a signal may be carried by a serial digital interface (e.g. SMPTE 292M) with 10-bit sample size to be compressed by an MPEG-2 encoder with an 8-bit sample size. The default method to reduce the sample size at the interface to the encoder is to truncate the least significant bits of each sample. The difference between the value of the original sample and the truncated sample is a form of quantization error. For some images, especially shallow ramps of color or brightness, truncation can result in an objectionable contouring or banding visual artifact. For an 8-bit sample in YCbCr colorspace, artifacts are most likely to be seen in computer-generated images. They can sometimes be seen in natural images containing blue sky, underwater sea green, or other broad washes of color or brightness. Color banding or contouring artifacts are well known in the field of digital video and have been addressed in various ways. Contouring that is introduced specifically in the course of reducing sample size is a more specific problem that has been dealt with in several ways. All of the techniques, including error diffusion, can be categorized as exchanging spatial resolution for dynamic range. The resulting field of sample values is not locally constant as with the truncation technique, but includes a modulation such that the reduced-size sample values averaged over the local region in the image are approximately equal to the original sample values before the reduction of sample size. Conventional approaches directed to correcting contouring in digital images include random dither, ordered dither, and probabilistic dither. A random dither is added to the image before truncating the least significant bits of each sample. This makes fine detail harder or impossible to see (reduced spatial resolution) but it does cause the local average color after sample size reduction to be the same as in the original image which is the desired result. The disadvantages of this approach are that it adds random noise to the image and it requires a random number generator in its implementation. An ordered dither is a repeating two-dimensional pattern of dither values applied to the image before truncating the least significant bits of each sample. This technique has the disadvantage of creating bands of a common dither pattern that may be as objectionable as the color bands that the technique is working to prevent. Probabilistic dither, covered by U.S. Patent No. 5,404,427 (hereinafter the "'427 Patent"), entitled "Video Signal Processing with Added Probabilistic Dither", issued on April 4, 1995, does not modify the original image before sample size reduction but rather increments the brightness and color values of certain pixels according to a random function with probability equal to the fraction that is truncated from the original sample. This technique is effective and preferable to the ordered and random dither techniques, but is complex and expensive to implement. A need for a random function is disclosed in the '427 Patent to prevent dot patterning from appearing in the place of contouring. Accordingly, it would be desirable and highly advantageous to have an error diffusion method and apparatus for digital video with reduced sample size that overcomes the above-identified problems of the prior art.

SUMMARY OF THE INVENTION The problems stated above, as well as other related problems of the prior art, are solved by the present invention, which is directed to an error diffusion method and apparatus for digital video with reduced sample size. The error diffusion technique of the present invention is adapted to digital video to compensate for the loss in dynamic range when the sample size is reduced. The resulting images are much less likely to exhibit banding or contouring artifacts compared to, e.g., a simple truncation technique. Advantageously, the present invention is less complex and less expensive to implement than for example, the Probabilistic Dither approach described above, and does not require a random number generator as does the Probabilistic Dither approach. According to an aspect of the present invention, there is provided an error diffusing method for processing a digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, wherein m > n. The method includes the step of distributing a quantization error calculated with respect to at least one previously processed pixel sample to only at least one subsequently processed pixel sample, the quantization error corresponding to at least one error diffusion function. According to another aspect of the present invention, there is provided an error diffusing apparatus for processing a digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, wherein m > n. The apparatus includes means for accumulating quantization errors, the quantization errors corresponding to at least one error diffusion function. The apparatus further includes means for distributing the quantization errors such that a quantization error calculated with respect to at least one previously processed pixel sample is distributed to only at least one subsequently processed pixel sample. According to yet another aspect of the present invention, there is provided an error diffusing method for processing a digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, where m > n. The method includes the step of performing error diffusion with respect to the digital video using a set of coefficient values for distributing quantization error among pixel samples of the digital video that have yet to be processed, the set containing exactly one coefficient value equal to unity and the rest of the coefficient values equal to zero. These and other aspects, features and advantages of the present invention will become apparent from the following detailed description of preferred embodiments, which is to be read in connection with the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a diagram illustrating a partially processed image to which the present invention may be applied, according to an illustrative embodiment of the present invention; FIG. 2 is a diagram illustrating diffusion coefficient values relating the to the

Spatial Grayscale Algorithm; FIG. 3 is a diagram illustrating simplified error diffusion coefficient values for digital video, according to an illustrative embodiment of the present invention; FIG. 4 is a block diagram illustrating an error diffusion apparatus for digital video, according to an illustrative embodiment of the present invention; FIG. 5 is a flow diagram illustrating an error diffusion method for digital video, according to an illustrative embodiment of the present invention; FIG. 6 is a diagram illustrating an 11-bit data set with 8 bits over the decimal and 3 under, to which the present invention may be applied, according to an illustrative embodiment of the present invention; FIG. 7 is a diagram illustrating a modified version of the sample data set from FIG. 6 reduced to 8 bits with error diffusion, according to an illustrative embodiment of the present invention; FIG. 8A is a diagram illustrating a shallow ramp reduced to 6 bit RGB samples with no error diffusion in which banding artifacts are visible; and FIG. 8B is a diagram illustrating a modified version of the shallow ramp reduced to 6 bit RGB samples with error diffusion to eliminate banding artifacts according to an illustrative embodiment of the present invention. DETAILED DESCRIPTION OF THE INVENTION The present invention is directed to an error diffusion method and apparatus for digital video with reduced sample size. It is to be understood that the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or a combination thereof. Preferably, the present invention is implemented as a combination of hardware and software. Moreover, the software is preferably implemented as an application program tangibly embodied on a program storage device. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units (CPU), a random access memory (RAM), and input/output (I/O) interface(s). The computer platform also includes an operating system and microinstruction code. The various processes and functions described herein may either be part of the microinstruction code or part of the application program (or a combination thereof) that is executed via the operating system. In addition, various other peripheral devices may be connected to the computer platform such as an additional data storage device and a printing device. Alternatively, the present invention may be implemented in hardware circuits within an application specific integrated circuit (ASIC) or a programmable logic device (PLD) such as a field programmable gate array (FPGA). It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying Figures are preferably implemented in software, the actual connections between the system components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention. The invention is an extension of the technique described by Floyd et al., in

"An Adaptive Algorithm for Spatial Greyscale" (hereinafter the "Spatial Grayscale Algorithm"), Proceeding of the Society for Information Display, vol. 17/2, pp. 75-77, second quarter 1976. A brief description will now be given of the basic algorithm described in the Spatial Greyscale Algorithm referred to above, followed by the enhancements for digital video provided by the present invention. Error Diffusion converts a raster-based, digital image or sequence of images from an original pixel sample size of m bits to a target sample size of n bits, where m > n. The method prevents objectionable banding or contouring artifacts that could result from a simple truncation of the {m - n) least significant bits. It is understood that color images are comprised of three or more components, any of which may be expressed in any of a number of color spaces such as, for example, YCbCr, CYMK, RGB, and so forth. When an image contains multiple color components, error diffusion is applied separately and independently to each component. It is also understood that some color spaces such as YCbCr support sub-sampled chroma, and that the error diffusion technique and the present invention are also applicable in this case. In the original description of the Spatial Greyscale Algorithm, the original pixel sample size is not mentioned and is implied to be infinite, i.e., an analog value with infinite dynamic range. However, the error diffusion technique is inherently numerical, so it is reasonable to assume that m has some finite, practical value. The target sample size in the original description is 1 bit as the algorithm is originally proposed as a greyscale algorithm for bi-level devices, such as a printed page. The Spatial Greyscale algorithm is disclosed as being applicable to devices that allow several brightness levels at each pixel instead of only two. Error diffusion operates on raster-based images, which means that they are expressed in terms of a two-dimensional array of color and brightness values arranged on a uniform grid. Processing proceeds along one line of samples from first to last, then proceeds to the next line, and so on until the entire image is processed. For example, consider the partially processed image in FIG. 1. FIG. 1 is a diagram illustrating a partially processing image 100 to which the present invention may be applied, according to an illustrative embodiment of the present invention. In this example, processing proceeds from left to right, top to bottom. Pixels marked by "Λ" are already processed, pixels marked by "P' are currently processed, and pixels marked by "(7 have not yet been processed. Processing includes dividing the original m-bit sample(s) at P by 2^m'n, and keeping the integer part of the quotient as the final value(s) for P. 2^m'n'1 is added to P before the division to give rounding rather than truncation.

R_ = int[(R_m + 2^m-^π-¹ )/^2W"" J

The quantization error δ from the division is then expressed in terms of the original sample value and may be positive or negative. The value of the quantization error δ is expressed with m bits but its magnitude is less than 2^m'n. δ = P_m - (P_n x 2^m-" )

Before processing the next pixel, the quantization error δ from P is then distributed about the neighboring pixels ahead on the same line and on the next line. In the Spatial Greyscale Algorithm, a particular distribution is given as shown in FIG. 2. FIG. 2 is a diagram illustrating diffusion coefficient values 200 relating the to the Spatial Grayscale Algorithm. According to the authors of the Spatial Greyscale Algorithm, these values were chosen for n =1 by trial and error to minimize texturing of the resulting image. Note that practical implementation of these coefficients requires the image frame store to support m + 4 bits per sample. Error diffusion is clearly not limited to this particular set of coefficients, and other sets have been proposed for various special cases of m and n. In accordance with the present invention, it has been found that a particularly simple coefficient set, e.g., such as that shown in FIG. 3, is particularly effective for digital video with m = 10 and n = 8. FIG. 3 is a diagram illustrating simplified error diffusion coefficient values 300 for digital video, according to an illustrative embodiment of the present invention. The coefficient set 300 of FIG. 3 has the advantages of not requiring the addressing of pixels on the next line, which can complicate practical implementations, and the resulting pixel values can be stored within the original sample size m of the source image. The disadvantage of the simplified coefficient set 300 is a greater possibility of objectionable textures and patterns to be visible in the processed image, similar to those problems observed with the random or ordered dither technique. However, this is an issue with bi-level target images, and is typically not observed at all in digital video images with n = 8. The simplified coefficient set 300 of FIG. 3 is directed to one part of the present invention. Another part of the present invention deals with the problem of a regular pattern of sample values appearing in the processed image when the source image is a noise-free, shallow ramp of brightness or color. Computer generated images tend to have this characteristic. Avoiding the regular pattern of sample values is the reason for adopting a random function in the probabilistic dither algorithm of the '427

Patent described above. The following describes how the error diffusion algorithm may be extended to avoid patterns of sample values without requiring the use of a random function, in accordance with various embodiments of the present invention. The error diffusion functions, using the simplified coefficient set 300 of the present invention shown in FIG. 3 can be expressed as an accumulator that accumulates the quantization error of the division operation, as follows:

A = A_prev + P_m - P_n x2 m-n

A and A_prθV are recognized as the quantization error from the current pixel at P and that of the previous pixel, respectively. The term in parentheses includes the distribution of the previous quantization error into the current pixel. The term in square braces is the division operation. A is also recognized in this equation as performing an accumulator function.

For example, when the quantization error at each pixel is small and constant, A becomes progressively larger until it is big enough to shift the value of P_n. The accumulator value then experiences a discontinuous jump to the other end of its range and then builds again. The result of the error diffusion algorithm is the modulation of the pixel values in the processed image. The exact position of a particular modulation is not important. In fact, it is desired that the modulation be irregular from line to line to avoid regular patterns of sample values. The method of the present invention avoids a regular pattern of modulation by not clearing the accumulator value from one raster line to the next. This means that each line of error diffusion begins with a quasi-random seed value that resulted from the accumulation of processing of the previous line. The seed value has nothing to do with the image samples on the new line (i.e., the line currently being processing), and the value of the accumulator at any particular point is not significant. What is of significance is the modulation of pixel values that emerges from the error diffusion processing as it progresses down the line. If the accumulator is not cleared from one picture to the next in a sequence of pictures, a temporal modulation results that can further prevent the visibility of any regular pattern of pixel values. FIG. 4 is a block diagram illustrating an error diffusion apparatus 400 for digital video, according to an illustrative embodiment of the present invention. FIG. 5 is a flow diagram illustrating an error diffusion method for digital video, according to an illustrative embodiment of the present invention. An image such as, e.g., a frame or field image 401 , is input to a raster scanner 410. The output of the raster scanner 410 (raster-based digital image 402) is input to a color component demultiplexor 420. The output of the demultiplexer 420 includes three or more color components such as, but not limited to, R, G, B, or Y, CB, CR, or Y, U, V, and so forth. The output of the demultiplexor 420 includes serialized sample streams 403, which are applied to an error diffusion module 430. The method of FIG. 5 is performed by the error diffusion module 430. The output of the error diffusion module 430 is applied to a color component multiplexor 440. The output of the color component multiplexor is applied to a raster generator 450 which, in turn, outputs a frame or field image 404 corresponding to image 401 such that image 404 exhibits less or no banding or contouring artifacts compared to, for example, a simple truncation technique. A description will now be given of the steps performed by the error diffusion module 430 corresponding to FIG. 5 with respect to a given digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, where m > n. Initially, an accumulator value A, corresponding to the original pixel sample size of m bits, is set to zero (0) (step 505). The accumulator value A may be considered as the cumulative quantization error for previously processed samples to be applied to the pixel sample that is currently being processed. The next pixel sample Pm to be processed (which is the currently processed pixel sample at step 515), having the original pixel sample size of m bits, is retrieved (step 510). For a pixel sample other than the first pixel sample to be processed, an accumulator value A_prθV for the previously processed pixel is added to that pixel sample (e.g., the next sample Pm retrieved at step 510) (step 515), and a rounding operation is performed on the sum (step 520). For example, 2^{m~π~1) is added to the sum of Pm and the accumulator value A_prβvto effect rounding. A truncation operation is then performed on the resultant value (i.e., the sum of Pm and A_prev and 2^(m"π",)) from step 520 (step 525). For example, the resultant value is divided by 2^(m"π)to effect truncation. The integer of the resultant value of step 525 is calculated to obtain a sample pixel Pn having the target pixel sample size of n bits (step 527). The sample Pn is sent to the next process (e.g., color component multiplexing) (step 530). The error of the pixel sample Pm is added to the accumulator value A (step 535). The error is as follows: (Pm + A_prθV) - (Pn * 2^{m~n)). A restriction is imposed on the error diffusion method such that the accumulator value A is not reset on the line or frame boundaries (step 540). The method then returns to step 510 to retrieve the next pixel sample Pm for processing.

Experimental Results As an example, the image block depicting a shallow ramp with fractional pixel values (m = 8 + 3 bits) in FIG. 6 is reduced to the sample set without fractional values (n = 8 bits) in FIG. 7. In the processed image, the modulation of the pixel values is apparent. This is the desired result that greatly reduces or eliminates the visibility of banding artifacts. FIG. 6 is a diagram illustrating an 11 -bit data set 600 with 8 bits over the decimal and 3 under, to which the present invention may be applied, according to an illustrative embodiment of the present invention. FIG. 7 is a diagram illustrating a modified version 700 of the sample data set 600 from FIG. 6 reduced to 8 bits with error diffusion, according to an illustrative embodiment of the present invention. Error diffusion as applied to digital video with m = 10 and n = 8 was evaluated in a very critical viewing environment. A TEXAS INSTRUMENTS DLP cinema projector was used to display the image onto a 24-foot wide screen. The projector was specially modified to not perform internally any image resizing and to display the center 1280 x 1024 pixels of the image. Error diffusion was shown to eliminate banding and contouring artifacts in several different shallow ramps of brightness and color. A quality CRT monitor is also a suitable device for evaluating banding artifacts because high resolution is not required. A simple demonstration of error diffusion is also available on the printed page. In FIGs. 8A and 8B, m = 16 and n = 6. FIG. 8A is a diagram illustrating a shallow ramp 800 with 6 bit RGB samples with no error diffusion, and FIG. 8B is a diagram illustrating a modified version 850 of the shallow ramp 800 with 6 bit RGB samples with error diffusion according to an illustrative embodiment of the present invention. Although the illustrative embodiments have been described herein with reference to the accompanying drawings, it is to be understood that the present invention is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one of ordinary skill in the related art without departing from the scope or spirit of the invention. All such changes and modifications are intended to be included within the scope of the invention as defined by the appended claims.

Claims

1. An error diffusing method for processing a digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, wherein m > n, the method comprising the step of: distributing a quantization error calculated with respect to at least one previously processed pixel sample to only at least one subsequently processed pixel sample, the quantization error corresponding to at least one error diffusion function.

2. The method of claim 1 , wherein the quantization error calculated with respect to the at least one previously processed pixel sample is restricted from being distributed to a pixel sample processed prior to the previously processed pixel sample.

3. The method of claim 1 , further comprising the step of reducing a pixel sample size of a pixel sample corresponding to the digital video from the original pixel sample size of m bits to the target pixel sample size of n bits, as follows:

A = P_m - P_n x 2" wherein P_π and P_m respectively represent a currently processed pixel having a target sample size of n bits and an original pixel sample size of m bits, and A and

^A _prev respectively represent the quantization error from the currently processed pixel

and a previously processed pixel.

4. The method of claim 3, wherein P„ has a range of values from a first end to a second end, the range of values increasing from the first end to the second end, and wherein A becomes progressively larger up to a point capable of shifting a value of P_n and then of performing a discontinuous jump to the second end and then continuing to build up, when the quantization error at each pixel sample is constant and smaller than a predefined threshold.

5. The method of claim 1 , further comprising the step of modulating pixel sample values to obtain irregular patterns of pixel sample values having the target pixel sample size, without generating random numbers.

6. The method of claim 1 , further comprising the step of maintaining a previous value of the quantization error on line boundaries corresponding to the digital video.

7. The method of claim 1 , further comprising the step of maintaining a previous value of the quantization error on frame boundaries corresponding to the digital video.

8. The method of claim 1 , wherein the at least one subsequently processed pixel sample to which the quantization error is distributed consists of only one subsequently processed pixel sample.

9. An error diffusing apparatus for processing a digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, wherein m > n, the apparatus comprising: means for accumulating quantization errors, the quantization errors corresponding to at least one error diffusion function; and means for distributing the quantization errors such that a quantization error calculated with respect to at least one previously processed pixel sample is distributed to only at least one subsequently processed pixel sample.

10. The apparatus of claim 9, wherein the quantization error calculated with respect to the at least one previously processed pixel sample is restricted from being distributed to a pixel sample processed prior to the previously processed pixel sample.

11. The apparatus of claim 9, further comprising means for reducing a pixel sample size of a pixel sample corresponding to the digital video from the original pixel sample size of m bits to the target pixel sample size of n bits, as follows:

A = P_m - P 2^m-"

wherein P_n and P_m respectively represent a currently processed pixel having a target sample size of n bits and an original pixel sample size of m bits, and A and

A_preV respectively represent the quantization error from the currently processed pixel

and a previously processed pixel.

12. The apparatus of claim 11 , wherein P_n has a range of values from a first end to a second end, the range of values increasing from the first end to the second end, and wherein A becomes progressively larger up to a point capable of shifting a value of P_π and then of performing a discontinuous jump to the second end and then continuing to build up, when the quantization error at each pixel sample is constant and smaller than a predefined threshold.

13. The apparatus of claim 9, wherein said means for distributing maintains a previous value of the quantization error on line boundaries corresponding to the digital video.

14. The apparatus of claim 9, wherein said means for distributing maintains a previous value of the quantization error on frame boundaries corresponding to the digital video.

15. The apparatus of claim 9, wherein the at least one subsequently processed pixel sample to which the quantization error is distributed consists of only one subsequently processed pixel sample.

16. An error diffusing method for processing a digital video having an original pixel sample size of m bits and a target pixel sample size of n bits, where m > n, the method comprising the step of: performing error diffusion with respect to the digital video using a set of coefficient values for distributing quantization error among pixel samples of the digital video that have yet to be processed, the set containing exactly one coefficient value equal to unity and the rest of the coefficient values equal to zero.