Lossless, near-lossless, and refinement coding of bilevel images

We present general and unified algorithms for lossy/lossless coding of bile vel images. The compression is realized by applying arithmetic coding to co nditional probabilities. As in the current JBIG standard the conditioning m ay be specified by a template. For better compression, the more general fre e tree may be used. Loss may be introduced in a preprocess on the encoding side to increase compression. The primary algorithm is a rate-distortion co ntrolled greedy flipping of pixels. Though being general, the algorithms ar e primarily aimed at material containing halftoned images as a supplement t o the specialized soft pattern matching techniques that work better for tex t. Template based refinement coding is applied for lossy-to-lossless refine ment. Introducing only a small amount of loss in halftoned test images, com pression is increased by up to a factor of four compared with JBIG. Lossy, lossless, and refinement decoding speed and lossless encoding speed are les s than a factor of two slower than JBIG. The (de)coding method is proposed as part of JBIG2, an emerging international standard for lossless/lossy com pression of bilevel images.