- Research
- Open Access
- Published:

# Automatic segmentation of coronary angiograms based on fuzzy inferring and probabilistic tracking

*BioMedical Engineering OnLine*
**volume 9**, Article number: 40 (2010)

## Abstract

### Background

Segmentation of the coronary angiogram is important in computer-assisted artery motion analysis or reconstruction of 3D vascular structures from a single-plan or biplane angiographic system. Developing fully automated and accurate vessel segmentation algorithms is highly challenging, especially when extracting vascular structures with large variations in image intensities and noise, as well as with variable cross-sections or vascular lesions.

### Methods

This paper presents a novel tracking method for automatic segmentation of the coronary artery tree in X-ray angiographic images, based on probabilistic vessel tracking and fuzzy structure pattern inferring. The method is composed of two main steps: preprocessing and tracking. In preprocessing, multiscale Gabor filtering and Hessian matrix analysis were used to enhance and extract vessel features from the original angiographic image, leading to a vessel feature map as well as a vessel direction map. In tracking, a seed point was first automatically detected by analyzing the vessel feature map. Subsequently, two operators [e.g., a probabilistic tracking operator (PTO) and a vessel structure pattern detector (SPD)] worked together based on the detected seed point to extract vessel segments or branches one at a time. The local structure pattern was inferred by a multi-feature based fuzzy inferring function employed in the SPD. The identified structure pattern, such as crossing or bifurcation, was used to control the tracking process, for example, to keep tracking the current segment or start tracking a new one, depending on the detected pattern.

### Results

By appropriate integration of these advanced preprocessing and tracking steps, our tracking algorithm is able to extract both vessel axis lines and edge points, as well as measure the arterial diameters in various complicated cases. For example, it can walk across gaps along the longitudinal vessel direction, manage varying vessel curvatures, and adapt to varying vessel widths in situations with arterial stenoses and aneurysms.

### Conclusions

Our algorithm performs well in terms of robustness, automation, adaptability, and applicability. In particular, the successful development of two novel operators, namely, PTO and SPD, ensures the performance of our algorithm in vessel tracking.

## Background

Accurate extraction of the coronary artery tree from coronary angiograms is important for the diagnoses, treatment, and clinical study of various coronary artery diseases. In particular, computer-assisted analysis can improve the performance of quantitative evaluation. It can reduce the inter- and intra-observer variations in determining the severity of coronary artery stenosis [1]. An efficient vessel extraction algorithm also enables the detection of coronary artery motion, as well as the reconstruction of 3D vascular structures from a single-plan or biplane angiographic system [2].

Anatomical structures, such as blood vessels, nerves, and bronchi, present themselves as line-liked structures in 2D images or as tubular structures in 3D images. Over the past 10 years, a variety of approaches have been developed for vessel segmentation from 2D and 3D medical images [3], which typically differ in terms of basic strategies or imaging modalities. Common segmentation approaches employ multiscale filters, morphological segmentations, deformable models, front propagation methods, tracking-based methods, and ridge traversal-based methods. Although many of these approaches are promising for vessel segmentation, developing fully automated, faster, robust, and accurate vessel segmentation algorithms remains highly challenging because of the complexity of vascular structures as well as large variations in image intensities and noise.

Tracking-based methods [4–9] exhibit a natural advantage in extracting arterial axis lines in the angiographic images because of their relative simplicity, as well as their adaptability to variations in vessel diameters. In addition, their ability to capture detailed quantitative descriptions of vessel axes, diameters, and boundaries, leads to high levels of accuracy. Traditional tracking-based methods, however, are guided by simple local features that limit their utility because of difficulties in efficiently integrating advanced features into canonical expressions for guiding the tracking. Therefore, the use of minimum cost functions or multi-scale filters [10–13] to construct the tracking operator poses several advantages in the segmentation of coronary angiograms; this approach, however, may also be problematic when meeting bifurcations or vessel crossings because it can follow only the path with the strongest response.

In this work, we propose a fully automatic tracking-based method that can adapt to varying vessel curvatures and diameters resulting from arterial stenoses or aneurysms. It can also walk across intensity gaps along the longitudinal vessel direction, and manage vessel bifurcations and crossings.

## Methods

An integrated framework was designed to solve the challenging problem of coronary angiogram segmentation. The main components in this framework are summarized in Figure 1. The automatically detected seed point is generally located near the root of the arterial tree or on the main trunk. The probabilistic tracking operator (PTO) was initialized with the initial seed point to search for a candidate artery element with the most similar vessel geometries (including vessel feature, direction, and diameter) in the neighborhood. The vessel structure pattern detector (SPD) was utilized in parallel to classify each detected artery element as bifurcation or crossing. The artery element classified as bifurcation is placed on the list of source data to enable tracking new vessel segments beginning from this artery element in subsequent tracking. The tracking algorithm stops when all points on the list of source data are tracked.

During the process mentioned above, local features and measures, such as the Gabor response, vessel path, skeleton-line, and directional consistency, were also analyzed to integrate the relational vessel attributes for probabilistic vessel tracking and structure pattern identification. The PTO is designed to incorporate local features and measures to determine candidate artery elements along the same vessel segment. These candidates were selected particularly from the overlapping region between the binarized vessel regions and a sampling disk centered at the current artery element under consideration. The size of the sampling disk corresponds to the current vessel diameter, thus rendering the PTO adaptive to varying vessel diameters in case of arterial stenoses or aneurysms. Simultaneously, the SPD works to infer the vessel structure pattern, such as the distal end, segment, bifurcation, and crossing. To complete structure pattern identification, the vessel feature profile scanned from a circle around the current artery element was analyzed and a fuzzy inferring function was applied. In particular, multiple features such as vessel feature, direction continuity, and Gabor responses at the peaks of the vessel feature profile were integrated into the fuzzy inferring function for pattern identification.

### Vessel feature and direction maps

The intensity profile across the longitudinal direction of the vessel may highlight an elevation or even a slight intensity dip at the center, depending on the contrast between vessels and background. On the other hand, the profile along the longitudinal direction of the vessel can be smooth [Figure 2(b)]. Accordingly, the multiscale detection or enhancement of vessel structures can be completed by convolving angiographic image *I*(**x**) [where **x** = (*x*, *y*)] with normalized second-order Gaussian derivatives *G* (**x**; σ_{
f
}) at different scales σ_{
f
} . The use of a Gaussian filter is important in reducing the influence of noise, properly shaping the line profile and ensuring a large second derivative across the vessel.

