A typical arithmetic coder consists of three steps: range calculation, renormalization, and probability model updating. In this paper, we propose and analyze from an information theoretic point of view a greedy renormalization method, which has two components: greedy thresholding and greedy outputting. The method significantly reduces the computational complexity of the renormalization step of arithmetic coding by (1) using the greedy thresholding to minimize the number of renormalizations required to encode a sequence and (2) using the greedy outputting to minimize the number of operations within each renormalization. The method is particularly suitable for binary arithmetic coding (BAC). Two BAC algorithms based on this method are presented. The first algorithm replaces the renormalization method in the TOIS BAC with the greedy renormalization method, and keeps other parts of the TOIS BAC unchanged. For binary independent and identically distributed (i.i.d.) sources with the probability of the less probable symbol ranging from --, over gain in speed (on average), and less than loss in compression rate (in the worst case) are observed in the experiments. The second algorithm combines the greedy renormalization method with the QM-Coder. On an average, gain in speed and gain in compression rate are observed in the experiments.

Summary form only given. A novel method that significantly reduces the computational complexity of the re-normalization step of arithmetic coding is described. Called greedy re-normalization, the method involves a reduction to both the number of re-normalizations required to encode and the number of operations within each re-normalization. To reduce the number of re-normalizations in the encoding sequence, the method adopts a dynamic re-normalization criterion. Experimental results show that the proposed greedy re-normalization method indeed improved the speed of arithmetic coding.

In this paper, the multilevel pattern matching (MPM) code for compression of one-dimensional (1D) sequences is first generalized to compress two-dimensional (2D) images, resulting in a 2D multilevel pattern matching (MPM) code. It is shown that among all images of n pixels, the worst case redundancy of the 2D MPM code against any finite-template-based arithmetic code is O(1//spl radic/logn). This result contrasts unfavorably with the fact that among all 1D sequences of length n, the MPM code has a worst case redundancy of O(1/logn) against any finite-state arithmetic code; this is caused by the so-called 2D boundary effect. To alleviate the 2D boundary effect, we extend the 2D MPM code to the case of context modeling, yielding a context-dependent 2D MPM code. It is shown that among all images of n pixels, the context-dependent 2D MPM code has an O(1/logn) worst case redundancy against any finite-template-based arithmetic code satisfying a mild condition; this redundancy is better than that of the 2D MPM code without context models. Experimental results demonstrate that the context-dependent 2D MPM code significantly outperforms the 2D MPM code without context models for bi-level images. It is also demonstrated that, in terms of compression rates, the context-dependent 2D MPM code performs significantly better than the progressive coding mode of JBIG1 for both textual and bi-level images, and better than or comparably to the sequential coding mode of JBIG1 and JBIG2. In addition to its excellent compression performance, the context-dependent 2D MPM code allows progressive transmission of images.