Methods and systems for descreening a digital image

Embodiments of the present invention comprise methods and systems for descreening a digital image.

FIELD OF THE INVENTION

Embodiments of the present invention comprise methods and systems for descreening digital images.

BACKGROUND

Many printed documents contain halftone images that are 1-bit images consisting of dot patterns on a contrasting background. Often the images are composed of black dots printed on light-colored media such as the newsprint of a newspaper. The human eye perceives a grayscale image from the 1-bit, halftone image. While halftone dot patterns reduce the bit-depth of a digital image and maintain the grayscale appearance to a viewer, the characteristics of the quantized image are considerably different than those of a continuous-tone or grayscale image.

When halftone images are scanned or otherwise transformed into digital images, it is often advantageous to process the image to enhance image characteristics or to compress the image to reduce the size of the image file for storage or transmission. Some image processing operations, such as filtering, decimation, interpolation, sharpening, and others, do not work well on halftone images. The high-frequency distribution of dots in halftone images precludes using many image processing methods that function well with grayscale images.

Halftone dot modulation can have deleterious effects when compressing, processing, or reprinting the scanned image. Because many grayscale image processing algorithms and compression methods do not perform well on halftone images, the halftone images must be transformed from halftone to grayscale. This process may be referred to as inverse halftoning or descreening.

Some existing methods for descreening may employ low-pass filtering. However, low-pass filtering that is sufficient to smooth the high-frequency patterns of halftone images will not preserve text and line art edges and other detailed content of the image. It is desirable to maintain edges corresponding to significant image structure. The goal of preservation of image structure precludes the use of simple smoothing techniques.

Accordingly, low-pass filtering methods typically result in grainy or blurred images.

Other existing methods may employ a neural network to transform an image from halftone to grayscale. These methods require training of the neural network and are typically not optimal over a range of halftone techniques. These methods generally do not take advantage of a priori constraints or the nature of the halftone mask, when it is known.

Some current descreening methods involve a wavelet representation that allows selection of useful information from each wavelet band. This may be performed by applying a nonorthogonal, overcomplete, wavelet transform to a halftone image. The high-pass wavelet images are dominated by halftoning blue noise, whose power increases with respect to frequency. Adaptive filtering must then be applied to segregate image detail from halftone modulation. These filters may be adaptive in both space and frequency bands.

Each of the above-described methods has drawbacks related to performance or complexity of the process. It would be advantageous to have a method of descreening that provides superior performance to the more simplistic filtering methods without the complexity of the neural network and wavelet methods.

SUMMARY

Embodiments of the present invention comprise systems and methods for descreening a digital image. These embodiments comprise methods and systems for removing or reducing halftone dot modulation from scanned, or otherwise digital, halftone image data.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

Embodiments of the present invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The figures listed above are expressly incorporated as part of this detailed description.

It will be readily understood that the components of the present invention, as generally described and illustrated in the figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the methods and systems of the present invention is not intended to limit the scope of the invention, but it is merely representative of the presently preferred embodiments of the invention.

Elements of embodiments of the present invention may be embodied in hardware, firmware and/or software. While exemplary embodiments revealed herein may only describe one of these forms, it is to be understood that one skilled in the art would be able to effectuate these elements in any of these forms while resting within the scope of the present invention.

Some embodiments of the present invention may be described with reference toFIG. 1. These embodiments may comprise a correction calculator16for generating a correction image12. A corrected image14of an original image10may be formed by combining the correction image12with an original image10.FIG. 1shows an additive combination of the correction image12and the original image10, which, when combined, form a corrected image14. Other embodiments may comprise non-additive combinations of the correction image12and the original image10. In some embodiments of the present invention, the input image10may be a halftone image and the corrected image14is a descreened version of the input image10.

In an exemplary embodiment, a smoothed image14is generated by subtracting a correction image12from an input image10. In some embodiments, the input image10may be a luminance image. A luminance image may comprise luminance channel data from a complete image comprising luminance and chrominance channel data. In other embodiments, input image10may comprise chrominance channel data or data from other image channels.

