Maximizing entropy of image models for 2-D constrained coding

Søren Forchhammer, Matteo Danieli, Nino Burini, Marco Zamarin, Ann Ukhanova

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

167 Downloads (Pure)

Abstract

This paper considers estimating and maximizing the entropy of two-dimensional (2-D) fields with application to 2-D constrained coding. We consider Markov random fields (MRF), which have a non-causal description, and the special case of Pickard random fields (PRF). The PRF are 2-D causal finite context models, which define stationary probability distributions on finite rectangles and thus allow for calculation of the entropy. We consider two binary constraints and revisit the hard square constraint given by forbidding neighboring 1s and provide novel results for the constraint that no uniform 2 £ 2 squares contains all 0s or all 1s. The maximum values of the entropy for the constraints are estimated and binary PRF satisfying the constraint are characterized and optimized w.r.t. the entropy. The maximum binary PRF entropy is 0.839 bits/symbol for the no uniform squares constraint. The entropy of the Markov random field defined by the 2-D constraint is estimated to be (upper bounded by) 0.8570 bits/symbol using the iterative technique of Belief Propagation on 2 £ 2 finite lattices. Based on combinatorial bounding techniques the maximum entropy for the constraint was determined to be 0.848.
Original languageEnglish
Title of host publicationProceedings WITMSE
Number of pages6
Publication date2010
Publication statusPublished - 2010
Event3rd Workshop on Information Theoretic Methods in Science and Engineering - Tampere University of Technology, Tampere, Finland
Duration: 16 Aug 201018 Aug 2010
Conference number: 3
http://sp.cs.tut.fi/WITMSE10/

Workshop

Workshop3rd Workshop on Information Theoretic Methods in Science and Engineering
Number3
LocationTampere University of Technology
CountryFinland
CityTampere
Period16/08/201018/08/2010
Internet address

Cite this