Universal lossless compressor for digitized analog data

Details Universal lossless compressor for digitized analog data Universal lossless compressor for digitized analog data

1999-12-03

2002-08-13

Jeanpierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

C341S051000, C382S166000

Reexamination Certificate

active

06433707

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to data compression and more particular lossless compression of digitized analog data.
BACKGROUND OF THE INVENTION
Lossless compression methods are required for the efficient transport and storage of high quality digitized images and sound. All existing methods suffer from one or more shortcomings, as is well known in the field, because they are all more or less media specific. Because they were designed to handle text, LZW and similar alphabet based schemes are best suited to data with a small set of primary symbols and frequently repeated combinations. Such methods tend to perform poorly on video and sound Conversely, Adaptive Transform Compression (ATC) works well on sound but performs badly on text.
In addition, many methods including JPEG variants that utilize Huffman or other table-based variable length coding schemes have the drawback that a frequency table for each data set being compressed must be calculated and communicated to the decoder. The calculation of the table increases the time required for encoding, and communication of the table to the decoder takes up valuable bandwidth, reducing the effective compression gain.
Tables can be eliminated if the data is transformed to a form that follows or approximates a Laplacian or other known distribution shape. An example of such a transformation is replacing pixel values with differences of successive pixel values along a scan line. Using the properties of the expected distribution, the encoder can assign efficient (i.e., near entropy) variable bit length codes without constructing a frequency table. In addition, the encoder need transfer to the decoder only the information required to characterize the expected distribution (e.g., the variance of the Laplacian).
Unfortunately, Laplacian encoders are relatively slow particularly when one has to separately encode multiple transformed streams (e.g., three channels of RGB data for color images or two channels for stereo sound). Moreover, the efficiency of standard variable-bit-length encoding depends on the variance of the distribution and the sparseness of the data. Laplacian encoding is inefficient for spiky distributions, i.e., sparse data with large blocks of zeros.
There has thus heretofore been a need for a data compressor that utilizes the advantages of Laplacian encoding, i.e., the elimination of data specific frequency tables, and that performs with speed and efficiency comparable to or better than that of existing table or alphabet based methods.
SUMMARY OF THE INVENTION
The present invention combines a lossless transformation producing approximately Laplacian distributed data with a space map to combine and reblock data streams in order to minimize the number of passes through an efficient Laplacian encoder and to maximize the efficiency of each pass. The present invention is “universal” in that it can compress digitized analog data from any source without calculating or communicating data specific frequency tables.


REFERENCES:
patent: 5359676 (1994-10-01), Fan
patent: 5369443 (1994-11-01), Woodham
patent: 5764374 (1998-06-01), Seroussi et al.
patent: 6125201 (2001-09-01), Zador

Affiliated with

Also associated with

Rating

Universal lossless compressor for digitized analog 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 Universal lossless compressor for digitized analog data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal lossless compressor for digitized analog data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2894255