The UINTA Algorithm

The high-level algorithm for UINTA is as follows:

1. 
   The input degraded image ${\bf\tilde x}$ comprises a set of intensities $\{ \tilde x_t \}_{t \in \mathcal{T}}$, neighborhoods $\{ {\bf\tilde y}_t \}_{t \in \mathcal{T}}$, and regions $\{ {\bf \tilde z}_t \}_{t \in \mathcal{T}} = \{ (\tilde x_t, {\bf\tilde y}_t) \}_{t \in \mathcal{T}}$. These values form the initial estimate ${\bf\hat x}^0 = {\bf\tilde x}$ of a sequence of images ${\bf\hat x}^0, {\bf\hat x}^1, {\bf\hat x}^2, \ldots$.
   
2. 
   At iteration $m$, compute
   

   $$\forall t \in \mathcal{T}, \frac { \partial h ( \hat X_t^m, {\bf\... ...frac { \partial h ( \hat X_t \vert {\bf\hat y}_t^m ) } { \partial \hat x_t^m }.$$ (107)

   
   
   Each $\tilde x_t$ undergoes a gradient descent based on the entropy of the Markov PDF estimated from $\mathcal{A}_t$. The gradient descent is
   

   $$\frac {\partial \hat x_t} {\partial \tau} = - \frac {\partial h (\hat X, {\bf\hat Y})} {\partial \hat x_t}$$

   $$\approx \frac {1} {\vert\mathcal{T}\vert} \frac {\partial \log P (\hat x_t, {\bf\hat y}_t)} {\partial \hat x_t}$$

   $$= \frac {1} {\vert\mathcal{T}\vert} \frac {\partial \log P (\hat x_t \vert {\bf\hat y}_t)} {\partial \hat x_t}$$

   $$= - \frac {1} {\vert\mathcal{T}\vert} \frac {\partial \hat x_t} {\p... ...}_t - {\bf\hat z}_u,\Psi_d)} \Psi_d^{-1} ({\bf\hat z}_t - {\bf\hat z}_s) \Bigg)$$ (108)

   
   
   where ${\partial \hat x_t} / {\partial {\bf\hat z}_t}$ is a projection operation that projects a $d$-dimensional vector ${\bf\hat z}_t$ onto the dimension associated with the center pixel intensity $\hat x_t$, and $\tau$ is a dummy evolution parameter. Figure 4.2 elucidates this process.
   
3. 
   Construct the new image ${\bf\hat x}^{m+1}$, using gradient descent with first-order finite forward differences:
   

   $$\forall t \in \mathcal{T}, \hat x_t^{m+1} = \hat x_t^m - \lambda \frac { \partial h ( \hat X_t^m \vert {\bf\hat y}_t^m )} { \partial \hat x_t^m },$$ (109)

   
   
   where $\lambda$ is the time step associated with the gradient descent. Section 4.5 explains more about the choice of $\lambda$.
   
4. 
   Check stopping criteria, as explained in Section 4.5. If not done, go to Step 2, otherwise the latest image estimate ${\bf\hat x}^{m+1}$ is the output.

Figure 4.2: The mechanism for updating pixel intensities UINTA. (a) An example $2$D PDF $P (\tilde X, \tilde Y)$ on feature space $< \!\!\! \tilde x, \tilde y \!\!\!>$. (b) A contour plot of the PDF depicts the forces (vertical arrows) that reduce the entropy of the conditional PDFs $P (\tilde X \vert \tilde y)$, as in (4.3). (c) Some pixels in $\mathcal{A}_t$ (black dots) along with their neighborhoods (squares around the dots) yielding feature-space observations $(\tilde x_t, \tilde y_t)$. The square thickness indicates the weights, as in (4.3), for the intensities of pixels in $\mathcal{A}_t$. The square with thickest edges denotes the neighborhood around the pixel being processed. (d) Attractive forces (arrow width $\equiv$ force magnitude) act on an observation ( $(\tilde x, \tilde y)$:circle) towards other observations ( $(\tilde x_t, \tilde y_t)$:squares) in the set $\mathcal{A}_t$, as per (4.3). The resultant force acts towards the weighted mean (dotted circle), and the observation $(\tilde x, \tilde y)$ moves based on its projection (vertical arrow).