Method of color quantization in color images
First Claim
Patent Images
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
26 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
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 ½
.
- equals ½
-
9. The method of claim 5, wherein γ
- is approximately equal to
- is approximately equal to
-
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. - View Dependent Claims (14, 15, 16)
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. - View Dependent Claims (18, 19, 20, 21, 22, 23)
- 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;
-
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.
- 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;
Specification