Abstract:
The present invention generates a color characterization model for performing transformation from a device-dependent color space of a color device to a device-independent color space. A first set of color measurement data is accessed corresponding to actual measurements of the color device, wherein the actual measurements define a measurement range in the device-dependent color space, and wherein the measurement data includes data point pairs, each data point pair having corresponding device-dependent values and device-independent values. Next, a second set of data point pairs is generated based on a predesignated set of device-dependent values outside the measurement range, by extrapolating device-independent values from the first set of color measurement data. The color characterization model is then determined based on both the first set of color measurement data and the generated second set of data point pairs. Because the color characterization model is determined based on actual measurements and extrapolated values, the color characterization model is well-behaved and does not exhibit significant overshooting or undershooting beyond the measurement range.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     This invention relates generally to the field of color characterization of color input devices, and specifically relates to generating a color characterization model for performing transformation from a device-dependent color space to a device-independent color space. The color characterization model is based on measured color data points.  
         [0003]     2. Description of the Related Art  
         [0004]     Traditional color management systems (CMSs) use color characterizations of color input devices to derive color transformations that transform color coordinates between a device-dependent color space that depends on the device, and a device-independent color space. In particular, color characterization for a color input device such as a camera or scanner can be derived by first capturing a target consisting of predesignated color patches. In a device-dependent color space such as the RGB color space, this results in an RGB bitmap image in which the color of each patch is encoded in an RGB value.  
         [0005]     Given a particular target, the color transformation between the device-dependent and device-independent color spaces can be modeled reasonably by polynomials of low degrees. The mathematical method or technique for fitting these polynomials is known as polynomial regression.  
         [0006]     A problem arises in the use of polynomial regression based on measured data points. In particular, the use of polynomials tends to overshoot or undershoot beyond the range of the measured data points in a given space. An aspect of this problem is that the device-independent color space typically has constraints associated with it that are imposed by the physical range of the quantities being modeled. In other words, a color in the device-independent color space is typically represented by three coordinates. These three coordinates must satisfy certain constraints and relationships among them to represent a physically possible color. To impose these constraints, domain knowledge rather than the use of purely statistical techniques is required.  
         [0007]     If the measured data points from the color input device uniformly fill in the device-dependent color space, the problem of overshooting or undershooting beyond the range of the data points does not arise. However, data points measured from a standard target are rarely distributed uniformly in the device-dependent color space. For instance, measured RGB points typically fill up the inner portions of the RGB cube, or reside in a lower dimensional manifold of the RGB cube. When this happens, the regressed polynomials based on the measured data points are inaccurate in predicting device-independent values beyond the range of the measured data points.  
       SUMMARY OF THE INVENTION  
       [0008]     The present invention addresses the foregoing problems by imposing boundary conditions in the color space of the color device on which polynomial regression is performed. In particular, the invention generates a set of boundary data points that are outside a measurement range of the captured data set, which preferably correspond to axes or corner points of the device-dependent color space of the color input device, and obtains a color characterization based on a best fit to both the actual measurements and the generated data points.  
         [0009]     In one aspect, the present invention generates a color characterization model for performing transformation from a device-dependent color space of a color device to a device-independent color space. A first set of color measurement data is accessed corresponding to actual measurements of the color device, wherein the actual measurements define a measurement range in the device-dependent color space, and wherein the measurement data includes data point pairs, each data point pair having corresponding device-dependent values and device-independent values. Next, a second set of data point pairs is generated based on a predesignated set of device-dependent values outside the measurement range, by extrapolating device-independent values from the first set of color measurement data. The color characterization model is then determined based on both the first set of color measurement data and the generated second set of data point pairs.  
         [0010]     Preferably, the second set of data point pairs is generated by extrapolating the device-independent values from the first set of color measurement data based on distance and hue angle. Shepard extrapolation may be used. The first set of color measurement data is preferably obtained from a measurement-only color profile corresponding to the color device.  
         [0011]     The color characterization model is preferably determined by either multivariate linear regression or nonlinear regression. In addition, the predesignated set of device-independent values preferably corresponds to axes or corner boundaries of the device-dependent color space. The device-dependent color space of the color device is preferably the RGB space. The device-independent color space is preferably any one of the CIELUV space, the CIELAB space or the JAB space. The color characterization model is preferably usable by a color management system.  
         [0012]     Because the present invention introduces a set of boundary data points that are outside of the measurement range of the first set of color measurement data, extra penalty is imposed on undesirable polynomials that overshoot or undershoot near device-dependent color space boundaries. In addition, the added data points allow for constraints which are imposed by the physical range of the color space being modeled to be considered.  
         [0013]     This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiment thereof in connection with the attached drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]      FIG. 1  is a view showing the appearance of one embodiment of the invention.  
         [0015]      FIG. 2  is a block diagram depicting an example of an internal architecture of the  FIG. 1  embodiment.  
         [0016]      FIG. 3  is a block diagram depicting a color management module which can carry out a method of generating a color characterization model according to the present invention.  
         [0017]      FIG. 4  is a flowchart that illustrates generating a color characterization model for a color input device according to the present invention.  
         [0018]      FIG. 5  is a representational diagram depicting the generation of additional data points according to the present invention.  
         [0019]      FIG. 6  is a flowchart illustrating the generation of additional data points according to the present invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]     Referring to  FIG. 1 , a view showing the exterior appearance of one embodiment of the invention is shown. Specifically,  FIG. 1  depicts computing equipment  100 , which includes host processor  103  comprising a personal computer (hereinafter “PC”). Provided with computing equipment  100  are color monitor  101  including display screen  107  for displaying text and images to a user, keyboard  106  for entering text data and user commands into PC  103 , and pointing device  111 . Pointing device  111  preferably comprises a mouse, for pointing, selecting and manipulating objects displayed on display screen  107 .  
         [0021]     Computing equipment  100  includes a computer readable memory medium such as floppy disk drive  108 , fixed disk  110 , and/or CD-ROM drive  109 . Such computer readable memory media allow computing equipment  100  to access information such as image data, computer-executable process steps, application programs, and the like, stored on removable and non-removable memory media. In addition, network access  105  allows computing equipment  100  to acquire information, images and application programs from other sources, such as a local area network or the Internet.  
         [0022]     Digital scanner  104  and digital camera  102  are both color input devices for which a color characterization model can be generated according to the present invention. Digital color scanner  104  is provided for scanning documents and images and sending the corresponding image data to computing equipment  100 . Digital color camera  102  is provided for sending digital image data to computing equipment  100 . Of course, computing equipment  100  may acquire digital image data from other color input devices, such as a digital video camera.  
         [0023]      FIG. 2  is a block diagram illustrating the internal architecture of the  FIG. 1  embodiment. As shown in  FIG. 2 , PC  103  includes network interface  202  for network access  105 , and a central processing unit (“CPU”)  201 , that interfaces with computer bus  200 . Also interfacing with computer bus  200  are fixed disk  110 , random access memory (“RAM”)  207  for use as main memory, read only memory (“ROM”)  208 , floppy disk interface  209  to allow PC  103  to interface with floppy disk drive  108 , display interface  210  for interfacing with monitor  101 , keyboard interface  203  for interfacing with keyboard  106 , mouse interface  204  for interfacing with pointing device  111 , scanner interface  205  for interfacing with scanner  104 , and camera interface  206  for interfacing with digital camera  102 .  
         [0024]     Main memory  207  interfaces with computer bus  200  so as to provide quick RAM storage to CPU  201  during execution of software programs such as the operating system application programs, and device drivers. More specifically, CPU  201  loads computer-executable process steps from fixed disk  110  or other memory media into a region of main memory  207  in order to execute software programs. Data such as color measurement data can be stored in main memory  207 , where the data can be accessed by CPU  201  during execution.  
         [0025]     Read only memory  208  stores invariant computer-executable program code, or program or process steps, for basic system functions such as basic input and output (I/O), startup, or reception of keystrokes from keyboard  106 .  
         [0026]     As also shown in  FIG. 2 , fixed disk  110  stores computer-executable code for application programs  211  such image processing programs like Adobe® Photo shop™.  
         [0027]     Fixed disk  110  also stores color management module (CMM)  218 . CMM  218  renders color image data from a device-dependent color space to a device-independent color space, and vice versa. CMM  218  uses measurement data from color measurement profiles to generate the device transforms necessary to transform color image data into the color space of the destination color image data.  
         [0028]     Forward model  219  is a data structure by which color behavior of a color device is modeled, and performs the transformation from the device-dependent color space of a color input device to a device-independent color space. Forward model  219  can be embodied into a single device driver such as scanner driver  213  or camera driver  214 . The generation of forward model  219 , being the color characterization model for performing transformation from a device-dependent color space of a color input device to a device-independent color space, is described in more detail below.  
         [0029]     It is also possible to implement CMM  218  according to the invention as a dynamic link library (“DLL”), or as a plug-in to other application programs such as image manipulation programs like the Adobe® Photoshop™ image manipulation program, or as part of scanner driver  213  or camera driver  214 .  
         [0030]     Fixed disk  110  further stores computer-executable code for monitor driver  212 , scanner driver  213 , camera driver  214 , other device drivers  215 , image files  216  and other files  217 .  
         [0031]      FIGS. 1 and 2  illustrate one example of a computing system that executes program code, or program or process steps, configured to generate a color transform using a data structure by which behavior of a color input device is modeled. Other types of computing systems may also be used.  
         [0032]     With reference to  FIG. 3 , a block diagram depicting CMM  218 , which carries out a method of generating a color characterization model according to the present invention, is shown. CMM  218  contains color input characterization module  301  for characterizing color input device  300 , as well as color output device profile  305  for defining a color characterization for color output device  306 . CMM  218  operates to accept color values in device-dependent coordinates (such as scanner RGB coordinates), apply the color characterization model and output corresponding color values in the device-independent coordinates (such as Luv). CMM  218  also operates to transform the device-independent coordinates into device-dependent coordinates (such as printer CMYK or monitor RGB) based on color output device profile  305 . CMM  218  also operates to perform gamut-mapping between the device-dependent and device-independent color spaces.  
         [0033]     Color input characterization module  301  contains process steps for an access data module  302  to access sampled color measurement data of color input device  300 , including data point pairs of measured device-dependent values and their corresponding device-independent values. Color input characterization module  301  also contains process steps for a generate additional points module  303  for generating additional points outside a range defined by the actual measurements of the color input device. In addition, color input characterization module  301  contains process steps for a determine forward model module  304  for determining a color characterization model (forward model  219 ) based on the original color measurement data and the additional generated data points.  
         [0034]     Color input characterization module  301 , access data module  302 , generate additional points module  303 , determine forward model module  304 , and color output device profile  305  can all be embedded within CMM  218 , or can be separate application programs accessed by CMM  218 , or can be combined into a single application program accessed by CMM  218 . In addition, image data can be input from color input device  300  to CMM  218  using forward model  219 . In this embodiment, color input device  300  is scanner  104  or digital camera  102 , although a different color input device such as a digital video camera can be used.  
         [0035]     Color characterization of color input device  300  generally consists of capturing an image of a target consisting of color patches with known color values in a device-independent color space. Popular choices of such a target include the IT8.7 target and the Color Checker. The result of the capture is an device-dependent bitmap image in which the color of each patch is encoded in a device-dependent value such as RGB. Data point pairs having corresponding RGB values and Luv values make up the color measurement data, and define a measurement range. The measurement range typically does not extend to the boundaries of the RGB color space cube.  
         [0036]     These color measurement data are specific to color input device  300 , and the goal of calorimetric characterization is to establish an empirical relationship between RGB values and color values in a device-independent color space such as CIELUV. More specifically, a mathematical transformation is sought from RGB to Luv that models as accurately as possible the behavior of color input device  300 . Such a transformation can be modeled reasonably well by polynomials of low degrees.  
         [0037]     In the preferred embodiment, RGB is the device-dependent color space, Luv is the device-independent color space, and a 20-term cubic polynomial is used as the color characterization model for color input device  300 . However, other device-dependent and device-independent color spaces can be used, as well as polynomials with a different number of terms. Given the 20-term cubic polynomial, coefficients λ i , α i , β i  are sought such that the following equations satisfy the least squares error condition on the data points.  
                 L   ^     ⁡     (     R   ,   G   ,   B     )       =       ⁢       λ   1     +       λ   2     ⁢   R     +       λ   3     ⁢   G     +       λ   4     ⁢   B     +       λ   5     ⁢     R   2       +       λ   6     ⁢   RG     +       λ   7     ⁢   RB     +                     ⁢         λ   8     ⁢     G   2       +       λ   9     ⁢   GB     +       λ   10     ⁢     B   2       +       λ   11     ⁢     R   3       +       λ   12     ⁢     R   2     ⁢   G     +       λ   13     ⁢     R   2     ⁢   B     +                     ⁢         λ   14     ⁢     RG   2       +       λ   15     ⁢   RGB     +       λ   16     ⁢     RB   2       +       λ   17     ⁢     G   3       +       λ   18     ⁢     G   2     ⁢   B     +                     ⁢         λ   19     ⁢     GB   2       +       λ   20     ⁢     B   3                   
                 u   ^     ⁡     (     R   ,   G   ,   B     )       =       ⁢       α   1     +       α   2     ⁢   R     +       α   2     ⁢   R     +       α   3     ⁢   G     +       α   4     ⁢   B     +       α   5     ⁢     R   2       +       α   6     ⁢   RG     +                     ⁢         α   7     ⁢   RB     +       α   8     ⁢     G   2       +       α   9     ⁢   GB     +       α   10     ⁢     B   2       +       α   11     ⁢     R   3       +       α   12     ⁢     R   2     ⁢   G     +                     ⁢         α   13     ⁢     R   2     ⁢   B     +       α   14     ⁢     RG   2       +       α   15     ⁢   RGB     +       α   16     ⁢     RB   2       +       α   17     ⁢     G   3       +                     ⁢         α   18     ⁢     G   2     ⁢   B     +       α   19     ⁢     GB   2       +       α   20     ⁢     B   3                   
                 v   ^     ⁡     (     R   ,   G   ,   B     )       =       ⁢       β   1     +       β   2     ⁢   R     +       β   3     ⁢   G     +       β   4     ⁢   B     +       β   5     ⁢     R   2       +       β   6     ⁢   RG     +       β   7     ⁢   RB     +                     ⁢         β   8     ⁢     G   2       +       β   9     ⁢   GB     +       β   10     ⁢     B   2       +       β   11     ⁢     R   3       +       β   12     ⁢     R   2     ⁢   G     +       β   13     ⁢     R   2     ⁢   B     +                     ⁢         β   14     ⁢     RG   2       +       β   15     ⁢   RGB     +       β   16     ⁢     RB   2       +       β   17     ⁢     G   3       +       β   18     ⁢     G   2     ⁢   B     +                     ⁢         β   19     ⁢     GB   2       +       β   20     ⁢     B   3                   
 
         [0038]     These polynomials should minimize the sum of squares of errors: 
 
 SSE=Σ ( {circumflex over (L)} ( R   i   , G   i   , B   i )− L   i ) 2 +( û ( R   i   , G   i   , B   i )− ui ) 2 +( {circumflex over (v)} ( R   i   , G   i   , B   i )− vi ) 2 ), 
 
 where the data point pairs are (R i , G i , B i ) and (L i , u i , v i ). The least squares problem can be stated as solving the following matrix equation, where N is the number of color measurement data points:  
           (         1         R   1           G   1           B   1         …           G   1     ⁢     B   1   2             B   1   3             1         R   2           G   2           B   2         …           G   2     ⁢     B   2   2             B   2   3             ⋮       ⋮       ⋮       ⋮       …       ⋮       ⋮           1         R   N           G   N           B   N         …           G   N     ⁢     B   N   2             B   N   3           )     ⁢     (           λ   1               λ   1             ⋮             λ   20           )       =     (           L   1               L   1             ⋮             L   N           )         
 
 or, more compactly, RΛ=L. 
 
         [0039]     Typically, N is larger than 20, so the above-equation is over-determined, necessitating a least squares solution. A closed form for the solution for Λ can be given by: 
 
