Abstract. Texture analysis consists of a classical and everlasting task in image processing, often involved in a broad range of applications, possibly very different in nature. For large classes of textures, scale-free (or fractal) spatial dynamics as well as anisotropy constitute key properties. However, the local (pixelwise) joint estimation of anisotropy and scale-free attributes constitutes a difficult challenge, as both consist of nonlocal properties. Yet accurately detecting variations of these attributes across the image is often crucial. The overarching goal of the present work is thus to propose an inverse problem formulation for the analysis of piecewise homogeneous textures, grounded jointly on scale-free dynamics and anisotropy, and to study its performance for local assessment of textures. The formulation combines several major contributions. First, piecewise homogeneous Gaussian fields are defined as texture mixture models, with prescribed scale-free and anisotropy properties. Second, multiband complex wavelet coefficients, implemented via (nondecimated) dual-tree fast algorithms, are theoretically shown to be sensitive to both scale-free dynamics and anisotropy. Notably, it is shown that the squared-modulus of the wavelet coefficients behaves locally (or pixelwise) approximately as power-laws, with both scaling exponent and intercept jointly sensitive to anisotropy and scale-free dynamics. Thus, a key originality of the present work is to propose to perform local analysis of intrinsically nonlocal properties without having recourse to local averages, which would significantly impair accurate segmentation or accurate local characterization. Third, these local power-law-like behaviors, combined with regularization terms enforcing piecewise homogeneity, are embedded into a minimization procedure, solved by an optimization algorithm, whose convergence conditions are theoretically well-studied, and practically implemented through an efficient proximal algorithm due to strong convexity of the resulting minimization problem. Segmentation performance achieved by the proposed procedure is quantified and compared with respect to the difficulty of the segmentation task, for synthetic piecewise homogeneous Gaussian fields. The potential of the proposed texture analysis tool is also illustrated at work on real-world textures.

In this paper, we present a new edge detection model based on proximal unfolded neural networks. The architecture relies on unfolding proximal Blake–Zisserman iterations, leading to a composition of two blocks: a smoothing block and an edge detection block. We show through simulations that the proposed approach efficiently eliminates irrelevant details while retaining key edges and significantly improves performance with respect to state-of-the-art strategies. Additionally, our architecture is significantly lighter than recent learning models designed for edge detection in terms of number of learnable parameters and inference time.

Plug-and-play algorithms constitute a popular frame- work for solving inverse imaging problems that rely on the implicit definition of an image prior via a denoiser. These algorithms can leverage powerful pretrained denoisers to solve a wide range of imaging tasks, circumventing the necessity to train models on a per-task basis. Unfortunately, plug-and-play methods often show unstable behaviors, hampering their promise of versatility and leading to suboptimal quality of reconstructed images. In this work, we show that enforcing equivariance to certain groups of transformations (rotations, reflections, and/or translations) on the denoiser strongly improves the stability of the algorithm as well as its reconstruction quality. We provide a theoretical analysis that illustrates the role of equivariance on better performance and stability. We present a simple algorithm that enforces equivariance on any existing denoiser by simply applying a random transformation to the input of the denoiser and the inverse transformation to the output at each iteration of the algorithm. Experiments on multiple imaging modalities and denoising networks show that the equivariant plug-and-play algorithm improves both the reconstruction performance and the stability compared to their non-equivariant counterparts.

Abstract. This paper presents a multilevel framework for inertial and inexact proximal algorithms that encompasses multilevel versions of classical algorithms such as forward-backward and FISTA. The methods are supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We propose a particular instance of IML (Inexact MultiLevel) FISTA, based on the use of the Moreau envelope to build efficient and useful coarse corrections, fully adapted to solve problems in image restoration. Such a construction is derived for a broad class of composite optimization problems with proximable functions. We evaluate our approach on several image reconstruction problems, and we show that it considerably accelerates the convergence of the corresponding one-level (i.e., standard) version of the methods for large-scale images.

