Markov random fields model and applications to image processing

1.   Introduction and motivations

Let $G = (V, E)$ be a Feynman graph, where $V$ and $E$ are the sets of vertices and edges respectively. The vertices are represented by points and classified into two category full and empty. The edges join different pairs of vertices will be denoted by $e = (v, w)$ and are represented by lines joining the vertices. For the graph $G$, we associate a network evolving according to the stochastic differential equation:

where $W = \{w \in V: (w, v) = e \in E\}$ is the set of all vertices connected to $v$, called parents of $v$, $\{X_v(t), \, t\geq 0\}$ is a stochastic process taking values in $\mathbb{R}^d$ and $\, \alpha = (\alpha_{vw})_{v, w \in V} \in \mathbb{R}^{d \times d}$ a matrix whose sparsity pattern is given by the graph $G$.

The process $\{L_v (t), \, t > 0\}$ is a Lévy process taking values in $\mathbb{R}^d, \, X_v (0) = x_0 \in \mathbb{R}^d$ is a random variable independent of $L_v (t)$, distributed according to the invariant measure, see ^{[1,2,3,4,5,21]}.

We are mainly interested in characterizing the scaling of the learning time for large networks. The Gaussian case, i.e, when the driving noise in Eq (1.1) is a Brownian motion $\{B_t, t > 0\}$ has been discussed by several authors see, e.g. ^[10] and ^[23]. In this work we will develop the general case, i.e when the noise in Eq (1.1) is of Lévy type, we will prove that the scaling limit of a Poisson noise gives a Gaussian noise. This result is of great interest, for instance it can be used to get the scaling of the learning time for large networks. Moreover, the It$\hat{o}$ formula applied to Eq (1.1) to find the solution $X_v,$ can be also related by a scaling limit of the classical It$\hat{o}$ formula for Gaussian noise.

In the paper ^[21], the author proved an asymptotic expansion of the transition probability density $p_t, \, t > 0$ of the semigroup associated to a SDE driven by Lévy noise, and he outlined some remarks on the applications of the neural networks. In this work we will focus on more applications using Markov Random fields particularly on images and cliques. This notion is captured by means of a local, conditional probability distribution and Gibbs distribution.

Let us also mention that getting such applications in a Complex biological networks, where extracting stochastic models from data is a challenging task, see, e.g., ^[18,19,22]. The model given by Eq (1.1) can be used to trace fluctuations of the process with respect to equilibrium values, for instance we will show that the stochastic process $\{X_v (t), t\geq 0\}$ given by Eq (1.1) with fluctuating force $\{L_v(t), \, t > 0\}$ is a MRF satisfying a Markov property. The probabilistic approaches behind image analysis is due to the fact that a probability distribution (Gibbs distribution) can interact to the different sets of image attributes. The MRF image models will be defined in this work using Feynman graphs, where the solution $X_v$ of the SDE (1) will depend only on the neighboring variables of the vertex $v$. The structure of the Feynman graphs defined in this work is in a such a way all variables are mutually independent, i.e., each two vertices in the graph can be joined through a path. This graphical representation is a powerful tool to study the structural properties of the model. Let us mention that, to the best of our knowledge, getting Feynman graphs representations of the distribution function $P(X_v = x)$ of the solution $X_v, \, v\in\, V$ of the SDE (1.1), is not studied before, it is the aim of this paper to give such a recipe by calculating first the Gibbs distribution of the solution $X_v,$ then Hammensley-Clifford theorem ensure that the stochastic process $\{X_v (t), t\geq 0\}$ is a MRF. Hence, by using Feynman graphs and rules approach we will prove that the distribution function of the solution $X_v, \, v\in V$ is given by a sum over all such graphs. The graphical representation of the MRF are defined in a way that it model and analyze images, see, e.g., ^[7]. For computations and numerical analysis we may restrict only to neighboring variables due to the Markovian properties conditions.

The structure of this paper is as follows: Section 2 is devoted to some definitions and assumptions that are useful for the current work. In Section 3 we will show how we can scale a Poisson process to obtain a Gaussian one, thus one can extract previous results where a Gaussian noise is considered from the current general work. Section 4 is devoted to the main results on MRFs and their graphical representations. In Section 5 some remarks and applications are given. Section 6 is reserved to the conclusion part of this work.

