Method of color quantization in color images

• US 6,678,406 B1
• Filed: 01/26/2000
• Issued: 01/13/2004
• Est. Priority Date: 01/26/2000
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Mojsilovic, Aleksandra, Soljanin, Emina
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/491,551
• Time in Patent Office: 1,448 Days
• Field of Search: 382/162, 382/166, 382/167, 382/274, 358/518-523, 358/539, 345/589-593, 345/597, 345/600-604
• US Class Current: 382/162
• CPC Class Codes: H04N 1/644 using a reduced set of representative colours, e.g. each representing a particular range in a colour space

Abstract

A method for assigning a color symbol to an image pixel comprises selecting a luminance value from a discrete set of quantized luminance values; selecting a chrominance value from an ordered discrete set of quantized chrominance values; and composing a color symbol from an index of the selected luminance value and an index of an ordinal position of the selected chrominance value. In particular embodiments of the invention, each discrete chrominance value is selected from a Fibonacci lattice on a constant-luminance plane in a perceptually uniform color space such as Lab or Luv.

Claims

1. A method for assigning a color symbol to at least one pixel of an image, comprising the steps of:

selecting a luminance value from a discrete set of quantized luminance values, the quantized luminance values being generated by partitioning a three-dimensional color space into planes of constant luminance;

selecting a chrominance value from an ordered discrete set of quantized chrominance values;

composing a color symbol from an index of the selected luminance value and an index of an ordinal position of the selected chrominance value, wherein the color symbol exhibits a relationship to a structure of the three-dimensional color space which permits processing of color information to be carried out, at least partially, at a symbolic level; and

storing the color symbol.

2. The method of claim 1, wherein the composing step comprises adding the chrominance index to a multiple of the luminance index.

3. The method of claim 1, wherein the joint selection of a quantized luminance value and a quantized chrominance value defines a discrete point, to be referred to as a lattice point, in said space.

4. The method of claim 3, wherein, in each constant-luminance plane, the quantized chrominance values occupy a spiral lattice.

5. The method of claim 4, wherein, in each spiral lattice:

each quantized chrominance value has an ordinal index n which is a non-negative integer, a radial coordinate r, and an angular coordinate θ

;

n and r are related by the equation r=sn^δ

, wherein s is a scale factor, and δ

is a real number; and

n and θ

are related by the equation θ

=2π

n γ

+φ

, wherein γ

is a real number, and φ

is an offset angle.

6. The method of claim 5, wherein δ

is constant over each constant-luminance plane.

7. The method of claim 5, wherein δ

varies with position on each constant-luminance plane.

8. The method of claim 5, wherein δ

equals ½

.

9. The method of claim 5, wherein γ

is approximately equal to $\frac{\sqrt{5}-1}{2}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{or}<br><br>\text{\hspace{1em}<br><br>}-\frac{\sqrt{5}-1}{2}.$

10. The method of claim 4, wherein:

the pixel has a color value associated with a point in a color space; and

the steps of selecting a quantized luminance value and a quantized chrominance value comprise searching for a lattice point that is closest to the pixel color value according to at least one distance measure.

11. The method of claim 10, wherein the step of searching for a closest lattice point comprises searching a portion of a constant-luminance plane for that lattice point having the least Euclidean distance from the pixel color value.

12. The method of claim 11, wherein said search in a constant-luminance plane is limited to at most an annular region of said plane.

13. A method for reproducing at least one pixel of a color image comprising the steps of:

receiving a color symbol for the pixel, wherein the color symbol exhibits a relationship to a structure of an underlying three-dimensional color space and defines a luminance level and an ordinality of a corresponding point in a plane of constant luminance of the three-dimensional color space;

converting the color symbol to a color value specified in a form usable by a display device, wherein color information is processed, at least partially, at a symbolic level; and

displaying the pixel such that it has the specified color value, wherein;

the converting step comprises recovering from the color symbol a scalar index designating a luminance value and a scalar index designating a chrominance value.

14. The method of claim 13, wherein the converting step further comprises deriving from the chrominance index a radial coordinate and an angular coordinate in a three-dimensional color space.

15. The method of claim 14, wherein:

the luminance index defines a plane in the color space;

the chrominance index designates an ordinal position on a spiral lattice lying in said plane; and

the radial and angular coordinates are derived by relating the chrominance index to a mathematical description of the spiral.

16. The method of claim 15, wherein:

the chrominance index n is related to the radial coordinate r through an equation of the form r=sn^δ

, wherein s is a scale factor, and δ

is a real number; and

