Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-03-28
2001-10-02
Lee, Thomas D. (Department: 2624)
Image analysis
Image compression or coding
Lossless compression
C382S246000, C382S239000, C341S107000, C341S051000
Reexamination Certificate
active
06298165
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to a method for improving efficiency of data encoding and decoding. Specifically, the present invention is directed to a method for enhancing an entropy encoder to reduce the worst case inefficiency of such an encoder.
As people seek to communicate more and more frequently in the digital domain, that is transferring digital data between a source and a receiver, a limiting factor is the availability of channel resources. Channels typically are provided with a predetermined bandwidth based on the physical characteristics of the channel itself. To therefore increase the overall information throughput along the channel, it is beneficial to provide capabilities by which information can be transmitted through the channel utilizing the least amount of bandwidth possible.
FIG. 1
illustrates an example of a prior art configuration for transmitting data from a source to a receiver which keeps this goal in mind. In particular, source information, which ultimately could be in analog form and has been digitized by some analog to digital converter (not shown) is provided to a compression device
101
. The compression device operates on the digital bit stream to reduce the number of bits needed to represent the information received from the source. Such information can take the form of a bit stream that is representative of some event, that is, for example, letters in text or pixels in an image. The compressed data is then provided to an encryption device
102
which can “scramble” the data to make it unusable by anyone who is not aware of both the encryption technique and the encryption key. This safeguards the data from being taken off of the channel by some third party and used without permission of the source. The encrypted data is provided to an error correction code (ECC) generator. This ECC generator provides additional information based on the encrypted data so as to permit the receiver to reconstruct data even where some limited number of errors occur in the course of the transmission of the data from the source to the receiver. The data is then provided to the channel
104
. At a receiving end the data is then passed to a device referred to as “EEC-decoder”
105
which uses the transmitted error correction code information to present a corrected data bit stream to the decryption device
106
. The decryption device then deciphers the received data based on some encryption key to essentially provide to the decompression device
107
the same data bit stream which was provided from the compression device
101
to the encryption device
102
. The decompression device thus takes what amounts to be the compressed data bit stream and expands it for use by the receiver (not shown).
FIGS. 2A and 2B
are block diagram representations of portions of the compression device and the decompression device of
FIG. 1
, respectively. In
FIG. 2A
the compression device may include an encoder modeler
201
and a coder
202
. In this context the modeler and the coder will both receive the digital representation of events. The modeler will provide probabilities with respect to the events, for example, the probability that the letter “u” will follow the letter “q”, to the coder. The coder takes this probability and based on the nature of the coder tries to produce a bit stream with the fewest bits possible.
FIG. 2B
relates to what transpires at the receiver in the decompression module. In this instance, the coded bit stream is provided to the decoder
204
. Again, the modeler provides probability information to the decoder so that the decoder can take the coded bit stream and provide a stream of decoded events to the receiver as well as feeding the events back to the modeler. Such modelers are well known in the art.
Sometimes it may be desirable to use different codes in the same application and to have the output from the different coders appear in the same coded bit stream. One way to insure decodability is to have the encoder arrange the bits and the coded bit stream so that the decoder, by reading bits sequentially, will automatically extract those bits it needs, exactly when it needs them. This mechanism is called decoder-synchronized encoding. This technique has been described in literature, for example, “Bi-Level Image Coding with Melcode-Comparison of Block-Type Code and Arithmetic-Type Code”, Ono et al., proceedings IEEE Global Telecommunications Conference, November 1989.
The prior art specifically describes interleaving codes referred to as run-length codes. These codes are based on the notion of producing a bit stream that represents how many occurrences in a row there are of more probable events. One example of such a run length code is referred to as a Golomb code described in “Run-Length Encodings”, Golomb, IEEE Trans. Inform Theory It—12, (July 1966), 399-401.
As an example, run-length codes can be based on a two-symbol alphabet (M,L) where M refers to a more probable event and L refers to a less probable event. The Golomb code is designed to send a bit stream that is representative of the length of a run of the more probable symbol, that is the number of consecutive times the more probable symbol has appeared. For purposes of this explanation, assume that the run corresponds to “n” consecutive occurrence of the more probable symbol, M. Then in accordance with the Golomb code, n=uR+b where 0≦b<R and R is considered to be the Golomb code parameter. R is typically expressed as R=2
p
+Q. For ease of discussion it is assumed for the moment that Q=0. Also as an example, let's assume that R=8, that is the coder is looking for blocks of eight consecutive occurrences of the more probable event. Also assume for this example that the run length n=19. In that circumstance, solving the equation n=uR+b yields that 19=2X8+3, so u=2 and b=3. The coder then outputs u in unary form, that is “u” number of is followed by 0, for instance, here since u=2 then the output of u in unary is 110. To complete the code for n=19, b is output in P-bit binary. Here since the block size is 2
P
=8, P=3, so b is expressed in 3-bit binary form, or as 011. The code then for n=19 is 110011. This represents the following string of events MMMMMMMMMMMMMMMMMMML. Thus, 20 events (19M+1L) are represented in six bits.
It is known that if Q does not equal 0 then if 0≦b<2
p
-q, b is then output is a P-bit binary number while if 2P-Q≦b<2
p
then b+2
p
-Q is output as a (P+1) -bit binary number. However, for ease of discussion, while the present invention may be applied to such circumstances, the embodiment described herein will presume that Q=0.
The Ono paper describes a method for interleaving Golomb codes that have different R parameters. Block Melcode uses decoder-synchronized encoding that is accomplished by encoder buffering. If a run of n occurrences of the more probable symbol (M) is being coded using Golomb parameter R, a block of R consecutive occurrences of M will add a one to the unary part of the expression for n. This “1” can be queued for output immediately. After some number of these blocks of M, a block will occur containing b Ms followed by a “less probable symbol” L and the run will end. To be properly decodable a block's encoding must appear in the output stream when the decoder is ready to decode the first symbol in the block. The output of blocks coded with other parameters will usually appear between blocks coded with any given parameter. Ordering and buffering the output blocks is the essence of the block Melcode. To decode a symbol that was coded using parameter R the decoder extracts either a 1 indicating the occurrence of R consecutive Ms, or a 0 followed by P or P+1 bits which indicate (after decoding the value of b from those bits) the occurrence of b consecutive Ms followed by an L. Until all the symbols from the block have been decoded, the decoder will not have to extra
AT&T Corp.
Chen Wenpeng
Kenyon & Kenyon
Lee Thomas D.
LandOfFree
Method for improving data encoding and decoding efficiency 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 for improving data encoding and decoding efficiency, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for improving data encoding and decoding efficiency will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2612619