Data Structure Assisted Accelerated Reconstruction Strategy for Handheld Photoacoustic Imaging

Abstract

In photoacoustic computed tomography (PACT), advanced model based iterative image reconstruction (MoBIIR) offers several advantages over analytical methods such as back-projection, time reversal, Fourier transform, delay and sum algorithms. However, MoBIIR also shows some disadvantages such as requirement of large storage memory, higher matrix computation time and necessity of selecting optimum parameters for the right solution. When using model based reconstruction methods for high resolution photoacoustic and ultrasound tomography, large matrix computation time is an important concern. In this chapter, we will discuss about filtered back-projection, time reversal methods, F-K migration and a specific model based iterative photoacoustic image reconstruction scheme where the direct non-symmetric photoacoustic system matrix of form $Hx=z$ (where H is m by n matrix and $m>n$) has been analyzed in detail using Least Squared Conjugate Gradient (LSCG) method where the computation of the $H^TH$ and thereafter regularization are explicitly avoided. Apart from this, a unique pseudo-dynamical systems approach based iterative algorithm is also discussed to demonstrate the insensitivity of tikhonov type physical regularization ($\lambda$), which is used frequently in normal equation of form $H^THx = H^Tz$. However, to implement the algorithms, the photoacoustic equation is usually discretized over the spatial and temporal domain to form spatial-temporal interpolated model photoacoustic system matrix (H), where the data structure for sparsity is considered for accelerating the computation and hence the reconstruction. Finally, the applications of algorithms in photoacoustic imaging modality are shown. The computational requirements of different reconstruction strategies suitable for handheld photoacoustic imaging are also analyzed and discussed in detail.

1 Introduction

Parameter recovery based on information carried by radiation has been the essential methodology employed in the development of many valuable tools for medical diagnostic imaging. Examples are the well known X-ray computer assisted tomography (CAT), magnetic resonance imaging (MRI), ultrasonic imaging (USI), positron emission tomography (PET), etc. Each of the above modalities possess certain advantages and some unavoidable disadvantages. For example, the ultrasound based imaging is affordable and uses non-ionizing radiation, but provides images with low soft-tissue contrast and probe-dependent spatial resolution, which does not give useful functional information (for example, the metabolic state of an organ being imaged), especially when the required resolution is below 200–500 mu. Our observation shows that contrast plays a vital role in enhancing the resolution. The MRI provides good quality images which can also give functional information with the administration of external contrast agents, but is prohibitively expensive. To this collection of imaging techniques, photoacoustic computed tomography (PACT) is a recent addition which uses the physics of near infrared (NIR) light for enhancing contrast and principle of ultrasound for improving high resolution in tissue. In PACT, a pulsed light is used for excitation of certain tissue substances and as a result of light absorption, ultrasound signals generation occur in the tissue substances through thermo-elastic phenomena. The process of generating ultrasound with light-matter interaction and use of those light induced ultrasound signals around the object for reconstructing the absorption image of tissue substances altogether is known as photoacoustic computed tomography (PACT). Near-infrared and ultrasound radiation are non-ionizing and therefore both can be repeatedly employed without harm to the patient.

Fig. 1

Reproduced with permission from [1]

Photoacoustic computed tomographic image and ultrasound image in human subject. Comparing the resolution and what wee see in photoacoustic and ultrasound image under rheumatoid arthritis disease in human finger joints.

Photoacoustic phenomena generates a pressure gradient locally within tissue in the ultrasound frequency regime, by the processes of optical absorption and thermoelastic expansion [2, 3]. The physics of photoacoustic wave propagation can be used to map the spatial distribution of light absorption in tissue substances (Fig. 1). Photoacoustic imaging shows clinical level potential in providing deep-tissue high resolution images with optical spectroscopic contrast (Fig. 1). This new imaging modality has several potential clinical applications in cancers [2,3,4,5], inflammatory arthritis [6], diabetes, metabolic rate estimation in healthy as well in disease affected patients. This is also proven clinically (Fig. 1) through the efforts of a number of researchers around the globe [1,2,3,4, 7]. Usually, light with nanosecond (ns) pulse widths illuminates the tissue sample. Ultrasound is produced by the PA effect following absorption of light by tissue substances such as hemoglobin. The pressure waves propagates from high gradient location to low gradient area and the propagated wave can be detected at the tissue surface using ultrasound detectors.

The partial differential equation that models the photoacoustic wave propagation through the acoustically homogeneous medium due to nanosecond pulsed laser irradiance can be described [8, 9] as

$$\begin{aligned} \nabla ^2p(r, t)-\frac{1}{c^2}\frac{\partial ^2p(r,t)}{\partial ^2 t}= -\frac{\beta }{C_{p}}\frac{\partial I(t)}{\partial t} A(r) \end{aligned}$$

(1)

where A(r) is the absorbed thermal energy density generated at position r and time t due to nanosecond pulsed laser irradiance. I(t) is temporal pulsed laser profile. $C_p$ is the isobaric specific heat of the medium, $\beta$ is the isobaric volume expansion coefficient, and c is the acoustic speed. Now if the pulsewidth of the nanosecond laser is much shorter than the stress relaxation time of the tissue like medium then we can write the temporal pulse laser profile I(t) with stress confinement condition [8, 9] as $\delta (t)$. The forward solution of above pressure wave equation can be obtained by the use of Green’s function approach [8, 9] with absorbed energy (A(r)) distribution as;

