In BTPC 2, the coding is integrated. The main reason for this is to exploit structural redundancy in the method. First, different bands are quantized differently, so their output codeword histograms are (usually) different. Integrated coders can be reset at the start of each band to avoid a lag in adapting to the new statistics. Second, the binary tree structure leads to potential redundancy: A leaf codeword means that the current point and all its descendants are zero. Now if a zero-valued parent has a leaf as its left child, the right child cannot be a leaf (otherwise, the parent would have been a leaf). Consequently, right children can be coded with different statistical models, depending on the values of their parents and siblings.
The entropy coding used in BTPC is adaptive Huffman coding [15]. Huffman and arithmetic coding are both superior to dictionary (Ziv-Lempel) compressors in this context, because BTPC models the source efficiently, and the entropy coder needs only 0-order statistics (symbol counts). Arithmetic coding compresses more than Huffman - in preliminary tests it showed improvements of 5 - 10% - but was rejected for BTPC 2 for three reasons. First, arithmetic coding is subject to patent restrictions while Huffman coding is not; second, Huffman coding is faster; third, evaluation of BTPC in these documents and elsewhere relies on comparison with the Independent JPEG group's implementation of JPEG [14]. That implementation uses Huffman coding only, and a fair comparison should therefore use Huffman coding too.
In adaptive coding, the codebook used for the current symbol is generated from the statistics of symbols previously coded. Gallager [15] included an adaptation time constant which periodically rescaled counter values so that recently coded symbols have more effect on the statistics than those coded earlier. However, BTPC's adaptive Huffman coders are based on Unix compact which does not use such a time constant. Thus, BTPC does not adapt to local sample statistics; rather it codes on the basis of all values so far in the current band. Improvements to adaptive Huffman coding by Knuth [16] and Vitter [17] are not used in BTPC.
In BTPC 2 three adaptive Huffman coders are used for each band. Coder 0 codes all left siblings, coder 1 is used for "normal" right siblings and coder 3 is used for right siblings whose parent is 0 and whose sibling is a leaf.
Next (Implementation) | Previous (Quantization) | Top (BTPC)