WO1992019076A1

WO1992019076A1 - Secondary quantization of digital image signals for minimum visual distortion

Info

Publication number: WO1992019076A1
Application number: PCT/US1992/002842
Authority: WO
Inventors: Lawrence Ray; Christopher Heckman; James Sullivan
Original assignee: Eastman Kodak Co
Current assignee: Eastman Kodak Co
Priority date: 1991-04-18
Filing date: 1992-04-07
Publication date: 1992-10-29
Anticipated expiration: 1993-10-18
Also published as: US5420705A; JPH05508281A; EP0537322A1

Abstract

The secondary quantization of a plurality of signals such as scanner signals quantized in a colorimetric coordinate system for the modified spectral response of a display device. The secondary quantization reflects the nonlinear human response to color. Two embodiments of the secondary quantization method are presented. The first method is a global cost reduction approach and the second is a method that diffuses the visual costs equally into each secondary quantization level or bin.

Description

SECONDARY QUANTIZATION OF DIGITAL IMAGE SIGNALS FOR

MINIMUM VISUAL DISTORTION

Technical Field

The present invention relates to the field of digital imaging both monochrome and color, and more particularly, to a method for secondarily quantizing previously digitally encoded signals in such as way that the secondary quantization is done by channel independent look-up tables and the visual distortion is minimized.

Background Art

The electronic generation of an image is often done digitally. Often that 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. Each of these toners has its own spectral signature over the visible frequency band. 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, or classified into discrete values. Most commonly the number of bits/pixel is the same for the input scanner as the output device.

When quantizing a signal, the edges of the quantization regions are known as decision points. The output for a signal falling within a

quantization region is known as the reconstruction point for the quantization region, i.e., all signals within the quantization bin have the same input.

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 further quantization or secondary quantization of the original analog image. However, because the image has already been encoded the secondary quantization must use the data from the scanning device. This is a second reduction of the information content contained in the original image.

One method for secondarily quantizing digital data is simply to ignore the low order bits. For example, a 12-bit/pixel signal can be secondarily quantized to an 8-bit/pixel signal by shifting all signals four bits to the right. This method does not account for non-linearities of the visual perception of color. The result from such approach is visually contouring and a noticeable loss of continuous-tone. A two-dimensional slice for the three-dimensional secondary quantization using this method is shown in Figure 2.

Quantization and secondary quantization via a functional form is another common approach, where the 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_i, i-0, ... ,2ⁿ-1, then the input quantization decision points are f^-1(d_i). For color systems these simple secondary quantization schemes are not optimal from a visual perception perspective. Moreover, visual perception of small color differences taken into account by these schemes is dependent upon the color primaries.

The use of channel-independent non-linear functions is also an approach to the secondary quantization. It suffers because it is visually suboptimal 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 Re-quantization of Coded Picture

Signals," by Yoshinori Hatori and Massahide Kaneko, US Patent No. 4,677,479) or to change the quantizer adaptively (see "Adaptive Type Quantizer", by Sumio Mori, US Patent 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 Figure 3. Quantization occurs by matching a signal with the cell that results in minimal distortion. Because 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-nary trees are more efficient to implement, but are sub-optimal.

The approach of the present invention differs from the adaptive techniques or vector quantization in that secondary quantization uses fixed look-up tables which are channel separable and is not dependent upon the input signal. This approach is advantageous since the 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., Q(c₁,

c₂,...., c_n) = (Q₁(c₁), Q₂(c₂),...,

Q_n (c_n)), which simplifies the process. This is shown in Figure 4, which can be compared to Figures 2 and 3. Interchannel signal dependencies are considered in the determination of the set of look-up tables.

Disclosure of the Invention

The objects of the present invention are achieved by designing channel independent tables from which the optimal secondary quantization of digital image signals can be made. These tables are formed by minimizing the visual perception, relative to some criterion, of all possible secondary

quantization schemes. For the secondary

quantization of an n-bit signal to an m-bit signal, the tables will have 2^m+l entries which refer to the decision points of the initial quantization decision points. Additionally, a table of

reconstruction points is also determined.

