Image analysis – Image compression or coding
Reexamination Certificate
2002-09-13
2004-01-06
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
C382S244000, C382S248000
Reexamination Certificate
active
06674908
ABSTRACT:
GOVERNMENT INTEREST STATEMENT AS TO RIGHTS UNDER FEDERALLY SPONSORED RESEARCH
Non-applicable
SEQUENTIAL LISTING OR PROGRAM
Non-applicable
FIELD OF THE INVENTION
The invention relates to dictionary based lossless data compression and encryption, particularly with respect to the manner in which the problem of statistical properties of the input data is treated.
BACKGROUND OF THE INVENTION
The term “data compression” refers to the process of transforming a set of data into a smaller compressed representational form, so that it occupies less space on a storage or that they can be transmitted in less time over a communications channel. The data decompression process complements a data compression process and is the process of restoration of the original set of data exactly if the process is lossless or to some approximation if the process is lossy.
Many techniques have been used over the years to compress digital data. However they all based on the same few basic principles: a statistical coding, a dictionary coding, or a decorrelation (see: Storer J. A., Data Compression: Method and Theory, Computer Science Press (1993), p.p. 6,7,10,11,103-111,114,115,126-128; Williams R. N. Adaptive Data Compression, Kluwer Academic Publishers (1990); Salomon D. Data Compression. Springer (1997), p.p. 35-37,62-64,67,126,151-157).
A major example of statistical coding is Huffman encoding (see, Salomon D. Data Compression, Springer (1997), p.p.62-67. In this method, it is assumed that certain bytes occur more frequently in the file than others. For example, in English text the letters have some special frequency distribution, and the length of the code assigned to specific letter is inversely related to the frequency of that byte in the file. These bit sequences are chosen to be uniquely decodable. Huffman encoding may greatly expand a file if the pre-assigned scheme assumes considerably different frequency statistics than the one actually present in the file. In the general case of a binary file, produced by a random source, the frequency distribution could be close to uniform, and Hoffman compression will fail.
The dictionary algorithms are variations of the Lempel-Ziv technique of maintaining a “sliding Window” of the most recent processed bytes of data and scanning the Window for sequences of matching bytes. The input data character stream is compared character-by-character with character sequences stored in a dictionary to check for matches. Typically, the character-by-character comparison is continued until the longest match is determined. Based on the match, the compressed code is determined, and the dictionary is updated with one or more additional character sequences. If the sequence is found, the length of the matching sequence and its offset within the Window are output; otherwise, a “raw” byte is output. One example of such scheme is described in U.S. Pat. No. 6,075,470 (Little), entitled ‘Block-wise Adaptive Statistical Data Compression’, issued on Jun. 13, 2000 (p.p 9-30). The scheme with parallel compression using different machines is described in U.S. Pat. No. 6,417,789 (Har at al) entitled ‘Highly-Efficient Compression Data Format’, issued on Jul. 9, 2002, that do not improve a rate of compression, if published statistical compression is not effective.
These dictionary algorithms require: a) a number of repetitions of the sequence, included in the dictionary; b) inclusion of the dictionary sequence in the output, so that matching rate must be high enough to actually achieve compression; c) an ‘exact match’ between sequences in an input Window and a dictionary. For example, the letters ‘b’ and ‘c’ do not match, and the compression will fail while with a binary coding the difference is only one bit. Many techniques use the process of adaptation to the statistical description of the data. In general, type-specific compression techniques may provide a higher compression performance than general-purpose algorithms on the file for which the techniques are optimized. However, they tend to have a much lower compression performance if the file model is not correct.
The decorrelation technique is applied to highly correlated data, like space or medical images, with wavelets or Fast Fourier Transformation, as a set of basic functions for an input image expansion. These transformations are described in details in: Rao K. R., Yip P. C., Eds. The Transform and Data Compression Handbook. CRC Press (2001), p.p. 13-15, 35-37, 61-63, 73-75, 117-123, 161-167, 191. If the input sequence is highly correlated, the coefficients of this transformation will decay rapidly, and the number of them could be cut-off, providing compression with some loss of information. These losses could be acceptable for a human perception of an image, but unacceptable for compression of text or executable files, which are not correlated, and when no losses are acceptable. It is also unacceptable for correlated diagnostic or intelligence images, for which the high-frequency component can have an important informative value. The method of using transformations with digital signal processing described in U.S. Pat. No. 6,333,705 (Amone), issued Dec. 25, 2001
One example of the decorrelation technique is described in U.S. Pat. No. 6,141,445 (Castelli et al.), entitled ‘Multiresolution Losseless/ Lossy Compression and Storage of Data for Efficient Processing thereof,’ issued on Oct. 31, 2000, that used a lossy technique to produce the losseless compression by means of applying an orthogonal expansion (could be the wavelet expansion) to an input sequence. (p.p. 12-16). After an inverse transform and finding residuals between an input data and the wavelet transform. The sequence of residuals could be compressed using statistical techniques. That patent applied this approach to a general case of random binary data, disregarding the fact that it may be not correlated. However, it is not efficient in that case: the sequence of coefficients of these orthogonal transformations does not decay, and it can not be cut-off. As a result, the compressed file may be longer than the input file.
The difference dictionary scheme is described in U.S. Pat. No. 5,977,889 (Cohen), entitled ‘Optimization of Data Representation for Transmission of Storage Using Differences from References Data’, issued on Nov. 2, 1999. This scheme uses the difference in the number of characters between the dictionary sequence and the input data while the selected sub-string must exactly match the dictionary sub-string.
The data compression process removes redundancy from the data, and this procedure can be related to the process of data encryption. The term “data encryption” refers to the process of transforming a set of data into a new representational form that prevents unauthorized reading of this data from a storage or a communications channel. The data decryption process is the process of restoration of exactly the original set of data from the encrypted representation. U.S. Pat. No. 6,411,714 (Yoshiura at al) entitled ‘Data decompression/decryption method and system’, issued on Jun. 25, 2002, uses a statistical distribution of data and interlocked the processes of compression and encryption, but the process of compression is not improved.
A random number generator (RNG) is a software program or hardware circuit that uses a recursive mathematical expression or shifted operations in a register to produce a stream of random numbers. A random number generator is used in the prime art only to encrypt the data but not to improve compression. See, for example, U.S. Pat. No. 6,122,379 (Barbir), entitled ‘Method and Apparatus for Performing Simultaneous Data Compression and Encryption’, issued on Sep. 19, 2000. The next example of using RNG for a data coding is U.S. Pat. No. 6,351,539 (Djakovic), entitled ‘Cipher Mixer with Random Number Generator’, issued on Feb. 26, 2002, which does not perform any compression, but only encrypts the data using RNG. Because the RNG is actually a deterministic mean and its sequence is used in the deterministic order, these procedures can b
Boudreau Leo
Dang Duy M.
LandOfFree
Method of compression of binary data with a random number... 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 of compression of binary data with a random number..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of compression of binary data with a random number... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3188409