Lossless Coding of Markov Random Fields with Complex Cliques

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.

Department dc:contributor.department

Mathematics and Statistics

Year dc:date.issued

2013

Author dc:creator

• Wu, Szu Kuan Steven

Advisors dc:contributor.supervisor

• Mansouri, Abdol-Reza
• Linder, Tamás

• Markov Random Fields
• Applied Probability
• Belief Propagation
• Reduced Cutset Coding
• Information Theory
• Complex Cliques
• Computer Science

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1974/8166

OAI identifier oai:identifier

oai:queensu.scholaris.ca:1974/8166