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 @cse.iitb.ac.in
|
|
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 @cse.iitb.ac.in |
| 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.  |
Results    |
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 |