Secondary Quantization of Digital Image Signals

The present invention relates to the field of digital imaging, and more particularly to a method for requantizing color digital image signals.

The electronic generation of an image is often done digitally. Often this is accomplished by a digital scanning device which takes the original analog image and converts it into a series of pixels, or picture elements, each of which is comprised of a number of bits. The image which is captured digitally is then reconstructed on a display device such as a CRT or thermal printer. For monochrome devices each pixel is encoded with a single n-bit number, while color systems commonly use a triple of binary numbers. Color systems typically use three (four in some instances) spectral components (see "Color Mixture and Fundamental Metamers: Theory, Algebra, Application," by Cohen and Kappauf, A. J. Psych., Vol. 98, No. 2, pp 171-259, Summer 1985) such as inks, toners, dyes, and phosphors to represent color space. Different colors are composed of combinations of these components. The relative amounts of the components form a coordinate system for the gamut of colors which can be represented. The color components are often referred to as the color primaries. In order to capture an image digitally, the analog image must be quantized into discrete digital values represented by n-bit code words.

When quantizing a signal the quantization regions are known as bins and the edges of the quantization regions are known as decision points.

It is possible that the input device can capture an image with more bits/pixel than can be displayed on the output device. Since the image has already been quantized into discrete levels, reducing the number of bits/pixel requires a secondary quantization of the original analog image signal also referred to herein as requantization.

One method of secondary quantization is simply to ignore the low order bits of the digital data. For example a 12-bit/pixel signal can be requantized to an 8-bit/pixel signal by eliminating the four least significant bits of each code word. Because this method does not account for non-linearities of the visual perception of color, it is not visually optimal. The result from such an approach can have visually objectionable contouring and a noticeable loss of continuous-tone quality. A two-dimensional slice for the three-dimensional secondary quantization using this method is shown in FIG. 2.

Quantization and secondary quantization via a functional form is another common approach, where the function .function.(.sub.--) (such as a cube root function) models the output of the system and the range of the output is uniformly quantized. If the decision points of the quantization of the output are denoted by d.sub.i, i=0, . . . , 2.sup.n -1, then the input quantization decision points are f.sup.-1 (d.sub.i). For color systems these simple secondary quantization schemes are not optimal from a visual perspective.

The use of channel-independent non-linear functions is also an approach to the secondary quantization. It suffers since it is visually sub-optimal and functional non-linearities do not fully utilize all possible secondary quantization levels. The visual sub-optimality is due to channel dependencies which the channel independent approach ignores.

Other approaches employ image metrics, such as variance or mean value of the pixels within an image to change the sampling rate adaptively (see "System for Requantization of Coded Picture Signals," by Yoshinori Hatori and Massahide Kaneko, U.S. Pat. No. 4,677,479) or to change the quantizer adaptively (see "Adaptive Type Quantizer," by Sumio Mori, U.S. Pat. No. 4,386,366). These schemes are signal dependent, and may not result in a minimal distortion to the output.

A final method is to partition the signal space into non-rectilinear cells is referred to as vector quantization (see R. M. Gray, "Vector quantization," IEEE ASSP Magazine, Vol. 1, April, 1984, pp. 4-29). This approach is illustrated in FIG. 3. Quantization occurs by matching a signal with the cell that results in minimal distortion. Since the quantization cells are not in general rectilinear with respect to the signal axes, an exhaustive table search algorithm must also be employed. Variations to this approach that decompose the space with m-ary trees are more efficient to implement, but are sub-optimal.

It is the object of the present invention to provide look-up tables which are channel separable and that are independent of the input signal. This approach is advantageous since the secondary quantization does not require adaptive processing hardware, and the implementation can be done by a set of look-up tables, which are separable, i.e., for n channels c.sub.1 through c.sub.n, Q(c.sub.1, c.sub.2, . . . , c.sub.n)=(Q.sub.1 (c.sub.1), Q.sub.2 (c.sub.2), . . . , Q.sub.n (c.sub.n)), which simplifies the process. The secondary requantization pattern according to the present invention is represented in FIG. 4, which can be compared to FIGS. 2 and 3. It will be understood that the secondary quantization regions are 3-dimensional and are shown here as 2-dimensional for ease of description. Interchannel signal dependencies are considered in the determination of the set of look-up tables.