In 2D cases, let ∇^{2} *I* (**x**, σ_{
f
}) be a Hessian matrix combined with Gaussian convolution for angiographic image *I*(**x**). It can be written as

where *G* (**x**; σ_{
f
}) denotes a Gaussian filter with standard deviation σ_{
f
}.

The bright line structure on a dark background can be reflected by a Hessian matrix with a large negative eigenvalue λ_{1} and a small eigenvalue λ_{2} of positive or negative sign; that is λ_{1} < 0 and |λ_{2}| ≪ |λ_{1}|. Various response functions have been proposed in previous studies [11–13]. We provide a similar response function to extract the vessel structures by thresholding the eigenvalue map using a low threshold |*r*
_{
λ
}|, expressed in

where *c* is a constant. Note that λ_{1} is negative in our case, with ${r}_{\lambda}=-\sqrt{2\pi {\sigma}_{f}}$. This response equation provides a vessel discriminant function at scale σ_{
f
}. To integrate multiscale responses corresponding to different scales at each location **x**, we select the maximum response across multiple scales, *i.e*.

where σ_{1} and σ_{
n
} are the minimum and maximum scales, determined according to the range of vessel diameters in the angiographic images. In this paper, 14 scales were used. For convenience, the resulting vessel features are normalized to 0[1] in this paper. Vessel feature map $\stackrel{\wedge}{Z}(\text{x})$ (Figure 2 (a3-a4)) may also be binarized for extracting the vessels, and may further be thinned to obtain the skeletal lines representing the vessels.

The vessel direction map is estimated using the best detected scale. First, the maximum of absolute eigenvalue |λ_{1}| is obtained at each location **x** by $|{\lambda}_{opt}(\text{x})|={\mathrm{max}}_{{\sigma}_{f}}|{\lambda}_{1}(\text{x};{\sigma}_{f})|$. Assuming that the eigenvector corresponds to λ_{
opt
}(**x**) is **v**
_{
opt
}(**x**), the direction orthogonal to **v**
_{
opt
}(**x**) is then selected as the vessel direction at **x**. For convenience, we again use **v**
_{2} to represent the estimated vessel direction map later in this paper.

Therefore, using this step of multiscale analysis, we obtain three separate maps from the original angiographic images, namely, a vessel feature map, a vessel direction map, and a map of skeleton lines. Next, an initial seed point **x**
_{0} is automatically detected from a point within the thinned vessel skeleton-lines, as well as with maximum vessel feature intensity $\stackrel{\wedge}{Z}({\text{x}}_{0})$. The determined initial seed point is generally located near the root of the arterial tree or the main trunk of the arterial tree. The data above are used for the identification of consequential vessel pattern.

### Probabilistic tracking of coronary artery

A dynamic mechanism was designed for our tracking framework. *First*, a list for source points (called source-list) was maintained to keep the initial seed point, as well as the vessel bifurcations that were detected during the vessel tracking procedure. In addition, a second list of crossings (called crossing-list) was designed to keep the possible crossings of two vessels. *Then*, a sampling disk with about half the size of the vessel diameter was used in the PTO to automatically track the artery segments (or branches) one at a time, beginning from the seed point and stopping at the vessel termination. During the tracking, the proposed SPD functioned simultaneously to report the local vessel pattern as bifurcation, crossing, segment, or termination. All detected vessel bifurcations were stored one at a time at the top of the source-list and were later used as subsequent starting points for tracking their respective artery segments (or branches). *Finally*, the vessel PTO and the SPD stop tracking and identifying vessels once all vessels have been tracked and registered.

### Tracking criterion

The tracking mechanism was designed based on the criterion of *continuity properties of luminance*, *position*, and *diameter* of the general coronary artery in the angiographic images. The appropriate incorporation of these properties into the PTO enables successful management of the cases of vessel gap (caused by nonuniformity of the contrast medium or inappropriate thresholding in the preprocessing step) and arterial lesion (such as stenosis or aneurysm).

### Description of PTO

Our PTO performs automatically along the coarse vessel path extracted from the vessel feature map. It begins or stops tracking an artery segment (or branch), depending on the structure pattern detected at current artery element *e*
_{
t
}. The tracking problem at simple artery positions, with no bifurcations, crossings, or terminations, is to determine the next artery element *e*
_{
t+1}in the vessel path. Each artery element *e*
_{
t
} has four associated attributes, namely position **x**
_{
t
}, vessel feature $\stackrel{\wedge}{Z}({\text{x}}_{t})$, direction vector *ϕ*
_{
t
} = **v**
_{2}(**x**
_{
t
}), and vessel diameter *d*
_{
t
}. These attributes guide the vessel tracking algorithm. For efficiency, a sampling disk centered at the current artery element *e*
_{
t
} was used to search for a set of candidate elements $\{({\text{x}}_{t+1}^{i},\stackrel{\wedge}{Z}({\text{x}}_{t+1}^{i}),{\varphi}_{t+1}^{i},{d}_{t+1}^{i})|i\in [1,\mathrm{...},{N}_{s}]\}$ from the overlapping region between the sampling disk and the binarized vessel feature map. From artery element *t* to *t*+1, the probabilistic tracking can be formulated by a maximum posterior probability (MAP), expressed as

