3-D reconstruction of the coronary artery tree from multiple views of a rotational X-ray angiography

Abstract

To present an efficient and robust method for 3-D reconstruction of the coronary artery tree from multiple ECG-gated views of an X-ray angiography. 2-D coronary artery centerlines are extracted automatically from X-ray projection images using an enhanced multi-scale analysis. For the difficult data with low vessel contrast, a semi-automatic tool based on fast marching method is implemented to allow manual correction of automatically-extracted 2-D centerlines. First, we formulate the 3-D symbolic reconstruction of coronary arteries from multiple views as an energy minimization problem incorporating a soft epipolar line constraint and a smoothness term evaluated in 3-D. The proposed formulation results in the robustness of the reconstruction to the imperfectness in 2-D centerline extraction, as well as the reconstructed coronary artery tree being inherently smooth in 3-D. We further propose to solve the energy minimization problem using α-expansion moves of Graph Cuts, a powerful optimization technique that yields a local minimum in a strong sense at a relatively low computational complexity. We show experimental results on a synthetic coronary phantom, a porcine data set and 11 patient data sets. For the coronary phantom, results obtained using different number of views are presented. 3-D reconstruction error evaluated by the mean plus one standard deviation is below one millimeter when 4 or more views are used. For real data, reconstruction using 4 to 5 views and 256 depth labels averaged around 12 s on a computer with 2.13 GHz Intel Pentium M and achieves a mean 2-D back-projection error of 1.18 mm (ranging from 0.84 to 1.71 mm) in 12 cases. The accuracy for multi-view reconstruction of the coronary artery tree as reported from the phantom and patient studies is promising, and the efficiency is significantly improved compared to other approaches reported in the literature, which range from a few to tens of minutes. Visually good and smooth reconstruction is demonstrated.

Introduction

Cardio-vascular disease (CVD) is responsible for more than one-third (36.3%) of total deaths in the United States in 2004 [1]. The gold standard for diagnosis of CVD is X-ray coronary angiography, which are 2-D projection images of the complex coronary artery tree. Therefore, a significant amount of 3D information of the underlying coronary arteries is lost by the 2-D projection simplification. Traditionally, several angiographic views are taken from different angles and then are selected subjectively based on the cardiologist’s experience, to minimize foreshortening and vessel overlap. However, this associates with high intra-observer variability and increased radiation/contrast injection. Green et al. [2] found that vessel shortening was markedly greater in expert-recommended views than in computer-generated views.

It has been quantitatively evaluated in [3, 4] that 3-D reconstruction of coronary arteries from 2-D angiography permits accurate, reproducible and quantitative assessment of the 3-D geometric properties of coronary arteries, including diameter statistics, length, volume, angles at vascular branching points and tortuosity of vessels. In [5, 6], it is demonstrated that 3-D reconstruction of traditional coronary angiography allows for direct 3-D measurement of the lesion length and hence is a promising technique to optimize the choice of drug-eluting stents (DES) length and to reduce the number of stents used during percutaneous coronary intervention (PCI). 3-D symbolic model of the coronary artery tree can further guide clinicians to choose the optimal patient-specific views that minimize vessel overlap and foreshortening [2, 7–9], and provides the magnification factor of the vessel for the estimation of the lumen diameter in 3-D (e.g. for lumen narrowing analysis) [10, 11]. Furthermore, the static 3-D symbolic reconstruction at a given cardiac phase is a critical step in modeling the dynamics and shape changes of coronary arteries during a cardiac cycle [12–14]. It is also an indispensable step in generating a full vessel 3-D model for stenosis detection and analysis by subsequent tomographic reconstruction. In [15, 16], the 3-D symbolic reconstruction was utilized for cardiac and/or breathing motion estimation and subsequent compensation throughout the rotational sequence before tomographic reconstruction was applied. In [17], 3-D centerline extraction and motion-correction of 2-D projections were performed simultaneously and optimized iteratively.

3-D symbolic reconstruction of coronary arteries from angiographic images was investigated using two projections [3–5, 8, 9, 11, 18, 19], either from a fixed biplane system, or from different projections on a monoplane C-Arm. Biplane angiography systems provide two synchronized acquisitions from two different view points, but are cumbersome for clinical usage and are not widely available. Moreover, 3-D reconstruction of the complex 3-D topology of coronary vessel using only two 2-D projections is often not sufficient to obtain a precise reconstruction. The extracted 2-D vessel centerlines may not be complete or accurate due to the flow of the dye, low image contrast, or superposition of vessels in a certain view.

In addition, whereas typically it is preferred to have two projections orthogonal to each other, this angular distance may not be achievable in a clinical setup when foreshortening and vessel overlap need to be minimized for the whole coronary artery tree in both projections. Another limitation is that vessel correspondence between the two views can be established typically only through user interaction. This is due to the fact that two views only, in general, do not provide sufficient information for automatic correspondence establishment, which limits its usage for fully-automated clinical applications.

In [20], multiple projections were used for realistic vessel lumen estimation, while 3-D centerline reconstruction was still based on two projections. The advantage of utilizing three projections for more robust 3-D symbolic reconstruction of coronary arteries was demonstrated experimentally in [10]. 2-D centerlines and their correspondences from three projections were given and the objective was to estimate the image orientation for the non-calibrated data. Therefore, their problem is not exactly the same as ours, which is to reconstruct a 3-D symbolic model based on automatic 2-D centerline extraction and correspondence matching from multiple views with a known projection geometry. 3-D centerline reconstruction and subsequent tomographic reconstruction of the coronary artery tree using multiple projections of a single rotational X-ray angiography was proposed in [17]. In their method, hard epipolar line constraint was imposed to reduce the number of matching candidate points per pixel. A high number of candidate point increases the computational complexity for the global optimization by dynamic programming. However, a hard epipolar line constraint is problematic for vessels that are close to being parallel to the epipolar line or containing missing segments. In addition, smoothness regularization can be imposed only to the extent of the set of epipolar line intersection points, which are relatively sparse and hence not guaranteed to be smooth in 3-D. Therefore, the reconstructed 3-D centerlines can be relatively jagged, especially when there is imperfectness in the 2-D centerline extraction or inaccuracies in the projection matrix calibration steps.

