Patent Publication Number: US-7916349-B2

Title: Color pixel error diffusion in a CMYK input color space

Description:
TECHNICAL FIELD 
     The present invention is directed to systems and methods for diffusing color pixel error in a halftoning process in a color marking device capable of dot-on-dot printing, such as solid ink devices. 
     BACKGROUND 
     Halftoning is the process of representing a continuous tone image by a bi-level image such that, when viewed from a suitable distance, the bi-level image gives the same impression as the contone image. Halftoning techniques are widely employed in the printing and displaying of digital images and are necessary because the physical processes involved are binary in nature or because the processes being used tend to be restricted to binary operation for reasons of cost, speed, memory, or stability in the presence of process fluctuations. The general idea behind halftoning is, by varying the density of the dots used to print the individual primary colors, Cyan, Magenta, Yellow and Black (CMYK), any particular shade can be reproduced. By varying dot density, the eye perceives a shade somewhere between the solid color and the color of the background paper. The effect has its limits. When the dots get too small or are spaced too far apart, the eye starts perceiving individual dots again. 
     A pattern of dots used to produce a particular shade of color is known as a halftone screen. A halftone screen describes the set of values which together make up the set of thresholds to be applied in a halftone screening process to generate the output halftone patterns. A single-center halftone screen uses the entire area for one cell, or tile, only. The resolution of a halftone screen is defined by the number of lines of dots in one inch, measured parallel with the angle of the halftone screen. The higher the resolution of the halftone screen, the greater the detail that can be reproduced. Higher resolution requires a higher quality printing processes, otherwise the printed output image may suffer from posterization. Posterization occurs when a region of an image with a continuous gradation of tone is replaced with several regions of fewer tones, resulting in an abrupt change from one tone to another. This creates the visual effect one notices when a relatively small image has been blown up to the size of a poster. Therefore it is important to match screen resolution to the desired printing process. Further, when different halftone screens meet, a number of distracting visual effects can occur. These include the edges being overly emphasized as well as a moiré pattern. These problems can be reduced by rotating the halftone screens in relation to each other. 
     Digital halftoning utilizes a raster image or bitmap within which each monochrome element or pixel is turned ON/OFF (dot or no dot). Raster type printers employ halftoning to transform contone image data to print data that can be rendered using an array of substantially uniform dots. For example, 24-bit/pixel contone data can be halftoned to a plurality of single color 1-bit/pixel bitmaps. The collection of individual single color bitmaps forms the image. 
     The digital halftone cell contains groups of monochrome pixels within the same-sized cell area. Each equal-sized cell relates to a corresponding area (size and location) of the contone input image. Within each cell, the high frequency attribute is a centered variable-sized halftone dot composed of ink or toner. The ratio of the inked area to the non-inked area of the output cell corresponds to the luminance or gray-level of the input cell. From a suitable distance, the human eye averages both the high frequency apparent gray-level approximated by the ratio within the cell and the low frequency apparent changes in gray-level between adjacent equally-spaced cells and centered dots. 
     Color pixel error diffusion is a popular halftoning method due to its detail preservation and moiré resistance. Error diffusion methods in a color environment can be classified into two types, vector error diffusion and scalar error diffusion. Vector error diffusion is often considered to be better in image quality because it achieves higher halftone quality compared to the channel-independent scalar color error diffusion due to the better correlation among CMYK color planes. However, it requires significantly more computation and can introduce artifacts into the output device space due to an accumulation of the errors. 
     Halftoning in a CMYK domain does not necessarily result in a well-behaved inter-color correlation among secondary colors (RGB). Consequently, noticeable increases in graininess can be observed when significant amounts of secondary color dots are used to achieve the determined input ink coverages. Therefore, explicit secondary color dot control is desirable to achieve uniform dot distribution. It is also desirable to position the color dots uniformly in the very highlight and very dark shadow areas due to a requirement of long-distance spatial correlation. Performing color error diffusion in a memory efficient manner is a challenge since many of the conversions and transformations are performed in an application specific integrated circuit (ASIC), or the like, where resources can be limited. 
     Accordingly, what is needed are increasingly sophisticated systems and methods for performing color error diffusion in an efficient manner while still achieving a high-quality dispersed-dot halftone output result. 
     BRIEF SUMMARY 
     What is provided are a novel system, method, and computer program product for diffusing pixel error in a halftoning process in a color management system. The present method computes and diffuses pixel error in an input CMYK color space via a pixel-based adaptive algorithm processing CMYK ink coverages on a per-pixel basis. In order to effectuate the above, the present method introduces imaginary dot coverages and provides a conversion to handle the real and imaginary dots in an elegant manner. Results demonstrate that the present method effectively diffuses pixel error and provides a comparable high-quality halftone output result. The method is computationally efficient and thus can be implemented in a bit-constrained environment such as an ASIC or FPGA placed in the image path of a color marking device or color management system. 
     In one example embodiment, an input CMYK ink coverage is received for each pixel in a color image. Optionally, the input CMY are clipped to insure that no colorant overlaps with composite K. The present pixel-based adaptive processing method computes an error amount for a next pixel based on values determined on a previous iteration. A temporary CMYK variable carries the error from a previous iteration into a next iteration. For each pixel, the following steps are performed. The temporary CMYK is added to the current pixel&#39;s input CMYK to produce a modified C i M i Y i K i  for the current iteration. The modified C i M i Y i K i  are divided into a real and an imaginary portion. The real portion comprises a positive portion, C p M p Y p K p , defined by a real amount of coverage, in the range of 0-100%, of a physically realizable “positive” dot. The imaginary portion comprises a negative portion and an excess portion. The negative portion, C n M n Y n K n , defines an amount of coverage, less than 0%, of an imaginary “negative” dot. The excess portion, C e M e Y e K e , defines an amount of coverage, greater than 100%, of an imaginary “excess” dot. An amount of CMYK is next determined for each of the dots. In one embodiment, determining the amount of CMYK for each of the dots involves the following. An amount of C p M p Y p  is determined for the positive dot based on a maximum of the modified C i M i Y i . An amount of C n M n Y n  for the negative dot is determined as the amount of CMY sufficient to cancel the positive dot. A maximum capacity of a space S available, sufficient to accommodate C, M, and Y colorants at the current pixel location, is determined. An amount of C e M e Y e  for the excess dot is determined by the amount of CMY which cannot be settled inside of space S. The C e M e Y e  of the excess dot is subtracted from the positive dot. Thereafter, the determined amounts of CMY for each of the dots are adjusted by removing their respective K to determine for each dot an amount of residual space remaining for C, M, and Y colorant. An amount of RGB is determined for each dot from their respective CMYK amounts. This produces a CMYKRGB for each dot. These are combined to produce a CMYKK p RGB output. A hierarchical thresholding technique is performed on the CMYKK p RGB output generated by the conversion routine. Hierarchical thresholding produces a (CMYKK p RGB) h  halftone result. An inverse transformation maps the halftone result to a (CMYK) h  halftone result for the current pixel. This result is outputted. A determination is made as to a difference between the halftone result and the output of the CMYK to CMYKK p RGB conversion. This difference produces as ΔCMYKK p RGB which represents the amount of pixel error for the current iteration. An inverse transform maps the ΔCMYKK p RGB to a ΔCMYK. The ΔCMYK is fed through a low-pass filter to reduce noise sensitivity. The ΔCMYK is assigned to the temporary CMYK which carries these values into the next iteration. The temporary CMYK are combined with the input CMYK of the next pixel to produce a modified C i M i Y i K i . Processing continues for all pixels. 
     Many features and advantages of the above-described method will become readily apparent from the following detailed description and accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The foregoing and other features and advantages of the subject matter disclosed herein will be made apparent from the following detailed description taken in conjunction with the accompanying drawings, in which: 
         FIG. 1  is a flow diagram of one embodiment of the present method for diffusing pixel error in a halftoning process in a color management system; 
         FIG. 2  is a continuation of the flow diagram of  FIG. 1  with processing continuing with respect to node A; 
         FIG. 3  is a block diagram of one example embodiment of the present pixel error diffusion method; 
         FIG. 4  is a flow diagram of one example embodiment of the CMYK to CMYKK p RGB transform  308  of  FIG. 3 ; 
         FIG. 5  is a block diagram of one example embodiment of a special purpose computer system useful for implementing one or more aspects of the present pixel error diffusion method; and 
         FIG. 6  is an explanatory diagram illustrating one example computer readable medium capable of storing machine readable instructions which, when mounted on a computer or a special purpose computer system, causes the system to perform one or more aspects of the present pixel error diffusion method. 
     
    
    
     DETAILED DESCRIPTION 
     What is provided are a system and method for hierarchical color error diffusion in a CYMK input color space. The present method diffuses pixel error in an input CMYK color space via a pixel-based adaptive processing algorithm. Pixel error in CMYK color space is computed on one iteration and added to the input CMYK on a next iteration to generate a modified C i M i Y i K i  which is processed as input for the current iteration. The modified C i M i Y i K i  of the current iteration is provided as input to a conversion module which produces a CMYKK p RGB output. The CMYKK p RGB output is provided to a hierarchical thresholding module which generates a (CMYKK p RGB) h  halftone result. An inverse transform maps this halftone result to a (CMYK) h  halftone for this pixel. An amount of error for the current pixel is determined by a difference between the generated (CMYKK p RGB) h  halftone result and the CMYKK p RGB output produced by the conversion module. This produces a ΔCMYKK p RGB. An inverse transform maps the ΔCMYKK p RGB to a ΔCMYK. The ΔCMYK is filtered and added to the input CMYK of the next pixel to produce the modified C i M i Y i K i  for the next iteration. All pixels are processed accordingly. The (CMYK) h  halftone result has the color pixel error diffused. 
     It should be understood that one of ordinary skill in this art would be readily familiar with the many facets of color science such as, for example, halftones and halftoning methods, color transformation algorithms and processes, color pixel values, and other related techniques and algorithms common to the color science arts. Additionally, one of ordinary skill in this art would also be familiar with mathematical techniques used in the manipulation and transformation of color. One of ordinary skill would also be knowledgeable about software programming techniques sufficient to implement the functionality described in detail herein in their own color management systems without undue experimentation. 
     A pixel, as used herein, refers to the smallest segment into which a printed image is divided and may also refers to a signal associated with a particular position in an image. Each pixel can be a bit in binary form, a gray scale value, or a set of coordinates in the color space of the image. Pixel values can be converted into CIELAB color space by a RBG to Lab converter to obtain luminance (L) and chrominance (a,b) values. Chrominance (a) is the chrominance of a first channel. Chrominance (b) is the chrominance of a second channel. Luminance (L) is a photometric quantity which, in essence, is the effect of radiance on our eyes. Radiance is the physical quantity related to light intensity, i.e., the power of the light spreading out in some solid angle over an area. Luminance is the integration of radiance weighted with a curve, which describes how efficiently different wavelengths of light trigger visual receptors in the eye. Brightness is the subjective visual experience of luminance, i.e., the effect of luminance on the brain. The relationship of brightness to luminance is non-linear, approximately a cube root. 
     Primary colors are understood to be: Cyan (C), Magenta (M), Yellow (Y), and Black (K). Secondary colors are understood to be: Red=(M+Y), Blue=(C+M), and Green=(C+Y). For CMYK printing, dot visibility decreases in the order of brightness given by: K, B, R, G, M, C, and Y. The order of brightness may vary depending on the color composition of the inks being used. 
     A color marking device refers to a color output device capable of rendering text, graphics, images, plots, graphs, and the like, for visual examination. Such devices include production printers, xerographic devices, image reproduction equipment, color monitors, displays, and any device capable of outputting a color signal. To render a color image is to output the image to a color output device. Color output devices receive a color signal of the image and reduce the signal to viewable form. Image reduction includes the process of marking a substrate with colorants to form the image from the visual integration of the colorants on the substrate, or to display the image on an image display device. Devices capable of dot-on-dot printing include products, such as inkjet devices, which operate by propelling variably-sized droplets of liquid or molten material (inks, pigments, etc.) mixed with a colorant onto a media substrate, such as paper. The output image is formed from the visual integration of the colored dots. Appropriate sizing operations have to be performed for images where the input resolution in terms of scanned pixels is different from the output resolution in terms of printed pixels. 
     Reference is now made to  FIG. 1  which is a flow diagram of one embodiment of the present method for diffusing pixel error in a halftoning process in a color management system. 
     In the example embodiment, since the computations for a next pixel are based on an output determined on a previous iteration, at  102 , a temporary CMYK is initialized to a default state to handle the first iteration. At  104 , an input CMYK ink coverage is received for each pixel in a color image. At  106 , a determination is made whether any of the input CMY are greater than 100-K. If so, at  108 , the values are clipped. At  110 , the temporary CMYK is added to the current pixel&#39;s input CMYK to produce a modified C i M i Y i K i  for the current iteration. At  112 , the modified C i M i Y i K i  are divided into a real and an imaginary portion. The real portion comprises a positive portion, C p M p Y p K p , defined by an amount of coverage, in the range of 0-100%, achievable by a physically realizable positive dot. The imaginary portion comprises a negative portion and an excess portion. The negative portion, C n M n Y n K n , defines an amount of coverage, less than 0%, of an imaginary negative dot. The excess portion, C e M e Y e K e , defines an amount of coverage, greater than 100%, of an imaginary excess dot. At  114 , an amount of CMYK is determined for each of the positive, negative, and excess dots. In one embodiment, determining an amount of CMYK for each of the dots involves the following. First, an amount of C p M p Y p is determined for the positive dot based on a maximum of the modified C i M i Y i  input values. An amount of C n M n Y n  is then determined for the negative dot. The amount of coverage of the negative dot is the amount of CMY sufficient to cancel the coverage area of the positive dot. A maximum capacity of a space S, available to accommodate C, M, and Y colorants at the current pixel location, is determined. An amount of C e M e Y e  for the excess dot is determined. The excess dot coverage is the amount of CMY coverage which cannot be settled inside of space S. The amounts of CMY for each dot are adjusted by removing their respective amounts of K to determine an amount of residual space remaining for each C, M, and Y colorant. 
     Reference is now made to  FIG. 2  which is a continuation of the flow diagram of  FIG. 1  wherein the flow continues with respect to node A. 
     At  216 , the determined amounts of CMYK for each of the dots are transformed from a 4-channel CMYK domain to an 8-channel domain. In one embodiment, the transformation involves determining an amount of RGB for each dot based on the dot&#39;s respective CMY and combining the CMYK and RGB for each of the dots. This produces a CMYKRGB for each dot. These are combined to generate a CMYKK p RGB output. At  218 , hierarchical thresholding is performed on the CMYKK p RGB output. Hierarchical thresholding produces a (CMYKK p RGB) h  halftone result for the current pixel. At  220 , the (CMYKK p RGB) h  halftone is transformed to a (CMYK) h  halftone through an inverse transformation. The (CMYK) h  halftone result for the current pixel can then be sent to database  222  for storage and subsequent retrieval. The (CMYKK p RGB) h  halftone result can also be stored to storage device  222 . At  224 , a determination is made as to a difference between the (CMYKK p RGB) h  halftone and the CMYKK p RGB output (before and after hierarchical thresholding). This difference, denoted ΔCMYKK p RGB, represents the amount of pixel error determined on the current iteration. At  226 , an inverse transformation maps the ΔCMYKK p RGB to a ΔCMYK output. The ΔCMYK contains the error. At  228 , the ΔCMYK is low-pass filtered to reduce noise. At  230 , the ΔCMYK are assigned to the temporary CMYK for carry-over to the next iteration. At  232 , a determination is made whether any more pixels remain to be processed. If not, then processing ends. If yes, then processing continues with respect to node B of  FIG. 1 , wherein the temporary CMYK are combined with the input CMYK of the next pixel to produce modified C i M i Y i K i  to be processed. Processing continues until all pixels have been processed and a (CMYK) h  output result has been produced for the entire image. 
     Reference is now made to  FIG. 3  which illustrates one example embodiment of a block diagram of the present pixel error diffusion method. 
     An input CMYK ink coverage  302  of a pixel of an image is received. Methods of obtaining CMYK ink coverages for pixels are well known. CMYK values often take the form of digital signals obtained from an imaging device, such as a scanner. The input CMYK signals can be received from a wide variety of imaging devices and networked sources, or retrieved from memory or a storage device. 
     Clipping module  304  determines whether any of the input C, M, and Y overlaps with composite K. CMY values are clipped so that there is no overlapping. Clipping limits the maximum value of each CMY channel to 100-K. Any dot of overlapping C, M and Y is replaced by k colorant. Clipping the inputs eliminates any color dot overlapping with K dot, which is a waste of toner that can be avoided in practice. The present method is operable without ink-clipping although clipping simplifies computational complexity. 
     Adder  306 , combines the input CMYK coverages with the temporary CMYK obtained from a previous iteration. It will be appreciated that, at the junction of adder  306 , a condition exists wherein, on a first iteration of the feedback loop, temporary CMYK values are needed. These act as temporary storage which carries results of a current iteration over to a next iteration. At the bottom of each iteration, these variables are assigned the ΔCMYK outputs. These are combined with the input CMYK at the top of each iteration to produce the modified C i M i Y i K i . In order to handle the instance of a first iteration where there is no previous carry-over, temporary variables are preferably initialized to a default state, such as zero. Otherwise, anomalies may be injected into the loop and unintended consequences may result. At the bottom of each iteration, the temporary CMYK values are assigned new ΔCMYK values. The addition of the temporary CMYK and the input CMYK of the current pixel produces a modified C i M i Y i K i  which is input to CMYK to CMYKK p RGB conversion  308 . 
     Conversion module  308  maps a CMYK to a CMYKK p RGB to produce a CMYKK p RGB output. To summarize, the CMYK to CMYKK p RGB conversion first divides the modified C i M i Y i K i  into a real and an imaginary portion. The real portion comprises a positive portion, C p M p Y p K p , defined by the amount of coverage which can be achieved by a physically realizable “positive” dot. The imaginary portion comprises a negative portion, C n M n Y n K n , and an excess portion, C e M e Y e K e . The negative portion is defined by an amount of coverage (less than 0%) which can be achieved by an imaginary “negative” dot. The excess portion is defined by an amount of coverage (greater than 100%) achieved by an imaginary “excess” dot. The CMYK for each of these dots are processed separately within the conversion module (the 3 columns in  FIG. 3 ). An amount of RGB is determined for each dot from their respective CMYK amounts. This produces a CMYKRGB for each dot. These are combined to generate a CMYKK p RGB output from the conversion. 
     Hierarchical thresholding  310  takes the CMYKK p RGB output and produces a (CMYKK p RGB) h  halftone result  312 . It should be appreciated that the use of the subscript h is used to distinguish a halftone result from another result bearing identical letters. The use of a parenthesis is intended to mean that the whole value represents the halftone. For instance, (CMYKK p RGB) h  is the halftone result generated from a CMYKK p RGB input. Methods for performing hierarchical thresholding are known in the arts. One method is disclosed in commonly owned U.S. application Ser. No. 12/025,842, “Hierarchical Color Error Diffusion In A CMYKRGB Domain”, which is incorporated herein in its entirety by reference. Briefly, color components of an input CMYKRGB are hierarchically grouped into a plurality of subgroups based on relative dot visibility. More visible dot subgroups are halftoned earlier to achieve maximum uniform dot distribution. Halftoning methods are well known. Hierarchical thresholding produces a halftone result. It should be appreciated that a variety of hierarchical thresholding techniques can be realized within module  310 . 
     Inverse transform module  314  maps the (CMYKK p RGB) h  halftone  312  to a (CMYK) h  halftone output  316 . One example transform, which maps an 8-channel to a 4-channel result, proceeds as follows:
 
 C=K   p   +G+B+C   p  
 
 M=K   p   +R+B+M   p  
 
 Y=K   p   +R+G+Y   p  
 
