We consider the problem of sampling distributions stemming from non-convex potentials with Unadjusted Langevin Algorithm (ULA). We prove the stability of the discrete-time ULA to drift approximations under the assumption that the potential is strongly convex at infinity. In many context, e.g. imaging inverse problems, potentials are non-convex and non-smooth. Proximal Stochastic Gradient Langevin Algorithm (PSGLA) is a popular algorithm to handle such potentials. It combines the forward-backward optimization algorithm with a ULA step. Our main stability result combined with properties of the Moreau envelope allows us to derive the first proof of convergence of the PSGLA for non-convex potentials. We empirically validate our methodology on synthetic data and in the context of imaging inverse problems. In particular, we observe that PSGLA exhibits faster convergence rates than Stochastic Gradient Langevin Algorithm for posterior sampling while preserving its restoration properties.

Plug-and-Play (PnP) algorithms are a class of iterative algorithms that address image inverse problems by combining a physical model and a deep neural network for regularization. Even if they produce impressive image restoration results, these algorithms rely on a non-standard use of a denoiser on images that are less and less noisy along the iterations, which contrasts with recent algorithms based on Diffusion Models (DM), where the denoiser is applied only on re-noised images. We propose a new PnP framework, called Stochastic deNOising REgularization (SNORE), which applies the denoiser only on images with noise of the adequate level. It is based on an explicit stochastic regularization, which leads to a stochastic gradient descent algorithm to solve ill-posed inverse problems. A convergence analysis of this algorithm and its annealing extension is provided. Experimentally, we prove that SNORE is competitive with respect to state-of-the-art methods on deblurring and inpainting tasks, both quantitatively and qualitatively.

Plug-and-Play (PnP) methods are efficient iterative algorithms for solving ill-posed image inverse problems. PnP methods are obtained by using deep Gaussian denoisers instead of the proximal operator or the gradient-descent step within proximal algorithms. Current PnP schemes rely on data-fidelity terms that have either Lipschitz gradients or closed-form proximal operators, which is not applicable to Poisson inverse problems. Based on the observation that the Gaussian noise is not the adequate noise model in this setting, we propose to generalize PnP using the Bregman Proximal Gradient (BPG) method. BPG replaces the Euclidean distance with a Bregman divergence that can better capture the smoothness properties of the problem. We introduce the Bregman Score Denoiser specifically parametrized and trained for the new Bregman geometry and prove that it corresponds to the proximal operator of a nonconvex potential. We propose two PnP algorithms based on the Bregman Score Denoiser for solving Poisson inverse problems. Extending the convergence results of BPG in the nonconvex settings, we show that the proposed methods converge, targeting stationary points of an explicit global functional. Experimental evaluations conducted on various Poisson inverse problems validate the convergence results and showcase effective restoration performance.

Plug-and-Play (PnP) methods solve ill-posed inverse problems through iterative proximal algorithms by replacing a proximal operator by a denoising operation. When applied with deep neural network denoisers, these methods have shown state-of-the-art visual performance for image restoration problems. However, their theoretical convergence analysis is still incomplete. Most of the existing convergence results consider nonexpansive denoisers, which is non-realistic, or limit their analysis to strongly convex data-fidelity terms in the inverse problem to solve. Recently, it was proposed to train the denoiser as a gradient descent step on a functional parameterized by a deep neural network. Using such a denoiser guarantees the convergence of the PnP version of the Half-Quadratic-Splitting (PnP-HQS) iterative algorithm. In this paper, we show that this gradient denoiser can actually correspond to the proximal operator of another scalar function. Given this new result, we exploit the convergence theory of proximal algorithms in the nonconvex setting to obtain convergence results for PnP-PGD (Proximal Gradient Descent) and PnP-ADMM (Alternating Direction Method of Multipliers). When built on top of a smooth gradient denoiser, we show that PnP-PGD and PnP-ADMM are convergent and target stationary points of an explicit functional. These convergence results are confirmed with numerical experiments on deblurring, super-resolution and inpainting.

We propose a new algorithm for sparse spike estimation from Fourier measurements. Based on theoretical results on non-convex optimization techniques for off-the-grid sparse spike estimation, we present a projected gradient descent algorithm coupled with a back-projection initialization procedure. Our algorithm permits to estimate the positions of large numbers of Diracs in 2d from random Fourier measurements. We present, along with the algorithm, theoretical qualitative insights explaining the success of our algorithm. This opens a new direction for practical off-the-grid spike estimation with theoretical guarantees in imaging applications.

In this work we introduce a statistical framework in order to analyze the spatial redundancy in natural images. This notion of spatial redundancy must be defined locally. To do so, we define an auto-similarity function which, given one image, computes a dissimilarity measurement between patches. To derive a criterion for taking a decision on the similarity between two patches, we present an a contrario model. Namely, two patches are said to be similar if the associated dissimilarity measurement is unlikely to happen in a background model. Choosing Gaussian random fields as background models, we derive nonasymptotic expressions for the probability distribution function of similarity measurements. We present an algorithm in order to assess redundancy in natural images and discuss applications in denoising, periodicity analysis, and texture ranking.