Although utilizing multiple projections in the modeling procedure generates better 3D reconstruction result, up to now it has received much less attention in the literature. To our knowledge, a quantitative analysis of the 3-D accuracy of the reconstructed coronary artery tree with respect to the number of projections used has not been reported in the literature. This is most probably due to the fact that most methods rely on nontrivial manual editing on 2-D centerline, and the involvement of more than two projections requires significantly more user interactions. In addition, the long processing time of the existing 3-D model generation methods, ranging from several minutes to a few hours, limits their applications in the clinical environment.

The goal of this paper is to describe an efficient and robust method for 3-D model generation of the coronary artery tree using all the projections of a rotational X-ray sequence that correspond to the same cardiac phase. A rotational X-ray sequence is acquired by rotating the C-arm with a constant source to intensifier distance, a constant cranio/caudal angle (CRAN/CAUD), and a varying left/right anterior oblique angle (LAO/RAO). Depending on the rotation speed and the heart rate of the patient, a rotational X-ray sequence may cover 5–8 cardiac cycles. The contributions of this study is two-fold: First, multiple projections (more than two) are used for robust automatic 3-D coronary reconstruction. A quantitative analysis of the accuracy of 3-D coronary modeling, with respect to the number of projections used is presented for a coronary phantom study. Second, automatic 3-D symbolic reconstruction of the coronary arteries is formulated as an energy minimization problem that incorporates a soft epipolar line constraint and a smoothness term evaluated in 3-D. This problem is then solved using an optimization approach known as α-expansion moves of graph cuts (GCs) [21]. Graph cuts has shown to be a powerful and efficient optimization technique, and has been successfully applied to a wide variety of computer vision problems, including image restoration, stereo and motion, and image synthesis [22–24]. For medical imaging, GCs optimization yields promising results for fast segmentation [25, 26]. To our knowledge, this is the first application of graph cuts technique for efficient and robust 3-D symbolic reconstruction of the coronary artery tree.

With significant improvements on the efficiency, our method is promising in terms of clinical usability. The most straightforward application of our method in a clinical setup would be to provide the reconstructed 3-D coronary model to the interventional cardiologists at the beginning of the PCI procedures. The 3-D model visualization will help the clinicians choose optimal angiographic views to minimize vessel foreshortening, select proper stent type and size, and properly plan the stent placement 3-D locations.

Methods

2-D coronary segmentation and centerline extraction

In order to reduce the noise and enhance coherent flow-like structures such as vessels in the X-ray projection images, a nonlinear diffusion technique named coherence enhanced diffusion (CED) [27] is applied to the original image (see “Appendix A”). The diffusion process is anisotropic and acts preferably along the direction of the highest coherence, i.e. along vessel orientation. Three iterations of diffusion are applied on X-ray projection images in our algorithm for optimal trade-off between performance and efficiency. Multi-scale Hessian-based vesselness filtering (MSHBVF) [28] is then applied on the CED preprocessed image to generate the vesselness feature image (see “Appendix B”). The filter identifies tubular structures and is calculated for different scales in order to enhance all vessels with different diameters that need to be segmented later. Five different scales are selected in our algorithm and their results are combined by taking the maximum response for each pixel to generate the final vesselness feature image.

Coronary arteries are segmented by a hysteresis thresholding filter on the vesselness feature image, which retains connected components with all points that have a vesselness value greater than a low threshold and having at least one pixel with a vesselness value greater than a given threshold. The low and high thresholds are calculated as fixed quantiles (90 and 96 percent) of the accumulated histogram of the vesselness image. Only sufficiently large connected components are retained and the minimal size is set to 25 pixels (or 10 mm²). Discontinuities of the segmented coronary arteries are then hole-filled by closing operation and the centerlines are extracted automatically using topological thinning [29]. For large vessels with local diameter variations, small branches may be produced artificially by topological thinning. Only coronary vessel branches longer than 5 pixels (or 3.2 mm) are retained after pruning. Line linking is further performed according to their vesselness orientation and spatial location in order to connect line segments that belong to the same vessel but are broken due to local vesselness discontinuity.

In general, our fully automatic 2-D centerline extraction algorithm works robustly for a typical coronary angiography with sufficient contrast. Some examples are shown in Fig. 1. Similar work was also presented in [16] with two main differences: (a) CED was not applied in their method, and (b) local directional maxima extraction (versus topological thinning in our method) was used for the purpose of 2-D centerline point detection. Nevertheless, there could be clinical cases where the contrast of vessels is relatively low (e.g. due to diseases and blockages), and other with peripheral anatomical structures of high contrast, as shown in Fig. 2a. A fully automated method that can robustly segment the coronary arteries in all these challenging cases is not yet known.

Fig. 1

X-ray angiography (upper) and automatically extracted 2-D coronary artery centerlines (bottom)

Fig. 2

Semi-automatic 2-D coronary artery tree segmentation and centerline extraction. a original X-ray image b multi-scale analysis c coherence enhanced multi-scale analysis d binarized mask by hysteresis thresholding e topological thinning with line segment pruning and connection e manual editing based on fast marching using the modified vesselness. User needs to accept a segment obtained by fast marching method by mouse click, and the end point of the newly accepted segment becomes the new seed point for the search of the next segment until a given coronary artery is finished

