Entropies in investigation of dynamical systems and their application to digital image analysis

1. Introduction

Scientific investigations of various processes are often based on observations. P. Bak in [1] noted, that observations are statistical in nature, and we use some distribution functions for measurable values to formalize them. It leads to forming informational (statistical) approach to study the behavior of a complex system, which is described by models processes we observe using the characteristics based on distribution functions.

In 1850, R. Clausius introduced the concept of entropy of an isolated system in thermodynamics as a measure of the change of system state under a change of temperature. The term “entropy” denoted the energy that does not perform work, and in any isolated system it can only increase.

L. Boltzmann [2] introduced the statistical approach in thermodynamics – he proposed to describe a system state by using its microstates. The Boltzmann entropy – statistical entropy for equiprobable distribution of a system over $N$ states:

For non-equiprobable distributions, the ensembles of microcanonical subsystems are used so that all its $N_i$ states are equiprobable with a probability $p_i$ for every $i$-th subsystem. The Boltzmann entropy (1) of $i$-th subsystem is $H_B^i=-\ln p_i$. The averaging of ensembles results in the expression for Gibbs-Shannon entropy:

The development of informational approach to the description of complex systems led to the creation of other forms of informational entropies, in particular Rényi entropies — a set of functions depending on a real parameter $q$:

These functions are important characteristics of a complex system, in particular in image analysis. Rényi spectra are calculated by using Renyi entropies. The Gibbs-Shannon entropy Eq. (2) is the Rényi entropy Eq. (3) for $q=1$.

Then the term of “entropy” began to take on more general meaning not related directly to thermodynamics. In 1948, C. Shannon invented entropy as a term in the information theory, A. Kolmogorov in 1958 created the concept of “dynamical entropy” in the theory of dynamical systems. Now, one can find the term entropy in mathematics, physics, and computer science. In dynamical systems, the entropy characterizes the system complexity. Topological entropy describes the complexity of orbit structure. Moreover, topologically conjugated systems have the same entropy, thus they have the characteristics of a class of systems. To describe the statistical behavior of orbits, the metric entropy of measure-preserving transforms, which is a statistical analog of topological entropy, is introduced. A comprehensive review on entropy in dynamical systems and the relation between them are given in [3, 4].

Symbolic dynamical systems form one of fundamentally important classes of dynamical systems. They are obtained in the process of coding the smooth dynamical systems. The coding means that we construct a finite partition of a phase space and assign a symbol from a finite alphabet to any element of the partition. Then we code a trajectory with a symbol sequence by writing one-by-one codes of partition elements which the trajectory visits. We obtain a space of symbol sequences corresponding to an approximation of the set of system trajectories, and define the shift map on the space so that one step along the trajectory is the shift of the corresponding sequence on one symbol. Symbolic dynamical systems having a presentation by the oriented graph are topological Markov chains, which are very important in different applications.

Practical application of symbolic dynamical systems was made possible due to elaboration of applied symbolic dynamics methods. Trajectory coding for description of global behavior of geodesic on the surfaces with negative curvature was applied in 1898 by J. Hadamar [5]. The papers of H. Morse and G. Hedlung [6, 7] and R. Bowen [8] made an important contribution to the progress of the method. V. Alekseev [9] applied it for celestial mechanics problems. In 1983 G. Osipenko elaborated the method of symbolic image, in which the system dynamics is represented by an oriented graph constructed by some rules. Actually, symbolic image graph is a topological Markov chain, where symbol sequences correspond to paths on the graph. By applying the technique of adaptive partition subdivision, one can construct a sequence of symbolic images that is an approximation of the dynamics of the initial system. This method was successfully applied to the approximation of invariant sets, Morse spectrum and invariant measures [10].

To study the dynamics of a system, one may analyze its phase portraits in various points in time. The operations with symbolic sequences naturally result in the calculation of a statistical characteristic of the system — relative frequency of a symbol occurrence in the sequence, which corresponds to the frequency at which a trajectory of the initial system visits a partition element. When considering phase portraits as digital images, we may interpret the set of frequencies as a measure distribution. Basing on this distribution, we may calculate multifractal spectra, Rényi spectra and divergences. These characteristics use Rényi entropies.