The sequent modeling was based on the aforementioned continuity properties of the artery vessel. During tracking vessel length [Figure 3(a)], three local terms were used to constrain the candidates based on vessel feature continuity, longitudinal direction continuity, and diameter continuity. The first term, $\stackrel{\wedge}{Z}({\text{x}}_{t+1}^{i})$, was acquired from the vessel feature map at candidate position ${\text{x}}_{t+1}^{i}$. The second term to some extent, kept the vessel tracking from being interrupted by noise, pseudo contours, and crossing, although more assurances should come from the structure pattern detection result, as described in aforementioned sections. Given vector ${V}_{t+1}^{i}$ pointing from current position **x**
_{
t
} to candidate point ${\text{x}}_{t+1}^{i}$, a deflection of vessel direction ${\theta}_{t+1}^{i}=\angle {V}_{t+1}^{i}-\angle {\varphi}_{t}$ [Figure 3(a)] yields a means of the longitudinal continuity. In the case of vessel crossing or paralleling with each other (especially for thin vessels), the third term of diameter continuity enables the tracking of the current vessel segment/branch to proceed without being affected by neighboring vessels. Given ${d}_{t+1}^{i}$ and *d*
_{
t
} as the vessel diameters, respectively at candidate point ${\text{x}}_{t+1}^{i}$ and current artery element **x**
_{
t
}, increment $\nabla {d}_{t+1}^{i}=|{d}_{t+1}^{i}-{d}_{t}|$ yields the measure of diameter continuity. Altogether, the estimation of the optimal candidate gives emphasis to the continuity properties, which is also the basic idea for probabilistic tracking. In the following paragraph, we provide further discussion to mathematically model.

First, the relationship between the sampling instance and the posterior probability can be described as

All feature measures in the left of the abovementioned expression are normalized before participation in the estimation of probability. In particular, maximal vessel feature ${\stackrel{\wedge}{Z}}_{\mathrm{max}}$ and maximal diameter *d*
_{
max
} are determined from all *N*
_{
s
} candidate points in the sampling disk, and are used to normalize the respective measures. Note that in practice, estimated vessel direction ∠*ϕ*
_{
t
} can be reversed; thus, it should be considered in the normalization of ${\theta}_{t+1}^{i}$. Given normalized measures ${Q}_{Z}({\text{x}}_{t+1}^{i})=|1-\stackrel{\wedge}{Z}({\text{x}}_{t+1}^{i})/{\stackrel{\wedge}{Z}}_{\mathrm{max}}|$, ${Q}_{\theta}({v}_{t+1}^{i})=\frac{1}{\pi}\mathrm{min}\left\{\right|\mathrm{arg}{\theta}_{t+1}^{i}-\pi |,|\mathrm{arg}{\theta}_{t+1}^{i}\left|\right\}$, and ${Q}_{d}({\text{x}}_{t+1}^{i})=\nabla {d}_{t+1}^{i}/{d}_{\mathrm{max}}$, their probabilities can be respectively written as:

where σ_{
Z,t
}, σ_{
θ,t
}, and σ_{
d,t
} are the standard deviations, which can be estimated by calculating the variances of the corresponding measures in all *N*
_{
s
} candidates. For example, σ_{
Z,t
} is estimated as

where ${\overline{Q}}_{Z}$ is the average measure obtained by ${\overline{Q}}_{Z}=1/{N}_{s}{\displaystyle \sum _{i=1}^{{N}_{s}}{Q}_{Z}({\text{x}}_{t+1}^{i})}$. By integrating all distribution functions in Eq. (6), the optimal estimation of artery element *e*
_{
t+1}can be obtained by

PTO uses adaptive parameters adjusted according to Eq. (7) based on all candidates in the sampling disk. Thus, it can successfully estimate the artery elements along the vessel path even in cases of gaps and arterial lesions. The gap is generally regarded as the region of a longitudinal narrow crack with a width less than the vessel radius, whereas the arterial lesion presents as a short or long component of the longitudinal region with large variations in vessel diameter and, at times, weak luminance. During the vessel tracking, the candidates running into the gaps can be crossed out by the continuity terms, thus enabling PTO to continue working. On the other hand, in case candidates run into the regions of the artery lesion, the PTO still carries on, even with large variations in vessel diameter.

### Artery diameter estimation

Considering that the blood vessels have measurable abnormalities in diameter, intensity, and tortuosity, the artery diameter of candidate ${\text{x}}_{t+1}^{i}$ should be estimated adaptively by analyzing its 1-D vessel feature profile orthogonal to the vessel direction. All candidates sitting along the sample profile have the same vessel diameter estimated (as described next). For example, in Figure 3(b), another candidate ${\text{x}}_{t+1}^{j}$ sitting at the peak of the profile has the same vessel diameter as ${\text{x}}_{t+1}^{i}$. The profile can be represented by transversal line ${C}_{t+1}^{i}$ with a single pixel width, as shown in Figure 3(b). Candidates ${\text{x}}_{t+1}^{i}$ and ${\text{x}}_{t+1}^{j}$ have the same profile, and thus the same diameter.

The feature values in the particular profile can be obtained from vessel feature map $\stackrel{\wedge}{Z}$. The vessel diameter on this profile can be measured through the convolution of the normalized second derivative of the 1-D Gaussian function with the profile. Standard deviation σ in the 1-D Gaussian function should be adjusted during the vessel diameter estimation. Standard deviation $\stackrel{\wedge}{\sigma}$ that results in the largest response among all convolution results with the use of different standard deviations is finally selected as the estimated diameter for all candidates sitting on the same profile. Using this method, we can estimate vessel diameter ${d}_{t+1}^{i}$ for candidate ${\text{x}}_{t+1}^{i}$.

This vessel diameter estimation process proceeds automatically without user interaction. The relevant diameter estimation results are demonstrated in the experimental section.

### Inferring structure pattern of artery vessel

When the PTO works on current artery element **x**
_{
t
}, the SPD should also work in parallel to report the structure pattern to guide the PTO. Our SPD performs in the following manner. First, a circular pattern detector is centered on current artery element **x**
_{
t
}. It then acquires the circular cross-section profile from vessel feature map $\stackrel{\wedge}{Z}$. Subsequently, it captures local vessel measures, including the number of peaks in profile (M_{
t
}), the azimuth vector directing from the detector center to every peak (*p*
_{
m
}), and the Gabor response on each peak (*γ*
_{
o.m
}). Finally, it returns the structure pattern inferred by a fuzzy inferring operator using the fuzzy membership degrees of multi-feature fuzzy subsets.

### Detecting the peaks of the vessel-feature profile

