COLOR QUANTIZATION BASED ON DESIRED UPPER BOUND FOR RELATIVE QUANTIZATION STEP

• US 20090096809A1
• Filed: 10/11/2007
• Published: 04/16/2009
• Est. Priority Date: 10/11/2007
• Status: Active Grant

• Current Assignee: KWE International, Inc.
• Original Assignee: KWE International, Inc.
• Inventors: Bezryadin, Sergey N.
• Granted Patent: US 8,019,150 B2
• Time in Patent Office: Days
• US Class Current: 345/597
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: H04N 1/644 using a reduced set of representative colours, e.g. each representing a particular range in a colour space
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component

Abstract

A computer system (710) receives a desired upper bound δ_Smax for a relative quantization step ∥S′−S″∥/∥S′∥ to be used when quantizing any color in some range of colors. Here S′ and S″ are adjacent colors in the set of colors to be made available for the quantized image, and ∥·∥ is a norm in a 70%-orthonormal linear color coordinate system, the norm being the square root of the sum of squares of the tristimulus values. The computer system determines (510) suitable quantization steps for the brightness coordinate (B) and the chromatic coordinates (e,f) in a non-linear color coordinate system, and quantizes (520) the brightness and chromatic coordinates accordingly.

Claims

1. A computer-implemented method for quantizing a first digital image, the method comprising:

obtaining a first parameter representing a desired upper bound δ

_Smax for relative quantization steps to be used when quantizing any color in at least a first range of colors, wherein any adjacent colors S′

;

S″

available for a quantized image correspond to relative quantization steps δ

S′

=∥

S′

−

S′

∥

/∥

S′

∥ and

δ

S″

=∥

S′

−

S″

∥

/∥

S″

∥

, where for any color S, ∥

S∥

is the square root of the sum of squares of tristimulus values of the color S in a predefined 70%-orthonormal linear color coordinate system (“

linear CCS”

); and

generating a quantized digital image using the first parameter.

2. The method of claim 1 further comprising obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS, wherein the non-linear CCS also comprises one or more chromatic coordinates whose values are unchanged if the tristimulus values are multiplied by a positive number;

wherein generating the quantized digital image comprises quantizing the brightness coordinate using the first parameter and quantizing said one or more chromatic coordinates using the first parameter.

3. The method of claim 2 further comprising:

using the first parameter to generate (i) a brightness parameter specifying a desired maximum bound for relative quantization steps δ

B for the brightness coordinate in at least a range of values of the brightness coordinate, and (ii) one or more chromatic parameters specifying one or more desired maximum bounds for quantization steps d for the one or more chromatic coordinates in at least one or more ranges of values of the chromatic coordinates;

wherein the brightness coordinate is quantized using the brightness parameter and said one or more chromatic coordinates are quantized using the one or more chromatic parameters.

4. The method of claim 3 wherein the brightness parameter and the one or more chromatic parameters are determined from the first parameter to satisfy an equation:

δ

_Smax²=c₁−

d²+c₂·

δ

B²

where c₁, c₂ are predefined constants independent of the first parameter.

5. The method of claim 1 further comprising obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS;

wherein generating the quantized digital image comprises quantizing the brightness coordinate, wherein in at least a range of values of the brightness coordinate the quantizing of the brightness coordinate comprises logarithmic quantizing in which a quantized brightness coordinate is a predefined first rounded or unrounded linear function, or its rounded value, of a logarithm to a predefined base of a predefined second rounded or unrounded linear function of the brightness, the first and/or second linear functions and/or the base being dependent on the first parameter.

6. The method of claim 1 wherein the linear CCS is 90%-orthonormal.

7. A computer system programmed to perform the method of claim 1.

8. The computer system of claim 7 wherein the method further comprises obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS, wherein the non-linear CCS also comprises one or more chromatic coordinates whose values are unchanged if the tristimulus values are multiplied by a positive number;

wherein generating the quantized digital image comprises quantizing the brightness coordinate using the first parameter and quantizing said one or more chromatic coordinates using the first parameter.

9. The computer system of claim 8 wherein the method further comprises:

using the first parameter to generate (i) a brightness parameter specifying a desired maximum bound for relative quantization steps δ

B for the brightness coordinate in at least a range of values of the brightness coordinate, and (ii) one or more chromatic parameters specifying one or more desired maximum bounds for quantization steps d for the one or more chromatic coordinates in at least one or more ranges of values of the chromatic coordinates;

wherein the brightness coordinate is quantized using the brightness parameter and said one or more chromatic coordinates are quantized using the one or more chromatic parameters.

10. The computer system of claim 9 wherein the brightness parameter and the one or more chromatic parameters are determined from the first parameter to satisfy an equation:

δ

_Smax²=c₁·

d²+c₂·

δ

B²

where c₁, c₂ are predefined constants independent of the first parameter.

11. The computer system of claim 9 wherein the brightness coordinate is quantized logarithmically in a first brightness range B>

B_L wherein B is the brightness and B_L is a predefined positive number, and the brightness coordinate is quantized linearly in the range B<

