We consider the problem of estimating log-determinants of large, sparse, positive definite matrices. A key focus of our algorithm is to reduce computational cost, and it is based on sparse approximate inverses. The algorithm can be implemented to be adaptive, and it uses graph spline approximation to improve accuracy. We illustrate our approach on classes of large sparse matrices.

The detection of landmarks or patterns is of interest for extracting features in biological images. Hence, algorithms for finding these keypoints have been extensively investigated in the literature, and their localization and detection properties are well known. In this paper, we study the complementary topic of local orientation estimation, which has not received similar attention. Simply stated, the problem that we address is the following: estimate the angle of rotation of a pattern with steerable filters centered at the same location, where the image is corrupted by colored isotropic Gaussian noise. For this problem, we propose an estimator formulated as linear combinations of circular harmonics with given radial profiles. We prove that the proposed estimator is unbiased. This property allows us to use a statistical framework based on the Cramér--Rao lower bound (CRLB) to study the limits on the accuracy of the corresponding class of estimators. We aim at evaluating the performance of detection methods based on steerable filters in terms of angular accuracy (as a lower bound), while considering the connection to maximum likelihood estimation. Beyond the general results, we analyze the asymptotic behavior of the lower bound in terms of the order of steerablility and propose an optimal subset of components that minimizes the bound. We define a mechanism for selecting optimal subspaces of the span of the detectors. These are characterized by the most relevant angular frequencies. Finally, we project our template to the span of circular harmonics with given radial profiles and experimentally show that the prediction accuracy achieves the predicted CRLB. As an extension, we also consider steerable wavelet detectors.

We present texture operators encoding class-specific local organizations of image directions (LOIDs) in a rotation-invariant fashion. The LOIDs are key for visual understanding, and are at the origin of the success of the popular approaches, such as local binary patterns (LBPs) and the scale-invariant feature transform (SIFT). Whereas, LBPs and SIFT yield hand-crafted image representations, we propose to learn data-specific representations of the LOIDs in a rotation-invariant fashion. The image operators are based on steerable circular harmonic wavelets (CHWs), offering a rich and yet compact initial representation for characterizing natural textures. The joint location and orientation required to encode the LOIDs is preserved by using moving frames (MFs) texture representations built from locally-steered image gradients that are invariant to rigid motions. In a second step, we use support vector machines to learn a multi-class shaping matrix for the initial CHW representation, yielding data-driven MFs called steerable wavelet machines (SWMs). The SWM forward function is composed of linear operations (i.e., convolution and weighted combinations) interleaved with non-linear steermax operations. We experimentally demonstrate the effectiveness of the proposed operators for classifying natural textures. Our scheme outperforms recent approaches on several test suites of the Outex and the CUReT databases.

MOTIVATION: SpotCaliper is a novel wavelet-based image-analysis software providing a fast automatic detection scheme for circular patterns (spots), combined with the precise estimation of their size. It is implemented as an ImageJ plugin with a friendly user interface. The user is allowed to edit the results by modifying the measurements (in a semi-automated way), extract data for further analysis. The fine tuning of the detections includes the possibility of adjusting or removing the original detections, as well as adding further spots. RESULTS: The main advantage of the software is its ability to capture the size of spots in a fast and accurate way. AVAILABILITY AND IMPLEMENTATION: http://bigwww.epfl.ch/algorithms/spotcaliper/ CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In analogy with steerable wavelets, we present a general construction of adaptable tight wavelet frames, with an emphasis on scaling operations. In particular, the derived wavelets can be “dilated” by a procedure comparable to the operation of steering steerable wavelets. The fundamental aspects of the construction are the same: an admissible collection of Fourier multipliers is used to extend a tight wavelet frame, and the “scale” of the wavelets is adapted by scaling the multipliers. As an application, the proposed wavelets can be used to improve the frequency localization. Importantly, the localized frequency bands specified by this construction can be scaled efficiently using matrix multiplication.

To address the classic interior tomography problem where projections at each view extend only to the shadow of a circular region completely interior to the subject being scanned, previously we showed that the exact recovery of two- and three-dimensional piecewise smooth images is guaranteed using a one-dimensional generalized total variation seminorm penalty which allows a much faster reconstruction. To further accelerate the algorithm up to a level for clinical use, this paper proposes a novel multiscale reconstruction method by exploiting the Bedrosian identity of the Hilbert transform. More specifically, we show that the high frequency parts of the one-dimensional signals can be quickly recovered analytically with the Hilbert transform because of the Bedrosian identity. This implies that computationally expensive iterative reconstruction need only be applied to low resolution images in the downsampled domain, which significantly reduces the computational burden. Moreover, even for incomplete trajectories such as circular cone-beam geometry, we demonstrate that the proposed multiscale interior tomography approach can be combined with a novel spectral blending method in order to mitigate cone-beam artifacts from missing frequency regions. We show the efficacy of the proposed multiscale algorithm using circular fan-beam, helical cone-beam data, and circular cone-beam geometry. With a graphics processing unit implementation, we demonstrate that the speed of the algorithm can be significantly accelerated up to the level for clinical use for various acquisition geometries.

Motivated by the interior tomography problem, we propose a method for exact reconstruction of a region of interest of a function from its local Radon transform in any number of dimensions. Our aim is to verify the feasibility of a one-dimensional reconstruction procedure that can provide the foundation for an efficient algorithm. For a broad class of functions, including piecewise polynomials and generalized splines, we prove that an exact reconstruction is possible by minimizing a generalized total variation seminorm along lines. The main difference with previous works is that our approach is inherently one-dimensional and that it imposes less constraints on the class of admissible signals. Within this formulation, we derive unique reconstruction results using properties of the Hilbert transform, and we present numerical examples of the reconstruction.