In some embodiments, the correction image12may be calculated by the correction calculator16based on characteristics of the input image10. The gradient of the input image10and the second derivative of the input image10may be the characteristics of the input image10from which the correction calculator16calculates the correction image12in some embodiments. In other embodiments, other input image characteristics may be used in correction image12calculations.

In some embodiments, the correction image12may be determined and applied on a pixel-by-pixel basis. In other embodiments, the correction calculator16may comprise an array processor, or other processing means, to produce the correction image12on a basis that does not require pixel-by-pixel calculations.

Some embodiments of the present invention may be described with reference toFIG. 2. In these embodiments, the value of a smoothed-image pixel24may be given by the difference between the value of the corresponding pixel20in the input image10(e.g., the pixel at the same spatial location) and a pixel-correction term22calculated for that pixel20by a pixel-correction calculator26. In other embodiments, the pixel-correction term22may be combined with the input image pixel value20by other methods.

Some embodiment of the present invention may be described with reference toFIG. 3. In these embodiments, a pixel-correction calculator26may use a pixel value of a pixel20in an input image10and the values of several neighboring pixels31-48in generating a pixel correction term22. In other embodiments, the support of the pixel-correction calculations may include other pixels and/or other image characteristics.

In some embodiments, image values at pixels20,31, and35, denoted v20, v31, and v35, respectively, may be used to approximate the second derivative of the input image10at the input-image pixel20in the vertical (or y) direction. Image values at pixels20,41, and45, denoted v20, v41, and v45, respectively, may be used to approximate the second derivative of the input image10at the input-image pixel20in the horizontal (or x) direction.

In some embodiments, approximation of the second derivative at the input-image pixel20in the x direction may be given by −v45+2v20−v41, denoted D2x.

In some embodiments, approximation of the second derivative at the input-image pixel20in the y direction may be given by −v31+2v20−v35, denoted D2y.

In other embodiments, the second derivative may be approximated using non-separable filters or by other methods.

In some embodiments, image values at pixels31-38, denoted v31, v32, v33, v34, v35, v36, v37, and v38, respectively, may be used to approximate the gradient of the input image10at the input-image pixel20in the vertical (or y) direction. Image values at pixels41-48, denoted v41, v42, v43, v44, v45, v46, v47, and v48may be approximate the gradient of the input image10at the input-image pixel20in the horizontal (or x) direction.

Approximation of the gradient at the input-image pixel20in the x direction may be given by

Approximation of the gradient at the input-image pixel20in the y direction may be given by

In other embodiments, the gradient may be approximated using non-separable filters or by other methods.

In some embodiments, the correction term22for the input-image pixel20may be given by

D⁢⁢2⁢xS⁢Gx+k+D⁢⁢2⁢yS⁢Gy+k,
where S=1 and k=5 in some embodiments.

In some embodiments, the pixel-correction calculator26may use the pixel value of a pixel20in the input image10and the values of several neighboring pixels, shown inFIG. 3. In some embodiments, if a neighboring pixel lies outside the image region, the value of the nearest pixel that is inside the image region may be used in place of the value of the neighboring pixel that is outside the image for calculation in the pixel-correction calculator26. Some embodiments of the present invention may correct only pixels for which all neighboring values required by the pixel-correction calculator26lie inside the image.

Some embodiments of the present invention comprise an iterative process in which, at each iteration, an iteration or input image is corrected based on characteristics of the iteration or input image. Some of these embodiments may be described with reference toFIG. 4. These embodiments of the present invention may comprise a correction calculator56for calculating a correction image52. These embodiments may further comprise a correction combiner53for combining a correction image52with an input image50or iteration image51. These embodiments may further comprise an iteration terminator60, for determining when iterations will terminate. These embodiments may further comprise an iteration image buffer68for storing a modified iteration image54and feeding the iteration image54back into the correction calculator56for another iteration.

