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.

Keywords: Segmentation, restoration, inverse problems, nonsmooth optimization, nonconvex optimization, proximal algorithms, PALM, Mumford–Shah.

Wi-Fi networks often consist of several Access Points (APs) to form an Extended Service Set. These APs may interfere with each other as soon as they use the same channel or overlapping channels. A classical model to describe interference is the conflict graph. As the interference level varies in the network and in time, we consider a weighted conflict graph. In this paper, we propose a method to infer the weights of the conflict graph of a Wi-Fi network. Weights represent the proportion of activity from a neighbor detected by the Clear Channel Assessment mechanism. Our method relies on a theoretical model based on Markov networks applied to a decomposition of the original conflict graph. The input of our solution is the activity measured at each AP, measurements available in practice. The proposed method is validated through ns-3 simulations performed for different scenarios. Results show that our solution is able to accurately estimate the weights of the conflict graph.

Keywords: Wi-Fi, Weighted conflict graph, Inference

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 the present work, 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 estimationand robustness to initialization) are evaluated on simulated data, in the context of vote transfer matrix estimation.

Keywords: Mumford-Shah, graph, mixing matrice estimation, nonconvex optimisation.

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: l1-norm and a proposed quadratic-l1 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.

Keywords: Segmentation, restoration, Ambrosio–Tortorelli, non-smooth optimization, proximal algorithm

The Mumford-Shah (MS) functional is one of the most influential variational model in image segmentation, restoration, and cartooning. Difficult to solve, the Ambrosio-Tortorelli (AT) functional is of particular interest, because minimizers of AT can be shown to converge to a minimizer of MS. This paper takes an interest in a new method for numerically solving the AT model [2]. This method formulates the AT functional in a discrete calculus setting, and by this way is able to capture the set of discontinuities as a one-dimensional set. It is also shown that this model is competitive with total variation restoration methods. We present here the discrete AT models in details, and compare its merit with recent convex relaxations of AT and MS functionals. We also examine the potential of this model for inpainting, and describe its implementation in the DGtal library, an open-source project.

Keywords: image denoising and restoration, Mumford-Shah functional, variational model, optimization, inverse problems, discrete calculus, Ambrosio-Tortorelli functional, image inpaiting.

Essential image processing and analysis tasks, such as image segmentation, simplification and denoising, can be conducted in a unified way by minimizing the Mumford-Shah (MS) functional. Although seductive, this minimization is in practice difficult because it requires to jointly define a sharp set of contours and a smooth version of the initial image. For this reason, various relaxations of the original formulations have been proposed, together with optimisation methods. Among these, the Ambrosio-Tortorelli (AT) parametric functional is of particular interest, because minimizers of AT can be shown to converge to a minimizer of MS. However this convergence is difficult to achieve numerically using standard finite difference schemes. Indeed, with AT, discontinuities need to be represented explicitly rather than implicitly.
In this work, we propose to formulate AT using the full framework of Discrete Calculus (DC), which is able to sharply represent discontinuities thanks to a more sophisticated topological framework. We present our proposed formulation, its resolution, and results on synthetic and real images. We show that we are indeed able to represent sharp discontinuities and as a result significantly better stability to noise, compared with finite difference schemes.

Keywords: segmentation, denoising, simplification, Mumford-Shah functional, variational formulation, optimisation, inverse problems.

We propose a novel method to regularize a normal vector field defined on a digital surface (boundary of a set of voxels). When the digital surface is a digitization of a piecewise smooth manifold, our method localizes sharp features (edges) while regularizing the input normal vector field at the same time. It relies on the optimisation of a variant of the Ambrosio-Tortorelli functional, originally defined for denoising and contour extraction in image processing [Ambrosio and Tortorelli, 1990]. We reformulate this functional to digital surface processing thanks to discrete calculus operators. Experiments show that the output normal field is very robust to digitization artifacts or noise, and also fairly independent of the sampling resolution. The method allows the user to choose independently the amount of smoothing and the length of the set of discontinuities. Sharp and vanishing features are correctly delineated even on extremely damaged data. Finally, our method can be used to enhance considerably the output of state-of-the-art normal field estimators like Voronoi Covariance Measure [Merigot et al., 2011] or Randomized Hough Transform [Boulch and Marlet, 2012].