Lossless Image Compression with a Codebook of Block Scans

Nasir D. Memon, Khalid Sayood, Spyros S. Magliveras

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


When applying predictive compression on image data there is an implicit assumption that the image is scanned in a particular order. Clearly, depending on the image, a different scanning order may give better compression. In earlier work, we had defined the notion of a prediction tree (or scan) which defines a scanning order for an image. An image can be decorrelated by taking differences among adjacent pixels along any traversal of a scan. Given an image, an optimal scan that minimizes the absolute sum of the differences encountered can be computed efficiently. However, the number of bits required to encode an optimal scan turns out to be prohibitive for most applications. In this paper we present a prediction scheme that partitions an image into blocks and for each block selects a scan from a codebook of scans such that the resulting prediction error is minimized. Techniques based on clustering are developed for the design of a codebook of scans. Design of both semiadaptive and adaptive codebooks is considered. We also combine the new prediction scheme with an effective error modeling scheme. Implementation results are then given, which compare very favorably with the JPEG lossless compression standard.

Original languageEnglish (US)
Pages (from-to)24-30
Number of pages7
JournalIEEE Journal on Selected Areas in Communications
Issue number1
StatePublished - Jan 1995
Externally publishedYes

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Lossless Image Compression with a Codebook of Block Scans'. Together they form a unique fingerprint.

Cite this