the chrominance index n is related to the angular coordinate θ

through an equation of the form θ

=2π

n γ

+φ

, wherein γ

is a real number, and φ

is an offset angle.

17. An image-processing method comprising the steps of:

obtaining representations of color values for plural pixels of an image, computing pairwise color differences between at least some pairs of pixels, and storing the color differences, wherein;

the color value of each pixel is represented as a color symbol composed from a scalar luminance index indicative of a luminance value and a scalar chrominance index indicative of a chrominance value, wherein the color symbol exhibits a relationship to a structure of an underlying three dimensional color space which permits processing of color information to be carried out, at least partially, at a symbolic level;

each pairwise color difference is computed, in part, by combining a difference between scalar luminance values with a difference between scalar chrominance indices; and

the luminance value being selected from a discrete set of quantized luminance values, the quantized luminance values being generated by partitioning a three-dimensional color space into planes of constant luminance.

18. The method of claim 17, wherein the color symbol of each pixel comprises the sum of the chrominance index with a multiple of the luminance index.

19. The method of claim 17, wherein the difference between a pair m, n of chrominance indices is a function of the quantity Δ

_mn=S[m+n−

2{square root over (mn)} cos (2π

(m−

n)γ

)]^½

, wherein γ

is a real number, and s is a scale factor.

20. The method of claim 19, wherein the difference between a pair L_m, L_n, of luminance values is a function of the quantity Λ

_mn=L_m−

L_n or of the absolute value thereof.

21. The method of claim 20, wherein the color difference between two color values having respective chrominance indices m and n and respective luminance values L_m and L_n is computed as (Λ

_mn²+Δ

_mn²)^½

.

22. The method of claim 17, wherein the method comprises at least one operation of digitally filtering an image, and the pairwise color-difference computations are included in the digital filtering operation.

23. The method of claim 17, wherein the method comprises at least one operation of edge detection, and the pairwise color-difference computations are included in the edge-detection operation.

24. A method for assigning a color symbol to at least one pixel of an image, comprising the steps of:

selecting a luminance value from a discrete set of quantized luminance values, wherein the selection of a quantized luminance value defines a constant-luminance plane in a three-dimensional color space;

selecting a chrominance value from an ordered discrete set of quantized chrominance values, wherein the joint selection of a quantized luminance value and a quantized chrominance value defines a lattice point in the three-dimensional color space;

composing a color symbol from an index of the selected luminance value and an index of an ordinal position of the selected chrominance value; and

storing the color symbol;

 

wherein;

the quantized chrominance values occupy a spiral lattice in each constant-luminance plane, and in each spiral lattice;

each quantized chrominance value has an ordinal index n which is a non-negative integer, a radial coordinate r, and an angular coordinate θ

;

n and r are related by the equation r=sn^δ

, wherein s is a scale factor, and δ

is a real number; and

n and θ

are related by the equation θ

=2π

n γ

+φ

, wherein γ

is a real number, and φ

is an offset angle.

25. A method for reproducing at least one pixel of a color image comprising the steps of:

receiving a color symbol for the pixel;

converting the color symbol to a color value specified in a form usable by a display device; and

displaying the pixel such that it has the specified color value, wherein;

the converting step comprises recovering from the color symbol a scalar index designating a luminance value and a scalar index designating a chrominance value, and deriving from the chrominance index a radial coordinate and an angular coordinate in a three-dimensional color space;

the luminance index defines a plane in the color space;

the chrominance index designates an ordinal position on a spiral lattice lying in the plane;

the radial and angular coordinates are derived by relating the chrominance index to a mathematical description of the spiral;

the chrominance index n is related to the radial coordinate r through an equation of the form r=sn^δ

, wherein s is a scale factor, and δ

is a real number; and

the chrominance index n is related to the angular coordinate θ

through an equation of the form θ

=2π

n γ

+φ

, wherein γ

is a real number, and φ

is an offset angle.

26. An image-processing method comprising the steps of:

obtaining representations of color values for plural pixels of an image, computing pairwise color differences between at least some pairs of pixels, and storing the color differences, wherein;

the color value of each pixel is represented as a color symbol composed from a scalar luminance index indicative of a luminance value and a scalar chrominance index indicative of a chrominance value; and

each pairwise color difference is computed, in part, by combining a difference between scalar luminance values with a difference between scalar chrominance indices;

wherein the difference between a pair m, n of chrominance indices is a function of the quantity Δ

_mn=s[m+n−

2{square root over (mn)} cos(2π

(m−

n)γ

]^½

, wherein γ

is a real number, and s is a scale factor.