K=K p .
 
     Alternatively, K out =K in . Inverse transformations from one domain to another are well understood in the color science arts. Other transformations are possible. The resulting (CMYK) h  halftone  316  is stored or otherwise output for subsequent utilization in a variety of methods depending on the system wherein the present method is implemented. 
     Comparator  318 , compares the output of transform module  308  with the halftone output of hierarchical thresholding module  310 . A comparator determines a difference between two inputs by subtracting one input from another. In the present instance, comparator  318  subtracts the (CMYKK p RGB) h  halftone result from the CMYKK p RGB output. This difference, ΔCMYKK p RGB, contains the pixel error in 8-channel space. 
     Inverse transform  320  maps the ΔCMYKK p RGB to a ΔCMYK. In the embodiment of  FIG. 3 , the ΔCMYK is provided to low-pass filter  322  to clip high frequencies. Such a filter is a 2-dimensional filter which reduces noise. Various filters find many uses in feedback loops. It should be appreciated that the use of a low-pass filter is intended to show one example embodiment which can improve the functionality of the illustrated feedback loop. However, it is not required for operation. One embodiment hereof does not implement a low-pass filter. Other variations use differing means in substitution for the low-pass filter depending on the complexity of the overall design wherein the present method is implemented. 
     Reference is now being made to  FIG. 4  which is a flow diagram of one example embodiment of the CMYK to CMYKK p RGB transformation  308  of  FIG. 3 . 
     The following assumes that each input CMYK has been scaled to a value in the range from 0 to 100% inclusive. It should be appreciated that scaling the inputs to a defined range decreases computational complexity. 
     For the current iteration, the modified C i M i Y i K i    400  are divided into a real and an imaginary portion. The real portion comprises a positive C p M p Y p K p  dot. The imaginary portion comprises a negative C n M n Y n K n  dot, and an excess C e M e Y e K e  dot. Each of the three dots are processed individually. The negative dot is processed on the left-most column of the flow diagram. The excess dot is processed in the middle column. The positive dot is processed on the right-most column. 
     The following describe the CMYK to CMYKK p RGB conversion. 
     At  402 , an amount of C n M n Y n K n  is determined for the negative dot. The CMY of the negative dot is based on a minimum of the modified C i M i Y i . The amount of black K n  of the negative dot is determined by the smallest CMY colorant.
 
 C   n =|min( C   i ,0)|
 
 M   n =|min( M   i ,0)|
 
 Y   n =|min( Y   i ,0)|
 
 K   n =min( C   n   ,M   n   ,Y   n ).
 
     At  404 , an amount of C p M p Y p  is determined for the positive dot:
 
 C =|max( C   i ,0)|
 
 M =|max( M   i ,0)|
 
 Y =|max( Y   i ,0)|.
 
     At  406 , a maximum capacity of a space S available to accommodate C, M, and Y colorants at the current pixel location. Space S is given by:
 
 S =max(0, 100 +K   n   −K   i ).
 
     At  408 , an amount of C e M e Y e  is determined for the excess dot. The amount of C e M e Y e  is the amount of CMY which cannot be settled inside of space S.
 
 C   e =max( C   p   −S ,0)
 
 M   e =max( M   p   −S ,0)
 
 Y   e =max( Y   p   −S ,0)|
 
 K   e =|min( C   e   ,M   e   ,Y   e )|.
 
     At  410 , the amount of C e M e Y e  of the excess dot is subtracted from the positive dot in order to determine the portion of the positive coverage that can be accommodated with the available space at the current pixel.
 
 C   p   =C   p   −C   e  
 
 M   p   =M   p   −M   e  
 
 Y   p   =Y   p   −Y   e  
 
