Fast data-driven learning of parallel MRI sampling patterns for large scale problems.

In this study, a fast data-driven optimization approach, named bias-accelerated subset selection (BASS), is proposed for learning efficacious sampling patterns (SPs) with the purpose of reducing scan time in large-dimensional parallel MRI. BASS is applicable when Cartesian fully-sampled k-space measurements of specific anatomy are available for training and the reconstruction method for undersampled measurements is specified; such information is used to define the efficacy of any SP for recovering the values at the non-sampled k-space points. BASS produces a sequence of SPs with the aim of finding one of a specified size with (near) optimal efficacy. BASS was tested with five reconstruction methods for parallel MRI based on low-rankness and sparsity that allow a free choice of the SP. Three datasets were used for testing, two of high-resolution brain images ([Formula: see text]-weighted images and, respectively, [Formula: see text]-weighted images) and another of knee images for quantitative mapping of the cartilage. The proposed approach has low computational cost and fast convergence; in the tested cases it obtained SPs up to 50 times faster than the currently best greedy approach. Reconstruction quality increased by up to 45% over that provided by variable density and Poisson disk SPs, for the same scan time. Optionally, the scan time can be nearly halved without loss of reconstruction quality. Quantitative MRI and prospective accelerated MRI results show improvements. Compared with greedy approaches, BASS rapidly learns effective SPs for various reconstruction methods, using larger SPs and larger datasets; enabling better selection of sampling-reconstruction pairs for specific MRI problems.

Monotone FISTA with Variable Acceleration for Compressed Sensing Magnetic Resonance Imaging.

An improvement of the monotone fast iterative shrinkage-thresholding algorithm (MFISTA) for faster convergence is proposed. Our motivation is to reduce the reconstruction time of compressed sensing problems in magnetic resonance imaging. The proposed modification introduces an extra term, which is a multiple of the proximal-gradient step, into the so-called momentum formula used for the computation of the next iterate in MFISTA. In addition, the modified algorithm selects the next iterate as a possibly-improved point obtained by any other procedure, such as an arbitrary shift, a line search, or other methods. As an example, an arbitrary-length shift in the direction from the previous iterate to the output of the proximal-gradient step is considered. The resulting algorithm accelerates MFISTA in a manner that varies with the iterative steps. Convergence analysis shows that the proposed modification provides improved theoretical convergence bounds, and that it has more flexibility in its parameters than the original MFISTA. Since such problems need to be studied in the context of functions of several complex variables, a careful extension of FISTA-like methods to complex variables is provided.

Component tree analysis of cystovirus φ6 nucleocapsid Cryo-EM single particle reconstructions.

The 3-dimensional structure of the nucleocapsid (NC) of bacteriophage φ6 is described utilizing component tree analysis, a topological and geometric image descriptor. The component trees are derived from density maps of cryo-electron microscopy single particle reconstructions. Analysis determines position and occupancy of structure elements responsible for RNA packaging and transcription. Occupancy of the hexameric nucleotide triphosphorylase (P4) and RNA polymerase (P2) are found to be essentially complete in the NC. The P8 protein lattice likely fixes P4 and P2 in place during maturation. We propose that the viral procapsid (PC) is a dynamic structural intermediate where the P4 and P2 can attach and detach until held in place in mature NCs. During packaging, the PC expands to accommodate the RNA, and P2 translates from its original site near the inner 3-fold axis (20 sites) to the inner 5-fold axis (12 sites) with excess P2 positioned inside the central region of the NC.

XTEND: Extending the depth of field in cryo soft X-ray tomography.

We have developed a new data collection method and processing framework in full field cryo soft X-ray tomography to computationally extend the depth of field (DOF) of a Fresnel zone plate lens. Structural features of 3D-reconstructed eukaryotic cells that are affected by DOF artifacts in standard reconstruction are now recovered. This approach, based on focal series projections, is easily applicable with closed expressions to select specific data acquisition parameters.

Blob parameter selection for image representation.

A technique for optimizing parameters for image representation using blob basis functions is presented and demonstrated. The exact choice of the basis functions significantly influences the quality of the image representation. It has been previously established that using spherically symmetric volume elements (blobs) as basis functions, instead of the more traditional voxels, yields superior representations of real objects, provided that the parameters that occur in the definition of the family of blobs are appropriately tuned. The technique presented in this paper makes use of an extra degree of freedom, which has been previously ignored, in the blob parameter space. The efficacy of the resulting parameters is illustrated.

Data fusion in X-ray computed tomography using a superiorization approach.

