# - Acharya T.

ISBN 0-471-48422-9

**Download**(direct link)

**:**

**21**> 22 23 24 25 26 27 .. 100 >> Next

Since we are going to do the integer arithmetic, we need to replace the cumulative probability F(i) of the symbol with index i by an integer expression. We can replace this by the cumulative frequency Cum-Frequency(i). Define Ni as the number of times the symbol with index i occurs in a sequence of length Total-Count. Then Cum-Frequency(i) and F(i) can be expressed as

Cum-Frequency(i) = Nk

> .

- DUNk = Cum-Frequency(i) I W Total-Count Total-Count -

As a result, the ranges can be updated by the following expressions LOW _ LOW -(- №IGH — LOW + l)*Cum-FrequeTicy(i — 1) \

Total-Count I

HIGH — LOW 4- IGH~LOW + l)*CuTn-Frequency(i) _ ^ I

Total-Count '

If LOW > max-value+i , j.jjg range [LOW, HIGH) entirely belongs to the upper half of the interval [0, MAX-VALUE). If HIGH < M.M.-,Y.dMLE±i; the range [LOW, HIGH) entirely belongs to the lower half of the interval [0, MAX-VALUE).

Details of the integer arithmetic implementation of the binary arithmetic algorithm and the source code in C have been presented in [4]. The binary arithmetic coding became particularly useful for encoding binary images. Q-coder is a popular implementation of an adaptive binary arithmetic coding technique for coding bilevel images (i.e., the source symbols are 0 and 1 only) without requiring any multiplication [5]. The Q-coder approximates the intervals in such a way that it can avoid the multiplications and adjustment of the intervals in successive coding steps. It does not achieve optimum coding efficiency, but evidence shows that it can achieve coding efficiency within 2 to 6% of the ideal results. A variation of this technique called QM-coder has been adopted for entropy encoding in a mode of JPEG image compression standard [8]. The upcoming JPEG2000 standard uses another variation called the MQ-coder, a context-based adaptive arithmetic coder [9].

2.4.2 The QM-Coder

The QM-coder [8] is an enhancement of the Q-coder [5]. The QM-coder is the adaptive binary arithmetic coding algorithm used in the JBIG (Joint Bi-level

40 SOURCE CODING ALGORITHMS

Image Processing Group) standard for bi-level image compression. Although it follows the same principle of arithmetic coding, QM-coder is designed for simplicity and speed. The input symbols to the QM-coder are single bits of the bi-level image and it is free from multiplications by approximating the computation of intervals by fixed-precision integer arithmetic operations (addition, subtraction, and shift operations only).

The main idea behind the QM-coder is to map the input bits into more probable symbol (MPS) and less probable symbol (LPS). This can be explained in terms of a black-and-white image. If bits 0 and 1 represent the black and white pixels respectively, then in a mostly black region 0 will be mapped to MPS and 1 will be mapped to LPS, whereas in a mostly white region 1 will be mapped to MPS and 0 will be mapped to LPS. Before the next bit is input, the QM-coder determines which bit is MPS (the other bit is LPS) and compresses this information instead of the input bit directly. During the decoding process, the QM-decoder decodes whether the bit just decoded is MPS or LPS and then converts this information to actual binary pixel value. Hence the QM-coder assigns the intervals to the MPS and LPS symbols instead of the 0 or 1 input bit. If the probability estimate of LPS is Q, then the probability estimate of MPS is (1 — Q) because there are only two symbols in the alphabet. For interval A, the QM-coder divides the interval into two subintervals according to the value of Q. The sizes of the subintervals assigned to LPS and MPS are AQ and A(\ — Q) respectively as shown in Figure 2.5.

LPS subinterval = Q x A Q

MPS subinterval = (1 - Q) A s? A-Q

Fig. 2.5 Subinterval assignment in QM-coder.

In QM-coder, the value of A is always assumed to maintain close to 1. As a result, the subintervals of LPS and MPS can be approximated to AQ « Q and A(\ — Q) « A — Q respectively and hence the multiplication is avoided. The subinterval of LPS is placed above the subinterval of MPS as shown in Figure 2.5. Accordingly, the MPS and LPS are assigned the subintervals [0, A — Q) and [A — Q, A) respectively. Actually the value of A is always maintained within the range 1.5 > A > 0.75. Whenever the value of A drops below

A-Q

I

BINARY ARITHMETIC CODING 41

0.75 during the encoding process, the renormalization is done by repeated doubling (shifting left) A until it is greater than or equal to 0.75. Whenever we renormalize A, we need to apply the same renormalization to C as well to keep these two parameters in sync.

We denote the output code stream of the QM-coder by C. Ideally C can be any value within the current interval as we explained in the arithmetic coding algorithm in the previous section. However, for simplicity of implementation, the QM-coder points C at the bottom of the current interval. If the current input is MPS (or LPS), C is updated by adding the bottom of the MPS (or LPS) subinterval to the current value of C. Since the bottom of MPS subinterval is 0, C actually remains unchanged when MPS is encoded. During encoding of LPS, C is updated by adding A — Q to the current value of C since A — Q is the bottom of the LPS subinterval as shown in Figure 2.5. It should be noted that the encoder is initialized with the A = 1 at the beginning of the encoding process. Hence the encoding algorithm can be described as follows.

**21**> 22 23 24 25 26 27 .. 100 >> Next