sum p   =C   p   +M   p   +Y   p  
 
 K   p =max(sum p −2 *S , 0).
 
     At this point, CMYK values have been produced for each of the negative, positive, and excess dots. Thereafter, the determined CMY for each of the dots are adjusted by removing their respective amounts of K. This determines an amount of residual space remaining for each C, M, and Y for each dot. 
     At  412 , the amount of K n  is subtracted from each of the C n M n Y n  of the negative dot.
 
 C   n   =C   n   −K   n  
 
 M   n   =M   n   −K   n  
 
 Y   n   =Y   n   −K   n .
 
     At  416 , the amount of K e  is subtracted from each of the C e M e Y e  of the excess dot.
 
 C   e   =C   e   −K   e  
 
 M   e   =M   e   −K   e  
 
 Y   e   =Y   e   −K   e .
 
     At  418 , the amount of K p  is subtracted from each of the C p M p Y p  of the excess dot.
 
 C   p   =C   p   −K   p  
 
 M   p   =M   p   −K   p  
 
 Y   p   =Y   p   −K   p .
 
     At this point, adjusted CMYK values have been produced for each dot. 
     In order to complete the CMYK to CMYKK p RGB conversion process, RGB values must be produced from each of the negative, positive, and excess dots. Performing these sub-conversions entails using the adjusted CMYK values for each dot in a manner as follows. 
     At  420 , the R n G n B n  for the negative dot is determined by:
 
 B   n =min( C   n   ,M   n )
 
 C   n   =C   n   −B   b  
 
 M   n   =M   n   −B   n  
 
 R   n =min( Y   n   ,M   n )
 
 Y   n   =Y   n   −R   n  
 
 M   n   =M   n   −R   n  
 
 G   n =min( C   n   ,Y   n )
 
 C   n   =C   n   −G   n  
 
 Y   n   =Y   n   −G   n .
 
     At  422 , the R e G e B e  for the excess dot is determined by:
 
 B   e =min( C   e   ,M   e )
 
 C   e   =C   e   −B   e  
 
 M   e   =M   e   −B   e  
 
 R   e =min( Y   e   ,M   e )
 
 Y   e   =Y   e   −R   e  
 
 M   e   =M   e   −R   e  
 
 G   e =min( C   e   , Y   e )
 
 C   e   =C   e   −G   e  
 
 Y   e   =Y   e   −G   e .
 
     At  424 , the R p G p B p  for the positive dot is determined by:
 
