Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-11-15
2002-11-12
Wallerson, Mark (Department: 2722)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S520000, C358S537000
Reexamination Certificate
active
06480301
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to images and image forming devices, and more particularly, to determining a gamut boundary for an image or an image forming device.
BACKGROUND OF THE INVENTION
A color gamut is a delimited region in color space, containing colors that are physically realizable by a given device or that are present in a given image. Knowledge of the color gamut surface is useful for many color science-related tasks such as visualization, gamut volume calculation, and deciding how colors outside the color gamut should be reproduced.
Approaches to reconstruction of the gamut surface can be divided into two groups: color space methods, which use the information about the connectivity in a device color space; and geometric methods, which are based only on a set of point coordinates in a device-independent (or colorimetric) color space such as CIELAB or CIECAM97s.
The colorant space methods are based on an assumption that a color space point lies on a surface of the gamut when at least one of the colorant coordinates attains its minimum or maximum value. Such identified surface points can then be connected to form a mesh describing the whole surface of the gamut. The resulting boundaries are called physical boundaries. When there are more than three colorants involved, this usually involves computing the gamuts of the three-colorant subprocesses and then finding their union.
In one method for the reconstruction of a gamut surface, the surface points identified in the colorant space are converted to the cylindrical CIELAB coordinates and projected on the L*h* plane, The points were triangulated using neighborhood information from the colorant space. The obtained gamut surface is represented by a matrix specifying the maximum chroma value attainable for give lightness and hue. This technique assumes that for each point on the gamut boundary there is at most one chroma value for a given combination, which is true for most typical printer gamuts but is not satisfied by some image gamuts. The corners and edges of the gamut may not be represented accurately because of the discrete location of the grid points.
As an alternative to colorant space methods, the geometric approaches work for any number of colorants and without knowledge of the colorant space data or the device model. Therefore they can be used for construction of gamut surfaces for arbitrary data sets such as measurements of targets with unknown underlying colorant specifications or for the set of colors present in an image. Similar to colorant space methods, many color space points are needed to describe the gamut surface precisely.
One geometric approach to the construction of gamut surfaces uses a convex hull of the data set as the gamut surface. Unfortunately, in practice, non-convex (concave) surfaces are common in device gamut boundaries, and the convexity assumption usually leads to an overestimation of the gamut volume.
An approach to fixing this deficiency includes “inflating” the data set before computing its convex hull in such a way that the concave surfaces become convex for the purpose of generating the mesh. The disadvantage of this approach is the heuristic character of the method requiring precise selection of the center point and three parameters. This limits the method's applicability to printer-like gamuts. Over-inflation of the gamut may result in interior points being identified as surface points.
For these and other reasons there is a need for the present invention.
SUMMARY OF THE INVENTION
In one embodiment of the invention, a method for finding a gamut boundary of a color image includes several operations. A set of points defining a gamut of the color image is identified. A parameter &agr; for an alpha-shape is selected, and the gamut boundary of the color image is computed from the set of points and &agr;. Computing the gamut boundary of the color image from the set of points and the &agr; includes finding a Delaunay triangulation of a set of points such that for each of the plurality of tetrahedrons included in the &agr;-shape its circumsphere does not contain points from the set of points.
In an alternate embodiment of the invention, an apparatus includes a processing unit, a memory unit coupled to the processing unit, and a software means operative on the processing unit. The software means, in one embodiment, is capable of calculating a color gamut volume from a color gamut. For the purpose of calculating the color gamut volume, the software means comprises the operations of identifying an alpha shape having a plurality of tetrahedra associated with the color gamut and summing the volumes of the plurality of tetrahedra.
In an alternate embodiment, the software means includes operations capable of finding the percentage of colors in an image that can be rendered by an image forming unit. The software means calculates this percentage by identifying the volume of the intersection of the image gamut and the image forming unit gamut. This volume is divided by the volume of image gamut to obtain the percentage of colors in the image that are also capable of being rendered by the image forming unit.
Various means for practicing the invention and other advantages and novel features thereof will be apparent from the following detailed description of illustrative embodiments of the invention.
REFERENCES:
patent: 5343311 (1994-08-01), Morag et al.
patent: 5390035 (1995-02-01), Kasson et al.
patent: 5416890 (1995-05-01), Baretta
patent: 5510910 (1996-04-01), Bockman et al.
patent: 5519515 (1996-05-01), Komatsu
patent: 5625378 (1997-04-01), Wan et al.
patent: 5704026 (1997-12-01), Wan
patent: 5721572 (1998-02-01), Wan et al.
patent: 5731818 (1998-03-01), Wan et al.
patent: 5734745 (1998-03-01), Ohneda
patent: 5740076 (1998-04-01), Lindbloom
patent: 5748858 (1998-05-01), Ohtsuka et al.
patent: 5767992 (1998-06-01), Tanaka et al.
patent: 5801854 (1998-09-01), Naylor, Jr.
patent: 5809213 (1998-09-01), Bhattacharjya
patent: 5815642 (1998-09-01), Kumada
patent: 5850229 (1998-12-01), Edelsbrunner et al.
patent: 5872898 (1999-02-01), Mahy
patent: 6268930 (2001-07-01), Ohta et al.
Balasubramanian, R., et al., “A Method for Quantifying the Color Gamut of an Output Device.”,Proceedings of SPIE, 3018, 110-116, (Jan. 1997).
Braun, G.J., et al., “Techniques for Gamut Surface Definition and Visualization”,The Fifth IS&T/SID Color Imaging Conference: Color Science, Systems and Application, Scottsdale, Arizona, Nov. 17-20, 1997., 147-152, (1997).
Edelsbrunner, H., et al., “Three-Dimensional Alpha Shapes”,ACM Transactions on Graphics, 13(1), 43-72, (Jan. 1994).
Herzog, P.G., “Further Development of the Analytical Color Gamut Representation”,Proceedings of SPIE, 3300, San Jose, California, Jan. 28-30, 1998, 118-128, (1998).
Mucke, E.P., “Shapes and Implementations in Three-Dimensional Geometry”,Thesis for the Degree of Doctor of Philosophy in Computer Science, Graduate College of the University of Illinois at Urbana-Champaign; University Microfilm International, publ. (Order #9416411), 1-101, (1998).
Rolleston, R., “Visualization of Colorimetric Calibration”,Proccedings of SPIE, 1912 Color Hard Copy and Graphic Arts 11., 299-309, (1993).
King & Schikli PLLC
Lexmark International Inc.
Wallerson Mark
LandOfFree
Method and apparatus for gamut boundary determination does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for gamut boundary determination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for gamut boundary determination will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2993118