In this work, we focus on the challenging problem of designing an off-the-grid method for dictionaries involving both positional and scale shifts.To tackle this challenge, we introduce a novel algorithm inspired by the Sliding Frank-Wolfe approach.In our proposed algorithm, positions are treated as continuous variables, whereas scales are discretized.Such a strategy eliminates numerical instabilities inherent to the direct application of Sliding Frank-Wolfe.We successfully apply this algorithm to the study of DNA replication data.

International audience

The present work addresses the segmentation of textures characterized by anisotropy and scale-free statistics, two generic properties of use to model numerous real-world applications. This is achieved by proposing to combine a complex dual-tree multi-scale (wavelet) analysis within an inverse problem formulation aiming to estimate anisotropy and scale-free local parameters and to group them into piecewise homogeneous patches, jointly and in one single step. To minimize the corresponding functional, a primal-dual proximal convergent algorithm is devised and accelerated by taking advantage of the strong convexity of the data-fidelity term. Segmentation performance are assessed as function of the complexity of the task by means of Monte Carlo simulations conducted over synthetic textures, defined from anisotropic scale-free stochastic models.

This paper presents a multilevel fast iterative soft thresholding algorithm (FISTA), based on the use of the Moreau envelope to incorporate correction from coarse models, which is easy to compute when the explicit form of the proximal operator for the considered functions is known. This approach is supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We evaluate our approach on image restoration problems and we show that it outperforms classical FISTA for large-scale images.

This work focuses on the discrete Mumford-Shah (D-MS) functional which aims to perform jointly image reconstruction and contour detection but at the price of minimizing a non-convex objective function. This functional was of main interest during the 90’s but was then forsaken in order to focus on the unique restoration task relying on non-smooth convex minimization. Recent advances about D-MS were dedicated to alternative objective functions for which efficient numerical solution based on proximal iterations can be designed. In the 90’s literature about D-MS, equivalences between primal and dual formulations were derived. However, in the framework obtained by more recent developments dedicated to DMS such an equivalence was not yet derived and it is the goal of this work. By providing both a primal and dual formulation, a large panel of algorithms can be employed including recent proximal-based algorithms benefiting of good convergence behavior, especially due to KL properties and also most standard methods such as BFGS.

In this paper we provide a theoretical and numerical comparison of convergence rates of forward-backward, Douglas-Rachford, and Peaceman-Rachford algorithms for minimizing the sum of a convex proper lower semicontinuous function and a strongly convex differentiable function with Lipschitz continuous gradient. Our results extend the comparison made in [1], when both functions are smooth, to the context where only one is assumed differentiable. Optimal step-sizes and rates of the three algorithms are compared theoretically and numerically in the context of texture segmentation problem, obtaining very sharp estimations and illustrating the high efficiency of Peaceman-Rachford splitting.

This work designs an image restoration deep network relying on unfolded Chambolle-Pock primal-dual iterations. Each layer of our network is built from Chambolle-Pock iterations when specified for minimizing a sum of a$\ell _2$-norm data-term and an analysis sparse prior. The parameters of our network are the step-sizes of the Chambolle-Pock scheme and the linear operator involved in sparsity-based penalization, including implicitly the regularization parameter. A backpropagation procedure is fully described. Preliminary experiments illustrate the good behavior of such a deep primal-dual network in the context of image restoration on BSD68 database.

This work is dedicated to joint image restoration and contour detection considering the Ambrosio-Tortorelli functional. Two proximal alternating minimization schemes with convergence guarantees are provided, PALM-AT and SL-PAM-AT, as well as closed-form expressions of the involved proximity operators. A thorough numerical study is conducted in order to evaluate the performance of both numerical schemes as well as comparisons to state-of-the-art Mumford-Shah strategies.

The Mumford-Shah model is a standard model in image segmentation, and due to its difficulty, many approximations have been proposed. The major interest of this functional is to enable joint image restoration and contour detection. In this work, we propose a general formulation of the discrete counterpart of the Mumford-Shah functional, adapted to nonsmooth penalizations, fitting the assumptions required by the Proximal Alternating Linearized Minimization (PALM), with convergence guarantees. A second contribution aims to relax some assumptions on the involved functionals and derive a novel Semi-Linearized Proximal Alternated Minimization (SL-PAM) algorithm, with proved convergence. We compare the performances of the algorithm with several nonsmooth penalizations, for Gaussian and Poisson denoising, image restoration and RGB-color denoising. We compare the results with state-of-the-art convex relaxations of the Mumford-Shah functional, and a discrete version of the Ambrosio-Tortorelli functional. We show that the SL-PAM algorithm is faster than the original PALM algorithm, and leads to competitive denoising, restoration and segmentation results.

