Search

Smoothing splines are twice differentiable by construction, so they cannot capture potential discontinuities in the underlying signal. In this work, we consider a special case of the weak rod model of Blake and Zisserman that allows for discontinuities penalizing their number by a linear term. The corresponding estimates are cubic smoothing splines with discontinuities (CSSD) which serve as representations of piecewise smooth signals and facilitate exploratory data analysis. However, computing the estimates requires solving a non-convex optimization problem. So far, efficient and exact solvers exist only for a discrete approximation based on equidistantly sampled data. In this work, we propose an efficient solver for the continuous minimization problem with non-equidistantly sampled data. Its worst case complexity is quadratic in the number of data points, and if the number of detected discontinuities scales linearly with the signal length, we observe linear growth in runtime. This efficient algorithm allows to use cross-validation for automatic selection of the hyperparameters within a reasonable time frame on standard hardware. We provide a reference implementation and . We demonstrate the applicability of the approach for the aforementioned tasks using both simulated and real data. for this article are available online. [ABSTRACT FROM AUTHOR]

We consider geometric Hermite subdivision for planar curves, i.e., iteratively refining an input polygon with additional tangent or normal vector information sitting in the vertices. The building block for the (nonlinear) subdivision schemes we propose is based on clothoidal averaging, i.e., averaging w.r.t. locally interpolating clothoids, which are curves of linear curvature. To this end, we derive a new strategy to approximate Hermite interpolating clothoids. We employ the proposed approach to define the geometric Hermite analogues of the well-known Lane-Riesenfeld and four-point schemes. We present numerical results produced by the proposed schemes and discuss their features. [ABSTRACT FROM AUTHOR]

In this paper, we consider the variational regularization of manifold-valued data in the inverse problems setting. In particular, we consider total variation and total generalized variation regularization for manifold-valued data with indirect measurement operators. We provide results on the well-posedness and present algorithms for a numerical realization of these models in the manifold setup. Further, we provide experimental results for synthetic and real data to show the potential of the proposed schemes for applications. [ABSTRACT FROM AUTHOR]

In this paper, we consider the sparse regularization of manifold-valued data with respect to an interpolatory wavelet/multiscale transform. We propose and study variational models for this task and provide results on their well-posedness. We present algorithms for a numerical realization of these models in the manifold setup. Further, we provide experimental results to show the potential of the proposed schemes for applications. [ABSTRACT FROM AUTHOR]

Median filtering is among the most utilized tools for smoothing real-valued data, as it is robust, edge-preserving, value-preserving, and yet can be computed efficiently. For data living on the unit circle, such as phase data or orientation data, a filter with similar properties is desirable. For these data, there is no unique means to define a median; so we discuss various possibilities. The arc distance median turns out to be the only variant which leads to robust, edge-preserving and value-preserving smoothing. However, there are no efficient algorithms for filtering based on the arc distance median. Here, we propose fast algorithms for filtering of signals and images with values on the unit circle based on the arc distance median. For non-quantized data, we develop an algorithm that scales linearly with the filter size. The runtime of our reference implementation is only moderately higher than the Matlab implementation of the classical median filter for real-valued data. For quantized data, we obtain an algorithm of constant complexity w.r.t. the filter size. We demonstrate the performance of our algorithms for real life data sets: phase images from interferometric synthetic aperture radar, planar flow fields from optical flow, and time series of wind directions. [ABSTRACT FROM AUTHOR]

We study jump-penalized estimators based on least absolute deviations which are often referred to as Potts estimators. They are estimators for a parsimonious piecewise constant representation of noisy data having a noise distribution which has heavier tails or which leads to many severe outliers. We consider real-valued data as well as circle-valued data which appear, for instance, as time series of angles or phase signals. We propose efficient algorithms that compute Potts estimators for real-valued scalar as well as for circlevalued data. The real-valued version improves upon the state-of-the-art solver w.r.t. to computational time. In particular for quantized data, the worst case complexity is improved. The circle-valued version is the first efficient algorithm of this kind. As an illustration, we apply our method to estimate the steps in the rotation of the bacterial flagella motor based on real biological data, and to the estimation of wind directions. [ABSTRACT FROM AUTHOR]

