Improved association graph matching of intra-patient airway trees

Pulmonary diseases are frequently associated with changes in lung anatomy. These diseases may change the airway, vessel and lung tissue properties. In order to evaluate the lung in a longitudinal study, a stable reference system is required to identify corresponding parts of the lung. The structure of the airway tree can be used to repeatedly identify the regions of interest. In this study, an improved method for matching of intra-patient airway trees was proposed and evaluated. The association graph method proposed by Pelillo et al. matches free and rooted trees by detecting the maximal sub-tree isomorphism. Tschirren et al. implemented this approach for labeling and matching of human airway trees and reported 92.9% matching accuracy which is the highest among existing methods. However we recognized a few shortcomings of this method. When we tested it on seven normal human cases, we observed that successful matching relies heavily on the accurate labeling of main branchpoints in the trees. Incorrect labeling of main branch points or failure in labeling results in failure to match that branch point. Such matching errors may eventually propagate to sub-trees. On our seven data samples, matching accuracy was found to be as low as 65%.

To improve the matching performance, we propose to make matching independent of labeling as well as improve association graph by adding constraint of path-length along with the existing constraints. Furthermore, we would like to redefine the incorrect matches as those matches which are mismatched as well as those that are missed by the matching algorithm. Our results for a total of 27 cases show a significant improvement in accuracy. The accuracy calculated as per the convention without accounting for the branchpoint pairs missed by the algorithm is 92.19% whereas the accuracy calculated as per our definition is 73.98%, with runtime in the range of 0.01-262.81 sec (average runtime is 25.14 sec). We thus propose an improved association graph method which is efficient in matching intra-patient airway trees with good accuracy and within

a reasonable time.