The discrete Mumford-Shah formalism has been introduced for the image denoising problem, allowing to capture both smooth behavior inside an object and sharp transitions on the boundary. In this letter, we propose first to extend this formalism to graphs and to the problem of mixing matrix estimation. New algorithmic schemes with convergence guarantees relying on proximal alternating minimization strategies are derived, and their efficiency (good estimation and robustness to initialization) is evaluated on simulated data, in the context of vote transfer matrix estimation.

In this paper, we propose an adaptation of the PAM algorithm to the minimization of a nonconvex functional designed for joint image denoising and contour detection. This new functional is based on the Ambrosio-Tortorelli approximation of the well-known Mumford-Shah functional. We motivate the proposed approximation, offering flexibility in the choice of the possibly non-smooth penalization, and we derive closed form expression for the proximal steps involved in the algorithm. We focus our attention on two types of penalization: ℓl-norm and a proposed quadratic-f. function. Numerical experiments show that the proposed method is able to detect sharp contours and to reconstruct piecewise smooth approximations with low computational cost and convergence guarantees. We also compare the results with state-of-the-art relaxations of the Mumford-Shah functional and a recent discrete formulation of the Ambrosio-Tortorelli functional.

Texture segmentation still constitutes an on-going challenge, especially when processing large-size images. Recently, procedures integrating a scale-free (or fractal) wavelet-leader model allowed the problem to be reformulated in a convex optimization framework by including a TV penalization. In this case, the TV penalty plays a prominent role with respect to the data fidelity term, which makes the approach costly in terms of memory and computation cost. The present contribution aims to investigate the potential of recent block-coordinate dual and primal-dual proximal algorithms for overcoming this numerical issue. Our study shows that a key ingredient in the success of the proposed block-coordinate approaches lies in the design of the blocks of variables which are updated at each iteration. Numerical experiments conducted over synthetic textures having piece-wise constant fractal properties confirm our theoretical analysis. The proposed lattice block design strategy is shown to yield significantly lower memory and computational requirements.

Texture segmentation constitutes a task of utmost importance in statistical image processing. Focusing on the broad class of monofractal textures characterized by piecewise constancy of the statistics of their multiscale representations, recently shown to be versatile enough for real-world texture modeling, the present work renews this recurrent topic by proposing an original approach enrolling jointly scale-free and local variance descriptors into a convex, but non smooth, minimization strategy. The performance of the proposed joint approach are compared against disjoint strategies working independently on scale-free features and on local variance on synthetic piecewise monofractal textures. Performance are also compared for multiphase flow image characterization, a topic of crucial importance in geophysics as well as in industrial processes. Applied to large-size images (above two million pixels), the proposed approach is shown to significantly improve state-of-the-art strategies by permitting the detection of the smallest gas bubbles and by offering a better understanding of multiphase flow structures.

This contribution focuses, within the ℓ1-Potts model, on the automated estimation of the regularization parameter balancing the ℓ1data fidelity term and the TVℓ0penalization. Variational approaches based on total variation gained considerable interest to solve piecewise constant denoising problems thanks to their deterministic setting and low computational cost. However, the quality of the achieved solution strongly depends on the tuning of the regularization parameter. While recent works have tailored various hierarchical Bayesian procedures to additionally estimate the regularization parameter for Gaussian noise, less attention has been granted to Laplacian noise, of interested in numerous applications. This contribution promotes a fast and parameter-free denoising procedure for piecewise constant signals corrupted by Laplacian noise, that includes automated selection of the regularization parameter. It relies on the minimization of a Bayesian-driven criterion whose similarities with the ℓ1-Potts model permit to derive a computationally efficient algorithm.

