Lossy cutset coding of bilevel images based on markov random fields

Matthew G. Reyes, David L. Neuhoff, Thrasyvoulos N. Pappas

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


An effective, low complexity method for lossy compression of scenic bilevel images, called lossy cutset coding, is proposed based on a Markov random field model. It operates by losslessly encoding pixels in a square grid of lines, which is a cutset with respect to a Markov random field model, and preserves key structural information, such as borders between black and white regions. Relying on the Markov random field model, the decoder takes a MAP approach to reconstructing the interior of each grid block from the pixels on its boundary, thereby creating a piecewise smooth image that is consistent with the encoded grid pixels. The MAP rule, which reduces to finding the block interiors with fewest black-white transitions, is directly implementable for the most commonly occurring block boundaries, thereby avoiding the need for brute force or iterative solutions. Experimental results demonstrate that the new method is computationally simple, outperforms the current lossy compression technique most suited to scenic bilevel images, and provides substantially lower rates than lossless techniques, e.g., JBIG, with little loss in perceived image quality.

Original languageEnglish (US)
Article number6725607
Pages (from-to)1652-1665
Number of pages14
JournalIEEE Transactions on Image Processing
Issue number4
StatePublished - Apr 2014


  • Ising model
  • Lossy bilevel image coding
  • MAP
  • Markov random fields
  • arithmetic coding
  • image interpolation
  • image reconstruction
  • lossy bilevel image compression
  • odd bonds

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Lossy cutset coding of bilevel images based on markov random fields'. Together they form a unique fingerprint.

Cite this