It is the object of the present invention to provide a secondary quantization scheme for both monochrome and color imagery which minimizes the visual perception of information loss, in the case of color imagery, is channel independent, and requantizes relative to the same color primaries as the original signal. Two approaches are used, one which minimizes the maximum error of any secondary quantization region, and the other which minimizes the total visual error 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-error or a minimum-maximum error criteria. The errors are calculated in a uniform visual space (see Syszecki 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. Brief Description of the Drawings

Figure 1 illustrates a typical color imaging system where the output of the scanner is processed and then secondarily quantized or image processed before being converted back to an image on a display device;

Fig. 2 illustrates one method for secondarily quantizing digital data by truncating the lower order bits. It can be seen that using this method secondarily quantized levels are equally spaced;

Fig. 3 illustrates secondary quantization of a plane of a multi-channel signal by vector quantization. The cells are not rectilinear, which makes look-up table implementations difficult; Fig. 4 illustrates the secondary

quantization of a plane of a multi-channel signal by channel independent look-up tables. The secondary quantization cell widths are made optimal with this constraint;

Fig. 5 illustrates a flow diagram for the determination of the secondary quantization levels which minimizes the total visual distortion;

Fig. 6 illustrates a flow diagram for the determination of the secondary quantization approach to minimize the maximum visual distortion in any secondarily quantized level.

Modes of Carrying Out 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 unachievable number of bits. System designs are generally forced to reduce this number to comply with constraints introduced by channel, storage, and component limitations.

The initial quantization of 12

bits/color/pixel performed by the scanner and colorimetric processing partitions a color continuum with each partition being assigned an interpretation or reconstruction value that is contained within the partition. The secondary-quantization repartitions the color space more coarsely (from 12

bits/color/pixel to 8 bits/color/pixel) with the constraints that the new partitions must be subset of the initial partitions. The initial partitioning can in some cases be solved analytically for minimum error by differential calculus. These methods cannot be used for the repartitioning, however, because the input values are discrete. Repartitioning is over a bounded region (α, β) 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 0 to 2^m-1, with the reconstruction values being a continuous value within each repartition.

The methods used to attain the minimum for each criterion is 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 requantizing a

12-bit/color/pixel signal to an 8-bit/color/pixel signal. The methods are equally applicable to other color primaries and n-to-m level requantization.

As mentioned above, the 12-bit 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 L*a*b* and 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 L*a*b*. The transformation is

rather simple, though nonlinear and is given by: where

XYZ are CIE tristimulus values, and X_n, Y_n,

Z_n, are the tristimulus values of the "white" point. This transformation will be denoted by

(xyz).

If the color primaries used in the system can be linearly transformed to the XYZ color primaries then a visual color cost can be determined for the requantization scheme. For purposes of notational simplicity 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 cases of primaries for HDTV the transformation, A, is represented by the matrix

Including this transformation prior to secondary quantization, the visual cost function to be

minimized is:

where r , g , b are the coordinates of the input color space and

The error metric accounts for interchannel effects which occur because of the nonlinearity of the L*a*b* transformation. Designing independent look-up tables for each color channel without accounting for the interaction will result in sub-optimal performance, while maintaining the same level of hardware complexity.

For each minimization technique the requantized decision levels are represented as three vectors of length 257 denoted by V_r, V_g, and

V_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 values. Thus, if V_r[i] = 237 and V_r[i+1] = 248, then the i^the bin of the 8-bit secondary quantization spans the 12-bit decision values 237 through 248 exclusive. With a given bin width an optimal reconstruction value for the bin can be computed. The three vectors have an

additional constraint in that the values must be strictly monotonically increasing.

The algorithms operate on these vectors by changing the components of the vector, which has the effect of relocating the decision and reconstruction levels. A change of a single component has the effect of changing the width of two bins, and associated reconstruction levels.

The resulting vectors from the algorithm will determine a channel independent remapping of the decision levels and the reconstruction values. This is 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 cost function.

The first algorithm minimizes the overall visual cost and is known as the EBD-method. The minimization process includes the following steps and is schematically illustrated in Figure 5:

1) Select a color axis at random to operate on.

2) Compute the cost difference for each bin that would occur if one original quantization level were removed from the secondarily quantization bin,

3) Compute the cost difference for each bin that would occur if one original secondary quantization level were added to the secondarily quantized bin, 4) Add an original quantization level to the bin where the smallest cost increase is incurred, and remove an original quantization level from the bin where the largest cost increase occurs,

5) If variation of the cost differences are

sufficiently small, terminate the process, otherwise return to step 1.

To improve the speed of the algorithm a number of pairs are selected for each selection of color axis to operate on. A 2^m-1 element vector is established for each color where the components of the vector are linked to the original

quantization levels, i.e., the i^th component in a given vector corresponds to the i^th secondary quantization level. The component for a donor level is -1 and for an acceptor level is a +1. A running total is generated and the new secondary

quantization configuration is derived by adding the old configuration to this vector. The secondarily quantized bins have new widths as well as new decision points have the decision points shift in the process.

The motivation for the algorithm is based upon equalizing the derivatives of costs with respect to bin widths. Normally the bin widths are considered as the variables of the secondary

quantization levels. However, since there is a constraint that the sum of the bin widths must be 2 12 there are only 255 independent variables. The mapping into the space of bin widths is:

By elementary multivariable calculus (see Warner, Foundations of Differentiable Manifolds and Lie Groups, Scott Foresman and Company, Glenview,

Illinois, 1971) we know that a necessary condition for a minimum of a function f is:

for all k = 1,...,255. The differential transformation which results form the change of coordinates is:

or in matrix form

This implies that

for all k. Hence all partial derivatives must be equal, which is the basis for the algorithm.