Proximal splitting algorithms for convex optimization are largely used in signal and image processing. They make possible to call the individual proximity operators of an arbitrary number of functions, whose sum is to be minimized. But the larger this number, the slower the convergence. In this letter, we show how to compute the proximity operator of a sum of two functions, for a certain type of functions operating on objects having a graph structure. The gain provided by avoiding unnecessary splitting is illustrated by an application to depth map estimation.

Fetal heart rate (FHR) monitoring is routinely used in clinical practice to help obstetricians assess fetal health status during delivery. However, early detection of fetal acidosis that allows relevant decisions for operative delivery remains a challenging task, receiving considerable attention. This contribution promotes sparse support vector machine classification that permits to select a small number of relevant features and to achieve efficient fetal acidosis detection. A comprehensive set of features is used for FHR description, including enhanced and computerized clinical features, frequency domain, and scaling and multifractal features, all computed on a large (1288 subjects) and well-documented database. The individual performance obtained for each feature independently is discussed first. Then, it is shown that the automatic selection of a sparse subset of features achieves satisfactory classification performance (sensitivity 0.73 and specificity 0.75, outperforming clinical practice). The subset of selected features (average depth of decelerations MADdtrd, baseline level β0, and variability H) receives simple interpretation in clinical practice. Intrapartum fetal acidosis detection is improved in several respects: A comprehensive set of features combining clinical, spectral, and scale-free dynamics is used; an original multivariate classification targeting both sparse feature selection and high performance is devised; state-of-the-art performance is obtained on a much larger database than that generally studied with description of common pitfalls in supervised classification performance assessments.

Internet traffic monitoring is a crucial task for network security. Self-similarity, a key property for a relevant description of internet traffic statistics, has already been massively and successfully involved in anomaly detection. Self-similar analysis was however so far applied either to byte or Packet count time series independently, while both signals are jointly collected and technically deeply related. The present contribution elaborates on a recently proposed multivariate self-similar model, Operator fractional Brownian Motion (OfBm), to analyze jointly self-similarity in bytes and packets. A non-linear regression procedure, based on an original Branch & Bound resolution procedure, is devised for the full identification of bivariate OfBm. The estimation performance is assessed by means of Monte Carlo simulations. Further, an Internet traffic anomaly detection procedure is proposed, that makes use of the vector of Hurst exponents underlying the OfBm based Internet data modeling. Applied to a large set of high quality and modern Internet data from the MAWI repository, proof-of-concept results in anomaly detection are detailed and discussed.

In transport networks, Origin-Destination matrices (ODM) are classically estimated from road traffic counts whereas recent technologies grant also access to sample car trajectories. One example is the deployment in cities of Bluetooth scanners that measure the trajectories of Bluetooth equipped cars. Exploiting such sample trajectory information, the classical ODM estimation problem is here extended into a link-dependent ODM (LODM) one. This much larger size estimation problem is formulated here in a variational form as an inverse problem. We develop a convex optimization resolution algorithm that incorporates network constraints. We study the result of the proposed algorithm on simulated network traffic.

This work aims to segment a texture into different regions, each characterized by a priori unknown multifractal properties. The multifractal properties are quantified using the multiscale function C1, jthat quantifies the evolution along analysis scales 2jof the empirical mean of the log of the wavelet leaders. The segmentation procedure is applied to local estimate of C1, j. It involves a multivariate Mumford-Shah relaxation formulated as a convex optimization problem involving a structure tensor penalization and an efficient algorithmic solution based on primal-dual proximal algorithm. The performances are evaluated on synthetic textures.

Sparsity inducing penalizations are useful tools in variational methods for machine learning. In this paper, we design a learning algorithm for multiclass support vector machines that allows us to enforce sparsity through various nonsmooth regularizations, such as the mixed ℓ1, p-norm with p ≥ 1. The proposed constrained convex optimization approach involves an epigraphical constraint for which we derive the closed-form expression of the associated projection. This sparse multiclass SVM problem can be efficiently implemented thanks to the flexibility offered by recent primal-dual proximal algorithms. Experiments carried out for handwritten digits demonstrate the interest of considering nonsmooth sparsity-inducing regularizations and the efficiency of the proposed epigraphical projection method.

