1 Introduction

Automatic or semiautomatic segmentation of vasculature from its surroundings is an active area of research in the field of medical image analysis. It helps researchers as well as clinicians to explore the underlying hemodynamics, which is one of the major factors in determining one’s vascular health. The present work is focused on human carotid vasculature/cerebrovasculature. In general, human cerebrovasculature refers to the underlying vessel network circulating blood to/from the various parts of the brain. Arteries and veins are the main components of this network. In this work, we are mainly interested in the carotid arteries, which are supplying oxygenated and nutrient-filled blood to entire cerebral system. Anatomical analysis of the lumen vessel network is the first step towards exploration of the blood flow patterns in the vasculature, determination of irregular dilation of vessel wall, detection of possible obstruction in the flow, etc. To understand the anatomy of carotid arteries properly, one should have the knowledge about the anatomy of circle of Willis. The left and right internal carotid arteries, anterior and posterior cerebral arteries (left and right), anterior and posterior communicating artery form this circular vasculature. The basilar and middle cerebral arteries are also part of this circle.

Generally, there are two ways to analyse the carotid arteries: (1) using physical vascular phantom, which is a replica of the original one and (2) digital modelling of the vessel network using mathematical model. Both of them have individual merits and demerits, and researchers sometimes work on both of the models to verify the experiments as in work [1,2,3]. The present work, extension of our previous work in [2], focuses only on the segmentation of vasculature using mathematical model from human cerebral CT angiogram (CTA) images. One can find many existing works on segmentation of carotid vasculature in the present state of the art. Banerjee et al. [3] proposed a robust mathematical model using piecewise Bezier curve for design of approximate digital model of segmented cerebrovasculature to reduce the overhead of real-life patient study and ex vivo/ in vivo analysis. They also custom-developed a 2-D/3-D user interface for construction of sphere-based tubular structure with varying diameter. In [4], they extended the work in [3] and developed a new module to segment cerebrovasculature from real patients’ CT angiogram images of human brain with the help of previously developed 2-D/3-D user interface. But the segmentation process needs a lot of human interactions. In addition to active human interactions, another challenge in the segmentation process lies in the segmentation of vessel and bones in the region of overlapping intensities. In CT angiogram images of human brain, there are high overlapping between intensity regions of soft tissues, bones, arteries and veins which makes the images fuzzy in nature. Researchers have adopted various FDT-based and fuzzy morphoconnectivity-based approaches to separate objects residing in the overlapping intensity regions. Saha et al. [5] presented a topomorphplogical way to separate objects fused at different scale and locations where no trace of intensity variation can be found. The authors have applied this methodology on non-contrast pulmonary CT images to separate artery and vein and on mathematical phantoms to distinguish different object’s identity at location of isointensity. Basu et al. [6] have extended the work in [5] to separate objects in shared intensity space, and the method have been experimentally proven to give elegant results with patients’ CT angiogram images of the brain to separate soft bones and vessel network. In [7, 8], they have presented the theoretical foundation of the multi-scale opening (MSO) and established it as new topomorphological operator.

Although accuracy and reproducibility of the algorithm in segmenting carotid vasculature is very promising, it has some drawbacks too. First, the performance of the algorithm depends on the initial selection of three different kinds of seed points. Inaccurate selection of seed points may lead to decreased performance. Also, it needs active human participation in the region of high overlapping of intensities, low resolution, imaging ambiguities.

Using the proposed algorithm, we have successfully reduced the amount of human participation by the notion of fuzzy distance transform (FDT)-based geodesic path propagation approach [2]. Please note that, the concept of FDT has been widely used before in various segmentation algorithms [9,10,11,12].

In the subsequent discussions, first we will introduce the theory and notations related to the proposed algorithm, followed by the methodology of our proposed algorithm and experimental results.

2 Theory and methods

