An Advanced Automatic Fuzzy Rule-Based Algorithm for 3D Vessel Segmentation

Mohamed A. Abdou; Ashraf El-Sayed; Eman Ali

doi:10.2991/ijcis.11.1.7

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 11, Issue 1, 2018, Pages 79 - 85

An Advanced Automatic Fuzzy Rule-Based Algorithm for 3D Vessel Segmentation

Authors

Mohamed A. Abdou^*^{, 1}^,m.abdou@pua.edu.eg, Ashraf El-Sayed²^,ashraf.elsayed@alexu.edu.eg, Eman Ali²^,eman_ali3@alexu.edu.eg

¹Informatics Research Institute, City for Scientific, Research & Technology Applications, Alexandria, Egypt†

²Department of Mathematics and Computer science, Faculty of science, Alexandria University, Alexandria, Egypt

^*Corresponding author.

Corresponding Author

Mohamed A. Abdoum.abdou@pua.edu.eg

Received 10 December 2016, Accepted 4 September 2017, Available Online 1 January 2018.

DOI: 10.2991/ijcis.11.1.7 How to use a DOI?
Keywords: Fuzzy systems; Hessian matrix; Frangi filter parameters; Chan-Vese segmentation method; and automatic 3D vessel extraction
Abstract: Fuzzy Logic has played an important role in medical image (MI) segmentation in the last decade. Automatic blood vessel segmentation from 3D medical images is an emerging area where segmentation algorithms could be combined with evolutionary computation methods for better diagnosis and higher decision accuracy. This paper introduces an automatic blood vessel segmentation algorithm from 3D images using Fuzzy logic. The proposed fuzzy system decides degree of Vesselness according to Eigen values of Hessian matrix. 3D synthetic and real CTA clinical image database are used to test the proposed algorithm and show a correct voxel classification. The proposed method shows better segmentation results compared to manual and swarm intelligence methods. Furthermore, fuzzy has led to better time improvement.
Copyright: © 2018, the Authors. Published by Atlantis Press.
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Blood vessels segmentation from 3D images is still a challenging problem due to many reasons: dimensionality of MI acquisition problems, noise attack, complex structure and shape of vessels, variability in blood vessels’ size, and finally vessels’ overlap with other organs¹. Researchers in the past few years proposed various segmentation techniques for blood vessels to fit with different organs, image modalities, and applications. Pattern recognition techniques, model-based approaches, vessel tracking, and matched filtering are all methods introduced to solve this problem².

Hessian-based multi -scale filtering gained significant importance in this area³. Based on Eigen values of the Hessian matrix, this method tries to find the probability of each 3D voxel to specify blood vessel tubular structure. However, Hessian-based filtering encounters problems due to image discontinuity, which leads to wrong vessels’ classification. In Ref. 4, Morphological top hat transformation, Hessian filtering followed by Chan-Vese level set has been used to extract vascular structures from the enhanced image. A common problem with this filter is how to find the parameters of Frangi filter. The manual parameter selection is very common since these parameters vary with image modality and intensity. Evolutionary computational methods have succeeded to solve this problem using particle-swarm optimization (PSO) as in Ref. 5. In our previous work5, PSO was used to optimize parameters of Frangi filter3. Although that work gave good segmentation results compared to manual and semiautomatic methods, it showed the high computational complexity and large execution time. This could be due to swarming idea that usually begins randomly. For such reasons, work continues for better solving such problems. The execution time is one challenging facing the PSO-based segmentation algorithm.

Fuzzy approach has successfully solved several engineering and medical problems⁶. Fuzzy logic surpasses conventional mathematical algorithms in classifications and clustering⁷. Depending on the number of uncertainty levels in the model, the computational burden can increase dramatically and the working time. Management of uncertainty is a necessity in the design of many systems, where the information in the knowledge base is ambiguous and imprecise. This particular kind of uncertainty is best-modeled using fuzzy numbers, as they allow dealing with such type of quantifiers. In this paper, we are attacking the manual Frangi filter problem using conventional fuzzy sets⁸.

The paper is divided into four sections: Section 2 explains the proposed fuzzy based segmentation technique including fuzzy enhancement map and multiscale top hat transformation. Section 3 presents the obtained results for both synthetic and real 3D data. Comparison with state of the art work is introduced. Finally, Section 4 presents the conclusion.

2. Proposed Fuzzy-Based Segmentation Technique for 3D Vessel Extraction

2.1 Highlights on Frangi Enhancement Algorithm

