Implementation of LDGM codes with belief propagation for steganography

Supervisor(s)Martin Beneš, MSc


Steganography is a technique to hide secret messages inside inconspicuous cover media. A common approach is to choose a cover and insert the message by making slight, ideally undetectable changes. Modern methods choose the positions for changes based on the cover content. This is typically carried out in two phases, (1) estimating a distortion cost of change at each position, and (2) choosing the positions to change so that the message is present, while minimizing the distortion. To do so, the second phase is based on coding theory.

The goal of this thesis is to create an implementation for encoding and decoding for Low-Density Generator Matrix (LDGM) codes with belief propagation (BP). It has been described as a concept in a research paper and in fact might outperform syndrome-trellis codes (STCs), considered the state-of-the-art at the moment. However, there has not been many papers following up on the idea, and there is no known, available implementation of LDGM+BP.

The student needs to develop a thorough understanding of how steganography is implemented. A starting point is to study the method and prepare a prototype implementation that produces similar results to the ones reported in the research paper. The functionality should be illustrated on steganographic embedding and subsequent extraction of a secret message. The efficiency and performance of the coding should be compared to STCs.


  • Günther, P., Schönfeld, D., and Winkler, A. Reduced embedding complexity using BP message passing for LDGM codes. In Security, Forensics, Steganography, and Watermarking of Multimedia Contents X. 6819, SPIE, 2008, pp. 482–491.
  • Filler, T. and Fridrich, J. Binary quantization using belief propagation with decimation over factor graphs of LDGM codes. arXiv preprint arXiv:0710.0192, (2007).