Hierarchical Lossy Bilevel Image Compression Based on Cutset Sampling

Shengxin Zha, Thrasyvoulos N. Pappas*, David L. Neuhoff

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We consider lossy compression of a broad class of bilevel images that satisfy the smoothness criterion, namely, images in which the black and white regions are separated by smooth or piecewise smooth boundaries, and especially lossy compression of complex bilevel images in this class. We propose a new hierarchical compression approach that extends the previously proposed fixed-grid lossy cutset coding (LCC) technique by adapting the grid size to local image detail. LCC was claimed to have the best rate-distortion performance of any lossy compression technique in the given image class, but cannot take advantage of detail variations across an image. The key advantages of the hierarchical LCC (HLCC) is that, by adapting to local detail, it provides constant quality controlled by a single parameter (distortion threshold), independent of image content, and better overall visual quality and rate-distortion performance, over a wider range of bitrates. We also introduce several other enhancements of LCC that improve reconstruction accuracy and perceptual quality. These include the use of multiple connection bits that provide structural information by specifying which black (or white) runs on the boundary of a block must be connected, a boundary presmoothing step, stricter connectivity constraints, and more elaborate probability estimation for arithmetic coding. We also propose a progressive variation that refines the image reconstruction as more bits are transmitted, with very small additional overhead. Experimental results with a wide variety of, and especially complex, bilevel images in the given class confirm that the proposed techniques provide substantially better visual quality and rate-distortion performance than existing lossy bilevel compression techniques, at bitrates lower than lossless compression with the JBIG or JBIG2 standards.

Original languageEnglish (US)
Article number9307275
Pages (from-to)1527-1541
Number of pages15
JournalIEEE Transactions on Image Processing
StatePublished - 2021


  • JBIG2
  • Lossy bilevel image coding
  • Markov random fields (MRFs)
  • constant quality
  • cutset sampling

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Hierarchical Lossy Bilevel Image Compression Based on Cutset Sampling'. Together they form a unique fingerprint.

Cite this