Abstract:
A method is disclosed. The method includes generating a Continuous Tone Image (CTI) with all pixel values same as the first gray level and an initial Half Tone Image (HTI) with all pixel values equal to minimum absorptance level, computing a change in pixel error by toggling with all the possible output states and swapping with all neighbor pixels only if the stacking constraint is satisfied, updating the HTI with the maximum error decrease operation and continue to next pixel location till the end criteria is met. Once the end criteria is met, the updated HTI is saved as a final halftone screen for that gray level and copied as the initial HTI for the next gray level along with CTI pixel values updated to the next gray level till the final gray value is reached.

Description:
FIELD OF THE INVENTION 
     The invention relates to the field of image reproduction, and in particular, to digital halftoning. 
     BACKGROUND 
     Digital halftoning is a technique for displaying a picture on a two-dimensional medium, in which small dots and a limited number of colors are used. The picture appears to consist of many colors when viewed from a proper distance. For example, a picture consisting of black and white dots can appear to display various gray levels. Digital printers, which were initially pure black and white machines with a very coarse resolution, have evolved to accommodate colors, finer resolutions, and more recently, more than one bit of information per pixel (referred to as “multi-bit” or “multi-tone”). 
     Screening is a type of halftoning method used commonly in practical implementations. A common binary screening method employs a matrix of thresholds replicated to the size of printable area. These replicated matrices are compared to the Continuous Tone Image (CTI) to determine which PELs are ON or OFF. The print controller receives a CTI, such as a digital picture, from a host. The print controller then uses the screening algorithm to process the CTI and convert the image into an array of pixels. The result of the screening algorithm is a bitmap where each pixel may be ON or OFF which is referred to as a Half-Tone Image (HTI). The print controller then sends the HTI to a print engine for printing. 
     With the prevalence of devices having multi-bit capability there is a potential to improve overall image quality of print jobs using multi-bit halftoning. Multi-bit screening enables a selection among multiple drop sizes or exposure levels at each addressable pixel. The multi-bit screen consists of array of thresholds for every drop size or exposure level. Another way of representing this screen is a Look-Up Table (LUT) which is a 3D array having planes representing each darker gray level, ranging from the pattern for gray level zero through the maximum gray level of the halftone mask. The maximum gray level is used to produce a solid, where all of the pixels are printed at the maximum output state. 
     Several single bit halftone screen algorithms are available that may be extended to multi-bit applications in order to produce high quality halftone images. For example, the article “Multilevel Screen Design Using Direct Binary Search,” (G. Lin and J. P. Allebach) Journal of the Optical Society of America, A19, 1969-1982 (2002) demonstrate the extension of single bit screening algorithm to multi-bit using DBS with the help of schedulers. However, these algorithms require many parameters to guide through the multi-bit screen creation. 
     Accordingly, an algorithm to efficiently create multi-bit halftone screen is desired. 
     SUMMARY 
     In one embodiment, a method is disclosed. The method includes generating a Continuous Tone Image (CTI) with all pixel values same as the first gray level and an initial Half Tone Image (HTI) with all pixel values equal to minimum absorptance level, computing a change in pixel error by toggling with all the possible output states and swapping with all neighbor pixels only if the stacking constraint is satisfied, updating the HTI with the maximum error decrease operation and continue to next pixel location till the end criteria are met. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       A better understanding of the present invention can be obtained from the following detailed description in conjunction with the following drawings, in which: 
         FIG. 1  illustrates one embodiment of a printing network; 
         FIG. 2  illustrates one embodiment of a print controller; 
         FIG. 3  is a flow diagram illustrating one embodiment of a multi-bit screening process; 
         FIG. 4  is a flow diagram illustrating a further of embodiment of a multi-bit screening process; 
         FIG. 5  illustrates one embodiment of a ramp halftone; 
         FIG. 6  illustrates one embodiment of calculated fraction of drop sizes in a multi-bit mask; and 
         FIG. 7  illustrates one embodiment of a computer system. 
     
    
    
     DETAILED DESCRIPTION 
     A direct multi-bit search screen mechanism is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and devices are shown in block diagram form to avoid obscuring the underlying principles of the present invention. 
     Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment. 
       FIG. 1  is a block diagram illustrating a printing network  100 . Network  100  includes a host system  110  in communication with a printing system  130  to print a sheet image  120  onto a print medium  180  (e.g., paper) via a printer  160 . The resulting print medium  180  may be printed in color and/or in any of a number of gray shades, including black and white. 
     The host system  110  may include any computing device, such as a personal computer, a server, or even a digital imaging device, such as a digital camera or a scanner. The sheet image  120  may be any file or data that describes how an image on a sheet of print medium should be printed. For example, the sheet image  120  may include PostScript data, Printer Command Language (PCL) data, and/or any other printer language data. The print controller  140  processes the sheet image to generate a bitmap  150  for printing to the print medium  180  via the printer  160 . 
     The printing system  130  may be a high-speed printer operable to print relatively high volumes (e.g., greater than 100 pages per minute). The print medium  180  may be continuous form paper, cut sheet paper, and/or any other tangible medium suitable for printing. In one embodiment, the printing system  130  includes the printer  160  that presents the bitmap  150  onto the print medium  180  (e.g., via toner, ink, etc.) based on the sheet image  120 . 
     The print controller  140  may be any system, device, software, circuitry and/or other suitable component operable to transform the sheet image  120  for generating the bitmap  150  in accordance with printing onto the print medium  180 .  FIG. 2  is a block diagram illustrating an exemplary print controller  140 . 
     Referring to  FIG. 2 , the print controller  140 , in its generalized form, includes an interpreter module  212  and a halftoning module  214 . In one embodiment, these separate components represent hardware used to implement the print controller  102 . Alternatively or additionally, the components may represent logical blocks implemented by executing software instructions in a processor of the printer controller  140 . Accordingly, the invention is not intended to be limited to any particular implementation as such may be a matter of design choice. 
     The interpreter module  212  is operable to interpret, render, rasterize, or otherwise convert images (i.e., raw sheetside images such as sheet image  120 ) of a print job into sheetside bitmaps. The sheetside bitmaps generated by the interpreter module  212  are each a two-dimensional array of pixels representing an image of the print job e.g., a continuous tone image (CTI), also referred to as full sheetside bitmaps. 
     The two-dimensional pixel arrays are considered “full” sheetside bitmaps because the bitmaps include the entire set of pixels for the image. The interpreter module  212  is operable to interpret or render multiple raw sheetsides concurrently so that the rate of rendering substantially matches the rate of imaging of production print engines. 
     Halftoning module  214  is operable to represent the sheetside bitmaps as patterns of ink drops or other dots, having one or more different drop of dot sizes. For example, the halftoning module  214  may convert the continuous tone sheetside bitmaps to a pattern of ink drops for application to the print medium  180  (e.g., paper). Once computed, the halftoning module  214  transfers the converted sheetside bitmaps to the print head controllers of the printer  160  to apply the ink drop(s) to the tangible medium  180 . 
     According to one embodiment, halftoning module  214  performs halftoning using a screen generated via a Direct Multi-bit Search Screen Algorithm (DMSSA). In such an embodiment, the DMSSA optimizes a halftone pattern at each gray level using a Human Visual System or other suitable filter and selects from among multiple drop sizes that printer  160  is capable of applying to the tangible medium  180 . In a further embodiment, the DMSSA screen is generated at host system  100  or another host system in printing network  100 . However, the mask may be generated at a third party computer system and transferred to printing network  100 . 
     In one embodiment, the DMSSA is based on the Direct Multi-bit Search (DMS) algorithm which is an extension to Direct Binary Search (DBS) algorithm. The DMS algorithm is an iterative/recursive search heuristic that uses a perceptual filter, such as a HVS model, to minimize the perceived error difference (ε), between a continuous tone image (CTI) and its corresponding rendered halftone image (HTI). This error is represented as: 
     ε=|h(x,y)**g(x,y)−h(x,y)**f(x,y)| 2  dxdy, where ** denotes 2-dimensional convolution, h(x,y) represents the point spread function (PSF) of the human visual system or other suitable filtering function, f(x,y) is the continuous tone original image and g(x,y) is the halftone image corresponding to the original image, where all image values are assumed to lie between 0 (white) and 1 (black). 
     The halftone image g(x,y) itself incorporates a printer model. g(x,y)=Σ m Σ n g[m,n]p(x−mX,y−nX), which represents the combination of the digital halftone image g[m,n] with a spot profile p(x,y) having device PEL spacing X, where X is the inverse of the printer addressability DPI. Superposition is assumed in this model for the interaction between overlapping spots. The digital halftone image g[m,n] can have any absorptance value between 0 (white) and 1 (black). 
     DMS is a computationally expensive algorithm that requires several passes through the halftone image (HTI) before converging to the final HTI. The DMS algorithm starts by generating an initial halftone image, then a local improvement to the halftone image is produced by swapping and toggling, ultimately resulting in an optimized halftone image by selecting the most appropriate swaps and toggles. Where swapping is the operation of switching the absorptance values of nearby pixels and toggling is the operation of changing the absorptance value of individual pixels. 
     The cost function may be represented as ε=&lt;{tilde over (e)}, {tilde over (e)}&gt;, where &lt;.,.&gt; denotes the inner product and {tilde over (e)}(x,y)=h(x,y)*(g(x,y)−f(x,y)) represents the perceptually filtered error. In such an embodiment, the CTI f(x,y) may also be expressed in terms of its samples f[m,n] where (m,n) are coordinate on the halftone array or printer grid. Thus, the perceived error is given by {tilde over (e)}(x,y)=Σ m,n e[m,n]p(x−mX,y−nX), where e[m,n]=g[m,n]−f[m,n], and {tilde over (p)}(x,y)=h(x,y)**p(x,y) is the perceived printer spot profile. 
     Considering the effect of a trial change. The new error will be {tilde over (e)}′={tilde over (e)}+Δ{tilde over (e)}. Substituting this and expanding the inner product results in ε′=ε+2&lt;Δ{tilde over (e)},{tilde over (e)}&gt;+&lt;Δ{tilde over (e)},Δ{tilde over (e)}&gt;, assuming all signals are real-values. Either a toggle at pixel (m 0 ,n 0 ) or a swap between pixels (m 0 ,n 0 ) and (m 1 ,n 1 ) can be represented as g′[m,n]=g[m,n]+Σ i a i δ[m−m i ,n−n i ]. As a result,
 
 Δ{tilde over (e)} ( x,y )=Σ i   a   i   {tilde over (p)} ( x−m   i   X,y−n   i   X ), and
 