B_L.

12. The computer system of claim 8 wherein the method further comprises obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS;

wherein generating the quantized digital image comprises quantizing the brightness coordinate, wherein in at least a range of values of the brightness coordinate the quantizing of the brightness coordinate comprises logarithmic quantizing in which a quantized brightness coordinate is a predefined first rounded or unrounded linear function, or its rounded value, of a logarithm to a predefined base of a predefined second rounded or unrounded linear function of the brightness, the first and/or second linear functions and/or the base being dependent on the first parameter.

13. Computer-readable manufacture comprising a computer-readable program for performing the method of claim 1.

14. The computer-readable manufacture of claim 13 wherein the method further comprises obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS, wherein the non-linear CCS also comprises one or more chromatic coordinates whose values are unchanged if the tristimulus values are multiplied by a positive number;

wherein generating the quantized digital image comprises quantizing the brightness coordinate using the first parameter and quantizing said one or more chromatic coordinates using the first parameter.

15. The computer-readable manufacture of claim 14 wherein the method further comprises:

using the first parameter to generate (i) a brightness parameter specifying a desired maximum bound for relative quantization steps δ

B for the brightness coordinate in at least a range of values of the brightness coordinate, and (ii) one or more chromatic parameters specifying one or more desired maximum bounds for quantization steps d for the one or more chromatic coordinates in at least one or more ranges of values of the chromatic coordinates;

wherein the brightness coordinate is quantized using the brightness parameter and said one or more chromatic coordinates are quantized using the one or more chromatic parameters.

16. The computer-readable manufacture of claim 15 wherein the brightness parameter and the one or more chromatic parameters are determined from the First parameter to satisfy an equation:

δ

_Smax²=c₁·

d²+c₂·

δ

B²

where c₁, c₂ are predefined constants independent of the first parameter.

17. The computer-readable manufacture of claim 15 wherein the brightness coordinate is quantized logarithmically in a first brightness range B>

B_L wherein B is the brightness and B_L is a predefined positive number, and the brightness coordinate is quantized linearly in the range B<

B_L.

18. The computer-readable manufacture of claim 14 wherein the method Further comprises obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS;

wherein generating the quantized digital image comprises quantizing the brightness coordinate, wherein in at least a range of values of the brightness coordinate the quantizing of the brightness coordinate comprises logarithmic quantizing in which a quantized brightness coordinate is a predefined first rounded or unrounded linear function, or its rounded value, of a logarithm to a predefined base of a predefined second rounded or unrounded linear function of the brightness, the first and/or second linear functions and/or the base being dependent on the first parameter.

19. A network transmission method comprising transmitting, over a network, a computer program which is operable to cause a computer system to perform the method of claim 1.

20. The method of claim 19 wherein the method further comprises Obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS, wherein the non-linear CCS also comprises one or more chromatic coordinates whose values are unchanged if the tristimulus values are multiplied by a positive number;

wherein generating the quantized digital image comprises quantizing the brightness coordinate using the first parameter and quantizing said one or more chromatic coordinates using the first parameter.

21. The method of claim 20 wherein the method further comprises:

using the first parameter to generate (i) a brightness parameter specifying a desired maximum bound for relative quantization steps δ

B for the brightness coordinate in at least a range of values of the brightness coordinate, and (ii) one or more chromatic parameters specifying one or more desired maximum bounds for quantization steps d for the one or more chromatic coordinates in at least one or more ranges of values of the chromatic coordinates;

wherein the brightness coordinate is quantized using the brightness parameter and said one or more chromatic coordinates are quantized using the one or more chromatic parameters.

22. The method of claim 21 wherein the brightness parameter and the one or more chromatic parameters are determined from the first parameter to satisfy an equation:

δ

_Smax²=c₁d²+c₂·

δ

B²

where c₁, c₂ are predefined constants independent of the first parameter.

23. The method of claim 21 wherein the brightness coordinate is quantized logarithmically in a first brightness range B>

B_L wherein B is the brightness and B_L is a predefined positive number, and the brightness coordinate is quantized linearly in the range B<

B_L.

24. The method of claim 20 wherein the method further comprises Obtaining color data representing each color of the first digital image in a non-linear color coordinate system (“

non-linear CCS”

), wherein the non-linear CCS includes a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS;

wherein generating the quantized digital image comprises quantizing the brightness coordinate, wherein in at least a range of values of the brightness coordinate the quantizing of the brightness coordinate comprises logarithmic quantizing in which a quantized brightness coordinate is a predefined first rounded or unrounded linear function, or its rounded value, of a logarithm to a predefined base of a predefined second rounded or unrounded linear function of the brightness, the first and/or second linear functions and/or the base being dependent on the first parameter.

25. The method of claim 1 wherein the non-linear CCS comprises a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS, wherein the non-linear CCS also comprises two chromatic coordinates each of which is equal to a ratio of a respective one of the tristimulus values to the brightness coordinate;

wherein generating the quantized digital image comprises quantizing each of the chromatic coordinates with a step 1/k_eƒ

where k_eƒ

is a value dependent on the first parameter; and

