Gamut boundary determination using alpha-shapes
Tomasz J.Cholewo and Shaun Love
Lexmark International,Inc.
Lexington,KY,USA
Abstract
日凌
This paper proposes a solution to the problem offinding the boundary of the gamut of a color printing device or of a color image.A surface triangulation of a set of points in the color space is computed using an alpha-shape,which is a generalization of a convex hull applicable also to non-convex solids.The desired level of detail can be controlled by means of an alpha parameter.A method for selecting the suitable value of this parameter is proposed. Keywords:color gamut,visualization,convex hull,alpha-shape
Introduction
A color gamut is a delimited region in color space,con-taining colors that are physically realizable by a
given de-vice 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 re-produced.
Approaches to reconstruction of the gamut surface can be divided into two groups:colorant 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 colori-metric)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(Rolleston,1993).Such identified sur-face points can then be connected to form a mesh describ-ing the whole surface of the gamut.The resulting bound-aries are called physical boundaries.When there are more than three colorants involved,this usually involves comput-ing the gamuts of the three-colorant subprocesses and then finding their union.
In a method described by Braun and Fairchild(1996) the surface points identified in the colorant space are con-verted to the cylindrical CIELAB coordinates and projected on the L*h*plane.The poin
ts were triangulated using neighborhood information from the colorant space.The obtained gamut surface is represented by a matrix specify-ing the maximum chroma value attainable for given light-ness 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 ac-curately because of the discrete location of the grid points.
Other authors used the characterization data(pairs of corresponding colorant space and color space values)to create a device model which then is employed for deriva-tion of the gamut surface.This requires making additional assumptions about the behavior of the device and hence de-pends on the physics of the printing process,but in return provides a method for removing some measurement noise from the data and a possibility to create analytical repre-sentations of the gamut.
Mahy(1999)used the device characterization data to build a number of localized three-dimensional Neugebauer models.These models are analytically inverted to produce a set of closed contours situated on planes corresponding to constant lightness values in the color space.The color gamut contours of an n-colorant process for specific sur-faces are determined as envelopes of contours of all its three-ink subprocesses.
Herzog(1998)proposed to represent the gamut by an analytical function based on a distorted cube.This pro-vides an easy method of calculating the maximum chroma for any combination of lightness and hue but limits appli-cability of the method to cube-shaped gamuts.
As an alternative to colorant space methods,the geo-metric approaches work for any number of colorants and without knowledge of the colorant space data or the de-vice 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 col-orant space methods,many color space points are needed to describe the gamut surface precisely.
Mahy(1998)observed that for some printing processes certain colorant combinations result in colors that fall out-side the region delimited by physical gamut boundaries. This phenomenon is caused by the presence of regions of
non-monotonic mapping between the colorant and the color spaces which give rise to so-called natural boundaries cor-responding to the local extrema of these mappings.The necessary condition for this to occur is to have some col-orant combination inside the gamut produce the same color as s
ome colorant combination from the physical boundary. The problem of natural boundaries which is very difficult to solve using colorant space methods can be addressed by geometric techniques by ensuring that the used color point set covers also the regions inside the colorant hypercube.2009年7月1日
One simple geometric approach is to use a convex hull of the data set as the gamut surface.Unfortunately,in prac-tice,non-convex(concave)surfaces are common in device gamut boundaries,and the convexity assumption usually leads to an overestimation of the gamut volume.
Balasubramanian and Dalal(1997)attempted tofix this deficiency by“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 disad-vantage 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.
In this paper we present a new geometric method based on the alpha-shape of the set of points.
Alpha shapes
The concept of alpha-shapes developed by Edelsbrunner and M¨u cke(1994)formalizes the intuitive notion of“shape”for spatial point sets.The alpha-shape is a mathematically well-defined generalization of the convex hull and is a sub-graph of the Delaunay triangulation.Given afinite point set,a family of shapes can be derived from the Delaunay triangulation of the point set;a real parameterαcontrols the desired level of detail.The set of all real alpha val-ues leads to a whole family of shapes capturing the in-tuitive notion of“crude”versus“fine”shapes of a point set.Alpha-shapes have been used in scientific computing and engineering for a variety of purposes,such as molecu-lar modeling,modeling and examination of tissue features, CAD/CAM solid surface reconstruction,mesh generation, and three-dimensional morphing between two shapes.
In three-dimensions the alpha-shape consists of many, possibly disjoint,,tetrahedra,triangles,edges, and points.Forα=0,the alpha-shape is identical to the original set of points S,and forα=∞,the set of all trian-gles in an alpha-shape is equal to the convex hull of S.A simplex belongs to the alpha-shape of S when there exists a sphere of radiusαwhich does not contain any points of S and which has the property that all vertices of this simplex lie on its boundary.
For our purposes we are using only tetrahedra and trian-gles of the alpha-complex.Tetrahedra are us
ed for volume computation.For gamut surface definition we use a subset of an alpha-shape consisting of all regular , triangles which bound some tetrahedra which are also part of an alpha-shape,which we denote as an alpha-surface.
In practice the computation of the alpha-surface starts withfinding the Delaunay triangulation of the point set S, which is a triangulation of the points in S such that no tetra-hedron contains a point of S in its circumsphere.This re-sults in a set of tetrahedra and convex hull triangles.Each face(triangle)is shared by exactly two tetrahedra or is a convex hull triangle bounding one tetrahedron.A triangle belongs to the alpha-surface when the value of the parame-terαis between the radii of the smallest circumspheres for neighboring tetrahedra.
These concepts are illustrated for a two-dimensional case in Figure1.An interactive demonstration is available on the Internet(B´e lair,1997).
Sorted radii of the smallest circumspheres of all tetra-hedra form a so calledα-spectrum.As the parameterαis increased,the alpha-shape changes only at values belong-ing to theα-spectrum,and therefore it is possible to create an ordered collection of alpha-shapes.In such a collection, alpha-rank denotes an index of a specific alpha-shape.
An important issue when using alpha-surfaces is selec-tion of an appropriate value for theαparameter.When alpha-shapes are applied to the device gamut surface recon-struction we can make additional assumptions that make this task easier.The minimal useful value ofα,which we will denote byα∗,is provided by the condition that all tetrahedra enclosed by the alpha-surface must belong to the alpha-shape.This corresponds to the intuitive notion that the gamut should not have any voids(regions in a shape that cannot be accessed from the outside).
Another requirement could be for the alpha-surface to consist of a single connected component.Since all trian-gles in an alpha-surface are regular we can determine the number of connected tetrahedral components by checking connectivity of a graph formed by the edges of the alpha-shape.
The alpha-surface obtained forα∗will sometimes be unnecessarily ragged as a result of not including tetrahedra located close to the surface.On the other hand,overly large parameter values will result in overestimation of the gamut volume by hiding some surface concavities.Therefore,the optimum value ofα,especially for irregular image gamuts, is best determined experimentally,preferably using inter-active visualization tools.
Results
We developed a visualization package in VRML2.0and JavaScript which allows us to interactively select the value
a.
中国青年运动的
时代主题c.
d.
Figure1: values of set of shape. shape(αplane.
a.
100
200
300
400
500
600
700
800
100
200 300rank
volume
100
200
300
400
500
600
700
800
10
20 30 40rank
area
c.
100
200
300
400
500
600
700
800
100
200 300rank
triangles
Figure 3:Signatures of a laser printer gamut alpha-shape as a function of the alpha-rank:a.volume (in thousands of cubic CIELAB units),b.surface area (in thousands of square CIELAB units),and c.the number of triangles.The vertical line shows the alpha-rank corresponding to the value α∗for which the alpha-surface consists of a single component.
eral disjoint components which are common in the case of image gamuts.
By an extension of this method,one can calculate the approximate percentage of colors shared by tw
o different gamuts.The volumes of V (A )and V (B )of alpha-shapes based on the two separate data sets A and B and the volume of the combined data sets V (A ∪B )are computed.Then the volume of the common part can be found from the equation V (A ∩B )=V (A )+V (B )−V (A ∪B ).One possible application of this method is to find the percentage of CRT colors that can be reproduced on a specific printer.
Figure 4presents the results of applying our gamut sur-face construction method to a set of colors used in an im-age.The parameter αwas chosen to be less than α∗in order to better emphasize lack of light blue colors in the image.In this case there is no central point from which all surface triangles are visible and therefore the gamut sur-face and its volume cannot be computed by the method de-scribed in (Balasubramanian and Dalal,1997).This also makes it impossible to represent this gamut surface as a function of lightness and hue using method of Braun and Fairchild (1996).
Conclusions
The described method enables creation of approximate an-alytical descriptions of the surfaces of the gamuts of color printing devices and color images.This facilitates com-parisons of gamuts,computation of simple figure-of-merit quantities related to the quality of the device such as a
vol-ume of a gamut,and performing out-of-gamut mappings using geometric techniques.Many printers exhibit natural color gamut boundaries which exceed the physical colorant boundaries and therefore it is important to use geometric
methods of gamut surface construction to get an accurate estimate of the gamut boundary and volume.
As an extension of our method it is possible to construct a shape that has different levels of detail in different parts of space by assigning a weight to each point where a large weight favors and a small weight discourages connections to neighboring points.The resulting object is known as the weighted alpha shape (Edelsbrunner,1992).If all weights are zero,it is the same as the original,unweighted alpha shape.
References
R.Balasubramanian and E.Dalal.A method for quantifying the color gamut of an output device.In Proceedings of SPIE ,vol-ume 3018,pages 110–116,San Jose,Calif.,January 1997.F.B´e lair.ill.ca/˜banzai/alpha/alpha.html:Ev-erything you always wanted to know about alpha shapes but were afraid to ask,1997.G.J.Braun and M.D.Fairchild.Techniques for gamut surfac
e definition and visualization.In Proceedings of the IS&T/SID Color Imaging Conference ,pages 147–152,Scottsdale,Ariz.,November 1996.H.Edelsbrunner.Weighted alpha shapes.Technical Re-port UIUCDCS-R-92-1760,Department of Computer Science,University of Illinois at Urbana-Champaign,1992.H.Edelsbrunner and E.P.M¨u cke.Three-dimensional alpha shapes.ACM Trans.Graphics ,13:43–72,1994.P.G.Herzog.Further development of the analytical color gamut representation.In Proceedings of SPIE ,volume 3300,pages 118–128,San Jose,Calif.,January 1998.M.Mahy.Insight into the solutions of the Neugebauer equations.In Proceedings of SPIE ,volume 3300,pages 76–85,San Jose,Calif.,January 1998.M.Mahy.Color separation method and apparatus for same.U.S.Patent 5,878,195,March 1999.
a.
b.
L* c.
L* Figure4:)image “N1A:Portrait”:a.image;b.histogram of colors present in the image in CIELAB space(larger spheres correspond to colors ap-pearing more frequently);c.alpha-shape of the set of points from subfigure b.forα<α∗.E.P.M¨u cke.Shapes and Implementations in Three-Dimensional
Geometry.PhD thesis,University of Illinois at Urbana-Champaign,Dept.Comput.Sci.,1993.
National Center for Supercomputing Applications.
/alpha/,Alpha shapes visual-ization software,1996.
R.J.Rolleston.Visualization of colorimetric calibration.In Pro-ceedings of SPIE,volume1912,pages299–309,1993.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议