Abstract
Ultrasonic computed tomography (UCT) is a potentially useful technique that has been explored for decades in the context of medical imaging. UCT can provide quantitative images of acoustical parameters such as speed of sound, attenuation, and density from measurements of pressure fields. Throughout the years, several algorithms that rely on different wave propagation models have been developed. In this chapter, the fundamentals of forward and inverse solvers for ultrasonic tomography will be described.
Access provided by Autonomous University of Puebla. Download chapter PDF
Similar content being viewed by others
Keywords
1 Ultrasonic Tomography and the Wave Equation
Ultrasound imaging is widely used as a tool for medical diagnosis. The most commonly used ultrasonic imaging method is sonography or B-mode imaging. B-mode imaging uses data in reflection mode to produce anatomical greyscale images. The brightness of each pixel is proportional to the amplitude of the logarithmically compressed envelope of the echoes produced by tissues. Spatial localization is performed using the pulse-echo principle.
However, the propagation of acoustic waves is a much richer phenomenon than simple reflections of acoustic echoes. Attempts were conducted in the early 1970s to produce ultrasonic images in transmission mode that were more similar to projective images formed with other modalities such as radiography and scintigraphy. These transmission-mode ultrasonic images were constructed by placing a transmitter and a receiver transducer to face each other. By raster scanning a sample placed in between the transducer pair, images of quantities such as transmitted amplitude (Green et al. 1974; Marich et al. 1975) and time-of-flight delays (Heyser and Croissette 1973, 1974) were produced. Advantages of using ultrasound for projective imagings included the use of non-ionizing radiation and the potential to exploit new sources of contrast for diagnostic imaging.
It was also in the early 1970s that the feasibility of applying the theory of transmission tomography for clinical practice was demonstrated. In particular, Hounsfield developed the first X-ray computed tomography device that allowed production of two-dimensional cross-sectional images of X-ray attenuation coefficients from a set of projection data at different orientation angles (Hounsfield 1973). This is not the only tomographic imaging modality used in clinical practice. The concept of emission tomography using SPECT actually predates X-ray tomography, having been demonstrated by Kuhl and Edwards in the 1960s (1963). Emission tomography of humans using PET was reported in the mid 1970s (Phelps et al. 1976). It was also by the mid 1970s that live animal imaging using magnetic resonance principles was demonstrated (Damadian 1971; Lauterbur 1974). The advantages of tomographic imaging compared to projective imaging were quickly appreciated by the medical community. It is therefore not surprising that researchers in the field of ultrasonic imaging also attempted to construct tomograms from ultrasound projective data.
Acoustic tomography encompasses a set of techniques that aim to reconstruct images of acoustic parameters from measurements of scattered pressure fields at different spatial locations and frequencies. Considering the case of an incident monochromatic field of angular frequency \(\omega \) propagating in fluid media, the wave equation can be written as
where \(p(\mathbf {r})\) is the acoustical pressure, \(\phi ^{\text{inc}}(\mathbf {r})\) are the acoustical sources, \(k(\mathbf {r})\) is the complex wave number, and \(\rho (\mathbf {r})\), \(c(\mathbf {r})\) and \(\alpha _{\omega }(\mathbf {r})\) are the density, sound speed, and acoustic attenuation (at frequency \(\omega \)) of the medium, respectively.
Equation (14.1) explicitly shows the relationship between parameters of the medium and the complex scattered pressure field. Therefore, by inverting the wave equation one can potentially create images of these parameters. Towards this end, several approaches have been pursued throughout the decades in order to obtain quantitative two- and three-dimensional tomographic ultrasonic images.
2 Ray-Based Acoustic Tomography
The first experimental demonstrations of ultrasonic tomography were performed in the early 1970s. Given the limited power of computer resources at that time, it is not surprising that initial attempts at ultrasonic tomography were based on simplifications of the wave equation. If density is assumed to be constant, the wave equation (14.1) in the absence of a source can be written as
If we let \(p=p_0 \exp (-ik_0\tau (\mathbf {r}))\), with the wave number \(k_0\) corresponding to a homogeneous background of sound speed \(c_0\), then the wave equation can be rewritten in terms of the acoustic wavefront \(\tau (\mathbf {r})\) as
Furthermore, if the medium is assumed lossless and the wavelength \(\lambda _0 \rightarrow 0\), the equation above can be written as
where \(n(\mathbf{{r}})=c_0/c(\mathbf{{r}})\) is the acoustic index of refraction. Equation (14.4) is known as the eikonal equation, and is a fundamental result in geometrical acoustics (Pierce 1989). The eikonal equation dictates how the acoustic wave front changes due to variations of the acoustic wave number. The eikonal equation can alternatively be written as
where \(s(\mathbf{{r}})=1/c(\mathbf{{r}})\) is the slowness and \(T(\mathbf{{r}},s) = \tau (\mathbf{{r}},c)/c_0\) is the time of flight required for the wave to reach point \(\mathbf {r}.\)
2.1 Straight-Ray Propagation
A very significant implication of Eq. (14.4) is that if variations of \(s(\mathbf {r})\) are assumed to be negligible, i.e., \(s({\mathbf {r}}) \approx {1/c_0}\), then \(|\nabla T(\mathbf {r})|\) is a constant. Therefore, the minimum-time arrival path between a transmitter and a receiver is a straight line. Although some researchers attempted to perform acoustic tomography through bone (Carson et al. 1977; Dines et al. 1981), a more favorable condition is met when imaging soft tissues for which expected refraction index changes are typically less than 10 % (Goss et al. 1978, 1980). Therefore, at least in principle it was reasonable to assume a straight ray propagation between a transmitter and a receiver when imaging regions of the body composed exclusively of soft tissues. A particular but important case that satisfied this requirement was breast imaging, which to this day remains the most widely studied medical application of acoustic tomography.
Straight-ray acoustic tomography. Transducers with a narrow beam width are arranged in a line of transmitters (red) and a line of receivers (blue), and measurements of time-of-flight are collected. The scattering object occupies the region of space \(\Omega \)
Time-of-flight tomography creates tomograms of sound speed using measurements of \(\Delta T (\mathbf{{r}}_t, \mathbf{{r}}_r) = T(\mathbf{{r}}_r - \mathbf{{r}}_t, s) - T(\mathbf {r}_r - \mathbf {r}_t, s_0)\), i.e., the difference in times of arrival between a transmitter at \({\mathbf {r}}_t\) and a receiver at \({\mathbf {r}}_r\) with and without the sample in between the transducers. If straight-ray propagation is assumed, \(\Delta T ({\mathbf {r}}_t, {\mathbf {r}}_r)\) can be related to the slowness using
where \(\Delta s = \left( s(\mathbf{{r}}) - s_0 \right) \). Consider the case of transmitters and receivers distributed in straight lines as shown in Figure 14.1. Equation (14.6) can then be rewritten as
With this configuration, the same theory extensively used for other tomographic medical imaging modalities can be used to create index of refraction tomograms (Greenleaf et al. 1975). In particular, and using the notation in Fig. 14.1, the Fourier slice theorem (Bracewell 1956) states that
i.e., the values of the 1D Fourier transform of the measured data \(\Delta T(p, \theta )\) correspond to samples of the 2D Fourier transform of \(\Delta s(\mathbf {r})\) over a line at \(\theta \) degrees passing through the origin of k-space. A widely used method for the solution of Eq. (14.6) is the filtered backprojection algorithm (Bracewell and Riddle 1967; Ramachandran and Lakshminarayanan 1971; Shepp and Logan 1971). The algorithm is based on rewriting (14.8) in polar coordinates, which results in
where \(\displaystyle \Delta \bar{T}(\kappa , \theta )\) is the 1D Fourier transform of \(\Delta T(p, \theta )\). The second integral in Eq. (14.9) is the convolution of \(\Delta T(p, \theta )\) with a filter \(h(p)\) whose Fourier transform is equal to \(|\kappa |.\) Therefore, Eq. (14.9) can be rewritten as
where \(\displaystyle \Delta T_h(p, \theta ) = \Delta T(p, \theta ) \mathop {*}_{p} h(p)\) and \(\displaystyle \mathop {*}_{p}\) represents the convolution with respect to \(p\). Algebraic methods were also developed for the inversion of Eq. (14.6) such as the simultaneous algebraic reconstruction technique (SART) (Andersen and Kak 1984). Reconstruction methods for fan-beam tomography were also explored for UCT under straight ray propagation assumptions (Glover 1978).
Creating tomograms of acoustic attenuation proved to be slightly more complicated. It was initially postulated that projections could be constructed from either transmitted signal amplitude or integrated intensity measurements (Greenleaf et al. 1974). However, these measurements were found to be sensitive to effects such as out-of-plane signal propagation, signal loss due to reflection, and phase cancellation across the receiver. Therefore, some researchers suggested extracting projection data from the power spectrum of the received data instead (Dines and Kak 1979; Klepper et al. 1981). After proper measurement of projection data, the reconstruction process was carried out using the same methods described for time-of-flight tomography.
2.2 Refraction-Corrected Tomography
However, the simple straight-ray model was quickly found to be inappropriate for tomography based on acoustic waves. In spite of the low variations of refraction index, ultrasonic waves may undergo a non-negligible amount of refraction when propagating through soft tissues. This is not the case for X-ray imaging, for which refraction effects can be safely neglected. This limitation was acknowledged even in the early days of acoustic tomography as a mechanism with potential to reduce the visualization of small structures when using UCT (Greenleaf et al. 1975, 1978). An illustration of the effects of refraction is presented in Fig. 14.2, where significant deviations from straight-ray path are shown when propagating through an object with only 10 % speed-of-sound contrast.
Refraction effects on wave front propagation through a cylinder with index of refraction \(n = 1/1.1.\) a Homogeneous medium b Cylinder, index of refraction \(n = 1/1.1\)
As a result, efforts were conducted in order to incorporate refraction effects in ray-based acoustic tomography. If the wavelength can be considered small compared to the size of the scatterer, the wavefront refraction can be explained using the eikonal equation in (14.4). Ray tracing methods allow for estimating the refracted paths that replace the straight lines assumed in Eq. (14.6).
Using the method of characteristics (Jakowatz and Kak 1976), the eikonal equation in Eq. (14.4) can be rewritten as a set of five ordinary differential equations given by
where \(p=\partial \tau / \partial x\), \(q=\partial \tau / \partial y\), and \(s\) is an auxiliary curve parameter. Only the first four equations in (14.11) are needed to obtain the ray path \((x(s), y(s))\) corresponding to transmitter location \((x_0, y_0)\) and starting ray direction \((p_0, q_0)\). Other approaches for ray tracing may be derived from different forms of the eikonal equation. For example, Johnson et al. (1975) performed ray tracing by solving the second-order differential form of the eikonal equation
Numerical recipes for the solution of Eqs. (14.11) and (14.12) can be found in (Andersen and Kak 1982; Andersen 1986).
For the problem of refraction-corrected tomography one is concerned with finding the actual bent path that connects a transmitter with a receiver, i.e., the ray linking problem (Andersen and Kak 1982; Norton 1987). Ray linking in the geophysical imaging community was traditionally performed using ray shooting and ray bending methods (Julian and Gubbins 1977), with the former being one of the earliest methods proposed for refraction-corrected tomography (Schomberg 1978; Lytle and Dines 1980). Ray shooting consists of solving the eikonal equation for a fixed transmitter position \((x_0, y_0)\) and different values of \((p_0, q_0)\) to find all rays that pass through the receiver location. If more than one ray is found, the solution is taken to be equal to the ray of minimum travel time between transmitter and receiver. Ray bending is based on Fermat’s principle,Footnote 1 which states that the ray that connects two points is the path of minimum travel time. Ray bending consists of perturbing an initial ray path joining the transmitter and receiver until a minimum time-of-flight criterion is met.
Ray linking approaches can be computationally expensive due to the need to calculate many ray paths for different transmitter/receiver pairs. Therefore, researchers sought alternative methods more efficient than classical ray linking (Andersen 1987). A particularly interesting class of algorithms consists of using graph theory methods to find the path of minimum travel time connecting transmitter/receiver pairs. Not only is this approach computationally efficient, but it also provides a global optimum solution and therefore avoids convergence problems of the shooting and bending methods (Moser 1991; Klimes and Kvasnicka 1994; Song and Zhang 1998; Li et al. 2010).
The main difficulty with reconstructing refraction-corrected acoustic tomograms is that in order to calculate the ray paths one has to know the spatial distribution of the index of refraction, which is the quantity that needs to be estimated. Therefore, the imaging problem becomes nonlinear with respect to the speed of sound distribution and more sophisticated methods than simple inverse Radon transforms need to be applied. Refraction-corrected approaches were applied since the early days of acoustic tomography by iteratively refining propagation paths based on the current estimate of the speed of sound distribution and the eikonal equation (Johnson et al. 1975; Schomberg 1978; Denis et al. 1995). Other researchers proposed methods based on modifying the measured data rather than the propagation paths (Norton and Linzer , 1982). Refraction-corrected paths were also proposed to reduce artifacts in acoustic attenuation reconstruction (Farrell 1981; Pan and Liu 1981).
2.3 Reflection Mode Tomography
Another variation of UCT is reflection mode tomography, which is based on using data collected in pulse-echo mode. Pulse-echo data \(p(t, \mathbf{{r}}_{tr})\) collected with the transducer at location \({\mathbf {r}}_{tr}\) can be modeled as (Jensen 1990)
where \(v_{pe}(t)\) is related to the pulse-echo wavelet generated by the transducer, \(h_{pe}(\mathbf{{r}}_{tr},\mathbf{{r}},t)\) is the pulse-echo spatial impulse response of the transducer and \(f_m(\mathbf {r})\) is the spatially varying reflectivity of the medium.Footnote 2
For point-like transducers and at large measurement distances such that \(|\mathbf{{r}}_{tr}| \gg |\mathbf{{r}}|\), \(h_{pe}(\mathbf{{r}}_{tr},\mathbf{{r}},t) \propto \delta (t-2|\mathbf{{r}}_{tr} - \mathbf{{r}}|/c_0)\). This allows Eq. (14.13) to be written as
Norton and Linzer (Norton and Linzer 1979a, b) proposed to collect pulse echo data in a circle of radius \(R\), i.e., \(\mathbf{{r}}_{tr} = (R\cos \theta , R\sin \theta )\) with \(\theta \in [0,2\pi ]\). It was proposed that images of \(f_m(\mathbf {r})\) could be generated by using the backpropagation operationFootnote 3
The formulation by Norton and Linzer assumes that propagation paths are straight lines. As discussed in Sect. 14.2.2, this will not be the case when propagating in inhomogeneous media. Bent ray paths derived from sound speed tomograms have been proposed to improve the backpropagation operation in Eq. (14.15) (Ashfaq and Ermert 2007; Schmidt et al. 2011; Koch et al. 2012).
2.4 Results and Limitations
Experimental imaging systems that utilize ray-based approaches to construct acoustic tomograms of sound speed and acoustic attenuation from tissues have been built over the decades. Several systems were built in the late 1970s and early 1980s to obtain clinical acoustic tomograms of human breasts (Glover 1977; Carson et al. 1981; Greenleaf and Bahn 1981; Schreiman et al. 1984). One example of a currently available system is CURE, developed at the Karmanos Cancer Institute (Duric et al. 2005). Both straight-ray (Duric et al. 2007) and refraction-corrected (Li et al. 2009) acoustic tomography have been implemented in this system. The CURE system provides images of speed of sound, attenuation, and reflectivity. Another example is the HUTT system, developed by researchers from the University of Southern California (Jeong et al. 2005, 2008, 2009). This system uses ray-based tomography to reconstruct images of attenuation coefficients at different frequencies. Image fusion methods are used to combine the different tomograms into 3D volumes for improved diagnostic capabilities. In laboratory environments, the 3D-USCT systems developed at the Karlsruhe Institute of Technology use transducers arranged in a 2D cylindrical aperture. Using ray-based theory, tomograms of sound speed and reflectivity have been constructed (Gemmeke and Ruiter 2007; Jirík et al. 2012).
Ray-based tomography has also been proposed to reconstruct images of parameters other than sound speed, acoustic attenuation and reflectivity. For example, Zhang et al. proposed to reconstruct tomograms of the acoustic nonlinear parameter from measurements of second harmonic amplitude (Zhang and Gong 1999) and nonlinear interaction of waves at two different frequencies (Zhang et al. 2001).
Diffraction tomography using plane wave illumination and point receivers. The plane wave travels in the direction of the unit vector \(\hat{s}_0\). The receivers are placed at locations \(\mathbf{{r}}_r\) over a line \(\eta = l_0\) perpendicular to \(\hat{s}_0\). The scattering object occupies the region of space \(\Omega \)
k-space coverage of first order Born diffraction tomography. Scattered field data are related to the 2D Fourier transform of \(O(\mathbf {r})\) at spatial frequencies \(k=k_0({\hat{s}} - {\hat{s}}_0)\). Using scattered field measurements at \(\eta = l_0\) (blue) and \(\eta = -l_0\) (red) provides samples over a full circle of radius \(k_0\) centered at \(-k_0{\hat{s}}_0\)
Despite its successful experimental implementation, ray-based ultrasonic tomography has usually been met with partial skepticism due to the simplified physical model used to reconstruct the acoustic tomograms. Refraction is a dominant mechanism when imaging large objects compared to the wavelength, but diffraction needs to be considered when the size of scattering structures are on the order of the wavelength. Simulation studies suggest that even after refraction correction, ray-based tomography can only produce quantitatively accurate reconstructions of structures that are larger than a few wavelengths (i.e., 2–5 wavelengths) (Quan and Huang 2007). This limitation has also been observed with experimental data (Leach Jr. et al. 2002). Therefore, attention shifted in the early 1980s to methods that provide sub-wavelength resolution by taking diffraction into account.
3 Diffraction Tomography
Although diffraction tomography was formally introduced to the acoustic imaging community by Mueller et al. in the late 1970s (Mueller et al. 1979, Mueller 1980), the theoretical foundation for diffraction tomography was available in the literature prior to the development of ray-based acoustic tomography. In his seminal work on optical imaging back in 1969 (Wolf 1969), Emil Wolf outlined a method to reconstruct three-dimensional distributions of refractive index using measurements of scattered data. For the case of constant density, the wave equation in (14.1) can be written as
where \(O(k, \mathbf{{r}}) = (k^2 - k_0^2)\) is the scattering potential function. Equation (14.16) can be written in terms of the Green’s function \(G_0(\mathbf {r})\) corresponding to \(k_0\) as
where \(p^{\text{sc}}(\mathbf{{r}})\) is the scattered pressure field, \(p^{\text{inc}}(\mathbf{{r}})\) is the incident pressure field caused by the sources \(\phi ^{ \text{inc}}(\mathbf{{r}})\), and \(\Omega \) is the region occupied by the object to be imaged.
3.1 The First-Order Born Approximation and the Fourier Diffraction Theorem
As in the case of refraction-corrected tomography, (14.17) is a nonlinear equation of the function \(O(k, \mathbf {r})\) to be imaged because \(p(\mathbf {r}^\prime )\) depends on the scattering potential function. In order to obtain a closed-form, tractable solution, Wolf (1969) invoked the first-order Born approximation to write Eq. (14.17) as
The results in Wolf (1969) were developed by Wolf using plane wave illumination and the plane wave decomposition of the 3D Green’s function. The derivation provided here corresponds to the 2D case depicted in Fig. 14.3 and is presented with more details in Kak and Slaney (2001). The plane wave travels in the direction of the unit vector \(\hat{s}_0\). The receivers are placed at locations \(\mathbf{{r}}_r\) over a line \(\eta = l_0\) perpendicular to \(\hat{s}_0\). Under the first order Born approximation, the scattered field at locations \(\mathbf{{r}}_r\) can be written as
where \(H_0^{(1)}(\cdot )\) is the zero-order Hankel function of the first kind. Using the plane wave decomposition of the Hankel function (Chew 1995) results in
where \(\beta = \sqrt{k_0^2 - \alpha ^2}\). Rearranging terms and using the fact that \(l_0>{{\eta }^\prime }\), \(\forall {\mathbf{{r}}^\prime } \in \Omega \) results in
where \(\bar{O}(k, \mathbf {u})\) is the 2D Fourier transform of \(O(k, \mathbf {r})\). From Eq. (14.21), the 1D spatial Fourier transform of \(p_{\text{ Born}}^{\text{sc}}(\xi , \phi _0)\) is given by
where \(\gamma = \sqrt{k_0^2 - \kappa ^2}\). From Eq. (14.23) one can observe that the 1D Fourier transform of the measured scattered pressure field is related to samples of the 2D Fourier transform of the scattering potential function (see Fig. 14.4). Further, these 2D Fourier samples lie along semi-circular arcs of radius \(k_0\) whose centers in turn lie on a circle of radius \(k_0\) centered at the origin of the 2D k-space. Therefore, by using different transmitter/receiver combinations one can sample a disk of radius \(\sqrt{2}k_0\) in 2D k-space. By placing additional receiver lines at \(\eta = -l_0\) one can readily measure in k-space full circles instead of semi-circular arcs per transmitted plane wave, effectively increasing the k-space coverage to a circle of radius \(2k_0\). This fundamental result is termed the Fourier diffraction theorem, and was quickly acknowledged to be a generalization of the Fourier slice theorem (that applies to non-diffracting tomographic imaging) to the case of imaging with diffracting sources. One can also show that for a circular array of receivers with large radius such that measurements are collected in the far field, the actual values of \(p_{\text{ Born}}^{\text{sc}}(\mathbf{{r}}_r)\) are proportional to \(\bar{O}(k, k_0[\hat{r}_r - \hat{s}_0])\) with \(\hat{r}_r\) the unit vector in the direction of \(\mathbf{{r}}_r\) (Naidu et al. 1995).
3.2 The First-Order Rytov Approximation
The first-order Born approximation is not the only way to linearize the wave equation. In particular, the first-order Rytov approximation was also applied to obtain analytical solutions to the wave inversion problem (Iwata and Nagata 1975; Devaney 1981; Kak and Slaney 2001). If the total pressure field is written as \(p(\mathbf{{r}})=\exp (\varPhi (\mathbf{{r}}))\), then Eq. (14.3) can be written as
Further, if the total complex phase is rewritten as \( \varPhi (\mathbf{{r}})={\varPhi ^{inc}}(\mathbf{{r}}) + \varPhi ^\Delta (\mathbf{{r}}) \) with \( {p^{inc}}(\mathbf{{r}}) = \exp (\varPhi ^{\text{inc}}(\mathbf{{r}}))\), Eq. (14.24) can be written as
Using the fact that \(\nabla ^2p^{\text{inc}}(\mathbf{{r}})={-k_0^2}{p^{\text{inc}}}(\mathbf{{r}})\), it can be shown that
Combining Eqs. (14.25) and (14.26) results in
Equation (14.27) can be written in integral form as
Up to this point, no simplifications have been made. If \(O(k, \mathbf{{r}}) \gg |\nabla \varPhi (\mathbf{{r}})|^2\), then the complex excess phase can be approximated as
Equation (14.29) implies that the Fourier diffraction theorem can also be used to reconstruct tomograms from measurements of the pressure field phase. Therefore, diffraction tomography under either the first-order Born or Rytov approximations can be used to reconstruct images of sound speed and acoustic attenuation by mapping measurements of scattered fields to k-space samples of the scattering potential function.
3.3 Multi-Frequency Diffraction Tomography
In order to reconstruct an \(N\)-dimensional object, \(N\) degrees of freedom in the measurements are needed. Conventional diffraction tomography exploits three degrees of freedom (i.e., transmitter position and two angular orientations between transmitter and receivers) to reconstruct 3D imaging targets. However, frequency diversity can also be exploited as a degree of freedom. For a fixed transmitter/receiver pair location, changing the angular frequency of the incident field will provide a different sample of the scattering potential function in k-space. This was exploited by Kenue and Greenleaf (1982) in order to increase k-space coverage when a limited number of transmitter/receiver locations is allowed. Other researchers exploited frequency diversity more aggressively by using bistatic scanning configurations (i.e., a fixed angular separation between transmitter and receiver) with broadband transducers (Norton 1983).
3.4 Frequency-Domain Interpolation Methods
Diffraction tomography under the Born and Rytov approximations provided an elegant solution to the wave inversion problem. The most direct approach for reconstructing tomograms under first order scattering assumptions is to use the Fourier diffraction theorem to obtain samples of the 2D Fourier transform of the scattering potential function. In order to reconstruct images of the scattering potential function on a Cartesian grid, samples of \(\bar{O}(k, \mathbf {u})\) distributed on a Cartesian grid in k-space are needed. Therefore, the use of interpolation methods is required given that measurements of scattered fields provide Fourier samples in circular arcs as described in Sect. 14.3.1. Frequency-domain interpolation was one of the first algorithms proposed for acoustic diffraction tomography (Mueller et al. 1979). Pan and Kak reported that good results in terms of reconstruction quality can be obtained by using bilinear interpolation after increasing sampling density using zero-padding (Pan and Kak 1983). The unified Fourier reconstruction (UFR) method performs the frequency-domain interpolation exploiting the limited spatial support of the scattering potential function (Kaveh et al. 1984; Soumekh 1988).
3.5 The Filtered Backprojection Method
The filtered backpropagation algorithm was proposed by Devaney as the analogous of filtered backprojection when imaging with diffracting sources (Devaney 1982). Consider the case depicted in Fig. 14.3. From the results in Sect. 14.3.1, the scattering potential function can be reconstructed from its Fourier components using
where \(O^{\text{ bp }}(\mathbf{{r}}) = -O(k,\mathbf{{r}})/k_0^2\) and \(\bar{O}^{\text{ bp }}\) is the spatial Fourier transform of \(O^{\text{ bp }}\). Introducing \(\chi \) such that \(\hat{s} = \left( \cos \chi , \sin \chi \right) \), Eq. (14.30) can be rewritten as
The integral in \(\chi \) can be written in terms of \(\kappa \) by noticing that in the \({\hat{\xi }} - {\hat{\eta }}\) frame, \(\cos \chi = \kappa /k_0\) (\(\kappa \in [-k_0, k_0]\)) and \(\phi _0 = \pi /2\). As a result,
Using the Fourier diffraction theorem in (14.23), Eq. (14.33) can be written as
According to Eq. (14.34), the scattering potential function can be reconstructed using a modified filtered backprojection algorithm. The modification consists of including an additional filter \(\bar{G}(\kappa , \eta )\) prior to backpropagating the measured scattered pressure data. Also, the angular integration uses angles in [\(-\pi , \pi \)] as opposed to [0, \(\pi \)] in Eq. (14.9).
The need for depth-dependent filtering causes the filtered backpropagation method to be more computationally expensive than its filtered backprojection counterpart. Further, early studies found that Fourier interpolation methods were able to produce images of comparable quality but reduced computational cost when compared to filtered backpropagation (Pan and Kak 1983). In order to reduce the computational cost of the method, Devaney proposed an approximate solution that consisted of replacing the backpropagation filter \(\bar{G}(\kappa , \eta )\) with \(\bar{G}(\kappa , \eta _0 = x_0\cos {\phi _0} + y_0\sin {\phi _0})\), where \((x_0, y_0)\) are the coordinates of the center of the region where good image quality is desired (Devaney 1983). Therefore, the modified filtered backpropagation method enables a reduction of computational cost at the expense of image quality.
Other variations of the filtered backpropagation method were later developed. In particular, the hybrid filtered backpropagation method by Sponheim et al. preserved the essence of the original filtered backpropagation method while allowing the use of data from a circular array of receivers and better handling Rytov data for image reconstruction (Sponheim et al. 1991, 1994).
3.6 Algebraic Reconstruction Methods
Diffraction tomography as described in Sect. 14.3.1 was developed assuming plane wave illumination and receivers arranged in a straight line. These are very restrictive conditions, and therefore algorithms were later developed to handle more complex incident fields and receiver apertures (Devaney and Beylkin 1984; Devaney 1985; Gelius et al. 1991; Anastasio and Pan 2003). A particular approach to handle more general imaging configurations consisted of casting the linearized wave equation in (14.18) as a matrix equation. This approach allows the use of algebraic methods to solve the diffraction tomography problem (Devaney 1986; Ladas and Devaney 1991). An additional benefit of using algebraic methods is the possibility of incorporating a priori information about the scattering potential function during the reconstruction process. These approaches are usually simplified versions of methods for the inversion of the full integral wave equation, which will be discussed in Sect. 14.4.
3.7 Advantages and Limitations
The most significant advantage of diffraction tomography is its spatial resolution. If the scattered pressure is measured with full angular coverage on reception (i.e., transmitters and receivers distributed over a fully enclosed surface) the k-space can be fully covered within a sphere of radius \(2k_0\). Therefore, the achievable spatial resolution is approximately \(\lambda /2\) and as a result diffraction tomography is expected to produce tomograms with better spatial resolution than ray-based acoustic tomography. Diffraction tomography methods were also developed to reconstruct images of parameters other than sound speed and acoustic attenuation. Examples include density imaging (Devaney 1985; Moghaddam and Chew 1993; Mensah and Lefebvre 1997; Anastasio et al. 2005) and acoustic nonlinear parameter (Kai et al. 1992).
However, the main limitation of diffraction tomography is its convergence properties. Given that diffraction tomography is based on approximate expressions of the full wave equation, it is expected to provide accurate quantitative images only under weakly scattering conditions. The convergence of diffraction tomography was analyzed in detail in the early 1980s (Slaney et al. 1984; Robinson and Greenleaf 1986). Different convergence behavior was found depending on whether the first order Born or Rytov approximations were used to linearize the wave equation.
For the first order Born approximation it is required that \(\left| p^{\text{sc}}\right| \ll \left| p^{\text{inc}}\right| \) within the imaging target. A somewhat equivalent condition was adopted by Slaney et al. (Slaney et al. 1984) regarding the quantity \(\Delta \phi \), which represents the maximum phase change that the incident field suffers when propagating through an inhomogeneity. Slaney et al. found through simulations that diffraction tomography based on the first order Born approximation breaks down as \(|\Delta \phi |\rightarrow 0.8\pi \). This bound was consistent with the expectation of the first order Born approximation breaking down for \(|\Delta \phi | \ge \pi \) (Iwata and Nagata 1975; Slaney et al. 1984). An example of the degradation of reconstruction quality with increasing \(\Delta \phi \) values is given in Fig. 14.5.
Diffraction tomography under the first order Born approximation. The imaging targets are circular cylinders of radius 5\(\lambda \) and \(\Delta \phi \) values of (a) 0.25\(\pi \), (b) 0.5\(\pi \), (c) \(\pi \), and (d) 2\(\pi \). Radial profiles corresponding to the ideal (solid lines) and reconstructed (dash lines) sound speed images are shown
The first order Rytov approximation is derived under the assumption that \(|\nabla \varPhi |^2\ll k_0^2 \max (c/c_0 - 1)\) (Slaney et al. 1984; Tsihrintzis and Devaney 2000). Unlike the Born approximation, the Rytov approximation imposes no restriction on the size of the scatterer, and therefore it is usually valid for a wider class of imaging targets. However, inversions using the Rytov approximation suffer from phase wrapping problems caused when estimating \(\varPhi \) from measurements of the scattered pressure data. Tomograms obtained with the Rytov approximation are usually of better quality than the ones obtained with the Born approximation, but phase wrapping causes a sudden and catastrophic failure in the inversion (Slaney et al. 1984; Robinson and Greenleaf 1986). Phase unwrapping algorithms have been proposed in order to improve the performance of Rytov-based methods (Kaveh et al. 1984; Wedberg and Stamnes 1995) but only with limited success.
Therefore, just like for the case of ray-based acoustic tomography, diffraction tomography is better suited for imaging regions composed exclusively by soft tissues. However, unlike the case of ray-based tomography, non-convergence of diffraction tomography may lead to unusable tomograms due to the distortion of the underlying structures in the image (Robinson and Greenleaf 1986).
Several researchers have studied methods to extend the region of convergence of diffraction tomography. A particular approach is to use a non-uniform background that accounts for large structures of the imaging target when linearizing the wave equation. If both the incident field and Green’s function can be calculated for such a background, then diffraction tomography can be used to image the fine details of the object. A gross estimate of the scattering potential function can be obtained from ray-based tomography. In order to retain the mathematical simplicity of diffraction tomography, researchers have proposed to modify both the free-space incident field and Green’s function by using time delays that model the time-of-flight difference between the homogeneous and inhomogeneous backgrounds. This approach has been explored with the delays calculated using straight and refracted ray theory, and interesting results can be found in the literature (Gelius et al. 1991; Mast 1999; Astheimer and Waag 2008).
However, the limitations of diffraction tomography caused the attention of the research community to shift towards approaches that invert the full wave equation and therefore account for refraction, diffraction, and multiple scattering.
4 Full Wave Inversion Methods
The pioneering studies on full acoustic wave inversion were conducted almost simultaneously with the development of ultrasonic diffraction tomography. It was during the early 1980s that initial reports of methods designed to invert the wave equation were reported. These methods have a much higher computational cost than diffraction tomography approaches, and were therefore not widely explored until continued reports of the limitations of single-scattering tomography were made available.
4.1 The Alternating Variables Method
Diffraction tomography under the first-order Born approximation will fail if the condition \(p(\mathbf{{r}}) \approx p^{\text{inc}}(\mathbf{{r}})\) is not met. If one were to exactly know the total pressure field \(p(\mathbf{{r}})\) inside the imaging target, then the Born approximation would not be needed and the scattering potential function could be determined. In a seminal series of articles (Johnson and Tracy 1983; Tracy and Johnson 1993), Johnson et al. (1984) provided full details on an algorithm designed for the simultaneous estimation of \(p(\mathbf{{r}})\) and \(O(k, \mathbf{{r}})\). This method is known as the alternating variables algorithm, and is also known as the iterative Born method in the microwave imaging community (Wang and Chew 1989).
To illustrate the alternating variables method, it is convenient to express the integral wave equation (14.17) in operator notation as
in which the total and incident pressures are explicit functions of \(\mathbf{{r}}_t\in \Omega _t\) for some set \(\Omega _t\) characterizing a variety of incident fields. Equation (14.37) is called the forward problem, and solutions to the forward problem for distinct sources corresponding to unique points \(\mathbf{{r}}_t\) are independent. The operator \(\mathcal G \) characterizes interactions among points within the scattering domain \(\Omega \) and, in practice, is usually well conditioned.
For a known total field \(p(\mathbf{{r}},\mathbf{{r}}_t)\), the scattered field observed at some observation location \(\mathbf{{r}}_r\in \Omega _r\) may be written
The operator \(\mathcal G _r\) maps the total field within the domain \(\Omega \) to an observed scattered field within the set \(\Omega _r\). \(\mathcal G _r\) may be inverted to compute the scattering potential \(O\) if the total pressure \(p\) within \(\Omega \) is known. Unlike in the forward problem, the inverse problem is ill-posed and is rarely well determined. A generalized solution to the inverse problem (14.38) is given by
The alternating variables algorithm consists of iterating through the following steps: (1) calculate the total field \(p\) using Eq. (14.37) and an estimate of \(O\), (2) calculate \(O\) using Eq. (14.39) and the current estimate of \(p\), and (3) repeat steps (1)–(2) until \(O\) does not change significantly between consecutive iterations.
4.1.1 Variable Density Case
Consider the wave equation in (14.1). By applying the change of variables \(p(\mathbf{{r}}) = f(\mathbf{{r}}) \rho ^{1/2}(\mathbf{{r}})\) (Johnson et al. 1982; Pourjavid and Tretiak 1992), Eq. (14.1) can be rewritten in integral form as
where \(O_\rho (k,\mathbf {r})\) is given by
By comparing Eqs. (14.17) and (14.40), it is clear the only difference between the constant and variable density cases is the form of the scattering potential function. Therefore, the alternating variables algorithm can be used to reconstruct tomograms of \(O_\rho (k,\mathbf {r})\). If one assumes a non-dispersive medium for which \(\left( k^2(\mathbf {r}) - k_0^2 \right) \) scales as \(\omega ^2\), the term \(\mathcal F _{\rho } = \rho ^{1/2}(\mathbf {r}) \nabla ^2 \rho ^{-1/2}(\mathbf {r})\) can be isolated from the algebraic combination of reconstructions of \(O_\rho (k,\mathbf {r})\) at two or more frequencies.Footnote 4 Density tomograms can be constructed by solving the differential equation
with \(u(\mathbf{{r}}) = \left( \rho _r^{-1/2}(\mathbf{{r}}) - 1\right) \). This approach for density imaging using the alternating variables algorithm was proposed in (Berggren et al. 1986).
4.1.2 Convergence
This algorithm was extensively studied by Cavicchi et al. in the late 1980s. Initial results showed that the alternating variables algorithm could provide improved results in terms of reconstruction error when compared to diffraction tomography based on the first-order Born approximation (Cavicchi et al. 1988). However, it was found that the alternating variables algorithm suffered from divergence when \(\left| \Delta \phi \right| \ge \pi \) (Cavicchi and O’Brien, Jr. 1989), which is only marginally better than the \(\left| \Delta \phi \right| \rightarrow 0.8\pi \) condition found for first-order Born diffraction tomography in (Slaney et al. 1984).
4.2 Newton-Type Methods
The shortcomings of the alternating variables approach are caused by the nonlinearity of the inverse problem as a function of the total pressure. The solution to the wave equation is unique, but inverse scattering is generally ill-posed (Colton et al. 2000). The ill-posed nature of the acoustic tomography problem becomes more problematic for moderate to large complex wave number contrast with respect to the background. Therefore, the key to improving the convergence of the inverse scattering problem is to update not only the scattering potential function and total pressure field, but also the background and its corresponding Green’s function.
Iterative updates of a background contrast profile were explored for electromagnetic inverse scattering by Chew and Wang (1990) and the approach was termed the distorted Born iterative method (DBIM). For acoustic tomography, Borup et al. (Borup et al. 1992) independently developed an inversion method based on Newton-type iterations. Both the distorted Born and Newton-type approaches have been found to be exactly equivalent (Remis and van den Berg 2000). Due to its more intuitive nature, the DBIM approach will be presented here.
Although a homogeneous background \(k_0\) was used to write the integral wave equation in Sect. 14.3.1, one can use any inhomogeneous function \(k_b(\mathbf{{r}})\) to characterize the acoustic background. Therefore, the integral wave equation can be written
where \(p(\mathbf{{r}},\mathbf{{r}}_t,k)\) is the total pressure field produced by a source characterized by \(\mathbf{{r}}_t\) in a medium with wave number \(k\), \(\Delta O(\mathbf{{r}}) = O(k, \mathbf{{r}}) - O(k_b, \mathbf{{r}})\), and \(G_b\) is an inhomogeneous Green’s function that characterizes the response of a point source in the presence of the background. A first-order Born approximation can be applied to linearize Eq. (14.43), which yields
in which \(p^{\text{sc}}(\mathbf{{r}},\mathbf{{r}}_t,k) = p(\mathbf{{r}},\mathbf{{r}}_t,k) - p^{\text{inc}}(\mathbf{{r}},\mathbf{{r}}_t)\) is the scattered field relative to a homogeneous background with wave number \(k_0\). This approach has been termed the distorted-wave Born approximation (Devaney and Oristaglio 1983) and was proposed as a tool for introducing prior knowledge about the scattering strength function into diffraction tomography.
Just as with Eq. (14.38), it is possible to invert Eq. (14.44) to obtain \(\Delta O\) provided that the total field \(p\) is known throughout \(\Omega \). Because \(p^{\text{sc}}\) and, therefore, \(\Delta p^{\text{sc}}\) are generally observed on a set \(\Omega _r\) that is distinct from \(\Omega \), a generalized solution
must be sought. The DBIM consists of iterating through the following steps: (1) calculate \(p\) using Eq. (14.37) and a current estimate of \(k_b\), (2) calculate the scattered field corresponding to \(k_b\) using Eq. (14.38), (3) compute \(\Delta p^{\text{sc}}\) by subtracting the measured scattered field from the result of step (2), (4) estimate \(\Delta O\) using Eq. (14.45), (5) update \(k_b \leftarrow k_b + \Delta O\), (6) repeat steps (1)–(5) until the \(L^2\) norm of \(\Delta O\) drops below a specified threshold, (7) set \(k=k_{b}.\)
(a) Experimental DBIM reconstructions of a balloon phantom containing a saline solution. In the frequency-hopping reconstruction, both \(0.64\)- and \(1.2\)-MHz data were used to produce an image ((b) reconstruction using 0.64-MHz data only, (c) reconstruction using 1.2-MHz data only, and (d) reconstruction using 0.64-MHz data initially followed by 1.2-MHz data). Results show the actual profile of the model and reconstructions using both ideal (computed) and measured data. Adapted from Lavarello and Oelze (2008)
Given a background \(k_b\), it is possible to numerically compute the Green’s function \(G_b\) and, therefore, the operator \(\mathcal G _b\). However, it is often preferable to avoid explicit construction of the Green’s operator \(\mathcal G _b\) in favor of a representation that describes the DBIM in terms of solutions of homogeneous, rather than inhomogeneous, scattering problems. From Eq. (14.44), is is possible to represent the inverse problem in the form (Borup et al. 1992)
where \(\mathcal{F }\) is the Fréchet derivative of the scattering operator \(\mathcal G _r\) in Eq. (14.38) (Ghosh Roy et al. 2007). For iterative solutions of Eq. (14.46), it is not required to explicitly invert \(\mathcal{F }\), but rather to repeatedly compute products of \(\mathcal{F }\) (and, generally, \(\mathcal{F }^{\dagger }\)) with test solutions. The product of \(\mathcal{F }\) with some test solution \(\Delta O\) can be shown to be equivalent to (Hesford and Chew 2010)
where \(p = p(\mathbf{{r}},\mathbf{{r}}_t,k_b)\) and \(O= O(k_b,\mathbf{{r}})\) correspond to the background medium with wave number \(k_b\) and \(\mathcal G _r\) and \(\mathcal G \) are the free-space Green’s operators in Eqs. (14.37) and (14.38), respectively. Similarly, the adjoint Fréchet derivative product is equivalent to
in which \((\cdot )^{*}\) denotes complex conjugation. Therefore, it is possible to invert Eq. (14.46) without explicit knowledge of an inhomogeneous background Green’s function \(G_b\). This operation can be made efficient provided that solutions of the forward problem, represented by the operators \((1 - \mathcal G )^{-1}\) and \((1 - \mathcal G O)^{-1}\), and products of the operators \(\mathcal G \) and \(\mathcal G _r\) can be computed efficiently. This topic will be discussed more thoroughly in Sect. 14.5.
4.2.1 Convergence and Frequency-Hopping Approach
The DBIM also suffers from divergence if the initial guess is far from the true solution such that approximately \(\left| \Delta \phi (k) - \Delta \phi (k_b^0)\right| >\pi \), where \(\Delta \phi (k)\) and \(\Delta \phi (k_b^0)\) are the maximum excess phases for the true and initial guess wave number profiles. However, this condition is less restrictive than the condition corresponding to the alternating variables algorithm. Therefore, the DBIM can provide an extended convergence region if a good initial guess is available. The simplest scheme is the frequency-hopping approach, i.e., the sequential use of multiple frequency data, processing first the low frequency data to achieve convergence and then the high frequency data to refine the spatial resolution of the resulting tomograms (Kim et al. 1987; Borup et al. 1992; Chew and Lin 1995; Haddadin and Ebbini 1998; Lavarello and Oelze 2008). An example taken from (Lavarello and Oelze 2008) is shown in Fig. 14.6, where DBIM and frequency hopping were used to reconstruct the cross-section of a cylindrical rubber balloon filled with a saline solution.Footnote 5 The low frequency (0.64 MHz, \(\Delta \phi = 0.85 \pi \)) data reconstruction exhibits limited spatial resolution, whereas the high frequency (1.2 MHz, \(\Delta \phi = 1.6 \pi \)) reconstruction diverged from the expected sound speed profile. The use of frequency hopping resulted in a convergent sound speed tomogram with improved resolution with respect to the low frequency reconstruction.
4.3 Conjugate Gradient Methods
An alternative way to invert the full wave equation is to use conjugate gradient approaches. This approach was studied in the early 1990s by researchers in the electromagnetics community (Kleinman and van den Berg 1992; Harada et al. 1995; Lobel et al. 1997). Conjugate gradient approaches have been used in UCT as well. Zhang et al. studied the performance of different methods to estimate the conjugate gradient directions (Zhang et al. 2004) as well as regularization methods for improved robustness (Zhang et al. 2002). Wiskin et al. (2007) have successfully demonstrated the application of the conjugate gradient method for obtaining clinical ultrasonic tomograms.
The conjugate gradient method consists of iterating through the equations
where \(\bar{O}\) and \(\bar{g}\) are vector representations of the scattering potential function and the Fréchet derivative of the residual minimized in Eq. (14.39), respectively,Footnote 6 \(\bar{d}\) is a vector pointing in the search direction, and \(\alpha \) and \(\beta \) are scalar parameters. Numerical methods for calculating \(\bar{d}\), \(\alpha \) and \(\beta \) are discussed in (Wiskin et al. 2007).
A notable variation of the conjugate gradient method is the contrast source inversion (CSI) method, developed by van den Berg and Kleinman (van den Berg and Kleinman 1997). The residual \(R\) to be minimized in the CSI approach is given by
where \(w = Op\) and \(w^{\text{inc}} = Op^{\text{inc}}\). More recent versions of the technique, such as the multiplicative regularized contrast source inversion method (van den Berg et al. 1999; Pelekanos et al. 2003), added further robustness to the original CSI formulation.
4.4 Kaczmarz-Like Inverse Scattering
In the early days of X-ray tomography, algebraic methods were also studied for constructing tomograms. Even though the X-ray CT imaging problem is linear, the limited computing resources available at the time made it necessary to use iterative methods for matrix inversion. The algebraic reconstruction technique (ART) (Gordon 1974), one of the most celebrated iterative methods for the inversion of the Radon transform, is based on Kaczmarz’s method. In short, Kaczmarz’s method successively refines a current estimate of the solution by performing orthogonal projections on the hyper-planes corresponding to the equations given by each row of the matrix operator. If the system \(\mathbf{R } \cdot \bar{\mathbf{f }} = \bar{\mathbf{g }}\) is to be inverted, starting from an initial guess \(\bar{\mathbf{f }}_{{0}}\) an updated solution \(\bar{\mathbf{x }}_{(n)}\) is calculated as
where \(\bar{\mathbf{g }}_m\) and \(\mathbf{R }_m\) are the \(m\)-th entry of the measurement vector \(\bar{\mathbf{g }}\) and the \(m\)-th row of the matrix \(\mathbf{R }\), respectively, and \(\beta \) is a relaxation factor. This is a row-action method because only one row of the matrix equation is used at a time. Similar methods for inverse scattering that avoid constructing the Fréchet derivative matrix are therefore of potential benefit for ultrasonic tomography.
4.4.1 The Propagation-Backpropagation Method
Natterer and Wübbeling (Natterer and Wübbeling 1995) proposed in 1995 a method for inverse scattering that updated the scattering potential function using scattered data from one transmission at a time. In essence, the method is a non-linear version of Kaczmarz’s method. The imaging configuration corresponds to Fig. 14.3, with the incident plane wave propagating with different direction vectors \({\mathbf {\theta}}_m = (\cos \theta _m, \sin \theta _m)\). The wave equation in (14.2) is written in the form
From Eq. (14.54) it can be derived that the scaled scattered field \(v_{\theta _m}\) for the \(m\)-th transmission satisfies
for points inside the computational domain. In operator form, Eq. (14.55) can be written as \(R_m(f) = g_m\), where \(g_m = v_{\theta _m}\) at the receiver locations \({\mathbf {r}}_r\). This equation indirectly represents the scattered pressure field as a nonlinear transformation of the scattering potential function. The proposed algorithm, termed the propagation-backpropagation method, consists of updating \(f\) as
where \(R_m^{\prime }(f)\) is the derivative of the operator \(R_m(f)\), \(R_m^{\prime }(f)^*\) is the adjoint of \(R_m^{\prime }(f)\), and \(C_m = R_m^{\prime }(f) R_m^{\prime }(f)^*\).Footnote 7
The operator \(C_m\) can be simplified considering the limit \(k_0 \rightarrow \infty \) for which \(C_m \rightarrow R_m^{\prime }(0) R_m^{\prime }(0)^* = k_0^2/\rho \mathbf{I }\) and \(\rho \) is the radius of the reconstructed region (Natterer 1997). In order to calculate the updates, \(R_m^{\prime }(f)^*g\) needs to be calculated. This is performed indirectly by using the relationship
where \(z\) satisfies the differential equation
The boundary conditions for both Eqs. (14.55) and (14.58) are given in (Natterer and Wübbeling 1995). As a result, this method allows reconstruction of the scattering potential function by successively solving two initial-value problems. Both (14.55) and (14.58) were solved using five-point finite difference marching schemes. A key detail of the actual marching implementations is that in order for the recursion to be stable the condition \(h \ge \pi /k_0 \sqrt{1-f}\) has to be met, with \(h\) the discretization step. Therefore, Natterer and Wübbeling suggested filtering high spatial frequency components after each step of the iteration.
Finally, the propagation-backpropagation method has been reported to converge as long as the initial guess \(f_0\) satisfies the heuristic rule \(|\int ds\, (f-f_0)|\le \lambda\) (Natterer 2008). For low sound speed contrasts \(\Delta c_r = |c - c_0|/c_0\), i.e., \(\Delta c_r \ll 1\), this convergence rule is equivalent to the one provided for DBIM in Sect. 14.4.2.
4.4.2 Kaczmarz-Like DBIM
The fundamental principals of the propagation-backpropagation method can also be applied to the DBIM to yield a Kaczmarz-like, round-robin scheme (Hesford and Chew 2010). Rather than attempt to invert the entire Fréchet derivative to arrive at an update to the background contrast, the round-robin scheme considers only the portion of the Fréchet derivative constrained to a limited number of source positions. The constrained Fréchet derivative problem will be severely underdetermined. In this case, the problem must be solved in the minimum-norm sense by forcing the solution to exist in the adjoint space of the Fréchet derivative. Unlike the propagation-backpropagation method, the round-robin DBIM does not require planar incident fields. Furthermore, the round-robin technique is readily incorporated into existing DBIM solvers without requiring a reformulation of the wave equation.
In analogy with frequency hopping, the round-robin technique attempts to avoid local minima associated with the solution of a single, restricted inverse problem (e.g., involving a single imaging frequency and a limited set of transmit angles) by using a previously obtained solution as a starting guess for a subsequent inversion. If local minima associated with distinct transmit angles do not coincide, a solution stagnating in a local minimum for one transmit angle may move away from the local minimum and toward the global minimum when the transmit angle is shifted.
4.5 Eigenfunction Methods
Eigenfunction methods for inverse scattering (Mast et al. 1997; Lin et al. 2000; Waag et al. 2007) rely on eigenfunctions of the far-field operator
where \(C\) is an arbitrary constant, \(k_0\) is the wave number of a homogeneous background material, \(\hat{s}_R\) and \(\hat{s}_T\) are points on the \(d\)-dimensional unit sphere \(\Omega \), \(\mathbf{{r}}_R = r\hat{s}_R\), and the scattered pressure \(p_s\) is expressed as a function of the observation point \(\mathbf{{r}}_R\) and the direction \(\hat{s}_T\) of an incident plane wave. Thus, the far-field operator relates the angle \(\hat{s}_T\) of an incident plane wave to the far-field scattering behavior observed at an angle \(\hat{s}_R\).
For arbitrary focusing functions \(\varphi _i\) and \(\varphi _j\), a measurement is defined as
in which \((\cdot )^{*}\) represents complex conjugation. In the presence of an assumed background with wave number \(k_b(\mathbf{{r}})\) and corresponding contrast profile \(O_b\), the eigenfunction method is concerned with solving the differential far-field scattering problem (Waag et al. 2007)
for a differential update \(\Delta O\), where the far-field operator \(A_{b}\) corresponds to the scattering behavior of \(O_b\) relative to the homogeneous background \(k_0\) and the far-field operator \(A_{\Delta }\) corresponds to the scattering behavior of the unknown contrast \(\Delta O\) relative to \(O_b\). The problem is regularized to ensure a unique solution by minimizing
where \(V\) contains the support of \(\Delta O\), for a suitable weighting function \(W_R\).
The unknown far-field operator \(A_{\Delta }\) may be written as
in which \(p\) is the acoustic pressure at a point \(\mathbf{{r}}\) due to a plane wave incident from an angle \(\hat{s}_T\) and \(G_b^f\) is a far-field representation of the Green’s function corresponding to the background \(O_b\) and is, in analogy with Eq. (14.59), given by
Thus, Eqs. (14.43) and (14.63) are equivalent when the former is restricted to incident plane waves and far-field observations.
The differential scattering operation Eq. (14.43) that forms the basis of the distorted Born iterative method may be generalized to transmission focusing with an envelope function \(\alpha \) and receive focusing with an envelope function \(\beta \) by writing
where the total acoustic pressure \(p\) is now expressed as an explicit function of the source corresponding to a position \(\mathbf{{r}}_T\) in some transmission domain \(T\) and the point \(\mathbf{{r}}\) now exists in some measurement domain \(R\). In the far-field limit, \(G_b\rightarrow G_b^f\), \(R = \Omega \) and \(\mathbf{{r}}\mapsto \hat{s}_R\). If only plane-wave incidence is considered, then \(T = \Omega \) and \(\mathbf{{r}}_T\mapsto \hat{s}_T\). When \(\alpha = \varphi _i\) and \(\beta (\hat{s}) = \varphi _j^{*}(-\hat{s})\), Eqs. (14.61) and (14.65) are equivalent. The eigenfunction method employs a distorted Born approximation to linearize Eq. (14.61); therefore, the eigenfunction method is mathematically equivalent to a DBIM that employs focused plane-wave transmissions and focused far-field measurements.
The eigenfunction method is so named because artificial focusing envelopes \(\varphi _i\) and \(\varphi _j\) are chosen to be eigenfunctions of the measured scattering operator \(A\). These eigenfunctions concentrate energy within the support of the contrast function. When coupled with an explicit representation of the inverse scattering solution using Lagrange multipliers, the advantage of this choice of focusing profiles is a reconstruction that uses minimal unnecessary information (Mast et al. 1997).
Because the operator \(A\) characterizes far-field scattering of incident plane waves, focused transmissions or receptions are not directly applicable to the eigenfunction method. Instead, focused measurements would need to be suitably transformed into the required far-field operator, or the method would need to be reformulated to directly incorporate focusing. Such modifications to the eigenfunction method have not been described in the literature.
4.6 The T-matrix Formulation
The methods described so far are designed to reconstruct a single functional that depends on the complex wave number function. From this functional, sound speed and attenuation tomograms can be obtained. As described in Sect. 14.4.1.1, the functional can be made dependent on density variations with a proper change of variables. Although density tomograms can be reconstructed with this approach and the use of DBIM (Kwon and Jeong 1998; Lavarello and Oelze 2010; Lavarello et al. 2010), the solution of Eq. (14.42) can cause instabilities in the presence of noise. Alternatively, methods have been designed to natively take both compressibility and density variations into account when inverting the wave equation (van Dongen and Wright 2007).
One of these methods is the T-matrix formulation, presented by Lin and Chew in Lin and Chew (1996). Unlike the methods considered so far in Sect. 14.4 that directly use the wave equation in continuous differential or integral form, the T-matrix formulation is based on the harmonic expansion of the acoustic pressure field. Consider the case of a harmonic acoustic wave incident on an object. The computational domain is divided into \(N\) homogeneous subscatterers distributed on a rectangular grid of pixel size \(h\). The total acoustic field produced at some point \({\mathbf {r}}_p\) in space is given by
where \({\mathbf {r}}_s\) is the location of the source, \({\mathbf {r}}_m\) is the location of the \(m\)-th subscatterer, \(\psi (\mathbf {r})\) is a vector whose elements are cylindrical harmonics, i.e.,
and \(\bar{f}_s\) and \(\bar{a}_m\) are vectors containing the amplitudes of the cylindrical harmonic fields generated by the source and the \(m\)-th subscatterer, respectively.
The equation above can be rewritten using the \(j\)-th subscatterer as the spatial origin for all the cylindrical harmonics. Using the vector \(\hat{\psi }(\mathbf{{r}})\) whose elements are defined as \(\left[ \hat{\psi }(\mathbf{{r}})\right] _k\,=\, J_k(k_0|\mathbf{{r}}|)e^{il\angle \mathbf{{r}}}\), Eq. (14.66) can be rewritten as
where the elements of matrix \(\alpha _{jm}\) and vector \(\bar{e}_{js}\) can be obtained using the addition theorem of Bessel functions (Chew 1995) as detailed in Lin and Chew (1996).
If \(h \ll \lambda \), the coefficient that relates the amplitude of the source waves \(J_k(\mathbf {r})\) with the outgoing waves \(H_k^{(1)}(\mathbf {r})\) in Eq. (14.68) can be approximated by the scattering coefficient \(R_k(\kappa _j,\rho _j)\) by a sphere of radius \(h/\sqrt{\pi }\), where \(\kappa _j\) and \(\rho _j\) are the compressibility and density of the \(j\)-th subscatterer, respectively. Further, under the same condition \(h \ll \lambda \) the harmonics \(l=0,1,-1\) have been reported to be sufficient to characterize the scattering process (Lin and Chew 1996). Consequently, and considering Eq. (14.68) at all subscatterer locations \(\mathbf {r}_j\), \(j = 1, 2, \cdots N\), the \(N \times 1\) vectors of equivalent induced sources \(\bar{a}^s_{k}\) whose elements are given by \(\bar{a}_m\) satisfy the equation
with \(\bar{R}_{k}\) an \(N \times 1\) vector whose elements are equal to \(R_k(\kappa _j, \rho _j)\), \(\bar{A}\) a \(3N \times 3N\) matrix whose coefficients are taken from matrices \(\bar{\alpha }_{jm}\), and \(\bar{e}^s_k\) an \(N \times 1\) vector whose elements taken from vectors \(\bar{e}_{js}\). If the total field \(\bar{e}^{ts}\) at the scatterer is defined such that \(\bar{a}^s = \mathcal D (\bar{R}) \cdot \bar{e}^{ts}\), then from Eq. (14.69),
Assuming that the receiver positions \(\mathbf {r}_r\), \(r = 1, 2, \cdots , N_r\) are held constant for all transmissions, the corresponding scattered field vector \(\bar{p}_s^{\text{sc}}\) can be computed as
with \(\bar{\psi }_l\) an \(N_r \times N\) matrix whose rows can be calculated using Eq. (14.67) with \(\mathbf{{r}} = \mathbf{{r}}_r - \mathbf{{r}}_i\), \(i = 1, 2, \cdots , N\).
Speed of sound (top row) and density (bottom row) images obtained using the multiple frequency T-matrix approach. First column: ideal profiles. Second and third columns: reconstructions using single frequency data and multiple frequency data with \(f_{min} = f_0/64\), respectively. Even though the sound speed tomograms converged for both cases, multiple frequency data was needed to obtain a convergent density tomogram. Adapted from Lavarello and Oelze (2010)
The matrix equations in Eqs. (14.70) and (14.71) are counterparts to the integral equations in Eqs. (14.37) and (14.38), and can be solved for \(\bar{R}\) using Newton-type or gradient descend methods as described in Lin and Chew (1996a, b).
4.6.1 Convergence
The convergence of the T-matrix formulation has been studied by Lavarello and Oelze (Lavarello and Oelze 2009). It was found that sound speed images derived using the T-matrix formulation follow the same convergence rules that the DBIM does, i.e., sound speed imaging convergence is dependent upon the maximum phase shift induced by the scatterer on the incident field. Density imaging using the T-matrix approach diverges due to a different mechanism, namely the weak dependence of the scattering pattern on \(\rho \) for large \(ka\) values. When imaging circular cylinders of radius \(a\), the convergence condition was heuristically approximated as \(k_0a<1\).Footnote 8 Therefore, for practical biomedical imaging applications the condition for convergence in \(\kappa \) and \(\rho \) is likely to be more restrictive than that for convergence in \(c\). This restriction was later found to be valid for more complex imaging targets exhibiting structures of different sizes, as shown in Fig. 14.7. Further studies showed that the convergence of the T-matrix formulation is also dependent on the acoustical properties of the imaging target, i.e., the actual values of sound speed and density (Lavarello and Oelze 2010).
4.7 Results
The complexity of both algorithmic implementations and required experimental setup has prevented widespread implementations of full wave inversion techniques. However, experimental validation of some of these methods using acoustic waves have been reported. An example is the laboratory system at the University of Rochester (Waag and Fedewa 2006), which consists of 2048 elements operating at 2.5 MHz with 67 % −6-dB bandwidth and distributed in a 150 mm diameter ring. Using this ring system, reconstructions of large scale phantoms using eigenfunction methods have been performed (Lin et al. 2000). Another notable system is the scanner by Techniscan Inc. (Johnson et al. 1999), which consists of linear arrays facing each other operating at frequencies up to 2.5 MHz. Mechanical rotation is used in order to obtain full angular coverage on transmission. Using this system, Techniscan Inc. researchers have successfully implemented inverse scattering methods based on Newton-type and gradient descent approaches and obtained breast images in vivo (Johnson et al. 2007; Wiskin et al. 2012). These encouraging results suggest full wave inversion methods have reached a level of maturity that allows them to be explored for clinical applications.
5 Numerical Forward Scattering Solutions
Full-wave inversion techniques such as the alternating variables method and the distorted Born iterative method require repeated solutions of the integral equation of scattering (14.17). For practical application of full-wave inverse scattering methods, efficient methods should be employed to solve the acoustic scattering problem with minimal computational effort. Among a wide variety of techniques developed to address these issues, fast Fourier convolution methods (Johnson et al. 1984; Borup and Ghandi 1985; Cui and Chew 1999; Xu and Liu 2002) and the fast multipole method (FMM) (Greengard and Rokhlin 1987; Rokhlin 1990; Chew et al. 2001; Michielssen and Jin 2008) are popular choices. These methods are here presented because they provide a complete solution to the wave equation and because they illustrate a number of the efficiency issues present in forward and inverse scattering problems. Simplified methods that trade accuracy for efficiency by solving a restricted version of the scattering problem may offer greatly improved performance and still provide sufficient accuracy for desired applications.
A generalized representation of the method-of-moments formulation of the wave scattering equation takes the form (Harrington 1993)
in which the \(N\times N\) matrices \(A\) and \(G\) are given by
for a Green’s function \(G_0\), a domain \(\Omega \) that contains the support of a scattering contrast profile \(O\), a basis function \(\chi _j\) and a testing function \(t_k\). The \(N\)-element vectors \(f\) and \(f^i\) are discrete representations of the total and incident fields, respectively, such that
Using an iterative method such as GMRES (Saad and Schultz 1986) or BiCG-STAB (Van der Vorst 1992), the inverse of the matrix \(A - G\) does not need to be directly computed. Instead, the solution is obtained through repeated products of \(A - G\) with a succession of test vectors. Because the basis and testing functions are often localized, the matrix \(A\) tends to be sparse and, therefore, products of the form \(Af\) are inherently efficiently computed. Consequently, fast Fourier convolution methods and the FMM are each concerned with efficiently representing the matrix product \(Gf\).
5.1 Fast Fourier Convolution Methods
Methods that employ fast Fourier convolution of the Green’s function require that the basis functions \(\chi _j\) and the testing functions \(t_k\) in a method-of-moments formulation (14.73) have supports that are positioned at regular intervals throughout the domain. Most commonly, a three-dimensional scattering domain \(\Omega \) is subdivided into a collection \(\left\{ c_j: 0\le j < N\right\} \) of \(N\) disjoint cubic cells coincident with an \(M_x\times M_y\times M_z = N\) grid. Each cell \(c_j\) has a volume \(\Delta \) and is associated with a constant contrast value \(O_j\) and a constant field value \(f_j\). Hence, the basis function \(\chi _j\) is the characteristic function, or pulse basis function, associated with cell \(c_j\). In this case, the contrast function \(O\) is separable from the Green’s matrix \(G\) in Eq. (14.73):
where \(O\) is interpreted as a diagonal matrix with elements \(O_{jj}\) that correspond to samples \(O_j\) of the contrast for cell \(c_j\).
Let \(c_i\) represent a target cell that has an index \((l,m,n)\) within the \(M_x\times M_y\times M_z\) grid, while a source cell \(c_j\) has an associated grid index \((t,u,v)\). The scattering contribution to the matrix-vector product (14.76) at cell \(c_i\) may be expressed as
where \(O_{tuv}f_{tuv} = O_jf_j\) for the global index \(j\) corresponding to the local grid index \((t,u,v)\) and the Green’s function
Translational invariance and the equivalence of all cells \(c_i\) allows the characteristic functions \(\chi _i\) and \(\chi _j\) in the definition of the Green’s matrix element \(G_{s,ij}\) to be replaced with an arbitrary characteristic function such as \(\chi _0\). Hence, elements of the Green’s function are functions only of the separation of two cells, rather than their absolute positions. The offset in Eq. (14.78) is given by
where each scattering cell has \(x\), \(y\), and \(z\) lengths \(\Delta x\), \(\Delta y\), and \(\Delta z\), respectively. Since the grid is cubic, \(\Delta x = \Delta y = \Delta z = \root 3 \of {\Delta }\).
The three-dimensional convolution (14.78) can be evaluated in the Fourier domain if \(G\) satisfies the cyclic properties
To satisfy these criteria, the pairwise Green’s function \(G\) defined on the local \(M_x\times M_y\times M_z\) grid must be replaced with a modified Green’s function \(G^{\prime }\) defined on an expanded \(2M_x\times 2M_y\times 2M_z\) grid. The modified Green’s function
in which the mappings
relate indices \((t^{\prime },u^{\prime },v^{\prime })\) on the original \(M_x\times M_y\times M_z\) grid to indices \((t,u,v)\) on the expanded \(2M_x\times 2M_y\times 2M_z\) grid. The product of the contrast and pseudo-pressure must similarly be expressed on an expanded grid as
The expressions (14.81) and (14.83) allow contributions to the field observed at \(c_i\) (14.77) to be represented as a Fourier-domain multiplication:
where \(\mathbb F \) represents the discrete Fourier transform and the index triple \((l,m,n)\) corresponds to a linearized index \(i\). Thus, rather than requiring \(O(N^2)\) computer time storage to evaluate products of the Green’s matrix with some vector \(f\), fast Fourier convolution reduces the computational cost to that of the fast Fourier transform (FFT): \(O(N\log N)\). Likewise, rather than computing the Green’s function for all pairwise interactions on the computational grid, which would require \(O(N^2)\) memory storage, the convolutional Green’s function \(G^{\prime }\) is defined only once for each point on the extended \(2M_x\times 2M_y\times 2M_z\) grid, which requires \(O(N)\) storage.
5.2 The Fast Multipole Method
Like fast Fourier convolution methods, the FMM provides a mechanism for evaluating the product of a discrete Green’s matrix and an arbitrary vector with computational and storage complexities better than the \(O(N^2)\) complexities of a direct matrix-vector multiplication and without requiring explicit computation of the full Green’s matrix \(G\). This facilitates large-scale solutions even on modest computer hardware. Although a hierarchical implementation provides optimum performance, a single-level FMM highlights the fundamentals of the technique.
The FMM is derived by replacing the Green’s function represented in the method of moments with a truncated expansion derived from Gegenbauer’s addition theorem (Coifman et al. 1993):
in which \(\left| \mathbf {d}\right| < \left| \mathbf {D}\right| \) and the spectral translator
The substitution in Eq. (14.85) decomposes the Green’s function into local shifts \(\mathbf {d}\) and a long-distance translation \(\mathbf {D}\).
The number of terms in the translator sum (14.86) is determined by the excess bandwidth formula bandwidth formula (Koc et al. 1999; Song and Chew 2001; Chew et al. 2001)
in which \(d_0 = -\log \epsilon \) is the number of digits of accuracy for a desired error \(\epsilon \). The formula (14.87) results in an approximate addition theorem (14.85) that exhibits the desired accuracy provided that the translation distance \(k\left| \mathbf {D}\right| > L\). If this constraint cannot be satisfied, more sophisticated methods, such as that described in Hastriter et al. (2003), are required to select the truncation point. The excess bandwidth formula (14.87) balances the need to incorporate sufficiently many terms to accurately approximate an unbounded sum in the underlying addition theorem with the tendency for Hankel functions to become unbounded with increasing order, which can result in inaccurate finite-precision evaluation of Eq. (14.86).
The FMM is made efficient by subdividing the scattering domain into some number of distinct interaction groups that are each associated with a collection of unique basis and testing functions. Define a source group of basis functions \(J = \{\chi _j: 0\le j < M\}\) with center \(\mathbf{{r}}_J\) and an observation group of testing functions \(K = \{t_k: 0\le k < {{M}^\prime }\}\) with center \(\mathbf{{r}}_K\), such that \(K\) is sufficiently distant from \(J\) for an appropriate definition of “sufficiently distant”. Typically, two groups are deemed sufficiently distant if the smallest spheres that contain the groups do not overlap; the minimum acceptable distance may be increased to improve accuracy at the expense of efficiency. The indices \(k\) and \(j\) refer to a local enumeration of the functions within groups \(K\) and \(J\), respectively. For each group, a one-to-one mapping exists such that \(j\mapsto {{j}^\prime }\) and \(k\mapsto {{k}^\prime }\), where the primed indices \(j^{\prime }\) and \(k^{\prime }\) are used to refer to the respective global enumeration for basis and testing functions.
The contribution to the total Green’s matrix product in Eq. (14.73) for an element \(t_k\in K\) due to the source group \(J\) takes the form
where \(f\) is an arbitrary discrete function being multiplied by the Green’s matrix and the functions \(F_j\) and \(R_k\) are called, respectively, the radiation and receiving patterns defined by
The radiation patterns of all basis functions of the group \(J\) have been aggregated to yield the group radiation pattern
The radiation pattern in Eq. (14.90) is a Fourier transform, restricted to the unit sphere, of the product of the contrast function \(O\) with the discrete approximation of \(f\) within \(J\), and is here called the far-field transform of \(J\).
Accumulation of radiation patterns using the far-field transform in Eq. (14.90) prior to translation is one key aspect of the FMM. This allows the fields radiated by all elements within one group to be translated en masse, avoiding redundant calculations in Green’s function expansions in Eq. (14.85). Further redundancy may be eliminated by considering the aggregate interaction of all source groups \(J \in {{\text{far}}}\,K\), in which \({{\text{far}}}\,K\) denotes the collection of all groups that are sufficiently distant from the observation group \(K\), The total far-field contribution to the Green’s matrix product for an element \(t_k\in K\) is written
Hence, radiation patterns from all source groups \(J\in {{\text{far}}}\,K\) may be successively translated to the observer group \(K\) and accumulated before being distributed en masse to the testing function \(t_k\) using the receiving pattern \(R_k\). Still greater efficiency is obtained when the summation in Eq. (14.91) is reused for calculations \([Gf]_{{{k}^\prime },{{\text{far}}}\,K}\) for all \(t_k\in K\). Because the sum depends only on the center \(\mathbf{{r}}_K\) and not on the individual testing functions \(t_k\), radiation patterns for all source groups \(J\in {{\text{far}}}\,K\) need only be translated to \(K\) once; this translated field, which is expanded in terms of incoming plane waves, may be successively distributed to every testing function in \(K\) by simply changing the receiving pattern \(R_k\).
The FMM fails to accurately compute interactions between an observation group \(K\) and source groups \(J\not \in {{\text{far}}}\,K\). Entries in the Green’s matrix corresponding to these near-field interactions must be directly computed using the method of moments. Thus, the total action of the Green’s matrix product on an element \(t_k\in K\) may be written
where \(M_J\) is the number of basis functions in source group \(J\) and, as before, the mapping \((\cdot )^{\prime }\) converts a local index into a global index.
The FMM can be improved by recursively subdividing the scattering domain into a hierarchy of cubic scattering groups. The hierarchical implementation facilitates multiplication of a vector by an \(N \times N\) Green’s matrix in \(O(N)\) time and with \(O(N)\) storage (Chew et al. 2001). A (finer) level-\(l\) hierarchy is obtained by dividing each group of the (coarser) level-\((l-1)\) hierarchy into eight “child” subgroups, halving the length of the cube edges along each dimension. The level-\(0\) group contains the entire scattering domain; thus, the \(l\)-th level of the hierarchy contains \(2^l\) cubic groups.
In the hierarchical FMM, diagonal translators are used to carry fields between groups at the coarsest possible level in the hierarchy. Near-field interactions, being unsuitable for diagonal translations, are deferred to the next finer level, where a portion of the interactions now exist between children of neighboring groups that are, in the finer level, now suitable for diagonal translation of a lower bandwidth. This is possible because, according to the excess bandwidth formula (14.87), the approximate bandwidth of diagonal translators, and hence the minimum translation distance, at any level is proportional to the size of the groups, relative to the acousti wavelength, in that level. The deferment of any remaining near-field interactions continues recursively until the finest level of the hierarchy is reached. At this level, all remaining near-field interactions are directly computed using the summation in Eq. (14.92).
Graphical depiction of aggregation and distribution (dashed arrows) and diagonal translations (curved arrows) in a two-level, hierarchical FMM
Key to the efficiency of this technique are interpolation and filtering schemes that alter the sampling rate of outgoing radiation patterns and incoming group fields. Because the possible bandwidth of outgoing and incoming wave expansions depends on the size of the FMM group, these expansions should be sampled at the minimum rate necessary for accurate representation. Radiation patterns for each group at a particular level may be recursively aggregated from interpolated and shifted forms of the radiation patterns of the group’s children. Likewise, incoming waves may be recursively distributed among the children of each group at a particular level by shifting and then filtering the waves to reduce their sampling rates. A schematic representation of these procedures is provided in Fig. 14.8. Radiation patterns of source groups at the finer level are aggregated, following the converging, dashed arrows at the left, to form the radiation pattern of the circled source group at the coarser level. The resulting radiation pattern is translated via the curved, solid arrow to an observer group at the right. The incoming plane-wave envelope is distributed via the diverging, dashed arrows to constituent observer groups at the finer level. At the finer level, interactions at each observer group that were not represented at the coarser level are carried via diagonal translations along the curved, hollow arrows.
5.2.1 Optimizations for Inverse Scattering Applications
Because the contrast profile is unknown during inverse scattering reconstructions, the use of basis and testing functions specialized to the shape of the scatterer is unwarranted. It is therefore convenient and computationally beneficial to employ the same discrete representation used in fast Fourier convolution methods; namely, that pulse basis functions \(\chi _j\) and testing functions \(t_k = \chi _k\) are defined on a collection of \(N\) disjoint cubic cells regularly spaced to cover the scattering domain \(\Omega \). While Eq. (14.91) still approximates the elements of the Green’s matrix in this arrangement, the radiation pattern (14.89a) of a basis function \(\chi _j\in J\) for some group \(J\) can be altered to remove its dependence on the contrast function, leaving
where \(j\) now refers to a local index of the basis function within group \(J\) and \(j^{\prime }\) is the corresponding global index. Thus, only one of the radiation or receiving patterns for each group must be computed. The group far-field transform (14.90) becomes
in which the contrast \(O\) now modifies the source distribution \(f\) within the group rather than the radiation patterns of its constituent basis functions. The total far-field contribution to the Green’s matrix product is still governed by Eq. (14.91) with the redefined group radiation patterns (14.94). The integration in Eq. (14.91), generalized as
in which \(\gamma _K\) is an arbitrary function that describes the complex amplitude of plane waves converging on \(\mathbf{{r}}_K\) from directions \(\hat{s}\), is the adjoint of the far-field transform when the far-field transform is viewed as an operator acting on the product \(\tilde{f} = Of\). Thus, a discrete representation of the far-field transform operator (14.94) is sufficient to represent both the forward and adjoint transforms.
Even greater savings in memory and computation are realized when the grid of scattering cells aligns with the grid of FMM groups at the finest level. In that case, for two groups \(J = \{\chi _j : 0\le j < M\}\) and \(K = \{\chi _k : 0\le k < M\}\) with respective centers \(\mathbf{{r}}_J\) and \(\mathbf{{r}}_K\), \(j = k \Rightarrow \mathbf{{r}}_j - \mathbf{{r}}_J = \mathbf{{r}}_k - \mathbf{{r}}_K\), where \(\mathbf{{r}}_j\) and \(\mathbf{{r}}_k\) represent, in turn, the centers of the globally indexed cells \(c_{j^{\prime }}\) and \(c_{k^{\prime }}\). Hence, the radiation and receiving patterns in Eq. (14.93) are independent of the group center \(\mathbf{{r}}_J\) and a single representation of the group far-field transform (14.94) applies to every FMM group.
The use of gridded basis and testing functions means that near-field evaluations among finest-level groups that each contain \(O(M)\) elements can be computed in \(O(M\log M)\) time, with \(O(M)\) storage, using an FFT-accelerated convolution (Hesford and Waag 2010) that extends the approach described in Sect. 14.5.1 to accommodate pairwise Green’s functions that depend on the separation between source and observer groups in the FMM hierarchy. If the total number of scattering elements is \(N\), then the number of finest-level FMM groups will be \(O(N/M)\). The total cost for the evaluation of neighboring interactions using FFT convolution is therefore \(O(N\log M)\), compared to the \(O(NM)\) total cost for dense-matrix multiplication of neighboring interaction matrices. Thus, for a fixed problem size \(N\), FFT convolution dramatically reduces the dependence of calculations of neighboring interactions on the group size \(M\).
Another limiting factor in the size of the finest-level groups of a hierarchical FMM is the cost of evaluating far-field transforms and of distributing incoming plane waves to testing functions in each group. In a cubic, gridded arrangement of scatterers, the diameter of each group is \(d = O(M^{1/3})\). Because the excess bandwidth formula (14.87) is used to predict the bandwidth \(L\) of the radiation and receiving patterns for a group, and \(L = O(d)\), the total number of samples of the patterns is \(O(M^{2/3})\). Thus, the far-field transform (14.94) may be represented by a matrix \(F\in {\mathbb{ C}} ^{m \times n}\), where \(m = O(M^{2/3})\) and \(n = O(M)\). Similarly, the adjoint far-field transform (14.95) may be represented as a matrix \(R = F^{\dagger }\in {\mathbb C} ^{n \times m}\), where \((\cdot )^{\dagger }\) represents the matrix adjoint.
The band-limited nature of the radiation and receiving patterns suggests that an accurate, but approximate, reduced-rank decomposition of the far-field transform may be obtained in the form
with \(U\in {\mathbb C} ^{m\times k}\), \(V\in {\mathbb C} ^{n\times k}\) and the rank \(k = O(L) = O(M^{1/3})\). This approximation reduces the cost of applying a far-field transform or its adjoint from \(O(M^{5/3})\) to \(O(M^{4/3})\). The adaptive cross approximation (ACA) (Bebendorf 2000; Zhao et al. 2005; Shaeffer 2008) provides a method for computing an approximation of the form in Eq. (14.96). The effective use of adaptive-cross approximated far-field transforms, together with recompression based on an efficient singular value decomposition, was explored in Hesford and Waag (2011) and shown to significantly reduce the computational cost of the FMM. Conceptually, the ACA works by alternatively constructing columns to populate the column matrix \(U\) and the row matrix \(V\). Columns for \(U\) and \(V\) are selected as the most significant of the remaining columns and rows, respectively, of the matrix \(F\) to be approximated; for this purpose, “most significant” means the column or row of \(F\) that contributes the largest element of the column of \(U\) or \(V\) that is currently being analyzed, neglecting elements contributed by previously analyzed columns or rows.
6 Parallel Computing
Modern computer systems are inherently parallel. Low-cost desktop systems often contain at least two CPU cores that share access to a common memory store, while supercomputers are most commonly composed of many interconnected nodes that each contain distinct memory stores and multiple CPUs. More recently, graphics processing units (GPUs) have been adapted to general-purpose computations that exploit low memory latency, rapid context switching and massive parallel processing abilities to provide excellent computational power. Algorithms that compute large-scale forward and inverse scattering solutions should leverage such parallel facilities to be most effective.
Each parallel computing methodology has distinct advantages and drawbacks. Shared-memory algorithms, for example, provide multiple computing threads access to all data within a shared memory store. While such algorithms do not require communication between the threads, threads must be synchronized to prevent conflicting attempts to modify the same data. Distributed-memory systems provide each task with its own locally relevant data that eliminates the need for synchronization. However, operations that require the cooperation of more than one task must use communication (typically over a network) of data. Both synchronization and communication result in serial bottlenecks that can limit the effectiveness of massive parallelization. Furthermore, distributed-memory communication often exhibits relatively high latency. To some extent, latency can be concealed by initiating non-blocking communication that can be completed while each task processes its local data.
General-purpose GPU computing takes a different approach than those of classical shared- or distributed-memory parallel systems. A typical GPU may have hundreds of lightweight, individual processing units capable of manipulating floating-point numbers, but each performs optimally on independent data accessed through a graphics memory store. Interactions with system memory must be performed over a comparatively slow bus, and the graphics memory, while fast, can have comparatively high latency with respect to the floating-point performance of the GPU. To conceal this latency, GPUs offer fast context switches, and dispatch hundreds of independent tasks that can be quickly interchanged while they await memory accesses. When multiple tasks must collaborate on blocks of data, special care must be taken to avoid redundant memory access or performance can suffer greatly. GPU computing has been reported to significantly speed-up the execution of full wave inverse scattering methods (Garland et al. 2008; Roy et al. 2010; Wiskin et al. 2010).
The choice of algorithm and the selection of parallel hardware are closely linked. The independence of the multiple forward solutions required for each iteration of the DBIM makes for an ideal parallelization scheme, without the need for substantial communication or synchronization, on either shared- or distributed-memory systems (Hesford and Chew 2006). In contrast, the fast Fourier transforms in the FFT-based methods described above are not ideal in distributed-memory systems, since all elements in the FFT interact. Alternative forward solvers like the FMM, with appropriate consideration, can be efficiently implemented on distributed-memory systems without requiring communication among all tasks.
Shared- and distributed-memory parallel speed-up of an FMM solution of an acoustic scattering problem involving approximately 440 million unknowns
In practice, modern algorithms often require hybrid parallelization to take advantage of supercomputers with multiple, distributed-memory nodes that each house several shared-memory CPUs. For example, a distributed-memory FMM that subdivides the scattering object among multiple nodes can be readily adapted to shared-memory nodes by assigning to each CPU a portion of the scattering object assigned to that node. With careful ordering of computations, it is possible to update representations of the field confined to the local portion of the object in parallel without the need for synchronization. Figure 14.9 provides an illustration of the benefit of multiple shared-memory threads and distributed-memory processes when solving an acoustic scattering problem involving approximately 440 million unknowns on a supercomputer. The reported parallel speed-up is the ratio of some reference solution time to the time required to compute a solution with the number of parallel tasks (threads or processes) scaled by a task multiplier. For the distributed-memory experiment, a minimum of 16 supercomputer nodes were required to store the problem in memory; therefore, the reference solution (with a unity task multiplier) employed 16 distributed processes. In all experimental configurations, each distributed process employed six shared-memory threads. In the shared-memory experiment, a total of 64 distributed processes were used for all experimental configurations; the unity task multiplier corresponds to one shared-memory thread per process.
7 Closing Remarks
Acoustic tomography has reached a high level of maturity over the past four decades. A wide variety of reconstruction algorithms exist that represent different trade-offs between accuracy and computational cost. Several of these algorithms have been described in this chapter, but the list should not be considered to be complete.
Over the years, several engineering aspects of acoustic tomography have been successfully implemented. Even with the use of full wave inversion methods, the reconstruction of computational regions with hundreds of thousands to millions of unknowns is now possible (Lavarello and Oelze 2008; Haynes and Moghaddam 2010; Hesford and Chew 2010; Wiskin et al. 2012). However, certain implementation aspects still require additional developments. The vast majority of research in acoustic tomography involves the use of synthetic measurements, whereas system calibration for measuring phase-sensitive data is a non-trivial problem (Andre et al. 1997; Johnson et al. 1997; Waag and Fedewa 2006; Parhizkar et al. 2011) which may impair imaging of sensitive parameters such as attenuation coefficients and density. Although 3D imaging has been successfully demonstrated, proper handling of boundary conditions needs to be addressed for certain applications such as breast imaging where inspection in the axillary region and near the chest wall may be required.
Perhaps the biggest challenge remaining for ultrasonic tomography is the validation of its usefulness in clinical practice. The significance of imaging sound speed, attenuation, or mass density for applications such as breast cancer detection has not been properly addressed yet. Specifically, the contrast associated with diseased tissue in terms of sound speed, density, and attenuation has not been explicitly established and conflicting reports in the literature exist. Therefore, the next chapter will provide a comprehensive discussion on the lessons learned from experimental acoustic tomography studies.
Notes
- 1.
The eikonal equation can alternatively be derived from Fermat’s principle, and therefore this principle can also be used for ray tracing. The interested reader can refer to acoustics textbooks such as Pierce (1989).
- 2.
- 3.
This approach is in fact a synthetic aperture reconstruction method (Soumekh 1999) equivalent to the delay-and-sum algorithm. A commonly used variation is to perform the backpropagation operation using envelope-detected data, which results in a spatial compounding reconstruction method (Trahey et al. 1986).
- 4.
Density information from dispersive media can also be isolated from \(O_\rho (k,\mathbf {r})\) profiles at different frequencies if the dispersion can be properly modeled as a function of \(\omega \).
- 5.
- 6.
See Sect. 14.5 for a discussion on the discretization of the wave equation.
- 7.
- 8.
Like in the case of sound speed imaging with DBIM, frequency hopping can be used to improve the spatial resolution of density tomograms constructed with the T-matrix formulation.
References
Green PS, Schaefer LF, Jones ED, Suarez JR (1974) A new high-performance ultrasonic camera system, in Acoustical Holography, 5th edn. Wiley, New York, pp 493–504
Marich KW, Green PS, Suarez JR, Zatz LM, Macovski A (March 1975) Real-time imaging with a new ultrasonic camera: Part I, in vitro experimental studies on transmission imaging of biological structures. J Clin Ultrasound 3(1):5–16
Heyser R, Le Croissette D (1973) Transmission ultrasonography. In: Proceedings of the IEEE ultrasonics, symposium, pp 7–9
Heyser RC, Croissette DHL (1974) A new ultrasonic imaging system using time delay spectrometry. Ultrasound Med Biol 1(2):119–131
Hounsfield GN (December 1973) Computerized transverse axial scanning (tomography): I. Description of system. Br J Radiol 46(552):1016–1022
Kuhl DE, Edwards RQ (April 1963) Image separation radioisotope scanning. Radiology 80(4):653–662
Phelps ME, Hoffman EJ, Mullani NA, Higgins CS, Ter Pogossian MM (February 1976) Design considerations for a positron emission transaxial tomogram (PETT III). IEEE Trans Nucl Sci 23(1):516–522
Damadian R (March 1971) Tumor detection by nuclear magnetic resonance. Science 171(3976):1151–1153
Lauterbur PC (1974) Magnetic resonance zeugmatography. Pure Appl Chem 40(1):149157
Pierce AD (1989) Acoustics: an introduction to its physical principles and applications. Acoustical Society of America, Woodbury
Carson PL, Oughton TV, Hendee WR, Ahuja AS (1977) Imaging soft tissue through bone with ultrasound transmission tomography by reconstruction. Med Phys 4(4):302–309
Dines KA, Fry FJ, Patrick JT, Gilmor RL (October 1981) Computerized ultrasound tomography of the human head: experimental results. Ultrason Imaging 3(4):342–351
Goss SA, Johnston RL, Dunn F (1978) Comprehensive compilation of empirical ultrasonic properties of mammalian tissues. J Acoust Soc Am 64(2):423–457
Goss SA, Johnston RL, Dunn F (1980) Compilation of empirical ultrasonic properties of mammalian tissues II. J Acoust Soc Am 68(1):93–108
Greenleaf J, Johnson S, Samayoa W, Duck F (1975) Algebraic reconstruction of spatial distributions of acoustic velocities in tissue from their time-of-flight profiles in Acoustical Holography vol 6. pp 71–90
Bracewell RN (1956) Strip integration in radio astronomy. Aust J Phys 9(2):198–217
Bracewell RN, Riddle AC (1967) Inversion of fan-beam scans in radio astronomy. Astrophysl J 150(2):427–434
Ramachandran GN, Lakshminarayanan AV (1971) Three-dimensional reconstructions from radiographs and electron micrographs: application of convolutions instead of fourier transforms. Proc Nat Acad Scie USA 68(9):2236–2240
Shepp LA, Logan BF (1971) The fourier reconstruction of a head section. IEEE Trans Nucl Sci 68(9):2236–2240
Andersen AH, Kak AC (1984) Simultaneous algebraic reconstruction technique (SART): a superior implementation of the ART algorithm. Ultrason Imaging 6(1):81–94
Glover GH (1978) Ultrasonic fan beam scanner for computerized time-of-flight tomography. U.S. Patent 4,075,883
Greenleaf J, Johnson S, Lee S, Herman G, Wood E (1974) Algebraic reconstruction of spatial distributions of acoustic absorption within tissue from their two-dimensional acoustic projections, in Acoustical Holography vol 5. pp 591–603
Dines KA, Kak AC (1979) Ultrasonic attenuation tomography of soft tissues. Ultrason Imaging 1(1):16–33
Klepper JR, Brandenburger GH, Mimbs JW, Sobel BE, Miller JG (1981) Application of phase-insensitive detection and frequency-dependent measurements to computed ultrasonic attenuation tomography. IEEE Trans Biomed Eng 28(2):186–201
Greenleaf JF, Johnson SA, Lent AH (1978) Measurement of spatial distribution of refractive index in tissues by ultrasonic computer assisted tomography. Ultrasound Med Biol 3(4):327–339
Jakowatz CV, Kak AC (1976) Computerized tomographic imaging using X-rays and ultrasound. School of Electrical Engineering, Purdue University, Tech Rep TR-EE 76–26
Johnson SA, Greenleaf JF, Samayoa WA, Duck FA, Sjostrand J (1975) Reconstruction of three-dimensional velocity fields and other parameters by acoustic ray tracing. In: Proceedings of the IEEE Ultrasonics, Symposium, pp 46–51
Andersen AH, Kak AC (1982) Digital ray tracing in two-dimensional refractive fields. J Acoust Soc Am 34(10):1562–1582
Andersen AH (1986) A top-down philosophy for accurate numerical ray tracing. J Acoust Soc Am 80(2):656–660
Norton SJ (1987) Computing ray trajectories between two points: a solution to the ray-linking problem. J Opt Soc Am 4(10):1919–1922
Julian BR, Gubbins D (1977) Three-dimensional seismic ray tracing. J Geophys 43(1–2):95–113
Schomberg H (1978) An improved approach to reconstructive ultrasound tomography. J Phys D: Appl Phys 11(15):L181–L185
Lytle RJ, Dines KA (1980) Iterative ray tracing between boreholes for underground image reconstruction. IEEE Trans Geosci Remote Sens 18(3):234–240
Andersen AH (1987) Ray linking for computed tomography by rebinning of projection data. J Acoustl Soc Am 81(4):1190–1192
Moser TJ (1991) Shortest path calculation of seismic rays. Geophysics 56(1):59–67
Klimes L, Kvasnicka M (1994) 3-D network ray tracing. Geophys J Intl 116(3):726–738
Song L, Zhang S (1998) Stabilizing the iterative solution to ultrasonic transmission tomography. IEEE Trans Ultrason, Ferroelectr, Freq Control 45(4):1117–1120
Li S, Jackowski M, Dione DP, Varslot T, Staib LH, Mueller K (2010) Refraction corrected transmission ultrasound computed tomography for application in breast imaging. Med Phys 37(3):201–233
Denis F, Basset O, Gimenez G (1995) Ultrasonic transmission tomography in refracting media: reduction of refraction artifacts by curved-ray techniques. IEEE Trans Med Imaging 14(1):173–188
Norton SJ, Linzer M (1982) Correcting for ray refraction in velocity and attenuation tomography:a perturbation approach. Ultrason Imaging 4(3):201–233
Farrell EJ (1981) Tomographic imaging of attenuation with simulation correction for refraction. Ultrason Imaging 3(2):144–163
Pan KM, Liu CN (1981) Tomographic reconstruction of ultrasonic attenuation with correction for refractive errors. IBM J Res Dev 25(1):71–82
Jensen JA (1990) A model for the propagation and scattering of ultrasound in tissue. J Acoustl Soc Am 89(1):182–190
Norton S, Linzer M (1979a) Ultrasonic reflectivity tomography: reconstruction with circular transducer arrays. Ultrason Imaging 1(2):210–231
Norton SJ, Linzer M (1979b) Ultrasonic reflectivity imaging in three dimensions: reconstruction with spherical transducer arrays. Ultrason Imaging 1(3):210–231
Soumekh M (1999) Synthetic aperture radar signal processing with matlab algorithms. Wiley, New York
Trahey GE, Smith SW, von Ramm OT (1986) Speckle pattern correlation with lateral aperture translation: experimental results and implications for spatial compounding. IEEE Trans Ultrason, Ferroelectr, Freq Control 33(3):257–264
Ashfaq M, Ermert H (2007) Acoustic tomography scheme for small animal tissue characterization. In: Proceedings of the IEEE ultrasonics, symposium, pp 977–980
Schmidt S, Duric N, Li C, Roy O, Huang Z-F (2011) Modification of Kirchhoff migration with variable sound speed and attenuation for acoustic imaging of media and application to tomographic imaging of the breast. Medl Phys 38(2):998–1007
Koch A, Koch I, Hansen C, Lerch R, Ermert H (2012) Numerical ray-tracing in full angle spatial compounding. Acoust Imaging 31:103–113
Glover GH (1977) Computerized time-of-flight ultrasonic tomography for breast examination. Ultrasound Med Biol 3(2–3):117–127
Carson PL, Meyer CR, Scherzinger AL, Oughton TV (1981) Breast imaging in coronal planes with simultaneous pulse echo and transmission ultrasound. Science 214(4525):1141–1143
Greenleaf JF, Bahn RC (1981) Clinical imaging with transmissive ultrasonic computerized tomography. IEEE Trans Biomed Eng 28(2):177–185
Schreiman JS, Gisvold JJ, Greenleaf JF, Bahn RC (1984) Ultrasound transmission computed tomography of the breast. Radiology 150(2):523–530
Duric N, Littrup P, Babkin A, Chambers D, Azevedo S, Kalinin A, Pevzner R, Tokarev M, Holsapple E, Rama O, Duncan R (2005) Development of ultrasound tomography for breast imaging: technical assessment. Med Phy 32(5):1375–1386
Duric N, Littrup P, Poulo L, Babkin A, Pevzner R, Holsapple E, Rama O, Glide C (2007) Detection of breast cancer with ultrasound tomography: first results with the computed ultrasound risk evaluation (CURE) prototype. Med Phys 34(2):773–785
Li C, Duric N, Littrup P, Huang L (2009) In vivo breast sound-speed imaging with ultrasound tomography. Ultrasound Med Biol 35(10):1615–1628
Jeong J-W, Kim T-S, Shin DC, Do S, Singh M, Marmarelis VZ (2005) Soft tissue differentiation using multiband signatures of high resolution ultrasonic transmission tomography. IEEE Trans Medl Imaging 24(3):399–408
Jeong J-W, Shin DC, Do S-H, Blanco C, Klipfel NE, Holmes DR, Hovanessian-Larsen LJ, Marmarelis VZ (2008) Differentiation of cancerous lesions in excised human breast specimens using multiband attenuation profiles from ultrasonic transmission tomography. J Ultrasound Med 27(3):435–451
Jeong J-W, Shin DC, Marmarelis VZ (2009) Image fusion methodology for efficient interpretation of multiband images in 3D high-resolution ultrasonic transmission tomography. Intl J Imaging Syst Technoly 19(4):277–282
Gemmeke H, Ruiter NV (2007) 3D ultrasound computer tomography for medical imaging. Nucl Instrum Methods Phys Res A 580(2):1057–1065
Jirík R, Peterlík I, Ruiter N, Fousek J, Dapp R, Zapf M, Jan J (2012) Sound-speed image reconstruction in sparse-aperture 3-D ultrasound transmission tomography. IEEE Trans Ultrason, Ferroelectr, Freq Control 59(2):254–264
Zhang D, Gong X-F (1999) Experimental investigation of the acoustic nonlinearity parameter tomography for excised pathological biological tissues. Ultrasound Med Biol 25(4):593–599
Zhang D, Chen X, Gong X-F (2001) Acoustic nonlinearity parameter tomography for biological tissues via parametric array from a circular piston source: theoretical analysis and computer simulations. J Acoust Soc Am 109(3):1219–1225
Quan Y, Huang L (2007) Sound-speed tomography using first-arrival transmission ultrasound for a ring array. In: Proceedings of the SPIE, vol 6513. pp 651 306.1-651 306.9
Leach Jr RR, Azevedo SG, Berryman JG, Bertete-Aguirre HR, Chambers DH, Mast JE, Littrup P, Duric N, Johnson SA, Wuebbeling F (2002) Comparison of ultrasound tomography methods in circular geometry. In: Proceedings of the SPIE, vol 4687. pp 362–377
Mueller RK, Kaveh M, Wade G (1979) Reconstructive tomography and applications to ultrasonics. Proc IEEE 67(4):567–587
Mueller RK (1980) Diffraction tomography I: the wave equation. Ultrason Imaging 2(3):213–222
Wolf E (1969) Three-dimensional structure determination of semi-transparent objects from holographic data. Opt Commun 1(4):153–156
Kak A, Slaney M (2001) Principles of computerized tomographic imaging. SIAM, Philadelphia
Chew WC (1995) Waves and fields in inhomogeneous media. IEEE Press, Piscataway
Naidu P, Vasuki A, Satyamurthy P, Anand L (1995) Diffraction tomographic imaging with a circular array. IEEE Trans Ultrason, Ferroelectr, Freq Control 42(4):787–789
Iwata K, Nagata R (1975) Calculation of refractive index distribution from interferograms using the Born and Rytov’s approximations. Japan J Appl Phys 14(14–1):379–383
Devaney A (1981) Inverse-scattering theory within the Rytov approximation. Opt Lett 6(8):374–376
Kenue SK, Greenleaf JF (1982) Limited angle multifrequency diffraction tomography. IEEE Trans Sonics Ultrason 29(4):213–216
Norton SJ (1983) Generation of separate density and compressibility images in tissue. Ultrason Imaging 5(3):240–252
Pan S, Kak A (1983) A computational study of reconstruction algorithms for diffraction tomography: interpolation versus filtered-backpropagation. IEEE Trans Acoust, Speech Signal Process 31(5):1262–1275
Kaveh M, Soumekh M, Greenleaf JF (1984) Signal processing for diffraction tomography. IEEE Trans Sonics and Ultrason 31(4):230–239
Soumekh M (1988) Band-limited interpolation from unevenly spaced sampled data. IEEE Trans Acoust, Speech Signal Process 36(1):110–122
Devaney A (1982) Inversion formula for inverse scattering within the Born approximation. Opt Lett 7(3):111–112
Devaney AJ (1983) A computer simulation study of diffraction tomography. IEEE Trans Biomed Eng 30(7):377–386
Sponheim N, Gelius L-G, Johansen I, Stamnes JJ (1991) Quantitative results in ultrasonic tomography of large objects using line sources and curved detector arrays. IEEE Trans Ultrason, Ferroelectr, Freq Control 38(4):370–379
Sponheim N, Gelius L-J, Johansen I, Stamnes JJ (1994) Ultrasonic tomography of biological tissue. Ultrason Imaging 16(1):19–32
Devaney AJ, Beylkin G (1984) Diffraction tomography using arbitrary transmitter and receiver surfaces. Ultrason Imaging 6(2):181–193
Devaney AJ (1985) Generalized projection-slice theorem for fan beam diffraction tomography. Ultrason Imaging 7(3):264–275
Gelius L-G, Johansen I, Sponheim N, Stamnes JJ (1991) A generalized diffraction tomography algorithm. J Acoust Soc Am 89(2):523–528
Anastasio M, Pan X (2003) An improved reconstruction algorithm for 3-D diffraction tomography using spherical-wave sources. IEEE Trans Biomed Eng 50(4):517–521
Devaney AJ (1986) Reconstructive tomography with diffracting wavefields. Inverse Prob 2(2):161–183
Ladas KT, Devaney AJ (1991) Generalized ART algorithm for diffraction tomography. Inverse Prob 7(1):109–125
Devaney AJ (1985) Variable density acoustic tomography. J Acoust Soc Am 78(1):120–130
Moghaddam M, Chew W (1993) Variable density linear acoustic inverse problem. Ultrason Imaging 15(3):255–266
Mensah S, Lefebvre JP (1997) Enhanced compressibility tomography. IEEE Trans Ultrason, Ferroelectr, Freq Control 44(6):1245–1252
Anastasio MA, Shi D, Deffieux T (2005) Image reconstruction in variable density acoustic tomography. In: Proceedings of the SPIE, vol 5750. pp 326–331
Kai A, Sun J, Wade G (1992) Imaging the acoustic nonlinear parameter with diffraction tomography. IEEE Trans Ultrason, Ferroelectr, Freq Control 39(6):708–715
Slaney M, Kak A, Larsen L (1984) Limitations of imaging with first-order diffraction tomography. IEEE Trans Microwave Tech 32(8):860–874
Robinson B, Greenleaf J (1986) The scattering of ultrasound by cylinders: Implications for diffraction tomography. J Acoust Soc Am 80(1):40–49
Tsihrintzis GA, Devaney AJ (2000) Higher-order (nonlinear) diffraction tomography: inversion of the Rytov series. IEEE Trans Inf Theory 46(5):1748–1765
Wedberg TC, Stamnes JJ (1995) Comparison of phase retrieval methods for optical diffraction tomography. Pure Appl Opt 4(1):39–54
Mast TD (1999) Wideband quantitative ultrasonic imaging by time-domain diffraction tomography. J Acoustl Soc Am 106(6):3061–3071
Astheimer JP, Waag RC (2008) Born iterative reconstruction using perturbed-phase field estimates. J Acoust Soc Am 124(4):2353–2363
Johnson S, Tracy M (1983) Inverse scattering solutions by a sinc basis, multiple source, moment method - part I: theory. Ultrason Imaging 5(4):361–375
Tracy M, Johnson S (1983) Inverse scattering solutions by a sinc basis, multiple source, moment method - part II: numerical evaluations. Ultrason Imaging 5(4):376–392
Johnson S, Zhou Y, Tracy M, Berggren M, Stenger F (1984) Inverse scattering solutions by a sinc basis, multiple source, moment method - part III: fast algorithms. Ultrason Imaging 6(1):103–116
Wang YM, Chew WC (1989) An iterative solution of two-dimensional electromagnetic inverse scattering problem. Int J Imaging Syst Technol 1(1):100–108
Johnson SA, Stenger F, Wilcox C, Ball J, Berggren MJ (1982) Wave equations and inverse solutions for soft tissue. Acoust Imaging 11:409–424
Pourjavid S, Tretiak OJ (1992) Numerical solution of the direct scattering problem through the transformed acoustical wave equation. J Acoust Soc Am 91(2):639–645
Berggren MJ, Johnson SA, Carruth BL, Kim WW, Stenger F, Kuhn PK (1996) Ultrasound inverse scattering solutions from transmission and/or reflection data. In: Proceedings of the SPIE, vol 671. pp 114–121
Cavicchi T, Johnson S, O’Brien WD Jr (1988) Application of the sinc basis moment method to the reconstruction of infinite circular cylinders. IEEE Trans Ultrason, Ferroelectr, Freq Control 35(1):22–33
Cavicchi T, O’Brien WD Jr (1989) Numerical study of higher-order diffraction tomography via the sinc basis moment method. Ultrason Imaging 11(1):42–74
Colton D, Coyle J, Monk P (2000) Recent developments in inverse acoustic scattering theory. SIAM Rev 42(3):369–414
Chew WC, Wang YM (1990) Reconstruction of two-dimensional permittivity distribution using the distorted Born iterative method. IEEE Trans Med Imaging 9(2):218–225
Borup D, Johnson S, Kim W, Berggren M (1992) Nonperturbative diffraction tomography via Gauss-Newton iteration applied to the scattering integral equation. Ultrason Imaging 14(1):69–85
Remis RF, van den Berg PM (2000) On the equivalence of the Newton–Kantorovich and distorted Born methods. Inverse Prob 16(1):L1–L4
Devaney AJ, Oristaglio ML (1983) Inversion procedure for inverse scattering within the distorted-wave Born approximation. Phys Rev Lett 51(4):237–240
Ghosh Roy DN, Roberts J, Schabel M, Norton SJ (2007) Noise propagation in linear and nonlinear inverse scattering. J Acoust Soc Am 121(5):2743–2749
Hesford AJ, Chew WC (2010) Fast inverse scattering solutions using the distorted Born iterative method and the multilevel fast multipole algorithm. J Acoust Soc Am 128(2):679–690
Kim W, Borup D, Johnson S, Berggren M, ZhouY (1987) Accelerated inverse scattering algorithms for higher contrast objects. In: Proceedings of the IEEE Ultrasonics, Symposium, pp 903–906
Chew WC, Lin JH (1995) A frequency-hopping approach for microwave imaging of large inhomogeneous bodies. IEEE Microwave Guided Wave Lett 5(12):440–441
Haddadin O, Ebbini E (1998) Imaging strongly scattering media using a multiple frequency distorted Born iterative method. IEEE Trans Ultrason, Ferroelectr, Freq Control 45(6):1485–1496
Lavarello RJ, Oelze ML (2008) A study on the reconstruction of moderate contrast targets using the distorted Born iterative method. IEEE Trans Ultrason, Ferroelectr, Freq Control 55(1):112–124
Lavarello RJ, Oelze ML (2009) Tomographic reconsruction of three-dimensional volumes using the distorted Born iterative method. IEEE Trans Med Imaging 28:1643–1653
Duncan DP, Astheimer JP, Waag RC (2009) Scattering calculation and image reconstruction using elevation-focused beams. J Acoust Soc Am 125(5):3101–3119
Kleinman RE, van den Berg PM (1992) A modified gradient method for two-dimensional problems in tomography. J Comput Appl Math 42(1):17–35
Harada H, Wall DJN, Takenaka T, Tanaka M (1995) Conjugate gradient method applied to inverse scattering problem. IEEE Trans Antennas Propag 43(8):784–792
Lobel P, Pichot C, Blanc-Feraud L, Barlaud M (1997) Microwave imaging: reconstructions from experimental data using conjugate gradient and enhancement by edge-preserving regularization. Int J Imaging Syst Technol 8(4):337–342
Zhang X, Broschat S, Flynn PJ (2004) A numerical study of conjugate gradient directions for an ultrasound inverse problem. J Comput Acoust 12(4):587–604
Zhang X, Broschat S, Flynn P (2002) A comparison of material classification techniques for ultrasound inverse imaging. J Acoust Soc Am 111(1):457–467
Wiskin J, Borup D, Johnson S, Berggren M, Abbott T, Hanover R (2007) Full wave, non-linear, inverse scattering: High resolution quantitative breast tissue tomography. Acoust Imaging 28:183–193
van den Berg PM, Kleinman RE (1997) A contrast source inversion method. Inverse Prob 13(6):1607–1620
van den Berg PM, van Broekhoven AL, Abubakar A (1999) Extended contrast source inversion method. Inverse Prob 15(5):1325–1344
Pelekanos G, Abubakar A, van den Berg PM (2003) Contrast source inversion methods in elastodynamics. J Acoust Soc Am 114(5):2825–2834
Gordon R (1974) A tutorial on ART (algebraic reconstruction technique). IEEE Trans Nucl Sci 21(3):78–93
Natterer F, Wübbeling F (1995) A propagation-backpropagation method for ultrasound tomography. Inverse Prob 11(6):1225–1232
Natterer F (1997) An algorithm for 3D ultrasound tomography. In: Chavent G, Sabatier PC (eds) Lecture Notes in Physics, Vol 486: inverse problems of wave propagation and diffraction. Springer, New York, pp 216–225
Natterer F (2008) Reflectors in wave equation imaging. Wave Motion 45(6):776–784
Mast TD, Nachman AI, Waag RC (1997) Focusing and imaging using eigenfunctions of the scattering operator. J Acoust Soc Am 102(2):715–725
Lin F, Nachman AI, Waag RC (2000) Quantitative imaging using a time-domain eigenfunction method. J Acoust Soc Am 108(3):899–912
Waag RC, Lin F, Varslot TK, Astheimer JP (2007) An eigenfunction method for reconstruction of large-scale and high-contrast objects. IEEE Trans Ultrason, Ferroelectr, Freq Control 54(7):1316–1332
Kwon S, Jeong M (1998) Ultrasound inverse scattering determination of speed of sound, density and absorption. In: Proceedings of the IEEE Ultrasonics, Symposium, pp 1631–1634
Lavarello RJ, Oelze ML (2010) Density imaging using a multiple frequency DBIM approach. IEEE Trans Ultrason, Ferroelectr, Freq Control 57(11):2471–2479
Lavarello R, Bond S, Oelze M (2010) Regularized tomographic density imaging using multiple frequency information. In: Proceedings of the IEEE Ultrasonics, Symposium, pp 2336–2339
van Dongen KWA, Wright WMD (2007) A full vectorial contrast source inversion scheme for three-dimensional acoustic imaging of both compressibility and density profiles. J Acoust Soc Am 121(3):1538–1549
Lin J, Chew W (1996a) Ultrasonic imaging by local shape function method with CGFFT. IEEE Trans Ultrason, Ferroelectr, Freq Control 43(5):956–969
Lin JH, Chew WC (1996b) Three-dimensional microwave imaging by local shape function method with CGFFT. In: IEEE antennas and propagation society international. Symposium 3:2148–2151
Lavarello RJ, Oelze ML (2009) Density imaging using inverse scattering. J Acoust Soc Am 125(2):793–802
Lavarello RJ, Oelze ML (2010) Scattering by an arrangement of eccentric cylinders embedded on a coated cylinder with applications to tomographic density imaging. J Acoust Soc Am 127(2):645–648
Waag RC, Fedewa RJ (2006) A ring transducer system for medical ultrasound research. IEEE Trans Ultrason, Ferroelectr, Freq Control 53(10):1707–1718
Johnson SA, Borup DT, Wiskin JW, Natterer F, Wubeling F, Zhang Y, Olsen SC (1999) Apparatus and method for imaging with wavefields using inverse scattering techniques. U.S. Patent 6,005,916
Johnson SA, Abbott T, Bell R, Berggren M, Borup D, Robinson D, Wiskin J, Olsen S, Hanover B (2007) Noninvasive breast tissue characterization using ultrasound speed and attenuation. Acoust Imaging 28:147–154
Wiskin J, Borup DT, Johnson SA, Berggren M (2012) Non-linear inverse scattering: high resolution quantitative breast tissue tomography. J Acoust Soc Am 131(5):3802–3813
Borup DT, Ghandi OP (1985) Calculation of high-resolution SAR distributions in biological bodies using the FFT algorithm and conjugate gradient method. IEEE Trans Microwave Theory Tech 33(5):417–419
Cui TJ, Chew WC (1999) Fast algorithm for electromagnetic scattering by buried 3-D dielectric objects of large size. IEEE Trans Geosci Remote Sens 37:2597–2608
Xu XM, Liu QH (2002) The BCGS-FFT method for electromagnetic scattering from inhomogeneous objects in a planarly layered medium. IEEE Antennas Wireless Propag Lett 1:77–80
Greengard L, Rokhlin V (1987) A fast algorithm for particle simulations. J Comput Phys 73:325–348
Rokhlin V (1990) Rapid solution of integral equations of scattering theory in two dimensions. J Comput Phys 86(2):414–439
Chew WC, Jin J, Michielssen E, Song J (eds) (2001) Fast and efficient algorithms in computational electromagnetics. Artech House, Boston
Michielssen E, Jin J-M (2008) Guest editorial for the special issue on large and multiscale computational electromagnetics. IEEE Trans Antennas Propag 56(8):2146–2149
Harrington RF (1993) Field computation by moment methods. IEEE Press, New York
Saad Y, Schultz MH (1986) GMRES–a generalized minimal residual algorithm for solving nonsymmetric linear-systems. SIAM J Sci Stat Comput 7:856–869
Van der Vorst HA (1992) Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J Sci Stat Comput 13(2):631–644
Coifman R, Rokhlin V, Wandzura S (1993) The fast multipole method for the wave equation: a pedestrian prescription. IEEE Antennas Propag Mag 35(3):7–12
Koc S, Song JM, Chew WC (1999) Error analysis for the numerical evaluation of the diagonal forms of the scalar spherical addition theorem. SIAM J Numer Anal 36(3):906–921
Song J, Chew WC (2001) Error analysis for the trunction of multipole expansion of vector Green’s functions. IEEE Microwave Wirel Compon Lett 11:311–313
Hastriter ML, Ohnuki S, Chew WC (2003) Error control of the translation operator in 3D MLFMA. Microwave Opt Technol Lett 37(3):184–188
Hesford AJ, Waag RC (2010) The fast multipole method and Fourier convolution for the solution of acoustic scattering on regular volumetric grids. J Comput Phys 229:8199–8210
Bebendorf M (2000) Approximation of boundary element matrices. Numerische Mathematik 86:565–589
Zhao K, Vouvakis MN, Lee J-F (2005) The adaptive cross approximation algorithm for accelerated method of moments computations of EMC problems. IEEE Trans Electromagn Compatibility 47:763–773
Shaeffer J (2008) Direct solve of electrically large integral equations for problem sizes to 1 M unknowns. IEEE Trans Antennas Propag 56(8):2306–2313
Hesford AJ, Waag RC (2011) Reduced-rank approximations to the far-field transform in the gridded fast multipole method. J Comput Phys (submitted)
Garland M, Le Grand S, Nickolls J, Anderson J, Hardwick J, Morton S, Phillips E, Zhang Y, Volkov V (2008) Parallel computing experiences with CUDA. IEEE Micro 28(4):13–27
Roy O, Jovanovic I, Hormati A, Parhizkar R, Vetterli M (2010) Sound speed estimation using wave-based ultrasound tomography: theory and GPU implementation. In: Proceedings of the SPIE, vol 7629. pp 76 290J.1–76 290J.12
Wiskin J, Borup D, Johnson S, Berggren M, Robinson D, Smith J, Chen J, Parisky Y, Klock J (2010) Inverse scattering and refraction corrected reflection for breast cancer imaging. In: Proceedings of the SPIE, vol 7629. pp 76 290K.1–76 290K.12
Hesford AJ, Chew WC (2006) A frequency-domain formulation of the Frechet derivative to exploit the inherent parallelism of the distorted Born iterative method. Waves Random Complex Media 16(4):495–508
Haynes M, Moghaddam M (2010) Large-domain, low-contrast acoustic inverse scattering for ultrasound breast imaging. IEEE Trans Biomed Eng 57(11):2712–2722
Andre MP, Janee HS, Martin PJ, Otto GP, Spivey BA, Palmer DA (1997) High-speed data acquisition in a diffraction tomography system employing large-scale toroidal arrays. Int J Imaging Syst Technol 8(1):137–147
Johnson SA, Borup DT, Wiskin JW, Berggren MJ, Zhdanov MS, Bunch K, Eidens R (1997) Application of inverse scattering and other refraction corrected methods to environmental imaging with acoustic or electromagnetic energy. In: Dolic G, Wheeler MJ (eds) Next generation environmental models and computational methods. SIAM, Philadelphia, pp 295–312
Parhizkar R, Karbasi A, Vetterli M (2011) Calibration in circular ultrasound tomography devices. In: Proceedings of the IEEE international conference on acoustics, speech and, signal processing. pp 549–552
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Science+Business Media Dordrecht
About this chapter
Cite this chapter
Lavarello, R.J., Hesford, A.J. (2013). Methods for Forward and Inverse Scattering in Ultrasound Tomography. In: Mamou, J., Oelze, M. (eds) Quantitative Ultrasound in Soft Tissues. Springer, Dordrecht. https://doi.org/10.1007/978-94-007-6952-6_14
Download citation
DOI: https://doi.org/10.1007/978-94-007-6952-6_14
Published:
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-007-6951-9
Online ISBN: 978-94-007-6952-6
eBook Packages: Biomedical and Life SciencesBiomedical and Life Sciences (R0)