Motivated by intelligent scissor (IS) [30], we propose a method for interactive editing of the automatically extracted centerlines, to be used if necessary. In particular, when the user moves the mouse, the shortest path between a seed point (e.g. the root of the coronary artery tree) and the current mouse position is searched on-the-fly by a fast marching (FM) method [31]. One segment can be confirmed (accepted) by user’s mouse click and the end point of the newly accepted segment. This end point seed point becomes then the new seed point for the search of the next segment until a given coronary branch is finished. This process repeats until the whole coronary artery tree is extracted. The cost of a path L that is to be minimized by FM is:

$$ C(L) = \sum\limits_{p = 1}^{m} {1/(0.001 + v(p)^{4} ) + \omega S(L)} $$

(1)

where v(p) is the vesselness at pixel p, m is the number of pixels on the path L, S(L) is the length of the path L, and ω controls the relative weights of these two factors (set to 50 experimentally). In order for the extraction of the smaller vessels to be less susceptible to the influence from the neighboring large vessels, a modified vesselness v(p) is used. In particular, all points on the automatically extracted centerlines in Fig. 2e are assigned the same (maximum) value for their vesselness, and the vesselness for the points not on the automatically extracted centerlines is their coherence enhanced multi-scale vesselness response in Fig. 2c. Hence, more accurate automatic centerline extraction leads to more convenient and robust semi-automatic editing. It can be seen that a path of a stronger vesselness and a shorter length is favored over a path of a weaker vesselness and a longer length. Since the fast marching method may produce jagged line segments due to the fact that it does not consider the global topology, the output of the editing step can be optionally smoothed by fitting a B-spline that has a minimized weighted summation of the total curvature and the distance to the original centerline, as shown for the root segment pointed by the red arrows in Fig. 2f. A block diagram of the 2-D centerline extraction algorithm is shown in Fig. 3.

Fig. 3

Block diagram of 2-D coronary artery centerline extraction

Multi-view correspondence matching

Suppose we have n views that are taken at the same cardiac phase and denoted by (I ₁…I _n ), and their associated projection geometries are (M ₁…M _n ). Assume one view (I ₁) is selected as the reference view and its projection matrix is $M_{1} = (\begin{array}{*{20}c} {M_{1a} } & {M_{1b} } \\ \end{array} )$, where M _1a is a 3 × 3 matrix, and M _1b is a 3 × 1 vector. The optical center for I ₁ in C-ARM iso-center coordinates can be calculated as:

$$ o_{c} = - M_{1a}^{ - 1} M_{1b} $$

(2)

The 3-D space between the optical center and the imaging plane of the reference view I ₁ is divided into 3-D planes of equal depth increments, and a label l (l ϵ L) is attributed to each depth. Therefore, for a given pixel p on I _1, (p, l) corresponds to a point in 3-D space, which is the intersection of the plane l and the ray passing through the optical center o _c and pixel p (Fig. 4). The goal of our 3-D reconstruction is to optimally assign a depth label l for each centerline pixel p in the reference view I ₁. The 3-D symbolic reconstruction is piecewise continuous and its n − 1 projections onto the views (I ₂…I _n ) using projection geometries (M ₂…M _n ) match the corresponding centerlines extracted from (I ₂…I _n ). Here, we denote the mapping of the depth labels for all the pixels on the 2-D centerline P extracted from I ₁ by f, and denote the assignment of the depth label for a given pixel p on the 2-D centerline P by f _p . Then, the mapping $f:p \to f_{p} (p \in P, f_{p} \in L)$ is established via the minimization of the energy function:

$$ E(f) = \sum\limits_{p \in P} {D_{p} (f_{p} ) + {{\upbeta}}\sum\limits_{p,q \in N} {V_{p,q} (f_{p} ,f_{q} )} } $$

(3)

Fig. 4

A schematic view of multi-view matching using GCs for 3-D reconstruction. The 3-D space between the optical center and the imaging plane of the reference view is divided into 3-D planes of equal depth. The intersection of the 3-D ray and a labeled plane is re-projected onto the other two views, and the distance of the projected point to the nearest 2-D centerline point on the other two views is minimized via GCs

Here D(·) is the data term that encodes the soft epipolar line constraint:

$$ D_{p} \left( {f_{p} } \right) = {\frac{1}{n - 1}}\sum\limits_{i = 2}^{n} {d({\text{proj}}_{i} (p,f_{p} ),c_{i} ({\text{proj}}_{i} (p,f_{p} )))} $$

(4)

where ${\text{proj}}_{i} (p, f_{p} )$ is the projection of the 3-D point $(p, f_{p} )$ onto the i th view, c _i (r) is the point on the 2-D centerline of the i th view that is closest to a given 2-D point r, and $d\left( {p, \, q} \right) = { \min }\left( {|p - q|,K_{ 1} } \right)$ for some constant K ₁ . The cap K ₁ (set to 20 pixels, or 12.8 mm) is to make the distance penalty robust when the corresponding stereo point is missing in some views. A kd-tree structure [32] is implemented for an efficient spatial search of the point c _i (r) for any point r. While the data term favors the 3-D points that are closer to the epipolar lines, it is clear that no hard epipolar line constraint is imposed. This property is crucial for the robustness of the reconstruction algorithm, especially when there is incompleteness and/or inaccuracies in the extracted 2-D centerlines. In addition, a soft epipolar line constraint allows the smoothness regularization to be optimized up to the accuracy of a small depth increment ΔL in 3-D (further details about why a small depth increment can be used in our algorithm with a tractable complexity will be discussed later), instead of up to the extent of the set of relatively sparse epipolar line intersection points. This property helps to improve the smoothness of the reconstructed coronary artery tree in 3-D.

The smoothness term V(·) involves the notion of neighborhood N:

$$ N = \{ (p,q),p \in P,q \in P,|p_{x} - q_{x} | + |p_{y} - q_{y} | = 1\} $$

(5)

and

