Context adaptive coding of bi-level images

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

Abstract

With the advent of sequential arithmetic coding, the focus of highly efficient lossless data compression is placed on modelling the data. Rissanen's Algorithm Context provided an elegant solution to universal coding with optimal convergence rate. Context based arithmetic coding laid the grounds for the modern paradigm of data compression based on a modelling and a coding stage. One advantage of contexts is their flexibility, e.g. choosing a two-dimensional ("-D) context facilitates efficient image coding. The area of image coding has greatly been influenced by context adaptive coding, applied e.g. in the lossless JBIG bi-level image coding standard, and in the entropy coding of contemporary lossless and lossy image and video coding standards and schemes. The theoretical work and analysis of universal context based coding has addressed sequences of data and finite memory models as Markov chains and sources. This paper discusses relations between context based coding of images and the context formation in some image models. Image models include Markov random fields (MRF), which hav a non-causal description, and the special case of Pickard random fields, which are causal. These field represent generalizations to 2-D of a finite memory source. Further developments of causal image models, e.g. to approximate MRF, lead to considering hidden states in the context formation. These causal image models provides image coding models and they are here related to context based image coding. The entropy of the image models is also considered. Finally it is outlined how the techniques by duality may play a role in 2-D constrained coding for high density storage by switching the roles of encoding and decoding.
Original languageEnglish
Title of host publicationFestschrift in Honor of Jorma Rissanen
EditorsP. Grünwald, P. Myllymäki, I. Tabus, M. Weinberger, B. Yu
Number of pages320
Place of PublicationTampere, Finland
PublisherTempere University of Technology
Publication date2008
Pages213-228
ISBN (Print)95-21-51962-2
Publication statusPublished - 2008

Cite this