wherein generating the quantized digital image also comprises quantizing the brightness coordinate, wherein in at least a range of values of the brightness coordinate the quantizing of the brightness coordinate comprises logarithmic quantizing in which a predefined first linear function of a natural logarithm of a predefined second linear function of the brightness coordinate is quantized with a step 1, the first linear function multiplying said natural logarithm by a value k_B dependent on the first parameter;

wherein k_eƒ

is about 3·

K_B, or k_eƒ

is equal to the smallest power of 2 which is greater than or equal to about 3·

k_B.

26. The computer system of claim 10 wherein c₁:

c₂=9;

1 and c₁d;

c₂η

B=1;

1.

27. The computer-readable manufacture of claim 13 wherein the non-linear CCS comprises a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS, wherein the non-linear CCS also comprises two chromatic coordinates each of which is equal to a ratio of a respective one of the tristimulus values to the brightness coordinate;

wherein generating the quantized digital image comprises quantizing each of the chromatic coordinates times k_eƒ

with a step 1, where k_eƒ

is a value dependent on the first parameter; and

wherein generating the quantized digital image also comprises quantizing the brightness coordinate, wherein in at least a range of values of the brightness coordinate the quantizing of the brightness coordinate comprises logarithmic quantizing in which a predefined first linear function of a natural logarithm of a predefined second linear function of the brightness coordinate is quantized with a step 1, the first linear function multiplying said natural logarithm by a value k_B dependent on the first parameter;

wherein k_eƒ

is about 3·

k_B, or k_eƒ

is equal to the smallest power of 2 which is greater than or equal to about 3·

k_B.

28. The method of claim 19 wherein the non-linear CCS comprises a brightness coordinate representing the square root of the sum of squares of the tristimulus values of the linear CCS, wherein the non-linear CCS also comprises two chromatic coordinates each of which is equal to a ratio of a respective one of the tristimulus values to the brightness coordinate;

wherein generating the quantized digital image comprises quantizing each of the chromatic coordinates times k_eƒ

with a step 1, where k_eƒ

is a value dependent on the first parameter; and

wherein generating the quantized digital image also comprises quantizing the brightness coordinate, wherein in at least a range of values of the brightness coordinate the quantizing of the brightness coordinate comprises logarithmic quantizing in which a predefined first linear function of a natural logarithm of a predefined second linear function of the brightness coordinate is quantized with a step 1, the first linear function multiplying said natural logarithm by a value k_B dependent on the first parameter;

wherein k_eƒ

is about 3·

k_B, or k_eƒ

is equal to the smallest power of 2 which is greater than or equal to about 3·

k_B.

29. A computer-implemented method for image processing, the method comprising converting a digital image between a first digital representation of the image and a second digital representation of the image, wherein the image comprises a plurality of image portions, wherein an image at each said image portion has color coordinates S₁, S₂, S₃ in a first color coordinate system (CCS), wherein

S₁=√

{square root over (T₁²+T₂²+T₃²)}

S₂=T₂/S₁

T₁, T₂, T₃ are color coordinates in a predefined 70%-orthonormal linear CCS;

wherein at least for each said image portion whose color coordinate S₁ is in a predefined range, the first digital representation comprises color coordinates s₁, s₂, s₃ such that;

s₁=k_B·

(1n(α

S₁)+β

) rounded to an integer, where α and

β

are predefined constants,

S₂=k_eƒ

·

S₂/S₁ rounded to an integer,

S₃=k_eƒ

·

S₃/S₁ rounded to an integer,

wherein k_eƒ

is about 3·

k_B, or k_eƒ

is equal to the smallest power of 2 which is greater than or equal to about 3·

k_B.

30. A computer system adapted to perform the method of claim 29.

31. A network transmission method comprising transmitting, over a network, a computer program which is operable to cause a computer system to perform the method of claim 29.

32. A computer-readable manufacture comprising computer-readable encoding of digital data representing an image at a plurality of image portions, wherein the image comprises a plurality of image portions, wherein an image at each said image portion has color coordinates S₁, S₂, S₃ in a first color coordinate system (CCS), wherein

S₁=√

{square root over (T₁²+T₂²+T₃²)}

S₂=T₂/S₁

S₃=T₃/S₁

T₁, T₂, T₃ are color coordinates in a predefined 70%-orthonormal linear CCS;

wherein at least for each said image portion whose color coordinate S₁ is in a predefined range, the first digital representation comprises color coordinates s₁, s₂, S₃ such that;

s₁=k_B·

(1n(α

S₁)+β

) rounded to an integer, where α and

β

are predefined constants,

S₂=k_eƒ

·

S₂/S₁ rounded to an integer,

S₃=k_eƒ

·

S₃/S₁ rounded to an integer,

wherein k_eƒ

is about 3·

k_B, or k_eƒ

is equal to the smallest power of 2 which is greater than or equal to about 3·

k_B.

33. A computer system adapted to perform the method of claim 32.

34. A network transmission method comprising transmitting, over a network, a computer program which is operable to cause a computer system to perform the method of claim 32.