In this paper, we consider combined TV denoising and diffusion tensor fitting in DTI using the affine-invariant Riemannian metric on the space of diffusion tensors. Instead of first fitting the diffusion tensors, and then denoising them, we define a suitable TV type energy functional which incorporates the measured DWIs (using an inverse problem setup) and which measures the nearness of neighboring tensors in the manifold. To approach this functional, we propose generalized forward- backward splitting algorithms which combine an explicit and several implicit steps performed on a decomposition of the functional. We validate the performance of the derived algorithms on synthetic and real DTI data. In particular, we work on real 3D data. To our knowledge, the present paper describes the first approach to TV regularization in a combined manifold and inverse problem setup. [ABSTRACT FROM AUTHOR]

We consider L¹-TV regularization of univariate signals with values on the real line or on the unit circle. While the real data space leads to a convex optimization problem, the problem is nonconvex for circle-valued data. In this paper, we derive exact algorithms for both data spaces. A key ingredient is the reduction of the infinite search spaces to a finite set of configurations, which can be scanned by the Viterbi algorithm. To reduce the computational complexity of the involved tabulations, we extend the technique of distance transforms to nonuniform grids and to the circular data space. In total, the proposed algorithms have complexity O(KN), where N is the length of the signal and K is the number of different values in the data set. In particular, the complexity is O(N) for quantized data. It is the first exact algorithm for total variation regularization with circle-valued data, and it is competitive with the state-of-the-art methods for scalar data, assuming that the latter are quantized. [ABSTRACT FROM AUTHOR]

Signals with discontinuities appear in many problems in the applied sciences ranging from mechanics, electrical engineering to biology and medicine. The concrete data acquired are typically discrete, indirect and noisy measurements of some quantities describing the signal under consideration. The task is to restore the signal and, in particular, the discontinuities. In this respect, classical methods perform rather poor, whereas non-convex non-smooth variational methods seem to be the correct choice. Examples are methods based on Mumford-Shah and piecewise constant Mumford-Shah functionals and discretized versions which are known as Blake- Zisserman and Potts functionals. Owing to their non-convexity, minimization of such functionals is challenging. In this paper, we propose a new iterative minimization strategy for Blake-Zisserman as well as Potts functionals and a related jump-sparsity problem dealing with indirect, noisy measurements. We provide a convergence analysis and underpin our findings with numerical experiments. [ABSTRACT FROM AUTHOR]

We investigate the nonsmooth and nonconvex L¹-Potts functional in discrete and continuous time. We show G-convergence of discrete L¹-Potts functionals toward their continuous counterpart and obtain a convergence statement for the corresponding minimizers as the discretization gets finer. For the discrete L¹-Potts problem, we introduce an O(n²) time and O(n) space algorithm to compute an exact minimizer. We apply L¹-Potts minimization to the problem of recovering piecewise constant signals from noisy measurements f. It turns out that the L¹-Potts functional has a quite interesting blind deconvolution property. In fact, we show that mildly blurred jump-sparse signals are reconstructed by minimizing the L¹-Potts functional. Furthermore, for strongly blurred signals and a known blurring operator, we derive an iterative reconstruction algorithm. [ABSTRACT FROM AUTHOR]

We recover jump-sparse and sparse signals from blurred incomplete data corrupted by (possibly non-Gaussian) noise using inverse Potts energy functionals. We obtain analytical results (existence of minimizers, complexity) on inverse Potts functionals and provide relations to sparsity problems. We then propose a new optimization method for these functionals which is based on dynamic programming and the alternating direction method of multipliers (ADMM). A series of experiments shows that the proposed method yields very satisfactory jump-sparse and sparse reconstructions, respectively. We highlight the capability of the method by comparing it with classical and recent approaches such as TV minimization (jump-sparse signals), orthogonal matching pursuit, iterative hard thresholding, and iteratively reweighted \ell ^1 minimization (sparse signals). [ABSTRACT FROM AUTHOR]

Abstract: We establish results on convergence and smoothness of subdivision rules operating on manifold-valued data which are based on a general dilation matrix. In particular we cover irregular combinatorics. For the regular grid case results are not restricted to isotropic dilation matrices. The nature of the results is that intrinsic subdivision rules which operate on geometric data inherit smoothness properties of their linear counterparts. [Copyright &y& Elsevier]

We investigate interpolatory multiscale transformations for functions between manifolds which are based on interpolatory subdivision rules. We characterize the Hölder-Zygmund smoothness of a function between manifolds in terms of the coefficient decay w.r.t. this multiscale transform. [ABSTRACT FROM AUTHOR]

