Entropies in investigation of dynamical systems

1. Introduction

Investigations of various real processes are often based on observations. As P. Bak [1] noted observations are mainly statistical in character, and the laws formalizing the observations are expressed by distribution functions for measurable values. It results in applying informational (statistical) approach to the studying complex system behavior and using characteristics based on obtained distribution functions. The concept of entropy introduced by R. Clausius in 1850 in thermodynamics subsequently began to take on more general meaning not related directly to thermodynamics. Clausius considered entropy of an isolated system as a measure of the system state changing under changes of temperature. The term entropy denoted the energy that does not perform work, and in any isolated system it can only grow. It was L. Boltzmann [2] who first introduced statistical approach in thermodynamics – he proposed to describe a system state by using its microstates. The extension of Boltzmann’s entropy to nonequiprobable distributions results in Gibbs-Shannon entropy, which is one of Rényi entropies set. In 1948 C. Shannon invented entropy as a term in information theory, A. Kolmogorov in 1958 created dynamical entropy in dynamical systems. Now the term entropy is widely used in mathematics, computer science and many other areas of exploration.

In dynamical systems by entropy is meant a characteristic of a system complexity. Topological entropy describes the complexity of orbit structure and is the most important numerical invariant under topological conjunction. Another approach to the system dynamics study is statistical description of orbit behavior, and metric entropy of measure-preserving transforms is a statistical analog of topological entropy. Comprehensive information on entropy in dynamical systems and the relation between topological and metric entropy are given in [3, 4].

Of fundamental importance is the class of symbolic dynamical systems which are used for the coding smooth dynamical systems. The coding means that to any element of a finite partition is assigned a symbol from a finite alphabet and a trajectory is written as a symbol sequence in accordance with the transition of a trajectory from one partition element to another. On the space of sequences the shift map is considered such that one step along the trajectory is the shift of the corresponding sequence. Symbolic dynamical systems with a simple graphic presentation – topological Markov chains – are of frequent use.

Practical application of symbolic dynamical systems is based on elaboration of applied symbolic dynamics methods. In 1898 J. Hadamar [5] applied trajectory coding to describe global behavior of geodesic on the surfaces with negative curvature. H. Morse and G. Hedlung [6] and R. Bowen [7] contributed significantly to the progress of the method. V. Alekseev [8] applied it for celestial mechanics problems. In 1983 G. Osipenko proposed the method of symbolic image in which trajectory transitions between partition elements are represented by an oriented graph. Symbolic image is a topological Markov chain, and symbol sequences correspond to paths on the graph. This method was applied to approximation of invariant sets, Morse spectrum and invariant measures [9].

The dynamics of a system may be studied by analyzing its phase portrait. In this work, we consider the image analysis methods based on combining symbolic dynamics and information approach, and various types of entropies serve as connecting links between different problems and methods. The operating with symbolic sequences naturally leads to the calculation of a statistical characteristic of the system – relative frequency of a symbol occurrence, which corresponds to the frequency that a trajectory of an initial system visits a partition element. Hence, we obtain a measure of trajectory distribution in phase space, which provides calculation techniques for spectral characteristics – multifractal spectrum, Rényi spectra and divergences.

One may model the dynamics of diffusion processes by constructing the Markov chain on an oriented graph corresponding to a digital image which is a phase portrait of the process. The flow is defined by pixel intensities and nearest neighbours. Then the stationary state of the chain is calculated, which maximizes so called weighted entropy. This value (interpreted as a “distance” between an initial state and the stationary one) may be used as a classifying sign in image analysis.

These methods appear to have considerable promise for analysis of high resolution images with complex structure. We show the application of the construction of stationary flow on the graph and calculation of Rényi divergences to the analysis of biomedical preparation images. (All the images were provided by the department of morbid anatomy of Mariinsky hospital and medical center Terapeuticum in St. Petersburg.)

2. Calculation and estimation of topological and metric entropy

Topological entropy may be defined by different ways, for example through minimal coverings or separated sets [10]. For some systems it coincides with the growth rate of periodic orbits and may be calculated at once (linear extending maps, hyperbolic automorphism of torus). But for the most part of systems direct calculations are difficult and we should use methods of estimations. In 1993 S. Newhouse and T. Pignataro [11] proposed a method for estimating the topological entropy of a smooth dynamical system. The method is based on estimating the logarithmic growth rates of suitably chosen curves in the system. The method may be successfully applied for studying the complex system having strange attractors. In [12] the authors described the algorithm for obtaining rigorous lower bound for the topological entropy of planar diffeomorphisms based on approximation of stable and unstable manifolds of hyperbolic periodic points. Basing on these methods estimations of topological entropy were obtained for Henon and Ikeda map. Topological entropy with relative ease may be obtained for topological Markov chain – as the module of maximal eigenvalue of the adjacency matrix for the chain graph.