One can simulate the dynamics of diffusion processes illustrated by their phase portraits by constructing an oriented graph and the Markov chain on it. The flow is defined by pixel intensities. Then the stationary flow (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 a considerable promise for high resolution images with complex structure.

In this work, we consider the application of analysis methods of dynamical systems including image analysis ones, which are based on combining the symbolic dynamics and information approach. Various types of entropies serve as connecting links between different problems and methods. The described methods were used to analyze and classify digital images of biomedical preparations having a complex structure.

2. Calculation and estimation of topological entropy

Topological entropy may be defined by different ways, for example through minimal coverings or separated sets [11]. For simple system having complex structure of orbits, one may calculate the growth rate of periodic orbits. Examples of such systems are linear extending maps, and hyperbolic automorphism of torus. For them, the topological entropy coincides with the growth rate, which may be easily calculated. But for the most part of systems, we need to use methods of estimations. In 1993, S. Newhouse and T. Pignataro [12] proposed a method to estimate the topological entropy of a smooth dynamical system by calculating the logarithmic growth rates of suitably chosen curves in the system. The method may be successfully applied to study complex systems with strange attractors. In [13], the authors described the algorithm for obtaining rigorous lower bound of the topological entropy of planar diffeomorphisms. They used a method of approximation of invariant manifolds of hyperbolic periodic points, and applied it to estimate entropy for Henon and Ikeda maps. An effective algorithm was proposed in [14], where the authors calculated lower bound of the topological entropy and used it to identify regions of high mixing.

Topological entropy with relative ease may be obtained for a topological Markov chain: we should calculate the module of maximal eigenvalue of the adjacency matrix for the corresponding graph. In this connection, we may estimate topological entropy of a system by using the symbolic image method: in accordance with a given partition to construct the oriented graph (which is a topological Markov chain) and calculate eigenvalues of the adjacency matrix. In order to simplify the problem, one may perform this procedure for each component of strong connectivity of the graph.

The technique for estimation of topological entropy for the spaces of symbol sequences (“edge space” and “vertex space”) on oriented graphs was proposed in [15]. Basing on this approach, G. Osipenko in [10] designed and implemented algorithms for estimation of the entropy of symbolic image and obtained the estimation of topological entropy of Henon and logistic maps.

3. Metric entropy estimation

The concept of metric entropy of a map is introduced for maps preserving a measure. It means that we should deal with invariant measures of a map. The Krilov-Bogolyubov theorem [4] guarantees that any continuous map on a compact space has an invariant measure. One may construct an approximation to the invariant measure using the symbolic image method. In this case, we should calculate stationary flow on the graph of symbolic image. In doing so, we obtain a stationary distribution for a Markov chain. Then metric entropy of the distribution is a lower bound for the topological entropy of symbolic image. The algorithms of the construction of stationary flow were described and implemented in [16, 17], where the estimations for topological entropy of delay map, double logistic map, Henon and Ikeda map were obtained.

In this work, we also use the idea of construction of stationary flow on a graph constructed for a digital image by a specific way. It is known that stationary flow gives maximum to the function dealing with initial and stationary distributions (so called weighted entropy). For digital images weighted entropy may be considered as a classifying sign.

4. Entropies as goal functions in variational problems

The Shannon and Rényi entropies are often used as goal functions when finding distributions that maximize (minimize) the function for some given restrictions. We consider one problem which is related to multifractal spectrum calculation.

Let a distribution ${\{p}_i\}$ with ${\sum }_{i=1}^N{p}_i=1$ be given. Find the distribution ${\mu }_i$ maximizing the Shannon entropy $-\sum {\mu }_i\ln {\mu }_i$ on the conditions ${\sum }_{i=1}^N{\mu }_i=1$, and the constraints on $\ln p_i$ averaged over ${\mu }_i,$ i.e. $\sum _{i=1}^N{\mu }_i\ln p_i=k$, where $k$ is a real constant.

Consider the Lagrange function with parameters $q$ and $\lambda$:

Equaling partial derivatives of $\phi$ (given by Eq. (4)) by ${\mu }_i$ to zero, we obtain the system:

It follows that:

Combining Eq. (5), we obtain $1=e^{\lambda -1}\sum _{i=1}^N{p}_i^q,$ that taking into account Eq. (6) leads to excluding $\lambda$:

For given conditions on average values $\left(k\right)$, one can calculate $q$ and solve the optimization problem. But it is significant that Eq. (7) determines a set of solutions depending on the parameter $q$. In fact, it is a transform of the initial measure $\left\{p_i\right\}$ (so called direct multifractal transform). It is easy to see that for $q\ne 0$ transforms Eq. (7) forms a group, namely if we denote $f_q\left(p\right)=p_i^q/\sum p_i^q$, then $f_{q_1}\left(f_{q_2}\right)=f_{q_1{q}_2}$,$f_q\left(Id\right)=f_q$ and $f_q\left(f_{1/q}\right)=Id$, where $Id=f_1.$ For $q=1$ we have the fixed point. The set of probabilistic measures falls into non-intersecting transitivity classes.

5. Entropy in analysis of digital images

5.2. Weighted entropy calculation

Weighted entropy is calculated for 4 classes of biomedical preparation images, and each class contains 12 images. The images were obtained by microscope AxioCam MRc5 of the company Carl Zeiss Microimaging GmbH. All the images were made with 200-fold zoom, represented in RGB and with the size of 2584×1936 pixels.

A preliminary classification was performed by an expert. All the images are represented both in grayscale and HSV palette (component wise).

Fig. 1 shows images from 4 classes of liver tissue: plethora, dystrophy, cirrhosis, metastasis.

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

a) Plethora

