Recent advances in patch-based image processing


Michael Elad (Technion)
Peyman Milanfar (University of California, Santa Cruz)
Gabriel Peyré (Universite Paris-Dauphine)

The past few years have witnessed the emergence of a series of papers that tackle various image processing tasks in a locally adaptive, patch-based manner. These methods serve various applications, such as denoising, deblurring, inpainting, image decomposition, segmentation, super-resolution reconstruction, and more. As the name suggests, these techniques operate locally in the image, applying the same process for every pixel by manipulating small patches of pixels. In this mini-symposium we intend to gather the leading researchers in this maturing arena to present a series of talks that will expose the current state of knowledge in this field.



Session 1.

Session 2.

Session 3.


Peyman Milanfar (University of California, Santa Cruz) - The Pat(c)h Ahead: A Wide-Angle View of Image Filtering - (slides)

Filtering 2- and 3-D data (i.e. images and video) is fundamental and common to many fields. From graphics, machine vision and imaging, to applied mathematics and statistics, important innovations have been introduced in the past decade which have advanced the state of the art in applications such as denoising and deblurring. While the impact of these contributions has been significant, little has been said to illuminate the relationship between the theoretical foundations, and the practical implementations. Furthermore, new algorithms and results continue to be produced, but generally without reference to fundamental statistical performance bounds. In this talk, I will present a wide-angle view of filtering, from the practical to the theoretical, and discuss performance analysis and bounds, indicating perhaps where the biggest (if any) improvements can be expected. Furthermore, I will describe various broadly applicable techniques for improving the performance of *any* given denoising algorithm in the mean-squared error sense, without assuming prior information, and based on the given noisy data alone.

Joseph Salmon (Duke University) - Poisson Noise Reduction with Non-local PCA - (slides)

Photon limitations arise in spectral imaging, nuclear medicine, astronomy and night vision. The Poisson distribution used to model this noise has variance equal to its mean so blind application of standard noise removals methods yields significant artifacts. Recently, overcomplete dictionaries combined with sparse learning techniques have become extremely popular in image reconstruction. The aim of the present work is to demonstrate that for the task of image denoising, nearly state-of-the-art results can be achieved using small dictionaries only, provided that they are learned directly from the noisy image. To this end, we introduce patch-based denoising algorithms which performs an adaptation of PCA (Principal Component Analysis) for Poisson noise. We carry out a comprehensive empirical evaluation of the performance of our algorithms in terms of accuracy when the photon count is very low. The results reveal that, despite its simplicity, PCA-flavored denoising appears to be competitive with other state-of-the-art denoising algorithms. Joint work with C-A. Deledalle, R. Willet and Z. Harmany.

Dimitri Van De Ville (EPFL) - Getting It Right: Parameter Selection for Non-Local Means using SURE - (slides)

Non-local means (NLM) is an effective denoising method that applies adaptive averaging based on similarity between neighborhoods in the image. An attractive way to both improve and speed-up NLM is by first performing a linear projection of the neighborhood. One particular example is to use principal components analysis (PCA) to perform dimensionality reduction. However, tuning the various parameters of the algorithm is a difficult problem due to their data dependency; e.g., width of the smoothing kernel, size of the neighborhood, dimensionality of the subspace when using PCA. To tackle this problem, we have derived an explicit analytical expression for Stein's unbiased risk estimate (SURE) in the context of NLM with linear projection of the neighborhoods. The SURE-NLM allows to monitor the MSE for restoration of an image corrupted by additive white Gaussian noise without knowledge of the noise-free signal. Moreover, the SURE comes with low computational cost. The SURE-NLM can then be used to optimize the parameters by combining it with a search algorithm in the parameter space. We propose an alternative based on the principle of linear expansions of multiple NLMs, each with a fixed parameter set, for which the optimal weights can be found by solving a linear system of equations. The experimental results demonstrate the accuracy of the SURE and its successful application to tune the parameters for NLM.

Charles Kervrann (IRISA) - Aggregation methods for optical flow computation - (slides)

In this talk, we address the problem of optical flow estimation, that is recovering the dense apparent motion of the pixels in a sequence of images. It is a fundamental computer vision task at the basis of a large variety of applications: object tracking, video compression, motion segmentation, movement detection, 3D reconstruction . . . Most of state of the art methods rely on a common global variational framework. Computing optical flow amounts to minimizing a global energy. Our experiments demonstrated that the restriction of the minimization to local regions yields significal improvements of the estimation. Motivated by this fact, we developped a novel method to take advantage of this local approach by deriving the global estimate from an aggregation of several local estimates. Our work can thus be seen as a general semi-local framework which can be used to improve the performance of any global variational method. In this document, we present the main ideas of the variational estimation of optical flow, and we describe our contribution which is related to the spatial aggregation of local estimates. We evaluate the performance of our approach on real and synthetic sequences.

Michael Elad (Technion) - A Generalized Tree-Based Wavelet Transform and Its Application to Patch-Based Image Denoising - (slides)

What if we take all the overlapping patches from a given image and organize them to create the shortest path by using their mutual distances? This suggests a reordering of the image pixels in a way that creates a maximal 1D regularity. Could we repeat this process in several 'scales'? What could we do with such a construction? In this talk we consider a wider perspective of the above line of questions: We introduce a wavelet transform that is meant for data organized as a connected-graph or as a cloud of high-dimensional points. The proposed transform constructs a tree that applies a 1D wavelet decomposition filters, coupled with a pre-reordering of the input, so as to best sparsify the given data. We adopt this transform to image processing tasks by considering the image as a graph, where every patch is a node, and vertices are obtained by Euclidean distances between corresponding patches. State-of-the-art image denoising results are obtained with the proposed scheme. Joint work with Idan Ram and Israel Cohen, Electrical Engineering Department - Technion.

