Model-Based Interaction Map

An MBIM jointly depicts the partial energies of all clique families in a texture, from which a characteristic pixel neighbourhood $\mathcal{N}$ can be estimated.

A generic MGRF model allows an arbitrary structure of pairwise pixel interactions, but the longest interaction to recover depends on the size of each individual training image in practice. Without loss of generality, Markov property is assumed such that all the neighbours of a pixel $i$ are limited into a large search window $\mathcal{W}_i$ centred on the pixel. So, $\mathcal{N}_i \in \mathcal{W}_i$. In order to capture the periodicity structure of a texture, the search window must be large enough to cover at least a few repetitions. Empirically, the window size is chosen between $1/3$ and $/1/2$ of the size of the training texture. The empirical rule accounts for the need of enough samples for each clique family to reliably collect GLCHs and estimate energies.

Let the width and the height of a search window $\mathcal{W}$ be denoted $\vert\mathcal{W}\vert _x$ and $\vert\mathcal{W}\vert _y$ respectively. A clique family $\mathbf{C}_a$ in a texture has the maximum displacement of $\frac{\vert\mathcal{W}\vert _x}{2}$ and $\frac{\vert\mathcal{W}\vert _y}{2}$ along $x$ and $y$ axes respectively, so that,

$$\mathbf{C}_a=\left\{(i,j):i,j \in \mathbf{R}; i-j=(\delta{x_a},\d... ...W}\vert _x}{2},\vert\delta{y_a}\vert<\frac{\vert\mathcal{W}\vert _y}{2}\right\}$$

Formally, an MBIM is a 2D function, $f: \mathcal{W} \rightarrow \mathbf{E}$, which maps a search window $\mathcal{W}$ onto real-valued partial energies $\mathbf{E}$. A two-step procedure is involved in computing the partial energy for each clique family. First, a GLCH matrix is collected for the family, by convolving the displacement vector with the image. Second, the partial energy is computed by Eq. (6.3.4) from the collected statistics. A generic MGRF model only counts on the relative frequency, $F_a(q,s;q,s\in \mathbf{Q} \mid {g}^{\circ})$, of co-occurrence of every two grey levels $q$ and $s$, $q,s \in \mathbf{Q}$, so the resulting matrix has a dimensionality of $\vert\mathbf{Q}\vert \times \vert\mathbf{Q}\vert$. To have statistically meaningful estimates for small training images (e.g., $128\times 128-256 \times 256$) and also due to computational restrictions, a texture is typically converted into a 16-level gray-scale image before further processing [38].

Since the relative energy is sufficient for ranking clique families, the first approximation of relative partial energy $\mathsf{\varepsilon}_{a}^{\circ}$ in Eq. (6.3.4) is used to approximate the `real' partial energy $E_a$ in forming an MBIM. The procedure of computing the MBIM is outlined by Algorithm 5.

An MBIM is symmetric about the origin $(0,0)$, because a clique family $\mathbf{C}_{\delta{x_a},\delta{y_a}}$ has the same pixel interaction as the clique family $\mathbf{C}_{-\delta{x_a},-\delta{y_a}}$. It also should be noted that there is no such a clique family with a zero displacement vector $(0,0)$.

The major computation in constructing an MBIM comes from convolution operation in collecting the GLCH statistics for each clique family of the image. The process involves quadratic time complexity of $O(\vert\mathbf{R}\vert\cdot \vert\mathcal{W}\vert)$, which depends on the sizes of both the searching window and the training image.

An MBIM can be represented graphically either by a 2D bitmap or on a 3D surface, in which each coordinate $(\delta{x_a},\delta{y_a})$ represents a clique family $\mathbf{C}_{\delta{x_a},\delta{y_a}}$, and the corresponding scalar value represents the partial energy $E_a$ of that family. Figure 6.2 shows a few examples of 2D representation of MBIMs by grey-level images, with the partial energy encoded by intensity, i.e. dark intensities correspond to higher-energy clique families, light intensities correspond to lower-energy clique families. In Figs 6.3 and 6.4, the MBIMs are rendered on a 3D surface, where the $z$ values represent real-valued partial energies.

An MBIM reveals several important properties of the clique families in a texture, which helps to recover a characteristic neighbourhood and identify texels from a texture. Experimental comparisons have shown that the more accurate potential estimates in Appendix A produce quite similar MBIMs to those with the potentials of Eq. (6.3.3). For simplicity, below, only the latter estimates are used.