Extraction of local features constitutes a first step of many algorithms used in computer vision. The choice of keypoints and local features is often driven by the optimization of a performance criterion on a given computer vision task, which sometimes makes the extracted content difficult to apprehend. In this paper we propose to examine the content of local image descriptors from a reconstruction perspective. For that, relying on the keypoints and descriptors provided by the scale-invariant feature transform (SIFT), we propose two stochastic models for exploring the set of images that can be obtained from given SIFT descriptors. The two models are both defined as solutions of generalized Poisson problems that combine gradient information at different scales. The first model consists in sampling an orientation field according to a maximum entropy distribution constrained by local histograms of gradient orientations (at scale 0). The second model consists in simple resampling of the local histogram of gradient orientations at multiple scales. We show that both of these models admit convolutive expressions which allow us to compute the model statistics (e.g., the mean, the variance). Also, in the experimental section, we show that these models are able to recover many image structures, while not requiring any external database. Finally, we compare several other choices of points of interest in terms of quality of reconstruction, which confirms the optimality of the SIFT keypoints over simpler alternatives.

Exemplar-based texture synthesis consists in producing new synthetic images which have the same perceptual characteristics as a given texture sample while exhibiting sufficient innovation (to avoid verbatim copy). In this paper, we propose to address this problem with a model obtained as local transformations of Gaussian random fields. The local transformations operate on $3 \times 3$ patches and are designed to solve a semi-discrete optimal transport problem in order to reimpose the patch distribution of the exemplar texture. The semi-discrete optimal transport problem is solved with a stochastic gradient algorithm, whose convergence speed is evaluated on several practical transport cases. After studying the properties of such transformed Gaussian random fields, we propose a multiscale extension of the model which aims at preserving the patch distribution of the exemplar texture at multiple scales. Experiments demonstrate that this multiscale model is able to synthesize structured textures while keeping several mathematical guarantees, and with low requirements in synthesis time and memory storage. In particular, a single patch optimal transport map is shown to be better than iterated nearest neighbor assignments in terms of statistical guarantees. Besides, once the model is estimated, the resulting synthesis algorithm is fast and highly parallel since it amounts to performing weighted nearest neighbor patch assignments at each scale.

Abstract Designing realistic noise patterns from scratch is hard. To solve this problem, recent contributions have proposed involved spectral analysis algorithms that enable procedural noise models to faithfully reproduce some class of textures. The aim of this paper is to propose the simplest and most efficient noise model that allows for the reproduction of any Gaussian texture. Texton noise is a simple sparse convolution noise that sums randomly scattered copies of a small bilinear texture called texton . We introduce an automatic algorithm to compute the texton associated with an input texture image that concentrates the input frequency content into the desired texton support. One of the main features of texton noise is that its evaluation only consists to sum 30 texture fetches on average. Consequently, texton noise generates Gaussian textures with an unprecedented evaluation speed for noise by example. A second main feature of texton noise is that it allows for high‐quality on‐the‐fly anisotropic filtering by simply invoking existing GPU hardware solutions for texture fetches. In addition, we demonstrate that texton noise can be applied on any surface using parameterization‐free surface noise and that it allows for noise mixing.

Inpainting consists in computing a plausible completion of missing parts of an image given the available content. In the restricted framework of texture images, the image can be seen as a realization of a random field model, which gives a stochastic formulation of image inpainting: on the masked exemplar one estimates a random texture model which can then be conditionally sampled in order to fill the hole. In this paper is proposed an instance of such stochastic inpainting methods, dealing in particular with the case of Gaussian textures. First, a simple procedure is proposed for estimating a Gaussian texture model based on a masked exemplar, which, although quite naive, gives sufficient results for our inpainting purpose. Next, the conditional sampling step is solved with the traditional algorithm for Gaussian conditional simulation. The main difficulty of this step is to solve a very large linear system, which, in the case of stationary Gaussian textures, can be done efficiently with a conjugate gradient descent (using a Fourier representation of the covariance operator). Several experiments show that the corresponding inpainting algorithm is able to inpaint large holes (of any shape) in a texture, with a reasonable computational time. Moreover, several comparisons illustrate that the proposed approach performs better on texture images than state-of-the-art inpainting methods.

Image inpainting consists in filling missing regions of an image by inferring from the surrounding content. In the case of texture images, inpainting can be formulated in terms of conditional simulation of a stochastic texture model. Many texture synthesis methods thus have been adapted to texture inpainting, but these methods do not offer theoretical guarantees since the conditional sampling is in general only approximate. Here we show that in the case of Gaussian textures, inpainting can be addressed with perfect conditional simulation relying on kriging estimation. We thus obtain a microtexture inpainting algorithm that is able to fill holes of any shape and size in an efficient manner while respecting exactly a stochastic model.