$$ V_{p,q} \left( {f_{p} , f_{q} } \right) = \left\{ {\begin{array}{*{20}c} {\min (|f_{p} - f_{q} |,k_{2} )} \\ {\min (|f_{p} - f_{q} |,k_{3} )} \\ \end{array} } \right.\begin{array}{*{20}c} {f_{p} ,f_{q} \notin B,} \\ {\text{otherwise}} \\ \end{array} $$

(6)

where B denotes the union of branching points that have three or more neighboring points on the 2-D centerline P in its eight-connection neighborhood. A higher smoothness penalty is imposed between the non-branching points by k ₂ > k ₃. k ₂ and k ₃ are set to 50 and 15 pixels (or 32 and 9.6 mm), respectively in our algorithm. It is important to allow for discontinuity at a branching point because it may be the intersection of two vessels at different depths. A reasonably high smoothness penalty for a non-branching point is necessary in order to achieve a smooth 3-D reconstruction. Furthermore, it is clear that V _p,q (·) is a metric for any (p, q), which satisfies the necessary condition for α-expansion move of GCs optimization to be discussed next.

A naïve way of finding the global minimum of E(f) in Eq. 3 is the brute-force search by altering the existing label f _p for each centerline pixel p to a new label and evaluate which combination of the depth labels results in the smallest E(f). This process is NP-hard and is not practical for this problem. Instead, we use the α-expansion move [21] to efficiently achieve a local minimum that is within a known factor of the global minimum, $E_{\text{local}} \le 2k_{2} E_{\text{global}}$.

Consider a given input label mapping f and a depth label α (α ϵ L). Another configuration of mapping f ^′ is defined to be within a single α-expansion of f when for all pixels p ϵ P either $f_{p}^{\prime }$ or$f_{p}^{\prime } = \alpha$, that is, for a given pixel p, its depth label $f_{p}$ either changes to α, or stays unchanged. GCs optimization using α- expansion moves is as follows:

• (1) Start with an arbitrary labeling f;

• (2) Set success = false;

• (3) For each label α ϵ L, either in a fixed order (i.e. $\alpha = 1,2,3, \ldots ,L$) or randomly selected;

  • (3.1) Find $\hat{f} = \arg \min E(f^{\prime})$ among all $f^{\prime }$ within one α-expansion of f;

  • (3.2) If $E(\hat{f}) < E(f)$, set $f = \hat{f}$ and success = true;

• (4) If success = true, go to 2; otherwise exit.

Therefore, if there is some label α that decreases the energy E in step 3, another cycle of step 3 is repeated over all the labels. Otherwise, the optimization process stops. Each α-expansion move in step 3.1 is performed on all the centerline pixels in the reference view simultaneously. Since for a given pixel p, its depth label f _p either changes to α or stays unchanged, it is essentially a partition problem whose global solution can be efficiently achieved using GCs algorithm (“Appendix C”) [21, 33].

It is shown in [21] that experimentally the computational time increases only linearly with the number of labels in L, implying that a large number of labels and hence a small depth increment ΔL can be searched within a reasonable time. In comparison, most existing methods use dynamic programming for a global optimization, whose time complexity exhibits quadratic growth with the average number of candidate positions per pixel. Hence, a hard epipolar line constraint has to be imposed in order to make the computation feasible.

3-D reconstruction of the coronary artery tree

The symbolic 3-D representation of the coronary tree is reconstructed as a 3-D point cloud, in which each pixel on the 2-D centerline P from the reference view I₁ is assigned a depth label. This is achieved by minimizing E(f) in Eq. 3 using GCs optimization, as elaborated in Sect. 2.2. The topology of the coronary tree is then recovered from the reconstructed 3-D point cloud by applying a euclidean minimum spanning tree algorithm [34], which finds the minimum total length tree that connects all the reconstructed 3-D points.

The coronary angiography also contains information about the cross-sectional size and shape of the vessels. For visualization purposes, following the calculation of the 3-D vessel centerline points, the 2-D vessel radii are measured automatically along the 2-D centerlines in the reference view based on the detection-scale of the multi-scale vesselness analysis. Vessel radii can also be measured in the other views at the matching cardiac phase for higher robustness, but is not adopted in our method considering that a given vessel branch may not be visible (contrast-filled) in all the other views. The automatically measured 2-D radii are then edited manually if needed. For 3-D lumen rendering, the radii measured in 2-D are further corrected for geometric magnification by d _or/d _op, where d _or is the distance between the optical center and the reconstructed 3-D point, and d _op is the distance between the optical center and the corresponding 2-D pixel. The radii are only used here for visualization, however, fully automated vessel extraction methods such as those proposed in [11, 35, 36] could be employed to produce more realistic rendering for quantitative lumen analysis purpose.

Experiments

Coronary phantom study

Validation of the technique described above was first performed on a synthetic ground truth data set. A physical coronary phantom, filled with contrast agent, was acquired using multi-slice computed tomography (MSCT). From the MSCT acquisition, the 3-D centerlines of the coronary artery tree were automatically extracted using the method detailed in [37], and a symbolic 3-D centerline representation (Fig. 5a) was modeled using B-spline curves. The main advantage of using B-spline curves instead of discrete 3-D centerlines is to preserve the relative connectivity of each of the vessel branches for perturbation-induced cases that will be explained later.

Fig. 5

Coronary phantom used for validation purposes: a physical coronary phantom and its MSCT acquisition, b virtual coronary phantom modeled using B-spline curves and the simulated rotational sequence using 2-D projections

A simulated rotational sequence (200 images, 180 degrees) was generated using cone beam projections of 3-D centerlines and their known projection matrices. The generated 2-D images (512 × 512 with resolution 0.66 × 0.66 mm) were used as the input to our 3-D reconstruction algorithm (Fig. 5b). Hence, only the 3-D reconstruction algorithm accuracy is evaluated, without having to identify manually 2-D vessel on each view. Reconstructions were performed with the number of views ranging from 3 to 10 and with a constant angular increment of 10 to 80 degrees apart in order to cover approximately the same total angulations. Since two views only do not provide sufficient constraint for fully automatic stereoscopic correspondence establishment, experiment using two views was not carried out. The number of depth labels was set to 256 and the depth increment was 1 mm. The reconstruction algorithm was evaluated according to two criteria. First, the reconstructed 3-D centerlines were back-projected onto the 2-D imaging plane and the 2-D re-projection error was averaged over twenty views, distinct from the views used for reconstruction. Second, 3-D validation was performed using the Euclidean root mean square distance between the 3-D coordinates of the reconstructed centerlines and the ground truth. Quantification of continuous variables is expressed in the form of mean ± standard deviation. 80% percentile was also considered, as well as the maximum and minimum error values.

The setup described above represents the ideal case where no actual motion can be observed between gated frames. However, since the rotational sequence is acquired while the heart is still moving and cardiac gating is performed at different heart cycles, some residual motion might be present between the gated frames. This motion might affect the accuracy of the 3-D reconstruction process. To quantify the accuracy of the reconstruction algorithm in the presence of such residual motion, the coronary phantom was modified to incorporate slight perturbation. Uniform white noise was applied randomly on the control points of the B-spline to simulate slight residual displacement that might occur, even if the projections are gated using the ECG signal. The perturbation was applied at 5 different levels of 20, 40, 60, 80 and 100%, and the maximum perturbation at 100% level resulted in a total mean displacement of 2.6 mm root mean square Euclidean distance (L ₂ norm) in the 3-D centerlines. The 3-D centerlines were projected as described above and the experiments were repeated with presence of this simulated motion.

Real coronary data

To validate the accuracy of the proposed 3-D coronary reconstruction algorithm in vivo, a porcine data set (resolution 620 × 480) and 11 human data sets (resolution 1,240 × 960) were acquired using a Siemens Axiom Artis stationary C-arm, with pixel size of 0.6 and 0.3 mm, respectively. The images were resampled (without cropping) to 512 × 512 lattices for computational purposes. Projection matrices for all views were computed in a prior calibration run of the C-arm. Table movement was minimized by iso-centering the table prior to the procedure. Gantry angulations were constant CRAN/CAUD at 0 degree, and varying RAO/LAO in the range of −100 to 100 degrees, with the increment of 1.5 degrees per projection. 133 images were acquired with ~6 s long acquisition for each data set, covering 5 to 8 cardiac cycles depending on the heart rate. The electrocardiogram (ECG) was recorded synchronously with the X-ray acquisition, and was used to extract the R–R interval for cardiac cycle identification. Depending on the number of images available for a given cardiac phase, 4 to 5 projections were used to reconstruct the 3-D symbolic coronary artery tree. The remaining projection that was not utilized for the reconstruction was then used for the quantification of the 2-D back-projection error of the reconstructed 3-D centerlines. Reconstruction at 75% of the R–R interval (typically around end-diastole) was used for error quantification for all the data sets, and no automatic optimal reconstruction phase detection was performed. Among the 11 patient data sets, 2 data sets showed contrast agent injected into the right coronary artery (RCA) and 9 into the left coronary artery (LCA). All analyses were performed offline following completion of the angiographic study.

Results

Coronary phantom study

Results for 2-D and 3-D accuracy of the reconstructed centerlines using a coronary phantom with a different number of views are described in Table 1. The advantage of exploiting more views for a more accurate reconstruction is clearly demonstrated through the decreased reconstruction error with an increasing number of views used. When three views were used, utilization of images of angular increment of 80 degrees resulted in a significantly larger reconstruction error compared to the cases of angular increment of 60 or 70 degrees. This is due to the fact that the third view was 160 degrees apart from the first view, meaning that it was close to being opposite to the first view and hence, provided very weak constraint for the 3-D reconstruction in the depth direction. Moreover, reconstruction time varied from 10 to 20 s when using a different number of views and 256 depth labels, and increased only slightly when more views were used. This property is appealing in clinical applications for obtaining on-the-fly a 3-D reconstruction immediately after a rotational X-ray acquisition.

Table 1 Benchmark of 3-D reconstruction results obtained on a coronary phantom with different angle increments (different angle between views and different number of views)

It is further observed that when five views were used for reconstruction, the computational time was 2.41, 6.05, 13.72, 22.65, and 42.98 s, respectively when 64, 128, 256, 512 and 1,024 depth labels were used. The computational time therefore increased almost linearly with the number of depth labels used, conforming to the results reported in [21]. Hence, our algorithm can still produce computationally efficient reconstruction when the number of depth labels was as large as 1,024 with increment ΔL as small as 0.25 mm.

Figure 6 illustrates the performance of the proposed algorithm in the presence of displacements in between views, which was introduced by uniform white noise on the control points of the B-spline curves of each of the coronary arteries. It can be seen that the algorithm was relatively robust to the introduced perturbation. The RMS reconstruction error in 3-D was still around one millimeter when the perturbation was as large as 2.6 mm. This demonstrates the advantage of our reconstruction formulation by using a soft epipolar line constraint, which relies on the nearest distance from a 2-D centerline point, instead of relying of an exact match on 2-D views that can be over-constrained for the reconstruction.

Fig. 6

Effect of noise ratio on a 2-D projections on 20 images unused for reconstruction b 3-D reconstruction accuracy

Real coronary data

ECG recording was observed to be adequate for cardiac cycle identification for all the data by visual inspection on the correspondence of prominent bifurcation points shown in the X-ray angiography with the aid of epipolar line display [38]. Breathing motion was negligible for the human data acquired during breath hold, and was observed to be minimal for the porcine data that was acquired under anesthesia and mechanical respiratory support. 2-D coronary artery centerline extraction was fully automatic on the human data (Fig. 1) and took, in general, less than 1 s per view. Semi-automatic editing of the 2-D centerlines was needed for the porcine data (Fig. 2), which could be accomplished reliably within a few minutes for trained users. The intra-observer variability for the porcine data was observed to be negligible due to the fact that user input was indeed minimal (essentially the distal points only). CED was observed to improve the vessel segmentation result qualitatively (Fig. 2c).

The reconstructed 3-D centerlines appear smooth (Fig. 7), and their projections visually overlay reasonably well with the vessels in the X-ray images (Figs. 8, 9). The 2-D re-projection error for a projected point (purple line) was defined as its Euclidean distance (L ₂ norm) to the closest point on the expert-identified centerlines (blue line) in Fig. 9. The mean, standard deviation, minimum, maximum, and 80% percentile of errors for all the data sets reconstructed at 75% of R–R interval are summarized in Table 2. In average, the mean error for all the 12 data sets was 1.86 pixels (1.18 mm, ranging from 0.84 to 1.71 mm). For some data sets, the standard deviation of the error was significant in comparison to the relatively small mean error. This mainly came from two sources: (1) incompleteness of the 2-D centerline extraction when the target vessel was not contrast-filled and hence could not be identified in the view used for quantification; (2) less accurate 3-D reconstruction at the distal end of the coronary artery tree when it is not contrast-filled in a sufficient number of views used for reconstruction. Although it is not meaningful to run statistical tests on the extremely small sample set of RCA group (only 2 samples), no apparent difference was observed for the 3-D reconstruction accuracy and efficiency between RCA and LCA group. Typical running time was 12 s on 2.13 GHz Intel Pentium M when using five views and 256 labels. Reconstructions of the coronary artery tree at three different percentages of R–R intervals were further obtained for several data sets and the sample result is shown in Fig. 10. The three cardiac phases were selected to sample from systole to diastole, and the reconstructed 3-D coronary artery trees were observed to adequately cover the possible topological changes of the coronary artery tree through a cardiac cycle.

Fig. 7

Examples of 3-D reconstruction of coronary artery tree viewed at different angles. The 3-D lumen is approximated based on a sequence of circular cross section contours perpendicular to the reconstructed 3-D coronary centerline. The radii of the circular cross sections were measured semi-automatically with manual editing from 2-D X-ray angiography followed by 3-D geometric magnification correction

Fig. 8

Examples of overlay of back-projection of coronary artery reconstruction onto six views of X-ray angiography, among which five views were used for reconstruction and the sixth view was used for quantification of the 2-D back-projection error

Fig. 9

Examples of coronary artery reconstruction (purple line) and expert-generated centerlines (blue line). Note that the vessel pointed by the yellow arrow is not visible in the reference view and hence is not reconstructed

Table 2 Quantification of the 2-D back-projection error in mm for 12 real data sets

Fig. 10

Examples of symbolic reconstruction of the coronary artery tree for three representative cardiac phases from systole to diastole

Discussions

While it has been well recognized that 3-D model generation from a traditional X-ray angiography has important clinical value, much effort has been invested in utilizing two projections for 3-D reconstruction. Incorporating multiple projections for efficient and robust 3-D coronary reconstruction is particularly important when a complex coronary artery tree needs to be generated because it may be difficult to find two views with good angular distance that both have sufficient contrast injection and minimal vessel overlap/foreshortening for the complete coronary artery tree. The requirement on user interaction for correspondence matching also presents a major limitation for its clinical applications. The advantage of utilizing more than two views for automatic, accurate and robust reconstruction is quantitatively demonstrated in this work using a software coronary phantom. No user interaction was required for vessel correspondence matching by utilizing the complementary information provided by additional views. The 3-D reconstruction error for the phantom study (evaluated by the mean plus one standard deviation) was found to be below 1 mm with 4 or more views, and the execution time increased only slightly with the increasing number of views used. Moreover, 4 to 5 views seem to provide the best trade-off between reconstruction accuracy and computational time in our algorithm, which coincides well with the number of views available for the same or close cardiac phase in a typical X-ray rotational sequence.

3-D reconstruction is very challenging for any optimization method when the number of views is limited and there is significant appearance change among views coming from high angular increment, even for static and uncomplicated structures. The results for both phantom and real data demonstrate the strength and efficiency of GCs optimization. The computational time increased only approximately linearly with the number of depth labels used, and with the small depth increment, the reconstructed coronary artery tree could be relatively smooth in 3-D. For the phantom study, the reconstruction performance was relatively robust in the presence of small motion/perturbation in between views, demonstrating the advantage of our reconstruction formulation by using a soft versus hard epipolar line constraint. While it was more difficult to assess the algorithm performance for real data, we quantified the 2-D back-projection error on the view that was not used for reconstruction, averaging at 1.18 mm for 12 cases. Note that the re-projection error on the view that is not used for reconstruction is typically larger than the re-projection error for the views used for reconstruction, and our result is comparable to (or better than) the results reported in previous studies (3.0 mm in [4, 9], 2.5 mm in [10], and 1.6 mm in [39]). In addition, accurate back-projection in multiple projections from a wide range of angles implies an accurate 3-D reconstruction from our algorithm. The computation time was ~5 s for centerline extraction and ~12 s for 3-D reconstruction, which is a significant improvement over previously reported methods (several minutes to hours).

Three-dimensional approach at the beginning of the procedure provides a basis for combining different image modalities, e.g. intracoronary ultrasound [3] or positron emission tomography (PET) [10] with X-ray angiography. Image fusion is considered an important field of development, because it brings complementary information into the interventional cardiology room. For example, it can provide cross-sectional geometry, which may improve the clinical evaluation of patients being considered for revascularization. Furthermore, the reconstruction methodology has been extended to several representative cardiac phases from systole to diastole in the cardiac cycle (Fig. 10), providing the potential ability to measure dynamic properties of coronary arteries during the entire cardiac cycle.

The current method does not handle breathing motion compensation, and hence requires patients’ breath-hold when applied clinically. Breath-hold for a rotational run is a common clinical practice to minimize motion artifacts, and is typically well-tolerated by patients due to the relatively short acquisition time (~6 s). Nevertheless, various methods have been proposed for breathing motion compensation for cardiac intervention applications [40, 41], and any breathing compensation technique appropriate for rotational X-ray angiography could be applied as a preprocessing step on the rotational image sequence before it is input into our reconstruction algorithm. In addition, motion correction for cardiac C-arm CT imaging using multiple sweeps of rotational runs is proposed in [42].

A full vessel lumen model is critical for stenosis analysis. After the 3-D coronary centerline is generated, two groups of methods have been applied to generate a vessel lumen model. One approach is to estimate and compensate the cardiac and/or breathing motion shown in the X-ray image sequence using the reconstructed 3-D coronary centerline [15, 16]. Tomographic reconstruction, e.g. based on filtered back projection technique, is then performed on the motion-compensated X-ray rotational sequence in a CT-like manner. An alternative approach [11, 13, 20] is based on 2-D vessel width estimation from X-ray angiography. Here the 3-D lumen cross section is computed using the 2-D vessel width estimated from one, two, or more projections and corrected by 3-D projection geometry. Our semi-automatic approach used for 3-D lumen rendering shown in this study falls into the second category. However, fully automated 3-D lumen estimation methods should be employed for the purpose of quantitative analysis of stenoses.

In the current method, only those vessels visible in the reference view can be reconstructed. A symmetric variation of the algorithm using different views as reference is currently under investigation. This is achieved by topology merging of several symbolic trees obtained for different reference views. While only a small number of challenging data sets needed manual interaction for 2-D centerline extraction (1 out of 12), statistical analysis on the intra-observer and inter-observer variability may be needed when more data sets requiring manual interaction are observed. This, however, is not expected to be an issue due to the fact that the requirement for manual interaction is indeed minimal in our algorithm, and the 2-D centerline extraction step is largely driven by the underlying automatically-extracted centerlines obtained in the preprocessing step even during manual editing procedure. A fully automatic method to extract the 2-D centerlines is currently being investigated and shows promising results. This is achieved by a more general formulation of the vesselness filter, which requires a less number of parameters to be adapted to varying image contrast, vessel sizes, etc.

At this point, we systematically use the approximate end-diastole images (75% of R–R interval) for quantification of the reconstruction error for real data. It has been shown in [43] that for coronary CT angiography using Dual-Source CT, the optimal reconstruction window for most patients appears to be 30–35% of R–R interval for systolic phase and 70–75% of R–R interval for diastolic phase. To automatically determine the ideal cardiac phase for reconstruction is an active area of research. One approach by Hansis et al. [44] defines an inconsistency measure for each cardiac phase based on its vessel centerline geometry. However, our research showed that the individual motion patterns of the different branches cannot adequately be represented by a global inconsistency measure defined on the whole coronary tree.

In addition, improved validation methods can be deployed for real data. For example, recently 3-D coronary reconstruction from the traditional angiography is validated against CT acquisition for patient coronary angiography [11].

Conclusions

A framework based on GCs optimization is presented for an efficient multi-view reconstruction of the coronary artery tree. The accuracy as reported from the phantom and patient studies is promising, and the efficiency is significantly improved compared to other approaches reported in the literature, ranging from a few to tens of minutes. Visually good and smooth reconstruction is demonstrated. The reconstructed 3-D model can be used for optimal visualization, quantitative assessment of coronary lesion, and 3-D measure of intracoronary devices. The 3-D model can further serve as the initial point for 4-D cardiac motion estimation and 4-D coronary model generation, as well as the first step for subsequent tomographic reconstruction of the coronary artery volume.

Appendix

A. Coherence enhanced diffusion

For CED, The diffusion equation applied on the image I is given by:

$$ \partial_{t} I(x,t) = \nabla \cdot (D(\nabla I(x,t))), $$

(7)

where $\nabla \cdot$ is the divergence operator, $D$ is a diffusion tensor that depends on local image structures so that not only the amount, but also the direction of the diffusion can be regulated. Let $K_{\sigma }$ be the Gaussian kernel:

$$ K_{\sigma } (x) = {\frac{1}{{2\pi \sigma^{2} }}}e^{{ - {\frac{{\left| x \right|^{2} }}{{2\sigma^{2} }}}}} $$

(8)

and $I_{\sigma }$ be the convolving result of $I$ with $K_{\sigma }$: $I_{\sigma } (x,t) = K_{\sigma } * I(x,t)$.

The structure tensor $J_{\rho }$ is defined as the convolving result of gradient tensor product with $K_{\rho }$:

$$ J_{\rho } (\nabla I_{\sigma } ) = K_{\rho } * (\nabla I_{\sigma } \otimes \nabla I_{\sigma } ) . $$

(9)

$J_{\rho }$ has the eigenvalues $\mu_{1}$ and $\mu_{2}$, and the corresponding eigenvectors $w_{1}$ and $w_{2}$. The coherence-enhancing anisotropic diffusion tensor D is structured to have the same eigenvectors as $J_{\rho }$, but with customized eigenvalues $\lambda_{1}$ and $\lambda_{2}$,

$$ D = \left( {w_{1} |w_{2} } \right)\left( {\begin{array}{*{20}c} {\lambda_{1} } & 0 \\ 0 & {\lambda_{2} } \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {w_{1}^{T} } \\ {w_{2}^{T} } \\ \end{array} } \right) $$

(10)

where

$$ \begin{aligned} \lambda_{1} &=& \kappa \\ \lambda_{2} &=& \kappa + (1 - \kappa )e^{{{\frac{ - 1}{{(\mu_{1} - \mu_{2} )^{2} }}}}} \\ \end{aligned} $$

(11)

with $\kappa \in (0,1)$. The diffusion process acts preferably along $w_{2}$ direction of the highest coherence within the scale $\rho$. $\sigma = 1.0$, $\rho = 4.0$, $\kappa = 0.001$, $t = 3$ are adopted in our algorithm.

B. Multi-scale hessian-based vesselness filtering

The MSHBVF is defined as:

$$ F(u) = \max\nolimits_{\varepsilon } f(u,\varepsilon ) $$

(12)

where f is the filter at scale ɛ. The filter response is calculated for different scales and the maximal response is used as the final vesselness result. The filter calculates 2^nd-order derivatives to build the Hessian matrix:

$$ \user2{H}_{\varepsilon } = \varepsilon^{2} \left[ \begin{gathered} \begin{array}{*{20}c} {{\frac{{\partial^{2} {\mathbf{u}}_{\varepsilon } }}{{\partial x^{2} }}}} & {{\frac{{\partial^{2} {\mathbf{u}}_{\varepsilon } }}{\partial x\,\partial y}}} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {{\frac{{\partial^{2} {\mathbf{u}}_{\varepsilon } }}{\partial x\,\partial y}}} & {{\frac{{\partial^{2} {\mathbf{u}}_{\varepsilon } }}{{\partial y^{2} }}}} \\ \end{array} \hfill \\ \end{gathered} \right]. $$

(13)

Here ${\mathbf{u}}_{\varepsilon }$ is the convolution of the CED preprocessed image with a Gaussian kernel of size ε corresponding to the radius of the vessel of interest. Based on the hypotheses that the dark tubular structures on the bright background have the eigenvalues $\nu_{1} \approx 0$, $\nu_{2} > 0$, and $|\nu_{1} | \ll |\nu_{2} |$, the vesselness strength is calculated as [28]:

$$ V_{\varepsilon } = \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} 0 \\ {e^{{{{ - R_{B}^{2} } \mathord{\left/ {\vphantom {{ - R_{B}^{2} } {2\beta^{2} }}} \right. \kern-\nulldelimiterspace} {2\beta^{2} }}}} (1 - e^{{{{ - S^{2} } \mathord{\left/ {\vphantom {{ - S^{2} } {2\gamma^{2} }}} \right. \kern-\nulldelimiterspace} {2\gamma^{2} }}}} )} \\ \end{array} } & {\begin{array}{*{20}c} {\nu_{2} \le 0} \\ {\nu_{2} > 0} \\ \end{array} } \\ \end{array} } \right\} $$

