Analytical Method for MGRF Potts Model Parameter Estimation∗ Asem M. Ali1 Aly A. Farag1 Georgy Gimel’farb2 1 Computer Vision and Image Processing Laboratory, University of Louisville, USA. {asem,farag}@cvip.uofl.edu 2
Department of Computer Science, The University of Auckland, New Zealand.
[email protected]
Abstract This paper proposes a new analytical method for estimating parameters of a homogeneous isotropic Potts model with an asymmetric Gibbs potential function. The model is generalized by including both pairwise and triple cliques. The maximum likelihood estimates of the cliques potentials are obtained by a further elaboration of the approximate analytical estimator proposed in [8]. Experiments with synthetic textures have shown that our potential estimates are more accurate and practicable than their counterparts obtained with classical methods.
1. Introduction Fitting an Markov Random Field (MRF) model to an image requires estimating its parameters from a sample of the image. The literature is rich with works that propose different Markov-Gibbs Random Field (MGRF) models, which are suitable for a specific system behavior. Usually, these works identify parameters of the models using an optimization technique trying to maximize either the likelihood or the entropy of the probability distributions involved. The Maximum Likelihood Estimates (MLE) are most popular in finding unknown parameters of a distribution (see e.g. [4, 7, 9].) Let Θ be a vector of potential parameters (e.g. in a second order neighborhood system) for a homogeneous anisotropic Potts model with pairwise cliques1 : Θ = [γ1 , γ2 , γ3 , γ4 ] or triple cliques: ∗ This research has been supported by US National Science Foundation Grant IIS-0513974. 1 A clique is defined as a set of sites (e.g. image pixels) such that all pairs of sites are mutual neighbors in accord with a given neighborhood system N [6].
978-1-4244-2175-6/08/$25.00 ©2008 IEEE
Θ = [γ5 , γ6 , γ7 , γ8 ]. The Gibbs probability distribution is represented as a function of Θ as follows: P (f ) =
1 exp − Z
X
V (f , Θ)
(1)
{p,q}∈N
where Z is a normalizing factor, V is the potential function, and f is a realization of the MGRF. The log-likelihood function is defined as L(f |Θ) =
1 log P (f ) |P|
(2)
where P is the set of sites of the realization f (e.g. P is the set of image pixels if f represents an image). Thus, the MLE of Θ is defined by −1 Θ∗ = arg max |P| Θ
P
V (f , Θ) + log Z(Θ)
{p,q}∈N
(3) Equation (3) cannot be solved by the differentiation of the log-likelihood because the second term log(Z(Θ)) is intractable. Thus, numerical techniques are usually used to find a solution for this problem. One of the popular MRF parameter estimators is the Coding Method (CM) proposed by Besag [1]. In this method, the image grid is partitioned into coding patterns. The codings are chosen such that the distribution of the pixel values within one coding pattern are statistically independent of the pixel values in the other coding patterns. The coding method estimates the vector parameters Θ by finding the vectors Θj maximizing each the log-likelihood Lj (Θ) for the coding pattern j. Then the estimate of the vector Θ for the model is built as the average of the vectors Θj for all the all coding patterns. The Least Square Error (LSQR) method was proposed by Derin and Elliot [3]. They established different 3×3 color blocks
of pixels: for a pixel p with the color fp and the 8neighborhood Np , the block is (fp , fNp ). Each different 3 × 3 block of colors establishes a block type. Let l1 , l2 denote colors for two particular pixels p with the same neighborhoods Np . One can formulate a linear equation for the ratio of the probabilities of this pair of blocks. This ratio is estimated by counting the number of blocks of each type. In order to estimate the model parameters using the least square methods, one needs to solve an overdetermined system of linear equations for the most frequently occurring block types. Farag et al. [5] proposed an analytical approach to estimate the parameter of the homogenous isotropic MGRF model. The potential function of Potts model governs symmetric pairwise co-occurrences of the region labels. To identify the homogeneous isotropic Potts model that describes the image f , they need to estimate only one potential value γ1 = γ2 = γ3 = γ4 = γ. This parameter was obtained analytically using the approximate maximum likelihood estimate (MLE) for a generic MGRF [7, 8]. Unlike common computer vision studies, this work adopts the pairwise and triple homogenous isotropic MGRF model to be an image model with the Potts prior. Similar to Farag et al. [5], parameters of this model are analytically estimated. However, this work focuses on asymmetric pairwise cooccurrences of the region labels. The asymmetric Potts model is chosen to provide more chances to guarantee that the Gibbs energy function is submodular, so it can be globally minimized using a standard graph cuts approach in polynomial time.
2
The Proposed Approach
The Gibbs potential governing asymmetric pairwise co-occurrences of the region labels can be described as follows: V (fp , fq ) = γδ(fp 6= fq )
(4)
where the indicator function δ(A) equals 1 when the condition A is true and zero otherwise. Then the MGRF model of region maps is specified by the following Gibbs probability distribution: −
P (f ) =
1 Z
e
P {p,q}∈N
V (fp ,fq )
=
1 Z
e−γ|T |Fneq (f )
(5)
Here, T = {{p, q} : p, q ∈ P; {p, q} ∈ N } is the family of the neighboring pixel pairs supporting the Gibbs potentials, |T | is its cardinality, and
Fneq (f ) denotes the relative frequency of the nonequal labels in the pixel pairs of that family: X 1 Fneq (f ) = δ(fp 6= fq ) (6) |T | {p,q}∈T
To completely identify the Potts model that describes the image f , the potential value γ specifying the Gibbs potential has to be estimated. In so doing, the MGRF model is identified, much as in [7, 8], using a reasonably close first approximation of the maximum likelihood estimate of γ. Us1 ing (5), the model log-likelihood L(f |γ)= |P| log P (f ) can be rewritten as follows: X ˆ 1 L(f |γ) = −γρFneq (f ) − |P| log e−γ|T |Fneq (f ) (7) ˆ f ∈F
where F is the set of all realizations and ρ = |T | |P| . The model log-likelihood (7) can be approximated by truncating the Taylor’s series expansion of L(f |γ) to the first three terms in the close vicinity of the zero potential, γ = 0: |γ) L(f |γ) ≈ L(f |0) + γ dL(f |γ=0 + 12 γ 2 d dγ
˛ ˛ ˛
2 L(f |γ) ˛ dγ 2
(8)
γ=0
The first derivative of the log-likelihood (7) is dL(f |γ) dγ
= −ρFneq (f ) + ρE{Fneq (ˆf )|γ}
(9)
where E{.} denotes math expectation. By replacing Fneq (.) with 1 − Feq (.), it becomes: dL(f |γ) = ρ Feq (f ) − E{Feq (ˆf )|γ} (10) dγ If γ = 0, this MGRF becomes the independent random field (IRF) of the equiprobable K colors, so 1 that the expectation E{Feq (ˆf )|0} = K . Thus in the vicinity of the origin γ = 0, the first derivative of the log-likelihood is equal to dL(f |γ) 1 (11) |γ=0 = ρ Feq (f ) − K dγ Similarly, it can be shown that in the vicinity of the origin the the second derivative of the loglikelihood has the following form: d2 L(f |γ) |γ=0 dγ 2
= −ρ K−1 K2
(12)
and the approximate log-likelihood (8) becomes 2 L(f |γ) ≈ −|P| log K + ργ Feq (f ) − K1 − γ2 ρ K−1 K2 (13) To maximize the approximate log-likelihood (13), |γ) = 0. This results in the following aplet dL(f dγ proximate MLE of γ: K−1 K2 − Fneq (f ) ≈ K 1 − Fneq (f ) (14) γ ∗ = K−1 K
2.1
Triple Clique Potential
The Gibbs potential governing asymmetric triple co-occurrences of the region labels can be described as follows: V (fp , fq ) = γ(1 − δ(fp = fq = fr ))
(15)
(a) γ = 0.1
(b) γ = 0.75
(c) γ = 1.0
(d) γ = 1.75
Following the above method for the pairwise potentials, one can prove that the potentials of the third order cliques have the analytical form similar to (14): 4 K 2 −1 γ ∗ = KK2 −1 −Fneq (f ) ≈ K 2 1−Fneq (f ) (16) K2 with the frequency P Fneq (f ) = |T1 | {p,q,r}∈T (1−δ(fp = fq = fr )) (17)
3
Figure 1. Samples of the synthesized binary images of size 128 × 128.
Experiments and Discussion
We tested the robustness of the proposed method for estimating Gibbs potentials of the Potts model by applying it to simulated texture images with known potential values. These images were generated using the Gibbs sampler approach [2]. The idea of the synthesis process is to find the configuration f in F which maximizes the probability P (f ). To assess the robustness of the proposed approach, many experiments were conducted. In the first experiment, four binary different realizations of the homogeneous isotropic Potts model were generated. Samples of these realizations for images of size 128 × 128 are shown in Fig. 1. To get the accurate statistics, 100 realizations were generated for each type of the model, and the proposed method was used to estimate the parameter γ for these data sets. The means and the variances, which are written in parentheses, for these 100 realizations of each type are shown in Table 1. In the second experiment, four different realizations of the Potts model were generated with 32 colors (i.e., K = 32). Samples of these realizations for images of size 128 × 128 are shown in Fig.2. Also, 100 realizations were generated for each type of the model and for different image sizes, and the proposed method was used to estimate the model parameter γ for these data sets. The means and the variances for the realizations for each type are shown in Tables 2–5. For comparison, the estimates obtained with the Coding Method (CM) [1] and the Least Square Error method (LSQR) [3] are also shown. The CM allows for an easy formulation of the estimator
for the auto-binomial model. However, it is generally considered difficult to be used reliably [3]. Picard [9] confirmed that the performance of the CM varies widely for different data. In our experiments the CM worked well for some images but poorly for others (e.g. γ = 1.75, 25 and γ = 0.75, 5 in Tables 1–5, respectively). Also, Picard [9] mentioned that the CM estimates sometimes need to be adjusted upward. In our experiments, the CM estimates of the Potts model parameters with 32 colors were adjusted by 10. Another disadvantage of the CM is that this technique requires a good initial guess for convergence to the optimal siolution and may run into local optima far away from the proper solution [4] as shown in the cases of binary realizations for γ = 0.75 and 32-colors realizations for γ = 5. Derin and Elliott [3] in their implementation of the LSQR claimed an accurate estimation by using the most frequently occurring block types. However, there is no consistent way to establish these types of blocks [4]. Also, to estimate the model parameters using the LSQR for binary realizations (e.g., Fig. 1), one needs to solve an overdetermined system of linear equations with up to 28 = 256 equations. But this is not practical in the case of 32 colors where the overdetermined system of equations has up to 328 equations. In the last experiment, two different realizations of the Potts model with triple cliques were synthesized (see Fig. 3). The means and the variances of the estimated parameters for 100 samples of each type are also shown in Fig. 3. This paper proposed an analytical method to identify homogeneous Potts models with asym-
(a) γ = 0.5
(b) γ = 5
(c) γ = 10
(d) γ = 25
Figure 2. Synthesized images of size 128× 128 with 32 colors and pairwise cliques.
Figure 3. Synthesized images with 32 colors and higher order cliques. metric Gibbs potential functions. Our experiments showed that the proposed analytical estimates of the potentials outperform two classical methods (the CM and the LSQR). The statistical evaluation highlighted the robustness of the proposed analytical approach for both the pairwise and higher order cliques. This promising accurate identification of the MGRF model can be used in many other computer vision problems.
References [1] J. E. Besag. Spatial interaction and the statistical analysis of lattice systems. J. Royal Stat. Soc., Series B, 36:192–236, 1974. [2] C. C. Chen. Markov Random Field Models in Image Analysis. PhD thesis, Michigan State University, East Lansing, 1988. [3] H. Derin and H. Elliott. Modeling and segmentation of noisy and textured images using Gibbs random fields. IEEE Trans. PAMI, 9(1):39–55, 1987.
[4] R. C. Dubes and A. K. Jain. Random field models in image analysis. J. Appl. Stat., 16:131–164, 1989. [5] A. A. Farag, A. El-Baz, and G. Gimel’farb. Density estimation using modified Expectation– Maximization for a linear combination of Gaussians. In Proc. ICIP, volume 3, pages 1871–1874, 2004. [6] S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. PAMI, 6:721–741, 1984. [7] G. L. Gimel’farb. Texture modeling with multiple pairwise pixel interactions. IEEE Trans. PAMI, 18(11):1110–1114, 1996. [8] G. L. Gimel’farb. Image Texture and Gibbs Random Fields. Kluwer Academic Publishers: Dordrecht, 1999. [9] R. W. Picard. Gibbs random fileds: Temperature and parameter analysis. In Proc. ICASSP, volume III, pages 45–48, San Francisco, March 1992.