A 3-D cubic grid is expressed by \(\{{\mathcal {Z}}^{3}|{\mathcal {Z}}\) is the set of positive integers}. A point on the grid, often referred to as a voxel, is a member of \({\mathcal {Z}}^{3}\) and is denoted by a triplet of integer coordinates. Standard 26 adjacency [13] is used here, i.e. two voxels \(P=\left( {x_1 ,x_2 ,x_3 } \right) \) and \(Q=\left( {y_1 ,y_2 ,y_3 } \right) \in {\mathcal {Z}}^{3}\) are adjacent if and only if,

$$\begin{aligned} \{\max \left( {\left| {x_i -y_i } \right| } \right) \le 1\,|\,1\le i\le 3\}, \end{aligned}$$

where \(\left| \cdot \right| \) means the absolute value. Two adjacent points in a cubic grid are often referred to as neighbours of each other. Twenty-six neighbours of a voxel P omitting itself is symbolized as \({\mathcal {N}}^{*}\left( P \right) \).

CT angiogram images are 3-D greyscale images where each voxel is represented by 8 bit character or 16 bit unsigned short value. Numeric value of a voxel denotes the intensity of the voxel. Artery, veins and soft tissues acquire small intensity values, whereas bones take high intensity values. We will denote artery and veins together as vessels. Intensity of vessels and soft tissues are highly overlapping. In this paper, we are mainly interested in segmentation of arterial tree of human cerebrovasculature.

It has been observed that in general intensity of vessels lies between 130 and 500 Hu (Hounsfield unit), as described in reference [6], but there is almost zero overlapping around the middle point of this intensity scale. Hence, voxels within this intensity range are considered as object voxel and rest of the intensity regions are taken as background.

Distance transformation [14] is an essential step in many 2-D/3-D image processing tasks like merging and segmentation, clustering and matching, finding out centre of maximal discs/centre of maximal balls, skeletonization, etc. The distance transformation algorithm works on a binary image and converts it to an image where the value of each foreground pixel/voxel depicts the distance from the nearest background pixel/voxel. Over the years various distance transformation algorithms have been proposed both in 2-D and 3-D [15,16,17,18,19]. Among the different proposed distance metrics, city block distance (4-distance)/chess board distance (8-distance) is popular in two dimension and in three dimension these are 6-, 18- and 26-distance. If \(P=\left( {x_1 ,x_2 ,x_3 } \right) \) is a point in a 3-D image, then DT value of that point will be,

