Image analysis – Image transformation or preprocessing – Combining image portions
Reexamination Certificate
1998-12-23
2002-01-29
Mancuso, Joseph (Department: 2723)
Image analysis
Image transformation or preprocessing
Combining image portions
C382S294000, C345S440000, C348S584000
Reexamination Certificate
active
06343159
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to methods and systems that model and reconstruct continuous tone or grayscale images from halftoned binary images. More specifically, this invention is directed to methods and systems that convert or reconvert through modeling and reconstruction halftoned binary images into approximations of the original continuous tone images using template matching.
2. Description of Related Art
Conventionally, a typical black and white image on photographic film, for example, includes various gray levels of light. That is, different amounts of light are reflected from various spots of the image on the film, providing what is known as a continuous tone photographic image. It is conventionally known how to digitize the grayscale continuous tone photographic image. More specifically, each pixel or spot of the photographic image is assigned a number representing the amount of light or gray level of that particular spot. Typically, an eight-bit word is used, giving 256 different digitized gray levels of light. The digitized image is known as a continuous tone digital image. Further, it is possible to go back and forth between the analog and digital images and maintain a reasonable reproduction of the image.
It is also conventionally known to provide an image on a recording medium, for example, a paper sheet, rather than on photographic film. For example, a modulated laser can be used to scan a xerographic drum to give a series of black and white spots. The spots are formed by turning the laser on and off. The image on the drum is then developed and transferred to a copy sheet. This process of developing black and white spots provides a binary image, but does not generate a continuous tone image.
It is possible, however, to give the impression of a continuous tone image by using halftoning. The halftone process uses a mathematically stored screen pattern, for example, which is an almost-sinusoidal two-dimensional pattern. The process converts the original or continuous tone image into an image of black and white spots that “appears” to be a continuous tone image. This process is generally accomplished by systematically comparing each pixel's continuous tone value with the value of the screen. If the continuous tone value of the pixel is less dense than the screen value, then a white spot is produced. On the other hand, if the pixel value is more dense than the screen value, a black spot is produced. It should be understood that the pixel values are the 8-bit grayscale values for each pixel of the original image.
In effect, this procedure converts a grayscale image into black and white spots, but gives the impression of multiple gray levels by producing more white spots for a less-dense area and more black spots for a denser area. Although a true continuous tone image is not produced by this procedure, the procedure has two advantages. One advantage is that each spot of the image is described with one bit, rather than the eight-bit word used for each gray level pixel in the original continuous tone picture. This allows the halftone image to be stored with approximately ⅛ of the storage of the original continuous tone image. Another advantage is that, in fact, a halftone image can be printed on paper. In other words, the conversion takes each eight-bit pixel value representing a grayscale value, compares the pixel value to a screen value and provides either a zero (0) or a one (1) to modulate the laser. This image can then be printed on a recording medium such as paper.
Another known halftoning method is called error-diffusion. Typical applications of error diffusion include viewing continuous tone images on low resolution displays and generating bitmaps for binary printers. Error diffusion is an adaptive binarization process which has the property of preserving the local average gray level of the input continuous tone image. Specifically, error-diffusion propagates the error generated during binarization to neighboring pixels.
SUMMARY OF THE INVENTION
Accordingly, if all that is required is printing of the stored halftone image, then there is no difficulty. However, if it becomes necessary to modify the image, for example, to magnify or to change the tone scale, the continuous tone image is often not available. It is then necessary to go back to the original continuous tone image, with the eight-bit words representing the grayscale value of each pixel, to make the modification. However, because this original image requires eight times the storage capacity of the stored halftone image, it is often no longer available. If the original image is no longer available, then the halftone image needs to be converted back to an estimated grayscale image, which represents the original continuous tone image. Clearly, reversing the halftoning process should be performed as accurately and efficiently as possible.
The process of digital inverse halftoning is the process of reconverting a binary image into an approximation of the original grayscale image. Inverse halftoning can be applied to a wide variety of binary image processing applications. Illustratively, inverse halftoning may be used in conjunction with scaling, tone correction, interchanging between halftone methods, facsimile image processing, non-linear filtering, enhancement and/or image compression, for example.
Image conversion between a binary image and a grayscale image is often necessary. Illustratively, image conversion may be necessary where multiple devices are connected together and must communicate with each other. For example, devices such as a scanner, a personal computer or a facsimile machine may be connected such that they are in communication with each other. Often a network is utilized to connect these various devices. In a networked environment, images may be preprocessed for a particular printer. However, it may be necessary to transmit or communicate these images to a second, different, printer. The second printer may have a different printing strategy than the first printer. For example, the second printer could have a different resolution, a different tonal response, and/or a different halftoning method than the first printer. Under such conditions, it may be necessary or desirable to recover the grayscale image information and perform device specific corrections before printing.
It should be appreciated that it is impossible to exactly reverse the halftoning process to recreate the original continuous tone image, since some information has been lost during halftoning and is simply not recoverable. However, just as the halftone image gives the visual impression of grayscale values, conventional methods may be used to reconstruct an approximation of the original continuous tone image.
A partial solution known in the art approximates the original continuous tone image by spatially filtering the halftone image with a low pass filter. This process uses an averaging procedure on the halftone image and yields a reconstructed continuous tone image. The reconstructed image, however, provides a blurred image without sharp lines.
Further, there are a number of other conventional methods and approaches to inverse halftoning. Some of these conventional methods relate to dithered images. When using dithered images, one technique utilizes a neighborhood approach. The neighborhood approach uses adaptive run lengths of 1's and 0's, referred to as the adaptive binary run length (ABRL). This method performs particularly well in a three-step cascade algorithm comprised of ABRL, statistical smoothing and impulse removal.
Thus, the conventional methods and techniques described above have various shortcomings associated with them. Specifically, the conventional methods and techniques described above do not provide optimized methods to perform inverse halftoning to convert halftoned binary images into approximations of the original continuous tone image.
Accordingly, this invention provides improved systems and methods that model and reconstruct grayscale
Cuciurean-Zapan Clara
Kingsley Jeffrey D.
Loce Robert P.
Nagarajan Ramesh
Kassa Yosef
Mancuso Joseph
Xerox Corporation
LandOfFree
Method and apparatus for modeling and reconstruction of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for modeling and reconstruction of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for modeling and reconstruction of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2850810