Effects of Path-Finding Algorithms on the Labeling of the Centerlines of Circle of Willis Arteries

• Published in: Tomography (Ann Arbor) 2023-07, Vol.9 (4), p.1423-1433
• Main Authors: Kim, Se-On, Kim, Yoon-Chul
• Format: Article
• Language: English
• Subjects: A algorithm; Algorithms; Arteries; cerebral arteries; Circle of Willis; Comparative analysis; Dijkstra algorithm; graph structure; magnetic resonance angiography; vessel segmentation
• ISSN: 2379-139X; 2379-1381; 2379-139X
• DOI: 10.3390/tomography9040113

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.