A Comparative Study of Graph Search Algorithms for Segmenting Coronary Arteries from Cine Angiography

摘要

Accurate and timely segmentation of coronary vessels in quantitative coronary angiography (QCA) may be important toensure accurate patient diagnosis. This paper compares three variations of graph search algorithms for use in segmentingcoronary arteries in X-ray angiographic images. For comparing these algorithms, we propose a semi-automatic vesselsegmentation technique that combines Hessian-based filtering, Gabor filtering, and graph-based search routines for tracingthe boundaries1,2. This allows for a more automated procedure by incorporating automatic centerline detection while theuse of Gabor filtering promotes a more natural and geometrically continuous border segmentation1. The method requiresminimal effort by the user; the only manual input required is a start and end-point along the vessel of interest. Three graphsearch methods were compared by analyzing the accuracy and computational speed of the segmentations while using eachsearch technique: Dijkstra's algorithm, a restricted Dijkstra's algorithm, and the A* search algorithm were compared. Therestricted Dijkstra's and A* approaches reduced the computational time but resulted in low accuracies or outrightsegmentation failures. As outlined in the paper, Dijkstra's algorithm results in a superior segmentation with only a marginalincrease in computational time.