Patent Publication Number: US-7595911-B2

Title: Methods and systems for descreening a digital image

Description:
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. 
   The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention taken in conjunction with the accompanying drawings. 

   
     BRIEF DESCRIPTION OF THE SEVERAL DRAWINGS 
       FIG. 1  is a diagram showing an exemplary embodiment of the present invention comprising a correction calculator; 
       FIG. 2  is a diagram showing an exemplary embodiment of the present invention comprising a pixel-correction calculator; 
       FIG. 3  is a diagram showing, for an exemplary embodiment of the present invention, the image pixels used in calculating the correction value for a pixel; 
       FIG. 4  is a diagram showing an exemplary embodiment of the present invention comprising an iterative process; 
       FIG. 5  is a diagram showing an exemplary embodiment of the present invention comprising a pixel-correction calculator; 
       FIG. 6  is a diagram showing, for an exemplary embodiment of the present invention, the image pixels used in calculating the correction value for a pixel for an iteration; and 
       FIG. 7  is a flow diagram showing an exemplary embodiment of the present invention comprising a correction calculator and an image corrector. 
   

   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 to  FIG. 1 . These embodiments may comprise a correction calculator  16  for generating a correction image  12 . A corrected image  14  of an original image  10  may be formed by combining the correction image  12  with an original image  10 .  FIG. 1  shows an additive combination of the correction image  12  and the original image  10 , which, when combined, form a corrected image  14 . Other embodiments may comprise non-additive combinations of the correction image  12  and the original image  10 . In some embodiments of the present invention, the input image  10  may be a halftone image and the corrected image  14  is a descreened version of the input image  10 . 
   In an exemplary embodiment, a smoothed image  14  is generated by subtracting a correction image  12  from an input image  10 . In some embodiments, the input image  10  may 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 image  10  may comprise chrominance channel data or data from other image channels. 
   In some embodiments, the correction image  12  may be calculated by the correction calculator  16  based on characteristics of the input image  10 . The gradient of the input image  10  and the second derivative of the input image  10  may be the characteristics of the input image  10  from which the correction calculator  16  calculates the correction image  12  in some embodiments. In other embodiments, other input image characteristics may be used in correction image  12  calculations. 
   In some embodiments, the correction image  12  may be determined and applied on a pixel-by-pixel basis. In other embodiments, the correction calculator  16  may comprise an array processor, or other processing means, to produce the correction image  12  on a basis that does not require pixel-by-pixel calculations. 
   Some embodiments of the present invention may be described with reference to  FIG. 2 . In these embodiments, the value of a smoothed-image pixel  24  may be given by the difference between the value of the corresponding pixel  20  in the input image  10  (e.g., the pixel at the same spatial location) and a pixel-correction term  22  calculated for that pixel  20  by a pixel-correction calculator  26 . In other embodiments, the pixel-correction term  22  may be combined with the input image pixel value  20  by other methods. 
   Some embodiment of the present invention may be described with reference to  FIG. 3 . In these embodiments, a pixel-correction calculator  26  may use a pixel value of a pixel  20  in an input image  10  and the values of several neighboring pixels  31 - 48  in generating a pixel correction term  22 . 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 pixels  20 ,  31 , and  35 , denoted v 20 , v 31 , and v 35 , respectively, may be used to approximate the second derivative of the input image  10  at the input-image pixel  20  in the vertical (or y) direction. Image values at pixels  20 ,  41 , and  45 , denoted v 20 , v 41 , and v 45 , respectively, may be used to approximate the second derivative of the input image  10  at the input-image pixel  20  in the horizontal (or x) direction. 
   In some embodiments, approximation of the second derivative at the input-image pixel  20  in the x direction may be given by −v 45 +2v 20 −v 41 , denoted D 2   x.    
   In some embodiments, approximation of the second derivative at the input-image pixel  20  in the y direction may be given by −v 31 +2v 20 −v 35 , denoted D 2   y.    
   In other embodiments, the second derivative may be approximated using non-separable filters or by other methods. 
   In some embodiments, image values at pixels  31 - 38 , denoted v 31 , v 32 , v 33 , v 34 , v 35 , v 36 , v 37 , and v 38 , respectively, may be used to approximate the gradient of the input image  10  at the input-image pixel  20  in the vertical (or y) direction. Image values at pixels  41 - 48 , denoted v 41 , v 42 , v 43 , v 44 , v 45 , v 46 , v 47 , and v 48  may be approximate the gradient of the input image  10  at the input-image pixel  20  in the horizontal (or x) direction. 
   Approximation of the gradient at the input-image pixel  20  in the x direction may be given by 
               1   64     ⁢     (         -   v     ⁢           ⁢   48     -     6   ⁢   v   ⁢           ⁢   47     -     14   ⁢           ⁢   v   ⁢           ⁢   46     -     14   ⁢           ⁢   v   ⁢           ⁢   45     +     14   ⁢           ⁢   v   ⁢           ⁢   41     +     14   ⁢           ⁢   v   ⁢           ⁢   42     +     6   ⁢           ⁢   v   ⁢           ⁢   43     +     v   ⁢           ⁢   44       )       ,         