Λ=( R   T   R ) −1 ( R   T   L ) 
 
         [0040]     In practice, the closed form solution is not used. Instead, for a more numerically stable algorithm, the least squares solution is obtained by first decomposing the matrix R into a matrix product (for example, using singular value decomposition), followed by back substitution.  
         [0041]     As noted above, the use of polynomials tends to overshoot or undershoot beyond the range of the measured data points in a region beyond the range of the measured data points. An aspect of this problem is that the Luv color space typically has constraints associated with it that are imposed by the physical range of the quantities being modeled. In other words, a color in the device-independent color space is typically represented by three coordinates. These three coordinates must satisfy certain constraints and relationships among them to represent a physically possible color. To impose these constraints, domain knowledge rather than the use of purely statistical techniques is required. The present invention addresses the foregoing by introducing boundary points outside of the measurement range of the color measurement data.  
         [0042]     Referring now to  FIG. 4 , a flowchart that illustrates generating a color characterization model for a color input device according to the present invention is shown. Following start bubble S 400 , color measurement data is accessed in step S 401 , additional points are generated in step S 402  based on the color measurement data, and forward model  219  is determined using both the color measurement data and the generated data points in step S 404 . The generation of additional points is described in more detail in relation to  FIGS. 5 and 6 .  
         [0043]     With reference to  FIG. 5 , a representational diagram depicting the generation of additional data points according to the present invention is shown. In the preferred embodiment, eight control points are introduced corresponding to the corners of the RGB color space cube. These points are typically outside of the measurement range of the color measurement data. If the values for color input device  300  are normalized to unity, then the RGB values for these control points are: 
        R=0, G=0, B=0     R=0, G=0, B=1     R=0, G=1, B=0     R=0, G=1, B=1     R=1, G=0, B=0     R=1, G=0, B=1     R=1, G=1, B=0     R=1, G=1, B=1        
 
         [0052]     Luv values corresponding to each of the listed (R, G, B) control points are then determined. In determining the Luv values, the hue of the (R, G, B) color should be considered.  
         [0053]     Generally, for a given (R, G, B) from above, a weight is assigned to each of the (R i , G i , B i ) within a neighborhood of (R, G, B) in the sampled data set. Weight is determined based on two criteria. First, the weight is inversely proportional to the distance between (R, G, B) and (R i , G i , B i ). Second, data points having a significantly different hue than the given (R, G, B) point should be discarded, meaning the weight for those data points should be set to 0. To take the hue into account, only points that lie within a cone whose vertex is at (0, 0, 0) are considered, whose axis coincides with the line joining (0, 0, 0) to (R, G, B), and whose semi-vertical angle θ satisfies cos θ=0.9, if such points exist.  
         [0054]     With reference to  FIG. 6 , a flowchart illustrating the generation of additional data points according to the present invention is shown. Following start bubble S 600 , the Luv value for white R=G=B=1) is assigned L=100 and u=v=0 in step S 601 . Then, in step S 602 , a determination is made as to whether all the Luv values corresponding to the eight corners of the RGB cube have been assigned. If the answer to this inquiry is yes, step S 602  is followed by end bubble S 613 . Otherwise, in step S 603 , an RGB point without a corresponding Luv value is selected. Cos θ is initialized to 0.9 in step S 604 , followed by a decision as to whether cos θ is greater than or equal to 0 in step S 605 . If the answer to this inquiry is no, an error condition occurs in end bubble S 614 . Otherwise, a maximum radius value MAX_R is initialized to a maximum distance (MAXD) divided by 5 if cos θ exceeds 0, or MAX_R is initialized to MAX_D if cos θ equals 0. MAX_D equals 3 in the case of 1-norm. In step S 607 , a radius value R is initialized to 0.1. This is followed by an inquiry in step S 608  as to whether R is less than or equal to MAX_R. If the answer to this inquiry is no, cos θ is decremented by 0.05 and step S 605  is revisited. Otherwise, sample points are collected for a set S in step S 609 . Then, in step S 610 , a determination is made as to whether set S is empty. If set S is not empty, an Luv value is calculated based on set S. The calculation of the Luv value is discussed in more detail below. If set S is empty, R is incremented by 0.1 in step S 611 , and step S 608  is revisited. This repeats until set S is not empty.  
         [0055]     After yielding a non-empty set S of points (R i , G i , B i ) and corresponding (L i , u i , v i ), then for each such point, a normalized weight w i  is assigned as follows:  
         h   i     =         (       max   ⁡     (       MAX_D   -     d   i       ,   0     )         d   i       )     2     ⁢           ⁢   where         
         d   i     =            R   -     R   i            +          G   -     G   i            +          B   -     B   i                  
         w   i     =       h   i     /       ∑     j   ∈   S       ⁢     h   j             
 
 where h i  is the weight before normalization and satisfies the inverse-distance property, and d i  is the distance of (R, G, B) from (R i , G i , B i ). 
 
         [0056]     The extrapolated Luv value for (R, G, B) is then calculated by:  
       L   =       ∑     i   ∈   S       ⁢       w   i     ⁢     L   i             
       u   =       ∑     i   ∈   S       ⁢       w   i     ⁢     u   i             
       v   =       ∑     i   ∈   S       ⁢       w   i     ⁢     v   i             
 
         [0057]     Referring back to  FIG. 4 , once the additional data points are generated, multivariate linear regression is performed on the N+8 data points (color measurement data points+generated data points). This results in a color characterization model (forward model  219 ) for input color device  300 .  
         [0058]     By introducing boundary data points outside of the measurement range of the original color measurement data, extra penalty is imposed on the polynomials that overshoot or undershoot near polynomial boundaries. In addition, the generated data points allow for constraints which are imposed by the physical range of the color space being modeled to be considered.  
         [0059]     The invention has been described above with respect to particular illustrative embodiments. It is understood that the invention is not limited to the above-described embodiments and that various changes and modifications may be made by those skilled in the relevant art without departing from the spirit and scope of the invention.