2.   Preleminaries and assumptions

In this section we will introduce some useful notations and basic results from stochastic process, Lévy noise and probability theory.

Denote by $\tilde{M}$ a compensated jump measure, then $\tilde{M}$ will be defined as:

here $\pi$ is the Lévy measure satisfying $\int_{{{\mathbb R}}^d\setminus \{0\}} (\mid x\mid^2\, \wedge\, 1)\, \pi(dx)\, < \, \infty.$ More detail about Lévy measure can be found in ^[9,20].

The Lévy process $L_t = L(t), t\, \geq 0$, is represented, see ^[20], by

where $m$ and $k$ are constants and $B_t = B(t), \, t \geq 0$ is a standard Brownian motion on ${{\mathbb R}}^d.$

For the particular case $m = k = 0,$ the Lévy process $L(t), \, t\geq 0$ is called a pure jump Lévy process denoted by $\tilde{L}, \, t\geq 0$ and defined on ${{\mathbb R}}^d$. $\tilde{L}$ is characterized by its characteristic function:

Moreover, the process $\tilde{L}_t$ can be represented as follows:

where $B$ is a Borel set, i.e., $B \in {\cal B}({{\mathbb R}}^d)$.

Definition 2.1. A transition kernel on $(\mathbb{R}^d, \mathcal{B}(\mathbb{R}^d))$, is a family of mappings $p_{s, t}(x, B), s, t\geq 0, \, x \in {{\mathbb R}}^d$ and $B \in {\cal B}({{\mathbb R}}^d)$, with values in $[0, 1]$ and satisfying:

(1) $p_{s, t}(x, B)$ is a probability measure as a function of $B$ for any fixed $x$;

(2) $p_{s, t}(x, B)$ is measurable in $x$ for any fixed $B$;

(3) $p_{0, 0}(x, B) = \delta_x(B)$;

(4)

Called semi-group or Chapman-Kolmogorov property.

Definition 2.2. Let $(\Omega, {\cal F}, P)$ be a probability space with a filtration $({\cal F}_t, t\geq 0)$. A stochastic process $(X = X_t, \, t\geq 0)$ adapted to ${\cal F}_t$ is said to posses the Markov property if for each $s, t\geq 0, \, s < t,$

A Markov process is a stochastic process which satisfies the Markov property with respect to its filtration.

Remark 2.3. (1) Markov processes are characterized by transition probability functions, moreover if $u(t), \; t \geq 0$ is a Markov process then for $0 < s < t,$

(2) If $P_t(u_0, .), \, t > 0, u_0\, \in\, {{\mathbb R}}^d$ is the transition semigroup of a homogeneous Markov process $u_t, t\geq 0,$ then by a result in ^[20] we have:

where $\Psi$ is the Lévy characteristic given by:

Here $l, \, D\, \in {{\mathbb R}}^d$ and $\nu$ is a positive Lévy measure satisfying:

(3) The transition probability density $q_t, \, t > 0$ of the solution $u_t, \, t\geq 0$ can be characterized by the Fourier transform:

Following Hartman and Wintner ^[14], existence of the transition probability density $q_t, t > 0$ associated to $u_t, t \geq 0$ is guaranteed in terms of the characteristic exponent of $\Psi$. To guarantee the smoothness of $q_t, \, t > 0$ we assume for $a\in (0, 2)$:

Definition 2.4. Let $X$ and $Y$ be two random variables. $X$ and $Y$ are said to be conditionally independent given the random variable $Z$, if and only if:

Let us remind that a random field is essentially a stochastic process defined on set of spatial nodes (called also sites). For instance, if $S = \{1, ..., n \}$ is a finite set and $\{X(s), \, s \in S \}$ is a collection of random variables on the sample space $\Omega$ and $X(s_1) = x_1, ..., X(s_m) = x_m,$ where $x_i \, \in \Omega$. Then the joint event $x = {x_1, ..., x_m}$ is called a configuration of $X(s)$, which corresponds to a realization of the random field (RF), more details can be found in ^[8,12].

