Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2001-08-20
2003-06-17
Johns, Andrew W. (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
C382S232000, C382S247000, C341S050000
Reexamination Certificate
active
06580833
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the processing of signals, and more particularly to an apparatus and method for entropy coding in the processing of signals.
BACKGROUND OF THE INVENTION
One shortcoming of conventional processing of electronic signals concerns the techniques that are used to reduce the amount of data that is used to represent the signal. One way that the amount of data required to represent a signal is reduced is by using data compression techniques.
Entropy coding is one technique for reducing the amount of data that is used to represent signals. Entropy coding changes the way that the actual values are stored, or redefines them, to reduce the amount of information that is used to represent a signal. A simple type of coding used in image coding, for example, uses a difference value instead of an actual value to represent pixels. Specifically, difference coding maintains the difference between each pixel and the previous pixel in an image. This coding type offers better compression when images are highly correlated because the pixel differences are low. However, difference coding is deficient in its failure to adequately compress the many images, or other types of data signals, that are not highly correlated.
Many conventional processors implement fixed probabilities to represent the symbol stream. One type of fixed probability coding is variable length coding, where values are coded based upon their expected frequency of occurrence. Specifically, if a certain value is expected to occur frequently within the images to be processed, then a short code (e.g., 1) is used to represent that value. However, if another value is expected to occur infrequently, then it is represented by a long code (e.g., 000001). Fixed probability coding, such as Huffman type, offers compression for signals with expected value distributions, but is not as effective when values vary greatly, which is often the case because data can make rapid and extreme localized changes in probability distributions.
An improvement to this form of signal processing implements a coding system, called historical coding, that encodes the signal using statistics collected on recent symbols in the signal. One implementation of this system involves using a table to keep a tally of the symbols in the signal. The tally kept for each symbol determines how the symbol will be encoded. These historical coding systems suffer from several problems. First, processing overhead is a function of the resolution of the data to be processed. Relatively large symbol sets require greater computational overhead. Additionally, as symbol sets are enlarged to increase signal resolution, larger neighborhoods of data are required to collect meaningful statistics. Thus, with large symbol sets, if the local probability is changing rapidly a large sample size can actually counter prompt and accurate determination of local probability. As the symbol set becomes large, it becomes progressively less likely that a specific symbol will be repeated in a local neighborhood.
Efforts to solve the problems of coding based upon data distribution collection have lead to complex systems which are difficult to implement in hardware, do not readily allow for either fast execution or reasonable cost, and provide low frequency approximations of local probability. These coding methods are also unable to implement effective encryption protection for the coded stream being transmitted. Combining entropy coding with encryption improves both the security and efficiency of communication.
Accordingly, there remains a need for signal processing that implements an entropy coding scheme that more efficiently reduces data quantities and does so in a real time environment. Additionally, there remains a need to effectively implement encryption technology during signal processing such that unauthorized receipt or use of the symbol stream can be prevented.
SUMMARY OF THE INVENTION
The present invention is a system and method for encoding symbols in a symbol stream to compress the amount of data required to represent a signal corresponding to the symbol stream. When coding a current symbol, a modeling value is calculated by a modeling module as a function of a sampling of symbols local to a current symbol. The classification module uses the modeling value to create, or retrieve, a probability function that corresponding to the stream. The probability function is used to calculate the probability that the current symbol would have been the next symbol in the stream. The encoding of the current symbol depends upon the probability that the current symbol would have been the next symbol in the stream. An encoder uses more or less bits to encode the symbol based on the probability provided.
The system and method can further be used to decode the symbols using the same process for determining a modeling value and mapping the modeling value to a probability function as was performed by the encoder. The characteristics of the bits in the encoded symbol are used by the decoder to determine the probability assessed by the encoder. The probability function retrieved by the decoder is used in a reverse lookup in order to determine the original symbol value that was encoded. Furthermore, an encryption value can be used to select the appropriate modeling, classification, or probability function preventing unauthorized decoding of the stream.
REFERENCES:
patent: 4363036 (1982-12-01), Subramaniam
patent: 5023611 (1991-06-01), Chamzas et al.
patent: 5025258 (1991-06-01), Duttweiler
patent: 5298896 (1994-03-01), Lei et al.
patent: 5315670 (1994-05-01), Shapiro
patent: 5357250 (1994-10-01), Healey et al.
patent: 5448642 (1995-09-01), Yeh
patent: 5546080 (1996-08-01), Langdon et al.
patent: 5748121 (1998-05-01), Romriell
patent: 5778102 (1998-07-01), Sandford et al.
patent: 6298160 (2001-10-01), Goertzen
patent: 0 600 646 (1994-06-01), None
patent: 0 600 646 (2000-09-01), None
patent: WO 96/19045 (1996-06-01), None
Barbir, A. “A Methodology for Performing Secure Data Compression.” pp. 266-270, IEEE 1997.
EPO International Search Report, dated Jul. 8, 1999, received Jul. 13, 1999.
Bromberg & Sunstein LLP
Dang Duy M.
Johns Andrew W.
Quvis, Inc.
LandOfFree
Apparatus and method for entropy coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for entropy coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for entropy coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3159846