A linear programming based algorithm for determining corresponding point tuples in multiple vascular images

Two-view and multi-view imaging are the primary modalities for high-spatial-resolution imaging of the vascular ture. The 3D vascular structure can be reconstructed if the imaging geometries relating the views are determined using known corresponding point-pairs (or k-tuples) in the projection images. Because reconstruction accuracy improves with more input corresponding point-pairs, we propose a new technique to automatically determine corresponding point-pairs in multi-view (k view) images, from 2D vessel image centerlines. We formulate the problem, first as a multi-partite graph matching problem. Each 2D centerline point is a vertex; each individual part in the graph contains all vessel-points (vertices) in that image. The weight ('cost') of the edges between vertices (in different graphs) is the shortest distance between the points' respective projection-lines. Using this construction, a universe of mappings (k-tuples) is created, each k-tuple having k vertices (one from each image). A k-tuple's weight is the sum of pair-wise 'costs' of its members. Ideally, a set of such mappings is desired that preserves the ordering of points along the vessel and minimizes an appropriate global cost function, such that all vertices (in all graphs) participate in at least one mapping. We formulate this problem as a special case of the well-studied Set-Cover problem with additional constraints. Then, the equivalent linear program is solved, and randomized-rounding techniques are used to yield a feasible set of mappings. Our algorithm has a low running time and in simulations, the correct matching is achieved in ∼ 98% cases, even with high input error. In clinical data, apparently correct matching is achieved in about 90% cases. This method should provide the basis for improving the calculated 3D vasculature from multi-view data-sets.