It is a further object of the present invention to provide a secondary quantization scheme for color imagery which minimizes the visual perception of information loss, is channel independent, and secondarily quantizes relative to the same color primaries as the original signal. The objects of the present invention are achieved by generating a set of color component requantization look-up tables by minimizing a visual cost function and employing the requantization look-up tables to requantize the color digital image. The look-up tables are generated by performing a first axial requantization of the color primaries of the color image signal, calculating a visual cost resulting from the first requantization, adjusting the first requantization based on visual cost criteria to obtain a second quantization, calculating a visual cost resulting from the second requantization, selecting either the first or second requantization having the least visual cost as a new first requantization, and repeating the steps of adjusting the requantization, calculating a visual cost and selecting the requantization having the least visual cost until a predetermined visual cost criteria is met. Two approaches are disclosed for minimizing the visual cost, one which minimized the maximum visual cost of any secondary quantization region, and the other which minimized the total visual cost of the system. The results depend upon the color primaries, however, the approach is sufficiently general to encompass a wide range of color primaries.

In the preferred modes of practicing the invention the tables are produced using either a minimum mean-square cost or a minimum-maximum cost criteria. The costs may be calculated in a uniform visual space (see Wyszecki and Stiles, Color Science: Concepts and Methods, Quantitative Data and Formulae, 2nd Ed., John Wiley & Sons, New York, 1982) after a transformation from the color space determined from the primaries of the display device.

FIG. 1 illustrates a color imaging system according to the present invention;

FIG. 2 illustrates a prior art method of secondary quantization by truncating the least significant Bit of the digital image signal;

FIG. 3 illustrates a prior art method of secondary quantization by vector quantization;

FIG. 4 illustrates the method of secondary quantization according to the present invention; and

FIG. 5 is a flow chart illustrating the method for generating the requantization look-up tables according to one embodiment of the invention .

High quality digital color imaging systems imply a large bandwidth defined by a wide dynamic range, high precision, and fine spatial and temporal resolution. This equates to a large and often infeasible number of bits. System designs are generally forced to reduce this number to comply with constraints introduced by channel, storage, and component limitations.

As an example, the initial linear quantization of 12 bits/color/pixel performed by a typical high-resolution scanner and colorimetric processing partitions a color continuum linearly with each partition being assigned an interpretation or reconstruction value that is contained with the partition. The secondary quantization repartitions the color space more coarsely (from 12 bits/pixel/color to 8 bits/pixel/color, for example) with the constraint that the new partitions must be a subset of the initial partitions. The new partitions will be termed coarsely quantized levels. The initial partitioning can in some cases be solved analytically for minimum visual lost by differential calculus. In general, these methods cannot be used for the repartitioning, because the input values are discrete. Repartitioning is over a bounded region (.alpha., .beta.) with the partitions being connected segments of the region. The points where there is a transition between successive repartitions are known as decision points, and the values which are assigned to the repartitions are reconstruction values. The reconstruction values of the secondarily quantized colors can be selected independently from the reconstruction values of the original quantized colors. The successive repartitions are numbered from o to 2m-1 for an n to m bit requantization, with the reconstruction values being a value within each repartition.

Referring to FIG. 1, a scanner 12 for scanning and digitizing color images 14 produces a 12-bit digital color image signal having 3 color primaries R, G, B. The 12-bit digital color signal is to be displayed on a 8-bit display device 16. Consequently, the 12 bit digital color image signal must be requantized to an 8-bit signal. According to the present invention, three look-up tables (LUT) 18, 20, and 22 are employed for this purpose. The look-up tables may be embodied for example in read only memories (ROM) as is well known in the art. The ROM's may contain 4096 eight-bit words, one of which is produced as an output when the LUT is addressed with a 12-bit word.

The present invention is directed to producing values for the LUT-s that result in a minimum visual cost by the display after requantizing the original digital image signal. Although the examples described below deal with a 3 color component signal wherein each component is represented by 12-bit words requantized to 8-bits, the method is equally valid for requantizing a signal having components with different numbers of bits on each component in either the input and/or output signal.

The methods used to attain the minimum for each visual cost criterion are described in detail below. In the following, a specific set of primaries, used for High-Definition-Television (HDTV), are used as examples, as well as secondarily quantizing a 12-bit/color/pixel signal to an 8-bit/color/pixel signal. The methods are equally applicable to a other color primaries and in general n-to-m level secondary quantization where n is greater than m.

