High resolution imaging of biological macromolecules using x-ray crystallography is a key component of modern molecular biology, the results of which are essential for understanding biological processes in health and disease, and for drug design. Macromolecular imaging is currently undergoing a revolution as a result of the recent availability of x-ray free-electron lasers (XFELs). XFELs produce extremely intense, ultra-short x-ray pulses which offer the possibility of imaging specimens that are different to the 3D crystals used in conventional x-ray crystallography. The application of XFEL imaging to nano-crystalline fibrous specimens - long, slender systems that are periodic in their axial direction exhibit partial lateral crystallinity - is investigated. It is shown that individual Fourier amplitudes can be measured from XFEL data from such specimens. It is demonstrated that the image reconstruction problem from diffraction data for specimens with reduced crystallinity, specifically 2D membranes, is achievable. Although such specimens are weakly diffracting, they potentially offer more information in their diffraction than do 3D crystals. Image reconstruction is demonstrated by simulation.
In MRI the presence of metal implants causes severe artifacts in images and interferes with the usual techniques used to separate fat signals from other tissues. In the Dixon method, three images are acquired at different echo times to enable the variation in the magnetic field to be estimated. However, the estimate is represented as the phase of a complex quantity and therefore suffers from wrapping. High field gradients near the metal mean that the phase estimate is undersampled and therefore challenging to unwrap.
We have developed POP, phase estimation by onion peeling, an algorithm which unwraps the phase along 1-D paths for a 2-D image obtained with the Dixon method. The unwrapping is initially performed along a closed path enclosing the implant and well separated from it. The recovered phase is expanded using a smooth periodic basis along the path. Then, path-by-path, the estimate is applied to the next path and then the expansion coefficients are estimated to best fit the wrapped measurements. We have successfully tested POP on MRI images of specially constructed phantoms and on a group of patients with hip implants.
In principle, POP can be extended to 3-D imaging. In that case, POP would entail representing phase with a suitably smooth basis over a series of surfaces enclosing the implant (the "onion skins"), again beginning the phase estimation well away from the implant. An approach for this is proposed.
Results are presented for fat and water separation for 2-D images of phantoms and actual patients. The practicality of the method and its employment in clinical MRI are discussed.
The recent availability of ultra-bright and ultra-short X-rays pulses from new sources called x-ray free-electron lasers (XFELs) has introduced a new paradigm in X-ray crystallography. Called "diffraction-before-destruction," this paradigm addresses the main problems that plague crystallography using synchrotron sources. However, the phase problem of coherent diffraction imaging remains: one has to retrieve the phase of the measured diffraction amplitude in order to reconstruct the object. Fibrous and membrane proteins that crystallize in 1D and 2D crystals can now potentially be used for data collection with free-electron lasers. The crystallographic phase problem with such crystalline specimens is eased as the Fourier amplitude can be sampled more finely than at the Bragg sampling along one or two directions. Here we characterise uniqueness of the phase problem for different types of crystalline specimen. Simulated ab initio phase retrieval using iterative projection algorithms for 2D crystals is presented.
Serial femtosecond nanocrystallography (SFX) is a form of x-ray coherent diffraction imaging that utilises a stream of tiny nanocrystals of the biological assembly under study, in contrast to the larger crystals used in conventional x-ray crystallography using conventional x-ray synchrotron x-ray sources. Nanocrystallography utilises the extremely brief and intense x-ray pulses that are obtained from an x-ray free-electron laser (XFEL). A key advantage is that some biological macromolecules, such as membrane proteins for example, do not easily form large crystals, but spontaneously form nanocrystals. There is therefore an opportunity for structure determination for biological molecules that are inaccessible using conventional x-ray crystallography. Nanocrystallography introduces a number of interesting image reconstruction problems. Weak diffraction patterns are recorded from hundreds of thousands of nancocrystals in unknown orientations, and these data have to be assembled and merged into a 3D intensity dataset. The diffracted intensities can also be affected by the surface structure of the crystals that can contain incomplete unit cells. Furthermore, the small crystal size means that there is potentially access to diffraction information between the crystalline Bragg peaks. With this information, phase retrieval is possible without resorting to the collection of additional experimental data as is necessary in conventional protein crystallography. We report recent work on the diffraction characteristics of nanocrystals and the resulting reconstruction algorithms.
The problem of reconstructing multiple objects from the average of their diffracted intensities is considered. Three cases of technical interest are studied. The first is where the incoherent average is measured over a single object that adopts a number of positions described by a symmetry group. The second is where the average is over a small number of distinct objects. The third is where the average is over a set of unit cells that can occur in an ensemble of nanocrystals as a result of different edge terminations. As a result of some redundancy in the multi-dimensional phase problem, a unique solution can be obtained for these problems under some circumstances. Uniqueness is characterised using the constraint ratio. Iterative projection algorithms can be adapted to accommodate these cases and example simulated reconstructions are presented.
Magnetic resonance imaging (MRI) has the potential to be the best technique for assessing complications in patients with metal orthopedic implants. The presence of fat can obscure definition of the other soft tissues in MRI images, so fat suppression is often required. However, the performance of existing fat suppression techniques is inadequate near implants, due to very significant magnetic field perturbations induced by the metal. The three-point Dixon technique is potentially a method of choice as it is able to suppress fat in the presence of inhomogeneities, but the success of this technique depends on being able to accurately calculate the phase shift. This is generally done using phase unwrapping and/or iterative reconstruction algorithms. Most current phase unwrapping techniques assume that the phase function is slowly varying and phase differences between adjacent points are limited to less than π radians in magnitude. Much greater phase differences can be present near metal implants. We present our experience with two phase unwrapping techniques which have been adapted to use prior knowledge of the implant. The first method identifies phase discontinuities before recovering the phase along paths through the image. The second method employs a transform to find the least squares solution to the unwrapped phase. Simulation results indicate that the methods show promise.
Protein X-ray crystallography is a method for determining the three-dimensional structures of large biological molecules by analysing the amplitudes of X-rays scattered from a crystalline specimen of the molecule under study. Conventional structure determination in protein crystallography requires chemical modification to the sample and collection of additional data in order to solve the corresponding phase problem. There is an urgent need for a direct (digital) low-resolution phasing method that does not require modified specimens. Whereas diffraction from large crystals corresponds to samples (so-called Bragg samples) of the amplitude of the Fourier transform of the scattering density, the diffraction from very small crystals allows measurement of the diffraction amplitude between the Bragg samples. Although highly attenuated, these additional measurements offer the possibility of iterative phase retrieval without the use of ancillary experimental data. In this study we examine the noise characteristics of small-crystal diffraction and propose a data selection strategy to improve the quality of reconstructions using iterative phase retrieval algorithms. Simulation results verify that a higher noise level can be tolerated by using such a data selection strategy.
The problem of estimating wind velocities from limited flight data recordings is considered, with application to
sailplane flights in high-altitude atmospheric mountain waves. Sailplane flight recorders routinely measure only
GPS position and the problem is highly underdetermined. The nature of this problem is studied and a maximum
a posteriori estimator is developed using prior information on the wind velocity and the sailplane airspeed and
heading. The method is tested by simulation and by application to sailplane flight data.
A brief description of various iterative projection algorithms and the relationships between them is given, along
with some possible reasons for their ability to solve non-convex problems. An empirical model of their behaviour
when applied to non-convex problems is also described.
Symmetry provides a source of redundancy which can be exploited in image reconstruction. In particular, internal
symmetries in molecules can help to compensate for the loss of Fourier phase information in macromolecular x-ray
crystallography. Symmetry projections are incorporated into iterative projection algorithms for reconstruction
of macromolecular electron densities from x-ray diffraction amplitudes from crystals. The effects of interpolation
are studied and the algorithms are applied to reconstruction of an icosahedral virus.
Proc. SPIE. 7800, Image Reconstruction from Incomplete Data VI
KEYWORDS: Statistical analysis, Data modeling, In situ metrology, Error analysis, Data processing, Velocity measurements, Atmospheric modeling, Wind measurement, Global Positioning System, Data analysis
The problem of estimating the wind velocity from measurement of limited flight data from a sailplane flight in
atmospheric mountain waves is considered. A Sailplane are often equipped with a flight recorder that records
position, and sometimes other information, at regular intervals during the flight. These data contain information
on the state of the atmosphere during the flight. A maximum likelihood method is developed for estimating
wind fields using such sailplane flight data. The methods are evaluated by application to simulated flight data.
A hybrid method is presented which allows the acceleration of parallel MR imaging through combining the ideas
of compressed sensing with inversion of the imaging matrix. A novel data reordering is employed to enhance the
sparsity inherent in the image transform. Simulation results with actual head scan data are presented.
An algorithm is described for reconstructing compact binary images from limited Fourier amplitude data. This
problem arises in macromolecular crystallography where one wishes to reconstruct the molecular envelope from
crystal x-ray diffraction amplitudes using a solvent contrast series. Such data are the amplitude of the Fourier
transform of an object that has a constant electron density within the boundary of the molecule and zero outside.
The image is thus binary and compact, but the data are available only within a limited resolution range in Fourier
space and are undersampled. The problem is solved using an iterative projection algorithm; a class of algorithm
used to solve inverse problems for which the solution is subject to a number of constraints that represent a priori
information and the data. Unfortunately, these algorithms experience convergence difficulties if one or more of
the constraints are non-convex, which is the case for all the constraints in this problem. We solve the problem
by constructing appropriate projection operators and implementing the difference map projection algorithm.
Simulations are used to study convergence behaviour of the algorithm.
Proc. SPIE. 6913, Medical Imaging 2008: Physics of Medical Imaging
KEYWORDS: Signal to noise ratio, Magnetic resonance imaging, Image restoration, Receivers, Computer programming, Data acquisition, Temporal resolution, Angiography, Magnetic resonance angiography, Resonance enhancement
A new way of performing contrast enhanced magnetic resonance angiography (CE-MRA) is presented, in which the entire k-space is decomposed into interlaced subsets that are acquired sequentially. Based on a new parallel imaging technique, Generalized Unaliasing Incorporating object Support constraint and sensitivity Encoding (GUISE), reconstructions can be made using different subsets of k-space to reveal the level of contrast agent in the corresponding data acquisition time period. A proof-of-concept study using a custom made phantom was carried out to examine the utility of the new method. A quantity of contrast agent (copper sulfate solution) was injected into water flowing within a tube while data was acquired using an 8-coil receiver and the modified MRI sequence. A sequence of images was successfully reconstructed at high temporal resolution. This eliminated the need to precisely synchronize data acquisition with contrast arrival. Furthermore, subtraction of a pre-contrast data set prior to reconstruction, which eliminates the need for recovering the static background signal, has proven to be an effective way to improve the SNR and allow a higher temporal resolution to be achieved in recovering the dynamic signal containing contrast level change. Acceptably good reconstruction results were obtained at a temporal resolution equivalent to a 16-fold speed up compared to the time taken to fully sample k-space.
Myosin filaments are important components of striated muscle and pack in a two-dimensional array.
The array can be imaged by electron microscopy of thin cross-sections which shows, for many species,
that the filaments adopt two orientations with an interesting statistical distribution. Analysis of the
micrographs and Monte Carlo modelling shows that the disorder maps to a frustrated Ising model.
The size and shape of the stones in dry gravel river beds are of interest in geology and river hydraulics.
The topography of a bed surface can be measured by three-dimensional laser scanning. A method
is described for fitting ellipsoids to the surfaces of individual stones to estimate their size, shape and
orientation in the river bed. Different cost functions are evaluated and the methods are applied to data
from a gravel river bed in the South Island of New Zealand.
Patient motion during magnetic resonance imaging (MRI) can produce significant artifacts in a reconstructed
image. Since measurements are made in the spatial frequency domain ('k-space'), rigid-body translational
motion results in phase errors in the data samples while rotation causes location errors. A method is presented
to detect and correct these errors via a modified sampling strategy, thereby achieving more accurate image
reconstruction. The strategy involves sampling vertical and horizontal strips alternately in k-space and employs
phase correlation within the overlapping segments to estimate translational motion. An extension, also based
on correlation, is employed to estimate rotational motion. Results from simulations with computer-generated
phantoms suggest that the algorithm is robust up to realistic noise levels. The work is being extended to physical
phantoms. Provided that a reference image is available and the object is of limited extent, it is shown that a
measure related to the amount of energy outside the support can be used to objectively compare the severity of
Phase retrieval has seen a resurgence of interest in the last ten years as a result of some serendipitous
developments in instrumentation (high flux x-ray sources) for molecular and nano-particle imaging.
This has led to new applications, new formulations of iterative phase retrieval algorithms, and some
new algorithms. These new developments are reviewed.
Myosin filaments are important components of striated muscle and pack in a semi-ordered, two-dimensional
array. The array can be imaged by electron microscopy of thin cross-sections which
indicates, for many species, that the filaments adopt two orientations that are distributed with short-ranging
order. We describe analysis and modelling of this substitution disorder based on the micrographs
and an Ising model.
An automated image analysis system for determination of myosin filament orientations in electron micrographs of muscle cross-sections is described. Analysis of the distribution of the orientations is important in studies of muscle structure, particularly for interpretation of x-ray diffraction data. Filament positions are determined using h-dome extraction and image filtering, based on grayscale reconstruction. Erroneous locations are eliminated based on lattice regularity. Filament orientations are determined by correlation with a template that incorporates the salient filament characteristics and classified using a Gaussian mixture model. Application to a number of micrographs and comparison with manual classifications of orientations shows that the system is effective in many cases.
Airflow over mountainous terrain can produce atmospheric waves in the lee of the mountains that have large vertical air velocities. These waves are used as sources of lift by sailplane pilots. Methods are developed for inverting flight data of airspeed and GPS-derived position to obtain estimates of the vector windspeed in mountain waves. Data from flight path segments with significantly different ground velocities within a region of constant windspeed give a well-determined solution for the windspeed. The methods are applied to flight data from a Perlan Project flight in lee waves of the Sierra Nevada Mountains in California.
The relative effects of spectral amplitude and phase errors on reconstructed images are studied in terms of the expected mean-square-error in the image. An appropriate mean-square-error appears to be that between reconstructed and original images that are scaled to have the same energy. Such an error metric appears to reflect the overall perceived quality of the images. Approximate relationships between spectral amplitude and phase errors that give rise to the same image mean-square-error are derived. For large amplitude errors saturation is significant and is studied by simulation. Simulations are used to illustrate these relationships. The relationship to phase dominance is discussed.
The inverse problem of determining the structure (atomic coordinates) of a helical molecule from measurements of the intensities of x-rays diffracted from a disordered, oriented, polycrystalline fiber of the molecule is considered. The problem is highly underdetermined, but can be solved by incorporating additional geometric and steric information. However, current solution methods do not allow for disorder in the fiber specimen. A method for solving this problem for disordered fibers is described that utilizes current solution methods by iteratively modifying the diffraction data to account for the disorder. The method is successfully applied to diffraction data from a disordered DNA fiber.
A Bayesian optimization scheme is presented for reconstructing fluorescent yield and lifetime, the absorption coefficient, and the scattering coefficient in turbid media, such as biological tissue. The method utilizes measurements at both the excitation and emission wavelengths for reconstructing all unknown parameters. The effectiveness of the reconstruction algorithm is demonstrated by simulation and by application to experimental data from a tissue phantom containing a fluorescent agent.
Optical diffusion tomography is a new imaging modality that offers significant potential in medical applications. The resulting nonlinear image reconstruction problem is further complicated by the fact that for practical imaging variable source excitation and detector coupling needs to be accounted for in order to obtain quantitative images. We formulated the joint problem of coupling coefficient estimation and three-dimensional image reconstruction in a Bayesian framework, and the resulting estimates are computed in an iterative coordinate-descent optimization scheme. Simulations show that this approach is an accurate and efficient method for simultaneous reconstruction of absorption and diffusion coefficients, as well as the coupling coefficients.
We demonstrate accurate and efficient three-dimensional optical diffusion imaging using simulated noisy data from a set of measurements at a single modulation frequency. A Bayesian framework provides for prior model conditioning, and a dual-step cost function optimization allows sequential estimation of the data noise variance and the image.
The M&diaero;bius inversion formula is an interesting theorem from number theory that has application to a number inverse problems, particularly lattice problems. Specific inverse problems, however, often require related M&diaero;bius inversion formulae that can be derived from the fundamental formula. Derivation of such formulae is not easy for the non- specialist, however. Examples of the kinds of inversion formulae that can be derived and their application to inverse lattice problems are described.
In synthetic aperture sonar, the highest platform speed is limited as a result of the low speed of sound in water and the requirement for adequate sampling in the along-track direction. This can result in slow seafloor mapping. The highest allowable platform speed can be increased by using a linear array of hydrophones. The signal-to-noise can also be improved by using multiple sets of hydrophone arrays. Maximum-likelihood estimation of images using data from sets of hydrophone arrays that each under-sample the underlying signal to different degrees is described. Simulations for synthetic aperture sonar imaging show that this improves the images obtained over those from a single array.
Optical diffusion imaging is a new imaging modality that promises great potential in applications such as medical imaging, environmental sensing and nondestructive testing. It presents a difficult nonlinear image reconstruction problem however. An inversion algorithm is formulated in Bayesian framework, and an efficient optimization technique that uses iterative coordinate descent is presented. A general multigrid optimization technique for nonlinear image reconstruction problems is developed and applied to the optical diffusion imaging problem. Numerical results show that this approach improves the quality of reconstructions and dramatically decreases computation times.
A method for estimating the point spread function of a remotely sensed image is described. The technique developed is based on locating and measuring blurred linear features in the imagery and tomographically reconstructing the point spread function. Image features able to be modeled by a single step function or by a combination of two steps are located. For the latter cases a form of blind deconvolution is applied to extract the estimate of the line spread function (equivalent to the projection of the point spread function in the direction of the feature). The process is unsupervised and requires only that the image contains suitable linear features. Examples are given of the estimation of blur in satellite images.
The central problem in the determination of protein structures form x-ray diffraction dada (x-ray crystallography) corresponds to a phase retrieval problem with undersampled amplitude data. Algorithms for this problem that have an increased radius of convergence have the potential for reducing the amount of experimental work, and cost, involved in determining protein structures. We describe such an algorithm. Application of the algorithm to a simulated crystallographic problem shows that it converges to the correct solution, with no initial phase information, where currently used algorithms fail. The results lend support to the possibility of ab initio phasing in protein crystallography.
Frequency-domain diffusion imaging is a new imaging modality which uses the magnitude and phase of modulated light propagation through a highly scattering medium to reconstruct an image of the scattering and/or the absorption coefficient in the medium. In this paper, the inversion algorithm is formulated in a Bayesian framework and an efficient optimization technique is presented for calculating the maximum a posteriori image. Numerical result show that the Bayesian framework with the new optimization scheme out-performs conventional approaches in both speed and reconstruction quality.
The structure completion problem in x-ray fiber diffraction is addressed from a Bayesian perspective. The experimental data are sums of the squares of the amplitudes of particular sets of Fourier coefficients of the electron density. In addition, a part of the electron density. In addition, a part of the electron density is known. The image reconstruction problem is to estimate the missing part of the electron density. A Bayesian approach is taken in which the prior model for the image is based on the fact that it consists of atoms, i.e., the unknown electron density consists of separated sharp peaks. The posterior for the Fourier coefficients typically takes the form of an independent and identically distributed multivariate normal density restricted to the surface of a hypersphere. However, the electron density often exhibits symmetry, in which case, the Fourier coefficient components are not longer independent or identically distributed. A diagonalization process results in an independent multivariate normal probability density function, restricted to a hyperspherical surface. the analytical form for the mean of the posterior density function is derived. The mean can be expressed as a weighting function on the Fourier coefficients of the known part of the electron density. The weighting function for the hyperellipsoidal and hyperspherical cases are compared.
A weighted distorted Born iterative method is presented for reconstruction optical diffusion images from scattering data. A generalization of the distorted Born iterative method that uses a preconditioned cost function and an elliptical constraint allows a weighting matrix to be applied to the gradient term in the iterative algorithm according to the reconstruction history. The proposed algorithm shows stable and fast convergence for reconstruction of high contrast inhomogeneities.
An algorithm is described for incorporating symmetry information into reconstruction of an image from the amplitude of its Fourier transform. The symmetry is used to compensate for the loss of information due to sampling of the Fourier amplitude below the Nyquist density. The study is motivated by an image reconstruction problem in x-ray crystallography. Application of the algorithm to a simulated crystallographic problem shows that it converges to the correct solution, with no initial phase information, where algorithms currently used in crystallography fail. The results lend support to the possibility of ab initio phase retrieval in macromolecular crystallography when sufficient ta priori information is available.
We address a problem of reconstruction of a periodic image from information in image space and Fourier space. The real space information consists of knowledge of part of the image, while the Fourier space information is data in the form of sums of the squares of the amplitudes of sets of particular Fourier coefficients of the image. Such a problem occurs in the determination of polymer structures from x-ray fiber diffraction data. We present a Bayesian approach to this problem, incorporating a priori model for the image based on the structure being made up of 'atoms'. The Bayesian minimum mean-square-error estimate for the missing part of the image is derived. Currently used heuristic estimates are the maxima of certain posterior densities. Simulations are performed for varying amounts of real and Fourier space information to assess the performance of the different estimators. The performance of the minimum mean- square-error estimate is superior to that of the other estimates.
Phase retrieval for reconstructing symmetric molecules from x-ray crystallographic data is investigated. The additional information contained in the symmetry should be sufficient to render the solution to such problems unique in many cases. This is supported by the application of iterative phase retrieval algorithms to simulated crystallographic data from a model of an icosahedral virus particle.
Theory is developed to describe diffraction, in the weak scattering regime, from finite distorted lattices. Correlations between lattice distortions are modeled using an imposed correlation field. The validity of the imposed correlation field is examined. Expressions for the intensity, and the circularly averaged intensity, diffracted from an ensemble of distorted lattices are derived. Calculated diffraction patterns are used to examine the relationship between diffraction and the kind and degree of disorder in a specimen. Implications of this work for inverse problems in x-ray crystallography are discussed.
Recovery of an image from a finite set of irregularly spaced samples is considered. A method of ranking the quality of such sampling sets described by Chen and Alleback is extended to the case of unequal numbers of samples. Calculations provide information on the relative effects of sample number, density and nonuniformity on reconstruction error.
The problem of reconstructing a three-dimensional scatterer from measurements of the cylindrical average of the intensity of its Fourier transform is discussed. Reconstruction involves phase retrieval as well as unraveling the effects of cylindrical averaging. The application area considered is x-ray analysis of polymer fibers, and other systems, that consist of collections of rotationally disordered particles. Diffraction from these types of specimens and reconstruction algorithms are described. The particles in these applications often exhibit helical symmetry and the effect of this on reconstruction is described.
X-ray crystallography is concerned with the determination of molecular structures from measurements of scattered x-rays and, historically, represents the first study of phase problems. The crystallographic problem is distinct from most other image reconstruction problems however, because of the periodic nature of the image. Reconstruction algorithms used in crystallography that make use of various kinds of constraints are described. Uniqueness properties are described and compared with those that apply in general imaging contexts.
The problem of determining the internal structure of the earth from the frequencies of free oscillation is considered. The simplified case of a spherically symmetric fluid sphere is examined. An asymptotic analysis implies that a velocity profile that is a small perturbation from a homogeneous fluid is determined, up to a finite number of parameters, by two infinite spectra of appropriate angular orders. A numerical study of the problem for finite spectra indicates what types of spectral data allow a stable reconstruction.
The problem of determining the density distribution of a circularly symmetric elastic membrane, fixed on the edge, from its frequencies of free vibration, is examined. An asymptotic analysis implies that a density function that is a small perturbation from a homogeneous membrane is determined, up to a finite number of parameters, by two infinite spectra of appropriate angular orders. An algorithm for reconstructing the density from the spectra is presented. The results are illustrated by numerical simulations.
It is shown that multiple blind deconvolution and phase retrieval in three or more dimensions are overdetermined problems if the image or Fourier amplitude, respectively, is measured continuously (or, equivalently, is sampled at the Nyquist rate). A sampling scheme is derived that removes the overdeterminancy and allows a measure of the redundancy to be defined. This indicates that phase retrieval and deconvolution are more stable, with respect to noise and partial information, with increasing dimensionality.
SC201: Practical Digital Image Reconstruction Algorithms
Many technical disciplines (e.g. remote sensing, medical imaging, etc.) require digital processing of data to reconstruct an image. This course presents an analysis of methods and algorithms used for reconstructing images from distorted and/or incomplete data, and the development for specific applications. Topics covered include image formation and degradation, Fourier methods and computations, filtering, projection- and probabilistic-based algorithms, deconvolution (deblurring), and phase retrieval.