denoted Gx.
 
   Approximation of the gradient at the input-image pixel  20  in the y direction may be given by 
               1   64     ⁢     (         -   v     ⁢           ⁢   38     -     6   ⁢   v   ⁢           ⁢   37     -     14   ⁢           ⁢   v   ⁢           ⁢   36     -     14   ⁢           ⁢   v   ⁢           ⁢   35     +     14   ⁢           ⁢   v   ⁢           ⁢   31     +     14   ⁢           ⁢   v   ⁢           ⁢   32     +     6   ⁢           ⁢   v   ⁢           ⁢   33     +     v   ⁢           ⁢   34       )       ,         
dentoed Gy.
 
   In other embodiments, the gradient may be approximated using non-separable filters or by other methods. 
   In some embodiments, the correction term  22  for the input-image pixel  20  may be given by 
                 D   ⁢           ⁢   2   ⁢   x         S   ⁢        Gx          +   k       +       D   ⁢           ⁢   2   ⁢   y         S   ⁢        Gy          +   k         ,         
where S=1 and k=5 in some embodiments.
 
   In some embodiments, the pixel-correction calculator  26  may use the pixel value of a pixel  20  in the input image  10  and the values of several neighboring pixels, shown in  FIG. 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 calculator  26 . Some embodiments of the present invention may correct only pixels for which all neighboring values required by the pixel-correction calculator  26  lie 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 to  FIG. 4 . These embodiments of the present invention may comprise a correction calculator  56  for calculating a correction image  52 . These embodiments may further comprise a correction combiner  53  for combining a correction image  52  with an input image  50  or iteration image  51 . These embodiments may further comprise an iteration terminator  60 , for determining when iterations will terminate. These embodiments may further comprise an iteration image buffer  68  for storing a modified iteration image  54  and feeding the iteration image  54  back into the correction calculator  56  for another iteration. 
   In some embodiments, illustrated in  FIG. 4 , image combiner  53  performs an additive combination of the correction image  52  and the input image  50  or iteration image  51 . Other embodiments may comprise non-additive combinations of the correction image  52  and the input image  50  or iteration image  51 . In some embodiments of the present invention, the input image  50  is a halftone image at the first iteration and the updated image  54  is a descreened or partially-descreened version of the input image  50 . 
   In an exemplary embodiment, a modified image  54  is generated at each iteration by subtracting a correction image  52  from an input image  50  on the first iteration and by subtracting a correction image  52  from a modified iteration image  54  on subsequent iterations. After the modified image  54  is generated, an iteration termination condition may be checked at the iteration terminator  60 . If the iteration termination condition is not met  62 , the modified image  54  becomes the iteration image  51  used as input for the next iteration. The iterations may be terminated  66  when the iteration termination condition is met  64 . 
   The correction image  52  may be calculated by a correction calculator  56  based on characteristics of the input image  50  or iteration image  51 . In some embodiments, illustrated in  FIG. 5 , a correction image  52  may be determined on a pixel-by-pixel basis using a pixel-correction calculator  76 . In other embodiments, the correction calculator  76  may comprise array processors or other means to produce the correction image  52  on a basis not requiring pixel-by-pixel calculations. 
   In the exemplary embodiments shown in  FIG. 5 , the value of a modified image pixel  74  may be obtained by applying a correction to the corresponding pixel in the input image  50  or iteration image  54  that is being processed. In some embodiments, this correction may be accomplished by taking the difference between the value of the corresponding pixel  70  in the input image  50  or iteration image  54  (i.e., the pixel at the same spatial location) and a pixel-correction term  72  calculated for that pixel. 
   In some embodiments, the pixel-correction calculator  76  may use the pixel value of the pixel  70  in the input image  50  or iteration image  54  and the values of one or more neighboring pixels. In some embodiments, illustrated in  FIG. 6 , these neighboring pixels  81 - 88  and  91 - 98  are the adjacent pixel immediately above, below, to the right and to the left of the pixel being processed  70 . In other embodiments, the support of the pixel-correction calculations may include other pixels. 
   In some embodiments, image values at pixels  70 ,  81 , and  85 , denoted v 70 , v 81 , and v 85 , respectively, may be used to approximate the second derivative of the iteration-input image  50  at the iteration-input-image pixel  70  in the vertical (or y) direction. Image values at pixels  70 ,  91 , and  95 , denoted v 70 , v 95 , and v 95 , respectively, may be used to approximate the second derivative of the iteration-input image  50  at the iteration-input-image pixel  70  in the horizontal (or x) direction. 
   In some embodiments, approximation of the second derivative at the iteration-input-image pixel  70  in the x direction may be given by −v 95 +2v 70 −v 91 , denoted d 2   x.    
   In some embodiments, approximation of the second derivative at the iteration-input-image pixel  70  in the y direction may be given by −v 81 +2v 70 −v 85 , denoted d 2   y.    
   In other embodiments, the second derivative may be approximated using non-separable filters. 
   In some embodiments, image values at pixels  81 - 88 , denoted v 81 , v 82 , v 83 , v 84 , v 85 , v 86 , v 87 , and v 88 , respectively, may be used to approximate the gradient of the iteration-input image  50  at the iteration-input-image pixel  70  in the vertical (or y) direction. Image values at pixels  91 - 98 , denoted v 91 , v 92 , v 93 , v 94 , v 95 , v 96 , v 97 , and v 98  may be used to approximate the gradient of the iteration-input image  50  at the iteration-input-image pixel  70  in the horizontal (or x) direction. 
   In some embodiments, approximation of the gradient at the iteration-input-image pixel  70  in the x direction may be given by 
               1   64     ⁢     (         -   v     ⁢           ⁢   98     -     6   ⁢   v   ⁢           ⁢   97     -     14   ⁢           ⁢   v   ⁢           ⁢   96     -     14   ⁢           ⁢   v95     +     14   ⁢           ⁢   v   ⁢           ⁢   91     +     14   ⁢           ⁢   v   ⁢           ⁢   92     +     6   ⁢           ⁢   v   ⁢           ⁢   93     +     v   ⁢           ⁢   94       )       ,         