The linear colorimetric coordinate system does not have an invariant metric for visual perception. Numerous studies (see Billmeyer and Saltzman, Principles of Color Technology 2nd Ed, John Wiley & Sons, New York, 1981) have been conducted to find such a uniform color coordinate system with CIE L*a*b* and CIE LUV being examples. For points that are sufficiently close, all of these systems exhibit visual uniformity. For the purpose of this application we have chosen CIE L*a*b*. The transformation is rather simple, though nonlinear and is given by ##EQU1## XYZ are CIE tristimulus values, and X.sub.n, Y.sub.n, Z.sub.n, are the tristimulus values of the "white" point of the color imaging system (e.g. the CCIR 601 primaries for HDTV at their maximum output levels). L*, a*, and b* are the color primaries of the CIE L*a*b* color coordinate system. This transformation will be denoted by L ().

In general, the color primaries to be requantized in the secondary quantization process can be converted into CIE XYZ tristimulus values by a multi-dimensional mapping. If the input signals represent linear drive signals for color primaries, then the transformation to CIE XYZ is linear. For purposes of notational simplicity the linear 10 assumption will be made and the color primaries used in the system will be referred to as R,G,B, and the linear transformation mapping the RGB color system to the XYZ color system will be denoted as A. For the case of the CCIR 601 primaries for HDTV the transformation, A, is represented by the matrix. ##EQU2##

Including this transformation prior to secondary quantization, the statistical mean square norm visual cost to be minimized for an 8-bit secondary quantization application is: ##EQU3## where r, g, b are the coordinates of the input color space and ##EQU4## {r.sub.i =the i.sup.th mid point on a continuous color component axis between the coarsely quantized decision points of the R component axis

{g.sub.j =the j.sup.th mid point on a continuous color component axis between the coarsely quantized decision points of the R component axis

{b.sub.k =the k.sup.th mid point on a continuous color component axis between the coarsely quantized decision points of the R component axis

For example, if the last 50 input 12-bit values are mapped to the last coarse level for the R color channel or axis, r.sub.255 =4046 and r.sub.256 =4096.

The visual cost criteria accounts for interchannel effects which occur because of the nonlinearity of the CIE L*a*b* transformation.

For each visual cost criteria and minimization technique the coarsely requantized decision levels are represented as three vectors of length 257 denoted by V.sub.r, V.sub.g, and V.sub.b, and the initial elements of all vectors are zero and the final element is 4096. The intermediate elements represent the indexes of the 12-bit decision points. Thus, if V.sub.r [i]=237 and V.sub.r [i+1]=248, the i.sup.th bin of the 8-bit secondary quantization spans the 12-bit decision points 237 through 248 exclusive. The three vectors have an additional constraint in that the values must be strictly monotonically increasing.

The visual cost minimization methods of the present invention operate on these vectors by changing the components of the vector, which has the effect of adjusting the coarsely requantized decision points. A change of a single component has the effect of changing the width of two bins.

The resulting vectors will determine a channel independent requantization of the fine input decision points to the coarse output decision points. The resulting vectors are easily implemented as one-dimensional look-up tables. Channel dependence is accounted for, however, in that the errors caused by the independent channel assignments are included in the determination of the overall secondary quantization visual cost defined by equation (3).

The first visual cost criteria minimization technique to be described is to minimize the total square norm visual cost defined by equation (3) and is referred to herein as the Equal-Bin-Derivative or EBD-method. Referring now to FIG. 5, the minimization process includes the following steps:

a) perform a first trial requantization on all color components of the finely quantized input decision points to form coarsely requantized output decision points that is a reasonable monotonic mapping such as uniform or a power law function,

b) compute the visual cost of equation (3) for the requantization of step a),

c) select a color component at random,

d) perform a second requantization by reassigning the finely quantized input decision points to the coarsely requantized output decision points by the following substeps:

i) compute the visual cost difference for each bin, i.e., one term in the sum of equation (3) for the color component chosen, that would occur if one input finely quantized decision point were removed,

ii) compute the visual cost difference for each bin, i.e., one term in the sum of equation (3) for the color component chosen, that would occur if one input finely quantized decision point were added,

iii) add a finely quantized decision point to the bin of substep i) that has the smallest visual cost difference,

iv) remove a finely quantized decision point from the bin in substep ii) that has the largest visual cost difference,

e) compute the visual cost of equation (3) for the reassignment of finely quantized decision points to coarsely requantized decision points of step d),

f) select the requantization that has the lesser visual cost computed in step b) or e),

g) if the variation in visual cost differences for each bin determined in substeps i) and ii) are sufficiently small, e.g. less than 10% of the average, then terminate the process, else replace the first quantization of step a) with the second requantization of step d) and return to step c).

