Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSmoothing for signals with discontinuities using higher order Mumford-Shah models
72
0
0.0
(
0
)
Added by
Martin Storath
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Minimizing the Mumford-Shah functional is frequently used for smoothing signals or time series with discontinuities. A significant limitation of the standard Mumford-Shah model is that linear trends -- and in general polynomial trends -- in the data are not well preserved. This can be improved by building on splines of higher order which leads to higher order Mumford-Shah models. In this work, we study these models in the univariate situation: we discuss important differences to the first order Mumford-Shah model, and we obtain uniqueness results for their solutions. As a main contribution, we derive fast minimization algorithms for Mumford-Shah models of arbitrary orders. We show that the worst case complexity of all proposed schemes is quadratic in the length of the signal. Remarkably, they thus achieve the worst case complexity of the fastest solver for the piecewise constant Mumford-Shah model (which is the simplest model of the class). Further, we obtain stability results for the proposed algorithms. We complement these results with a numerical study. Our reference implementation processes signals with more than 10,000 elements in less than one second.
rate research
Read More
We consider the problem of decomposing higher-order moment tensors, i.e., the sum of symmetric outer products of data vectors. Such a decomposition can be used to estimate the means in a Gaussian mixture model and for other applications in machine learning. The $d$th-order empirical moment tensor of a set of $p$ observations of $n$ variables is a symmetric $d$-way tensor. Our goal is to find a low-rank tensor approximation comprising $r ll p$ symmetric outer products. The challenge is that forming the empirical moment tensors costs $O(pn^d)$ operations and $O(n^d)$ storage, which may be prohibitively expensive; additionally, the algorithm to compute the low-rank approximation costs $O(n^d)$ per iteration. Our contribution is avoiding formation of the moment tensor, computing the low-rank tensor approximation of the moment tensor implicitly using $O(pnr)$ operations per iteration and no extra memory. This advance opens the door to more applications of higher-order moments since they can now be efficiently computed. We present numerical evidence of the computational savings and show an example of estimating the means for higher-order moments.
Mumford-Shah and Potts functionals are powerful variational models for regularization which are widely used in signal and image processing; typical applications are edge-preserving denoising and segmentation. Being both non-smooth and non-convex, they are computationally challenging even for scalar data. For manifold-valued data, the problem becomes even more involved since typical features of vector spaces are not available. In this paper, we propose algorithms for Mumford-Shah and for Potts regularization of manifold-valued signals and images. For the univariate problems, we derive solvers based on dynamic programming combined with (convex) optimization techniques for manifold-valued data. For the class of Cartan-Hadamard manifolds (which includes the data space in diffusion tensor imaging), we show that our algorithms compute global minimizers for any starting point. For the multivariate Mumford-Shah and Potts problems (for image regularization) we propose a splitting into suitable subproblems which we can solve exactly using the techniques developed for the corresponding univariate problems. Our method does not require any a priori restrictions on the edge set and we do not have to discretize the data space. We apply our method to diffusion tensor imaging (DTI) as well as Q-ball imaging. Using the DTI model, we obtain a segmentation of the corpus callosum.
The Ambrosio-Tortorelli functional is a phase-field approximation of the Mumford-Shah functional that has been widely used for image segmentation. The approximation has the advantages of being easy to implement, maintaining the segmentation ability, and $Gamma$-converging to the Mumford-Shah functional. However, it has been observed in actual computation that the segmentation ability of the Ambrosio-Tortorelli functional varies significantly with different values of the parameter and it even fails to $Gamma$-converge to the original functional for some cases. In this paper we present an asymptotic analysis on the gradient flow equation of the Ambrosio-Tortorelli functional and show that the functional can have different segmentation behavior for small but finite values of the regularization parameter and eventually loses its segmentation ability as the parameter goes to zero when the input image is treated as a continuous function. This is consistent with the existing observation as well as the numerical examples presented in this work. A selection strategy for the regularization parameter and a scaling procedure for the solution are devised based on the analysis. Numerical results show that they lead to good segmentation of the Ambrosio-Tortorelli functional for real images.
We propose and study numerically the implicit approximation in time of the Navier-Stokes equations by a Galerkin-collocation method in time combined with inf-sup stable finite element methods in space. The conceptual basis of the Galerkin-collocation approach is the establishment of a direct connection between the Galerkin method and the classical collocation methods, with the perspective of achieving the accuracy of the former with reduced computational costs in terms of less complex algebraic systems of the latter. Regularity of higher order in time of the discrete solution is ensured further. As an additional ingredient, we employ Nitsches method to impose all boundary conditions in weak form with the perspective that evolving domains become feasible in the future. We carefully compare the performance poroperties of the Galerkin-collocation approach with a standard continuous Galerkin-Petrov method using piecewise linear polynomials in time, that is algebraically equivalent to the popular Crank-Nicholson scheme. The condition number of the arising linear systems after Newton linearization as well as the reliable approximation of the drag and lift coefficient for laminar flow around a cylinder (DFG flow benchmark with $Re=100$) are investigated. The superiority of the Galerkin-collocation approach over the linear in time, continuous Galerkin-Petrov method is demonstrated therein.
Randomized smoothing is a recently proposed defense against adversarial attacks that has achieved SOTA provable robustness against $ell_2$ perturbations. A number of publications have extended the guarantees to other metrics, such as $ell_1$ or $ell_infty$, by using different smoothing measures. Although the current framework has been shown to yield near-optimal $ell_p$ radii, the total safety region certified by the current framework can be arbitrarily small compared to the optimal. In this work, we propose a framework to improve the certified safety region for these smoothed classifiers without changing the underlying smoothing scheme. The theoretical contributions are as follows: 1) We generalize the certification for randomized smoothing by reformulating certified radius calculation as a nested optimization problem over a class of functions. 2) We provide a method to calculate the certified safety region using $0^{th}$-order and $1^{st}$-order information for Gaussian-smoothed classifiers. We also provide a framework that generalizes the calculation for certification using higher-order information. 3) We design efficient, high-confidence estimators for the relevant statistics of the first-order information. Combining the theoretical contribution 2) and 3) allows us to certify safety region that are significantly larger than the ones provided by the current methods. On CIFAR10 and Imagenet datasets, the new regions certified by our approach achieve significant improvements on general $ell_1$ certified radii and on the $ell_2$ certified radii for color-space attacks ($ell_2$ restricted to 1 channel) while also achieving smaller improvements on the general $ell_2$ certified radii. Our framework can also provide a way to circumvent the current impossibility results on achieving higher magnitude of certified radii without requiring the use of data-dependent smoothing techniques.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
