Hybrid halftone generation mechanism using change in pixel error

A method is disclosed. The method includes generating a Continuous Tone Image (CTI) with all pixel values same as a first gray level, generating an initial Half Tone Image (HTI) with all pixel values equal to minimum absorptance level and computing a change in pixel error for a first pixel. The change in pixel error is computed by identifying a first pixel indicated in a valid pixel map, toggling the first pixel with all the possible output states and swapping the first pixel 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.

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 binary screening method employs a 3D Look-Up table (LUT) replicated to the size of printable area containing the binary output values for every PEL of the array and for every gray level of the device. These replicated LUTs are indexed by the Continuous Tone Image (CTI) data to determine which PELs are ON or OFF. A 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.

Conventional digital halftoning techniques are designed as a function of either the dot size (amplitude modulation (AM)) or the dot density (frequency modulation (FM)). Generally, AM halftoning methods have the advantage of low computation and good print stability for electro photographic printers, while FM halftoning methods typically have higher spatial resolution and resistance to moiré artifacts and are used in inkjet printers.

New classes of AM/FM (e.g., hybrid) halftoning algorithms exist that simultaneously modulate the dot size and density. The major advantages of hybrid halftoning are stable as AM halftones, moiré resistance as FM methods through irregular dot placement, and improved quality through systematic optimization of the dot size and dot density at each gray level.

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 3D LUT approach can be extended to represent multibit drop sizes or exposure values by using these values in the LUT instead of binary values.

The planes of the 3D Look-Up Table (LUT) form a 3D array having planes representing the halftone patterns for 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.

Accordingly, an algorithm to efficiently generate multi-bit hybrid halftone screens 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 a first gray level, generating an initial Half Tone Image (HTI) with all pixel values equal to minimum absorptance level and computing a change in pixel error for a first pixel. The change in pixel error is computed by identifying a first pixel indicated in a valid pixel map, toggling the first pixel with all the possible output states and swapping the first pixel with all neighbor pixels indicated in a valid pixel map 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.

In a further embodiment, a system is disclosed. The system includes a processor to generate a Continuous Tone Image (CTI) with all pixel values same as a first gray level, generate an initial Half Tone Image (HTI) with all pixel values equal to minimum absorptance level and compute a change in pixel error for a first pixel by identifying a first pixel indicated in a valid pixel map, toggling the first pixel with all the possible output states and swapping the first pixel with all neighbor pixels indicated in a valid pixel map 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.

DETAILED DESCRIPTION

FIG. 1is a block diagram illustrating a printing network100. Network100includes a host system110in communication with a printing system130to print a sheet image120onto a print medium180(e.g., paper) via a printer160. The resulting print medium180may be printed in color and/or in any of a number of gray shades, including black and white.

The host system110may 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 image120may be any file or data that describes how an image on a sheet of print medium should be printed. For example, the sheet image120may include PostScript data, Printer Command Language (PCL) data, and/or any other printer language data. The print controller140processes the sheet image to generate a bitmap150for printing to the print medium180via the printer160.

The printing system130may be a high-speed printer operable to print relatively high volumes (e.g., greater than 100 pages per minute). The print medium180may be continuous form paper, cut sheet paper, and/or any other tangible medium suitable for printing. In one embodiment, the printing system130includes the printer160that presents the bitmap150onto the print medium180(e.g., via toner, ink, etc.) based on the sheet image120.

The print controller140may be any system, device, software, circuitry and/or other suitable component operable to transform the sheet image120for generating the bitmap150in accordance with printing onto the print medium180.FIG. 2is a block diagram illustrating an exemplary print controller140.

Referring toFIG. 2, the print controller140, in its generalized form, includes an interpreter module212and a halftoning module214. In one embodiment, these separate components represent hardware used to implement the print controller140. Alternatively or additionally, the components may represent logical blocks implemented by executing software instructions in a processor of the printer controller140. Accordingly, the invention is not intended to be limited to any particular implementation as such may be a matter of design choice.

The two-dimensional pixel arrays are considered “full” sheetside bitmaps because the bitmaps include the entire set of pixels for the image. The interpreter module212is 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 module214is 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 module214may convert the continuous tone sheetside bitmaps to a pattern of ink drops for application to the print medium180(e.g., paper). Once computed, the halftoning module214transfers the converted sheetside bitmaps to the print head controllers of the printer160to apply the ink drop(s) to the tangible medium180.

