Full Record

New Search | Similar Records

Title Cutset Based Processing and Compression of Markov Random Fields.
Publication Date
Date Accessioned
Degree PhD
Discipline/Department Electrical Engineering: Systems
Degree Level doctoral
University/Publisher University of Michigan
Abstract This thesis presents results related to the compression a Markov random field (MRF) $bfX$ defined on a graph $G=(V,E)$ by first losslessly compressing a cutset of sites $U$ and then either losslessly compressing or estimating the remaining sites conditioned on the cutset. We present analytical solutions to the MAP estimate of a block conditioned on the commonly occurring boundaries with two or fewer runs of black, for both 4 pt. and 8 pt. grid graphs. Using these results we empirically demonstrate that Max-Product Loopy Belief Propagation converges to the correct results. We present a simple adaptive Arithmetic Encoding (AC) based method for losslessly compressing a square grid cutset of a binary image and, applying the Ising reconstruction results, show that the resulting lossy image coder is competitive compared to other methods. We present rigorous development of Local Conditioning for MRFs, algorithm for exact inference in cyclic graphs. We prove that the entropy of family of MRFs is monotone increasing in the associated exponential parameters and that the exponential parameters for the moment-matching reduced MRF induced by $U$ for a subset of nodes are component-wise greater than the original exponential parameters within $U$. We also show that the divergence between an MRF induced by exponential parameter $theta$ and another induced by $theta'$ is monotone increasing in $theta'$. Furthermore, we prove that the divergence between the marginal distribution for $bfX$ and reduced MRF follows a Pythagorean decomposition, providing reduced MRF analogue to well-known result in information geometry. We present efficient algorithms for optimal AC based lossless compression of acyclic and EASY cyclic MRFs, and use these for suboptimal lossless compression for HARD cyclic MRFs, called {em Reduced Cutset Coding}. Experiments with RCC on homogeneous Ising models both verify nearly optimal performance and provide estimates of upper and lower bounds to entropy.
Subjects/Keywords Markov Random Fields; Source Coding; Belief Propagation; Cutset; Ising Model; Monotonicity; Electrical Engineering; Engineering
Contributors Neuhoff, David L. (committee member); Blass, Andreas R. (committee member); Hero Iii, Alfred O. (committee member); Pappas, Thrasyvoulos N. (committee member); Sadanandarao, Sandeep P. (committee member)
Language en
Rights Unrestricted
Country of Publication us
Record ID handle:2027.42/84510
Repository umich
Date Indexed 2020-09-09
Grantor University of Michigan, Horace H. Rackham School of Graduate Studies
Issued Date 2011-01-01 00:00:00
Note [thesisdegreename] Ph.D.; [thesisdegreediscipline] Electrical Engineering: Systems; [thesisdegreegrantor] University of Michigan, Horace H. Rackham School of Graduate Studies; [bitstreamurl] http://deepblue.lib.umich.edu/bitstream/2027.42/84510/1/mgreyes_1.pdf;

Sample Images