We propose an efficient construction of wavelet frames in any number of dimensions that are divergence-free. Our approach is based on applying the Leray projector, which is scale-invariant, to a standard wavelet frame. We prove that the projected wavelets retain the basic characteristics (decay rate and order of vanishing moments) of the initial wavelets. Since the Leray projector is also shift-invariant, it is defined as a Fourier multiplier, and our construction is implemented efficiently using the fast Fourier transform. In order to illustrate the practicality of the method, we present vector field denoising experiments.

In this letter, we aim to identify the optimal isotropic mother wavelet for a given spatial dimension based on a localization criterion. Within the framework of the calculus of variations, we specify an Euler-Lagrange equation for this problem, and we find the unique analytic solutions. In the one- and two-dimensional cases, the derived wavelets are well known.

Kaiser-Bessel window functions are frequently used to discretize tomographic problems because they have two desirable properties: 1) their short support leads to a low computational cost and 2) their rotational symmetry makes their imaging transform independent of the direction. In this paper, we aim at optimizing the parameters of these basis functions. We present a formalism based on the theory of approximation and point out the importance of the partition-of-unity condition. While we prove that, for compact-support functions, this condition is incompatible with isotropy, we show that minimizing the deviation from the partition of unity condition is highly beneficial. The numerical results confirm that the proposed tuning of the Kaiser-Bessel window functions yields the best performance.

We introduce an adaptive continuous-domain modeling approach to texture and natural images. The continuous-domain image is assumed to be a smooth function, and we embed it in a parameterized Sobolev space. We point out a link between Sobolev spaces and stochastic auto-regressive models, and exploit it for optimally choosing Sobolev parameters from available pixel values. To this aim, we use exact continuous-to-discrete mapping of the auto-regressive model that is based on symmetric exponential splines. The mapping is computationally efficient, and we exploit it for maximizing an approximated Gaussian likelihood function.We account for non-Gaussian Lévy-type processes by deriving a more robust estimator that is based on the sample auto-correlation sequence. Both estimators use multiple initialization values for overcoming the local minima structure of the fitting criteria. Experimental image resizing results indicate that the auto-correlation criterion can cope better with non-Gaussian processes and model mismatch. Our work demonstrates the importance of the auto-correlation function in adaptive image interpolation and image modeling tasks, and we believe it is instrumental in other image processing tasks as well.

The Riesz transform is a natural multidimensional extension of the Hilbert transform, and it has been the object of study for many years due to its nice mathematical properties. More recently, the Riesz transform and its variants have been used to construct complex wavelets and steerable wavelet frames in higher dimensions. The flip side of this approach, however, is that the Riesz transform of a wavelet often has slow decay. One can nevertheless overcome this problem by requiring the original wavelet to have sufficient smoothness, decay, and vanishing moments. In this paper, we derive necessary conditions in terms of these three properties that guarantee the decay of the Riesz transform and its variants, and, as an application, we show how the decay of the popular Simoncelli wavelets can be improved by appropriately modifying their Fourier transforms. By applying the Riesz transform to these new wavelets, we obtain steerable frames with rapid decay.

We introduce a novel family of invariant, convex, and non-quadratic functionals that we employ to derive regularized solutions of ill-posed linear inverse imaging problems. The proposed regularizers involve the Schatten norms of the Hessian matrix, which are computed at every pixel of the image. They can be viewed as second-order extensions of the popular total-variation (TV) semi-norm since they satisfy the same invariance properties. Meanwhile, by taking advantage of second-order derivatives, they avoid the staircase effect, a common artifact of TV-based reconstructions, and perform well for a wide range of applications. To solve the corresponding optimization problems, we propose an algorithm that is based on a primal-dual formulation. A fundamental ingredient of this algorithm is the projection of matrices onto Schatten norm balls of arbitrary radius. This operation is performed efficiently based on a direct link we provide between vector projections onto lq norm balls and matrix projections onto Schatten norm balls. Finally, we demonstrate the effectiveness of the proposed methods through experimental results on several inverse imaging problems with real and simulated data.

Bayesian estimation problems involving Gaussian distributions often result in linear estimation techniques. Nevertheless, there are no general statements as to whether the linearity of the Bayesian estimator is restricted to the Gaussian case. The two common strategies for non-Gaussian models are either finding the best linear estimator or numerically evaluating the Bayesian estimator by Monte Carlo methods. In this paper, we focus on Bayesian interpolation of non-Gaussian first-order autoregressive (AR) processes where the driving innovation can admit any symmetric infinitely divisible distribution characterized by the Lévy-Khintchine representation theorem. We redefine the Bayesian estimation problem in the Fourier domain with the help of characteristic forms. By providing analytic expressions, we show that the optimal interpolator is linear for all symmetric -stable distributions. The Bayesian interpolator can be expressed in a convolutive form where the kernel is described in terms of exponential splines. We also show that the limiting case of Lévy-type AR(1) processes, the system of which has a pole at the origin, always corresponds to a linear Bayesian interpolator made of a piecewise linear spline, irrespective of the innovation distribution. Finally, we show the two mentioned cases to be the only ones within the family for which the Bayesian interpolator is linear.

We consider the problem of sampling continuous-time auto-regressive processes on a uniform grid. We investigate whether a given sampled process originates from a single continuous-time model, and address this uniqueness problem by introducing an alternative description of poles in the complex plane. We then utilize Kronecker's approximation theorem and prove that the set of non-unique continuous-time AR(2) models has Lebesgue measure zero in this plane. This is a key aspect in current estimation algorithms that use sampled data, as it allows one to remove the sampling rate constraint that is imposed currently.