

Minisymposium SIAM IS12
Recent advances in patchbased image processing
Organisers:
Michael Elad (Technion) Peyman Milanfar (University of California, Santa Cruz) Gabriel Peyré (Universite ParisDauphine)
The past few years have witnessed the
emergence of a series of papers that tackle various image processing tasks
in a locally adaptive, patchbased manner. These methods serve various
applications, such as denoising, deblurring,
inpainting, image decomposition, segmentation, superresolution
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
minisymposium 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.
Abstract
Peyman Milanfar (University of California, Santa Cruz)  The Pat(c)h Ahead: A WideAngle View of Image Filtering  (slides)
Filtering 2 and 3D 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 wideangle 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 meansquared error sense, without assuming prior information, and based on the given noisy data alone. Joseph Salmon (Duke University)  Poisson Noise Reduction with Nonlocal 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 stateoftheart results can be achieved using small dictionaries only, provided that they are learned directly from the noisy image. To this end, we introduce patchbased 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, PCAflavored denoising appears to be competitive with other stateoftheart denoising algorithms.
Joint work with CA. Deledalle, R. Willet and Z. Harmany. Dimitri Van De Ville (EPFL)  Getting It Right: Parameter Selection for NonLocal Means using SURE  (slides)
Nonlocal 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 speedup 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 SURENLM allows to monitor the MSE for restoration of an image corrupted by additive white Gaussian noise without knowledge of the noisefree signal. Moreover, the SURE comes with low computational cost.
The SURENLM 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 semilocal
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 TreeBased Wavelet Transform and Its Application to PatchBased 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
connectedgraph or as a cloud of highdimensional points. The proposed
transform constructs a tree that applies a 1D wavelet decomposition filters,
coupled with a prereordering 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. Stateoftheart 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 patchbased appearance models are generative statistical models that can be learned from an
image or a set of images. All these patchbased 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
patchbased method in image processing. In addition, we explain how geometric information such as tangent
plane and curvature in patchspace 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
stateoftheart denoising results. In this talk, we will discuss the role
of dictionary learning in patchbased 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 prelearned
from clean example images, or it can be learned online from the noisy
image, while the dictionary can be orthogonal or nonorthogonal. In the
case of PID without dictionary learning, an analytically predesigned
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 HelOr (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 nonlinear 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 nonlinear mappings and actually reduces to NCC when mappings are restricted to be linear. The MTM is shown to be invariant to nonlinear tone mappings, and is empirically shown to be highly discriminative and robust to noise. Gabriel Peyré (Universite ParisDauphine)  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 patchbased 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 offline and online
techniques, in particular, twostep approaches that first detect the correct model and then
optimally sense for it. Joint work with J. DuarteCarvajalino, G. Yu, and L. Carin. Alessandro Foi (Tampere University of Technology)  Patch Foveation in Nonlocal Imaging  (slides)
Patchbased 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 pointspread 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 selfsimilarity. 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 patchfoveation 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 selfsimilarity are shown for a number of imaging applications, with particular emphasis on image filtering, for which we demonstrate that foveated selfsimilarity is a more effective regularity assumption than the windowed selfsimilarity 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 nonlocal 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).
