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

Area of Science:

• Digital image processing
• Data compression algorithms
• Information theory

Background:

• Existing standards like JBIG efficiently compress bilevel images but can be improved for specific content types.
• Bilevel image compression often involves trade-offs between compression ratio and fidelity.
• Half-toned images present unique challenges for standard compression techniques.

Purpose of the Study:

• To develop general and unified algorithms for both lossy and lossless compression of bilevel images.
• To enhance compression efficiency, particularly for half-toned images, by introducing controlled loss.
• To propose a new coding method as part of the emerging JBIG2 international standard.

Main Methods:

• Arithmetic coding applied to conditional probabilities.
• Utilization of templates and a more general free tree for conditioning.
• Introduction of controlled loss via a rate-distortion controlled greedy pixel flipping preprocess.
• Template-based refinement coding for lossy-to-lossless transitions.

Main Results:

• Achieved compression increases of up to four times compared to JBIG for half-toned images by introducing minimal loss.
• Lossy, lossless, and refinement decoding speeds are less than twice as slow as JBIG.
• Lossless encoding speed is also less than twice as slow as JBIG.
• The proposed algorithms are primarily targeted at half-toned images, supplementing existing pattern matching techniques.

Conclusions:

• The developed algorithms provide a unified approach to lossy/lossless bilevel image compression.
• Controlled introduction of loss significantly boosts compression for half-toned images.
• The method is proposed for integration into the JBIG2 standard, offering competitive performance and speed.