The pattern detector samples of vessel features $\stackrel{\wedge}{Z}$ along the circular cross-section profile are centered at current artery element **x**
_{
t
} with radius *r*
_{
t
} = *α*·*d*
_{
t
}/2. Generally, the range of parameter *α* in *α* ∈ [1,1.5] is preferred for better measurement because in this case, the radius of circular pattern detector is a little bit larger than half of vessel diameter *d*
_{
t
} of current artery element **x**
_{
t
}; thus, the structure around **x**
_{
t
} can be adaptively and completely captured. The resulting vessel feature profile is called circular template *T*
_{(x,r,t)}, which consists of a fixed number (e.g., 150) of vessel features sampled over the circumference of a circle (**x**
_{
t
}, *r*
_{
t
}). The same number of vessel features $\stackrel{\wedge}{Z}$ is sampled to make the SPD adaptive to different sizes of vessel diameters. Therefore, even for small vessels, the same number of points is also sampled. Because vessel feature map $\stackrel{\wedge}{Z}$ is defined in discrete domain, the bilinear interpolation is used for sampling features from $\stackrel{\wedge}{Z}$ when generating circular template *T*
_{(x,r,t)}.

The sampling process is demonstrated in Figure 4, in which the vessel feature profiles are sampled by the circular templates (*T*
_{(x,r,t)}) in 4(a2)-4(c2). The typical profiles are shown in 4(a3) - 4(c3). To detect the peaks in each profile, first-order derivative *dT*
_{(x,r,t)}of *T*
_{(x,r,t)}is computed through the circular convolution of *T*
_{(x,r,t)}with the first-order derivative of the 1-D Gaussian filter. Figures 4(a4) - 4(c4) shows the magnitude profile of the resulting first-order derivative |*dT*
_{(x,r,t)}|. The local minima of the derivative magnitude correspond to the maxima or minima of the vessel feature profile along *T*
_{(x,r,t)}. The peaks of the profile corresponding to maxima can be detected according to the derivative signs. For example, a peak of the profile corresponds to the sign transition of the first-order derivative from positive to negative. In this manner, we can detect all peaks along with their locations [e.g., z{*p*
_{
m
} = (*x*
_{
m
}, *y*
_{
m
}), *m* = 1,...,*M*
_{
t
}}], where *M*
_{
t
} is the total number of peaks.

The resulting peaks provide the SPD vessel with several important properties, such as their positions, vessel features, vessel directions, as well as their relationships with the center of pattern detector (**x**
_{
t
}). To better infer the pattern of the vessel structure, more relevant metric features, such as the Gabor features described in the next section, should be extracted.

### The Gabor responses at locations of the peaks

Considering that the peaks of the circular profile provide useful information for structure identification, we first discuss how to infer the case in which two points (apart less than a few pixels) are located at the same vessel axis line. This case may also be called "co-vessel." To detect whether peak point *p*
_{
m
} = (*x*
_{
m
}, *y*
_{
m
}) and detector center (*O*
_{
d
}) are located in the same segment of the vessel, the Gabor filter operator [14, 15] was used for local description. As a function of orientation, frequency, and scale, the operator can characterize the dominant attributes at peak point *p*
_{
m
} = (*x*
_{
m
}, *y*
_{
m
}). Note that this responds strongly to the isolated vessel strip, but exhibits a weaker or no response to the noise.

Given the relationship between the Gabor filter scale and the frequency with 2σ = 2*πf* = *T*, several masks by the Gabor operator can be defined by the real component of the Gabor function with a size of *T* × *T*. The masks of different scales are shown in Figure 5(b). Thus, to characterize local attributes, such as direction and "co-vessel" at a peak point, we merely need to compute the responses of several Gabor masks, and retain only the related parameters corresponding to the maximum response. Although none of these parameters are invariant to common image transformation, such as scaling and rotation, only one set of parameters corresponds to maximum response *g*
_{max} at the considered position. Given vector *V*
_{
o,m
} directing from the detector center to the peak position (*x*
_{
m
}, *y*
_{
m
}), the following response measure *γ*
_{
o,m
} represents the degree with which peak *p*
_{
m
} = (*x*
_{
m
}, *y*
_{
m
}) belongs to the same vessel axis line of the center point of the pattern detector

Where 0 < *γ*
_{
o.m
} < 1. With an image sized 512 × 512, the size of the mask (σ) is equal to the vessel diameter, which ranges from 3 to 14 pixels. Therefore, the resulting measure *γ*
_{
o,m
} reflects the relationship between peak *p*
_{
m
} and the detector center. For example, the resulting measure *γ*
_{
o,m
} at peak *p*
_{
m
} is lower if mask orientation *V*
_{
o,m
} does not accord with the local vessel direction, that is, there is no "co-vessel" existing between the peak point and the detector center.

### The multi-feature based fuzzy inferring function (FIF)

Four types of patterns can be inferred, namely, vessel termination (*i* = 1), artery segment (*i* = 2), bifurcation (*i* = 3), and crossing point (*i* = 4), where variable *i* denotes the index for the ordinal structure pattern of the artery vessel. With effects from noise and pseudo edge, the number of peaks in each of these four types of patterns might be higher than the actual one. For example, by comparing the circular cross-section profile of different cases (Figure 4), we can observe that more than two peaks might occur in the profile of the artery segment, and more than three or four peaks might occur in the profile of the bifurcations or crossings, respectively. Without loss of generality, the circular pattern detector detects the number of peaks from the ordinal structure pattern according to *M*
_{
t
} ≥ 1, *M*
_{
t
} ≥ 2, *M*
_{
t
} ≥ 3 and *M*
_{
t
} ≥ 4 [Figure 5(a)]. Thus, the number *M*
_{
t
} can be regarded as a pseudo pattern of the artery structure. On the other hand, each peak *p*
_{
m
} has two metric features important to pattern identification: vessel feature $\stackrel{\wedge}{Z}({p}_{m})$ at peak *p*
_{
m
}, and response measure *γ*
_{
o,m
} of Gabor mask function ${G}_{\angle {V}_{o,m},\sigma /\pi ,\sigma}({x}_{m},{y}_{m})$. The relationship between the pattern detector and the metric features for a typical artery bifurcation is shown in Figure 5(a).

In the following section, the fuzzy subsets are defined for all metric features, as well as for number of peaks *M*
_{
t
}. They will then be integrated for pattern inferring of point **x**
_{
t
}.