The symbolic image method may be effectively applied to the problem of approximation of an invariant measure for a dynamical system. The existence of an invariant measure means the existence of a stationary flow on the symbolic image graph. To obtain it we should construct a stationary distribution for a Markov chain. Metric entropy of the distribution gives a lower bound for the topological entropy of symbolic image which is calculated as topological entropy of topological Markov chain. The algorithms of the construction of stationary flow were described and implemented in [13, 14], where we obtained a lower bound of topological entropy for delay map, double logistic map, Henon and Ikeda map.

3. Entropy and image analysis

3.1. Weighted entropy

A description of a system dynamics by using oriented graph may be applied for images illustrating diffusion processes. The image is considered as a pixel lattice, being every pixel $i$ is a vertex of the graph with the measure $p_i$ equal to the pixel intensity. There are edges from every vertex to nearest neighbours and for every edge $(i,j)$ its measure $p_{ij}$ is $p_i$ divided on the number of neighbours. Norming the distribution $p_{ij}$ we obtain a Markov chain on graph in which a vertex measure is equal to the sum of measures of outcoming edges. Construct a stationary distribution $u_{ij}$ (for every vertex the sum of measures of incoming edges is equal to the sum of measures of outcoming ones). It was shown in [15] that such a distribution maximizes weighted entropy:

1

$f\left(u\right)=-\sum _{ij}{u}_{ij}\ln \frac{p_{ij}}{u_{ij}},$

which in accordance with maximum entropy principle means that the system goes from an initial state into the state with maximal entropy – stationary one.

In [16] we proposed a model for digital image analysis which is based on the calculation of a stationary flow on the graph associated with given image. Weighted entropy is considered as a classification sign. The implementation of the algorithm and results of the classification of pharmacological $Ag$ solution images are given in [17].

We consider an example of calculation of weighted entropy for liver images (given in Fig. 1) from 4 classes: plethora, dystrophy, cirrhosis and metastasis. In Table 1 the results of experiments are given. Component H of HSV palette seems to be more effective than others.

Fig. 1Images of liver tissue with plethora, dystrophy, cirrhosis and metastasis

a) Plethora

b) Dystrophy

c) Cirrhosis

d) Metastasis

Table 1Weighted entropy values in several palette components

Image	Grayscale	H	S	V
Plethora	0,00001861	0,13403192	0,00002513	0,00001609
Dystrophy	0,00001713	0,12524680	0,00002104	0,00001625
Cirrhosis	0,00001607	0,08331278	0,00002021	0,00001627
Metastasis	0,00001676	0,09522161	0,00003831	0,00001648

3.3. Rényi divergences

To reveal difference between structures of two images one can calculate Rényi divergences of order $\alpha$ (or $\alpha$-divergences) which for given probabilistic distributions $p=\left\{p_i\right\}$ and $q=\left\{q_i\right\}$ are defined as follows:

7

$D_{\alpha }\left(p,q\right)=\frac{1}{\alpha -1}\mathrm{l}\mathrm{n}{\sum }_{i=1}^n{p}_i^{\alpha }{q}_i^{1-\alpha }.$

It is known that values given by Eq. (6) are nonnegative for any $\alpha$ and the Rényi divergence is a non-decreasing function of $\alpha$.

For $\alpha =$1 the divergence is given by the formula:

8

$D_1\left(p,q\right)={\sum }_{i=1}^n{p}_i\ln \frac{p_i}{q_i},$

and called the Kullback-Leibler divergence. Note that up to sign Eq. (8) is the expression for weighted entropy (1). To obtain a vector characteristic we applied direct fractal transform Eq. (4) to given initial measures and calculated Rényi divergences between members of obtained sequences of measures. The feature that may be used as a classifying sign is the rate of the growth of the vector. For images having similar structures this rate is lower than for images with different structures. This approach was applied in [22, 23] for biomedical preparation images analysis and classification.

As an example, compare digital images of blood crystals from 3 classes – acute inflammatory process (bl1), chronic inflammatory process (bl2) and degenerative processes (bl3), which are shown from left to right on Fig. 2. The results of comparing of divergence vectors for $\alpha =\text{1}$ in grayscale are shown on Fig. 3, the same in H component – on Fig. 4. We see that growth rates of divergence vectors are different$.$

Fig. 2Images of blood crystals: acute inflammatory process, chronic inflammatory process, degenerative process

Fig. 3Divergence vectors when comparing images from classes bl1, bl2 and bl3 in grayscale

Fig. 4Divergence vectors when comparing images from classes bl1, bl2 and bl3 in H component

4. Conclusions

Using the concept entropy in various subject areas is determined by the quest for applying a general characteristic to describe different processes as a whole. It is statistical character of observations of natural phenomena that leads to using distribution functions of measurable values, and entropy is described in these terms. It turns out that entropy characteristics may be obtained both for a system described analytically and for its phase portraits. For applications relating to digital image analysis the calculation of Rényi entropies and multifractal spectra makes possible the revealing essential peculiarities of image structure and solving classification problem.