Δε=2Σ i   c               [m   i   ,n   i ]+Σ i,j   a   i   a   j   c             [m   i   −m   j   ,n   i   −n   j ], where
 
 c             [m,n]=&lt;{tilde over (p)} ( x,y ), {tilde over (e)} ( x+mX,y+nX )&gt;, and
 
 c             [m,n]=&lt;{tilde over (p)} ( x,y ), {tilde over (p)} ( x+mX,y+nX )&gt;.

     According to one embodiment, a richer class of HVS model is implemented that yields enhanced halftoning results. This model is based on mixed Gaussian functions whose functional form is: 
     c           [u, v]=k 1 exp(−(u 2 +v 2 )/2σ 1   2 )+k 2 exp(−(u 2 +v 2 )/2σ 2   2 ), where the constants k 1 ; k 2 ; σ 1 ; σ 2  are the values 43.2, 38.7, 0.02, 0.06 respectively. Assuming that c          is symmetric, then:
 
Δε=2(Σ i   c             [m   i   ,n   i ]+Σ i&lt;j   a   i   a   j   c             [m   i   −m   j   ,n   i   −n   j ])+Σ i   a   i   2   c           [0,0].

     Assuming that a given printer can produce S possible output states/drops with absorptance levels α 1 , α 2 , . . . , α s  at every PEL location. Then, a i  represents the amount of change in the gray level for toggle as: a i =g new  [m i , n i ]−g old [m i , n i ]. A swap between pixels i and j is equivalent to two toggles with g new [m j , n j ]=g old [m i , n i ] and g new [m i , n i ]=g old [m j , n j ]. Thus, the amount of change in the gray level for swap is represented as a i =g old [m j , n j ]−g old [m i , n i ] and a j =g old [m i , n i ]−g old [m j , n j ]. Then a j =−a i  except for j=0 (e.g., toggle, a 0 =0). 
       FIG. 3  is a flow diagram illustrating one embodiment of a multi-bit screening process using the DMSSA based on a i  and a j . At processing block  310 , a CTI is generated of size N×N with f η (m,n)=η, where η is the gray level=0, 1           , 2         , . . . ,                    . Assuming an eight bit screen design,          would be equal to 255. At processing block  320 , an initial halftone image is generated for gray level 0 with all pixel values set to minimum absorptance level i.e. α 1  (e.g., g of size N×N with g 0-initial (m,n)=0). At processing block  330 , the auto-correlation function c         [m,n] is computed. At processing block  340 , pixel error processing is performed.
       FIG. 4  is a flow diagram illustrating one embodiment of performing pixel error processing. At processing block  410 , the initial error c           [m,n] between f η (m,n) and g η-initial (m,n) is computed. At processing block  420 , a change in c         [m,n] is computed for a pixel. The change in c         [m,n] is computed by toggling pixel g η-initial (m,n) with all the possible output states αs and swapping pixel g η-initial (m,n) with all of the neighbors.
     In one embodiment, both toggle and swap operations are performed only at locations that satisfy the stacking constraint. In such an embodiment, the stacking constraint specifies that output states for each pixel of the array are the same or higher relative to the output states for the halftone patterns for gray levels lower than the current levels. Output states increase until they reach the maximum output state, at which time they remain the same for all higher gray levels. 
     At processing block  430 , the operation with maximum error decrease in Δε is found for that pixel location. If there is no change in the error, then the next pixel is processed. At processing block  440 , c           [m,n] and g η-initial (m,n) are updated reflecting the accepted change: c         [m,n]′=c         [m,n]+a i c         [m−m i ,n−n i ]. At decision block  450 , it is determined whether there are one or more additional pixels to process. If additional pixels are to be processed, the next pixel is processed according to processing blocks  420 - 440 , described above.
     However, if no more pixels need to be processed, it is determined whether an end criteria has been met, decision block  460 . In one embodiment, the criteria have been met when no significant decrease in error is observed. At processing block  470 , the gray level g η-initial  is saved as the final halftone (g η ) for gray level η. At processing block  480 , the saved halftone (g η ) is copied so that it can be used as initial halftone image for the next gray level (e.g., g η+1-initial ). 
     Referring back to  FIG. 3 , it is determined, once the pixel error processing has been performed for all pixels of the gray level, whether there are one or more additional gray levels to process, decision block  350 . If there are additional gray levels to process, control is returned to processing block  340  where the next gray level is processed. 
     When the next gray level is selected at decision block  350 , the CTI is updated to f n+1 (m,n)=η+1 at block  310 , and the initial HTI g η+1-initial =g η  at block  320  and processed through pixel error processing block  340 . 
     If no additional gray tones are available to process, a multi-bit halftone screen or LUT is created that includes values generated from the DMSSA algorithm. The halftone LUT is constructed from the resulting DMSSA patterns for each gray level. 
       FIG. 5  illustrates one embodiment of a ramp halftoned using the DMSSA, while  FIG. 6  illustrates one embodiment of the calculated fraction of drop sizes in a multi-bit mask created using the DMSSA with 0, 1/3, 2/3 and 1 absorptance values. 
       FIG. 7  illustrates a computer system  700  on which print controller  140  and/or host system  110  may be implemented. Computer system  700  includes a system bus  720  for communicating information, and a processor  710  coupled to bus  720  for processing information. 
     Computer system  700  further comprises a random access memory (RAM) or other dynamic storage device  725  (referred to herein as main memory), coupled to bus  720  for storing information and instructions to be executed by processor  710 . Main memory  725  also may be used for storing temporary variables or other intermediate information during execution of instructions by processor  710 . Computer system  700  also may include a read only memory (ROM) and or other static storage device  726  coupled to bus  720  for storing static information and instructions used by processor  710 . 
     A data storage device  725  such as a magnetic disk or optical disc and its corresponding drive may also be coupled to computer system  700  for storing information and instructions. Computer system  700  can also be coupled to a second I/O bus  750  via an I/O interface  730 . A plurality of I/O devices may be coupled to I/O bus  750 , including a display device  724 , an input device (e.g., an alphanumeric input device  723  and or a cursor control device  722 ). The communication device  721  is for accessing other computers (servers or clients). The communication device  721  may comprise a modem, a network interface card, or other well-known interface device, such as those used for coupling to Ethernet, token ring, or other types of networks. 
     Embodiments of the invention may include various steps as set forth above. The steps may be embodied in machine-executable instructions. The instructions can be used to cause a general-purpose or special-purpose processor to perform certain steps. Alternatively, these steps may be performed by specific hardware components that contain hardwired logic for performing the steps, or by any combination of programmed computer components and custom hardware components. 
     Elements of the present invention may also be provided as a machine-readable medium for storing the machine-executable instructions. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, propagation media or other type of media/machine-readable medium suitable for storing electronic instructions. For example, the present invention may be downloaded as a computer program which may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection). 
     Whereas many alterations and modifications of the present invention will no doubt become apparent to a person of ordinary skill in the art after having read the foregoing description, it is to be understood that any particular embodiment shown and described by way of illustration is in no way intended to be considered limiting. Therefore, references to details of various embodiments are not intended to limit the scope of the claims, which in themselves recite only those features regarded as essential to the invention.