*Definition***1:** In the region $\Omega =\{{p}_{m},{\stackrel{\wedge}{Z}}_{m},{\gamma}_{o,m},{M}_{t}|1\le m\le {M}_{t};{\stackrel{\wedge}{Z}}_{m},{\gamma}_{o,m}\in [0,1]\}$, given that fuzzy subsets ${F}_{m,\stackrel{\wedge}{Z}}$ and *F*
_{
m,γ
} correspond to the metric features of peak *p*
_{
m
}, and fuzzy subset ${F}_{{M}_{t},{\text{x}}_{t}}^{i}$ corresponds to the *i*-th pseudo pattern at current position **x**
_{
t
}, the membership degrees of these fuzzy subsets can be defined by the standard Gaussian function as

where. ${\stackrel{\wedge}{Z}}_{\mathrm{max}}={\mathrm{max}}_{m}{\stackrel{\wedge}{Z}}_{m}$., *γ*
_{max} = max_{
m
}
*γ*
_{
o,m
}, and *m* = 1,...,*M*
_{
t
}. The above expressions, ${\mu}_{m,\stackrel{\wedge}{Z}}$ and *μ*
_{
m,γ
}, represent the respective degrees of membership of two metric features at current position **x**
_{
t
}, which are used to ensure that each peak *p*
_{
m
} is located at the center of the vessel. Meanwhile, ${\mu}_{{M}_{t},{\text{x}}_{t}}^{i}$ provides the membership degree of the pseudo pattern based on the number of peaks. According to the abovementioned membership degrees, the structure patterns of current position **x**
_{
t
} can be inferred by the following definition.

*Definition***2:** In the same region Ω, given *J*
_{
i
}(**x**
_{
t
}) the fuzzy subset of the structure pattern belonging to the *i*-th pattern at current position **x**
_{
t
}, the relationship between fuzzy set *J*
_{
i
}(**x**
_{
t
}) and the fuzzy sets of the metric features is given by

The membership degree of *J*
_{
i
}(**x**
_{
t
}) is given by:

where it is shown that the direct inferring of the local vessel structure can be hardly implemented using ${\mu}_{J}^{i}({\text{x}}_{t})>{T}_{\alpha}$ with threshold *T*
_{
α
}. Therefore, the optimal pattern inference should be based on the principle of maximum membership degree and can be expressed as

which infers the artery structure at current position **x**
_{
t
} belonging to the *i*
_{0}-th pattern.

When the detector center is near the vessel node (e.g., bifurcation or crossing), the resulting node position can be ambiguous; for example, a few of the redundant positions may possibly be the node positions because of the similarity of their metric features to those of the actual node. To solve this problem, a second local maximum operation is performed to obtain a preferable node position. Given *n* redundant positions near the bifurcation, with the membership degrees $\{{\mu}_{J}^{{i}_{3}}({\text{x}}_{t}^{1}),\mathrm{...},\text{and}{\mu}_{J}^{{i}_{3}}({\text{x}}_{t}^{n})\}$, the preferable one should be located at

In Figure 5(c), the numbers 2 and 3 represent the two structure patterns determined in the corresponding locations by the proposed pattern detector. Pattern detection result is used to guide the vessel tracking process.

### Manipulation of vessel tracking process and organiztion of tracking results

Appropriate termination conditions for vessel tracking are important to achieving better tracking performance. Our vessel tracking algorithm stops tracking the current artery segment or branch once one of the following conditions is satisfied: (1) a new vessel bifurcation is detected, which should be dealt with appropriately; (2) vessel feature $\stackrel{\wedge}{Z}({\text{x}}_{t+1})$ at position **x**
_{
t+1}along the vessel path is below a certain threshold, such as when a value is slightly higher than the background (this threshold is set as 0.05 in this paper); (3) the current path overlaps with a vessel path previously detected, except when a crossing point on the vessels has been detected and recorded in advance; (4) the source-list is empty and no new node is found; and (5) the new point is outside the image field. In all cases except for vessel crossing, the last valid vessel point is marked as a termination point, and the algorithm starts tracking the other vessel with the seed point placed at the top of the source-list.

The artery segment is a vessel length with two end-points at two nodes, or at an origin point and a node, whereas the artery branch is a distal vessel with a distal point. Either the artery segment or branch is composed of artery elements. Considering these artery elements arranged at intervals (or with "look-ahead distance") of less than the radius of the sampling disk, polylines are used to connect the artery elements by linear interpolation. The generated polylines are treated as an approximation of vessel centerlines, and have high probability inside the binarized vessel structures.

## Results

The proposed algorithm was tested on both simulated images and real image sequences with stenosis vessel and aneurysm. To obtain images with acceptable quality, the cranial and caudal angles, as well as the X-ray dose, were adjusted so that the X-rays travel a moderate distance. Our vessel tracking algorithm was implemented in MATLAB 7.0 on a Pentium IV PC (with CPU 2.8 G and 512 M memory).

Our algorithm was first tested on various simulated artery vessel images to adjust its parameters. Actual images were used to evaluate the actual performance of the algorithm by comparing the algorithm-segmented structure and vessel length of the entire artery network with those produced by expert cardiologists. The tracking algorithm has several distinguishing characteristics: (a) it is robust to the starting position detected; (b) it can detect and identify a larger area of the artery tree without any manual intervention; and (c) it can accurately distinguish the narrows resulting from the gaps in the vessel feature map or those caused by real vessel stenosis.

In our algorithm, total computational time *T* consisting of two major components *T*
_{1}, *T*
_{2}, and one minor component *T*
_{3,} were spent on preprocessing (36.7 s), tracking (15.7 s), and connecting artery elements (1.4 s), respectively.

General effects of vessel segmentation are listed in the first column of Table 1, where the results of right coronary artery (RCA) and the left coronary artery (LCA) in the real angiographic images are compared separately. In Table 1, *L*
_{∑} and $\overline{L}$ denote the length of algorithm-segmented vessels (in pixels) and the total vessel length delineated by expert cardiologists, respectively. The percentage of the detected artery segments (DAS %) and the extracted vessel length (EVL %), as well as the identification ratio (IR %) of the arterial structure was computed to evaluate the performance of our algorithm. In particular, the IR % is defined as the percentage of the correct parts of vessel length in the entire length of algorithm-segmented vessels. As openly reported in literature, the DAS % produced by Haris et al. [16] reached 90%, while the EVL % produced by Schrijver et al. [4] was less than 78%. On average, our algorithm can reach 94.7% for DAS % and 88.1% for EVL %.

