Approximate Potential Estimates

Recall Eq. (6.2.5). Given the neighbourhood $\mathcal{N}$, the specific log-likelihood of the potential:

$$\ell(\mathbf{V}\vert g^\circ) = \frac{1}{\vert\mathcal{R}\vert}\l... ...m\limits_{g\in\mathcal{G}} \exp\left( \mathbf{V}^\mathsf{T}\mathbf{F}(g)\right)$$ (A.0.1)

has the following gradient ( $\nabla\ell$) and the Hessian matrix ($\nabla^2$):

$$\begin{array}{lll} \nabla\ell(\mathbf{V}\vert g^\circ) & = & ... ... & = & -\mathbf{C}\{\mathbf{F}(g)\vert\mathbf{V}\} \end{array}$$ (A.0.2)

where $\E\{\ldots\vert\mathbf{V}\}$ denotes the math expectation under the GPD of Eq. (6.2.5) and $\mathbf{C}\{\mathbf{F}(g)\vert\mathbf{V}\}$ is the covariance matrix of the scaled empirical probability vectors. Because the covariance matrix is non-negatively defined, the log-likelihood is unimodal in the potential space [2]. The vector $\E\{\mathbf{F}(g)\vert\mathbf{V}\}$ of the scaled marginal co-occurrence probabilities in the vectorial equation $\nabla\ell(\mathbf{V}\vert g^\circ) = \mathbf{F}(g^\circ)- \E\{\mathbf{F}(g)\vert\mathbf{V}\} = 0$ for the exact MLE of $\mathbf{V}$ and the covariance matrix $\mathbf{C}\{\mathbf{F}(g)\vert\mathbf{V}\}$ are typically unknown except in the cases when the MGRF of Eq. (6.2.5) is reduced to an independent random field (IRF).

Starting from a potential $\mathbf{V}_0$ producing an IRF, the maximum likelihood estimate (MLE) of the potential is approximated by generalising the analytical approach proposed in [38].

PROPOSITION A.0.1   If the gradient and Hessian of Eq. (A.0.2) are known for an image $g^\circ$ and potential $\mathbf{V}_0$, the first approximation of the MLE:

