Lossless Reduced Cutset Coding of Markov Random Fields
Matthew G. Reyes, David L. Neuhoff · 2010
This paper presents Reduced Cutset Coding, a new Arithmetic Coding (AC) based approach to lossless compression of Markov random fields. In recent work, the authors presented an efficient AC based approach to encoding acyclic MRFs and described a Local Conditioning (LC) based approach to encoding cyclic MRFs. In the present work, we introduce an algorithm for AC encoding of a cyclic MRF for which the complexity of the LC method of, or the acyclic MRF algorithm of combined with the Junction Tree (JT) algorithm, is too large. For encoding an MRF based on a cyclic graph G = (V,E), a cutset U ¿ V is selected such that the subgraph GUinduced by U, and each of the components of G\U, are tractable to either LC or JT. Then, the cutset variables XUare AC encoded with coding distributions based on a reduced MRF defined on GU, and the remaining components XV\Uof XVare optimally AC encoded conditioned on XU. The increase in rate over optimal encoding of XVis the normalized divergence between the marginal distribution of XUand the reduced MRF on GUused for the AC encoding. We show this follows a Pythagorean decomposition and, additionally, that the optimal exponential parameter for the reduced MRF on GUis the one that preserves the moments from the marginal distribution. We also show that the rate of encoding XUwith this moment-matching exponential parameter is equal to the entropy of the reduced MRF with this moment-matching parameter. We illustrate the concepts of our approach by encoding a typical image from an Ising model with a cutset consisting of evenly spaced rows. The performance on this image is similar to that of JBIG.