Suyash P. Awate Suyash P. Awate
Asha and Keshav Bhide Chair Professor
Computer Science and Engineering Department, Indian Institute of Technology (IIT) Bombay
Office: A-214, Kanwal Rekhi Building
Email: my-first-name
Research Publications Teaching Students CV Personal
Patch-Based Denoising : UINTA
Unsupervised Information-Theoretic Adaptive Filtering
An Iterative Non-Local Means Algorithm
(proposed simultaneously with Non-Local (NL) Means at CVPR 2005)
UINTA, Non-Local Means code available in multi-threaded C++ open-source Insight Toolkit (ITK) through these classes in the denoising module
Suyash P. Awate, Ross T. Whitaker
Unsupervised, Information-Theoretic, Adaptive Image Filtering with Applications to Image Restoration
IEEE Trans. Pattern Analysis & Machine Intelligence (TPAMI) 2006, Vol. 28, Num. 3, pp. 364-376
Suyash P. Awate, Ross T. Whitaker
Higher-Order Image Statistics for Unsupervised, Information-Theoretic, Adaptive Image Filtering
IEEE Computer Vision & Pattern Recognition (CVPR), June 2005, vol 2, pp 44-51
(podium presentation, acceptance rate ~ 6 %)
Image restoration and denoising is an important and widely studied problem in computer vision and image processing. Various image filtering strategies have been effective, but invariably make strong assumptions about the properties of the signal and/or degradation. Hence, these methods lack the generality to be easily applied to new applications or diverse image collections. This work describes a novel unsupervised, information-theoretic, adaptive filter (UINTA) that improves the predictability of pixel intensities from their neighborhoods by decreasing their joint entropy. In this way, UINTA automatically discovers the statistical properties of the signal and can thereby restore a wide spectrum of images. The paper(s) describe the formulation to minimize the joint entropy measure and presents several important practical considerations in estimating neighborhood statistics. It presents a series of results on both real and synthetic data along with comparisons with current state-of-the-art techniques, including novel applications to medical image processing.
Key Ideas Underpinning UINTA
Nonparametric Markov Modeling
Neighborhoods in images lie on low-dimensional manifolds in high dimensional spaces (we call this a feature space), as demonstrated by: (i) several studies on natural image statistics; and (ii) several previous works on empirical Markov statistics.

Each neighborhood can be considered as an observation from the Markov probability-density-function (PDF) underlying the image. If we can estimate this Markov PDF empirically, from the given image itself, then we can discover the MRF model underlying the image ! We can use this MRF model for processing the image. In that case, we no longer need to impose adhoc, strong, parametric models on the image. Rather, we adapt the Markov model based on the data.
Now the question is: how can we estimate the Markov PDFs from the observed image ? The answer lies in nonparametric density estimation. Out of several schemes in the literature, we employ the kernel-based Parzen-window density estimation scheme. It estimates a PDF from a random sample desrived from the PDF. This is essentially a data-interpolation scheme. The PDF estimate is a superposition of kernel functions placed at each observation or datum. In this way, each observation contributes to the PDF estimate. With an infinite sample size, the estimate converges (L2) to the true PDF.
UINTA Restoration Strategy based on Entropy Reduction
Degraded images, by definition, have less regularity in the Markov statistics as compared to their original nondegraded versions. This increases the randomness associated with the Markov PDF. Degradations reduce the predictability of pixel values from the values in their neighborhoods. UINTA attempts to counter the degradations by increasing this regularity. One measure of randomness associated with a PDF is the entropy and, hence, UINTA attempts to restore images by reducing the entropy of the stationary Markov PDF. UINTA is an iterative process.

The next figure shows the Parzen-window sampling scheme to estimate the PDF at a particular point (image neighborhood) in the feature space. We derive the sample randomly from the proximity/locality of the neighborhood. We find optimal values of the Parzen-window kernel-width based on a penalized maximum-likelihood (ML) scheme. {ML estimation closely relates to entopy minimization} The sample size can also be optimally estimated based on entropy reduction.
Neighborhood shape: Hypercube-shaped neighborhoods (e.g. square in 2D) produce results with undesirable artifacts exhibiting preferences for grid-aligned features. A solution is to weight the intensities, making neighborhoods more isotropic.

Handling image boundaries: Typical image boundary conditions, e.g., replicating pixels or toroidal topologies, can produce neighborhoods that distort the feature-space statistics. We handle boundary neighborhoods by collapsing the feature space along the dimensions corresponding to the neighbors falling outside the image. We crop the square regions crossing image boundaries and process them in the lower-dimensional subspace.  
Entropy reduction drives the pixel-intensity updates. How do the pixel-intensity updates actually look like, analytically?

There exists a mathematical relationship between the mean-shift procedure and entropy reduction, thereby establishing UINTA as a generalization of the mean-shift algorithm, which incorporates image neighborhoods to reduce the entropy of the associated conditional PDFs.

The mean-shift algorithm is a gradient descent on the Shannon entropy associated with the grayscale intensities of an image. In the mean-shift algorithm, each point in feature space is attracted towards every other point, with a weighting term that diminishes with the distance (Gaussian weighted if Gaussian kernel used) between the two point. The UINTA updates have the same form, except that it influences the weights not only by the distances between intensities, but also by the distances between the neighborhoods. That is, pixels in the image with similar neighborhoods have a relatively larger impact on the weighted mean that drives the updates of the center pixels.
Some results with UINTA and comparisons with other algorithms

For some texture-like or fractal-like images, repeated UINTA iterations converge to desirable images. However, convergence is not always the goal. A few iterations of UINTA are sufficient for adequate restoration.

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.

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, and we have used this approach in all of the examples for which the Gaussian-noise levels are known.

Comparing UINTA with wavelet denoisers

Comparing UINTA with NL-Means

Related Works
Marcelo Bertalmio. Image processing for Cinema. CRC Press. 2014
Peyman Milanfar
A Tour of Modern Image Filtering: New Insights and Methods, Both Practical and Theoretical
IEEE Signal Process. Mag. 30(1): 106-128 (2013)
Dowson N, Salvado O
Hashed nonlocal means for rapid image filtering
IEEE Trans. Pattern Analysis & Machine Intelligence (TPAMI) 2011, 33(3):485-99
Pizarro L, Mrazek P, Didas S, Grewenig S, Weickert J
Generalized nonlocal image smoothing
Int. J. Computer Vision (IJCV) 2010, 90(1):62-87
A. Singer, Y. Shkolnisky, B. Nadler
Diffusion Interpretation of Nonlocal Neighborhood Filters for Signal Denoising
SIAM J. Imaging Sciences 2009, 2(1):118-139
Suyash P. Awate, Ross T. Whitaker
Feature-Preserving MRI Denoising using a Nonparametric, Empirical-Bayes Approach
IEEE Trans. Medical Imaging (TMI) 2007, 26(9):1242-1255
A. Buades, B. Coll, J. M. Morel
A Review of Image Denoising Algorithms, With a New One
Multiscale Model. Simul. 2005, vol 4, num 2, pp 490-530
A. Buades, B. Coll, J. M. Morel
A Non-Local Algorithm for Image Denoising
IEEE Computer Vision and Pattern Recognition (CVPR), vol 2, pp 60-65, June 2005