According to one embodiment, halftoning module214performs 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 suitable filter and selects from among multiple drop sizes that printer160is capable of applying to the tangible medium180. In a further embodiment, the DMSSA screen is generated at host system100or another host system in printing network100. However, the mask may be generated at a third party computer system and transferred to printing network100.

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 filter 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)|2dxdy, 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Σng[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 ε=<{tilde over (e)},{tilde over (e)}>, where <·,·> 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,ne[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<Δ{tilde over (e)},{tilde over (e)}>+<Δ{tilde over (e)},Δ{tilde over (e)}>, assuming all signals are real-values. Either a toggle at pixel (m0,n0) or a swap between pixels (m0,n0) and (m1,n1) can be represented as g′[m,n]=g[m,n]+Σiaiδ[m−mi, n−ni]. As a result,
Δ{tilde over (e)}(x,y)=Σiai{tilde over (p)}(x−miX,y−niX), and
Δε=2Σic{tilde over (p)}{tilde over (e)}[mi,ni]+Σi,jaiajc{tilde over (p)}{tilde over (p)}[mi−mj,ni−nj], where
c{tilde over (p)}{tilde over (e)}[m,n]=<{tilde over (p)}(x,y),{tilde over (e)}(x+mX,y+nX)>, and
c{tilde over (p)}{tilde over (p)}[m,n]=<{tilde over (p)}(x,y),{tilde over (p)}(x+mX,y+nX)>.

According to one embodiment, a model based on mixed Gaussian functions whose functional form is used: c{tilde over (p)}{tilde over (p)}[u, v]=k1exp(−(u2+v2)/2σ12)+k2exp(−(u2+v2)/2σ22), where k1; k2; σ1; σ2are constant values based on empirical analysis to yield desired results. Assuming that c{tilde over (p)}{tilde over (p)}symmetric, then: Δε=2(Σic{tilde over (p)}{tilde over (e)}[mi, ni]+Σi<jaiajc{tilde over (p)}{tilde over (p)}[mi−mj,ni−nj])+Σiai2c{tilde over (p)}{tilde over (p)}[0,0].

Assuming that a given printer can produce S possible output states/drops with absorptance levels α1, α2, . . . , αSat every PEL location. Then, airepresents the amount of change in the gray level for toggle as: ai=gnew[mi, ni]−gold[mi, ni]. A swap between pixels i and j is equivalent to two toggles with gnew[mj, nj]=gold[mi, ni] and gnew[mi, ni]=gold[mj, nj]. Thus, the amount of change in the gray level for swap is represented as ai=gold[mj, nj]−gold[mi, ni] and aj=gold[mi, ni]−gold[mj, nj]. Then aj=−aiexcept for j=0 (e.g., toggle, a0=0).

FIG. 3is a flow diagram illustrating one embodiment of a multi-bit screening process using the DMSSA based on aiand aj. At processing block310, 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 block320, 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 g0-initial(m,n)=0). At processing block330, the auto-correlation function c{tilde over (p)}{tilde over (p)}[m,n] is computed. At processing block340, pixel error processing is performed.

FIG. 4is a flow diagram illustrating one embodiment of performing pixel error processing. At processing block410, the initial error c{tilde over (p)}{tilde over (e)}[m,n] between fη(m,n) and gη-initial(m,n) is computed. At processing block420, a change in c{tilde over (p)}{tilde over (e)}[m,n] is computed for a pixel. The change in c{tilde over (p)}{tilde over (e)}[m,n] is computed by toggling pixel gη-initial(m,n) with all the possible output states as and swapping pixel gη-initial(m,n) with all of the neighbors. In another embodiment, only a subset of absorptance levels is used during the toggle operation.

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 block430, 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 block440, c{tilde over (p)}{tilde over (e)}[m,n] and gη-initial(m,n) are updated reflecting the accepted change: c{tilde over (p)}{tilde over (e)}[m,n]′=c{tilde over (p)}{tilde over (e)}[m,n]+aic{tilde over (p)}{tilde over (p)}[m−mi,n−ni]. At decision block450, 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 blocks420-440, described above.

However, if no more pixels need to be processed, it is determined whether an end criteria has been met, decision block460. In one embodiment, the criteria have been met when no significant decrease in error is observed. At processing block470, the gray level gη-initialis saved as the final halftone (gη) for gray level η. At processing block480, 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 toFIG. 3, an average minimum Euclidean distance between all non connected ON pixels is calculated, once the pixel error processing has been performed, processing block350. It should be understood that ON pixel refers to any isolated or group of connected non zero absorptance level pixels. In one embodiment, a Euclidean distance is measured between two pixel locations.FIG. 5illustrates one embodiment of an image having a center pixel being ON, and the corresponding Euclidean distance map.

In a further embodiment, the distance map may be represented by a neighborhood map that categorizes the neighbors into face neighbors and corner connected neighbors.FIG. 6illustrates one embodiment of a neighborhood map. Referring back toFIG. 5, the distance map shows a distance of 1 between the centroid and the face neighbors, and 1.4 between the centroid and the corner neighbors.

Referring back toFIG. 3, it is determined, after calculating the average Euclidean distance, whether an average minimum distance between ON pixels reaches (e.g., less than or equal) a user defined minimum (Dmin), decision block360. If the minimum distance has not reached Dmin, it is determined whether there are one or more additional gray levels to process, decision block370.

If there are additional gray levels to process, control is returned to processing block310where the next gray level is processed. When the next gray level is selected at decision block, the CTI is updated to fη+1(m,n)=η+1 at block310, and the initial HTI gη+1-initial=gηat block320and processed through pixel error processing block340, as discussed above.

However if at decision block360, it is determined that the minimum distance has reached Dmin, the current gray level screen is stored as a seed pattern, processing block380.FIG. 7Aillustrates one embodiment of a gray level screen stored as a seed pattern. Once the seed pattern is stored, the front facing neighbor locations for every centroid in the seed pattern are identified.

At processing block390, the front facing neighbor locations, along with the centroid locations, are passed to a valid pixel location map. In one embodiment, the valid pixel location map provides location information for subsequent pixel error processing for the PELS at which the process can perform toggle or swap operations. In another embodiment only a subset of all of the valid pixel locations is used. In a further embodiment, the valid pixel location map is the same size as the halftone mask.FIG. 7Billustrates one embodiment of a seed pattern with nearest neighbors identified.FIG. 8Aillustrates one embodiment of the corresponding valid pixel location map.

Once the valid pixel location map has been established, control is passed back to decision block370, where it is again determined whether there are additional gray levels to process. If there are additional gray levels to process, control is returned to processing block310where the next gray level is processed. When the next gray level is selected, the CTI and HTI are again updated and processed through pixel error processing block340.

However, during pixel error processing for each subsequent gray level, the toggle and swap operations are performed only at pixel locations indicated in the valid pixel location map. In one embodiment, toggle and swap operations are performed for the front facing neighbors of a centroid for each gray level.

In one embodiment, the mean squared perceived error ε is calculated for a screen at each gray level. If at decision block360, it is determined that the minimum distance has reached Dminand if the difference between ε values for two consecutive gray level screens is less that a pre-defined threshold, then new neighbors for every ON pixel are identified. These new locations are passed to the valid pixel location map.FIG. 7Cillustrates one embodiment of a seed pattern after several gray levels, whileFIG. 8Acontinues to illustrate the corresponding valid pixel location map. Further,FIG. 7Dillustrates one embodiment of a seed pattern including only face neighbors, whileFIG. 8Billustrates the corresponding valid pixel location map.

Referring back toFIG. 3, 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, processing block395. In one embodiment, the halftone LUT is constructed from the resulting DMSSA patterns for each gray level.

FIG. 9illustrates a computer system900on which print controller140and/or host system110may be implemented. Computer system900includes a system bus920for communicating information, and a processor910coupled to bus920for processing information.

Computer system900further comprises a random access memory (RAM) or other dynamic storage device925(referred to herein as main memory), coupled to bus920for storing information and instructions to be executed by processor910. Main memory925also may be used for storing temporary variables or other intermediate information during execution of instructions by processor910. Computer system900also may include a read only memory (ROM) and or other static storage device926coupled to bus920for storing static information and instructions used by processor910.

A data storage device925such as a magnetic disk or optical disc and its corresponding drive may also be coupled to computer system900for storing information and instructions. Computer system900can also be coupled to a second I/O bus950via an I/O interface930. A plurality of I/O devices may be coupled to I/O bus950, including a display device924, an input device (e.g., an alphanumeric input device923and or a cursor control device922). The communication device921is for accessing other computers (servers or clients). The communication device921may 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.