Regularized Interpolation for Noisy Images

Interpolation is the means by which a continuously defined model is fit to discrete data samples. When the data samples are exempt of noise, it seems desirable to build the model by fitting them exactly. In medical imaging, where quality is of paramount importance, this ideal situation unfortunately does not occur. In this paper, we propose a scheme that improves on the quality by specifying a tradeoff between fidelity to the data and robustness to the noise. We resort to variational principles, which allow us to impose smoothness constraints on the model for tackling noisy data. Based on shift-, rotation-, and scale-invariant requirements on the model, we show that the Lp-norm of an appropriate vector derivative is the most suitable choice of regularization for this purpose. In addition to Tikhonov-like quadratic regularization, this includes edge-preserving total-variation-like (TV) regularization. We give algorithms to recover the continuously defined model from noisy samples and also provide a data-driven scheme to determine the optimal amount of regularization. We validate our method with numerical examples where we demonstrate its superiority over an exact fit as well as the benefit of TV-like nonquadratic regularization over Tikhonov-like quadratic regularization.

Nonideal sampling and regularized interpolation of noisy data

Sathish Ramani

Conventional sampling (Shannon's sampling formulation and its approximation-theoretic counterparts) and interpolation theories provide effective solutions to the problem of reconstructing a signal from its samples, but they are primarily restricted to the noise-free scenario. The purpose of this thesis is to extend the standard techniques so as to be able to handle noisy data. First, we consider a realistic setting where a multidimensional signal is prefiltered prior to sampling, and the samples are corrupted by additive noise. In order to counterbalance the effect of noise, the reconstruction problem is formulated in a variational framework where the solution is obtained by minimizing a continuous-domain Tikhonov-like L2-regularization subject to a ℓp-based data fidelity constraint. We present theoretical justification for the minimization of this cost functional and show that the global-minimum solution belongs to a shift-invariant space generated by a function that is generally not bandlimited. The optimal reconstruction space is characterized by a condition that links the generating function to the regularization operator and implies the existence of a B-spline-like basis. We also consider stochastic formulations – min-max and minimum mean-squared error (MMSE/Wiener) formulations – of the nonideal sampling problem and show that they yield the same type of estimators and point towards the existence of optimal shift-invariant spaces for certain classes of stochastic processes. In the stochastic context, we also derive an exact formula for the error of approximating a stationary stochastic signal in the presence of discrete additive noise and justify the noise-reducing effect of regularization through illustrations. Next, we focus on the use of a much wider class of non-quadratic regularization functionals for the problem of interpolation in the presence of noise. Starting from the afine-invariance of the solution, we show that the Lp-norm (p ≠ 2) is the most suitable type of non-quadratic regularization for our purpose. We give monotonically convergent numerical algorithms to carry out the minimization of the non-quadratic cost criterion. We also demonstrate experimentally that the proposed regularized interpolation scheme provides superior interpolation performance compared to standard methods in the presence of noise. Finally, we address the problem of selecting an appropriate value for the regularization parameter which is most crucial for the working of variational methods in general including those discussed in this thesis. We propose a practical scheme that is based on the concept of risk estimation to achieve minimum MSE performance. In this context, we first review a well known result due to Stein (Stein's unbiased risk estimate — SURE) that is applicable for data corrupted by additive Gaussian noise and also derive a new risk estimate for a Poisson-Gaussian mixture model that is appropriate for certain biomedical imaging applications. Next, we introduce a novel and efficient Monte-Carlo technique to compute SURE for arbitrary nonlinear algorithms. We demonstrate experimentally that the proposed Monte-Carlo SURE yields regularization parameter values that are close to the oracle-optimum (minimum MSE) for all methods considered in this work. We also present results that illustrate the applicability of our technique to a wide variety of algorithms in denoising and deconvolution.

EPFL2009

Reconstruction of Large, Irregularly Sampled Multidimensional Images. A Tensor-Based Approach

Michaël Unser