denoted gx.
 
   In some embodiments, approximation of the gradient at the iteration-input-image pixel  70  in the y direction may be given by 
               1   64     ⁢     (         -   v     ⁢           ⁢   88     -     6   ⁢   v   ⁢           ⁢   87     -     14   ⁢           ⁢   v   ⁢           ⁢   86     -     14   ⁢           ⁢   v   ⁢           ⁢   87     +     14   ⁢           ⁢   v   ⁢           ⁢   81     +     14   ⁢           ⁢   v   ⁢           ⁢   82     +     6   ⁢           ⁢   v   ⁢           ⁢   83     +     v   ⁢           ⁢   84       )       ,         
denoted gy.
 
   In other embodiments, the gradient may be approximated using non-separable filters. 
   In some embodiments, the pixel-correction term  72  for the iteration-input-image pixel  70  is 
                 d   ⁢           ⁢   2   ⁢   x         S   ⁢        gx          +   k       +       d   ⁢           ⁢   2   ⁢   y         S   ⁢        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 calculator  76  may use the pixel value of the pixel in the input image  50  or iteration image  54  and the values of one or more neighboring pixels, such as those shown in  FIG. 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 calculator  76 . Some embodiments of the present invention may correct only pixels for which all neighboring values required by the pixel-correction calculator  76  lie 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&#39;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 in  FIG. 7 . 
   In the embodiments illustrated in  FIG. 7 , a correction image  112  is calculated by a correction calculator  115 . This exemplary correction calculator  115  calculates a correction image  112  from the second derivative  111  of the input image  110  and from the adjusted image-gradient magnitude  113 . A corrected image  114  may be derived from the correction image  112  and the input image  110 . 
   In these embodiments, the correction calculator  115  comprises an image gradient calculator  120  for 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 calculator  122 , which, in some embodiments, may calculate an image gradient magnitude in multiple directions. These embodiments may further comprise an image gradient magnitude adjuster  124  for 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 calculator  126  for calculating the second derivative of an image at one or more pixel locations and in one or more directions. These calculators  120 ,  122 ,  124  and  126  provide input to the correction value calculator  128 , which processes the output from the calculators  120 ,  122 ,  124  and  126  and calculates a correction image  112 . The correction image  112  may then be combined with the input image  110  to produce a corrected image  114 . 
   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. 
   The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention in the use of such terms and expressions of excluding equivalence of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.