$$\mathbf{V}^\ast = \mathbf{V}_0 + \lambda^\ast\nabla \ell(\mathbf{... ...nabla^2 \ell(\mathbf{V}_0\vert g^\circ) \nabla \ell(\mathbf{V}_0\vert g^\circ)}$$ (A.0.3)

maximises the second-order Taylor series expansion of the log-likelihood

$$\ell(\mathbf{V}\vert g^\circ) \approx \ell(\mathbf{V}_0\vert g^\c... ...)^\mathsf{T} \nabla^2 \ell(\mathbf{V}_0\vert g^\circ)(\mathbf{V}-\mathbf{V}_0)$$

along the gradient from $\mathbf{V}_0$.

It is easily proved by substituting $\mathbf{V}=\mathbf{V}_0 + \lambda\nabla \ell(\mathbf{V}_0\vert g^\circ)$ to the expansion and maximising the latter with respect to $\lambda$.

The approximate solution in [38] presumes the simplest IRF (denoted below $\mathrm{IRF}_0$) with zero potential $\mathbf{V}=\mathbf{0}$. It results in equal marginal probabilities $p(q) = \frac{1}{Q}$ of independent signals $g_{x,y}=q$; $q\in\mathcal;{Q}$, over $\mathcal{R}$ and equiprobable images in Eq. (6.2.5): $P_\mathbf{0}(g^\circ)=\frac{1}{Q^\vert\mathcal{R}\vert}$. In this case $\ell\{\mathbf{0}\vert g^\circ\}=-\ln Q$ and all pairwise co-occurrence probabilities are equal: $p_{\xi,\eta}(q,s)=\frac{1}{Q^2}$.

Let $\mathbf{P}_{0}$ be the vector of the scaled marginal co-occurrence probabilities for the $\mathrm{IRF}_0$: $\mathbf{P}_{0}^\mathsf{T} = \frac{1}{Q^2}\left[ \rho_{\xi,\eta}\mathbf{u}: (\xi,\eta)\in\mathcal{N} \right]$ where $\mathbf{u}^\mathsf{T}=[1,1,\ldots,1]$ is the $Q^2$-vector of unit components. Let $\mathbf{F}_\mathrm{cn}(g^\circ)$ be the vector of the centred scaled empirical co-occurrence probabilities $f_{\mathrm{cn};\xi,\eta}(q,s)=f_{\xi,\eta}(q,s\vert g^\circ)-\frac{1}{Q^2}$ for the image $g^\circ$, i.e. $\mathbf{F}_\mathrm{cn}^\mathsf{T}(g^\circ) = \left[ \rho_{\xi,\eta}[f_{\mathrm... ...(q,s\vert g^\circ) : (q,s)\in\mathcal{Q}^2 ]: (\xi,\eta)\in\mathcal{N} \right]$,

where $\sum_{(q,s)\in\mathcal{Q}^2}f_{\mathrm{cn};\xi,\eta}(q,s\vert g^\circ)=0$ for all $(\xi,\eta)\in\mathcal{N}$.

Then the log-likelihood gradient is $\nabla\ell(\mathbf{0}\vert g^\circ)=\mathbf{F}_\mathrm{cn}(g^\circ)\equiv \mathbf{F}(g^\circ)-\mathbf{P}_{0}$ and the covariance matrix $\mathbf{C}\{\mathbf{F}(g)\vert\mathbf{0}\}$ is closely approximated by the scaled diagonal covariance matrix $\mathbf{C}_\mathrm{ind}$ for the independent co-occurrence distributions: $\mathbf{C}\{\mathbf{F}(g)\vert\mathbf{0}\}\approx\mathbf{C}_\mathrm{ind}$ where $\mathbf{C}_\mathrm{ind} = \frac{1}{Q^2}\left(1 - \frac{1}{Q^2}\right)\mathsf{Diag} \left[ \rho_{\xi,\eta} \mathbf{u}: (\xi,\eta)\in\mathcal{N} \right]$.

PROPOSITION A.0.2   The first approximation of the potential MLE in the vicinity of zero point $\mathbf{V}_0 = \mathbf{0}$ is

$$\mathbf{V}^\ast=\frac{ \mathbf{F}_\mathrm{cn}^\mathsf{T}(g^\circ)... ...rc) }\mathbf{F}_\mathrm{cn}(g^\circ) \approx Q^2\mathbf{F}_\mathrm{cn}(g^\circ)$$ (A.0.4)

Proof. In line with Eq. (A.0.3), the maximising factor $\lambda^\ast$ is equal to

$$\frac{ \mathbf{F}_\mathrm{cn}^\mathsf{T}(g^\circ) \mathbf{F}_\mat... ...\in\mathcal{Q}^2}\left(f_{\xi,\eta}(q,s\vert g^\circ)-\frac{1}{Q^2}\right)^2 }$$

If $Q\gg 1$ and the lattice $\mathbf{R}$ is sufficiently large to assume that $\rho_{\xi,\eta}\approx 1$ for all clique families, it is simplified to $\lambda^\ast\approx Q^2$. $\qedsymbol$

Actual vs. Estimated Potentials for a General-case IRF.

In contrast to the $\mathrm{IRF}_\mathrm{eq}$, a general-case IRF on $\mathcal{R}$ has an arbitrary marginal probability distribution of signals $\mathbf{P}_\mathrm{irf}=(p_\mathrm{pix}(q): q\in\mathcal{Q})$. This IRF can be represented similarly to Eq. (6.2.5) by using the pixel-wise potential:

$$P_\mathrm{irf}(g^\circ)= \frac{1}{Z_\mathrm{irf}}\exp \left(\sum\... ...\vert \mathbf{V}^\mathsf{T}_\mathrm{pix}\mathbf{F}_\mathrm{pix}(g^\circ)\right)$$ (A.0.5)