In a given random fields, the sites in $S$ are related to one another through a neighborhood system denoted by $N = \{N(i), i\, \in S\},$ where $N(i)$ is the set of sites that are neighbors of $i, \, i \notin N(i).$ The neighborhood relation is symmetrical, which means that $i\, \in\, N(j)\leftrightarrow j \, \in\, N(i)$. Thus, for a finite set of sites $S = \{1, ..., N\},$ a Markov random field is a family of random variables $X_i, i \in S$ such that $P(X_i = x_i)\, > 0$ and with probability functions that satisfy the Markov properties:

Unfortunately, using the Markov property (2.14) one can not deduce the joint probability distribution $P(X_1, ..., X_N)$ from the conditional probability $P[X_i|X_j, \, j\, \in N(i)]$. Thanks to Hammersley-Clifford theorem which solves this problem:

Theorem 2.5. The random field $X$ is a Markov random field (MRF) if and only if $X$ is a Gibbs random field.

Proof. For the proof we refer to ^[6].

Definition 2.6. For a graph $G = (V, E)$, we define a Green function $\tilde{G}$ on $]0, \, \infty[$, as follows:

where $\delta(t)$ is the Dirac distribution on ${{\mathbb R}}_{+}$ and $\alpha_{vw}$ are the matrix coefficients given in Eq (1.1).

3.   A Gaussian process is a scaling limit of a Poisson process

Following ^[20] and From Eq (2.9), one can see that the Lévy process $L_{v}(t), \, t > 0$ can be decomposed into three independent components, i.e., $L_v = L^d_v+L^g_v+L^p_v,$ where $L^d_v, \, L^g_v$ and $L^p_v$ are respectively, the deterministic, Gaussian and Poisson noise given by their characteristic functions.

In the following and without loss of generality, $L^d_v, \, L^g_v$ and $L^p_v$ will be denoted by $L^d, \, L^g$ and $L^p$ respectively.

The deterministic component $L^d_v$ do not impose any difficulty in computing the moments of the noise, and we refer to several works from literature. In this work we will stress our selfes to the more general case, it is our aim then to show how can we recover the Gaussian noise $L^g$ starting from a Poisson noise $L^p$, then we will model a Markov chain by a neural networks. For this aim we consider a representation of the Poisson noise in terms of Poisson distribution: Let $\Lambda_n \subset\, \subset\, {{\mathbb R}}_{+}$ be a monotone sequence of compact sets, i.e, intervals, s.t, $\Lambda_n\, \uparrow\, {{\mathbb R}}_{+}$ as $n \longrightarrow\, \infty$ and $\Lambda_0 = \emptyset.$ For $n\, \in\, {{\mathbb N}}$, let $L_n = \Lambda_n \backslash\, \Lambda_{n-1}$ and we denote the Lebesgue volume of $L_n$ by $\mid\, L_n\mid$. Let

where $\delta_x$ is the Dirac measure of mass one in $x$, $\{S^n_j\}_{j\, \in\, {{\mathbb N}}}$ is a family of real valued and independent random variables with law given by $r$ and $N^z_T$ is a Poisson random variable with intensity $z\, \mid L_n\mid$, i.e,

Let now $S({{\mathbb R}})$ be the Schwartz space of all rapidly decreasing functions on ${{\mathbb R}}$ endowed with the Schwartz topology, its topological dual is the space of tempered distribution noted by $S'({{\mathbb R}})$. We denote by $\langle.\, , \, .\rangle$ the dual pairing between $S({{\mathbb R}})$ and $S'({{\mathbb R}}).$

The characteristic functional of the noise $L^p_n$ for any function $h\in\, S({{\mathbb R}})$ such that $supp h\subseteq\, L_n$ is given by:

We will denote now $C_{L^p}$ the generating functional of the function $f$ for a Poisson noise $L^p$ on ${{\mathbb R}}$ by:

Definition 3.1. Let $x_1, ..., x_k \in {{\mathbb R}}^d$, $I$ a partition of the set $\{1, ..., m\}$, $I \in {\cal P}(m), \, \\I = {\{I_1, ..., I_k\}}$ the truncated moments functions $\langle L(x_1)\cdot\cdot\cdot L(x_{m})\rangle^{T}$ are recursively defined by:

where $\langle I_l\rangle^T = \langle \prod_{j \in I_l}L(x_j)\rangle^T$. $

Theorem 3.2. The truncated moment functions of the noise $L$ are given by the following formula

where

$\delta_{n, \, n'}$ being the Kronecker symbol and $\psi$ the characteristic function given by Eq (2.9).

Proof. For the proof we refer to ^[13].

The following first result, shows that one can scale the Poisson noise to obtain a Gaussian noise.

Theorem 3.3. Let $C_{L^p}$ be the generating function of a function $f$ given by Eq (3.4) and $L^g$ the Gaussian noise. Assume that $\int_{{{\mathbb R}}\setminus\{0\}}s dr(s) = 0$, then:

Here $C_{L^g}(f)$ is the generating function of the function $f$ for a Gaussian noise $L^g$ on ${{\mathbb R}}$ and $c_2$ are the moment of order $2$ of $L^g$ given by Eq (3.7).

Proof. Consider the transformation $s\, \longrightarrow\, {s \over {\sqrt{z}}}$, then:

Remark 3.4. In the next section we will prove that the MRF can be represented through Feynman graphs according to some fixed rules, since the representation consider the Lévy process $L_v(t), \, t \geq 0$, then by using Theorem 3.3 one can scale the Poisson noise to get a Gaussian noise, this particular case consider the Gauss-Markov random fields, see, e.g., ^[6].

4.   Markov random fields and graphical representations

4.1.   Markov random fields

Markov random fields (MRF) is used in different areas, it was originally used in statistical mechanics to model system of particles interacting in two or three dimensional lattice. MRF have been recently widely used in statistics and image analysis, where pixels and voxels represents the images, see, e.g., ^[11].

Assuming now that a process is at particular location, it will be then influenced by the events happened in a neighborhood location. The relation is in one-to-one correspondence through a neighborhood system denoted by $N = \{N(v), \, v \in V\}$, where $N(v)$ is the set of sites that are neighbors of $V$, graphically this set is a subset from the set $V$ of all vertices of a graph $G$.

Notice that one can apply to symmetry in $N(V),$ i.e;

Consequently a MRF represents in this work a family of stochastic processes $\{X_v, v \in N(v)\}$ satisfying the Markov property:

Equation (4.2) establishes the local characteristics of the process $\{X_v, v \in N(v)\},$ this means that only neighboring sites have direct interactions on each other. For this reason it is important to discuss carefully the neighborhood structure in MRF, since it gives idea about the characteristic of the image data.

The neighborhood structure can be modeled by the graph $G = (V, E),$ where the sites represents the vertices and any two sites are connected by an edge $e \in E.$, see, Figure 1.

Definition 4.1. We define a clique of the graph $G = (v, E)$ as a subgraph of $G$ in which every site is a neighbor of all other sites. Example of three vertices clique is given in Figure 2.

One can understand that a MRF consists of a set of cliques since any vertex in a clique is a neighbor to all other vertices in the same clique, therefore the conditional probability $P\, (X_v|X_w, w \in N(v))$ will be represented by cliques.

The process $X_v$ is defined to have the Gibbs distribution if its distribution function is given by:

where $U(x)$ is the energy function, $\beta > 0$ characterizes the label scale variability in an image. Here $Z$ is the partition function given by

which is nothing else than a normalizing constant and involves a summation over all possible configurations of $X_v$.

Remark 4.2. The Gibbs distribution given by Eq (4.3) shows that high energies corresponds to low probabilities, whereas lower energies are more likely.

One can express $U(x)$ in terms of cliques as

$V_c(x)$ is the potential function that is associated with clique $c \in C$, which is known in image analysis, as a function of the values of the pixels in a clique $c \in C$, and $V_{N_{i}}, \, i = 1, 2, ....$ are potentials defined on the cliques of the neighborhood system $N_i$. Here $v$ and $w$ are neighbors if $x_v$ and $x_w$ appears simultaneously within a same factor $V_{N_i}, \, \, i = 1, 2, ....$

Following Hammensley-Clifford theorem the process $\{X_v, \, v \in N(v)\}$ is a MRF if and only if it has a Gibbs distribution with potentials defined on the cliques of the neighborhood system $N(v).$ The conditional probability $P(X_v|X_w, \, w \in N(v))$ is then given by:

where

here $\{x| X_v = y\} = \{x_1, \ldots, x_k, y, \ldots, x_d\}, \, \, k = 1, ..., d$.

In image processing one can understand Eq (4.6) as follows: Associate an image with the stochastic process $X_{v_0}$, where $v_0$ here refer to a site in the image. Then the conditional probability given by Eq (4.6) can be written in this case as:

Moreover, if $v_0$ is the site of $(v, w)$, then the neighbors of $v_0$ are $(v, w_1), (v, w_{-1}), (v_1, w)$ and $(v_{-1}, w)$, notice that each two sites are connected through a path, which will be expressed in terms of vertices and edges, consequently the conditional probability given by Eq (4.8) is nothing else then the first order Gauss-Markov model, see, e.g., ^[6]:

Remark 4.3. From the above example and the expression of the Gibbs distribution, one can obtain the density function by assembling the different clique energies from the conditional probability and then compute the energy function by adding up the clique energies, see, e.g., ^[6,11,16].

4.2.   Feynman graph representation

We would like now to establishes a graphical representation for the solution $\{ X_v, \, v\, \in V\}$ of the SDE equation (1.1). Since the solution is characterized by the Gibbs distribution given by Eq (4.3), it suffices then to provide a graphical representation to $P(X_v = x)$, this leads to express graphically the sites in image as well as the cliques.

Proposition 4.4. In the sense of formal power series the distribution function of the solution of the SDE (1) is given by:

where $x(a_i)$ are the neighbors of $a_i\, \in\, N_i, \, \, a_i = v, \, (u, v), \, ...$

Proof.

where $x(a_i)$ are the neighbors of $a_i\, \in\, N_i, \, \, a_i = v, \, (u, v), \, ...$

Definition 4.5. Let $G = (E, V)$ be a Feynman graph, the random variable ${\cal L}(G, \, x),$ is defined as follows:

1)-Assign $x \in {{\mathbb R}}^d$ to the root (first inner vertex) of the graph $G$.

- Assign values $x_1, ..., x_d \in {{\mathbb R}}$ to the other inner vertices, where $x(v) = (x_1, ..., x_d)\, \in\, {{\mathbb R}}^d.$

2)- For every edge with two end points, $e = \{v, \, w\}, \, \,$ assign a value $\tilde{G}(e) = \tilde{G}(v-w), \, \, \, (v\leq w)$ to this edge. $\tilde{G}$ is the Green function defined by Eq (2.15).