The present article deals with convergence and smoothness analysis of geometric, nonlinear subdivision schemes in the presence of extraordinary points. We discuss when the existence of a proximity condition between a linear scheme and its nonlinear analogue implies convergence of the nonlinear scheme (for dense enough input data). Furthermore, we obtain C1 smoothness of the nonlinear limit function in the vicinity of an extraordinary point over Reif’s characteristic parametrization. The results apply to the geometric analogues of well-known subdivision schemes such as Doo–Sabin or Catmull–Clark schemes. [ABSTRACT FROM AUTHOR]

Magnetic Particle Imaging is an emerging imaging modality through which it is possible to detect tracers containing superparamagnetic nanoparticles. The exposure of the particles to dynamic magnetic fields generates a non-linear response that is used to locate the particles and produce an image of their distribution. The bounding box that can be covered by a single scan curve depends on the strength of the gradients of the magnetic fields applied, which is limited due to the risk of causing peripheral nerve stimulation (PNS) in the patients. To address this issue, multiple scans are performed. The scan data must be merged together to produce reconstructions of larger regions of interest. In this paper we propose a mathematical framework which can deal with rather general multi-patching scenarios including rigid transformations of the field of view (FoV), the specimen and of the scanner. We show the flexibility of this framework in a variety of different scanning scenarios. Moreover, we describe an iterative reconstruction algorithm that yields a reconstruction of the target distribution by minimizing a convex functional which includes positivity constraints and sparsity enforcing priors. We show its convergence to a minimizer and perform numerical experiments on simulated data. [ABSTRACT FROM AUTHOR]

Magnetic Particle Imaging is an imaging modality that exploits the non-linear magnetization response of superparamagnetic nanoparticles to a dynamic magnetic field. In the multivariate case, measurement-based reconstruction approaches are common and involve a system matrix whose acquisition is time consuming and needs to be repeated whenever the scanning setup changes. Our approach relies on reconstruction formulae derived from a mathematical model of the MPI signal encoding. A particular feature of the reconstruction formulae and the corresponding algorithms is that these are independent of the particular scanning trajectories. In this paper, we present basic ways of leveraging this independence property to enhance the quality of the reconstruction by merging data from different scans. In particular, we show how to combine scans of the same specimen under different rotation angles. We demonstrate the potential of the proposed techniques with numerical experiments. [ABSTRACT FROM AUTHOR]

Signals and images with discontinuities appear in many problems in such diverse areas as biology, medicine, mechanics and electrical engineering. The concrete data are often discrete, indirect and noisy measurements of some quantities describing the signal under consideration. A frequent task is to find the segments of the signal or image which corresponds to finding the discontinuities or jumps in the data. Methods based on minimizing the piecewise constant Mumford–Shah functional—whose discretized version is known as Potts energy—are advantageous in this scenario, in particular, in connection with segmentation. However, due to their non-convexity, minimization of such energies is challenging. In this paper, we propose a new iterative minimization strategy for the multivariate Potts energy dealing with indirect, noisy measurements. We provide a convergence analysis and underpin our findings with numerical experiments. [ABSTRACT FROM AUTHOR]

We propose an algorithm to efficiently compute approximate solutions of the piecewise affine Mumford-Shah model. The algorithm is based on a novel reformulation of the underlying optimization problem in terms of Taylor jets. A splitting approach leads to linewise segmented jet estimation problems for which we propose an exact and efficient solver. The proposed method has the combined advantages of prior algorithms: it directly yields a partition, it does not need an initialization procedure, and it is highly parallelizable. The experiments show that the algorithm has lower computation times and that the solutions often have lower functional values than the state-of-the-art. [ABSTRACT FROM AUTHOR]

fter a discussion on definability of invariant subdivision rules we discuss rules for sequential data living in Riemannian manifolds and in symmetric spaces, having in mind the space of positive definite matrices as a major example. We show that subdivision rules defined with intrinsic means in Cartan-Hadamard manifolds converge for all input data, which is a much stronger result than those usually available for manifold subdivision rules. We also show weaker convergence results which are true in general but apply only to dense enough input data. Finally we discuss C and C smoothness of limit curves. [ABSTRACT FROM AUTHOR]

