Preprint 2014-10
Stefan P. Müller
Induced Markov Chains Combined with Graph Differences for Data Compression.
Abstract: Graph-based data occurs in various applications,
e.g. finite-element simulations and computer-generated imagery.
There are several techniques to compress these data sets with
prediction methods and encoding of the residual. The focus of
these methods is almost always on the prediction rather than on
encoding. The model of induced Markov chains (iMc) is a new
strategy to approximate the information content of graph-based
data. For this purpose, we define transition probabilities between
the occurring values that are dependent on the topology of the
graph. The basic idea is to transform a topological relation into a
value-based one. The transition probabilities along with an initial
distribution can be interpreted as a Markov chain, the so-called
iMc. The topology combined with the transition probabilities can
be used as side information for an encoder. We combine an iMc
encoding scheme with graph differences as a prediction method,
since some correlations cannot be entirely removed neither by
the prediction method, nor by the iMc by its own.
Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976), P-2014-10
5 pp.