Mini-symposium SIAM IS10 - "Recent Advances in Sparse and Non-local Image Regularization"

Jean-Francois Aujol (ENS Cachan) - Exemplar-based inpainting from a variational point of view - (slides)
Among all methods for reconstructing missing regions in a digital image, the so-called exemplar-based algorithms are very efficient and often produce striking results. They are based on the simple idea -- initially used for texture synthesis -- that the unknown part of an image can be reconstructed by simply copying samples extracted from the known part. Many variants have been proposed whose performances vary according to the type of image. Beyond heuristic considerations, very little has been done in the literature to explain the performances of this class of algorithms from a theoretical point of view. With a particular focus on the ability to reconstruct the geometry, we discuss in this paper a variational interpretation in \R^N of these methods. We propose an optimization model and several variants, and prove the existence of minimizers in the framework of functions of bounded variation. Focusing on a simple 2D situation, we provide experimental evidences that these global variational models are more efficient than a basic patch-based algorithm for reconstructing certain long-range geometric features without any loss of quality for the texture reconstruction. We eventually propose additional variants that fulfill a couple of axiomatic requirements and have a better asymptotic behaviour as the patch size goes to zero.
This is a joint work with Simon Masnou and Said Ladjal.
Alfred M. Bruckstein (Technion) - On Globally Optimal Local Modeling: From Moving Least Square to Overparametrization - (slides)
This paper discusses a spectrum of methods for signal, curve, image and surface denoising, adaptive smoothing and reconstruction from noisy samples that involve locally modeling the data while performing local, semi-local and/or global optimization. We show that the same methodolgy yields many of the previously proposed algorithms, from the popular moving least squares methods to the globally optimal overparametrization methods recently published for smoothing and optic-flow estimation. However, the unified look at the spectrum of problems and methods also suggests a wealth of novel global functionals and local modeling possibilities.
Antoni Buades (ENS de Cachan) - MRI Superresolution Using High Resolution Anatomical Priors - (slides)
In Magnetic Resonance Imaging low-resolution images are routinely interpolated to decrease voxel size and improve apparent resolution. However, classical interpolation techniques are not able to recover the high frequency information lost during the acquisition process. In the present paper a new superresolution method is proposed to recover such information using coplanar high resolution images. The proposed methodology takes benefit from the fact that in typical clinical settings both high and low-resolution images of different types are taken from the same subject. These available high resolution images can be used to improve effectively the resolution of other coplanar lower resolution images. Experiments on synthetic and real data are supplied to show the effectiveness of the proposed approach. A comparison with classical interpolation techniques is presented to demonstrate the improved performance of the proposed methodology over previous State-of-the-art methods.
Michael Elad (Technion) - Image Super-Resolution using Sparse-Representation - (slides)
Scaling up a single image while preserving is sharpness and visual-quality is a difficult and highly ill-posed inverse problem. A series of algorithms have been proposed over the years for its solution, with varying degrees of success. In CVPR 2008, Yang, Wright, Huang and Ma proposed a solution to this problem based on sparse representation modeling and dictionary learning. In this talk I present a variant of their method with several important differences. In particular, the proposed algorithm does not need a separate training phase, as the dictionaries are learned directly from the image to be scaled-up. Furthermore, the high-resolution dictionary is learned differently, by forcing its alignment with the low-resolution one. We show the benefit these modifications bring in terms of simplicity of the overall algorithm, and its output quality.
Jalal Fadili (ENSICaen) - Block Stein sparse denoising and deconvolution - (slides)
In this work, we propose fast image denoising and deconvolution algorithms that use adaptive block thresholding in sparse representation domain. Our main theoretical result investigates the minimax rates of Stein block thresholding in any dimension d over the so-called decomposition spaces. These smoothness spaces cover the classical case of Besov spaces for which wavelets are known to provide a sparse representation, as well as smoothness spaces corresponding to the second generation curvelet-type construction. We shows that block estimator can achieve the optimal minimax rate, or is at least nearly minimax (up to a log factor) in the least favorable situation. The choice of the threshold parameter is theoretically discussed and its optimal value is stated for the white Gaussian noise. We provide simple, fast and easy to implement algorithms. We also report a comprehensive simulation study to support our theoretical findings. The practical performance of our block Stein denoising and deconvolution algorithms compares very favorably to state-of-the art algorithms on a large set of test images.
Alessandro Foi (Tampere University of Technology) - Non-local filtering of images using data-driven transforms - (slides)
We consider the so-called grouping and collaborative filtering approach: similar patches in an image or video are collected and jointly transformed using a higher-dimensional transform, sparsity is then enforced by shrinkage of the higher-dimensional spectrum. This approach has proved to be very successful, especially as the core element of denoising, deblurring, and other inverse filtering algorithms. We discuss various aspects related to the adaptivity of the transforms used in collaborative filtering, with particular emphasis on the geometrical adaptation and on the learning of basis elements from noisy data.
Onur Guleryuz (DoCoMo) - Another Role for Sparsity in Pattern Matching: A Simple, First-principle Derivation Based on Computational Complexity - (slides)
We consider pattern matching problems where a pattern library, a set consisting of a large number of vectors, is to be queried for the presence of user-provided patterns in a Neyman-Pearson setting. Without any constraints on computational complexity, it is clear that one can answer such queries with arbitrarily high accuracy. Establishing computational complexity as the fundamental resource that needs to be traded with matching accuracy, our approach formulates the search problem as the maximization of accuracy for a given constraint in computational complexity. In effect, our work represents the pattern library in terms of its computational-complexity-dependent approximations, where coarser approximations are computationally easier to search but lead to less accurate results. Our solutions naturally lead to sparse approximations, establishing a duality between sparse decompositions and pattern matching problems: (a) Patterns that are easy to find must be sparse in some domain, (b) with low computational complexity, one can only hope to reliably find sparse approximations of patterns.
Guoshen Yu (Ecole Polytechnique) - Image Modeling and Enhancement via Structured Sparse Model Selection - (slides)
An image representation framework based on structured sparse model selection is introduced in this work. The corresponding modeling dictionary is comprised of a family of learned orthogonal bases. For an image patch, a model is first selected from this dictionary through linear approximation in a best basis, and the signal estimation is then calculated with the selected model. The model selection leads to a guaranteed near optimal denoising estimator. The degree of freedom in the model selection is equal to the number of the bases, typically about 10 for natural images, and is significantly lower than with traditional overcomplete dictionary approaches, stabilizing the representation. For an image patch of size \sqrt(N)xsqrt(N), the computational complexity of the proposed framework is O(N^2), typically 2 to 3 orders of magnitude faster than estimation in an overcomplete dictionary. The orthogonal bases are adapted to the image of interest and are computed with a simple and fast procedure. State-of-the-art results are shown in image denoising, deblurring, and inpainting. Joint work with Guillermo Sapiro and Stephane Mallat. Website
Charles Kervrann (IRISA) - Neighborhod filters and novel bayesian approximations for non-local image regularization - (slides)
In this talk, I will present formal connections between non-parametric estimation approaches, neighborhood filters and block estimators in the Bayesian framework. I will provide a statistical interpretation to current patch-based methods and justify the Bayesian inference that needs to explicitly accounts for discrepancies between the model and the data. I will present a recent method recommended in situations where the posterior or the likelihood are intractable or too prohibitive to calculate. In particular, the proposed approximations are suited for the analysis of large-dimensional distribution of patches and enable to denoise images corrupted by non-Gaussian noises. We demonstrate our algorithms on both artificial and real examples.
Peyman Milanfar (University of California, Santa Cruz) - Local and Non-local Similarity for Visual Recognition From a Single Example - (slides)
We present a novel framework for detection/recognition of visual (2-D and 3-D) objects without training. The proposed framework operates using one example (query) of an object of interest to find similar matches; does not require prior knowledge (learning) about objects being sought; and does not require any pre-processing step or segmentation of a target image/video. Our method is based on the computation of local regression kernels as descriptors from a query, which measure the likeness of a pixel, voxel, or patch, to its surroundings.
State of the art performance is demonstrated on challenging datasets in several visual processing tasks including generic detection and recognition of visual objects in 2-D and actions in 3-D, in diverse contexts and under varying imaging conditions. In addition, using the patch-based framework, we are able to robustly and accurately capture visually salient objects and their boundaries, closely mimicking human fixation data in both static and dynamic scenes.
Gabriel Peyré (Universite Paris-Dauphine) - Modeling Locally Parellel Textures - (slides)
In this talk I will present a new adaptive framework for locally parallel texture modeling. Oscillating patterns are modeled with functionals that constrain the local Fourier decomposition of the texture. We introduce a first convex texture functional which is a weighted Hilbert norm. The weights on the local Fourier atoms are optimized to match the local orientation and frequency of the texture. This adaptive convex model is then used to solve inverse problems in image processing, such as image decomposition and inpainting. The local texture orientation and frequency of the texture component are adaptively estimated during the minimization process. Furthermore, in the inpainting case, convex models present the issue of attenuation inside large missing parts. The amplitude of the reconstructed oscillating patterns tends indeed to vanish inside large holes. To deal with this difficult problem, a non convex generalization of our model is designed. This new model enables to impose the amplitude of the oscillating patterns inside the reconstructed parts and to cope with the inpainting of general oscillations profiles. Numerical results show that our method improves state of the art algorithms for directional textures.
This is a joint work with Pierre Maurel and Jean-Francois Aujol.
Guillermo Sapiro (University of Minnesota) - Universal sparse modeling - (slides)
The goal of this talk is to make formal connections between sparse modeling and information theory, and in particular, universal coding and MDL. We will show how this leads to novel sparsity-inducing priors which have a number of advantages over more classical l_0 and l_1 ones.
Joint work with I. Ramirez and F. Lecumberry.
Jean-Luc Starck (CEA Saclay) - 3D sparse representations and inverse problems - (slides)
In this paper, we show that using a few three dimensional sparse transforms with atoms of different morphologies, including the wavelets and two types of curvelets, we can design simple algorithms based on iterative thresholdings that solve many restoration and inverse problems such as denoising, morphological component separation, inpainting, de-interlacing or inverse Fourier/Radon transform with relatively few projections.
Pierre Vandergheynst (EPFL) - Image Denoising with Nonlocal Spectral Graph Wavelets - (slides)
We present a new method for denoising photographic images based on a novel nonlocal spectral graph wavelet transform. We employ the transform formed using the graph Laplacian corresponding to a nonlocal image graph measuring similarities between image regions, yielding wavelets at multiple scales with the interesting property that they diffuse among regions of similar image content. Denoising by soft thresholding with threshold determined from a simple Laplacian model for the clean coefficients yields good results.

Session 1.

Session 2.

Session 3.

Abstract