The motivation for the EBD method is based upon equalizing the derivatives of the visual cost criteria with respect to bin widths, i.e., the number of finely quantized input decision points that are requantized to a single coarse requantized output decision point. Normally the bin widths are considered as the variables of the secondary quantization process. However, since there is a constraint that the sum of the bin widths must span the range of the input signal, the mapping into the space of bin widths is: ##EQU5##

Multivariable calculus (see Warner, Foundations of Differentiable Manifolds and Lie Groups, Scott Foresman and Company, Glenview, Ill., 1971) provides a necessary condition for a minimum of a function f that: ##EQU6## for all k=1, . . . , 255. The differential transformation which results from the change of coordinates is: ##EQU7## or in matrix form ##STR1## This implies that ##EQU8## for all k. Hence all partial derivatives must be equal, which is the basis for the EBD visual cost minimization method.

The EBD visual cost minimization method also assumes that adding or subtracting an input quantization level to an output bin will increase or decrease the derivatives respectively. For this to occur the derivatives of the visual cost criteria must be monotonically increasing with increasing bin width. For the square norm visual cost metric of equation (3) this condition is satisfied.

The EBD visual cost minimization method for secondary quantization of 12-bit/pixel/color digital image signals to 8-bit/pixel/color digital image signals for color primaries used in HDTV phosphors was implemented in a computer program written in C language. This computer program was executed on an AT&T Pixel Machine to produce a requantization table.

The table of input and output values is shown in Table 1 below. To implement these values in apparatus of the type shown in FIG. 1, the look-up tables would be loaded at the appropriate addresses with the 8-bit output values. For example in the LUT 18 for the red color channel, the 12-bit addresses from 0 to 7 would be loaded with the 8-bit output value of 0; from 7 to 14 it would be loaded with the value of 1, etc. Similarly, the LUTs 20 and 22 would be loaded with the corresponding values for the green and blue channels respectively.

Alternatively, only the final quantized decision points of Table 1 may be stored in look-up tables. The input signal value is processed by searching the table for the first entry that exceeds the input signal value and selecting the previous corresponding output value. This method conserves memory at the expense of increased computation.

An alternative visual cost minimization method is to secondarily quantize the finely quantized linear input signal to equalize the visual cost in each of the coarse secondary quantization bins. This method is referred to herein as the Equal-Visual-Cost or EVC-method. This approach is reasonable in that the visual cost is diffused in an "equitable" fashion. It is also intended that the result will minimize the maximum visual cost of any bins.

The EVC visual cost minimization method proceeds by the following steps. These steps are the same as those described with reference to FIG. 5 above with the exception that the step of performing a second secondary quantization is different.

a) perform a first trial requantizaton on all color components of the finely quantized input decision points to form coarsely requantized output decision points that is a reasonable monotomic mapping such as uniform or a power law function,

b) compute the visual cost of equation (3) for the requantization of step a),

c) select a color component at random,

d) perform a second requantization by reassigning the finely quantized input decision points to the coarsely requantized output decision points by the following substeps:

i) compute the visual cost for each bin, i.e., each term in the sum of equation (3) for the color component chosen,

ii) compute the average cost for all the bins,

iii) adjust the bin widths according to the following equation: ##EQU9## iv) sum the widths of the new bins and randomly add or subtract finely quantized decision points so that the sum of the widths equals m (e.g. 4096)

e) compute the visual cost of each bin for the second requantization of finely quantized decision points to coarsely requantized decision points of step d),

f) select the requantization that has the lesser visual cost computed in step b) or 3), and

g) if the variation in the visual cost for each bin determined in substep i) is sufficiently small, e.g. less than 10% of the average, then terminate the process, else replace the requantization of step a) with the requantization of step d) and return to step c).

The EVC visual cost minimization method for secondary quantization of 12-bit/pixel/color digital image signals to 8-bit/pixel/color digital image signals for color primaries used in HDTV phosphors was implemented in a computer program written in C language. This computer program was executed on a AT&T Pixel machine to produce the table of input and output values shown in Table 1 below. The values are implemented in apparatus as described above with respect to the EBD method.

The secondary quantization techniques of the present invention are useful in systems that generate digital color imagery which are required to have the number of bits that represent the imagery reduced. The invention has the advantage that is channel independent while accounting for distortions caused by cross channel interactions which simplifies that implementation from an n.sup.3 element table to 3 n-element tables. The methods have advantages as they require simple one-dimensional look-up table implementation and minimal arithmetic processing. The present invention has the advantage of being mathematically optimal for the criteria of minimum square norm total visual distortion or minimum maximum visual distortion.

12 scanner

14 images

16 display device

18 look-up table

20 look-up table

22 look-up table