A novel multipurpose tree and path matching algorithm with application to airway trees

Jens N. Kaftan; Atilla P. Kiraly; David P. Naidich; Carol L. Novak

doi:10.1117/12.652440

13 March 2006 A novel multipurpose tree and path matching algorithm with application to airway trees

Jens N. Kaftan, Atilla P. Kiraly, David P. Naidich, Carol L. Novak

Proceedings Volume 6143, Medical Imaging 2006: Physiology, Function, and Structure from Medical Images; 61430N (2006) https://doi.org/10.1117/12.652440
Event: Medical Imaging, 2006, San Diego, California, United States

Abstract

Tree matching methods have numerous applications in medical imaging, including registration, anatomical labeling, segmentation, and navigation of structures such as vessels and airway trees. Typical methods for tree matching rely on conventional graph matching techniques and therefore suffer potential limitations such as sensitivity to the accuracy of the extracted tree structures, as well as dependence on the initial alignment. We present a novel path-based tree matching framework independent of graph matching. It is based on a point-by-point feature comparison of complete paths rather than branch points, and consequently is relatively unaffected by spurious airways and/or missing branches. A matching matrix is used to enforce one-to-one matching. Moreover our method can reliably match irregular tree structures, resulting from imperfect segmentation and centerline extraction. Also reflecting the nature of these features, our method does not require a precise alignment or registration of tree structures. To test our method we used two thoracic CT scans from each of ten patients, with a median inter-scan interval of 3 months (range 0.5 to 10 months). The bronchial tree structure was automatically extracted from each scan and a ground truth of matching paths was established between each pair of tree structures. Overall 87% of 702 airway paths (average 35.1 per patient matched both ways) were correctly matched using this technique. Based on this success we also present preliminary results of airway-to-artery matching using our proposed methodology.

Citation Download Citation

Jens N. Kaftan, Atilla P. Kiraly, David P. Naidich, and Carol L. Novak "A novel multipurpose tree and path matching algorithm with application to airway trees", Proc. SPIE 6143, Medical Imaging 2006: Physiology, Function, and Structure from Medical Images, 61430N (13 March 2006); https://doi.org/10.1117/12.652440

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