In some embodiments, illustrated inFIG. 4, image combiner53performs an additive combination of the correction image52and the input image50or iteration image51. Other embodiments may comprise non-additive combinations of the correction image52and the input image50or iteration image51. In some embodiments of the present invention, the input image50is a halftone image at the first iteration and the updated image54is a descreened or partially-descreened version of the input image50.

In an exemplary embodiment, a modified image54is generated at each iteration by subtracting a correction image52from an input image50on the first iteration and by subtracting a correction image52from a modified iteration image54on subsequent iterations. After the modified image54is generated, an iteration termination condition may be checked at the iteration terminator60. If the iteration termination condition is not met62, the modified image54becomes the iteration image51used as input for the next iteration. The iterations may be terminated66when the iteration termination condition is met64.

The correction image52may be calculated by a correction calculator56based on characteristics of the input image50or iteration image51. In some embodiments, illustrated inFIG. 5, a correction image52may be determined on a pixel-by-pixel basis using a pixel-correction calculator76. In other embodiments, the correction calculator76may comprise array processors or other means to produce the correction image52on a basis not requiring pixel-by-pixel calculations.

In the exemplary embodiments shown inFIG. 5, the value of a modified image pixel74may be obtained by applying a correction to the corresponding pixel in the input image50or iteration image54that is being processed. In some embodiments, this correction may be accomplished by taking the difference between the value of the corresponding pixel70in the input image50or iteration image54(i.e., the pixel at the same spatial location) and a pixel-correction term72calculated for that pixel.

In some embodiments, the pixel-correction calculator76may use the pixel value of the pixel70in the input image50or iteration image54and the values of one or more neighboring pixels. In some embodiments, illustrated inFIG. 6, these neighboring pixels81-88and91-98are the adjacent pixel immediately above, below, to the right and to the left of the pixel being processed70. In other embodiments, the support of the pixel-correction calculations may include other pixels.

In some embodiments, image values at pixels70,81, and85, denoted v70, v81, and v85, respectively, may be used to approximate the second derivative of the iteration-input image50at the iteration-input-image pixel70in the vertical (or y) direction. Image values at pixels70,91, and95, denoted v70, v95, and v95, respectively, may be used to approximate the second derivative of the iteration-input image50at the iteration-input-image pixel70in the horizontal (or x) direction.

In some embodiments, approximation of the second derivative at the iteration-input-image pixel70in the x direction may be given by −v95+2v70−v91, denoted d2x.

In some embodiments, approximation of the second derivative at the iteration-input-image pixel70in the y direction may be given by −v81+2v70−v85, denoted d2y.

In other embodiments, the second derivative may be approximated using non-separable filters.

In some embodiments, image values at pixels81-88, denoted v81, v82, v83, v84, v85, v86, v87, and v88, respectively, may be used to approximate the gradient of the iteration-input image50at the iteration-input-image pixel70in the vertical (or y) direction. Image values at pixels91-98, denoted v91, v92, v93, v94, v95, v96, v97, and v98may be used to approximate the gradient of the iteration-input image50at the iteration-input-image pixel70in the horizontal (or x) direction.

In some embodiments, approximation of the gradient at the iteration-input-image pixel70in the x direction may be given by

In some embodiments, approximation of the gradient at the iteration-input-image pixel70in the y direction may be given by

In other embodiments, the gradient may be approximated using non-separable filters.

In some embodiments, the pixel-correction term72for the iteration-input-image pixel70is

d⁢⁢2⁢xS⁢gx+k+d⁢⁢2⁢yS⁢gy+k,
where S=1 and k=5 in some embodiments. In an exemplary embodiment, S is the same for each iteration, and k is the same for each iteration. In some embodiments, S may vary with iteration.

In an exemplary embodiment, the pixel-correction calculator76may use the pixel value of the pixel in the input image50or iteration image54and the values of one or more neighboring pixels, such as those shown inFIG. 6. In some embodiments, if a neighboring pixel lies outside the image region, the value of the nearest pixel that is inside the image region may be used in the pixel-correction calculator76. Some embodiments of the present invention may correct only pixels for which all neighboring values required by the pixel-correction calculator76lie inside the image.