X-ray computed tomography (CT) is an important and widespread inspection technique in industrial non-destructive testing. However, large-sized and heavily absorbing objects cause artifacts due to either the lack of penetration of the specimen in specific directions or by having data from only a limited angular range of views. In such cases, valuable information about the specimen is not revealed by the CT measurements alone. Further imaging modalities, such as optical scanning and ultrasonic testing, are able to provide data (such as an edge map) that are complementary to the CT acquisition. In this paper, a superiorization approach (a newly developed method for constrained optimization) is used to incorporate the complementary data into the CT reconstruction; this allows precise localization of edges that are not resolvable from the CT data by itself. Superiorization, as presented in this paper, exploits the fact that the simultaneous algebraic reconstruction technique (SART), often used for CT reconstruction, is resilient to perturbations; i.e., it can be modified to produce an output that is as consistent with the CT measurements as the output of unmodified SART, but is more consistent with the complementary data. The application of this superiorized SART method to measured data of a turbine blade demonstrates a clear improvement in the quality of the reconstructed image.

Morphology of influenza B/Lee/40 determined by cryo-electron microscopy.

Cryo-electron microscopy projection image analysis and tomography is used to describe the overall architecture of influenza B/Lee/40. Algebraic reconstruction techniques with utilization of volume elements (blobs) are employed to reconstruct tomograms of this pleomorphic virus and distinguish viral surface spikes. The purpose of this research is to examine the architecture of influenza type B virions by cryo-electron tomography and projection image analysis. The aims are to explore the degree of ribonucleoprotein disorder in irregular shaped virions; and to quantify the number and distribution of glycoprotein surface spikes (hemagglutinin and neuraminidase) on influenza B. Projection image analysis of virion morphology shows that the majority (∼83%) of virions are spherical with an average diameter of 134±19 nm. The aspherical virions are larger (average diameter = 155±47 nm), exhibit disruption of the ribonucleoproteins, and show a partial loss of surface protein spikes. A count of glycoprotein spikes indicates that a typical 130 nm diameter type B virion contains ∼460 surface spikes. Configuration of the ribonucleoproteins and surface glycoprotein spikes are visualized in tomogram reconstructions and EM densities visualize extensions of the spikes into the matrix. The importance of the viral matrix in organization of virus structure through interaction with the ribonucleoproteins and the anchoring of the glycoprotein spikes to the matrix is demonstrated.

SNARK09 - a software package for reconstruction of 2D images from 1D projections.

The problem of reconstruction of slices and volumes from 1D and 2D projections has arisen in a large number of scientific fields (including computerized tomography, electron microscopy, X-ray microscopy, radiology, radio astronomy and holography). Many different methods (algorithms) have been suggested for its solution. In this paper we present a software package, SNARK09, for reconstruction of 2D images from their 1D projections. In the area of image reconstruction, researchers often desire to compare two or more reconstruction techniques and assess their relative merits. SNARK09 provides a uniform framework to implement algorithms and evaluate their performance. It has been designed to treat both parallel and divergent projection geometries and can either create test data (with or without noise) for use by reconstruction algorithms or use data collected by another software or a physical device. A number of frequently-used classical reconstruction algorithms are incorporated. The package provides a means for easy incorporation of new algorithms for their testing, comparison and evaluation. It comes with tools for statistical analysis of the results and ten worked examples.

Superiorization: an optimization heuristic for medical physics.

PURPOSE: To describe and mathematically validate the superiorization methodology, which is a recently developed heuristic approach to optimization, and to discuss its applicability to medical physics problem formulations that specify the desired solution (of physically given or otherwise obtained constraints) by an optimization criterion. METHODS: The superiorization methodology is presented as a heuristic solver for a large class of constrained optimization problems. The constraints come from the desire to produce a solution that is constraints-compatible, in the sense of meeting requirements provided by physically or otherwise obtained constraints. The underlying idea is that many iterative algorithms for finding such a solution are perturbation resilient in the sense that, even if certain kinds of changes are made at the end of each iterative step, the algorithm still produces a constraints-compatible solution. This property is exploited by using permitted changes to steer the algorithm to a solution that is not only constraints-compatible, but is also desirable according to a specified optimization criterion. The approach is very general, it is applicable to many iterative procedures and optimization criteria used in medical physics. RESULTS: The main practical contribution is a procedure for automatically producing from any given iterative algorithm its superiorized version, which will supply solutions that are superior according to a given optimization criterion. It is shown that if the original iterative algorithm satisfies certain mathematical conditions, then the output of its superiorized version is guaranteed to be as constraints-compatible as the output of the original algorithm, but it is superior to the latter according to the optimization criterion. This intuitive description is made precise in the paper and the stated claims are rigorously proved. Superiorization is illustrated on simulated computerized tomography data of a head cross section and, in spite of its generality, superiorization is shown to be competitive to an optimization algorithm that is specifically designed to minimize total variation. CONCLUSIONS: The range of applicability of superiorization to constrained optimization problems is very large. Its major utility is in the automatic nature of producing a superiorization algorithm from an algorithm aimed at only constraints-compatibility; while nonheuristic (exact) approaches need to be redesigned for a new optimization criterion. Thus superiorization provides a quick route to algorithms for the practical solution of constrained optimization problems.