Hessian matrix and mathematical morphology are now used to compensate against poor 3D medical images quality. These are considered to prompt the structure of the blood vessels at different scales^9,10. In this work, we are concerned with Frangi enhancement filter from Ref. 3 to find the Vesselness degree of the voxel in 3D images. Vesselness degree identifies whether a voxel will be considered vessel or not. They depend on the analysis of Eigen values of Hessian matrix where Hessian matrix of a voxel (x, y, z) at scale σ is defined by applying the convolution with a derivative of Gaussian on the 3D image in Eq. (1), and then constructs Hessian Matrix Eq. (2).

(1)I(x,y,z,σ)=G(x,y,z,σ)*I(x,y,z)G(x,y,z,σ)=1(2πσ2)3e(−x2+y2+z22σ2)

(2)H=(∂2I∂x2∂2I∂x∂y∂2I∂x∂z∂2I∂y∂x∂2I∂y2∂2I∂y∂z∂2I∂z∂x∂2I∂z∂y∂2I∂z2)

where I is the 3D image with vertices (x, y, z), and G is the Gaussian function with standard deviation σ. Frangi defined two dissimilarity ratios: R_B applied to distinguish blob-like structures, and R_A to distinguish tube-like structures. Eq. (3) and Eq. (4) gives these ratios:

(3)RB=| λ1 || λ2λ3 |

(4)RA=| λ2 || λ3 |

Where λ₁, λ₂, and λ₃ are the Eigen values of Hessian matrix.

Frangi also introduced a value called S, as shown in Eq. (5) to distinguish between the background and vessel.

(5)S=λ 12+λ 22+λ 32

Finally, Frangi defined the Vesselness function ν_σ in Eq. (6) that defines the probability of each pixel to being a vessel by the combination of three components R_A, R_B, and S.

