Research Document Imaging Image Compression JBIG MQ-coder

Search

The MQ-coder
Eugene Ageenko

The MQ-coder is an approximate implementation of arithmetic coding tailored for binary data. It's pre-ancestor, Q-coder, has similar working principles and is introduced in [PMLA88]. The sub-optimality of the coder is compensated by a sophisticated automaton-based probability estimation, which provides fast adaptation to the source data. Instead of maintaining pixel counts, the estimation process is implemented as a state automaton consisting of 94 states. The automaton is a Markov-chain containing one state for each probability estimate. The states are organized in rows that are ordered by the level of adaptation. The adaptation process starts from nearly uniform blank model represented by the state 0.

The statistical model is usually integrated with the coder. The model consists of the pointers to the automaton states, one per context. The encoder (and decoder) estimates the model dynamically during the compression (decompression). At the beginning, the coder has no a priori information about the image, and nearly equal initial probability distribution is assumed, represented by the zero-state. After the pixel is coded, the model is updated by assigning new, updated, state index for the pixel context.

The probability estimation is derived from the arithmetic coder renormalization and is based on the Bayesian estimation concept [PM88]. The renormalization of the coding interval occurs always after a less-probable symbol (LPS), and if necessary, after a more-probable symbol (MPS). After each MPS renormalization, the automaton makes transition to the next state situated to the right in the same row, having a smaller LPS probability. After each LPS renormalization, a transition is made to the state with a larger LPS probability, which is the appropriate state in the row at the next level in case of the transient state, or to the preceding state in the same row in case of non-transient states. Transient states are, therefore, visited only during the learning stage, and the pointers stabilize eventually to the non-transient states. If the statistics change later, the non-transient states can be re-entered from other non-transient states, making local adaptation possible.

Figure 1. Spatial organization of the state automaton in MQ-coder and the transition sketch for the fast-attack states. Because of the mirror symmetry regarding the change in sense of LPS and MPS, only half of the states are depicted.

Figure 2. Spatial organization of the state automaton in QM-coder (adopted in JBIG). Automaton has 226 states in total, only half of the states are depicted.