Other detailed experiments and performances are introduced in the next section.

### Arterial vessel simulation and algorithm evaluation

Simulated data were created for the arterial segment [Figure 6(b)] and the simulated arterial tree (SAT) [Figure 6(c)]. In particular, various levels of Gaussian smoothing were applied to simulate the spatial blurring in an X-ray projection. The SAT in Figure 6(c) was generated to simulate artery characteristics, such as curving, overlapping, and bifurcating. For these simulated images, all information related to vessel segments, centerline, and local structure are known beforehand. We can analyze the algorithm characteristics given that various levels of white Gaussian are added to these images.

The performance of our algorithm can first be evaluated using the simulated images, such as vessel segments A to F. Given an initial seed point at the left end of the vessel segment in A, B, E, and F of Figure 6(b), the PTO can automatically track vessels and measure their diameters. The measured diameters along the vessel are consistent with varying morphology, such as stenoses and aneurysms. The resulting mean errors are listed in Table 2, where *L*
_{
x
} denotes the length of the simulated arterial segment, *e*
_{0} and *e*
_{
d
} denote the mean error of the resulting vessel centerlines and diameters, respectively. Under zero-level Gaussian noise, the mean errors of estimated centerlines and diameters of stenosis or aneurysm vessels are no more than 0.02 and 0.04, respectively. In case of close proximity (such as C) and local gap (such as D), the tracking results depend on distance *d*
_{
P
} between two neighboring vessels and gap-width *w*
_{
G
}, respectively. Suppose that *r*
_{1} and *r*
_{2}, and *r*
_{D} denote the radii of two neighboring vessels and the radius of the detector, respectively. To enable the algorithm to operate through the vessel despite influence from the neighboring vessel and the gaps, the limiting distance and gap-width would be *d*
_{
P
} ≥ (*r*
_{1} + *r*
_{2})/2 and *w*
_{
G
} < *r*
_{
D
}, respectively. The entire length of the skeleton lines of the SAT is 948 pixels, and is entirely involved in the testing.

The results of structure identification on the SAT and real angiograms are provided in the following sections.

### Experiments on structure pattern inferring

Two experiments were performed on simulated and real images to test the capability of our algorithm to infer the structure patterns in the artery tree. The performances on identification of all four different patterns, as well as separate performances on the detection of bifurcation are reported.

The first experiment was conducted on the SAT image. Based on results of estimated membership degrees ${\mu}_{J}^{i}({X}_{t})$ in Eqs. (13) and (14), the attributes of all interesting points in Figure 6(c) can be well characterized by our algorithm. Overall, the captured membership degrees corresponded well to four different structure patterns, such as the membership degree distribution between N1-**N4** in Figure 7. For vessel overlapping cases, such as local superposition between the two vessel segments N2-**N4** *-* **N5**-D and N1-**N4**-**N5**-C, the structure ambiguity (between **N4** and **N5**) might be difficult to resolve using only a single-view projection, although it might be resolved by observing vessel motion or radius information from sequence images as done by human observers while reading cine-angiograms. In short, our multi-feature based fuzzy inferring method is capable of accurately estimating the structure patterns from 2D images.

