0, the range of possible actual values of the coefficient is [a - S, a + S). If a < 0, the range of possible actual values of the coefficient is (a - S, a + S]. If a = 0, the coefficient is not active, and the range of possible actual values of the coefficient is (-2S, 2S). When the value of a given coefficient is updated, there are three cases. 1. If the coefficient is not active (a = 0), then there are three possibilities for the next current interval: (-2S,-S], (-S,S), or [S, 2S). If the coefficient remains not active, then the next interval is (-S, S). Otherwise, the sign of the coefficient is decoded to choose between the other two intervals. If the coefficient is active and a > 0, then there are two possibilities for the next current interval: [a - S, a) or [a, a + S). The next decision for the coefficient is the increase coefficient absolute value decision. If this decision is , then [a, a + S) is the next interval. If the decision is , then [a - S, a) is the next interval. 1999 04 29 15:46 EDT ( ) 1999 AT&T > 0, decrement np by 1. If the value returned by the Z -Coder for the activate coefficient decision is 1, then the value of the activate coefficient decision is . If the value returned by the Z -Coder is 0, then the value of the activate coefficient decision is The decoding of the sign s+ of a newly activated coefficient uses the pass-through mode of the Z -Coder. If the value returned by the Z -Coder is 1, then s+ = -1. If the value returned by the Z -Coder is 0, then s+ = +1. Each of the 16 Z -Coder contexts for the activate coefficients decision for each color component is initially set to 0. 7.6.5 Previously-active-coefficient-decoding pass. For all coefficients in the block band, the following procedure is followed: If the coefficient's ACTIVE flag is S[ , the increase coefficient absolute value decision is decoded. If the decision , the absolute value of the coefficient is reduced by half of the coefficient's step size. If the decision is , the absolute value of the coefficient is increased by half of the coefficient's step size. A step size of i is a special case. If the step size is i and the decision is , the absolute value of the coefficient is reduced by 1. If the step size is i and the decision is the value of the coefficient is unchanged. 7.6.5.1 Arithmetic decoding. For each color component, there is a single context for use in decoding the increase coefficient absolute value decision. This context is used to decode the increase coefficient absolute value decision if the absolute value of the coefficient is less than or equal to 3 times the value of the step size for the coefficient. Otherwise, the pass-through mode of the Z -Coder is used. (Note: the effect of this test is that only the second most significant bit of a coefficient's value is decoded using this context; other less significant bits are decoded using the pass-through mode of the Z -Coder, with no context.) Whether the context or the pass-through mode is used, if the value returned by the Z Coder for the increase coefficient absolute value decision is 1, then the value of the increase coefficient absolute value decision is . If the value returned by the Z -Coder is 0, then the value of the increase coefficient absolute value decision is The Z -Coder context for the increase coefficient absolute value decision for each color component is initially set to 0. 7.7 Image reconstruction At any time during the decoding process, an image may be reconstructed from the current values of the wavelet coefficients already decoded. The wavelet coefficients are stored in three two-dimensional arrays one for each of the Y, Cb, and Cr color components. Each array has one entry for each image block. Each entry itself is a 1024-element one-dimensional array. The elements of each one-dimensional array are the wavelet coefficients. The wavelet coefficients are signed fixed-point numbers with six fractional bits. 7.7.1 Sequence of operations To reconstruct the image from the coefficients, the following steps must be performed: 1999 04 29 15:46 EDT 1999 AT&T > 0 v= In[-1 ifn < O. At the end of the process of decoding an integer, v is converted to n, the value of the decoded integer. The value of an integer is coded by making a sequence of binary decisions, each one narrowing the set of possible values that the integer can possibly take. The decisions are based on traversing a binary decision tree to one of its leaves. Note: although the tree conceptually has a large number of nodes, it is possible in an implementation to allocate memory only for those nodes actually traversed. Decoding proceeds in four phases. 8.2.2.1 Phase 1. Phase 1 determines the sign of n. A value of 0 returned by the Z -Coder means that n < 0. A value of 1 returned by the Z -Coder means that n _> 0. 1999 AT&T 1999 04 29 15:46 EDT > D){Z:=D} if(C > Z) { B := K(i)(rood2) if (A _> Oa:(i)) { K(i) = A:=Z else { := i - (K(i)(mod2)) A := A + 0xl0000 - Z C := C+ 0xl0000 - Z while (A A := C := _> 0x8000) { A + A- OxtOOO0 C + C - OxtOOO0 + next code bit return B Figure 4: Decoder for Z -Coder. Line 10. This line determines the value of kPS from the odd/even parity of the probability state index. Line 13. An LPS always triggers an update of the probability state index. Lines 15-18. When the values in the registers are too large, they must be renormalized. Lines 1ti-17. A+A and C+C may be accomplished by left shifts, leaving the least significant bit equal to 0. Line 17. The least significant bit of C is filled with the next bit from the input stream. Bits are taken from each octet in the input stream most significant bit first. 9.4 Pass-through decoding Figure 5 shows the steps involved in decoding a single binary decision using the Z -Coder in pass-through mode. No input is required. No context is involved. No probability state index values are updated. The output from the decoder is the single bit B. 9.4.1 Notes on specific lines of Figure 5 Line 1. The division is a right shift, discarding the three least significant bits. Lines 2-5. These lines are executed when the decoded bit is 0. Lines 11-10. These lines are executed when the decoded bit is 1. Lines 11-14. When the values in the registers are too large, they must be renormalized. 1999 04 29 15:46 EDT 1999 AT&T > Z) { 3 B:=0 4 A:=Z 6 else { ? B:=I 8 A := A + 0xl0000 - Z 9 C := C + 0xl0000 -- Z lo ) 11 while (A _ Ox8000) ( 12 A := A + A - 0xl0000 13 C := C + C - 0xl0000 + next code bit 4 } 15 return B Figure 5: Decoder for Z -Coder operating in pass-through mode. Lines 12-13. A+A and C+C may be accomplished by left shifts, leaving the least significant bit equal to 0. Line 13. The least significant bit of C is filled with the next bit from the input stream. Bits are taken from each octet in the input stream most significant bit first. 1999 AT&T 1999 04 29 15:46 EDT >
Back to Index Specification of DjVu Image Compression Format
Version of 1999-04-29 15:46 EDT Copyright (c) 1999 by AT&T
Digital Library Home