KDE 3.5 API Reference kviewshell
ZPCodec.h File Reference
#include "GContainer.h"
Go to the source code of this file.
Classes | |
| struct | ZPCodec::Table |
| class | ZPCodec |
| Performs ZP-Coder encoding and decoding. More... | |
Typedefs | |
ZPCodec.h | |
Files #"ZPCodec.h"# and #"ZPCodec.cpp"# implement a fast binary adaptive quasi-arithmetic coder named ZP-Coder. Because of its speed and convenience, the ZP-Coder is used in several parts of the DjVu reference library (See {BSByteStream.h}, {JB2Image.h}, {IW44Image.h}). The following comments avoid the theory (see the historical remarks for useful pointers) and concentrate on the user perspective on the ZP-Coder. { Introduction} --- Encoding consists of transforming a sequence of {message bits} into a sequence of {code bits}. Decoding consists of retrieving the message bits using only the code bits. We can make the code smaller than the message as soon as we can predict a message bit on the basis of a {coding context} composed of previously encoded or decoded bits. If the prediction is always correct, we do not even need to encode the message bit. If the prediction is totally unreliable, we need to generate one code bit in order to unambiguously specify the message bit. In other words, the more reliable the prediction, the more compression we get. The ZP-Coder handles prediction by means of {context variables} (see {BitContext}). There must be a context variable for each possible combination of context bits. Both the encoder and the decoder use same context variable for coding each message bit. For instance, we can code a binary image by successively coding all the pixels (the message bits) in row and column order. It is reasonable to assume that each pixel can be reasonably well predicted by looking at a few (say 10) neighboring pixels located above and to the left of the current pixel. Since these 10 pixels make 1024 combinations, we need 1024 context variables. Each pixel is encoded using the context variable corresponding to the values of the 10 neighboring pixels. Each pixel will be decoded by specifying the same context variable corresponding to the values of these 10 pixels. This is possible because these 10 pixels (located above and to the left) have already been decoded and therefore are known by the decoder program. The context variables are initially set to zero, which mean that we do not know yet how to predict the current message bit on the basis of the context bits. While coding the message bits, the ZP-Coder automatically estimates the frequencies of #0s and #1s coded using each context variable. These frequencies actually provide a prediction (the most probable bit value) and an estimation of the prediction reliability (how often the prediction was correct in the past). All this statistical information is stored into the context variable after coding each bit. In other words, the more we code bits within a particular context, the better the ZP-Coder adapts its prediction model, and the more compression we can obtain. All this adaptation works indeed because both the encoder program and the decoder program are always synchronized. Both the encoder and the decoder see the same message bits encoded (or decoded) with the same context variables. Both the encoder and the decoder apply the same rules to update the context variables and improve the predictors. Both the encoder and the decoder programs use the same predictors for any given message bit. The decoder could not work if this was not the case. Just before encoding a message bit, all the context variables in the encoder program contain certain values. Just before decoding this message bit, all the context variables in the decoder program must contain the same values as for the encoder program. This is guaranteed as long as each prediction only depends on already coded bits: {the coding context, on which the each prediction is based, must be composed of message bits which have already been coded. } { Usage} --- Once you know how to organize the predictions (i.e. which coding context to use, how many context variables to initialize, etc.), using the ZP-Coder is straightforward (see {ZPCodec Examples}): {itemize} The {encoder program} allocates context variables and initializes them to zero. It then constructs a {ZPCodec} object for encoding. For each message bit, the encoder program retrieves the context bits, selects a context variable on the basis of the context bits and calls member function {ZPCodec::encoder} with the message bit and a reference to the context variable. The {decoder program} allocates context variables and initializes them to zero. It then constructs a {ZPCodec} object for decoding. For each message bit, the decoder program retrieves the context bits, selects a context variable on the basis of the context bits and calls member function {ZPCodec::decoder} with a reference to the context variable. This function returns the message bit. {itemize} Functions encoder# and decoder# only require a few machine cycles to perform two essential tasks, namely {coding} and {context adaptation}. Function decoder# often returns after two arithmetic operations only. To make your program fast, you just need to feed message bits and context variables fast enough. { History} --- The ZP-Coder is similar in function and performance to the seminal Q-Coder (Pennebaker, Mitchell, Langdon, Arps, IBM J. Res Dev. 32, 1988). An improved version of the Q-Coder, named QM-Coder, has been described in certain parts of the JPEG standard. Unfortunate patent policies have made these coders very difficult to use in general purpose applications. The Z-Coder is constructed using a new approach based on an extension of the Golomb codes (Bottou, Howard, Bengio, IEEE DCC 98, 1998 [DjVu]{http://www.research.att.com/~leonb/DJVU/bottou-howard-bengio/} [PostScript]{http://www.research.att.com/~leonb/PS/bottou-howard-bengio.ps.gz}) This new approach does not infringe the QM-Coder patents. Unfortunately the Z-Coder is dangerously close to the patented Arithmetic MEL Coder. Therefore we wrote the ZP-Coder (pronounce Zee-Prime Coder) which we believe is clear of legal problems. Needless to say, AT&T has patents pending for both the Z-Coder and the ZP-Coder, licenced to LizardTech. The good news however is that we can grant a license to use the ZP-Coder in ``free software'' without further complication. See the Copyright for more information. Binary adaptive quasi-arithmetic coder.
| |
| typedef unsigned char | BitContext |
Typedef Documentation
| typedef unsigned char BitContext |
Context variable.
Variables of type BitContext# hold a single byte describing how to encode or decode message bits with similar statistical properties. This single byte simultaneously represents the current estimate of the bit probability distribution (which is determined by the frequencies of #1s and #0s already coded with this context) and the confidence in this estimate (which determines how fast the estimate can change.)
A coding program typically allocates hundreds of context variables. Each coding context is initialized to zero before encoding or decoding. Value zero represents equal probabilities for #1s and #0s with a minimal confidence and therefore a maximum adaptation speed. Each message bit is encoded using a coding context determined as a function of previously encoded message bits. The decoder therefore can examine the previously decoded message bits and decode the current bit using the same context as the encoder. This is critical for proper decoding.
