Image analysis – Image compression or coding – Gray level to binary coding
Reexamination Certificate
1997-03-27
2002-01-29
Nguyen, Madeleine (Department: 2622)
Image analysis
Image compression or coding
Gray level to binary coding
C358S426010, C358S438000
Reexamination Certificate
active
06343152
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention is in the field of digital image compression with specific application in connection with image compression for continuous raster scan output devices such as laser printers, although other uses such as facsimile transmission are also possible. The invention relates in particular to bi-level image compression. A bi-level image refers to a digitized image in which each pixel is either 1 or 0 meaning ON or OFF. It is suitable for line-art and text and, in many cases for gray scale and color images as well where the display device is not capable of displaying gray scale or color images respectively.
Prior art techniques for compressing bi-level images include:
Relative Element Address Designate (READ) algorithms which are lossless encodings of bi-level images. READ algorithms encode the transitions from 0 bits to 1 bits using the relative address of each transition. Compression occurs since runs of all-0 or all-1 are commonly encountered in text or line-art documents and thus there are relatively few transitions. Modified versions of READ are standardized by the CCITT and known as Group
3
(G
3
) and Group
4
(G
4
). G
3
and G
4
standards are common in fax machines and document storage devices. Since READ is a lossless algorithm, the achieved compression is dependent upon the image itself. It is well known that complicated documents including photographic-like images are not compressed well by READ; often the compressed size is larger than the original.
The Joint Bi-level Image Expert Group (JBIG) has proposed a compression standard to address the shortcomings of CCITT G
3
/G
4
in handling photographic-like images known as Progressive Bi-Level Image Compression. This is a lossless standard which addresses the same type of images expected to do well using the invented techniques. The JBIG algorithm sequentially (or progressively) codes bits in an image based upon the bits immediately before and above the current bit. Although there are no known implementations of this algorithm, it is reported to achieve good compression on documents that will grow under CCITT G
3
/G
4
. However, it is also reported to be approximately three times more compute intensive than G
3
/G
4
. Since JBIG is a lossless algorithm, the achieved compression is dependent upon the image itself.
The Joint Photographic Experts Group (JPEG) has introduced a lossy/lossless compression standard for gray-scale and color images. This standard is in common use for multi-level images and achieves good quality in its lossy mode at the expense of significant computational complexity. The complexity arises from the use of the Discrete Cosine Transform and a complicated encoding process. It is this complexity that precludes the JPEG algorithm from use in certain applications. The invented technique attempts to avoid this complexity.
Another bi-level image compression technique is known as resolution reduction. Resolution reduction algorithms are generally ad-hoc methods for encoding bi-level images to achieve a lossy compression. However, all are based upon the idea that a high-resolution image may be approximated by a lower resolution version. Compression occurs because a lower resolution image is smaller. Resolution reduction is done in many ways, including low-pass filtering, line drop and bit approximation as described below.
In low-pass filtering, the image is re-sampled by a low pass filter to a lower resolution. Decompression replicates each bit in the low-resolution image in two dimensions.
In line drop compression, scanlines from an original image are dropped completely, thus compressing the image. Decompression replicates the kept scanlines. This is essentially a one-dimensional low-pass filter, but is computationally more efficient than traditional low-pass filtering.
In bit approximation compression, the bit-pattern of a scanline is approximated by a table of values, where the table attempts to match the bits as closely as possible. This is generally done on very small bit patterns (e.g., 4-8 bits).
SUMMARY OF THE INVENTION
A method and apparatus are disclosed for the compression of complex bi-level images referred to herein as Gray-scale Encoding Compression (GEC). GEC is a lossy compression technique that retains good image quality with limited computation complexity over moderate compression ratios. GEC strives to regenerate the original image's shades of gray. No attempt is made to capture the bit patterns in the original image; instead, GEC captures the gray-scale content in the image. Upon decompression, the decompressed image has the same gray-scale content as the original, but typically will have a completely different bit map. GEC compression always produces a compressed image which is smaller than the original image. The compression is lossy since the actual bit-patterns regenerated do not match the original, although in many cases the regenerated image will appear to be of comparable quality as the original.
GEC has particular application when used with continuous raster scan output devices such as laser printers where the invention enables the printing of images using a smaller amount of memory than would be needed without GEC. The reason this advantage is obtained is because continuous raster scan output devices expect an entire page to be available at a speed required by the print engine. To accomplish this, without GEC or other compression, the entire image to be printed must exist in its bi-level image format in the printer's memory. The present invention overcomes this requirement allowing larger images (i.e., bi-level images with many black pixels) to be printed without as much memory as would otherwise be needed.
REFERENCES:
patent: 4075663 (1978-02-01), Wellendorf
patent: 4369463 (1983-01-01), Anastassiou
patent: 4677571 (1987-06-01), Riseman et al.
patent: 5113455 (1992-05-01), Scott
patent: 5140648 (1992-08-01), Hackett et al.
patent: 5264942 (1993-11-01), Shimotsuji
patent: 5303313 (1994-04-01), Mark et al.
patent: 5323247 (1994-06-01), Parker et al.
patent: 5416857 (1995-05-01), Chen et al.
patent: 5432870 (1995-07-01), Schwartz
patent: 5535277 (1996-07-01), Shibata et al.
patent: 5680129 (1997-10-01), Weinberger et al.
patent: 5704020 (1997-12-01), Hanyu et al.
patent: 5715329 (1998-02-01), Murata
Blakely & Sokoloff, Taylor & Zafman
Nguyen Madeleine
Peerless Systems Corporation
LandOfFree
Bi-level image compression by gray scale encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bi-level image compression by gray scale encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bi-level image compression by gray scale encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823040