sum p   =C   p   +M   p   +Y   p  
 
 rgb =max(sum p −( S−K   P ),0)
 
 B   p   =rgb −min( Y   p   , rgb )
 
 C   p   =C   p   −B   p  
 
 M   p   =M   p   −B   p  
 
 rg=rgb−B   p  
 
 R   p   =rg −min( C   p   ,rg )
 
 G   p   =rg−R   p  
 
 C   p   =C   p   −G   p  
 
 M   p   =M   p   −R   p  
 
 Y   p   =Y   p   −R   p   G   p .
 
     The above-described sub-conversions performed for each dot produces a CMYK and a RGB for each dot. 
     At  426 , these values for each dot are combined to produce a CMYKK p RGB output. The combination is given by:
 
 C=C   p   +C   e   −C   n  
 
 M=M   p   +M   e   −M   n  
 
 Y=Y   p   +Y   e   −Y   n  
 
K=K i  
 
 K   p   =K   p   +K   e   −K   n  
 
 B=B   p   +B   e   −B   b  
 
 R=R   p   +R   e   −R   n  
 
 G=G   p   +G   e   −G   n .
 
     The CMYK to CMYKK p  RGB conversion  208  is now complete. 
     The CMYKK p RGB output generated as a result of this conversion is provided as input to the hierarchical thresholding module  210  of  FIG. 2 . Since processing proceeds with respect to the various elements already discussed with respect to the embodiment of  FIG. 2 , a repeat discussion has been omitted. 
     Results demonstrate that the present method effectively diffuses pixel error and provides a comparable high-quality halftone output result. The method is computationally efficient and thus can be implemented in a bit-constrained environment such as an ASIC or FPGA placed in the image path of a color marking device or color management system. In one embodiment, the ASIC or FPGA iteratively processes the received CMYK input values and generates a halftone output result in either 4-channel CMYK space or 8-channel CMYKK p RGB space depending on the color management system wherein the present pixel error diffusion method finds its implementation. 
     Reference is now made to  FIG. 5  which illustrates a block diagram of one example embodiment of a special purpose computer system useful for implementing one or more aspects of the present method. 
     Special purpose computer system  500  includes processor  506  for executing machine executable program instructions for performing one or more aspects of the present method. The processor is in communication with bus  502  (e.g., a backplane interface bus, cross-over bar, or data network) for receiving and sending data. The system includes main memory  504  for storing machine readable instructions. Main memory may comprise random access memory (RAM) to support reprogramming and flexible data storage. Buffer  566  stores data accessible by the processor. Program memory  564  stores program instructions. A display interface  508  forwards data from bus  502  to display  510 . Secondary memory  512  includes a hard disk  514  and storage device  516  for reading/writing to removable storage unit  518 , such as a floppy disk, magnetic tape, optical disk, etc. Secondary memory  512  further includes other mechanisms for allowing programs or other machine executable instructions to be loaded into the processor. Such mechanisms may include, for example, a storage unit  522  adapted to exchange data through interface  520 . Examples of such mechanisms include a program cartridge and cartridge interface, a removable memory chip (such as an EPROM, PROM, etc.) and any associated sockets. Interface  520  enables the transfer of software and data from the storage unit to the processor. System  500  includes a communications interface  524  to allow data to be transferred between the system and external devices such as a color scanner (not shown). Example interfaces include a modem, a network card such as an Ethernet card, a communications port, a PCMCIA slot and card, etc. Software and data transferred via the communications interface are in the form of signals. Such signal may be any of electronic, electromagnetic, optical, or other forms of signals capable of being received by the communications interface. These signals are provided to the communications interface via channel  526  which carries such signals and may be implemented using wire, cable, fiber optic, phone line, cellular link, RF, memory, or other means known in the arts. 
     Reference is now made to  FIG. 6  which is an explanatory diagram illustrating one example of a computer readable storage medium capable of storing machine readable instructions which, when mounted on a computer or a special purpose computer system, causes the system to perform one or more aspects of the present pixel error diffusion method as described herein in detail. The machine readable instructions may be modified by one computer and transferred to another computer. In the illustrated embodiment, computer programs  600  for carrying out the present method are loaded on a computer-readable storage media  602  which includes media such as optical disks (CD-ROM etc.), magnetic disks, magnetic cards, memories (including IC cards and memory card). The storage media stores the machine readable program instructions for sale, transport, and storage by changing magnetic, optical, and/or electric energy states or orientations in response to program instructions having been transferred to the media. The computer programs containing machine executable instructions of the present method can then be mounted on computer  604  and transferred or otherwise communicated to computer  606 . The program instructions can then be off-loaded to medium  608 , in original form or modified, including data, and stored on media  610 . The computer systems include processors or special purpose computers capable of executing machine readable program instructions for carrying out one or more aspects of the present method. 
     Terms such as, computer program medium, computer readable medium, computer executable medium, and computer usable medium are used herein to generally refer to a machine readable media such as main memory, secondary memory, removable storage device such as a hard disk, and communication signals. Such computer program products are means for carrying instructions and/or data to the computer system or device. Such computer program products may include non-volatile memory, such as a floppy disk, hard drive, memory, ROM, RAM, flash memory, disk memory, and other storage useful for transporting machine readable program instructions for executing the present method. It may further include a CD-ROM, DVD, tape, cassette, or other digital or analog media, capable of having embodied thereon one or more logical programming instructions or other machine executable codes or commands that implement and facilitate the function, capability, and methods disclosed herein. Computer readable medium may additionally comprise information in a transitory state medium such as a network link or a network interface which may include a wired network or a wireless network which allows a computer to read such computer readable information. 
     It should be understood that the flow diagram hereof are intended to be illustrative. Other operations, for example, may be added, modified, enhanced, condensed, integrated, or consolidated. Variations thereof are intended to fall within the scope of the appended claims. 
     It should also be understood that one or more aspects of the present method are intended to be incorporated in an article of manufacture, including one or more computer program products. The article of manufacture may be included on at least one storage device readable by a machine architecture, xerographic, color management, or other image processing system capable of executing program instructions. The article of manufacture may be included as part of a xerographic system, color management system, an operating system, a software program, a plug-in, and the like, as are known in the arts. Such an article of manufacture may further be shipped, sold, leased, or otherwise provided either alone or as part of an add-on, update, upgrade, or product suite by the assignee or a licensee hereof. 
     It will be appreciated that the above-disclosed features and functions and variations thereof may be desirably combined into many other different systems or applications. Various presently unforeseen or un-anticipated alternatives, modifications, variations, or improvements may become apparent and/or subsequently made by those skilled in the art which are also intended to be encompassed by the appended claims. The embodiments set forth above are considered to be illustrative and not limiting. Various changes to the above-described embodiments may be made without departing from the spirit and scope of the invention.