A Novel Multi-Purpose Tree and Path Matching Algorithm with Application to Airway Trees

摘要

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.