An algorithm for compression of bilevel images

This paper presents the block arithmetic coding for image compression (BACIC) algorithm: a new method for lossless bilevel image compression which can replace JBIG, the current standard for bilevel image compression. BACIC uses the block arithmetic coder (BAC): a simple, efficient, easy-to-implement, variable-to-fixed arithmetic coder, to encode images. BACIC models its probability estimates adaptively based on a 12-bit context of previous pixel values; the 12-bit context serves as an index into a probability table whose entries are used to compute p₁ (the probability of a bit equaling one), the probability measure BAC needs to compute a codeword. In contrast, the Joint Bilevel Image Experts Group (JBIG) uses a patented arithmetic coder, the IBM QM-coder, to compress image data and a predetermined probability table to estimate its probability measures. JBIG, though, has not get been commercially implemented; instead, JBIG´s predecessor, the Group 3 fax (G3), continues to be used. BACIC achieves compression ratios comparable to JBIG´s and is introduced as an alternative to the JBIG and G3 algorithms. BACIC´s overall compression ratio is 19.0 for the eight CCITT test images (compared to JBIG´s 19.6 and G3´s 7.7), is 16.0 for 20 additional business-type documents (compared to JBIG´s 16.0 and G3´s 6.74), and is 3.07 for halftone images (compared to JBIG´s 2.75 and G3´s 0.50)