where $\mathbf{V}_\mathrm{pix}^\mathsf{T} = [V_\mathrm{pix}(q): q\in\mathcal{Q}]$ is the potential $Q$-vector, $\mathbf{F}^\mathsf{T}_\mathrm{pix}(g^\circ) = [f_\mathrm{pix}(q\vert g^\circ): q\in\mathcal{Q}]$ is the corresponding vector of empirical marginal probabilities of signals, and $Z_\mathrm{irf}$ is the partition function. The latter has in this case the analytical form: $Z_\mathrm{irf}=\left( \sum_{q\in\mathcal{Q}}\exp V_\mathrm{pix}(q) \right )^{\vert\mathcal{R}\vert}$.

Assuming the centred potential, $\sum_{q\in\mathcal{Q}}V_\mathrm{pix}(q)=0$, it is easily shown that the actual potential MLE and its first approximation obtained for a training image $g^\circ$ much as in Proposition A.0.2 but for the IRF in Eq. (A.0.5) are, respectively,

$$\begin{array}{lll} V_\mathrm{pix}(q) & = & \ln f_\mathrm{pix}... ... f_\mathrm{pix}(q\vert g^\circ)-\frac{1}{Q} \right) \end{array}$$ (A.0.6)

Table A.1 presents both the estimates in a special case when one intensity, $q_\mathrm{sp}$, has the empirical probability $f_\mathrm{pix}(q_\mathrm{sp}\vert g^\circ) = f$ and all remaining intensities are equiprobable, $f_\mathrm{pix}(q\vert g^\circ) =\frac{1- f}{Q-1}$; $q\in\mathcal{Q}\backslash q_\mathrm{sp}$. The estimates are given in function of $Q$ and the relative probability $\beta=\frac{f(Q-1)}{1-f}$. For small $Q$, both the estimates are close to each other except for $f \approx 1$. But for larger $Q$, the approximate MLE of Eq. (A.0.4) exceeds considerably the actual one so that the approximation may be intolerably inaccurate for the MGRFs, too.

Table: Approximate (``e"), $V_\mathrm{pix}(q_\mathrm{sp})$, and actual (``a"), $V^\ast_\mathrm{pix}(q_\mathrm{sp})$, MLE of the centred potentials specifying the generic IRFs for the relative probability $\beta=\frac{f(Q-1)}{1-f}$ if $f_\mathrm{pix}(q_\mathrm{sp}\vert g^\circ) = f$ and $f_\mathrm{pix}(q\vert g^\circ) =\frac{1- f}{Q-1}$ for $q\in\mathcal{Q}\backslash q_\mathrm{sp}$.

		Relative probabilities $\beta$
$Q$		1.0	2.0	5.0	10	20	50	100	200	500	$10^3$	$10^4$	$10^5$	$\infty$
2	e	0.00	0.67	1.33	1.64	1.81	1.92	1.96	1.98	1.99	2.00	2.00	2.00	2.00
	a	0.00	0.35	0.80	1.15	1.50	1.96	2.30	2.65	3.11	3.45	4.61	5.76	$\infty$
	$f$	0.50	0.67	0.83	0.91	0.95	0.98	0.99	1.00	1.00	1.00	1.00	1.00	1.00
$2^2$	e	0.00	0.80	2.00	2.77	3.30	3.70	3.84	3.92	3.97	3.98	4.00	4.00	4.00
	a	0.00	0.52	1.21	1.73	2.25	2.93	3.45	3.97	4.66	5.18	6.91	8.63	$\infty$
	$f$	0.25	0.40	0.63	0.77	0.87	0.94	0.97	0.98	0.99	1.00	1.00	1.00	1.00
$2^3$	e	0.00	0.89	2.67	4.24	5.63	6.88	7.40	7.69	7.87	7.94	7.99	8.00	8.00
	a	0.00	0.61	1.41	2.01	2.62	3.42	4.03	4.64	5.44	6.04	8.06	10.1	$\infty$
	$f$	0.13	0.22	0.42	0.59	0.74	0.88	0.93	0.97	0.99	0.99	1.00	1.00	1.00
