Convergence

The UINTA updates are closely related to the ICM updates (described in Section 2.6.3) with a uniform prior. If the prior PDF $P ( \tilde X_t \vert x_t )$ is uniform over the range of intensities in the image, then ICM guarantees convergence when every update for $x_t$ increases the probability $P_{\mathrm{Markov}} ( x_t \vert {\bf y}_t )$; where $P_{\mathrm{Markov}} ({\bf Z})$ is the stationary Markov PDF. The analysis of ICM [16] shows that synchronous-update schemes, i.e., when all pixel intensities update at once as in UINTA, can cause small oscillations while other schemes can cause artifacts [16,99].

We can show that with an appropriate update schedule as dictated by the analysis of ICM, UINTA guarantees convergence to a local mode of $P_{\mathrm{Markov}} ( {\bf\tilde Z} )$. We do this by relating the UINTA updates to the mean-shift algorithm. Cheng [27] analyzes a certain kind of mean-shift procedure, namely the blurring process, where the evolving sample of points redefines the nonparametric PDFs based on which it evolves. This is exactly the nature of the mean-shift procedure in UINTA where pixel-intensity updates redefine the nonparametric PDFs that are used for the next update. Based on Cheng's results (Theorem 5 in [27]), we deduce that points in the set $\mathcal{S}' = \{ s' \}$ evolving based on Gaussian Parzen-window kernels converge to the local mode of a PDF $f (\cdot)$ that is estimated using Gaussian kernels on the initial set $\mathcal{S}'$. Every update brings the points $\{ s' \}$ closer to the local mode of the PDF $f (\cdot)$ and, hence, increase their probability $f (s')$. In UINTA, the sample comprises image neighborhoods ${\bf\tilde z}_t$ and, hence, the nonparametrically estimated PDF $f (\cdot)$ converges to the stationary Markov PDF $P_{\mathrm{Markov}} ( {\bf\tilde Z} )$. In every UINTA update, therefore, the pixel intensities $x_t$ must change such that the $P_{\mathrm{Markov}} ( x_t \vert {\bf y}_t )$ increases. Therefore, with an appropriate update schedule as dictated by the analysis of ICM, UINTA guarantees convergence to a local mode of $P_{\mathrm{Markov}} ( {\bf\tilde Z} )$.

We have found that UINTA can produce small oscillations when using the mean-shift based time step $\lambda = \vert\mathcal{T}\vert \sigma^2$ together with a synchronous-updates scheme. Because other update schedules typically produce artifacts [16,99] related to the order in which the pixels are updated, we prefer to use UINTA with the synchronous-update scheme with a smaller time step of $\lambda = 0.2 \vert\mathcal{T}\vert \sigma^2$ that significantly reduces the oscillations.

An analysis of simple examples shows the existence of nontrivial steady states, e.g., an image which is a discrete sampling of a linear function such as a ramp or a binary image of a checkerboard. Empirical evidence shows that the filtering algorithm does sometimes converge to interesting results--Figure 4.3 gives two such examples where the UINTA iterations converges to a useful steady state. However, for most applications, convergence to a fixed point is not a useful goal. As with many other iterative filtering strategies, several iterations of the gradient descent are sufficient for acceptable restoration, but this requires either parameter tuning or the definition of suitable stopping criteria.

Figure 4.3: UINTA convergence. (a),(d) Uncorrupted images consisting of textures: a binary checkerboard image and a fractal image containing triangles. (b),(e) Images corrupted with i.i.d. additive Gaussian noise. (c),(f) Restored images that correspond to the steady-state of UINTA, i.e., the UINTA iterations converge to these images.

The choice of stopping criteria for this algorithm depends on a number of factors. For instance, in the absence of any knowledge of the signal, noise, or other types of degradation, the algorithm will inevitably require some parameter tuning. We assume that noiseless images have conditional PDFs with low entropy, and degradations substantially increase this randomness. We have found empirically that entropy reduction via gradient descent starts by counteracting the randomness introduced by the noise much more than reducing the inherent randomness in the signal. Thus an effective strategy is to stop when the relative rate of change of entropy, from one iteration to the next, falls below some threshold.

Figure 4.4: Root-mean-square (RMS) errors versus iterations for several images (see Section 4.6) with varying additive-noise levels. The circles represent the points where the residual equals the noise level.

When the level of additive noise is known, UINTA can iterate until the root-mean-square (RMS) difference (residual) between input and the processed image equals the noise level. We have found empirically that this method is quite effective (see Figure 4.4), and we have used this approach in all of the examples for which the Gaussian-noise levels are known.