$$\begin{aligned} \mathrm{DT}\left( P \right) =\left\{ {{\begin{array}{ll} \mathrm{DT}\left( {Q_i } \right) +d_k , &{} \mathrm{DT}\left( {Q_i } \right) +d_k <\mathrm{DT}\left( P \right) \\ \mathrm{DT}\left( P \right) , &{} \mathrm{otherwise} \\ \end{array}}} \right. \end{aligned}$$
(1)

where, \(Q_i \) is the neighbour of P, \(i=1,2,\ldots ,26\). \(d_{k=1,2,3} \) is the approximate Euclidean distance of P from three different kinds of neighbour voxels, i.e. 6-neighbour, 18-neighbour and 26-neighbour. In the present work, three approximate euclidean distance values are 3, 4 and 5 for 6-, 18- and 26-neighbour, respectively. Distance transform performs very well in case of binary images. But in case of segmentation of cerebrovasculature where the image is fuzzy in nature, distinction between vessel and soft bones is crucial which cannot be done in DT image. Hence, fuzzy distance transform is appropriate in the present work.

The theory of fuzzy distance transform is well established by Saha et al. in [20]. In this section, the formal notation related to the theory of FDT is introduced first. An object \({\mathcal {O}}\) is a fuzzy set \(\{\left( {p,\mu _{\mathcal {O}} \left( p \right) } \right) |p\in {\mathcal Z}^{3}\}\), where \(\mu _{\mathcal {O}} :{\mathcal {Z}}^{3}\rightarrow \left[ {0,1} \right] \) is the membership function. The support of an object \({\mathcal {O}}\) is the set of all voxels with nonzero membership value, i.e. \(\theta \left( {\mathcal {O}} \right) =\{p|p\in {\mathcal {Z}}^{3}\) and \(\mu _{\mathcal {O}} \left( p \right) \ne 0\}.\,\,{\bar{\theta }} \left( {\mathcal {O}} \right) ={\mathcal {Z}}^{3}-\theta \left( {\mathcal {O}} \right) \) is the back ground. Let S denotes a set of object voxels; a path \(\pi \) in S from \(p\in S\) to \(q\in S\) is a sequence of successive adjacent voxels, i.e. \(\left\langle {p=p_0 ,p_1 ,\ldots ,p_l =q} \right\rangle \). A link is a path \(\left\langle {p,q} \right\rangle \) consisting of exactly two mutually adjacent voxels \(p,q\in Z^{3}\). The length of a path \(\pi =\left\langle {p_0 ,p_1 ,\ldots ,p_l } \right\rangle \) in a fuzzy object \({\mathcal {O}},\) denoted by \(\prod _{\mathcal {O}} \left( \pi \right) \) is sum of the length of all links along the path, i.e.

$$\begin{aligned} \prod _{\mathcal {O}} \left( \pi \right) =\mathop \sum \limits _0^{l-1} \frac{1}{2}\left( {\mu _{\mathcal {O}} \left( {p_i } \right) +\mu _{\mathcal {O}} \left( {p_{i+1} } \right) } \right) \left| {| {p_i -p_{i+1} }|} \right| \end{aligned}$$
(2)

The fuzzy distance between two voxel \(p,q\in Z^{3}\) in an object \({\mathcal {O}}\), expressed as \(\omega _{\mathcal {O}} \left( {p,q} \right) \), is the length of one of the shortest path from p to q, i.e.

$$\begin{aligned} \omega _{\mathcal {O}} \left( {p,q} \right) =\mathop {\min }\nolimits _{\pi \in \left( {p,q} \right) } \prod _{\mathcal {O}} \left( \pi \right) |p\left( {p,q} \right) , \end{aligned}$$
(3)

where \(p\left( {p,q} \right) \) is the set of all paths from p to q. The FDT of an object \({\mathcal {O}}\) is an image \(\{\left( {p,\Omega \left( p \right) } \right) |p\in {\mathcal {Z}}^{3}\}\), where \(\Omega _{\mathcal {O}} :{\mathcal {Z}}^{3}\rightarrow \mathfrak {R}^{+}|\mathfrak {R}^{+}\) is the set of all real numbers including zero, is the fuzzy distance from the background, i.e.

$$\begin{aligned} \Omega _{\mathcal {O}} \left( p \right) =\mathop {\min }\limits _{q\in \mathop {\overline{\theta ( {\mathcal {O}}})}} \omega _{\mathcal {O}} \left( {p,q} \right) \end{aligned}$$
(4)

A local maxima is defined as the FDT value at nearest locally deepest voxel. Let \(L_{\max } \subset \theta _{\mathcal {O}} \) be the set of locally deepest voxels, i.e.

$$\begin{aligned} L_{\max } =\left\{ {p\hbox {|}p\in \theta ( {\mathcal {O}} )\,\hbox {and}\,\forall q\in {\mathcal {N}}_l ( p),\Omega _{\mathcal {O}} ( q )\le \Omega _{\mathcal {O}} ( p )} \right\} \nonumber \\ \end{aligned}$$
(5)

where \({\mathcal {N}}_l \left( p \right) \) is the \(\left( {2l+1} \right) ^{3}\) neighbourhood of p. So, a point may have several locally deepest points or it may not have any local maxima point in its neighbourhood.

We represent whole image as an undirected graph \(G=\left( {V,E} \right) \) where V is the vertex set denoted by \(\{P|P\) is a voxel in the 3-D image, E is the set of edges denoted by \(E=\{\left( {P_1 ,P_2 } \right) |P_1\) and \(P_2\) are adjacent}.

Methodology used here is to find the centre point of the presumed artery between input seed points and draw spheres in these points with radius equal to the FDT value of that point. A sphere \(S\left( {P,r} \right) \) with centre \(P=\left( {x_c ,y_c ,z_c } \right) \) and radius r is the locus of all points \(\left( {x,y,z} \right) \) in \(z^{3}\) such that,

$$\begin{aligned} \left( {x-x_c } \right) ^{2}+\left( {y-y_c } \right) ^{2}+\left( {z-z_c } \right) ^{2}=r^{2} \end{aligned}$$

Geodesic path [21] is defined as minimum-cost shortest path between two points in two- or three-dimensional space. Dijkstra’s shortest path algorithm has been used for geodesic path propagation with modification so that shortest path will always pass through the nearest local maxima point if it exists; otherwise, it will pass through the maximum FDT value point in its neighbourhood. To force the geodesic path between two seed points to pass through nearest local maxima points or maximum FDT value point, the edge weight between any point and corresponding nearest local maxima point or maximum FDT value point should be minimum. Here, we introduce a cost function \(\beta \) that computes edge weights between a point \(P=\left( {x_1 ,x_2 ,x_3 } \right) \) and one of the locally deepest points \(Q=\left( {y_1 ,y_2 ,y_3 } \right) \epsilon Z^{3}\) as follows:

$$\begin{aligned} \beta \left( {P,Q} \right) =\left( {\frac{2}{\left( {\mathrm{DT}\left( P \right) +\mathrm{DT}\left( Q \right) } \right) }} \right) \times \mathrm{DIST}\left( {P,Q} \right) . \end{aligned}$$
(6)

where

$$\begin{aligned} \mathrm{DIST}\left( {P,Q} \right) =\sqrt{\left( {x_1 -y_1 } \right) ^{2}+\left( {x_2 -y_2 } \right) ^{2}+\left( {x_3 -y_3 } \right) ^{2}}.\nonumber \\ \end{aligned}$$
(7)

Dijkstra’s algorithm is a greedy method where from current point algorithm chooses a neighbour connected through least cost edge for next iteration. In the proposed method due to cost function \(\beta \), it will always select the nearest local maxima point or maximum FDT value point in the neighbourhood of the current point. After termination, the algorithm will return connected centre points of the presumed artery. If we draw sphere taking these points as centre and radius equal to the FDT values of the point, we will get the desired segmentation.

Fig. 1
figure 1

Modular representation of the proposed algorithm

Full size image
Fig. 2
figure 2

a Mathematically generated binary phantom. b Discrete set of geodesic points after applying the proposed algorithm on (a)

Full size image

As the proposed method is a semiautomatic algorithm, user may not get accurate result at first; hence, trial and error method should be used to obtain proper segmentation result. In this method, user can modify the generated phantom by giving extra seed points. We can summarize the whole method in following steps Fig. 1.

3 Experimental methods and results

The experimental methods are facilitated with the help of our custom-developed 2-D/3-D graphical user interface allowing axial, coronal and sagittal views of segmented data. Facilities of selecting and editing different seed points are supported within the graphical user interface. With the help of the GUI, we have taken seed points as input and visualized the segmented results in axial, coronal, sagittal views. The 3-D rendition of the generated phantom in shown with the help of popular ITK-SNAP software [22]. We have worked with two different kinds of data: mathematically generated approximate phantom and another is segmented arterial tree from original patient’s CTA images. Figures 2,  3 and  4 expose how the proposed algorithm actually works with mathematically generated approximate arterial phantom. Figure 2 shows that the proposed algorithm generates discrete set of geodesic points on binary phantom data. Figure 3 shows some of the intermediate steps of geodesic points generation through six images (Fig. 3a–f). Total 18 initial seed points are taken to generate the set of geodesic points. Points are taken pairwise as start point and end point.

The accuracy of the generated geodesic points is checked by adding the set of discrete points as an overlay image with original image with the help of ITK-SNAP s/w in Fig. 4.

Fig. 3
figure 3

a–f Intermediate steps of generation discrete set of geodesic points for the mathematical phantom image shown in Fig. 2a

Full size image
Fig. 4
figure 4

Overlay of the set of discrete geodesic points with the original binary phantom data

Full size image

Now, the results on original patients’ CTA images are shown in Figs. 5, 6 and 7. Figure 5 shows the results on image id-3036. The intermediate steps of gradual segmentation of the arterial tree from its surroundings is shown by the images in Fig. 5a–f. A total of 14 seed point is used for segmentation. Initial seed points are taken in two different fashions: (1) start and end points and (2) joining points. The long segments generated by the first way, start and end points are taken initially and the intermediate points are generated by the algorithm. To generate the in-between small segments, the second way is chosen. If a point is chosen as a joining point, the proposed algorithm generates a set of geodesic points such that if a path is created by joining these points, the path will connect to the nearest arterial segment.

Fig. 5
figure 5

a–f Six phases of segmentation of vasculature from a CTA image (Data id-3036)

Full size image
Fig. 6
figure 6

a–h Digital phantoms generated around circle of Willis from 8 different CTA images. Image id—a 2005, b 1016, c 2001, d 2008, e 2009, f 3029, blue coloured portion is aneurysm g 3032, h 3036 (colour figure online)

Full size image
Fig. 7
figure 7

A segmented phantom image is shown as overlay of colour (red) with respect to the original CTA image. a Shows axial view, b shows coronal view, c shows sagittal view and d 3-D rendering of the segmented phantom with the help of ITK-SNAP s/w (colour figure online)

Full size image

Segmentation results are shown on eight patients’ CTA image in Fig. 6. Blue coloured portion in Fig. 6e shows aneurysm present in the cerebrovasculature. The accuracy of all the segmented data are verified by overlaying the phantoms with the original images. Figure 7 shows the overlay of image id-1016 with the original image in axial, coronal and sagittal views and 3-D rendition with the help of ITK-SNAP s/w. We have compared our proposed algorithm for segmentation of cerebrovasculature with the MSO algorithm proposed by Saha et al. in [8]. From Table 1, it can be easily seen that the number of vessel seeds required for reconstructing arterial tree for all the images (Image id 1016-2008) are lesser than the original MSO algorithm. In addition to the less number of seed points, the advantage of the proposed algorithm is that at the beginning users have to select only vessel seed points for segmenting arterial tree from the other components. On the contrary, in MSO algorithm the users have to select three different types of seed points, e.g. vessel seeds, separator seeds and the bone seeds.

Table 1 Comparative analysis of no. of seeds required for segmentation of arterial tree from the other components in MSO algorithm and the proposed algorithm
Full size table

4 Conclusion

The present work is focused towards reducing the number of user interaction in the segmentation process as well as proper segmentation of vasculature from soft bones in the overlapping intensity area. This paper has adopted fuzzy distance transform-based geodesic path propagation approach as in our previous work in [2], and it successfully over performed the pervious approaches made by Saha et al. [8] and other research groups. Geodesic points and fuzzy distance transformation are used to find the radius of the arterial tube. The proposed process is semiautomatic, and the user can modify the generated digital phantom structures to make it more accurate. We argue that the proposed algorithm is both efficient and precise. Digital phantoms generated through this algorithm can be helpful in studying the arterial bends, bifurcated regions, joins and possible modelling of digital fluid flows in human cerebrovasculature. We have used the ITK-SNAP [22] open-source software to overlay generated phantom structures over original CTA images. In future, we may attempt to use the generated digital phantoms for homodynamic analysis in human cerebrovasculature. Digital phantoms are also useful in various other bio-imaging applications, and we propose to develop similar synthetic structures for analysis of structural/plastic changes in hippocampal dendritic spines [23].