(6)νσ(σ)={ 0, if λ2>0 or λ3>0(1−exp(−R A22α2))exp(−R B22β2)(1−exp(−S22c2))O.W

Where α, β and c are thresholds that control the filter sensitivity to the measures R_A, R_B, and S. α ∈ [0, 1], β ∈ [0, 1] and c depend on the grey-scale of the image. They applied the Vesselness function ν_σ at different σ and took the greatest response above all σ, where σ_min and σ_max is the minimum and maximum scales and defined in Eq. (7).

(7)v1=maxσmin≤σ≤σmax{vσ(σ)}

2.2 Problem Definition

In Ref. 3, Frangi tried to put the relation between the Vesselness degree and the three Eigen values of each value as a set of rules. For example, a pixel belongs to vessel if λ₁ is small (ideally zero), and λ₂ and λ₃ are large magnitude and equal signed. Those relations between the three Eigen values could derive the degree that a voxel becomes vessel or not (Vesselness degree). A work focused on the three parameters in Eq. (3): α, β and c, to find optimum values by guessing the proper constant values and using traditional optimization methods³. In our recent work⁵, we used swarm intelligence methods to find optimum solutions and reached encouraging results. However, we had a serious problem regarding time complexity added by the PSO. In this paper, we are trying to formulate segmentation rules by introducing a fuzzy rule based classification that will classify whether a 3D pixel (voxel) is a vessel or not according to the obtained Eigen-values of the Hessian matrix. This is expected to reduce time complexity as will be shown in the incoming sections.

2.3 Fuzzy Enhancement Map

To specify Vesselness degree, fuzzy enhancement map is to be introduced. The detailed model of the system is depicted in figure 1. We represent our fuzzy-based system in figure 2. The inputs to the fuzzy system are three Eigen values derived from Hessian matrix at each voxel. Each input has three membership function: low (L), high positive (H+) and high negative (H−). The range of the membership function is the range of Eigen values in images [min (λ_i) max (λ_i)] and has a Gaussian distribution. Fuzzy system outputs are fuzzy mapping values represents the intensity values of 3D image after the mapping. The membership function of the output has the triangular distribution and range value [0, 1] where the higher value is a vessel. The rules set used by fuzzy mapping defined in table 1. We applied fuzzy mapping at different σ values of Gaussian convolution and took the greatest probability value. We can adapt the fuzzy mapping for applying on dark vessels by adopting fuzzy rules and changing the sign of λ₂ and λ_3.

3D			Result

λ₁	λ₂	λ₃
		H+	NV
		L	NV
	L	H−	NV
	H+	H−	NV
L	H−	H−	V

Table 1.

Possible-mapping values in 3D images depending on Eigen values of Hessian matrix. L=low, H=high, V=vessel, NV=non-vessel.

2.4 Chan-Vese Segmentation Algorithm

In this work, we use a segmentation method based on level set introduced by Osher and Sethian¹¹ and applied in a previous work⁵. It is to start with the regularized version of Heaviside function and the one-dimensional Dirac, H_ε and δ_ε respectively are defined in Eq. (8). ε = 1, and we can rewrite the evolution equation F as in Eq.(9).

(8)Hɛ(∅)={1,∅>ɛ0,∅<−ɛ 12(1+2πarctan(Øɛ)),|∅|≤ɛ δɛ(∅)=dd∅Hɛ(∅)

(9)Fnew=(B(x,y)+1).Fcv(C1,C1,Ø)=δɛ(∅)[ μ∇.∇∅| ∇∅ |−α−λ1(I0−C1)2+λ2(I0−C2)2 ]+B(x,y).δɛ(∅)[ μ∇.∇∅| ∇∅ |−α−λ1(I0−C1)2+λ2(I0−C2)2 ],

where C₀ is the initial contour obtained by using Otsu’s Thresholding¹², C₁ and C₂ in terms of Ø in Eq. (10).

(10)C1(∅)=∫ΩI0(x,y)H(∅(x,y))dxdy∫ΩH(∅(x,y))dxdy,C2(∅)=∫ΩI0(x,y)H(1−∅(x,y))dxdy∫ΩH(1−∅(x,y))dxdy,

where B (x, y) is defined as:

(11)B(x,y)={ 0,| Ct(x,y)−C0 |<dσ,−1,otherwise,

where d_σ is the largest contour evolution distance and sets to σ_max/2, and |C_t(x, y) − C₀| is the evolution distance in a point (x, y) from the first contour and σ (the greatest standard deviation of Gaussian function used in Fuzzy-based system) because Gaussian convolution tends to blur vessel boundaries.

3. Results and Discussion

3.1 Metrics and Data

To evaluate the proposed automatic fuzzy Vesselness algorithm, four metrics will be used: mean square error (MSE), Peak signal to noise ratio (PSNR), Jaccard distance (JD), and segmentation ratio (SR). Furthermore, 3D image data from Vascusynth library¹³ will be used as the testing environment. Working environment is a laptop with Intel core (TM) i7-4720HQ CPU @ 2.60 GH- 16 GB RAM- 64-bit Operating System, x64-based processor.

3.2 Noise Attack

Medical data always suffer noise problem. To check the reliability of recent algorithm working on medical data, it is important to validate the proposed ideas in a noisy environment. Vascusynth data will be blurred using a 3*3 Gaussian window, 0.5 standard deviation, 0.01 mean and 0.001 variance of Gaussian noise.

3.3 Comparison criteria

The proposed fuzzy-rule based algorithm results will be compared with two methods: manual Jin’s algorithm⁴ and the automatic PSO-based algorithm⁵. Results are shown for two case studies from synthetic data and one case study from clinical data. Figure 3 and 4 show two different case studies when applying the three algorithms for vessel segmentation. From these figures, it could be shown that the proposed fuzzy system reaches values better than manual method and automatic PSO-based algorithm. Acceptable blood vessel shapes either for 3D or 2D-slice images.

Table 2 specifies obtained values for the four metrics. From this table it could be observed that the introduced fuzzy algorithm achieves less MSE when compared to Jin manual method⁴ and when compared with PSO algorithm presented in Ref. 5. The reasons are that fuzzy logic could work as a better classifier when compared to PSO, and it surpasses manual methods that suffer physicians and hand errors.

		Jin’s manual algorithm⁴.	PSO based algorithm⁵	Proposed Fuzzy algorithm
Case Study (1)	MSE	0.0051	0.0035	0.0032
	PSNR	22.9499	24.5448	24.901
	JD	0.5144	0.4386	0.3455
	SR	0.5084	0.6522	1.2683

Case Study (2)	MSE	0.0063	0.0045	0.0026
	PSNR	22.0232	23.4746	25.9315
	JD	0.5305	0.4576	0.3322
	SR	0.4776	0.5876	1.2797

Table 2:

Four metrics obtained using three different segmentation algorithms

Figure 5 and table 3 give a similar comparison while using experimental CTA clinical data. The dataset used is VESSEL12. Obtained results assure that the proposed fuzzy based algorithm maintains the structure and the shape of the blood vessels where compared to the manual method and other automatic algorithm.

		Jin’s manual algorithm⁴.	PSO based algorithm⁵	Proposed Fuzzy algorithm
Case Study (3)	MSE	0.1798	0.1757	0.1492
	PSNR	7.4531	7.5525	8.2612
	JD	0.9899	0.9891	0.9890
	SR	0.6719	0. 6367	0.3905

Table 3:

Four metrics obtained using three different segmentation algorithms

3.4 Complexity and Time Performance

Table 4 compares both automatic methods. From this table, we can observe that the fuzzy rule-based algorithm working on Eigen values of the Hessian matrix outperforms the PSO-based algorithm in Ref. 5 working on Frangi filter parameters from complexity and execution time points of view. Time improvement reaches 140%, which makes it more effective and accurate an automatic segmentation algorithm.

Execution Time (sec)			% Time Improvement

	PSO Algorithm⁵.	Fuzzy Algorithm
Case study (1)	149.941977	28.451363	136.205 %
Case study (2)	130.105725	28.96342	127.168 %
Case study (3)	1326.84781	148.300506	159.787 %

Table 4:

automatic vessel segmentation algorithm comparison

4. Conclusions

This paper proposes an automatic blood vessel extraction from 3D medical images using Fuzzy sets. Fuzzy sets are used to estimate Vesselness degree of each voxel in 3D images according to Hessian matrix Eigen values. Two state of the art work algorithms from Ref. 4 and 5 are selected to compare and validate the proposed algorithm. Results show that Fuzzy-based algorithm yields to better PSNR, and less error. Experiments on both the synthetics and real 3D images show that our automatic algorithm is effective and detects most blood vessels from 3D images from both visual inspection and image quality metrics. From execution time point of view, fuzzy-based algorithm has overcome time complexity when compared to PSO-based algorithm by an average value of 140%. In our future work, we will try to parallelize our algorithms to achieve better performance.

References

1.D Lesage, ED Angelini, I Bloch, and G Funka-Lea, A review of 3D vessel lumen segmentation techniques: Models, features and extraction schemes, Medical Image Analysis, Vol. 13, No. 6, 2009, pp. 819-845.

2.C Kirbas and F Quek, A review of vessel extraction techniques and algorithms, ACM Computing Surveys, Vol. 36, No. 2, 2004, pp. 81-121.

3.AF Frangi, WJ Niessen, KL Vincken, and MA Viergever, Multiscale vessel enhancement filtering, Medical Image Computing and Computer-Assisted Intervention —MICCAI’98 Lecture Notes in Computer Science, 1998, pp. 130-137.

4.J Jin, L Yang, X Zhang, and M Ding, Vascular Tree Segmentation in Medical Images Using Hessian-Based Multiscale Filtering and Level Set Method, Computational and Mathematical Methods in Medicine, Vol. 2013, 2013, pp. 1-9.

5.E Ali, MA Abdou, and A Elsayed, Automatic Vessel Extraction Using Particle Swarming Optimization for 3D Medical Images, Current Medical Imaging Reviews, Vol. 13, 2017, pp. 1-7.

6.M Mahfouf, M Abbod, and D Linkens, A survey of fuzzy logic monitoring and control utilization in medicine, Artificial Intelligence in Medicine, Vol. 21, 2001, pp. 27-42.

7.SK Guirguis, MA Abdou, and AA ElNaggar, A Hybrid Fuzzy Multi-hop Unequal Clustering Algorithm for Dense Wireless Sensor Networks, International Journal of Computational Intelligence Systems, Vol. 10, 2017, pp. 951-961.

8.L Zadeh, Fuzzy sets, Information and Control, Vol. 8, No. 3, 1965, pp. 338-353.

9.X Bai, F Zhou, and B Xue, Image enhancement using multi scale image features extracted by top hat transform, Optics & Laser Technology, Vol. 44, No. 2, 2012, pp. 328-336.

10.M Liao, Y-Q Zhao, X-H Wang, and P-S Dai, Retinal vessel enhancement based on multi-scale top-hat transformation and histogram fitting stretching, Optics & Laser Technology, Vol. 58, 2014, pp. 56-62.

11.S Osher and JA Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, Vol. 79, No. 1, 1988, pp. 12-49.

12.NA Otsu, Threshold Selection Method from Gray-Level Histograms, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 9, No. 1, 1979, pp. 62-66.

13.G Hamarneh and P Jassi, VascuSynth: Simulating vascular trees for generating volumetric image data with ground-truth segmentation and tree analysis, Computerized Medical Imaging and Graphics, Vol. 34, No. 8, 2010, pp. 605-616.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 11 - 1
Pages: 79 - 85
Publication Date: 2018/01/01
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.11.1.7 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Mohamed A. Abdou
AU  - Ashraf El-Sayed
AU  - Eman Ali
PY  - 2018
DA  - 2018/01/01
TI  - An Advanced Automatic Fuzzy Rule-Based Algorithm for 3D Vessel Segmentation
JO  - International Journal of Computational Intelligence Systems
SP  - 79
EP  - 85
VL  - 11
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.11.1.7
DO  - 10.2991/ijcis.11.1.7
ID  - Abdou2018
ER  -

download .riscopy to clipboard