$2^4$	e	0.00	0.94	3.20	5.76	8.69	12.1	13.8	14.8	15.5	15.8	16.0	16.0	16.0
	a	0.00	0.65	1.51	2.16	2.81	3.67	4.32	4.97	5.83	6.48	8.63	10.8	$\infty$
	$f$	0.06	0.12	0.25	0.40	0.57	0.77	0.87	0.93	0.97	0.99	1.00	1.00	1.00
$2^5$	e	0.00	0.97	3.56	7.02	11.9	19.4	24.2	27.6	30.1	31.0	31.9	32.0	32.0
	a	0.00	0.67	1.56	2.23	2.90	3.79	4.46	5.13	6.02	6.69	8.92	11.2	$\infty$
	$f$	0.03	0.06	0.14	0.24	0.39	0.62	0.76	0.87	0.94	0.97	1.00	1.00	1.00
$2^6$	e	0.00	0.98	3.76	7.89	14.7	27.8	38.9	48.4	56.7	60.2	63.6	64.0	64.0
	a	0.00	0.68	1.58	2.27	2.95	3.85	4.53	5.22	6.12	6.80	9.07	11.3	$\infty$
	$f$	0.02	0.03	0.07	0.14	0.24	0.44	0.61	0.76	0.89	0.94	0.99	1.00	1.00
$2^7$	e	0.00	0.99	3.88	8.41	16.5	35.4	55.8	77.9	102.	113.	126.	128.	128.
	a	0.00	0.69	1.60	2.28	2.97	3.88	4.57	5.26	6.17	6.85	9.14	11.4	$\infty$
	$f$	0.01	0.02	0.04	0.07	0.14	0.28	0.44	0.61	0.80	0.89	0.99	1.00	1.00
$2^8$	e	0.00	1.00	3.94	8.69	17.7	41.1	71.4	112.	169.	204.	250.	255.	256.
	a	0.00	0.69	1.60	2.29	2.98	3.90	4.59	5.28	6.19	6.88	9.17	11.5	$\infty$
	$f$	0.00	0.01	0.02	0.04	0.07	0.16	0.28	0.44	0.66	0.80	0.98	1.00	1.00

More Accurate First Approximation of the MLE

is obtained if the starting potential $\mathbf{V}_0$ in Proposition A.0.1 produces a general-purpose IRF identified for the training image $g^\circ$ rather than the IRF$_0$.

PROPOSITION A.0.3   The potential $\mathbf{V}_0^\mathsf{T} = [V_{\mathrm{irf}:\xi,\eta}(q,s): (q,s)\in\mathcal{Q}^2;(\xi,\eta)\in\mathcal{N}]$ which components $V_{\mathrm{irf}:\xi,\eta}(q,s)=\frac{1}{\rho_{\xi,\eta}\vert\mathcal{N}\vert}V_\mathrm{pix}(q)$ scale the potential values $V_\mathrm{pix}(q)$; $q\in\mathcal{Q}$, of Eq. (A.0.6) reduces the MGRF of Eq. (6.2.5) to the general-purpose IRF with the marginal signal probability distribution $\mathbf{P}_\mathrm{irf} = \mathbf{F}_\mathrm{pix}(g^\circ)$.

Proof. Assuming that $\sum_{s\in\mathcal{Q}}f_{\xi,\eta}(q,s\vert g)=f_\mathrm{pix}(q\vert g)$ for all $(\xi,\eta)\in\mathcal{N}$, the normalised MGRF exponent is as follows:

$$\sum\limits_{(\xi,\eta)\in\mathcal{N}}\rho_{\xi,\eta}\sum\limits_... ...rt g) = \sum\limits_{q\in\mathcal{Q}}V_\mathrm{pix}(q)f_\mathrm{pix}(q\vert g)$$

The assumption holds precisely for the actual marginal signal co-occurrence and signal probability distributions and therefore is asymptotically valid for the empirical distributions, too, providing the lattice $\mathcal{R}$ is sufficiently large to ensure small deviations between the empirical and actual probabilities. $\qedsymbol$

If the potential $\mathbf{V}_0$ from Proposition A.0.3 is used in Proposition A.0.1, the resulting general-case IRF identified from $g^\circ$ has the specific log-likelihood

