A main task in cryo-electron microscopy single particle reconstruction is to find a three-dimensional model of a molecule given a set of its randomly oriented and positioned projection-images. In this work, we propose an algorithm for ab initio reconstruction for molecules with tetrahedral or octahedral symmetry. The algorithm exploits the multiple common lines between each pair of projection-images as well as self common lines within each image, and integrates the information from all images at once. The applicability of the proposed algorithm is demonstrated using simulated and experimental cryo-electron microscopy data.

Kernel methods are powerful tools in various data analysis tasks. Yet, in many cases, their time and space complexity render them impractical for large datasets. Various kernel approximation methods were proposed to overcome this issue, with the most prominent method being the Nyström method. In this paper, we derive a perturbation-based kernel approximation framework building upon results from classical perturbation theory. We provide an error analysis for this framework, and prove that in fact, it generalizes the Nyström method and several of its variants. Furthermore, we show that our framework gives rise to new kernel approximation schemes, that can be tuned to take advantage of the structure of the approximated kernel matrix. We support our theoretical results numerically and demonstrate the advantages of our approximation framework on both synthetic and real-world data.

Cryo-electron microscopy is a state-of-the-art method for determining high-resolution three-dimensional models of molecules from their two-dimensional projection images. A key step in this method is estimating a low-resolution model of the investigated molecule using only its projection images without any other prior information. Robust algorithms for this step for molecules without symmetry or with cyclic symmetry have been proposed, typically based on common lines between pairs of images. Deriving a common lines algorithm for molecules with $D_{2}$ symmetry is more challenging, since such molecules are invariant to an arbitrary orientation-preserving permutation of their coordinate system. This invariance also renders previous common lines algorithms inapplicable to $D_{2}$ symmetric molecules. In this work, we present a common lines algorithm for determining the structure of molecules with $D_{2}$ symmetry. We derive the geometry that the $D_{2}$ symmetry group induces on the common lines between pairs of images, develop a procedure for estimating the relative orientation of pairs of images, characterize the ambiguities inherent in these orientations due to the $D_{2}$ symmetry, and describe a robust method for combining all relative orientations into a single consistent assignment of orientations to all images. In contrast to local-search based methods, our procedure is unbiased, reference free, and guaranteed to find a globally consistent solution for the orientation assignment problem. We demonstrate the applicability of our algorithm using experimental cryo-electron microscopy data.