(14)

where $R_{B} = \nu_{1} /\nu_{2}$ to enhance the tubular structure, $S = \sqrt {\nu_{1}^{2} + \nu_{2}^{2} }$ to suppress the background noise, and the vesselness orientation is calculated as the eigenvector corresponding to $\nu_{1}$. Here β and γ control the sensitivity of the filter and are set to 1 and 3, respectively in our algorithm.

C. α-Expansion move of graph-cuts optimization

GCs optimization using α-expansion move is based on computing a labeling corresponding to a minimum cut on a graph $g_{\alpha } = \left\langle {V_{\alpha } ,E_{\alpha } } \right\rangle$. The structure of the graph is determined by the current partition and by the current label α. The set of vertices:

$$ V_{\alpha } = \left\{ {\alpha ,\bar{\alpha },P,\mathop \cup \limits_{\begin{subarray}{l} \{ p,q\} \in N \\ f_{p} \ne f_{q} \end{subarray} } a_{{\{ p,q\} }} } \right\} , $$

(15)

includes two terminals α and $\bar{\alpha }$, the centerline pixels P, and the auxiliary nodes $a_{{\{ p,q\} }}$ between neighboring centerline pixels p and q such that $f_{p} \ne f_{q}$. Each centerline pixel $p \in P$ is connected to the terminals α and $\bar{\alpha }$ by t-links $t_{p}^{\alpha }$ and $t_{p}^{{\bar{\alpha }}}$, respectively. Each pair of neighboring centerline pixels $\{ p,q\} \in N$ with $f_{p} = f_{q}$ is connected by an n-link $e_{{\{ p,q\} }}$. For each pair of neighboring centerline pixels $\{ p,q\} \in N$ with $f_{p} \ne f_{q}$, a triplet edges $E_{{\{ p,q\} }} = \{ e_{{\{ p,a\} }} ,e_{{\{ a,q\} }} ,t_{a}^{{\bar{\alpha }}} \}$ are created, where $a = a_{{\{ p,q\} }}$ is the auxiliary node, $e_{{\{ p,a\} }}$ and $e_{{\{ a,q\} }}$ connect pixels p and q and the t-link $t_{a}^{{\bar{\alpha }}}$ connects the auxiliary node $a_{{\{ p,q\} }}$ to the terminal $\bar{\alpha }$. So all the edges are:

$$ E_{\alpha } = \left\{ {\mathop \cup \limits_{p \in P} \left\{ {t_{p}^{\alpha } ,t_{p}^{{\bar{\alpha }}} } \right\},\mathop \cup \limits_{\begin{subarray}{l} \left\{ {p,q} \right\} \in N \\ f_{{p \ne f_{q} }} \end{subarray} } E_{{\{ p,q\} }} ,\mathop \cup \limits_{\begin{subarray}{l} \left\{ {p,q} \right\} \in N \\ f_{{p = f_{q} }} \end{subarray} } e_{{\{ p,q\} }} } \right\}. $$

(16)

Please refer to [21] for the weights assigned to the edges. After partition, the global solution of one α-expansion move is as follows: a centerline pixel p is assigned the label α if the cut seperates p from the terminal α, and p retains its old label if the cut separates p from the terminal $\bar{\alpha }$.