Multi-line matching for vessel formation in X-ray coronarography: a comparison of three algorithms

In this paper, we make use of the Attributed String Matching (ASM) technique to deal with three-lines matching in the frame of the formation of high-level entities in X-ray coronarography. Input data are free form shapes of different length representing the vessels contour and the centreline, extracted at a previous stage. We propose to associate these two type of information to reconstitute sets or sub-sets of vascular branches and remove inconsistencies coming from the errors of the detection. Two types of algorithms were implemented which respectively rely on (1) a pairwise comparison of the three lines by applying twice Wagner and Fisher algorithm for successively matching pairs of lines (2) a simultaneous three lines matching based first on a extension of Wagner and Fisher algorithm, then on the Sankoff developed approach. Their performances are compared on simulated data.