Preface
The MQ-coder is the binary adaptive multiplication-free arithmetic entropy coder used in JPEG2000. Under my opinion a really good reference is [1]. I implemented the algorithm in MATLAB for my Engineering Graduate Final Project. This was in June 2009 in the Image and Video Processing Group in the Communications and Signal Theory Department in the Technical University of Catalonia under the supervision of Prof. Philippe Salembier in collaboration with Julio C. Rolon.
Introduction
MQ-coder is the binary alphabet adaptive low-precision multiplication-free arithmetic coder used in JPEG2000. It is the evolution of the QM-coder used in JPEG and JBIG. There are many similarities between these two coders. The MQ-coder is adapted to the wavelet signal if the label set is the one specified in the standard. You can download the code.
Definition
Main Features
- Its input symbols are binary and each symbol must be associated to a label. This label is used to split up the bit stream into different kind of bits in order to take profit of different probability distributions: each label represents one of these distributions. So we are conditioning in order to decrease the entropy. In the encoding procedure, the label is used to know something a priori about the bit’s probability distribution.
- It is adaptive: the algorithm learns to estimate the pdf to improve its performance. This adaptation is implemented through the use of two tables (see section below).
- It uses low-precision arithmetics. There are 5 registers in the MQ coder: A and C are the lower bound and the upper bound of the interval, T is a byte register that accumulates bits from the coding procedure, t shows how many information bits are in the T register (it is used for the bit stuffing policy) and L register counts the byte stream length.
- It is a multiplication-free arithmetic coder. Therefore it is faster than other coders. Despite this is a desirable characteristic in a hardware scenario, it is not really important in a high-level programming language like MATLAB. However, we made that choice to be able to compare our results to JPEG2000, which uses that arithmetic coder as its entropy coder.
Performing adaptation: Dynamic and Static tables
But, how can MQ-coder adapt itself to the input signal? The statistics block is implemented as finite state machine (FSM) whose state diagram can be downloaded from here. There are two tables to take into account:
- Dynamic Table:
- Contains the information of each context. Each row represents a context and there are two columns. For each context, the first column represents the state of the Static Table in which the the context stays at that moment (the state in the FSM) and the second column shows the most probable symbol 0 or 1. The state of the Static Table represents the probability of that least probable symbol.
- Static Table:
- This table describes the update statistics decision algorithm and has four columns:
- In case we receive the most probable symbol and we must renormalize the interval, the algorithm may change the state in the Dynamic Table through this value.
- In case we receive the least probable symbol, the algorithm change the state in the Dynamic Table through this value
- In case we receive the least probable symbol, this number indicates if we have to change the role of MPS and LPS.
- This value represents the probability of the LPS.
In the Static Table, there are three set of states. The first set (from 1 to 6) is the initial set: all pointers of Dynamic Table must signal one of this states when we start coding. This first set is used to initially train the adaptive FSM. If the received symbols are not the expected one, the algorithm goes to the second set (states from 7 to 14). Finally the algorithm arrives to the third set (states from 15 to 46). The second set is an intermediate stage in order to train a little bit more the FSM. The third state corresponds to the stable zone of the table: when the algorithm arrives at this set, it is supposed to be trained. Once we arrive at the third set, we did not go back. The reader should observe that there is another set composed by only one state. This is used in JPEG2000, but we are not going to use it. One could gather more information in [1]. The state in the Static Table also affects to the output length. The higher the state is in the table, the lower the estimated probability (represented by the state) of the “least probable symbol” is, and the shorter the output length is.
Examples
To clarify a little bit the MQ-coder algorithm, we present two examples. In the first example (example A) the probability of the MPS is 0.99 and in the second example (example B) the probability of the MPS is 0.6. In both cases the MPS is 1. In both examples, the first two columns are the input symbol and the input label respectively. The third column is the state of the FSM in which the label stays before code the symbol. The fourth column is the expected symbol. The fifth is the probability of the Least Probable Symbol (expressed as a 32-bit integer) and the sixth is the same probability normalized to the unit interval. Notice that in both cases the MQ-coder estimates adaptively the probability distribution: in the example A the probability of the LPS is nearer 0.007, therefore, the probability of the MPS is nearer 0.993. In the example B, the mean estimated probability of the LPS is nearer 0.42 which corresponds to an estimated MPS probability near 0.58.
References
- Taubman D and M. Marcellin, JPEG2000: Image compression fundamentals, standards and practice, Kluwer academic publishers, 2001. [ bib ]
@book{Taubman-2001, author = "Taubman D, and Marcellin, M.", title = "JPEG2000: Image compression fundamentals, standards and practice", publisher = "Kluwer academic publishers", month = "November", year = "2001", }