Lossless Coding of Markov Random Fields with Complex Cliques
Loading...
Authors
Wu, Szu Kuan Steven
Date
2013-08-14
Type
thesis
Language
eng
Keyword
Markov Random Fields , Applied Probability , Belief Propagation , Reduced Cutset Coding , Information Theory , Complex Cliques , Computer Science
Alternative Title
Abstract
The topic of Markov Random Fields (MRFs) has been well studied in the past, and has found practical use in various image processing, and machine learning applications. Where coding is concerned, MRF specific schemes have been largely unexplored. In this thesis, an overview is given of recent developments and challenges in the lossless coding of MRFs. Specifically, we concentrate on difficulties caused by computational intractability due to the partition function of the MRF. One proposed solution to this problem is to segment the MRF with a cutset, and encode the components separately. Using this method, arithmetic coding is possible via the Belief Propagation (BP) algorithm. We consider two cases of the BP algorithm: MRFs with only simple cliques, and MRFs with complex cliques. In the latter case, we study a minimum radius condition requirement for ensuring that all cliques are accounted for during coding. This condition also simplifies the process of conditioning on observed sites. Finally, using these results, we develop a systematic procedure of clustering and choosing cutsets.
Description
Thesis (Master, Mathematics & Statistics) -- Queen's University, 2013-08-12 14:50:00.596
Citation
Publisher
License
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.