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

Vikas Singh; Jinhui Xu; Kenneth R. Hoffmann; Peter B. Noël; Alan M. Walczak

doi:10.1117/12.651707

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

Vikas Singh, Jinhui Xu, Kenneth R. Hoffmann, Peter B. Noël, Alan M. Walczak

Author Affiliations +

Proceedings Volume 6144, Medical Imaging 2006: Image Processing; 61442D (2006) https://doi.org/10.1117/12.651707
Event: Medical Imaging, 2006, San Diego, California, United States

Abstract

Multi-view imaging is the primary modality for high-spatial-resolution imaging of the vasculature. The 3D vascular structure can be reconstructed if the imaging geometries are determined using known corresponding point-pairs (or k-tuples) in two or more images. Because the 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 graph contains all vessel-points (vertices) in an 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 is efficient and yields a theoretical quality guarantee. In simulations, the correct matching is achieved in ~98% cases, even with high input error. In clinical data, apparently correct matching is achieved in >90% cases. This method should provide the basis for improving the calculated 3D vasculature from multi-view data-sets.

Citation Download Citation

Vikas Singh, Jinhui Xu, Kenneth R. Hoffmann, Peter B. Noël, and Alan M. Walczak "A linear programming based algorithm for determining corresponding point tuples in multiple vascular images", Proc. SPIE 6144, Medical Imaging 2006: Image Processing, 61442D (10 March 2006); https://doi.org/10.1117/12.651707

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

3D image processing

Computer programming

Imaging systems

Reconstruction algorithms

3D image reconstruction

3D modeling

Angiography

Show All Keywords

Keywords/Phrases

Search In:

Publication Years