b) Dystrophy

c) Cirrhosis

d) Metastasis

In Table 1 values of weighted entropy for images in Fig. 1 are given. Experiments show that the values of weighted entropy are different in H component.

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.09522162	0.00003832	0.00001648

5.4. Multifractal spectrum and entropy

Another example of the connection between fractal dimensions and entropy is the information dimension, which is a member of Rényi dimensions set. This dimension may be interpreted as the dimension of the measure-theoretic support of a particular measure (in other words, the complement of the support has zero Lebesgue measure).

Digital images with complex texture often have fractal or multifractal structures. Fractal sets may be described by a numerical characteristic called as fractal dimension, which reflects the main property of such sets – self-similarity. The last one may be strict (as for Cantor set) and statistical (as for majority of nature objects). Multifractal sets may be interpreted as unions of several fractal subsets. Each of subsets has its own fractal dimension, and they are arranged by a very complex way. Fractal dimensions of these subsets form multifractal spectrum. In the fractal analysis, we use a main assumption based on experimental data: if we divide an image on cells with a given size and calculate a measure of cells then there is power dependence between the measure and size. This exponent is an approximate value of the fractal dimension of the set.

Let us to give the number of cell of a partitions ($N$) with size $l$ for a set $M$. In [25], the authors considered a calculation method for the dimension of a measure $\left\{p_i\right\}$ support $M$ (in other words, the dimension of the set of trajectories on the phase portrait which corresponds to the given distribution) as:

12

$\dim M=-\underset{N\to \infty }{\lim }\frac{\sum _{i=1}^N{p}_i\ln p_i}{\ln N}.$

Taking into account the dependence measure ${\{p}_i\}$ on the cell size, and $l~1/N$, we obtain Eq. (12) rewritten as follows:

13

$\dim M=\underset{l\to 0}{\lim }\frac{\sum _{i=1}^N{p}_i\left(l\right)\ln p_i\left(l\right)}{\ln l}.$

The last one is the information dimension formula.

The authors also proposed to calculate multifractal spectrum by obtaining a sequence of measures from a given initial normalized measure distribution by applying direct multifractal transform, and then calculate information dimensions of supports of measures from the sequence by Eq. (13).

