Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
2000-10-26
2004-02-10
Wu, Jingge (Department: 2623)
Image analysis
Image compression or coding
Including details of decompression
C341S051000
Reexamination Certificate
active
06690832
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method, system and program for decoding compressed data.
2. Description of the Related Art
Digital images may use one or more bits to describe the color intensity at each pixel. The term “pixel” as used herein refers to one or more intensity inputs or bit values at a data point that represents data to be rendered (i.e., printed, displayed, etc.), where the data to be rendered may include, but is not limited to, images, text, composite images, graphs, collages, scientific data, video, etc. A pel is a picture element point that may be expressed with one bit. If only one bit is used to express the intensity, then the image is a bilevel image where there are two possible intensity values per pixel, such as black and white or full saturation and no intensity. Digital monochrome images that allow for more than two intensities per pixel express the intensities as shades of grey.
Most systems compress image data before transmitting the data to an output device, such as a printer or display, that renders the image data. The output device must decode or decompress the compressed image to output to print or otherwise render. Compressed images may also be archived and then at some later time transmitted to an output device for decompression and rendering, e.g., printing or display. For instance, International Business Machines Corporation (IBM) uses a concatenated Adaptive Bi-Level Image Compression (ABIC) algorithm to compress check images created using high speed scanners. The IBM ABIC technology is one of the industry standards for high speed scanning and storing of check images.
FIG. I illustrates planes
2
,
4
,
6
,
8
providing bit values for pixels in the plane, where each pixel has four bit values, one bit value from each plane. Each bit plane
2
,
4
,
6
,
8
provides a one bit value for one pixel represented in the four planes. Bit plane
2
provides the most significant bit for each pixel represented in the plane, bit plane
4
the second most significant bit, bit plane
6
the third most significant bit, and bit plane
8
the least significant bit for each pixel represented in the four planes
2
,
4
,
6
,
8
. Each plane provides one of the four bits used to express the intensity level, e.g., shade of grey, for the pixel. When four planes are used, there are sixteen possible intensity values for each pixel.
In the prior art IBM scanning and storage system, the checks are scanned and the scanned data processed down to produce sixteen possible levels of intensity for each pixel on the check. Each intensity value for a pixel can be expressed in four bits or four planes of data. Before compressing the data using the ABIC algorithm, the planes providing bit values for the pixels are concatenated as shown in FIG.
2
. into a single bi-level image
10
with four times the height and the same width. Concatenating the planes allows a grey scale image having more than two possible intensity values per pixel to be compressed as a bi-level image.
An ABIC coder would use arithmetic coding to code the concatenated image as a bi-level image. The ABIC algorithm of the prior art would sequentially code each bit of image data by using the seven nearest neighbor bits and a probability distribution that is calculated based on previously coded data. In current implementations, the ABIC decoder maintains a history group of bits comprising the last N +2 decoded bits. In certain current implementations, the ABIC decoder uses seven of the bits, including the last two decoded bits and bits in the history range from the (N −2) bit to the (N +2) bit. These are the seven nearest bits in the bit data stream. Details of using the ABIC algorithm to code and decode data are described in the IBM publication entitled “A Multi-Purpose VLSI Chip for Adaptive Data Compression of Bilevel Images”, by R. B. Arps, T. K. Truong, D. J. Lu, R. C. Pasco, and T. D. Friedman, IBM J. Res. Develop., Vol. 32, No. 6, pgs. 775-795 (November 1988) and the commonly assigned U.S. Pat. No. 4,905,297, which publication and patent are incorporated herein by reference in their entirety.
In the prior art, to decompress data compressed as concatenated ABIC, the output device hardware must decompress and buffer the values for the first three planes. After decoding at least some values in the fourth plane, the decoder may reassemble the four bits for a pixel from the previously buffered three planes and just decoded bits in the fourth plane into the four bits for a pixel and then transfer the decoded four bits per pixel to the output device to render. This technique requires substantial hardware resources because the output device hardware must have sufficient buffer space to decode and store three planes of data before being able to output data and release space in the buffer.
Further, the delay in having to wait to decode the first three planes and part of the fourth plane before outputting data limits the ability of the output device to continually feed data to the printer. As printer throughput increases, at some speed, the decoding operations will not been able to provide output pixel data at the printing rate of the printer.
Thus, there is a need in the art for an improved technique for decoding compressed data and, in particular, concatenated images that were coded using ABIC or other encoding techniques such as Huffman encoding, especially when high speed output devices are being used that are capable of processing and rendering data very quickly.
SUMMARY OF THE PREFERRED EMBODIMENTS
Preferred embodiments describe a method, system, program, and data structure for decompressing a compressed data stream. At least one reentry data set is received. Each reentry data set includes a pointer to a location in the compressed data stream and decoding information that enables decoding to start from the location addressed by the pointer. Decoding is performed from the beginning of the compressed data stream to a point in the compressed data stream preceding a location addressed by a first reentry data set. For each generated reentry data set, the location in the compressed data stream addressed by the pointer in the reentry data set is accessed. The decoding information in the reentry data set is then used to decode compressed data from the accessed location to a point in the compressed data stream preceding the location addressed by the pointer in the next reentry data set. The decoded data is buffered and outputted.
In further embodiments, the decoding information includes decoded data preceding output produced by decoding the compressed data stream at the location addressed by the pointer and probability estimates used to decode the compressed data at the location addressed by the pointer. The data may be compressed and decoded using an Adaptive Bi-Level Image Compression (ABIC) algorithm, or other compression algorithms known in the art.
In still further embodiments, the compressed data comprises concatenated bit planes. Each reentry data set pointer addresses a location in the compressed data stream that when decoded produces a first bit value in one plane following the first plane.
Yet further, multiple iterations of decoding further data prior to each reentry data set and decoding further data following the last reentry data set are performed until the entire data stream has been decoded.
Preferred embodiments provide a technique using reentry data sets to allow decoding of different parts of a decompressed data stream when data from different parts, such as bits from different concatenated planes, are needed before any data can be outputted. With the preferred embodiments, data from different parts of the compressed data stream can be decompressed and outputted before having to decompress all or a substantial part of the data stream, thereby increasing the throughput or the rate at which data is outputted.
REFERENCES:
patent: 4546385 (1985-10-01), Anastassiou
patent: 4616220 (1986-10-01), Grunewald et al.
patent: 4745473 (
Mitchell Joan LaVerne
Rijavec Nenad
International Business Machines - Corporation
Konrad Raynes & Victor & Mann LLP
Victor David W.
Wu Jingge
LandOfFree
Method, system, and program for decoding compressed data at... 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, system, and program for decoding compressed data at..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and program for decoding compressed data at... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3341030