The algorithm also assumes that the change of adding or subtracting a level to a bin will increase or decrease the derivatives respectively. For this to occur the derivatives have to be

monotonically increasing the increasing bin width. Fortunately, the error function is quadratic and this condition is satisfied.

To select the acceptor and donor bins, the criteria was to order the cost difference vectors, in decreasing order for thinning bins, and

increasing order for widening bins. The average cost difference was computed as well as the standard deviation of the cost differences. Pairs of bins were selected, one from the list of thinning bins and one from the list of widening bins. The pairing continued until the magnitude of the change relative to the average was less than the standard deviation.

The second approach to secondarily quantizing the data is to equalize the cost in each of the secondary quantization bins. This method is known as the EVC (Equal Visual Cost)-method. This concept seems reasonable in that the error is diffused in an "equitable" fashion. The intent is to reduce the overall visual cost of secondary quantization. It is also intended that the result will minimize the maximum error of any bin. Since many common quantization methods essentially produce quanta of equal cost, the heuristic is grounded in practical applications.

The EVC algorithm proceeds by the following steps and is schematically shown in Figure 5:

1) Randomly select a color channel,

2) Measure the visual cost of each bin,

3) Increase the width of bins with costs below the average cost and decrease the width of bins with above average costs, 4) Adjust the width by the following formula:

5) Measure the visual cost of each bin,

6) If the variation is the visual costs across the bins is sufficiently small terminate, otherwise return to step 1).

Both of these methods were implemented into a computer program written in C. This computer program was executed on an AT&T Pixel Machine to produce requantization tables and reconstruction levels. Once derived, the three channel tables can be implemented by a general purpose computer or specialized hardware.

Advantages and Industrial Applicability

The secondary quantization techniques of the present invention is useful in systems that generate digital color imagery which need to have the number of bits needed to represent the imagery reduced. The invention has the advantage that it is channel independent while accounting for distortions caused by cross channel interactions which

simplifies the implementation from an N element table to 3 n-elements tables. The methods have advantages as they require simple look-up table implementation and minimal arithmetic processing. The present invention has the advantage of being mathematically optimal or the criteria of minimum overall distortion or minimum maximum distortion over a secondary quantization region.

Claims

WHAT IS CLAIMED IS:

1. A method of secondarily quantizing fine quantities to course quantities for a plurality of multilevel input signals characterized by the steps of:

a) performing an initial mapping of the fine quantization levels to a course quantization level wherein the course quantization levels are referred to as bins;

b) selecting an input signal at random; c) computing the visual cost difference for each bin that would occur if one original quantization level were removed from the secondary quantization bin;

d) computing the visual cost difference for each bin that would occur if one original secondary quantization level were added to the secondarily quantized bin;

e) add an original quantization level to the bin where the smallest visual cost increase is incurred, and remove an original quantization level from the bin where the largest visual cost increase occurs;

f) repeat the steps b through f unless the visual cost is less than 1%.

2. The secondary quantization method set forth in Claim 1 wherein the initial mapping is a uniform quantization.

3. The secondary quantization method set forth in Claim 1 wherein the secondary quantization uses a minimum mean-square-error criteria.

4. The secondary quantization method set forth in Claim 1 wherein the secondary quantization uses a minimum-maximum error criteria.

5. The secondary quantization method set forth in Claim 1 wherein the plurality of input signals are comprised of a 12-bit linear

colorimetric coordinate system.

6. The secondary quantization method set forth in Claim 1 wherein the plurality of input signals are characterized by a uniform color coordinate system.

7. The secondary quantization method set forth in Claim 6 wherein the uniform color

coordinate system is L*a*b*.

8. The secondary quantization method set forth in Claim 6 wherein the uniform color

coordinate system is LUV.

9. The secondary quantization method set forth in Claim 1 wherein the initial mapping is a truncation using the most significant bits.

10. A method of secondarily quantizing fine quantization to course quantization for a plurality of multilevel input signals characterized by the steps of:

a) selecting an input signal at random; b) measuring the visual cost of each bin; d) calculating an average visual cost; e) increasing the width of bins having visual costs below the average visual cost and decreasing the width of the bins having a visual cost about the average visual cost;

f) measuring the actual visual cost of each bin;

g) adjusting the width of the bins using the following:

h) repeat the steps b through h, unless the visual cost is less than 1%.

11. The secondary quantization method set forth in Claim 10 wherein the initial mapping is a uniform requantization.

12. The secondary quantization method set forth in Claim 10 wherein the plurality of input signals are comprised of a 12-bit linear

colorimetric coordinate system.

13. The secondary quantization method set forth in Claim 12 wherein the uniform color

coordinate system is L*a*b*.

14. The secondary quantization method set forth in Claim 12 wherein the uniform color

coordinate system is LUV.

15. The secondary quantization method set forth in Claim 10 wherein the initial mapping is a truncation using the most significant bits.