In some embodiments of the present invention, a high-stop filter is used to smooth a digital image containing halftone regions. In some embodiments, the high-stop filter is applied iteratively, at the first iteration, to the original halftone image, and, at subsequent iterations, to the filtered image resulting from the previous iteration. In some embodiments, the gain of the high-stop filter may be modified spatially. This gain may also be scaled, in some embodiments, in inverse proportion to the local gradient estimation. For efficiency, in some embodiments, separable filters may be used to directionally measure gradients and high-frequency content. In some embodiments, further efficiencies may be realized by algebraic simplification and by the use of single channel gradient estimates.

In some embodiments of the present invention, the input image may comprise luminance channel data, chrominance channel data from one or more chrominance channels and other data. In other embodiments, data from a subset of all of an image's channels may be used. In some embodiments, the input image may comprise the data of the luminance channel of the image. In some embodiments, a brightness channel of an image may be used as an input image. Some embodiments of the present invention comprise an iterative process which iterates on multiple channels of the image data.

Some embodiments of the present invention comprise a process in which the data in an input image is corrected based on characteristics of the image data. Characteristics of the image data may comprise the second derivative and the gradient of the image data, in some embodiments. An exemplary embodiment of this process is illustrated inFIG. 7.

In the embodiments illustrated inFIG. 7, a correction image112is calculated by a correction calculator115. This exemplary correction calculator115calculates a correction image112from the second derivative111of the input image110and from the adjusted image-gradient magnitude113. A corrected image114may be derived from the correction image112and the input image110.

In these embodiments, the correction calculator115comprises an image gradient calculator120for calculating an image gradient. In some embodiments the image gradient calculator may calculate the image gradient in multiple directions. These embodiments may also comprise an image gradient magnitude calculator122, which, in some embodiments, may calculate an image gradient magnitude in multiple directions. These embodiments may further comprise an image gradient magnitude adjuster124for adjusting image gradient magnitudes, which, in some embodiments may adjust image gradient magnitudes by a scaling factor or an offset. These embodiments may also comprise a second derivative calculator126for calculating the second derivative of an image at one or more pixel locations and in one or more directions. These calculators120,122,124and126provide input to the correction value calculator128, which processes the output from the calculators120,122,124and126and calculates a correction image112. The correction image112may then be combined with the input image110to produce a corrected image114.

In some embodiments, modification of the image may be based on characteristics of the image in multiple directions. In some embodiments two directions may be used. In some embodiments, the two directions may be the horizontal and vertical directions in the image.

Some embodiments of the present invention comprise producing a modified version of the image by subtracting from an iteration or input version of the image a correction signal proportional to the second derivative of the iteration or input image. In some embodiments, the correction signal may be scaled in inverse proportion to the magnitude of an estimate of the iteration or input image gradient. The iterated version of the image becomes the “input” image or iteration image for the next iteration which, is in turn modified and used as input for the next iteration.

Some embodiments of the present invention may terminate after one iteration or a fixed number of iterations. Some embodiments may terminate the iterative process after a termination criterion is met. In some embodiments of the present invention, the termination criterion may comprise an image quality metric measured on the iterated version of the image. In some embodiments of the present invention, the termination criterion may comprise a metric measured in relation to the change between the iteration-input image and the iterated version of the image.

In some embodiments of the present invention, the termination criterion may comprise a metric measured between multiple channels of image data. In some embodiments of the present invention the termination criterion may comprise a metric measured in relation to the change between the present channel data and the next channel data for a multiplicity of data channels.

In some embodiments of the present invention, the second derivative may be approximated directionally using the convolution kernel [−1 2 −1] in each direction used in calculating the correction signal. In some embodiments of the present invention, the second derivative may be approximated using a kernel that is not separable.

In some embodiments of the present invention, the gradient may be approximated directionally using the convolution kernel [−1 −6 −14 −14 0 14 14 6 1]. In some embodiments, the gradient approximation may be scaled for normalization. In some embodiments of the present invention, the gradient may be approximated using a kernel that is not separable.