Later on we assume that $p_i\approx l^{{\alpha }_i}$, hence ${\alpha }_i\approx \mathrm{l}\mathrm{n}{p}_{i\left(l\right)}⁄\mathrm{l}\mathrm{n}l$. We also assume that for the generalized statistical sum $\phi \left(q\right)=\sum _{i=1}^N{p}_i^q\left(l\right)$ ($q$ is a real number), there is the function $\tau \left(q\right)$ such as $\phi \left(q\right)\approx l^{\tau \left(q\right)}$. For an initial distribution $\left\{p_i\right\}$ we obtain the sequence of measures $\mu \left(q,l\right)=\left\{{\mu }_i\left(q,l\right)\right\}$ by applying Eq. (7): ${\mu }_{i\left(q,l\right)}=\frac{p_i^{q\left(l\right)}}{{\sum }_{i=1}^N{p}_i^{q\left(l\right)}}$. For each measure $\mu \left(q,l\right)$, we calculate the information dimension of its support by Eq. (13) and obtain a set $f\left(q\right)$ – dimensions of measures $\mu \left(q,l\right)$ supports:

14

$f\left(q\right)=\underset{l\to 0}{\lim }\frac{\sum _{i=1}^N{\mu }_i(q,l)\ln {\mu }_i(q,l)}{\ln l}.$

Following the method mentioned above, we also calculate averaging of exponents $p_i\left(l\right)$ over the measure $\mu \left(q,l\right)$ and then the limit $\alpha \left(q\right)$ of these averaging:

15

$\alpha \left(q\right)=\underset{l\to 0}{\lim }\frac{\sum _{i=1}^N\ln p_i\left(l\right){\mu }_i(q,l)}{\ln l}.$

So, Eqs. (14) and (15) give the q-parametric presentation of multifractal spectrum $f\left(q\right)$ and averaging exponents $\alpha \left(q\right)$.To obtain the dependence $f\left(\alpha \right)$, we should exclude $q$. Excluding $q$ one may obtain the dependence $f\left(\alpha \right).$

It is interesting to note that substituting ${\mu }_i\left(q,l\right)=p_i^q\left(l\right)/\sum _{i=1}^N{p}_i^q\left(l\right)$ in Eq. (14) we obtain:

$f\left(q\right)=\underset{l\to 0}{\lim }\frac{\sum _{i=1}^N{\mu }_i\left(q,l\right)\ln {\mu }_i\left(q,l\right)}{\ln l}=\underset{l\to 0}{\lim }\frac{\sum _{i=1}^N{\mu }_i\left(q,l\right)\ln \frac{p_i^q\left(l\right)}{\sum _j{p}_j^q\left(l\right)}}{\ln l}$
$=q\underset{l\to 0}{\lim }\frac{\sum _{i=1}^N{\mu }_i\left(q,l\right)\ln p_i\left(l\right)}{\ln l}-\underset{l\to 0}{\lim }\frac{\sum _{i=1}^N{\mu }_i\left(q,l\right)\ln \phi \left(q,l\right)}{\ln l}$
$=q\alpha \left(q\right)-\underset{l\to 0}{\lim }\frac{\ln \phi \left(q\right)}{\ln l}=q\alpha \left(q\right)-\tau \left(q\right).$

Besides that:

$\frac{d\tau \left(q\right)}{dq}=\underset{l\to 0}{\lim }\frac{1}{\ln l}\frac{\sum _i{p}_i^k\left(l\right)\ln p_i\left(l\right)}{\sum _j{p}_j^k\left(l\right)}=\underset{l\to 0}{\lim }\frac{\sum _i\frac{p_i^q\left(l\right)}{\sum _j{p}_j^q\left(l\right)}\ln p_i\left(l\right)}{\ln l}$
$=\underset{l\to 0}{\mathrm{l}\mathrm{i}\mathrm{m}}\frac{\sum _i{\mu }_i\left(q,l\right)\ln p_i\left(l\right)}{\ln l}=\alpha \left(q\right).$

In other words, on the sequence of measures obtained from an initial measure by direct multifractal transform, the formula for the Legendre transform is made.