In recent years, improvements in various image acquisition techniques gave rise to the need for adaptive processing methods, aimed particularly for large datasets corrupted by noise and deformations. In this work, we consider datasets of images sampled from a low-dimensional manifold (i.e., an image-valued manifold), where the images can assume arbitrary planar rotations. To derive an adaptive and rotation-invariant framework for processing such datasets, we introduce a graph Laplacian (GL)-like operator over the dataset, termed a steerable graph Laplacian. Essentially, the steerable GL extends the standard GL by accounting for all (infinitely many) planar rotations of all images. As it turns out, similarly to the standard GL, a properly normalized steerable GL converges to the Laplace--Beltrami operator on the low-dimensional manifold. However, the steerable GL admits an improved convergence rate compared to the GL, where the improved convergence behaves as if the intrinsic dimension of the underlying manifold is lower by one. Moreover, it is shown that the steerable GL admits eigenfunctions of the form of Fourier modes (along the orbits of the images' rotations) multiplied by eigenvectors of certain matrices, which can be computed efficiently by the FFT. For image datasets corrupted by noise, we employ a subset of these eigenfunctions to “filter” the dataset via a Fourier-like filtering scheme, essentially using all images and their rotations simultaneously. We demonstrate our filtering framework by denoising simulated single-particle cryo-electron-microscopy image datasets.

As modern scientific image datasets typically consist of a large number of images of high resolution, devising methods for their accurate and efficient processing is a central research task. In this paper, we consider the problem of obtaining the steerable principal components of a dataset, a procedure termed "steerable PCA" (steerable principal component analysis). The output of the procedure is the set of orthonormal basis functions which best approximate the images in the dataset and all of their planar rotations. To derive such basis functions, we first expand the images in an appropriate basis, for which the steerable PCA reduces to the eigen-decomposition of a block-diagonal matrix. If we assume that the images are well localized in space and frequency, then such an appropriate basis is the prolate spheroidal wave functions (PSWFs). We derive a fast method for computing the PSWFs expansion coefficients from the images' equally spaced samples, via a specialized quadrature integration scheme, and show that the number of required quadrature nodes is similar to the number of pixels in each image. We then establish that our PSWF-based steerable PCA is both faster and more accurate then existing methods, and more importantly, provides us with rigorous error bounds on the entire procedure.

We present a method for improving a non-local means (NLM) operator by computing its low-rank approximation. The low-rank operator is constructed by applying a filter to the spectrum of the original NLM operator. This results in an operator, which is less sensitive to noise while preserving important properties of the original operator. The method is efficiently implemented based on Chebyshev polynomials and is demonstrated on the application of natural images denoising. For this application, we provide a comparison of our method with other denoising methods.

MOTIVATION: Structural information of macromolecular complexes provides key insights into the way they carry out their biological functions. Achieving high-resolution structural details with electron microscopy requires the identification of a large number (up to hundreds of thousands) of single particles from electron micrographs, which is a laborious task if it has to be manually done and constitutes a hurdle towards high-throughput. Automatic particle selection in micrographs is far from being settled and new and more robust algorithms are required to reduce the number of false positives and false negatives. RESULTS: In this article, we introduce an automatic particle picker that learns from the user the kind of particles he is interested in. Particle candidates are quickly and robustly classified as particles or non-particles. A number of new discriminative shape-related features as well as some statistical description of the image grey intensities are used to train two support vector machine classifiers. Experimental results demonstrate that the proposed method: (i) has a considerably low computational complexity and (ii) provides results better or comparable with previously reported methods at a fraction of their computing time. AVAILABILITY: The algorithm is fully implemented in the open-source Xmipp package and downloadable from http://xmipp.cnb.csic.es.

Change detection of imaging spectroscopy data is widely used in many applications. Among them, environmental monitoring is of great importance. In this paper, we introduce a new automated method, termed spectral overlapping threshold (SOT), to derive a threshold to distinguish between “change” and “no change” areas. The method exploits the overlapping regions in multi-strip mosaic images, which are regarded as “no change” areas because they are acquired only a few minutes apart. The method consists of two steps. First, similarity measures are applied to the overlapping areas. Then, the histogram of the similarity values are computed and the thresholds for each land use land cover (LULC) category are determined. The method is independent of the underlying SM used to detect changes, and is demonstrated here for the spectral angle measure (SAM), spectral information divergence (SID), Euclidean distance (ED) and spectral correlation measure (SCM). This process is demonstrated for a mosaic of HyMap sensor data acquired in 2009 and 2010 over Sokolov mining area, Czech Republic.

A central task in recovering the structure of a macromolecule from cryo-electron microscopy (cryo-EM) images is to determine a three-dimensional model of the macromolecule given many of its two-dimensional projection images. The direction from each image taken the images which was is unknown, and are small and extremely noisy. The goal is to determine the direction from which each image was taken and then to combine the images into a three-dimensional model of the molecule. We present an algorithm for determining the viewing direction of all cryo-EM images at once, which is robust to high levels of noise. The algorithm is based on formulating the problem as a synchronization problem; that is, we estimate the relative spatial configuration of pairs of images and then estimate a global assignment of orientations that maximizes the number of satisfied pairwise relations. Information about the spatial relation between pairs of images is extracted from common lines between triplets of images. These noisy pairwise relations are combined into a single consistent assignment of orientations by constructing a matrix whose entries encode the pairwise relations. This matrix is shown to have rank 3, and its nontrivial eigenspace is shown to reveal the projection orientation of each image. In particular, we show that the nontrivial eigenvectors encode the rotation matrix that corresponds to each image.

The discrete Radon transform (DRT) was defined by Abervuch as an analog of the continuous Radon transform for discrete data. Both the DRT and its inverse are computable in O(n(2) log n) operations for images of size n × n. In this paper, we demonstrate the applicability of the inverse DRT for the reconstruction of a 2-D object from its continuous projections. The DRT and its inverse are shown to model accurately the continuum as the number of samples increases. Numerical results for the reconstruction from parallel projections are presented. We also show that the inverse DRT can be used for reconstruction from fan-beam projections with equispaced detectors.

With regard to the above paper (ibid., vol. 21, no. 2, pp. 733-741, Feb. 2012), a portion of the authors' corrections were not included before the work was finalized. These are detailed here.

The cryo-electron microscopy reconstruction problem is to find the three-dimensional (3D) structure of a macromolecule given noisy samples of its two-dimensional projection images at unknown random directions. Present algorithms for finding an initial 3D structure model are based on the "angular reconstitution" method in which a coordinate system is established from three projections, and the orientation of the particle giving rise to each image is deduced from common lines among the images. However, a reliable detection of common lines is difficult due to the low signal-to-noise ratio of the images. In this paper we describe two algorithms for finding the unknown imaging directions of all projections by minimizing global self-consistency errors. In the first algorithm, the minimizer is obtained by computing the three largest eigenvectors of a specially designed symmetric matrix derived from the common lines, while the second algorithm is based on semidefinite programming (SDP). Compared with existing algorithms, the advantages of our algorithms are five-fold: first, they accurately estimate all orientations at very low common-line detection rates; second, they are extremely fast, as they involve only the computation of a few top eigenvectors or a sparse SDP; third, they are nonsequential and use the information in all common lines at once; fourth, they are amenable to a rigorous mathematical analysis using spectral analysis and random matrix theory; and finally, the algorithms are optimal in the sense that they reach the information theoretic Shannon bound up to a constant for an idealized probabilistic model.

The cryo-electron microscopy (cryo-EM) reconstruction problem is to find the three-dimensional structure of a macromolecule given noisy versions of its two-dimensional projection images at unknown random directions. We introduce a new algorithm for identifying noisy cryo-EM images of nearby viewing angles. This identification is an important first step in three-dimensional structure determination of macromolecules from cryo-EM, because once identified, these images can be rotationally aligned and averaged to produce "class averages" of better quality. The main advantage of our algorithm is its extreme robustness to noise. The algorithm is also very efficient in terms of running time and memory requirements, because it is based on the computation of the top few eigenvectors of a specially designed sparse Hermitian matrix. These advantages are demonstrated in numerous numerical experiments.

Image reconstruction from its projections is a necessity in many applications such as medical (CT), security, inspection, and others. This paper extends the 2-D Fan-beam method in [2] to 3-D. The algorithm, called Pyramid Beam (PB), is based upon the parallel reconstruction algorithm in [1]. It allows fast capturing of the scanned data, and in 3-D, the reconstructions are based upon the discrete X-ray transform [1]. The PB geometries are reordered to fit parallel projection geometry. The underlying idea is to use the algorithm in [1] by porting the proposed PB geometries to fit the algorithm in [1]. The complexity of the algorithm is comparable with the 3-D FFT. The results show excellent reconstruction qualities while being simple for practical use.

Nonlocal neighborhood filters are modern and powerful techniques for image and signal denoising. In this paper, we give a probabilistic interpretation and analysis of the method viewed as a random walk on the patch space. We show that the method is intimately connected to the characteristics of diffusion processes, their escape times over potential barriers, and their spectral decomposition. In particular, the eigenstructure of the diffusion operator leads to novel insights on the performance and limitations of the denoising method, as well as a proposal for an improved filtering algorithm.

We introduce a graph Laplacian-based algorithm for the tomographic reconstruction of a planar object from its projections taken at random unknown directions. A Laplace-type operator is constructed on the data set of projections, and the eigenvectors of this operator reveal the projection orientations. The algorithm is shown to successfully reconstruct the Shepp-Logan phantom from its noisy projections. Such a reconstruction algorithm is desirable for the structuring of certain biological proteins using cryo-electron microscopy.

We present an algorithm that detects rotational and reflectional symmetries of two-dimensional objects. Both symmetry types are effectively detected and analyzed using the angular correlation (AC), which measures the correlation between images in the angular direction. The AC is accurately computed using the pseudopolar Fourier transform, which rapidly computes the Fourier transform of an image on a near-polar grid. We prove that the AC of symmetric images is a periodic signal whose frequency is related to the order of the symmetry. This frequency is recovered via spectrum estimation, which is a proven technique in signal processing with a variety of efficient solutions. We also provide a novel approach for finding the center of symmetry and demonstrate the applicability of our scheme to the analysis of real images.

We present an algorithm for the registration of rotated and translated volumes, which operates in the frequency domain. The Fourier domain allows to compute the rotation and translation parameters separately, thus reducing a problem with six degrees of freedom to two problems of three degrees of freedom each. We propose a three-step procedure. The first step estimates the rotation axis. The second computes the planar rotation relative to the rotation axis, and the third recovers the translational displacement by using the phase correlation technique. The rotation estimation is based on Euler's theorem, which allows to represent a rotation using only three parameters. Two parameters represent the rotation axis and one parameter represents the planar rotation perpendicular to the axis. By using the 3D pseudo-polar FFT, the estimation of the rotation axis is shown to be algebraically accurate. A variant of the angular difference function registration algorithm is derived for the estimation of the planar rotation around the axis. The experimental results show that the algorithm is accurate and robust to noise.

The estimation of large motions without prior knowledge is an important problem in image registration. In this paper we present the angular difference function (ADF) and demonstrate its applicability to rotation estimation. The ADF of two functions is defined as the integral of their spectral difference along the radial direction. It is efficiently computed using the pseudo-polar Fourier transform, which computes the discrete Fourier transform of an image on a near spherical grid. Unlike other Fourier based registration schemes, the suggested approach does not require any interpolation. Thus, it is more accurate and significantly faster.

We present an algorithm for aligning rotated and translated volumes, which operates in the frequency domain. The Fourier domain allows us to compute the rotation and translation parameters separately, thus reducing a problem with six degrees of freedom to two problems of three degrees of freedom each. We propose a three-step procedure. The first step estimates the rotation axis, the second computes the planar rotation relative to the rotation axis, and the third recovers the translational displacement by using the phase correlation technique. By using the 3-D pseudo-polar FFT, the estimation of the rotation axis is shown to be algebraically accurate. Experimental results show that the algorithm is accurate and robust to noise.

The estimation of large motions without prior knowledge is an important problem in image registration. In this paper, we present the angular difference function (ADF) and demonstrate its applicability to rotation estimation. The ADF of two functions is defined as the integral of their spectral difference along the radial direction. It is efficiently computed using the pseudopolar Fourier transform, which computes the discrete Fourier transform of an image on a near spherical grid. Unlike other Fourier-based registration schemes, the suggested approach does not require any interpolation. Thus, it is more accurate and significantly faster.