$$\ell\{\mathbf{V}_0\vert g^\circ\}=\sum\limits_{q\in\mathcal{Q}} f_\mathrm{pix}(q\vert g^\circ) \ln f_\mathrm{pix}(q\vert g^\circ)$$

and the co-occurrence probabilities $p_{\xi,\eta}(q,s)=f_\mathrm{pix}(q\vert g^\circ)f_\mathrm{pix}(s\vert g^\circ)$ for $(q,s)\in\mathcal{Q}^2$ and $(\xi,\eta)\in\mathcal{N}$. Therefore, the $nQ^2$-vector of the expected scaled probabilities is $\E\{\mathbf{F}(g)\vert\mathbf{V}_0\}^\mathsf{T} = \mathbf{P}^\mathsf{T}(g^\cir... ...{\xi,\eta}\boldsymbol{\phi}^\mathsf{T}(g^\circ):(\xi,\eta)\in\mathcal{N}\right]$ where $\boldsymbol{\phi}^\mathsf{T}(g^\circ)= \left[f_\mathrm{pix}(q)g^\circ)f_\mathrm{pix}(s\vert g^\circ): (q,s)\in\mathcal{Q}^2\right]$.

Let $\Delta_{\xi,\eta;q,s}=f_{\xi,\eta}(q,s\vert g^\circ) - f_\mathrm{pix}(q\vert g^\circ)f_\mathrm{pix}(s\vert g^\circ)$ denote the difference between the empirical and actual signal co-occurrence probabilities for the IRF identified from the image $g^\circ$. Let $\mathrm{var}_{q,s}$ be the variance of the latter probability: $\mathrm{var}_{q,s} = f_\mathrm{pix}(q\vert g^\circ)f_\mathrm{pix}(s\vert g^\ci... ...\left( 1 - f_\mathrm{pix}(q\vert g^\circ)f_\mathrm{pix}(s\vert g^\circ) \right)$. Then the gradient $\nabla\ell(\mathbf{V}_0\vert g^\circ) = \mathbf{F}(g^\circ)-\mathbf{P}(g^\circ)\equiv \mathbf{\Delta}(g^\circ)$ of the log-likelihood is the $nQ^2$-vector of the scaled differences: $\mathbf{\Delta}^\mathsf{T}(g^\circ) = \left[ \rho_{\xi,\eta}\Delta_{\xi,\eta;q,s}: (q,s)\in\mathcal{Q}^2 ]: (\xi,\eta)\in\mathcal{N} \right]$ and the covariance matrix $\mathbf{C}\{\mathbf{F}(g)\vert\mathbf{V}_0\}$ is closely approximated by the scaled diagonal matrix $\mathbf{C}_\mathrm{irf} = \mathsf{Diag}\left[\rho_{\xi,\eta}\boldsymbol{\psi}(g^\circ):\xi,\eta)\in\mathcal{N}\right]$ where $\boldsymbol{\psi}(g^\circ)$ is the $Q^2$-vector of the variances: $\boldsymbol{\psi}(g^\circ) = \left[ \mathrm{var}_{q,s}: (q,s)\in\mathcal{Q}^2\right]^\mathsf{T}$.

PROPOSITION A.0.4   The first approximation of the potential MLE in the vicinity of the point $\mathbf{V}_0$ from Proposition A.0.3 in the potential space is $\mathbf{V}^\ast = \mathbf{V}_0 + \lambda^\ast\mathbf{\Delta}(g^\circ)$ with the maximising factor

$$\lambda^\ast = \frac{ \mathbf{\Delta}^\mathsf{T}(g^\circ)\mathbf{... ...m\limits_{(q,s)\in\mathcal{Q}^2} \mathrm{var}_{q,s} \Delta_{\xi,\eta;q,s}^{2} }$$ (A.0.7)

Now for all the signal cardinalities $Q$ the actual MLE for the IRF and its approximation in Proposition A.0.4 completely agree so that the approximation is closer to the actual MLE than the previous one in Proposition A.0.2.