Deterministic Restoration Algorithms

The MAP optimization problem can be dealt with much faster if we give up the need to converge to a global maximum and be satisfied on finding local maxima. Indeed, using a smart choice for an initial estimate, one can obtain local-maximum solutions that serve the purpose just as well as the global-maximum solution. Besag suggested deterministic algorithms for the optimization, guaranteeing convergence to local maxima. Writing the posterior as

$$P ( {\bf x} \vert {\bf\tilde x} ) = P ( x_t \vert \{ x_u \}_{u \i... ...de x} ) P ( \{ x_u \}_{u \in \mathcal{T} \setminus \{t\}} \vert {\bf\tilde x} )$$ (89)

motivates us to employ an iterative restoration scheme where, starting from some initial image estimate ${\bf\hat x}^0$, we can always update the current estimate ${\bf\hat x}^i$, at iteration $i$, so that the posterior never decreases. The algorithm computes the next estimate ($i+1$) by cycling through all indices as follows:

1. 
   Label the indices in $\mathcal{T}$ as $t_1, t_2, \ldots, t_{\vert\mathcal{T}\vert}$. Set $i \leftarrow 1$.
   
2. 
   Set $t \leftarrow t_i$.
   
3. 
   Update value at index $t$:
   

   $$x_t \leftarrow \mathop{\mbox{argmax }}_{x_t} P ( x_t \vert \{ x_u \}_{u \in \mathcal{T} \setminus \{ t \}}, {\bf\tilde x} ).$$ (90)

   
   
   
   
4. 
   Increment index: $i \leftarrow i + 1$.
   
5. 
   If $i > \vert\mathcal{T}\vert$ stop, otherwise go to Step 2.

This algorithm is the iterated conditional modes (ICM) algorithm [14], because it repeatedly updates image values based on modes of the conditional PDFs in Step 3. We can compute the mode of such conditional PDF by using Bayes rule, Markovity, and (2.86), as follows:

$$\mathop{\mbox{argmax }}_{x_t} P ( x_t \vert \{ x_u \}_{u \in \mathcal{T} \setminus \{ t \}}, {\bf\tilde x} ) = \mathop{\mbox{argmax }}_{x_t} P ( x_t \vert \{ x_u \}_{u \in \mathcal{T} \setminus \{ t \}} ) P ( {\bf\tilde x} \vert {\bf x} )$$

$$= \mathop{\mbox{argmax }}_{x_t} P ( x_t \vert {\bf y}_t ) P ( \tilde x_t \vert x_t ),$$ (91)

where $P ( x_t \vert {\bf y}_t )$ is the prior and $P (\tilde x_t \vert x_t)$ is the likelihood determined from the statistical noise model.

The ICM algorithm guarantees convergence to a local maximum provided that no two neighboring indices are simultaneously updated. Updating all sites at once, namely synchronous updating that is typically observed in image-processing algorithms [99], may cause small oscillations. On the other hand, synchronous-updating schemes are easily parallelizable. A partially-synchronous updating scheme offers a compromise. Such a scheme relies on codings, as described before in Section 2.6.2, to partition the index set $\mathcal{T}$ into mutually-exclusive and collectively-exhaustive sets $\mathcal{T}_\alpha$ such that no two indices in the same set are neighbors. Then, we can simultaneously update the values at all indices in a set $\mathcal{T}_\alpha$, cycle through the sets to update all index values, and guarantee convergence as well. Such schemes, however, typically result in artifacts related to the order in which index values are updated and, hence, it is helpful to vary the coding scheme randomly after each iteration.

Owen introduced the iterated conditional expectation (ICE) [119,120,186] algorithm as a variation of the ICM procedure. The only difference between ICE and ICM is that ICE updates each intensity $x_t$ as the expectation of the posterior--the ICM updates rely on the posterior mode. The ICE update is the optimal choice, based on Bayesian decision theory, for a squared-error penalty associated with the posterior PDF [48]. In the same sense, the ICM update is optimal for a zero-one penalty [48]. The ICE algorithm modifies the update rule in Step 3 of the ICM algorithm to

$$x_t \leftarrow E \Big[ P ( x_t \vert \{ x_u \}_{u \in \mathcal{T} \setminus \{ t \}}, {\bf\tilde x} ) \Big].$$ (92)

The ICE algorithm also possesses good convergence properties [119,120,186]. The ICE steady state relates to the mean-field approximation [186] of the MRF where the spatial interactions between RVs are approximated by the interactions between their means.