3)- For the $i-th$ inner vertex multiply with $V_{N_i}$.

4)- For the $i-th$ inner vertex multiply with the coefficient ${n!\over {n_0!n_1!...n_i!...}}\, \,$.

5)- Integrate with respect to the Lebesgue measure $dx_1\cdot\cdot\cdot dx_d$.

Theorem 4.6. The distribution function of the solution of the stochastic differential equation $(1)$ is given by a sum over all Feynman graph $G$ that are evaluated according to the ruled fixed in Definition 4.5, i.e.

Proof. From Proposition (4.4) and the Definition (4.5) we have

5.   A Remark on some applications

Markov random fields (MRF) enjoyed much success on the structural data particularly on image and cliques where pixels are well arranged, see, e.g., ^[17].

Traditional (MRF) has one graph in its model, later and in their work ^[15], the authors uses three graphs to characterize hidden communities in a given network. In our current work the (MRF) has $d\, \in\, {{\mathbb N}}$ graphs in its models. Moreover, if different models are provided, they will be used in competition to analyze and identify the content of a given image. A particular case arise when the SDE (1) is driven by a Gaussian noise. In this case the Gauss-Markov random field will be considered and identified by the distribution given in Eq (4.9). Moreover, the variable in the Feynman graph $G$ interacts with each others through the quadratic energy, since the matrix is sparse. Therefore the sites $v$ and $w$ are neighbors in $G$ if the corresponding entry $\alpha_{vw} = \alpha_{wv}$ is nonzero.

6.   Conclusions

In this work the following results are achieved: We proved that the solution of the Lévy type SDE is a MRF satisfying the Markov property, we proved also that by scaling the Poisson process one get the Gaussian process. we showed that the Gibbs distribution of the solution process is represented graphically through Feynman graphs according to a fixed rules. At the end, we outlined some applications in image processing mainly where the image intensity depends only on neighborhood of pixels.

Acknowledgements

This work is supported by King Fahd University of Petroleum and Minerals. The author gratefully acknowledges this support.

Conflicts of interest

The author declares that there is no conflict of interest regarding the publication of this paper.