A fast optimization algorithm for multicriteria intensity modulated proton therapy planning.

PURPOSE: To describe a fast projection algorithm for optimizing intensity modulated proton therapy (IMPT) plans and to describe and demonstrate the use of this algorithm in multicriteria IMPT planning. METHODS: The authors develop a projection-based solver for a class of convex optimization problems and apply it to IMPT treatment planning. The speed of the solver permits its use in multicriteria optimization, where several optimizations are performed which span the space of possible treatment plans. The authors describe a plan database generation procedure which is customized to the requirements of the solver. The optimality precision of the solver can be specified by the user. RESULTS: The authors apply the algorithm to three clinical cases: A pancreas case, an esophagus case, and a tumor along the rib cage case. Detailed analysis of the pancreas case shows that the algorithm is orders of magnitude faster than industry-standard general purpose algorithms (MOSEK'S interior point optimizer, primal simplex optimizer, and dual simplex optimizer). Additionally, the projection solver has almost no memory overhead. CONCLUSIONS: The speed and guaranteed accuracy of the algorithm make it suitable for use in multicriteria treatment planning, which requires the computation of several diverse treatment plans. Additionally, given the low memory overhead of the algorithm, the method can be extended to include multiple geometric instances and proton range possibilities, for robust optimization.

Efficient Controls for Finitely Convergent Sequential Algorithms.

Finding a feasible point that satisfies a set of constraints is a common task in scientific computing: examples are the linear feasibility problem and the convex feasibility problem. Finitely convergent sequential algorithms can be used for solving such problems; an example of such an algorithm is ART3, which is defined in such a way that its control is cyclic in the sense that during its execution it repeatedly cycles through the given constraints. Previously we found a variant of ART3 whose control is no longer cyclic, but which is still finitely convergent and in practice it usually converges faster than ART3 does. In this paper we propose a general methodology for automatic transformation of finitely convergent sequential algorithms in such a way that (i) finite convergence is retained and (ii) the speed of convergence is improved. The first of these two properties is proven by mathematical theorems, the second is illustrated by applying the algorithms to a practical problem.

Phase retrieval for superposed signals from multiple binary objects.

We introduce the binary superposed phase retrieval problem that aims at reconstructing multiple 0/1-valued functions with nonoverlapping bounded supports from moduli of superpositions of several displaced copies of their individual Fourier transforms. We discuss an application in coherent diffraction imaging of crystalline objects, propose two algorithms, and evaluate their performance by means of simulations.

Fully three-dimensional defocus-gradient corrected backprojection in cryoelectron microscopy.

Recognizing that the microscope depth of field is a significant resolution-limiting factor in 3D cryoelectron microscopy, Jensen and Kornberg proposed a concept they called defocus-gradient corrected backprojection (DGCBP) and illustrated by computer simulations that DGCBP can effectively eliminate the depth of field limitation. They did not provide a mathematical justification for their concept. Our paper provides this, by showing (in the idealized case of noiseless data being available for all projection directions) that the reconstructions obtained based on DGCBP from data produced with distance-dependent blurring are essentially the same as what is obtained by a classical method of reconstruction of a 3D object from its line integrals. The approach is general enough to be applicable for correcting for any distance-dependent blurring during projection data collection. We present a new implementation of the DGCBP concept, one that closely follows the mathematics of its justifications, and illustrate it using mathematically described phantoms and their reconstructions from finitely many distance-dependently blurred projections.

A GREEDY METHOD FOR RECONSTRUCTING POLYCRYSTALS FROM THREE-DIMENSIONAL X-RAY DIFFRACTION DATA.

An iterative search method is proposed for obtaining orientation maps inside polycrystals from three-dimensional X-ray diffraction (3DXRD) data. In each step, detector pixel intensities are calculated by a forward model based on the current estimate of the orientation map. The pixel at which the experimentally measured value most exceeds the simulated one is identified. This difference can only be reduced by changing the current estimate at a location from a relatively small subset of all possible locations in the estimate and, at each such location, an increase at the identified pixel can only be achieved by changing the orientation in only a few possible ways. The method selects the location/orientation pair indicated as best by a function that measures data consistency combined with prior information on orientation maps. The superiority of the method to a previously published forward projection Monte Carlo optimization is demonstrated on simulated data.

A Note on the Behavior of the Randomized Kaczmarz Algorithm of Strohmer and Vershynin.

In a recent paper by T. Strohmer and R. Vershynin ["A Randomized Kaczmarz Algorithm with Exponential Convergence", Journal of Fourier Analysis and Applications, published online on April 25, 2008] a "randomized Kaczmarz algorithm" is proposed for solving systems of linear equations [Formula: see text] . In that algorithm the next equation to be used in an iterative Kaczmarz process is selected with a probability proportional to ‖a(i)‖ (2). The paper illustrates the superiority of this selection method for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values.In this note we point out that the reported success of the algorithm of Strohmer and Vershynin in their numerical simulation depends on the specific choices that are made in translating the underlying problem, whose geometrical nature is "find a common point of a set of hyperplanes", into a system of algebraic equations. If this translation is carefully done, as in the numerical simulation provided by Strohmer and Vershynin for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values, then indeed good performance may result. However, there will always be legitimate algebraic representations of the underlying problem (so that the set of solutions of the system of algebraic equations is exactly the set of points in the intersection of the hyperplanes), for which the selection method of Strohmer and Vershynin will perform in an inferior manner.

A note on exact image reconstruction from a limited number of projections.

In a recent paper in this journal by Kesidis and Papamarkos "A new method for the exact reconstruction of any gray-scale image from its projections is proposed." In this note we point out that this method is a special case of a well-known approach (peeling) and that it can produce exact reconstructions only under assumptions that are not realistic for practical methods of data collection. Further, we point out that some statements made in the paper regarding disadvantages of the algebraic reconstruction techniques (ART) as compared to the method of the paper are false.

A fast algorithm for solving a linear feasibility problem with application to Intensity-Modulated Radiation Therapy.

The goal of Intensity-Modulated Radiation Therapy (IMRT) is to deliver sufficient doses to tumors to kill them, but without causing irreparable damage to critical organs. This requirement can be formulated as a linear feasibility problem. The sequential (i.e., iteratively treating the constraints one after another in a cyclic fashion) algorithm ART3 is known to find a solution to such problems in a finite number of steps, provided that the feasible region is full dimensional. We present a faster algorithm called ART3+. The idea of ART3+ is to avoid unnecessary checks on constraints that are likely to be satisfied. The superior performance of the new algorithm is demonstrated by mathematical experiments inspired by the IMRT application.

Parallel Fuzzy Segmentation of Multiple Objects.

The usefulness of fuzzy segmentation algorithms based on fuzzy connectedness principles has been established in numerous publications. New technologies are capable of producing larger-and-larger datasets and this causes the sequential implementations of fuzzy segmentation algorithms to be time-consuming. We have adapted a sequential fuzzy segmentation algorithm to multi-processor machines. We demonstrate the efficacy of such a distributed fuzzy segmentation algorithm by testing it with large datasets (of the order of 50 million points/voxels/items): a speed-up factor of approximately five over the sequential implementation seems to be the norm.

Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization.

Although three-dimensional electron microscopy (3D-EM) permits structural characterization of macromolecular assemblies in distinct functional states, the inability to classify projections from structurally heterogeneous samples has severely limited its application. We present a maximum likelihood-based classification method that does not depend on prior knowledge about the structural variability, and demonstrate its effectiveness for two macromolecular assemblies with different types of conformational variability: the Escherichia coli ribosome and Simian virus 40 (SV40) large T-antigen.

Maximum-likelihood multi-reference refinement for electron microscopy images.

A maximum-likelihood approach to multi-reference image refinement is presented. In contrast to conventional cross-correlation refinement, the new approach includes a formal description of the noise, implying that it is especially suited to cases with low signal-to-noise ratios. Application of this approach to a cryo-electron microscopy dataset revealed two major classes for projections of simian virus 40 large T-antigen in complex with an asymmetric DNA-probe, containing the origin of simian virus 40 replication. Strongly bent projections of dodecamers showed density that may be attributed to the complexed double-stranded DNA, while almost straight projections revealed a twist in the relative orientation of the hexameric subunits. This new level of detail for large T-antigen projections was not detected using conventional techniques. For a negative stain dataset, maximum-likelihood refinement yielded results that were practically identical to those obtained using conventional multi-reference refinement. Results obtained using simulated data suggest that the efficiency of the maximum-likelihood approach may be further enhanced by explicitly incorporating the microscope contrast transfer function in the image formation model.