This paper presents a 2D transposition of the Hilbert-Huang Transform (HHT), an empirical data analysis method designed for studying instantaneous amplitudes and phases of non-stationary data. The principle is to adaptively decompose an image into oscillating parts called Intrinsic Mode Functions (IMFs) using an Empirical Mode Decomposition method (EMD), and then to perform Hilbert spectral analysis on the IMFs in order to recover local amplitudes and phases. For the decomposition step, we propose a new 2D mode decomposition method based on non-smooth convex optimization, while for the instantaneous spectral analysis, we use a 2D transposition of Hilbert spectral analysis called monogenic analysis, based on Riesz transform and allowing to extract instantaneous amplitudes, phases, and orientations. The resulting 2D-HHT is validated on simulated data.

The identification of texture changes is a challenging problem that can be addressed by considering local regularity fluctuations in an image. This work develops a procedure for local regularity estimation that combines a convex optimization strategy with wavelet leaders, specific wavelet coefficients recently introduced in the context of multifractal analysis. The proposed procedure is formulated as an inverse problem that combines the joint estimation of both local regularity exponent and of the optimal weights underlying regularity measurement. Numerical experiments using synthetic texture indicate that the performance of the proposed approach compares favorably against other wavelet based local regularity estimation formulations. The method is also illustrated with an example involving real-world texture.

Nonlocal total variation (NLTV) has emerged as a useful tool in variational methods for image recovery problems. In this paper, we extend the NLTV-based regularization to multicomponent images by taking advantage of the structure tensor (ST) resulting from the gradient of a multicomponent image. The proposed approach allows us to penalize the nonlocal variations, jointly for the different components, through various l(1, p)-matrix-norms with p ≥ 1. To facilitate the choice of the hyperparameters, we adopt a constrained convex optimization approach in which we minimize the data fidelity term subject to a constraint involving the ST-NLTV regularization. The resulting convex optimization problem is solved with a novel epigraphical projection method. This formulation can be efficiently implemented because of the flexibility offered by recent primal-dual proximal algorithms. Experiments are carried out for color, multispectral, and hyperspectral images. The results demonstrate the interest of introducing a nonlocal ST regularization and show that the proposed approach leads to significant improvements in terms of convergence speed over current state-of-the-art methods, such as the alternating direction method of multipliers.

This paper provides an extension of the 1D Hilbert Huang transform for the analysis of images using recent optimization techniques. The proposed method consists of: 1) adaptively decomposing an image into oscillating parts called intrinsic mode functions (IMFs) using a mode decomposition procedure and 2) providing a local spectral analysis of the obtained IMFs in order to get the local amplitudes, frequencies, and orientations. For the decomposition step, we propose two robust 2D mode decompositions based on nonsmooth convex optimization: 1) a genuine 2D approach, which constrains the local extrema of the IMFs and 2) a pseudo-2D approach, which separately constrains the extrema of lines, columns, and diagonals. The spectral analysis step is an optimization strategy based on Prony annihilation property and applied on small square patches of the IMFs. The resulting 2D Prony–Huang transform is validated on simulated and real data.

TV-like constraints/regularizations are useful tools in variational methods for multicomponent image restoration. In this paper, we design more sophisticated non-local TV constraints which are derived from the structure tensor. The proposed approach allows us to measure the non-local variations, jointly for the different components, through various ℓ1,pmatrix norms with p ≥ 1. The related convex constrained optimization problems are solved through a novel epigraphical projection method. This formulation can be efficiently implemented thanks to the flexibility offered by recent primal-dual proximal algorithms. Experiments carried out for color images demonstrate the interest of considering a Non-Local Structure Tensor TV and show that the proposed epigraphical projection method leads to significant improvements in terms of convergence speed over existing numerical solutions.