$$\begin{aligned} p(r, t)= \frac{\beta }{C_{p}}\frac{\partial }{\partial t}\left[ \frac{1}{ct}\int \limits _{R=ct} A(r^{'}) dr^{'}\delta (t-|r'-r|/c)\right] \end{aligned}$$

(2)

The above equation is the pressure propagation equation where the propagation is estimated by spatial-temporal correlated impulse response function $\delta (t-|r-r'|/c)$. The pressure p(r, t) is an integrated pressure over a circle (in 2D) of radius $R=ct$ with a spatial sample width $dr'$. The equation shows that the contribution of the pressure at time t at detector location (r) is only from a circular strep of width $dr^{'}$ at a radial distance ct=$\parallel r'-r\parallel$. Here $r^{'}$ is an arbitrary point in the space where pressure build up occurs due to the photoacoustic effect. Both analytical and model based iterative image reconstruction (MoBIIR) have been developed for solving and modeling Eq. 2 for knowing the initial energy deposition at the site of the tissue substances. To reconstruct the map of total absorbed energy, we will discuss frequently used filtered back-projection and time reversal methods. In addition to the above mentioned algorithms, we will discuss in details about Fourier transform assisted F-K Migration based reconstruction, variants of model based iterative methods such as a specific model based iterative photoacoustic (PA) image reconstruction scheme where the direct non-symmetric PA system matrix of form $Hx=z$ (where H is m by n matrix and $m>n$) has been analysed in detail using Least Squared Conjugate Gradient (LSCG) method where the computation of the $H^TH$ and thereafter regularization are explicitly avoided. Apart from this, an unique pseudo-dynamical systems approach based iterative algorithm is also discussed to demonstrate the insensitivity of tikhonov type physical regularization ($\lambda$), frequently used in normal equation of form $H^THx = H^Tz$. The following sections describe various methods in more details.

2 Analytic Equation Based Algorithms

2.1 Filtered BackProjection Based PACT Imaging

Notable among the algorithms used for solving Eq. 2 are the analytic algorithms based on filtered backprojection (BP) [3, 10] in the time-domain, which assume that the measured data is a Radon Transform of the object function. The algorithms are easy to apply for planar, cylindrical and spherical geometries [11]. A drawback of this method is that it requires a full-view of object with a high number of projections, and does not provide quantitative solution.

Following are the steps to reconstruct the source image using the back projection algorithm in photoacoustic tomography. The original photoacoustic source, recorded signal and their amplitude,time graph and reconstruction with backprojection are presented conceptually in Fig. 2a–c

• 1. Start recording photoacoustic signals when t = 0.0 by using ultrasound detector, as shown in Fig. 2a

• 2. Filter the signal as per the interest and then extract the time of flight details from the signal, as shown in Fig. 2b

• 3. Drawing a circle by taking a detector position as its center and its time of flight data as the radius(calculated using c = speed of sound), as shown in Fig. 2c

• 4. Repeating this for each detectors, as shown in Fig. 2c.

Fig. 2

Backprojection’s conceptual presentation through visual graphs

Backprojection or filtered backprojection is widely used in qualitative photoacoustic image reconstruction due to its simplistic approach, ease of implementation and speed suitable for quasi real time PA imaging. Downside of this method is that it does not provide quantitative information.

2.2 Time Reversal Based PACT Imaging

In Time reversal (TR) approach, image reconstruction is performed by numerically propagating the recorded data in reversed temporal order back into the domain [12, 13]. When $t = 0$ is arrived, the initial pressure distribution is recovered. The advantages of the algorithm are that it can be applied to arbitrarily shaped measurement surfaces, and has generally been described to be the least sensitive PA algorithm to restrictions [12]. The method is also gaining its popularity due to the availability of a free third party MATLAB toolbox, which performs the time reversal image reconstruction using k-space methods [12]. The drawback of the TR approach lies in the requirement for the time-reversed waves to traverse the entire domain from detector coordinates which may entail unnecessary computations in regions which hold little interest. In cases when the propagation model assumes acoustic homogeneity while the measurement domain has unknown variations in density and speed-of-sound, image artifacts can result from the phenomenon of artefact trapping [14]. TR method needs large number projections to obtain high resolution images [12]. Time reversal conceptual presentation is shown in Fig. 3.

Fig. 3

Time reversal’s conceptual presentation. a Represent source and the array detector location in space, b recorded signal’s amplitude at linear detector array as per the arrival time at their correspond detector locations, c–e shows reversed temporal order back into the spatial domain at three different times

Figure 3a represents source and the array detector location, Fig. 3b shows recorded signal’s amplitude at linear detector array as per the arrival time at their correspond detectors’ spatial locations. Figure 3c–e shows reversed temporal order back into the spatial domain at three different time samples.

2.3 F-K Migration Based PACT Imaging

Fourier transform can be used to migrate the wave field as per the amplitude and phase. Originally, migration technique is developed based on the reflecting source model which assumes that all the field scatterers generate secondary acoustic sources. The main aim of migration is to reconstruct the secondary source position. Under the plane wave model, the scattering source estimation problem can be made suitable for plane wave imaging by a spatial transformation (F-K) of the hyperbolic traces present in the raw data. To produce an image of the scatterers, all the hyperbolas must be migrated back to their apexes. However, the advantage of migration technique is that it improves focusing by use of amplitude and phase rectifications where the correction is done for the effects of spreading of ray paths as the waves propagate. This technique has been used as a basic tool in geophysics since the 1950s [15].

F-K migration takes back the recorded US signal to that time at which the wave emerges out of the secondary source. It was first developed by Stolt in 1978 for B scan seismic imaging [15]. Later, it was developed for plane wave ultrasound imaging by Garcia in 2014 [16]. This algorithm is limited by the assumption of constant wave velocity [16]. However, its fastest computation time makes it suitable for real-time ultrasound imaging and same is true for photoacoustic imaging because both imaging modality uses raw ultrasound data. The assumption to neglect the downward going waves exactly matches with the PACT. Whereas, in plane wave ultrasound imaging we have to fit the travel time with the exploding reflector model as shown in Fig. 4.

Fig. 4

x-z plane, where linear transducer is placed on the x axis and reflector in x-z plane. The arrows represents the direction of propagation

In plane wave imaging, all the transducer elements emit the ultrasound at the same time to generate a plane wave. The plane wave proceeds towards the transducer and interacts with the reflector surface. After the interaction, the reflector(at $S(s_x,s_z)$, see Fig. 4) becomes the secondary source and starts to emit radially outwards. usually the reflected signal is recorded by the linear transducer. The travel time of the wave, varying with the detector position(x), is given below:

• For exploding reflector model:

  $$\begin{aligned} \hat{t(x)} = \frac{1}{\hat{c}}\sqrt{(\hat{s_x} - x)^2 + (\hat{s_z} - z)^2} \end{aligned}$$

  (3)

• For plane wave ultrasound imaging:

  $$\begin{aligned} t(x) = \frac{1}{c}\bigg (s_z + \sqrt{(s_x - x)^2 + (s_z - z)^2} \bigg ) \end{aligned}$$

  (4)

• For plane wave photoacoustic imaging:

  $$\begin{aligned} t(x) = \frac{1}{c}\sqrt{(s_x - x)^2 + (s_z - z)^2} \end{aligned}$$

  (5)

In order to use F-K migration in PWI we need to fit its travel time equation with the exploding reflector model. However, doing so is an unachievable task. Due to the dependency of wave amplitude with distance, most of the its energy is located at the apex of the hyperbola. By equating the 0th–2nd order derivative of the Eqs. 3, 4 and 5 we can find out approximate fitting parameters. It yields $\hat{c} = \frac{c}{\sqrt{2}}$ and $\hat{s_z} = \sqrt{2}s_z$ for plane wave ultrasound imaging [15] and $\hat{c} = c$ and $\hat{s_z} = s_z$ for photoacoustic imaging.

Lets assume that $\Psi (x,z,t)$ is the scalar wavefield that is a solution to

$$\begin{aligned} \nabla ^{2}\Psi - \frac{1}{c}\frac{\partial ^{2}}{\partial t^{2}}\Psi = 0 \end{aligned}$$

(6)

We know the scalar wavefield at $z = 0$, time t. We need to know the scalar wavefield at distance z at time $t = 0$ i.e. $\Psi (x,z,t=0)$ (see Fig. 4).

The Fourier transform of $\Psi (x,z,t)$ in the $(k_x, f)$ spectrum is defined in the following way:

$$\begin{aligned} \Psi (x,z,t) = \int \!\!\!\!\int \limits _{-\infty }^{\infty }\phi (k_x, z, f) e^{2\pi \iota (k_x x - ft)}dk_x df \end{aligned}$$

(7)

Now substituting Eqs. (7) in (6) we get

$$\begin{aligned}&\nabla ^{2}\Bigg [ \int \!\!\!\!\int \limits _{-\infty }^{\infty }\phi (k_x, z, f) e^{2\pi \iota (k_x x - ft)} dk_x df \Bigg ] \nonumber \\&\quad - \frac{1}{c}\frac{\partial ^2}{\partial t^2} \Bigg [ \int \!\!\!\!\int \limits _{-\infty }^{\infty }\phi (k_x, z, f) e^{2\pi \iota (k_x x - ft)}dk_x df \Bigg ] = 0 \end{aligned}$$

(8)

These derivatives can easily be taken inside the integral and can be evaluated to get

$$\begin{aligned} \int \!\!\!\!\int \limits _{-\infty }^{\infty } \Bigg [\frac{\partial ^{2} \phi (k_x,z,f)}{\partial z^2} + 4 \pi ^2 \Big [\frac{f}{c^2} - k_x^2 \Big ]\phi (k_x,z,f) \Bigg ] e^{2\pi \iota (k_x - ft)}dk_xdf = 0 \end{aligned}$$

(9)

The left hand side of Eq. (9) is the Fourier transform of the terms in the square bracket in Eq. (9). Now since its right hand side is equal to zero, the function will also be equal to zero.

$$\begin{aligned} \frac{\partial ^2}{\partial z^2}\phi (z) + 4\pi ^2k_z^2\phi (z) = 0 \end{aligned}$$

(10)

where,

$$\begin{aligned} k_z^2 = \frac{f^2}{v} - k_x^2 \end{aligned}$$

(11)

Fig. 5

Various steps for implementing F-K migration and photoacoustic image reconstruction strategies

Now we have formulated the problem in the $(k_x, f)$ domain i.e. is a Fourier domain of (x, t). The boundary condition is now the Fourier transform of $\Psi (x,z = 0,t)$ over (x, t) i.e. $\phi (k_x,z = 0,f)$. Since, Eq. (10) is a second order differential equation, its unique general solution can be written as

$$\begin{aligned} \phi (k_x,z,f) = A(k_x,f)e^{2\pi \iota k_z z} + B(k_x,f)e^{-2\pi \iota k_z z} \end{aligned}$$

(12)

where $A(k_x,f), B(k_x,f)$ are to be determined from the boundary condition. It is important to note that in Eq. (12) the two terms can be interpreted as the upgoing ($B(k_x,f)e^{-2\pi \iota k_z z}$) and downgoing($A(k_x,f)e^{2\pi \iota k_z z}$) wavefield (Fig. 5).

Since, we only have one boundary condition, i.e. $\phi (k_x,z = 0,f)$, in order to solve the problem we have to assume a limited model which assumes waves propagating in one direction only. This means that

$$\begin{aligned} A(k_x,f) = 0, \quad B(k_x, f) = \phi (k_x, z=0, f) \end{aligned}$$

(13)

Substituting (13) in (12) we get

$$\begin{aligned} \phi (k_x, z, f) = \phi (k_x, z=0, f)e^{-2\pi \iota k_z z} \end{aligned}$$

(14)

Substituting (13) solution in (7) we get

$$\begin{aligned} \Psi (x,z,t) = \int \!\!\!\!\int \limits _{-\infty }^{\infty }\phi (k_x, z=0, f) e^{2\pi \iota (k_x x -k_zz- ft)}dk_x df \end{aligned}$$

(15)

Now migrating (15) from time t to $t=0$ we get our migrated solution

$$\begin{aligned} \Psi (x,z,t=0) = \int \!\!\!\!\int \limits _{-\infty }^{\infty }\phi (k_x, z=0, f) e^{2\pi \iota (k_x x -k_zz)}dk_x df \end{aligned}$$

(16)

This solution has a disadvantage that it is not an inverse Fourier transform of function $\phi (k_z,z=0,f)$. Stolt in 1978 suggested a change of variable from $(k_x,f)$ to $(k_x, f(k_z))$ to make the migrated solution an inverse fourier transform of $\phi (k_x,z=0,f(k_z))$. The variable change is defined by Eq. (11) which then can be solved for f as:

$$\begin{aligned} f = c \times \root \of {k_x^2 + k_z^2} \end{aligned}$$

(17)

$$\begin{aligned} \implies df = \frac{ck_z}{\root \of {k_x^2+ k_z^2}}dk_z \end{aligned}$$

(18)

Now substituting (17) and (18) in (16) we get

$$\begin{aligned} \Psi (x,z,t=0) = \int \!\!\!\!\int \limits _{-\infty }^{\infty } \frac{ck_z}{\root \of {k_x^2+ k_z^2}}\phi (k_x, z=0, f(k_z)) e^{2\pi \iota (k_x x -k_zz)}dk_x dk_z \end{aligned}$$

(19)

Fig. 6

Comparing the reconstruction methods through visual perception and computed time

We have seen that the new FFT-based F-K migration determines the wavefield at the time of start that is $t=0$. Advantage of the F-K migration is that it uses few mapping and FFT techniques which makes it faster for real time imaging. The reconstructed images with backprojection (Fig. 6a), time reversal (Fig. 6b) and F-K migration (Fig. 6c) are compared visually and also based on the computation time. For computation we have used a PC with Intel(R) Core(TM) i7-6700 CPU @ 3.40 GHz, DDR4 RAM: 32 GB. The computation time for reconstructing images using BP is 2.6 s, TR is 99.3 s and for F-K migration it is 1.14 s.

3 Model Based Iterative Image Reconstruction Algorithms

Due to constant demand for quantitative and high resolution photoacoustic imaging, model based algorithms are gaining importance. In model based iterative image reconstruction (MoBIIR) methods, algebraic and matrix methods within an iterative framework are used to minimize the residue between the model-generated data and measured data. To implement the MoBIIR algorithms, first we shall discretize Eq. 2 and formulate forward model in such a way that it serves to model PA wave propagation [17,18,19,20,21,22] and relate the spatially discretized initial pressure distribution to the acquired signals. Such an approach lends itself to application of algebraic and matrix methods within an iterative framework, for image reconstruction. Now by shifting $r^{'}$, in Eq. 2, we find a new t and then corresponding integrated pressure at a new radial distance. So a spatial and temporal (spacetime) matrix H can be formed by shifting the position $r^{'}(i,j)$ over the discretized space for a series of sample time $t_k$ and then estimate the boundary pressure ($z_{r_d,t_k}$) at detector location $r_d$. The deposited energy A(r) can be expressed over a discretized spatial domain ($\Omega \in$ R $^{2}$, r,$r^{'}\in \Omega$) as A(i, j). Spatially correlated temporal impulse term for a sampled time, $t_k$ over space $r_{i,j}$ can be written as $h(t_k-|r^{'}-r_{i,j}|/c_{i,j})\simeq \delta (t-|r'-r|/c)$. The boundary pressure estimation forward problem can be formulated (assumed $\eta =\frac{\beta }{C_{p}}\frac{\partial }{\partial t}$) from Eq. 2 over discretized spatial-temporal domain as,

$$\begin{aligned} z_p(r_d, t_k)= \eta \sum _{i,j} \Big \{\int \limits _{R=ct}\frac{1}{c_{i,j}t_k}\times h(t_k- |r_{d}-r^{'}_{i,j}|/c_{i,j}) dr^{'}\Big \}A(i,j) \end{aligned}$$

(20)

A series of constant time samples ($t_k=k$/$f_{s}$, where $k=1 \ldots m$) are considered and h(t) is evaluated over space ($r_{i,j}\leftrightarrow r^{l}$) to form the propagation system matrix H. The simplified form of pressure propagation equation can be written with system matrix H and initial pressure vector $x_{A}^{l}$ ( with $\beta$ =1, $C_p$=1) as;

$$\begin{aligned} z_p(r_d, t_k)= \eta \sum _{l,k}H(t_k,r^{l})x^{l}_A \end{aligned}$$

(21)

where the initial pressure vector ($x_A^{l}$) is formed from energy absorption matrix A(i, j). The propagation system matrix H is formed with h(t) and its interpolated value around the sampled time $t_k$. The forward photoacoustic projection integral is computed as shown in Algorithm 1.

The PA forward problem (Eq. 21) with system matrix H can be written in matrix multiplication form as;

$$\begin{aligned} z_p= Hx_A \end{aligned}$$

(22)

where $z_p$ is measurement vector ($z_p\in \mathbb {R}^m$), H is the system matrix ($H\in M_{m\times n}(\mathbb {R}$) where $m>n$) which model the propagation of PA signal and the vector $x_A$ ($x_A\in \mathbb {R}^n$) represents initial pressure rise. A photoacoustic reconstruction algorithm is used to solve the PA inversion problem, that is to recover an image of the initial pressure rise distribution $x_A$ inside the tissue from $z_p$, the noisy PA signals measured at tissue boundary. The photoacoustic pressure $z_p$ at boundary is obtained by integrating pressure over a constant sampled time points with linear interpolated coefficients.

The solution is obtained with minimizing the residue between the model-generated ($Hx_A$) data and measured data ($z_p$) by iterations. The minimization function [17,18,19,20,21,22] for iterative method can be written as;

$$\begin{aligned} \chi = \arg \min _{\chi } \parallel z_{p} - Hx_A \parallel ^{2} \ + \lambda \parallel x_A\parallel ^{2}\ \end{aligned}$$

(23)

where $\lambda$ is a regularization parameter to stabilize the ill-condition of the system matrix in normal equation. The minimization equation (Eq. 23) with Gauss-Newton scheme lands to the normal equation [21, 22] required to be solved is then of the form;

$$\begin{aligned}{}[H^T H+I\lambda ]x_A=H^Tz_p \end{aligned}$$

(24)

The normal equation for photoacoustic inverse problem can be solved with variant of regularization schemes. The simplest regularization selection method is L-Curve method where a series of regularization set is formed and the best one which minimizes the residue is chosen. However, Dean-Ben et al. [21] has used a least squares QR (LSQR) based regularized reconstruction method where the direct solution vector from full view data is used as regularization and shown an added advantage of being highly efficient. Inversion of limited-view data is stabilized using Tikhonov or Total Variation regularization [17, 19,20,21,22,23] which require explicit selection of an optimal regularization parameter. Recently, Shaw et al. [22] presented a regularization optimization scheme based on LS-QR decomposition which shows good performance and computational efficiency with reconstruction time of 444.9 s.

In order to achieve high accuracy with flexibility in using limited-view data, H should be a highly discretized large system matrix. Further, the matrix H is transposed to form a square matrix $[H^T H+I\lambda ]$ and the inverse is computationally expensive, requiring large memory storage. $H^TH$ is often dense even when H is sparse [24]. Further, if H is ill-conditioned then the $H^TH$ is more ill-conditioned since its condition number is the square of the condition number —$\{\kappa (H)\}^2$ [24, 25]. One of the challenging issues of iterative PA imaging is to balance the trade-off between the computational efficiency of the reconstruction algorithms and the resolution of reconstructed images.

To avoid the regularization selection and explicit formulation of $H^{T}H$, non-symmetric system matrix equation (Eq. 22) can be solved by least squared CGS method. The steps for solving the non-symmetric PA system matrix are shown in Algorithm 2.

It can be noticed that the inverse Algorithm 2 explicitly avoids calculation of $H^{T}H$. The main aim of the algorithm is to estimate the residual $z_p-Hx$ and then multiply it by $H^T$ rather than subtracting $H^{T}Hx_A$ from $H^{T}z_p$. The algorithm 2 uses few simple vector multiplications and additions which helps to execute it faster due to use of the sparsity property of H and $H^T$.

3.1 Symmetry Conjugate Gradient Search (CGS) and Least Square Conjugate Gradient Search (LSCGS) Based Reconstruction

It is clear from several studies [17, 19,20,21,22,23] that symmetric normal equation is commonly used to model the photoacoustic reconstruction strategies and it is considered as a starting platform for adding various type of regularization and improving the reconstruction thereafter. Main goal of the inverse problem is to compute the eigenvalues of normal equation $H^THx$=$H^Tz_p$ or in other suitable mathematical form. Symmetric CG algorithm can be applied to the normal equation either from $[H^T H+I\lambda ]x_A=H^Tz_p$ explicitly or simply extending it through applying vector multiplications on $H^T$ and H in succession. By applying vector multiplication on $H^T$ and H in succession, we can avoid formulating matrix $H^TH$ which will generally be dense even when H is sparse. Formulating the normal equation ( $H^TH$) from data structure assisted formulated sparse rectangular matrix (H or $H^T$) does not solve the problem where the condition number of $H^TH$ is the square of the condition number of H and, it loses the sparsity which increase the required storage memory for $H^TH$. However, conjugate gradient algorithms use the matrix and matrix-vector multiplications only. So it is not mandatory to form the matrix $H^TH$ which leads to cancellation or loss of sparsity. Due to serious amplification of the spectral condition number (as it is squared), it introduces error in eigenvalues. The idea of least-squares CG was originally proposed by Hestenes and Stiefel [26] and, later it came to be known as CGLS which involves vector computing terms of the form $H^T$($Hx - H^Tz_p$) instead of $H^THx - H^Tz_p$. The difference between the two methods is entirely the rounding error, which is important in practical problems where sparsity of the large matrix need to be preserved for fast computing.

However, in the non-symmetric case, as it is shown in algorithm 2, all previous search directions are used in order to calculate a new approximation and the rate of convergence is determined by the Krylov sequence $Hr^0$, $H^2r^0$ and for symmetric CGS method, the rate of convergence is determined by $(H^TH)Hr^0$,$(H^TH)^2Hr^0, \ldots$ as it would have been the case if the normal equations had been used. Here r is the residue.

3.2 Pseudo-dynamical Systems Approach for PACT Imaging

A regularization-insensitive route to computing the parameter updates using the normal equations (Eq. 21) is to introduce an artificial time variable [23, 27,28,29]. Such pseudo-dynamical systems, typically in the form of ordinary differential equations (ODE-s), may then be integrated and the updated parameter vector is recovered once when either a pseudo steady-state is reached or a suitable stopping rule is applied to the evolving parameter profile (the latter being necessary if the measured data is limited and noisy). Indeed, it has been shown [23, 28,29,30] that the well known Landweber iterations correspond to an explicit Euler time discretization of the pseudo-time ODE-s for the Gauss-Newton’s updates (Eq. 21) and appear to exhibit a self-regularization character depending upon the pseudo time step. This is also desirable in view of the fact that the addition of the regularization term alters the minimization problem which we are trying to solve. Moreover, if one adopts an explicit pseudo-time integration scheme for the ODE-s, an explicit inversion of the discretized (linear case) operator in the normal equation for PA can be avoided. This is the best feature of this method which has several advantages when dealing with singularity and rank deficiency issues.

Here, we will develop a concept of solving the optimized normal equation for photoacoustic problem as it was said in previous paragraph. The normal form of minimized photoacoustic equation can be further simplified with a notion of $A=H^TH$ and $b=H^Tz_p$. The optimized system of linear or non-linear equation (Eq. 21) of many physical, biological, and economic processes can be expressed in a generalized form as,

$$\begin{aligned} Ax=b \end{aligned}$$

(25)

where $A\in \mathbb {R^{\mathbf {N}\times \mathbf {N}}}$ is a state companion matrix (for PAT, A = $H^{T}H+ \lambda I$), $b\in \mathbb {R^{\mathbf {N}\times \mathbf {m}}}$ ($b =H^{T}z_p$ in our case) is the constant force matrix and $x\in \mathbb {R^{\mathbf {N}\times \mathbf {1}}}$ is the unknown solution vector (x). Since $e^{tA}$ and $e^{tA}\mu _{0}$ are solutions of ordinary differential equations, it is natural to consider methods based on numerical integration. For an example, in a simple case, we solve a homogeneous matrix differential equation such as $Ax=0$ with an introduced fictitious time at steady state as $\dot{x}(t)=Ax(t)$ describing the evolution of the system on pseudo time. With an initial condition $x(t=0)=x_{0}$, the solution would be of form $e^{tA}x_{0}$. The solution of Eq. 25 can be obtained without inverting the square matrix A. In principle, the solution is obtained from $x(t) = e^{tA}x_{0}$ and can be formally defined by the convergent power series as,

$$\begin{aligned} e^{tA}x_{0}=Ix_{0}+tAx_{0}+\frac{t^{2}A^2x_{0}}{2!} + \cdots + \cdots \end{aligned}$$

(26)

Generally, A is large, dense and non-sparse (in some cases, partially sparse A is observed) due to formulation of normal equation from the sparse matrix with its own transpose form. In particular the system of ordinary differential equation arises from the spatial discretization of a partial differential equation. Typically $e^A$ is dense even if A is sparse, we would like to compute this in an iterative way. The iterative methods are used for sparse matrix problems where only matrix vector products are needed. A powerful class of methods that are applicable to many problems are the Krylov space methods [31, 32], in which approximations to the solution are obtained from the Krylov spaces spanned by the vectors $\{x_{0}, Ax_{0}, A^2x_{0}, \ldots , A^{m}x_{0}\}$ for some ‘m’ that is typically small compared to the dimension of A. The Lanczos method [33] for solving symmetric eigenvalue problems is of this form and for non-symmetric matrices the Arnoldi iteration [33] can be used. In this method the eigenvalues of a large matrix are approximated by the eigenvalues of a Hessenberg matrix of dimension ‘m’.

Now, we will show how to form a pseudo-dynamic time integral equation of minimized system Eq. 26 of form $Ax+b=0$. The steady state equation of $Ax+b=0$ (obtained from Eq. 26) with a fictitious time can be written as time derivative form,

$$\begin{aligned} \dot{x}(t)&=A x(t) + b(t). \end{aligned}$$

(27)

Multiplying by factor of $e^{-At}$ throughout and integrating, we obtain

$$\begin{aligned} e^{-At}\dot{x}(t)- e^{-At}A x(t)=e^{-At}b(t) \end{aligned}$$

(28)

$$\begin{aligned} e^{-At}\dot{x}(t)- A e^{-At}x(t)=e^{-At}b(t) \nonumber \\ \frac{d (e^{-At}x)}{d t} = e^{-At}b(t) \end{aligned}$$

(29)

Now integrating the above equations in [$t, t+\Delta t$ ] with initial boundary condition $x(t)=x^{*}$, we obtained the pseudo-dynamic time integration equation for updating the solution vector with $f(s)= A(x^{*})x^{*} - b$ as,

$$\begin{aligned} x(t+\Delta t) = e^{A\Delta t}x^{*} + \int \limits ^{t+\Delta t}_{t} e^{A(t+\Delta t-s)}f(s)ds \end{aligned}$$

(30)

which converges to $\hat{x}$ as $t \rightarrow \infty$. Note that we have assumed A is square and positive definite. Following the concept of local linearization [29], the linearization point $t=t^{*}$ (such that $x^{*} := x(t)^{*}$) could be chosen anywhere in the closed interval [$t, t + \Delta t$] without affecting the formal error order. While choosing $t=t^{*}$ yields the explicit phase space linearization (PSL) [29], $t=t^{*}$ results in the implicit locally transversal linearization (LTL) [34]. Denoting $h_d$ = $t_{k+1} - t_{k}$ to be the time step and $x_{k} := x(t_{k})$, the explicit PSL map corresponding to the continuous update Eq. 30 is written as:

$$\begin{aligned} x_{k+1} = e^{A(t_{k+1}-t_{k})}x_{k} + \int \limits ^{t+\Delta t}_{t} e^{A(t_{k+1}-s)}f(s) ds \end{aligned}$$

(31)

An explicit strategy for obtaining the parameter updates via a semi-analytical integration of the pseudo-dynamic linear equation is proposed in this chapter. Despite the ill-posedness of the inverse problem associated with photoacoustic computed tomography, adoption of the first derivative update scheme combined with the pseudo-time integration appears a muted sensitivity to the regularization parameter which includes the pseudo-time step size for integration (Fig. 7).

Fig. 7

Reconstructed with forward model generated data which were detected with a line detector of 128 sensors placed at y = 14.5 mm. Original image is shown in (a), noisy signal is shown in (b). The reconstruction are carried out by c BP method, d L-Curve method with regularization (0.001), e L-Curve method without (near zero, 0.000001) regularization, f LSCGS method, g pseudo dynamic approach with Tikhonov type physical regularization (0.001), h pseudo dynamic approach with negligible (near zero, 0.000001) Tikhonov type physical regularization

A digital numerical phantom with two holo circular shape photoacoustic emitting sources is considered to be embedded in a surrounding medium of size 20 $\times$ 20 mm and the medium is discretized with 100$\,\times \,$100 square grids where the size of each pixel is 20.0 $\upmu$m. The initial pressure rise is assumed to be 1 kPa to the both local shapes and 0 kPa pressure for the background medium. The speed of sound (c = 1500 m/s) is taken to be uniform all over the simulated domain. Numerically generated data with 128 detectors and data are corrupted with 40% random noise.

For computation we have used a PC with Intel(R) Core(TM) i7-6700 CPU @ 3.40 GHz, DDR4 RAM: 32 GB. The computation time was found to be 0.3 s for BP, more than 8000.3 s for pseudo dynamic system approach, 51.8 s for L-Curve method with regularization, 128 s for L-Curve method without regularization, and 1.5 s for LSCGS method. Selection of time step in pseudo dynamic system is one of the drawback where computation time depends on the time step size. As the time step size reduces, the computation time increases due to increase of iteration for smooth solutions.

4 Numerical Phantom Experiment

Phantoms (physical or numerical) are of paramount importance to evaluate the performance of reconstructed photoacoustic tomographic image either in experiment or in simulation model. The test objects were developed with the aim of providing known ground truths with complexity approaching the level of the context in which the imaging and reconstruction is intended for. For all cases, a numerical phantom with rectangular shape and circular shape photoacoustic emitting source is designed and simulations are performed.

A digital numerical phantom with rectangular shape and circular shape photoacoustic emitting source were considered to be embedded in a surrounding medium of size 30 $\times$ 30 mm and the medium is discretized with 2048 $\times$ 2048 square grids where the size of each pixel is 14.6 $\upmu$m. The initial pressure rise is assumed to be 1 kPa to the both local shapes and 0 kPa pressure for the background medium. The speed of sound (c = 1500 m/s) is taken to be uniform all over the simulated domain. Figure 8 shows simulated phantom, detector orientation and the pressure variation over the domain. We have considered almost discrete helical shape detector array orientation for getting very low number of linearly dependent algebraic equations in the measurement sets. Numerically generated data are corrupted with 40% random noise.

Fig. 8

Photoacoustic experimental set up for side illumination and the experimentation with ultrasound array detector

The image is reconstructed with full view where total number of projection is 12 and total number of detectors in the measurement is 384. Measurement data expands around 0$^{\circ }$–360$^{\circ }$ of phantom surface. The images are reconstructed with (a) TR method, (b) BP method, (c) L-Curve method, (d) proposed LSCGS method and their corresponding images are shown in Fig. 9.

Fig. 9

Reconstructed with forward model generated 12 projections (half view, 384 detectors) data expands around 0$^{\circ }$–180$^{\circ }$ of phantom surface. The reconstruction are carried out by a TR method, b BP method, c L-Curve method, d proposed LSCGS method

The image is reconstructed with half view where total number of projection is 6 and total number of detectors in the measurement is 192. Measurement data expands around 0$^{\circ }$–180$^{\circ }$ of phantom surface. The images are reconstructed with (a) TR method, (b) BP method, (c) L-Curve method, (d) proposed LSCGS method and their corresponding images are shown in Fig. 10.

Fig. 10

Reconstructed with forward model generated 6 projections (half view, 192 detectors) data expands around 0$^{\circ }$–180$^{\circ }$ of phantom surface. The reconstruction are carried out by a TR method, b BP method, c L-Curve method, d proposed LSCGS method

5 Discussion and Conclusions

Here we have shown several reconstruction schemes where the motivation was to develop or implement a suitable algorithm for real time handheld photoacoustic imaging. Analytic equation based reconstruction strategies are quite simple, fast and provide reasonably acceptable results though it faces challenging drawbacks due to quantification which can be addressed with well defined reference and standardization. Model based iterative reconstruction algorithm that permits to solve a non-symmetric matrix ($H\in M_{m\times n}(\mathbb {R}$) where $m>n$) without explicit formation of $H^TH$ and regularization can be used to obtain the photoacoustic solution of large system matrix. It is shown that this procedure is computationally simple and gives reasonably good results in terms of computation and resolution. It achieves low computation time by explicitly avoiding the computation of $H^TH$ and regularization. A major advantage of the proposed method is that it takes less memory compared to the normal equation and is fast in execution compared to the time reversal methods, but slower than backprojection. Computation time and memory requirement for conventional image reconstruction methods and certain new inversion algorithms were studied in detail using numerical phantoms. The computation details have been shown for both limited view data and full view data when a considerable Gaussian random noise is added to simulated boundary measurements. The resolution of non-symmetric system matrix inversion with LSCGS method can be further improved with suitable interpolation scheme which may introduce larger computation time and this needs further investigation. A new class of reconstruction strategy with pseudo-dynamic scheme has been discussed using normal equation where we showed the way to avoid direct inversion of the system matrix and makes it tikhonov type regularization free.

The total reconstruction computation time with 220 $\times$ 220 grid points, 80 MSPS sampling rate for back projection is 2.46 s and it used 3 GB memory, time reversal took 1405.4 s and used 2.8 GB memory, L-Curve based normal equation method took 6510.6 s and used 59.8 GB memory, non-symmetric matrix inversion took 7.4 s and used 4.5 GB memory, when half view data is considered. When full view data is considered the computation time with back projection is 4.22 s and it used 3 GB memory, time reversal took 1411.4 s and used 2.9 GB memory, L-Curve based normal equation method took 4588.6 s and used 59.9 GB memory, non-symmetric matrix inversion took 17.2 s and used 5.3 GB memory. The computer used has Processor: Xenon(R) CPU @2.67 MHz, 60 GB RAM).

The most formidable difficulty in crossing over to a full-blown 3D problem is the disproportionate increase in the parameter vector dimension (a typical tenfold increase) compared to the data dimension where one cannot expect an increase beyond two to three folds [35]. Thus, if 3D iterative image reconstruction algorithms are used, they would require implementation on highly parallelized processing architectures as in graphics processing units (GPUs) [36]. However, considering resolution and computation time, real time imaging may be possible with F-K migration based reconstruction both for 2D and 3D imaging, provided some calibration is performed for gathering quantitative information. Getting quantitative information from F-K migration method is still a debatable subject. However, combination of F-K migration and accelerated model based imaging may solve the purpose, where F-K migration will provide real time imaging capability and accelerated model method will quantify the parameters.