Related Experiment Video
Updated: Jul 15, 2026
Protocol for Isolating the Mouse Circle of Willis
Published on: October 22, 2016
Effects of Path-Finding Algorithms on the Labeling of the Centerlines of Circle of Willis Arteries
1Division of Digital Healthcare, College of Software and Digital Healthcare Convergence, Yonsei University, Wonju 26493, Republic of Korea.
Insights
Dijkstra's algorithm achieved the highest accuracy (97.1%) in automatically identifying intracranial vessel centerlines, outperforming depth-first search and A* algorithms for accurate vessel labeling in brain imaging.
Area of Science:
- Medical Imaging
- Computational Anatomy
- Neuroscience
Background:
- Accurate quantitative analysis of intracranial vessels relies on precise centerline identification.
- Path-finding algorithms offer automated solutions for detecting vessel centerlines in medical imaging.
Purpose of the Study:
- To compare the performance of three path-finding algorithms for intracranial vessel segmentation and labeling.
- To evaluate the accuracy and efficiency of depth-first search, Dijkstra's, and A* algorithms in analyzing 3D MRA data.
Main Methods:
- Utilized 3D time-of-flight magnetic resonance angiography (MRA) datasets.
- Manually annotated vessel segment endpoints.
- Compared depth-first search, Dijkstra's algorithm, and A* algorithm for path-finding accuracy.
Main Results:
- Dijkstra's algorithm demonstrated the highest accuracy (97.1%) in correctly identifying vessel paths.
- A* algorithm achieved 96.1% accuracy, while depth-first search showed 83.5% accuracy.
- Depth-first search exhibited significant inaccuracies in specific arteries like the AComm artery.
Conclusions:
- Dijkstra's algorithm is the most accurate method for automated intracranial vessel centerline detection among the tested algorithms.
- Dijkstra's and A* algorithms offer comparable accuracy and speed for analyzing the circle of Willis arterial segments.
- Accurate vessel segmentation is crucial for quantitative analysis in neuroimaging studies.
Abstract:
Quantitative analysis of intracranial vessel segments typically requires the identification of the vessels' centerlines, and a path-finding algorithm can be used to automatically detect vessel segments' centerlines. This study compared the performance of path-finding algorithms for vessel labeling. Three-dimensional (3D) time-of-flight magnetic resonance angiography (MRA) images from the publicly available dataset were considered for this study. After manual annotations of the endpoints of each vessel segment, three path-finding methods were compared: (Method 1) depth-first search algorithm, (Method 2) Dijkstra's algorithm, and (Method 3) A* algorithm. The rate of correctly found paths was quantified and compared among the three methods in each segment of the circle of Willis arteries. In the analysis of 840 vessel segments, Method 2 showed the highest accuracy (97.1%) of correctly found paths, while Method 1 and 3 showed an accuracy of 83.5% and 96.1%, respectively. The AComm artery was highly inaccurately identified in Method 1, with an accuracy of 43.2%. Incorrect paths by Method 2 were noted in the R-ICA, L-ICA, and R-PCA-P1 segments. The Dijkstra and A* algorithms showed similar accuracy in path-finding, and they were comparable in the speed of path-finding in the circle of Willis arterial segments.
More Related Videos
03:26Author Spotlight: Advancing Stroke Research with Periorbital Doppler Monitoring of Regional Cerebral Blood Flow in Rodent Models
Published on: November 22, 2024
05:23Author Spotlight: Noninvasive Cerebral Blood Flow Determination in Human Functional Brain Region for Diagnosis of Neurological Disorders
Published on: May 31, 2024