Many practical applications require the reconstruction of images from irregularly sampled data. The spline formalism offers an attractive framework for solving this problem; the currently available methods, however, are hard to deploy for large-scale interpolation problems in dimensions greater than two (3-D, 3-D+time) because of an exponential increase of their computational cost (curse of dimensionality). Here, we revisit the standard regularized least-squares formulation of the interpolation problem, and propose to perform the reconstruction in a uniform tensor-product B-spline basis as an alternative to the classical solution involving radial basis functions. Our analysis reveals that the underlying multilinear system of equations admits a tensor decomposition with an extreme sparsity of its one dimensional components. We exploit this property for implementing a parallel, memory-efficient system solver. We show that the computational complexity of the proposed algorithm is essentially linear in the number of measurements and that its dependency on the number of dimensions is significantly less than that of the original sparse matrix-based implementation. The net benefit is a substantial reduction in memory requirement and operation count when compared to standard matrix-based algorithms, so that even 4-D problems with millions of samples become computationally feasible on desktop PCs in reasonable time. After validating the proposed algorithm in 3-D and 4-D, we apply it to a concrete imaging problem: the reconstruction of medical ultrasound images (3-D+time) from a large set of irregularly sampled measurements, acquired by a fast rotating ultrasound transducer.

IEEE2011

Reconstruction Methods for Cryo-Electron Microscopy: From Model-based to Data-driven

Laurène Donati

The topic of this thesis is the development of new reconstruction methods for cryo-electron microscopy (cryo-EM). Cryo-EM has revolutionized the field of structural biology over the last decade and now permits the regular discovery of biostructures. Yet, the technical challenges associated to cryo-EM are still numerous, and the measurements remain notoriously difficult to process. This calls for fast and robust algorithms that can reliably handle the challenging reconstruction task at hand. In this thesis, we investigated two reconstruction paradigms: model-based and data-driven. Model-based methods formulate the reconstruction task as an inverse problem and rely on a faithful model of the acquisition physics. By contrast, the central philosophy of data-driven approaches is to let the reconstruction algorithm be guided by the measured data through some learning procedure. Both paradigms share a tight link in all our works: their reliance on a rigorous mathematical formulation of the cryo-EM imaging model. The first cryo-EM method we considered is scanning transmission electron tomography (STET), a modality whose primary concern is to reduce the electron dosage required for accurate imaging. To handle this, we developed a tailored acquisition-reconstruction STET framework that relies on the principles of compressed sensing. This scheme permits high-quality reconstruction from a reduced number of measurements, hence greatly preserving the sample. We then designed several reconstruction algorithms for single-particle analysis (SPA), a popular cryo-EM method that enables the determination of structures at near-atomic resolution. A key challenge for the deployment of robust, iterative reconstruction methods in SPA is that they usually come with a prohibitive computational cost if not carefully engineered. To circumvent this problem, we developed a regularized reconstruction scheme whose cost-dominant operation is recast as a discrete convolution, which makes the use of our robust scheme feasible in SPA. Building on this development, we devised a joint optimization framework that efficiently alternates between the reconstruction and the estimation of the unknown orientations. We then explored a learning-based method to estimate the unknown orientations in SPA directly from the acquired dataset of projections. Capitalizing on our ability to model the cryo-EM procedure, we generated large synthetic SPA datasets to train a function---parametrized as a neural network---to predict the relative orientation between two projections based on their similarity. The framework relies on the postulate that it is possible to recover, from these estimated orientation distances, the orientations themselves through an appropriate minimization scheme, as supported by preliminary tests. Finally, we developed a completely new paradigm for SPA reconstruction that leverages the remarkable capability of deep neural networks to capture data distribution. The proposed algorithm uses a generative adversarial network to learn the 3D structure that has simulated projections that most closely match the real data in a distributional sense. By doing so, it can resolve a 3D structure in a single algorithmic run using only the dataset of projections and CTF estimations as inputs. Hence, it bypasses many processing steps that are necessary in the usual cryo-EM reconstruction pipeline, which opens new perspectives for reconstruction in SPA.