Texture segmentation constitutes a classical yet crucial task in image processing. In many applications of very different natures (biomedical, geophysics,...) textures are naturally defined in terms of their local regularity fluctuations, which can be quantified as the variations of local Hölder exponents. Furthermore, such images are often naturally embedded in the class of piece-wise constant local regularity functions. The present contribution aims at proposing and assessing a segmentation procedure for this class of images. Its originality is twofold: First, local regularity is estimated using wavelet leaders, a novel multiresolution quantity recently introduced for multifractal analysis but barely used in local regularity measurement, comparisons against wavelet coefficient based estimation are conducted; Second, the challenging minimal partition problem underlying segmentation is convexified and conducted within a customized proximal framework. The estimation of the number of regions and their target regularity is obtained from a total-variation estimate that enables the actual use of proximal minimization for texture segmentation. Performance is assessed and illustrated on synthetic textures.

The concept of cosparsity has been recently introduced in the arena of compressed sensing. In cosparse modelling, the ℓ0(or ℓ1) cost of an analysis-based representation of the target signal isminimized under a data fidelity constraint. By taking benefit from recent advances in proximal algorithms, we show that it is possible to efficiently address a more general framework where a convex block sparsity measure is minimized under various convex constraints. The main contribution of this work is the introduction of a new epigraphical projection technique, which allows us to consider more flexible data fidelity constraints than the standard linear or quadratic ones. The validity of our approach is illustrated through an application to an image reconstruction problem in the presence of Poisson noise.

Regularization approaches have demonstrated their effectiveness for solving ill-posed problems. However, in the context of variational restoration methods, a challenging question remains, namely how to find a good regularizer. While total variation introduces staircase effects, wavelet-domain regularization brings other artefacts, e.g., ringing. However, a tradeoff can be made by introducing a hybrid regularization including several terms not necessarily acting in the same domain (e.g., spatial and wavelet transform domains). While this approach was shown to provide good results for solving deconvolution problems in the presence of additive Gaussian noise, an important issue is to efficiently deal with this hybrid regularization for more general noise models. To solve this problem, we adopt a convex optimization framework where the criterion to be minimized is split in the sum of more than two terms. For spatial domain regularization, isotropic or anisotropic total variation definitions using various gradient filters are considered. An accelerated version of the Parallel Proximal Algorithm is proposed to perform the minimization. Some difficulties in the computation of the proximity operators involved in this algorithm are also addressed in this paper. Numerical experiments performed in the context of Poisson data recovery, show the good behavior of the algorithm as well as promising results concerning the use of hybrid regularization techniques.

We propose a variational method for decomposing an image into a geometry and a texture component. Our model involves the sum of two functions promoting separately properties of each component, and of a coupling function modeling the interaction between the components. None of these functions is required to be differentiable, which significantly broadens the range of decompositions achievable through variational approaches. The convergence of the proposed proximal algorithm is guaranteed under suitable assumptions. Numerical examples are provided that show an application of the algorithm to image decomposition and restoration in the presence of Poisson noise.

Iterative optimization algorithms such as the forward-backward and Douglas-Rachford algorithms have gained much popularity since they provide efficient solutions to a wide class of non-smooth convex minimization problems arising in signal/image recovery. However, when images are degraded by a convolution operator and a Poisson noise, a particular attention must be paid to the associated minimization problem. To solve it, we propose a new optimization method which consists of two nested iterative steps. The effectiveness of the proposed method is demonstrated via numerical comparisons.

The objective of this paper is to develop methods for solving image recovery problems subject to constraints on the solution. More precisely, we will be interested in problems which can be formulated as the minimization over a closed convex constraint set of the sum of two convex functions f and g, where f may be nonsmooth and g is differentiable with a Lipschitz-continuous gradient. To reach this goal, we derive two types of algorithms that combine forward-backward and Douglas–Rachford iterations. The weak convergence of the proposed algorithms is proved. In the case when the Lipschitz-continuity property of the gradient of g is not satisfied, we also show that, under some assumptions, it remains possible to apply these methods to the considered optimization problem by making use of a quadratic extension technique. The effectiveness of the algorithms is demonstrated for two wavelet-based image restoration problems involving a signal-dependent Gaussian noise and a Poisson noise, respectively.