Suyash P.
Awate Associate Professor Computer Science and Engineering Department, Indian Institute of Technology (IIT) Bombay Office: A214, Kanwal Rekhi Building Email: myfirstname @cse.iitb.ac.in 

Research  Publications  Teaching  Students  CV  Personal 
PatchBased Denoising : UINTA Unsupervised InformationTheoretic Adaptive Filtering An Iterative NonLocal Means Algorithm (proposed simultaneously with NonLocal (NL) Means at CVPR 2005) 
UINTA, NonLocal Means code available in multithreaded C++ opensource Insight Toolkit (ITK) through these classes in the denoising module 
Suyash P. Awate, Ross T. Whitaker Unsupervised, InformationTheoretic, Adaptive Image Filtering with Applications to Image Restoration IEEE Trans. Pattern Analysis & Machine Intelligence (TPAMI) 2006, Vol. 28, Num. 3, pp. 364376 
Suyash P. Awate, Ross T. Whitaker HigherOrder Image Statistics for Unsupervised, InformationTheoretic, Adaptive Image Filtering IEEE Computer Vision & Pattern Recognition (CVPR), June 2005, vol 2, pp 4451 (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, informationtheoretic, 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 stateoftheart techniques, including novel applications to medical image processing. 
Key Ideas Underpinning UINTA 
Nonparametric Markov Modeling 
Neighborhoods in images lie on lowdimensional
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 probabilitydensityfunction (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 kernelbased Parzenwindow density estimation
scheme. It estimates a PDF from a random sample desrived from the PDF.
This is essentially a datainterpolation 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 Parzenwindow 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 Parzenwindow kernelwidth based on a penalized maximumlikelihood (ML) scheme. {ML estimation closely relates to entopy minimization} The sample size can also be optimally estimated based on entropy reduction. 
Neighborhood shape:
Hypercubeshaped neighborhoods (e.g. square in 2D) produce results with
undesirable artifacts exhibiting preferences for gridaligned 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 featurespace 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 lowerdimensional subspace. 
Entropy reduction drives the pixelintensity
updates. How do the pixelintensity updates actually look like,
analytically? There exists a mathematical relationship between the meanshift procedure and entropy reduction, thereby establishing UINTA as a generalization of the meanshift algorithm, which incorporates image neighborhoods to reduce the entropy of the associated conditional PDFs. The meanshift algorithm is a gradient descent on the Shannon entropy associated with the grayscale intensities of an image. In the meanshift 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 texturelike or fractallike 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 rootmeansquare (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 Gaussiannoise levels are known. 
Results 
Comparing UINTA with wavelet denoisers

Comparing UINTA with NLMeans

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): 106128 (2013) 
Dowson N, Salvado O Hashed nonlocal means for rapid image filtering IEEE Trans. Pattern Analysis & Machine Intelligence (TPAMI) 2011, 33(3):48599 
Pizarro L, Mrazek P, Didas S, Grewenig S,
Weickert J Generalized nonlocal image smoothing Int. J. Computer Vision (IJCV) 2010, 90(1):6287 
A. Singer, Y. Shkolnisky, B. Nadler Diffusion Interpretation of Nonlocal Neighborhood Filters for Signal Denoising SIAM J. Imaging Sciences 2009, 2(1):118139 
Suyash P. Awate, Ross T. Whitaker FeaturePreserving MRI Denoising using a Nonparametric, EmpiricalBayes Approach IEEE Trans. Medical Imaging (TMI) 2007, 26(9):12421255 
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 490530 
A. Buades, B. Coll, J. M. Morel A NonLocal Algorithm for Image Denoising IEEE Computer Vision and Pattern Recognition (CVPR), vol 2, pp 6065, June 2005 