The second experiment was performed on actual angiogram images selected from the angiogram sequences. The related results are provided in the second and third columns of Table 1. The lower level of the arterial structure can be inferred with higher IR %, and the recognizable vessels can reach up to the fifth level at best. In practice, the cardiovascular surgeon is often interested in the vessels below the fourth level; thus, the performance of our algorithm is promising. The second column of Table 1 also displays the rate of bifurcation identification (*N*^{b}/*W*^{b}). Here, *N*^{b} denotes the number of correctly detected bifurcations for the *b*-th level vessel branch, while *W*^{b} (≥*N*^{b}) denotes the total number of the detected bifurcations, including the incorrectly detected ones.

### Experiments on vessel tracking and measurement

We also evaluated the respective contributions of the probability terms of the continuity properties given in Eq. (6) to the vessel tracking. By rewriting Eq. (8) as ${\stackrel{\wedge}{\text{x}}}_{t+1}=f({q}_{\theta},{q}_{Z},{q}_{d})$, three different types of PTO, namely, ${\stackrel{\wedge}{\text{x}}}_{t+1}=f({q}_{\theta})$, ${\stackrel{\wedge}{\text{x}}}_{t+1}=f({q}_{\theta},{q}_{Z})$, and ${\stackrel{\wedge}{\text{x}}}_{t+1}=f({q}_{\theta},{q}_{Z},{q}_{d})$, can be constructed. Their respective results are compared in Figure 8, where the paths traced in the same sub-image were obtained by the same PTO. Figures 8(b1) and 8(b2) show that the direction constraint term in Eq. (6.2) can effectively compel the sampling disk and the pattern detector to move ahead, but it can often be lost in edges, pseudo contours, neighboring vessels, or even noise. By incorporating the vessel feature term, that is, using ${\stackrel{\wedge}{\text{x}}}_{t+1}=f({q}_{\theta},{q}_{Z})$, the vessel tracking result can be improved, as shown in Figures 8(c1) and 8(c2). Using all terms together, that is, using ${\stackrel{\wedge}{\text{x}}}_{t+1}=f({q}_{\theta},{q}_{Z},{q}_{d})$, the vessel tracking result can be further improved; this is reflected as the smooth and accurate tracking paths detected in Figures 8(d1) and 8(d2). In addition, if only the vessel feature or diameter term is used, the tracking model almost stops near the initial seed position. These visual results are not shown here.

Figures 8(c1) and 8(c2) also yield a typical case in which the algorithm can successfully manage the close proximity or crossing of vessels, as well as varying vessel curvatures, which validates a number of attractive characteristics of the PTO. For example, the algorithm can run across the local vessel gap, proceed along the current vessel branch in spite of crossing, and successfully manage arterial stenoses and aneurysms.

The *diameter* estimation errors at the artery elements are less than 0.23 pixels on average. The results of the axis line estimation along the artery segments in the SAT image indicate that more errors appear near the nodes, with 1.36 pixels on average. These results show that the axis line estimation error at the nodes is controlled within a limited extent. For actual angiograms, we compared the automatically extracted arterial axis lines with the standard arterial centerlines delineated by an expert cardiologist. We also obtained good results, with a mean error of 0.17 pixels and the maximum error close to half of the respective vessel radius. These errors are produced by noise, as well as large curvatures or abnormal morphologies at the locations of vessel nodes.

#### Vessel stenosis

We tested a simple method to determine the position and severity of coronary artery stenosis in the given images, which can be used as an additional evaluation criterion for our tracking algorithm. Our algorithm was able to detect the arterial stenosis. An example in which the diameter of arterial stenosis is tracked and measured is shown in Figure 9. According to stenosis evaluation using the grading scheme of the visual analysis of the American Heart Association [17], %-LENGTH stenosis is estimated as %-LENGTH stenosis = (1-*L*
_{
r
}/*L*
_{
m
}) × 100%, where *L*
_{
r
} and *L*
_{
m
} are the estimates of the minimal diameter of the stenotic part of a vessel and the mean diameter of the nonstenotic part, respectively. During tracking and detection, the vessel length of interest begins or terminates when %-LENGTH is 25% higher or lower than the minimum classified value. The vessel length of interest can be described by the rectangular sash in Figure 9.

In the testing, 35 angiograms with 40 stenosis positions were used to evaluate the correctness of stenosis identification, in which all the standard vessel stenoses, as well as their severities were provided beforehand by the expert cardiologist. As a result, 33 stenosis objects are correctly detected and the number of false negatives and false positives are seven and one, respectively. The average correctness rate of stenosis severity identification reaches 68.3%, in comparison with the given stenosis severity levels.

## Discussion

In this paper, we analyzed image data and vessel structures within X-ray projections. A structure distinction exists between the crossing and bifurcation of vessel segments. Two crossing vessel segments have no spatial structure connection, whereas vessel bifurcations (which in general produce three vessel segments) have a structural connection among them. Vessel bifurcation enables low-level vessel segment separation to two high-level ones at the bifurcation point where these vessel segments have different features in their diameters and direction continuity. However, in single-view X-ray projection, two spatial overlapping vessel segments may appear connected to each other at a crossing-point, where the vessel segments maintain their respective features of diameter and direction continuity near the point. The abovementioned vessel continuity of different cases can address, in part, 2D structure ambiguity.

In our algorithm, three parameters can be adjusted to achieve better segmentation results. These include threshold value *r*
_{
λ
} in the vessel function Eq. (2), the radius of sampling disk *r*
_{
S
}, and the radius of pattern detector *r*
_{
D
}. These parameters can be adjusted according to the overall performance integrated from the three percentages, DAS %, EVL %, and IR %. For instance, parameter *r*
_{
λ
} may be optimized according to

The optimization for parameters *r*
_{
S
} and *r*
_{
D
} can be conducted similarly. Using the simulated images with different levels of noise, we can determine the optimal values for these three parameters. In the absence of noise, *r*
_{
λ
} is computed as ${r}_{\lambda}=-\sqrt{2\pi {\sigma}_{f}}$

; parameters *r*
_{
S
} and *r*
_{
D
} turn out to be equal, that is, *r*
_{
S
} = *r*
_{
D
}, and are both equal to current diameter *d*
_{
t
} of the vessel under tracking.

In the experiments, the time spent in tracking depends on the length of the detected vessel, look-ahead distance *s*
_{
t
}, and vessel diameter *d*
_{
t
}. Look-ahead distance *s*
_{
t
} is determined by the diameter of the sampling disk, which is designed to vary with the diameter of current vessel *d*
_{
t
}. The ranges of these parameters are 1 ≤ *s*
_{
t
} ≤ 7 (pixels) and 3 ≤ *d*
_{
t
} ≤ 15 (pixels), respectively, which agree with the required relationship 1 ≤ *s*
_{
t
} ≤ *d*
_{
t
}/2. Similarly, more artery elements can result in more computational time.

The rate of bifurcation identification (*N*^{b}/*W*^{b}) in the second column of Table 1 is related to EVL % and independent of IR % because the IR% is calculated only by the detected vessel points. In addition, the IR % of bifurcation and crossing are relatively lower than that of other structure patterns, which is mostly caused by the structure ambiguity in the 2D image acquisition. According to the testing on SAT, the error ratio is correlated with the effects of image noise and the diameter of the detector.

Based on the results on 40 stenosis objects, the application for the diagnosis of stenosis severity levels do not appear to be very reliable because of the use of single-view projection images. The accurate quantification and analysis of stenotic lesions is actually very complicated and has been elaborately discussed by Sato et al. in [18]. The importance of designing an acquisition system for acquiring "good" images, in which stenotic lesions can be displayed clearly, rather than simply analyzing the given images by common clinic systems, is therefore important.

## Conclusions

We developed a vessel tracking framework for the segmentation and measurement of the arterial tree in angiographic images, and applied it to actual clinical data. Based on the various evaluation results using both simulated and actual data, our algorithm demonstrates a very impressive performance in tracking and measuring artery trees. The particular advantages include efficient handling of vessel nodes, such as bifurcation or crossing; distinguishing between bifurcations and crossings, and automatically locating their positions; and automatic adaptation to varying vessel diameters in the coronary artery. These advantages were made clear with the introduction of our tracking strategies.

Our algorithms are able to locate stenosis or aneurysm positions in a number of given images. Naturally, the actual 3D morphology cannot be simply inferred through the 2D structure patterns. The use of 2D angiograms can pose ambiguity in determining vessel connectivity, particularly in cases with vessel overlapping. This indicates the importance of extending our algorithm to 3D applications to achieve certain diagnostic functions. Moreover, although our fuzzy inferring function is found relatively effective in integrating spatial characteristics of centerline, orientation, diameter, and density along the coronary blood vessels, the performance of structure pattern identification might be further improved, if we can effectively employ advanced learning-based methods, such as support vector machine, to identify the vessel structure patterns. These ideas will be explored further in our future studies.

## References

- 1.
Kawarada O, Yokoi Y, Morioka N, Nakata S, Higashiue S, Mori T, Iwahashi M, Hatada A:

**Carotid stenosis and peripheral artery disease in Japanese patients with coronary artery disease undergoing coronary artery bypass grafting.***Circ J*2003,**67:**1003–1006. 10.1253/circj.67.1003 - 2.
Jian Y, Yongtian W, Yue L, Songyuan T, Wufan C:

**Novel Approach for 3-D Reconstruction of Coronary Arteries From Two Uncalibrated Angiographic Images.***IEEE Trans Image Process*2009,**18**(7):1563–1572. 10.1109/TIP.2009.2017363 - 3.
Kirbas C, Quek FKH:

**A review of vessel extraction techniques and algorithms.***ACM Comput Surv*2004,**36**(2):81–121. 10.1145/1031120.1031121 - 4.
Schrijver M, Slump CH:

**Automatic segmentation of the coronary artery tree in angiographic projections.***Proceedings of ProRISC*2002, 449–464. - 5.
Behrens T, Rohr K, Stiehl HS:

**Robust segmentation of tubular structures in 3-D medical images by parametric object detection and tracking.***IEEE Transactions on Systems, Man, and Cybernetics - Part B, Cybernetics*2003,**33**(4):554–561. 10.1109/TSMCB.2003.814305 - 6.
Olabarriaga SD, Breeuwer M, Niessen WJ:

**Minimum cost path algorithm for coronary artery central axis tracking in CT images.***In proceedings of MICCAI*2003,**2879:**687–694. LNCS - 7.
Al-Kofahi KA, Can A, Lasek S, Szarowski DH, Dowell-Mesfin N, Shain W, Turner JN, Roysam B:

**Median-based robust algorithms for tracing neurons from noisy confocal microscope images.***IEEE Trans Inf Technol Biomed*2003,**7**(4):302–17. 10.1109/TITB.2003.816564 - 8.
Wink O, Niessen WJ, Viergever MA:

**Multiscale vessel tracking.***IEEE Trans Med Imaging*2004,**23**(1):130–133. 10.1109/TMI.2003.819920 - 9.
Tolias YA, Panas SM:

**A fuzzy vessel tracing algorithm for retinal images based on fuzzy clustering.***IEEE Trans Med Imaging*1998,**17**(2):263–273. 10.1109/42.700738 - 10.
Lorenz C, Carlsen I-C, Buzug TM, Fassnacht C, Weese J:

**Multi-scale line segmentation with automatic estimation of width, contrast and tangential direction in 2-D and 3-D medical images.***CVRMED-MRCAS'97*1997,**1205:**233–242. full_text - 11.
Sato Y, Nakajima S, Shiraga N, Atsumi H, Yoshida S, Koller T, Gerig G, Kikinis R:

**3D multi-scale line filter for segmentation and visualization of curvilinear structures in medical images.***Medical Image Analysis*1998,**2**(2):143–168. 10.1016/S1361-8415(98)80009-1 - 12.
Frangi AF, Niessen WJ, Vincken KL, Viergever MA:

**Multiscale vessel enhancement filtering.***Medical Image Computing and Computer-Assisted Intervention - MICCAI'98*1998,**1496:**130–137. - 13.
Krissian K, Malandain G, Ayache N, Vaillant R, Trousset Y:

**Model based detection of tubular structures in 3-D images.***Computer Vision and Image Understanding archive*2000,**80:**130–171. 10.1006/cviu.2000.0866 - 14.
Moreno P, Bernardino A, Santos-Victor J:

**Model based selection and classification of local features for recognition using Gabor filters.***Lecture Notes in Computer Science, Image Analysis and Recognition*2006,**4142:**181–192. full_text - 15.
Moreno P, Bernardino A, Santos-Victor J:

**Gabor parameter selection for local feature detection.***Lecture Notes in Computer Science, Pattern Recognition and Image Analysis*2005,**3522:**11–19. - 16.
Haris K, Efstratiadis SN, Maglaveras N, Pappas C, Gourassas J, Louridas G:

**Model-based morphological segmentation and labeling of coronary angiograms.***IEEE Trans Med Imaging*1999,**18**(10):1003–1015. 10.1109/42.811312 - 17.
Austen WG, Edwards JE, Frye RL, Gensini GG, Gott VL, Griffith LS, McGoon DC, Murphy ML, Roe BB:

**A reporting system on patients evaluated for coronary artery disease.***Circulation*1975,**51**(4):5–40. - 18.
Sato Y, Araki T, Hanayama M, Naito H, Tamura S:

**A viewpoint determination system for stenosis diagnosis and quantification in coronary angiographic image acquisition.***IEEE Trans Med Imaging*1998,**17**(1):121–137. 10.1109/42.668703

## Acknowledgements

This work was partly supported by the National Basic Research Program of China (Grant No. 2010CB732505) and the National Science Foundation of China (Project No. 60772120, and Project No. 60902103). We would like to thank the Cardiac Center of Beijing Chaoyang Hospital and the Radiology Department of Tianjin General Hospital for clinical assistance and providing coronary angiogram data.

## Author information

### Affiliations

### Corresponding author

## Additional information

### Competing interests

The authors declare that they have no competing interests.

### Authors' contributions

ZS carried out the studies on image pre-processing, modeling of vascular structure inferring and tracking, and drafting the manuscript. CW conceived of the study, and participated in its design and coordination, and helped in the drafting of the manuscript. YJ carried out the data acquisition and simulated the coronary artery tree. WY checked the paper writing. All authors read and approved the final manuscript.

## Authors’ original submitted files for images

Below are the links to the authors’ original submitted files for images.

## Rights and permissions

## About this article

### Cite this article

Shoujun, Z., Jian, Y., Yongtian, W. *et al.* Automatic segmentation of coronary angiograms based on fuzzy inferring and probabilistic tracking.
*BioMed Eng OnLine* **9, **40 (2010). https://0-doi-org.brum.beds.ac.uk/10.1186/1475-925X-9-40

Received:

Accepted:

Published:

DOI: https://0-doi-org.brum.beds.ac.uk/10.1186/1475-925X-9-40

### Keywords

- Vessel Diameter
- Structure Pattern
- Membership Degree
- Artery Segment
- Vessel Segment