Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1995-08-18
2001-11-20
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Adaptive coding
C382S244000
Reexamination Certificate
active
06320986
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to systems and methods for compressing data. More particularly, the invention is directed to systems and methods for preprocessing sampled digital data to more efficiently implement sliding window type lossless Lempel-Ziv data compression.
BACKGROUND OF THE INVENTION
A tremendous need exists for systems and methods which can lossless compress sampled digital data. An application to which the present invention pertains involves the lossless compression of grey scale or color data of video images, such as exists in medical imaging applications.
High definition digital video images with multiple bits per sampled pixel require the lossless compression of data representing millions of pixels at data rates in the range of tens of megabytes per second for compression and decompression. Though lossless sliding window Lempel-Ziv algorithms have been implemented in hardware with sufficient throughput rates, the compression ratios of multiple bit per sampled pixel position data has been relatively poor. In part, this is attributable to the fact that as the quantization precision (in bits per sample) increases, so too does the likelihood that successively adjacent pixels will differ in the least significant bit positions of the digital data. Though preprocessing techniques have been developed, such as that described in the aforementioned co-pending U.S. patent application Ser. No. 08/409,766, the techniques presume a relatively low precision in the data samples and therefore a corresponding consistency of the sampled data in adjacent regions along a scan line. As the bit count per sampled pixel position increases, as with high definition grey scale or RGB format color images, the consistency of the data from pixel-to-pixel decreases dramatically.
Though sampled image data contains a great deal of information redundancy it does not compress well with a direct application of the Lempel-Ziv algorithm. Lempel-Ziv sliding window data compression achieves compression by finding identical matching strings of bytes in an input data stream. In sampled image data, a pixel is represented by an intensity value, or a RGB color content value, captured by digital to analog conversion. A typical high definition video image will have 16 bits per grey scale pixel or 24 bits per color pixel. Although large sections of the image may appear of the same intensity in casual observation, noise variations alone will cause changes in the lower order bits for adjacent pixels. For example for a 16 bit per pixel sample representing a grey scale pixel, noise variation of one part in approximately 65,000 will be sufficient to distinguish successive pixel data.
Grouping pixel data to improve compression is described in U.S. Pat. No. 5,416,857. However, the technique described in the patent does not employ the highly desirable Lempel-Ziv algorithm as first described in the article entitled “A Universal Algorithm for Sequential Data Compression” by authors Lempel and Ziv, in IEEE Transactions on Information Theory, Vol. IT-23, No. 3, pp. 337-343 in 1977. Furthermore, the technique disclosed in the patent involves the processing of the data through a unique circuit in contrast to a preprocessing implementation employing a conventional video graphics system frame buffer.
Therefore, there remains a need for systems and methods which process sampled data into a format particularly amenable lossless sliding window Lempel-Ziv data compression.
SUMMARY OF THE INVENTION
The present invention defines a system suited to the compression of sampled data, comprising a source of digital format data composed of multiple data bits per sample, means for selecting groups of data bits from successive samples based upon their corresponding bit significance in the samples, means for compressing the groups, and means for transmitting tokens representing the compressed groups. In another form, the invention is directed to a method of compressing sample data, comprising the steps of receiving digital format sampled data composed of multiple data bits per sample, selecting groups of data bits from successive samples based upon their corresponding bit significance in the samples and compressing the groups into an output string of tokens.
In one form, the present invention defines a system and method of preprocessing multiple bit per pixel sampled data for lossless Lempel-Ziv compression whereby data stored in a frame buffer is transposed from a pixel based format to a bit plane based format before compression. Regrouping of the sampled video data from groups and strings referenced by pixel to groups and strings by bit plane materially improves the compressibility of the data by segregating the more significant bits and the least significant bits. In this way, the most significant bits, which tend to be consistent across sections of the image, are highly compressible while the least significant bits, which are acknowledged to be influenced by noise and therefore not very compressible, are grouped for lower compression storage. The practice of the invention optimizes the sliding window data compression capabilities of the Lempel-Ziv technique in the context of data which characteristically exhibits patterns of change linked to bit positions by pixel.
Another aspect of the invention relates to its efficient implementation in the context of a video display system frame buffer. In this regard, the invention provides an elegant preprocessing technique whereby the image data as resident in the frame buffer is readily extracted by bit plane for grouping into strings peculiarly suited to the capabilities of Lempel-Ziv data compression.
These and other features of the invention will be more fully understood and appreciated upon considering the description of the detailed embodiment set forth hereinafter.
REFERENCES:
patent: 4409623 (1983-10-01), Kobayashi et al.
patent: 4598411 (1986-07-01), Berkovich et al.
patent: 4707729 (1987-11-01), Bruno et al.
patent: 4712140 (1987-12-01), Mintzer et al.
patent: 5058187 (1991-10-01), Kim
patent: 5140417 (1992-08-01), Tanaka et al.
patent: 5164819 (1992-11-01), Music
patent: 5170368 (1992-12-01), Hattori
patent: 5300949 (1994-04-01), Rodriquez et al.
patent: 5361147 (1994-11-01), Katayama et al.
patent: 5369605 (1994-11-01), Parks
patent: 5379351 (1995-01-01), Fandrianto et al.
patent: 5384646 (1995-01-01), Godshalk et al.
patent: 5416857 (1995-05-01), Chen et al.
patent: 5463699 (1995-10-01), Wilkinson
patent: 5526472 (1996-06-01), Strohacker
patent: 5532694 (1996-07-01), Mayers et al.
Tavakoli, Lossless compression of medical images, May 1991, pp. 200-207, IEEE.*
IBM Technical Disclosure Bulletin, vol. 24, No. 9, Feb. 1982, “High Performance Exact Gray-Scale Compression Technique”, pp. 4513-4516.
A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, vol. IT-23, No. 3, May 1977, pp. 337-343, Ziv et al.
International Business Machines - Corporation
Johnson Timothy M.
Salys Casimer K.
LandOfFree
Preprocessing multiple bit per pixel sampled data for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Preprocessing multiple bit per pixel sampled data for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Preprocessing multiple bit per pixel sampled data for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2616216