This method was applied in [26] for calculation of Rényi spectrum. Namely, by obtaining $\alpha \left(q\right)$ and $f\left(q\right)$ and using the Legendre transform, we have $\tau \left(q\right)=q\alpha \left(q\right)-f\left(q\right)$ and $D_q=\tau \left(q\right)/q-1$, where $D_q$ is $q$-order Rényi dimension.

We applied the described method in [27] to classify biomedical preparation images.

Example: Now the example of calculation of $f\left(q\right)$ and $\alpha \left(q\right)$ is considered for images of a healthy bone tissue and a tissue with osteoporosis. Images have the size [350, 279]. Calculations were performed for a grayscale palette, the parameter $k$ changed within the interval [–7, 3] with the step of 0.5. The cell measure is calculated as the relation of pixel intensities in the cell to the sum of pixel intensities of the image. To calculate $f\left(q\right)$ and $\alpha \left(q\right)$ by Eqs. (14) and (15) the least square method was used with cell sizes {5, 6, 7, 8, 9, 10, 11}.

Fig. 2Images of healthy bone tissue and bone tissue with osteoporosis

a) Healthy bone tissue

b) Bone tissue with osteoporosis

Fig. 3Graphics of parametrized spectra for healthy bone tissue

It should be noted that the choice of interval of values of parameter $q$ depends on the image structure and palette. Nevertheless, the obtained results show that parametrized spectra may be used as classification signs in the image analysis.

Fig. 4Graphics of parametrized spectra for bone tissue with osteoporosis

5.5. Rényi divergences

A calculation of Rényi divergences of order $\alpha$ (or $\alpha$-divergences) allows us finding differences in structures of two images. For given probabilistic distributions $p=\left\{p_i\right\}$ and $q=\left\{q_i\right\}$ and the $\alpha$-divergence is defined for some $\alpha$ as follows:

16

$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 not difficult to verify that these values are non-negative for any $\alpha$, and the Rényi divergence as a function of $\alpha$is non-decreasing.

Fig. 5a), b) Healthy kidney tissue and c) tissue with pyelonephritis

a)

b)

c)

Fig. 6Graphics of Rényi divergences for various parameter values when comparing images of healthy tissues Fig. 5(a-b)

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

17

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

It is known as the Kullback-Leibler divergence, and up to sign the Eq. (17) is the Eq. (8), which describes the weighted entropy.

For given initial measures, we applied direct fractal transform Eq. (7), obtained two sequences of transformed measures and calculated Rényi divergences between corresponding members of these sequences. We applied this approach in [28, 29] to analyze and classify some classes of biomedical preparation images. Consider the example of application of this method to the analysis of healthy tissue and tissue with pyelonephritis images.

Fig. 7Graphics of Rényi divergences for various parameter values when comparing images of healthy and invaded tissues Fig. 5(a, c)

6. Conclusions

Nowadays the concept of entropy may be considered as a general characteristic for the description of many processes. It is natural that our descriptions are based on observations, which are statistical by its nature. The mathematical formalization for statistical events is expressed in terms of distribution functions, and the entropy is also written by using these functions. It is significant that one may obtain entropy characteristics both for various dynamical systems, and for digital images which are phase portraits of such systems. Symbolic dynamics allows us giving a natural interpretation of statistical description of the dynamic system behavior: it shows the frequency with which a typical trajectory visits cells of a given partition. Thereby such a characteristic describes a distribution of a measure on the phase space. For a given measure, one can calculate the partition entropy and metric entropy. Namely metric entropy is the base to calculate the information dimension of the measure support. The set of these dimensions is a kind of multifractal spectrum. Rényi entropies also use the metric entropy. Multifractal characteristics reveal essential peculiarities of image structure and may be used as classification signs. These methods are successfully applied in the analysis of a wide range of biomedical preparations images which have high resolution and very complex structure. So, the concept entropy, which is understood in dynamical systems as the system complexity, preserves its meaning in the application problems: based on entropy, the numerical characteristics of phase portraits show their complexity and in this way the behavior of the initial system.