Francois Meyer (Colorado) - Analysis of image patches: a unified geometric perspective - (slides)

Recent work in computer vision and image processing indicates that the elusive quest for the 'universal' transform has been replaced by a fresh perspective. Indeed, researchers have recently proposed to represent images as a 'collage' of small patches. The patches can be shaped into square blocks or into optimized contours that mimic the parts of a jigsaw puzzle. These patch-based appearance models are generative statistical models that can be learned from an image or a set of images. All these patch-based methods implicitly take advantage of the following fact: the dataset of patches, whether it is aggregated from a single image, or a library of images, is a smooth and low dimensional structure. In this work, we propose a unifying geometric theory to explain the success of patch-based method in image processing. In addition, we explain how geometric information such as tangent plane and curvature in patch-space can be used to process images in an optimal manner. This is a joint work with D.N. Kaslovsky, and B. Wohlberg.

Lei Zhang (Polyu UK) - Patched based image denoising with and without dictionary learning - (slides)

Patch based image processing has proved to be very effective for denoising. By exploiting the image nonlocal redundancy, some representative patch based methods such as BM3D have achieved state-of-the-art denoising results. In this talk, we will discuss the role of dictionary learning in patch-based image denoising (PID), and compare the denoising performance with and without dictionary learning. In the case of PID with dictionary learning, the dictionary can be pre-learned from clean example images, or it can be learned online from the noisy image, while the dictionary can be orthogonal or non-orthogonal. In the case of PID without dictionary learning, an analytically pre-designed dictionary such as DCT bases and wavelet/curvelet bases can be used, or the noisy patches themselves are directly used as a dictionary. In this talk, we will present extensive experiments to compare the various schemes, analyze their pros and cons, and discuss the future development of PID.

Hagit Hel-Or (University of Haifa) - Matching By Tone Mapping - (slides)

A fast pattern matching scheme termed Matching by Tone Mapping (MTM) is introduced which allows matching under non-linear tone mappings. We exploit the recently introduced Slice Transform to implement a fast computational scheme requiring computational time similar to the fast implementation of Normalized Cross Correlation (NCC). In fact, the MTM measure can be viewed as a generalization of the NCC for non-linear mappings and actually reduces to NCC when mappings are restricted to be linear. The MTM is shown to be invariant to non-linear tone mappings, and is empirically shown to be highly discriminative and robust to noise.

Gabriel Peyré (Universite Paris-Dauphine) - Optimal Transport Over the Space of Patches (DONE) - (slides)

In this talk, I will propose a new model for static and dynamic textures as a statistical distribution over the space of patches. This set of patches is described as a discretized manifold using a nearest neighbor graph. A library of textures defines a collection of high dimensional distributions. It is possible to navigate over the set of distributions using the machinery of optimal transport on the graph manifold. I will show several applications such as patch-based synthesis using optimal transport projection and texture mixing using geodesic transport interpolation.

Guillermo Sapiro (University of Minnesota) - Learning to sense GMMs - (slides)

In this work we describe methodologies to design the sensing matrix for efficient coding and detection of signals that follow a Gaussian Mixture Model. We describe both off-line and on-line techniques, in particular, two-step approaches that first detect the correct model and then optimally sense for it. Joint work with J. Duarte-Carvajalino, G. Yu, and L. Carin.

Alessandro Foi (Tampere University of Technology) - Patch Foveation in Nonlocal Imaging - (slides)

Patch-based nonlocal imaging methods rely on the assumption that natural images contain a large number of mutually similar patches at different locations within the image. Patch similarity is typically assessed through the Euclidean distance of the pixel intensities and therefore depends on the patch size: while large patches guarantee stability with respect to degradations such as noise, the mutual similarity that can be verified between pairs of patches tends to reduce as the patch size grows. Thus, a windowed Euclidean distance is commonly used to balance these two conflicting aspects, assigning lower weights to pixels far from the patch center. We propose patch foveation as an alternative to windowing in nonlocal imaging. Foveation is performed by a spatially variant blur operator, characterized by point-spread functions having bandwidth decreasing with the spatial distance from the patch center. Patch similarity is thus assessed by the Euclidean distance of foveated patches, leading to the concept of foveated self-similarity. In contrast with the conventional windowing, which is only spatially selective and attenuates sharp details and smooth areas in equal way, patch foveation is selective in both space and frequency. In particular, we present an explicit construction of a patch-foveation operator that, given an arbitrary windowing kernel, replaces the corresponding windowing operator providing equivalent attenuation of i.i.d. Gaussian noise, yet giving full weights to flat regions. Examples of this special form of self-similarity are shown for a number of imaging applications, with particular emphasis on image filtering, for which we demonstrate that foveated self-similarity is a more effective regularity assumption than the windowed self-similarity in assessing the patch similarity in nonlocal means denoising..

Gabriele Facciolo (ENS Cachan) - Analysis of a variational framework for exemplar based image inpainting - (slides)

We discuss a variational framework for exemplar based image inpainting, in which both the reconstructed image u and the non-local weights w are treated as variables and updated using the variational formulation. This approach permits to draw relations with some existing inpainting schemes, in addition to leading to novel ones. We carry out an analysis of two of these schemes providing existence of the solution, regularity of the minima and convergence of the alternating scheme for the variables (u,w).