160
6: Teerasit Kasetkasem
by an additive noise before being captured by a non-linear photographic device. Then, based on the maximum a posteriori (MAP) criterion (Trees 1968;
Varshney 1997), an image restoration scheme selected the most likely noiseless image (configuration) given an observed image. Here, a standard iterative
search technique such as direct descent cannot be used to search for the solution due to the severe non-convexity of the MAP equation. As a result, this
noiseless image may be obtained by using the simulated annealing (SA) algorithm, which iteratively generates a sequence of random images converging to
the desired result under the MAP criterion. Here, the SA algorithm visits all the
sites (pixels) in the image and updates the corresponding configuration (e. g.
intensity value) of a visited site. The new configuration of a pixel is generated
through a random number generator whose underlying probability depends on
observed information at that site and configurations of its neighboring pixels.
A similar approach to solve the problem under the MAP criterion is implemented in the Metropolis algorithm (Winkler 1995) where a new configuration is proposed randomly and the algorithm can either accept or reject this
proposed configuration based on its underlying probability. Hasting (1970)
generalized the Metropolis algorithm to the Metropolis-Hasting (MH) algorithm where the proposed configuration can have any well-defined probability
density function (PDF). Begas (1986) developed an iterated conditional modes
(ICM) algorithm to speed up the image restoration process. The ICM algorithm
converges within several iterations whereas the previous algorithms may take
hundreds of iterations. However, the ICM algorithm may have lower performance because it converges to the closest saddle point, which is more likely to
be a local one. As an alternative to the MAP criterion, Marroguin et al. (1987)
chose to maximize the a posteriori marginal (MPM) where the goal is to minimize the expectation of a cost function. They claimed that the MPM criterion
outperforms the MAP criterion under low signal to noise ratio conditions.
The above methods are based on Monte Carlo procedures. A method not
based on the Monte Carlo procedure is the graduated nonconvexity (GNC)
algorithm introduced by Nikolova (1999). This algorithm follows a different
approach and directly combats the severe nonconvexity of the objective function. The objective function is assumed to be composed of two terms. The
first term is convex while the second term is nonconvex. At the beginning,
nonconvexity is removed by setting the nonconvex term equal to zero. Then,
the corresponding global optimal is determined by using the conventional
derivative. Next, nonconvexity is gradually inserted back by multiplying the
nonconvex term with a positive constant, r E (0,1), and the local optimal
closest to the current location is obtained by a gradient search. This process
is repeated until the original nonconvex function is reached when r = 1. It
was shown that under a proper release schedule of nonconvexity, the global
optimum point could be reached. However, the GNC algorithm is valid only if
an objective function is twice differentiable which might not be true in general.
Before we discuss the implications ofMRF models to remote sensing applications in Chaps. 11 and 12, some basic concepts related to the MRF model
are presented in this chapter. Section 6.2 is devoted to a detailed discussion
of an MRF and its equivalent form, namely a Gibbs field. We also establish
6: Teerasit Kasetkasem
by an additive noise before being captured by a non-linear photographic device. Then, based on the maximum a posteriori (MAP) criterion (Trees 1968;
Varshney 1997), an image restoration scheme selected the most likely noiseless image (configuration) given an observed image. Here, a standard iterative
search technique such as direct descent cannot be used to search for the solution due to the severe non-convexity of the MAP equation. As a result, this
noiseless image may be obtained by using the simulated annealing (SA) algorithm, which iteratively generates a sequence of random images converging to
the desired result under the MAP criterion. Here, the SA algorithm visits all the
sites (pixels) in the image and updates the corresponding configuration (e. g.
intensity value) of a visited site. The new configuration of a pixel is generated
through a random number generator whose underlying probability depends on
observed information at that site and configurations of its neighboring pixels.
A similar approach to solve the problem under the MAP criterion is implemented in the Metropolis algorithm (Winkler 1995) where a new configuration is proposed randomly and the algorithm can either accept or reject this
proposed configuration based on its underlying probability. Hasting (1970)
generalized the Metropolis algorithm to the Metropolis-Hasting (MH) algorithm where the proposed configuration can have any well-defined probability
density function (PDF). Begas (1986) developed an iterated conditional modes
(ICM) algorithm to speed up the image restoration process. The ICM algorithm
converges within several iterations whereas the previous algorithms may take
hundreds of iterations. However, the ICM algorithm may have lower performance because it converges to the closest saddle point, which is more likely to
be a local one. As an alternative to the MAP criterion, Marroguin et al. (1987)
chose to maximize the a posteriori marginal (MPM) where the goal is to minimize the expectation of a cost function. They claimed that the MPM criterion
outperforms the MAP criterion under low signal to noise ratio conditions.
The above methods are based on Monte Carlo procedures. A method not
based on the Monte Carlo procedure is the graduated nonconvexity (GNC)
algorithm introduced by Nikolova (1999). This algorithm follows a different
approach and directly combats the severe nonconvexity of the objective function. The objective function is assumed to be composed of two terms. The
first term is convex while the second term is nonconvex. At the beginning,
nonconvexity is removed by setting the nonconvex term equal to zero. Then,
the corresponding global optimal is determined by using the conventional
derivative. Next, nonconvexity is gradually inserted back by multiplying the
nonconvex term with a positive constant, r E (0,1), and the local optimal
closest to the current location is obtained by a gradient search. This process
is repeated until the original nonconvex function is reached when r = 1. It
was shown that under a proper release schedule of nonconvexity, the global
optimum point could be reached. However, the GNC algorithm is valid only if
an objective function is twice differentiable which might not be true in general.
Before we discuss the implications ofMRF models to remote sensing applications in Chaps. 11 and 12, some basic concepts related to the MRF model
are presented in this chapter. Section 6.2 is devoted to a detailed discussion
of an MRF and its equivalent form, namely a Gibbs field. We also establish