Facsimile and static presentation processing – Static presentation processing – Communication
Reexamination Certificate
1998-01-29
2002-01-08
Popovici, Dov (Department: 2622)
Facsimile and static presentation processing
Static presentation processing
Communication
C358S001170
Reexamination Certificate
active
06337747
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system for improving the efficiency and quality of digital image compression systems that are used in printing and other image processing systems.
2. Description of the Related Art
Current laser beam printer engines found inside printers, copiers, fax machines, multifunctional equipment and other imaging systems are capable of printing high resolution image data at high speeds. For such a printer engine, the motion of the engine must be uninterrupted and a data stream must be provided to the engine at a high rate at precise timings (within a few nanoseconds) from the moment the printer engine picks up a sheet of paper (or a similar medium) and until the sheet is ejected with all the information properly printed on it. Since typical pixel data flows to the printer engine at a rate of tens of millions of pixels per second, there is very little time for on-the-fly computations.
One method for providing such a data stream to a printer engine requires complete preparation and storage of a full page of rasterized image data prior to commencing any printing. Such a method usually requires a large amount of memory.
Recently-introduced high-speed printers are capable of printing high-resolution images in multi-level grayscale or in multi-level color. In multi-level grayscale printing, for example, an 8-bit value is used to represent each pixel on a page. Accordingly, approximately 30,000,000 bytes of memory are required in order to store a full 8 ½″ by 11″ 8-bit grayscale image to be printed at 600 dots per inch (dpi). A multi-level color image of the same size and density requires four times as much memory, approximately 120,000,000 bytes, in order to store, for each pixel, 8-bit values corresponding to each of the cyan, magenta, yellow, and black components. For these images, a large amount of memory is needed if the image data for an entire page were rasterized prior to commencing printing. This incurs high costs that are commercially unacceptable in many markets.
In order to reduce the amount of memory required to store a page of image data to be printed and to maintain an uninterrupted stream of image data to a printer engine, a banding and compression technique has been suggested whereby the page is partitioned into parallel bands. Prior to printing, each band is rasterized using a rasterized band memory, compressed and stored in compressed form. The rasterized band memory is then released for re-use and subsequent bands are processed similarly. During printing, each processed band is decompressed back into rasterized image data “on the fly” as the page is being printed.
The above technique requires: 1) A compression method which practically guarantees a minimum compression ratio, so as to be certain that a page of compressed image data bands will fit within a storage area of predesignated size, and 2) a decompression algorithm sufficiently fast to produce decompressed image data from the bands at the high rates required by laser beam printer engines.
Various compression techniques have been proposed to meet the above requirements. For example, lossless compression techniques such as Huffman, run-length, and Lempel-Ziv-Walsh (LZW) typically provide fast decompression, but these techniques cannot guarantee a particular compression ratio. Furthermore, although these techniques produce good compression ratios for binary images, such as text and black-only graphics images, lossless techniques often provide poor compression ratios when applied to multi-level images, particularly scanned color images.
In the event that lossless techniques fail to yield a required compression ratio, supplementary lossy compression techniques may be used.
JPEG compression, for example, can provide guaranteed minimum compression ratios, such as 10:1 or higher. However, image distortion due to JPEG processing tends to increase along with required compression ratios. If a required compression ratio is not too high (8:1 or less), image degradation is often unnoticeable for some multi-level images, such as natural photographs. However, JPEG compression blurs sharp edges, thereby significantly affecting the quality of text and graphics images.
Accordingly, what is needed is an improved lossless compression technique which provides acceptable (e.g., 4:1) compression ratios for a vast majority of possible input images and thereby reduces reliance on less-desirable lossy compression to a negligible minority of possible input images. Such an improved compression technique must also provide fast decompression so that print data is continuously provided to a printer engine during printing.
One improvement to lossless compression techniques is described in “Graphics Gems II”, edited by James Arvo, pages 93 to 100, Academic Press Inc., 1991 (the “Holt-Roberts Method”). The Holt-Roberts method is a two dimensional predictor-corrector technique which takes advantage of the similarity between neighboring pixels of high resolution images in order to convert the relatively flat statistics of an input image to statistics of differences (correctors), which are concentrated around zero and can therefore be compressed more effectively than the input image. Using the Holt-Roberts Method, an image is pre-processed by using a predictor algorithm to calculate a predictor value corresponding to each pixel of the image. For each predictor value, a corrector value is calculated based on the difference between the predictor value and its corresponding image pixel. The corrector values are stored in a corrector file which, in conjunction with the predictor algorithm, is completely descriptive or the original image file. The actual values of the predictor need not be stored. The corrector file is then subject to lossless compression.
If an effective predictor algorithm is used, many of the corrector values will be equal to zero or in the vicinity of zero. Advantageously, conventional lossless compression techniques such as Lempel-Ziv-Walsh or Huffman compression are most effective in achieving high compression ratios when compressing data having such an uneven statistical distribution. Accordingly, compression ratios achieved by applying lossless compression to the corrector obtained from predictor-corrector pre-processing of an image are significantly greater than those achieved by applying lossless compression directly to the original image.
However, while trying to realize the above method, Applicant encountered a problem inherent in practical implementations of predictor-corrector compression techniques. Applicant has discovered that implementation of Holt-Roberts usually results in a corrector file that is significantly larger then a corresponding original image file. The reason for this phenomenon is as follows. When applied to original image data having 8-bit pixel values ranging from 0 to 255, a predictor algorithm may, for example, produce predicted values also ranging from 0 to 255. Corresponding corrector values are calculated using the simple formula: corrector value =original image value−predictor value. Accordingly, the range of possible corrector values is twice the range of the original image values, namely −255 to 255.
It should be noted the corrector may be positive or negative, so a sign bit is also required. As a result, whereas each original pixel value could be stored using one 8-bit sequence, storage of each corrector value in the above example requires up to ten bits. Other predictor algorithms may require even more bits per corrector value.
Most digital processing equipment is constructed to operate on data organized into 8-bit bytes. Therefore, in order to represent a corrector value requiring ten bits or more, it is generally contemplated to reserve two bytes of eight bits each. Such a corrector file can be twice as large as an original eight bits per pixel image file which it represents. As a result, any improvements in compression ratio due to the uneven statistical distribution
LandOfFree
System to adaptively compress raster image data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System to adaptively compress raster image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System to adaptively compress raster image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2856661