We consider reconstructing multi-channel images from measurements performed by photon-counting and energy-discriminating detectors in the setting of multi-spectral x-ray computed tomography (CT). Our aim is to exploit the strong structural correlation that is known to exist between the channels of multi-spectral CT images. To that end, we adopt the multi-channel Potts prior to jointly reconstruct all channels. This nonconvex prior produces piecewise constant solutions with strongly correlated channels. In particular, edges are strictly enforced to have the same spatial position across channels which is a benefit over TV-based methods whose channel-couplings are typically less strict. We consider the Potts prior in two frameworks: (a) in the context of a variational Potts model, and (b) in a Potts-superiorization approach that perturbs the iterates of a basic iterative least squares solver. We identify an alternating direction method of multipliers approach as well as a Potts-superiorized conjugate gradient method as particularly suitable. In numerical experiments, we compare the Potts prior based approaches to existing TV-type approaches on realistically simulated multi-spectral CT data and obtain improved reconstruction for compound solid bodies. [ABSTRACT FROM AUTHOR]

Three-dimensional freehand imaging techniques are gaining wider adoption due to their flexibility and cost efficiency. Typical examples for such a combination of a tracking system with an imaging device are freehand SPECT or freehand 3D ultrasound. However, the quality of the resulting image data is heavily dependent on the skill of the human operator and on the level of noise of the tracking data. The latter aspect can introduce blur or strong artifacts, which can significantly hamper the interpretation of image data. Unfortunately, the most commonly used tracking systems to date, i.e., optical and electromagnetic, present a trade-off between invading the surgeon’s workspace (due to line-of-sight requirements) and higher levels of noise and sensitivity due to the interference of surrounding metallic objects. In this paper, we propose a novel approach for total variation regularization of data from tracking systems (which we term pose signals) based on a variational formulation in the manifold of Euclidean transformations. The performance of the proposed approach was evaluated using synthetic data as well as real ultrasound sweeps executed on both a Lego phantom and human anatomy, showing significant improvement in terms of tracking data quality and compounded ultrasound images. Source code can be found at https://github.com/IFL-CAMP/pose_regularization. [ABSTRACT FROM AUTHOR]

Magnetic particle imaging (MPI) is an emerging medical imaging modality which is based on the non-linear response of magnetic nanoparticles to an applied magnetic field. It is an important feature of MPI that even fast dynamic processes can be captured for 3D volumes. The high temporal resolution in turn leads to large amounts of data which have to be handled efficiently. But as the system matrix of MPI is non-sparse, the image reconstruction gets computationally demanding. Therefore, currently only basic image reconstruction methods such as Tikhonov regularization are used. However, Tikhonov regularization is known to oversmooth edges in the reconstructed image and to have only a limited noise reducing effect. In this work, we develop an efficient edge preserving and noise reducing reconstruction method for MPI. As regularization model, we propose to use the nonnegative fused lasso model, and we devise a discretization that is adapted to the acquisition geometry of the preclinical MPI scanner considered in this work. We develop a customized solver based on a generalized forward-backward scheme which is particularly suitable for the dense and not well-structured system matrices in MPI. Already a non-optimized prototype implementation processes a 3D volume within a few seconds so that processing several frames per second seems amenable. We demonstrate the improvement in reconstruction quality over the state-of-the-art method in an experimental medical setup for an in-vitro angioplasty of a stenosis. [ABSTRACT FROM PUBLISHER]

We introduce a new nonsmooth variational model for the restoration of manifold-valued data which includes second order differences in the regularization term. While such models were successfully applied for real-valued images, we introduce the second order difference and the corresponding variational models for manifold data, which up to now only existed for cyclic data. The approach requires a combination of techniques from numerical analysis, convex optimization, and differential geometry. First, we establish a suitable definition of absolute second order differences for signals and images with values in a manifold. Employing this definition, we introduce a variational denoising model based on first and second order differences in the manifold setup. In order to minimize the corresponding functional, we develop an algorithm using an inexact cyclic proximal point algorithm. We propose an efficient strategy for the computation of the corresponding proximal mappings in symmetric spaces utilizing the machinery of Jacobi fields. For the n-sphere and the manifold of symmetric positive definite matrices, we demonstrate the performance of our algorithm in practice. We prove the convergence of the proposed exact and inexact variant of the cyclic proximal point algorithm in Hadamard spaces. These results which are of interest on its own include, e.g., the manifold of symmetric positive definite matrices. [ABSTRACT FROM AUTHOR]