Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC2077841

Formats

Article sections

- Abstract
- I. INTRODUCTION
- II. MATCHING WITH ASSOCIATION GRAPH METHOD
- III. BRANCHPOINT MATCHING
- IV. ANATOMICAL LABELING
- V. VALIDATION — BRANCHPOINT MATCHING
- VI. VALIDATION — ANATOMICAL LABELING
- VII. CONCLUSION
- References

Authors

Related links

IEEE Trans Med Imaging. Author manuscript; available in PMC 2007 November 14.

Published in final edited form as:

PMCID: PMC2077841

NIHMSID: NIHMS4742

Juerg Tschirren, Member IEEE, Geoffrey McLennan, Kálmán Palágyi, Eric A. Hoffman, and Milan Sonka, Fellow IEEE

Juerg Tschirren, Department of Electrical and Computer Engineering, The University of Iowa, Iowa City, IA, USA;

The publisher's final edited version of this article is available at IEEE Trans Med Imaging

See other articles in PMC that cite the published article.

Matching of corresponding branchpoints between two human airway trees, as well as assigning anatomical names to the segments and branchpoints of the human airway tree, are of significant interest for clinical applications and physiological studies. In the past these tasks were often performed manually due to the lack of automated algorithms that can tolerate false branches and anatomical variability typical for in vivo trees. In this paper we present algorithms that perform both matching of branchpoints and anatomical labeling of in vivo trees without any human intervention and within a short computing time. No hand-pruning of false branches is required. The results from the automated methods show a high degree of accuracy when validated against reference data provided by human experts. 92.9% of the verifiable branchpoint matches found by the computer agree with experts’ results. For anatomical labeling, 97.1% of the automatically assigned segment labels were found to be correct.

The quantitative assessment of intrathoracic airway trees is critically important for the objective evaluation of the bronchial tree structure and function. Functional understanding of pulmonary anatomy, as well as the natural course of respiratory diseases like asthma, emphysema, cystic fibrosis, and many others, is limited by our inability to repeatedly evaluate the same region of the lungs time after time and perform accurate and reliable positionally corresponding measurements. Several approaches to three-dimensional reconstruction of the airway tree have been developed in the past. None of them, however, allows the direct comparison of airway trees across and within subjects.

The first six generations, roughly, of the human airway tree exhibit a relatively similar topology across subjects, and anatomical names exist for 31 segments and 42 sub-segments [1]. Beyond that, the branching structure gets variable and differs very much from subject to subject.

The term *branchpoint matching* is used for the process of finding corresponding branchpoints between two different scans of the same subject (intra-subject case; e.g., imaged in a longitudinal study or imaged at different lung volumes). This process is based on the similarities of the two input trees and finds matching branchpoints not only for the named segments but also beyond them.

The *anatomical labeling* algorithm presented here aims to assign 32 anatomical names to their respective segments (the left inferior bronchus was divided into two parts, which accounts for the one additional segmental name compared to the standard nomenclature). Labeling an airway tree does not only simplify the navigation of the tree in applications like virtual bronchoscopy, but also allows matching of branchpoints across subjects (inter-subject case). Another application of anatomical labeling is the identification of lobar and sub-lobar structures, which can, for example, be used for surgical planning.

Both branchpoint matching and anatomical labeling are tedious and error-prone to perform manually; consequently the goal is to automate these tasks. Working with human in-vivo data poses challenges. In-vivo trees deviate from ideal trees because of anatomical variations and because of false-branches introduced by imperfections of the preceding segmentation and skeletonization processes.

Branchpoint matching was mostly done manually in the past [2]. A few attempts of automating the process were undertaken. Pisupati et al. [3], [4] presented a matching algorithm based on dynamic programming that, however, was only applied to very similar pairs of canine trees, and the authors state that they expect the method to fail on human in-vivo scans. Park [5] presented a tree-matching method based on an association graph [6], but his method was applied only to phantom data and it does not tolerate false branches.

Publications about automated anatomical labeling are similarly sparse. Mori et al. [7] presented a knowledge-based labeling algorithm. The proposed algorithm was only applied to incomplete trees (about 30 branches per tree), and the builtin knowledge base did not incorporate anatomical variations. Additionally, the algorithm is sensitive to missing and spurious (false) branches. Kitaoka et al. [8] developed a branchpoint labeling algorithm that uses a mathematical phantom as reference. Labels are assigned by matching the target tree against this phantom. The method can not automatically handle false branches – they have to be pruned manually in a preprocessing step.

In a first step the airway tree is segmented from volumetric computed tomography (CT) images [9], [10] and then skeletonized [11], [12]. Branchpoints are detected in the skeletonization result, and the tree is represented as a directed acyclic graph (DAG) (Figure 1). This DAG is used as input for both the branchpoint matching and the anatomical labeling processes.

Branchpoint matching and anatomical labeling are both based on matching hierarchical structures (mathematical graphs) using association graphs [6]. Using association graphs for finding graph isomorphisms is a well known technique that has been introduced more than 20 years ago [13].

An association graph is an auxiliary graph structure derived from the two graph structures to be matched. A graph *G* = (*V*, *E*) consists of a set of vertices *V* and a set of edges *E*. For two graphs *G*_{1} and *G*_{2}, an association graph *G*_{ag} = (*V*_{ag}, *E*_{ag}) consists of the vertices *V*_{ag} = *V*_{1} × *V*_{2}. I.e., it contains a vertex for every possible pair of vertices in *G*_{1} and *G*_{2}. Two vertices in *G*_{ag} are connected with an edge if and only if the corresponding vertices in *G*_{1} and *G*_{2} stand in the same relationship to each other (e.g., inheritance relationship, topological distance, etc.). The *maximum clique* in the association graph, i.e., the biggest sub-set of vertices where every pair of vertices is connected by an edge, corresponds to the maximal subtree isomorphism. Each vertex contained in the maximum clique represents a pair of matching vertices in the original graphs. It has been shown [14] that the problem of finding the maximum clique is an NP-complete problem. This paper introduces methods that help keeping the required computing time within very reasonable limits.

One big association graph could be constructed from the two input-trees – creating one association graph vertex for every possible pair of matching vertices in the input trees – and the matching could then be performed in a single step. However, this approach is not practical because of the exponential computational complexity of the matching task. Steps have to be taken to reduce the computing time. Two possibilities exist to do this: reduce the overall problem size, or split the problem into a number of sub-problems. Both of these tactics are applied in the method presented here. The matching is performed in four main steps:

- Delete (prune) spurious branches from input trees.
- Align the two input trees by performing a rigid registration.
- Find and match major branchpoints.
- Match sub-trees underneath major branchpoints, one pair of sub-trees at a time.

The input trees contain some false branches, i.e., branches that do not represent real anatomical segments. False branches exist because of the often uneven surface of the segmentation result, which is caused by minor segmentation problems or by anatomical irregularities. Deleting false branches eliminates potential false matches and also reduces the problem size.

Pruning is performed in two steps: 1) delete terminal edges that are shorter than a predefined threshold length _{th}, 2) delete vertices that are left in the graph after a terminal edge was deleted in step 1, i.e., vertices that have only one remaining out-edge and connect parent- and child-vertices directly. An out-edge is defined as an edge emanating from a vertex.

The two input trees undergo a rigid registration with the goal of bringing potentially matching branchpoints as close to each other as possible. This restricts the search for matches to a relatively close perimeter, which reduces the problem size and consequently speeds up computing time. Registration is performed such that the carinas are superimposed (the carina is the first main branchpoint of the airway tree, where the trachea splits into the two main bronchi) and the angles between the corresponding main bronchi of the two trees are minimized.

Performing this registration first requires the identification of the carina and the left and right bronchus of each tree, which is done as follows. For every tree a depth-first search is performed, which labels every edge *e* with the minimum and maximum values of the *x*, *y*, and *z* positions of all vertices that are situated topologically underneath of *e* (all child-branches of *e*), designated as *x*_{min}(*e*), *x*_{max}(*e*), …, *z*_{max}(*e*). The number of vertices found topologically underneath of *e* is recorded as well, designated as *N* (*e*).

The *spatial extents* Δ* _{x}*(

Once the carina and the main bronchi have been identified, the registration itself is performed using a simple affine transformation.

To reduce computing time, the matching of the remaining branchpoints is performed in two main steps. First, only *major branchpoints* – branchpoints that are a parent of subtrees with substantial size – are matched. Second, starting from pairs of matched major branchpoints, sub-trees are matched, only one pair of sub-trees at a time.

A prerequisite for building the association graph is that, for each of the two input trees, the *inheritance relationship* and the *topological distance* between any two vertices is known. The topological distance is an integer that quantifies the number of edges between two vertices. To allow an easy and efficient lookup of these properties, the two-dimensional *vertex relationship array *
${\mathcal{R}}_{v}$of dimension *N* × *N* is computed, where *N* stands for the number of vertices in the respective tree. The cell
${\mathcal{R}}_{v}(s,t)$ of
${\mathcal{R}}_{v}$ contains the inheritance relationship *r*_{s,t} {PARENT, CHILD, SIBLING, N/A} and the topological distance *d*_{s,t} between the source vertex *s* and the target vertex *t*, with (*r*_{s,t} = N/A, *d*_{s,t} = 0) *s* = *t*. For *s* ≠ *t* only one of the three inheritance relationships PARENT, CHILD, and SIBLING is possible and *d*_{s,t} ≥ 1. If vertex *n* is not a direct descendant of vertex *m* and *m* is not a direct descendant of *n* then *r*_{n,m} = *r*_{m,n} = SIBLING. In other words, two vertices in neighboring branches or sub-trees are always labeled as SIBLINGS, no matter how many edges lie between them. No inheritance relationship like COUSIN, NEPHEW or similar is assigned. Using this simplified inheritance model has two advantages. First, it simplifies the handling of trifurcations that may occur in form of two bifurcations that follow each other within a short distance, and that may occur in different order in the second tree. Whatever the order of the two bifurcations, the vertices that are topologically below the trifurcation stay siblings and thus can still be matched. Second, the presence of false branches does not disturb the inheritance relationship either. Consequently it becomes possible to tolerate false branches — a necessity when in-vivo trees shall be matched without the need of a manual pruning step.

Vertices are only added to the association graph if the two corresponding vertices in the trees to be matched are not farther than *d*_{Euclidean max} apart. The value of *d*_{Euclidean max} is set to 40 mm for matching the main branchpoints, and to 15 mm for matching the sub-trees.

Restrictions also apply to the placement of edges in the association graph. Let *v*_{assoca} and *v*_{assocb} be the vertices in the association graph. Vertex *v*_{assoca} represents a match between vertex *v*_{1}* _{a}* in tree 1 and

- The inheritance relationship from
*v*_{1}to_{a}*v*_{1}is identical to the inheritance relationship from_{b}*v*_{2}to_{a}*v*_{2}._{b} - The topological distance between
*v*_{1}to_{a}*v*_{1}and the topological distance between_{b}*v*_{2}to_{a}*v*_{2}differ by at most ±2._{b} - The Euclidean distance between
*v*_{1}and_{a}*v*_{1}and the Euclidean distance between_{b}*v*_{2}and_{a}*v*_{2}differ by at most 20%._{b} - The angle between the two vectors
*v*_{1}−_{a}*v*_{1}and_{b}*v*_{2}−_{a}*v*_{2}is at most 1 radian._{b}

The restrictions described above minimize the size of the association graph and consequently speed up the matching process considerably. The tolerance for topological distances makes it possible to tolerate false branches that were not eliminated by the pruning step.

The maximum un-weighted clique in the association graph is found with the algorithm published by Carraghan and Pardalos [15]. Many published algorithms for finding the maximum clique are based on this method. More efficient algorithms are known for certain special cases, but for this application it performs very well since the individual problem size is kept relatively small. The runtime for the complete matching process amounts to 1 to 3 seconds for two trees containing 200 to 300 branchpoints each (measured on a 1.2 GHz AMD Athlon^{™} single CPU system).

The goal of anatomical labeling is to assign the 32 unique labels to the appropriate segments of a target tree (Figure 2).

Anatomical labels are assigned by matching the target tree against a pre-labeled tree that represents a population average and contains information about the geometrical and topological properties of the human airway tree. This information includes not only the mean values of various measures, but also the typical variability observed across the population.

Because of false branches, an anatomical segment may consist of more than one edge in the graph representation of the airway tree. For that reason labels are assigned to the respective endpoint (branchpoint) of their respective segment. The start- and end-branchpoint of a given segment are known by definition. For example, referring to Figure 2, the segment “RMB” (right main bronchus) starts in the branchpoint labeled “EndTrachea” and ends in the branchpoint labeled “EndRMB”. This statement holds true independently of the number of false branches that may branch off between these two points. Therefore assigning labels to end-of-segment branchpoints makes the labeling independent of false branches.

The population average is built based on a set of airway trees in which each tree individually has been hand-labeled by a human expert. Prior to recording the spatial properties, the trees undergo a rigid registration such that the carina lies in the origin of the coordinate system and the main right bronchus is aligned with the *z*-axis of the coordinate system. This allows for the measurement of the absolute position and orientation of segments. The following properties are recorded in the population average, using the notation shown in Figure 3. Items 1 and 2 represent single-segment measures, 3–6 represent inter-segment relationships.

*Segment length*, mean*μ*and standard deviation_{}*σ*of the length of each named segment._{}*Spatial orientation*, recorded as mean vector ${\overrightarrow{\mu}}_{\text{SO}}={\scriptstyle \frac{{\sum}_{i=0}^{T-1}{\overrightarrow{s}}_{n}}{T}}$ (representing average spatial orientation), and standard deviation of angular deviation ${\sigma}_{\text{SO}}=\sqrt{{\scriptstyle \frac{1}{T-1}}{\sum}_{i=0}^{T-1}{\left({cos}^{-1}{\scriptstyle \frac{{\overrightarrow{s}}_{n}\xb7{\overrightarrow{\mu}}_{\text{SO}}}{\mid {\overrightarrow{s}}_{n}\mid \xb7\mid {\overrightarrow{\mu}}_{\text{SO}}\mid}}\right)}^{2}}$. Computed separately for every named segment*$\stackrel{\u20d7}{s}$*in the_{n}*T*input trees.*Inheritance relationship*, consisting of a label from the set {PARENT, CHILD, SIBLING} assigned to every pair of named segments.*Topological distance*. For every pair of named segments, the topological distance is measured in every tree contributing to the population average and the minimum and maximum values are recorded. 5)*Angle between segments*. For every pair*$\stackrel{\u20d7}{s}$*and_{n}*$\stackrel{\u20d7}{s}$*of anatomically named segments the average angle and its standard deviation are computed with ${\mu}_{\varphi}={\scriptstyle \frac{1}{T}}{\sum}_{i=0}^{T-1}{cos}^{-1}{\scriptstyle \frac{{\overrightarrow{s}}_{m}\xb7{\overrightarrow{s}}_{n}}{\mid {\overrightarrow{s}}_{m}\mid \xb7\mid {\overrightarrow{s}}_{n}\mid}}$ and ${\sigma}_{\varphi}=\sqrt{{\scriptstyle \frac{1}{T-1}}{\sum}_{i=0}^{T-1}{\left({cos}^{-1}{\scriptstyle \frac{{\overrightarrow{s}}_{m}\xb7{\overrightarrow{s}}_{n}}{\mid {\overrightarrow{s}}_{m}\mid \xb7\mid {\overrightarrow{s}}_{n}\mid}}-{\mu}_{\varphi}\right)}^{2}}$ respectively._{m}*Spatial relationship*. For every pair*$\stackrel{\u20d7}{s}$*and_{n}*$\stackrel{\u20d7}{s}$*of anatomically named segments the average spatial relationship is computed with ${\overrightarrow{\mu}}_{\text{SR}}={\scriptstyle \frac{{\sum}_{i=0}^{T-1}{\overrightarrow{s}}_{{m}_{c}}-{\overrightarrow{s}}_{{n}_{c}}}{T}}$ where_{m}*$\stackrel{\u20d7}{s}$*and_{mc}*$\stackrel{\u20d7}{s}$*are the center-points of segment_{nc}*$\stackrel{\u20d7}{s}$*and_{n}*$\stackrel{\u20d7}{s}$*, respectively (Figure 3). The unit vector of_{m}_{SR}is recorded in the population average, as well as the average variation of the spatial relationship, computed as ${\sigma}_{\text{SR}}=\sqrt{{\scriptstyle \frac{1}{T-1}}{\sum}_{i=0}^{T-1}{\left({cos}^{-1}{\scriptstyle \frac{({\overrightarrow{s}}_{{m}_{c}}-{\overrightarrow{s}}_{{n}_{c}})\xb7{\overrightarrow{\mu}}_{\text{SR}}}{\mid {\overrightarrow{s}}_{{m}_{c}}-{\overrightarrow{s}}_{{n}_{c}}\mid \xb7\mid {\overrightarrow{\mu}}_{\text{SR}}\mid}}\right)}^{2}}$

It is not unusual to find relatively long “false” branches in human airway trees. These branches are not really false but represent anatomical segments that are not typical and are likely not represented in the population average. Figure 4a shows such an example. Pruning with a fixed threshold can not remove such branches without removing desired branches as well. Instead, *parallel edges* are introduced into the target tree prior to building the association graph. Referring to the example in Figure 4b, a parallel edge *e _{p}* is added to the tree if vertex

Long false branches. a) “False” branches may be too long for fixed-length thresholding. b) Introducing parallel edges to bridge potential false branches.

Introducing parallel edges allows the matching algorithm to choose from two possibilities — either use the original edges and ignore the parallel edge, or use the parallel edge and ignore the original edges. Two parallel edges can not be used simultaneously in the labeled end result. Again referring to Figure 4b, *e*_{1} and *e _{p}* have a SIBLING relationship. At the same time

Vertices are added to the association graph by pairing segments from the population average with potentially corresponding edges from the target tree. Edges are added to the association graph if the corresponding edges in the target tree have the same inheritance relationship as the corresponding segments in the population average, and if the topological distance is within the limits given by the population average.

Every vertex and every edge in the association graph has a weight *ω*_{vertex} = [0, 1] and *ω*_{edge} = [0, 1], respectively, associated with it.

Every association graph vertex weight *ω*_{vertex} is based on the single-segment measures and is computed by

$${\omega}_{\text{vertex}}=exp\left(-\frac{\ell -{\mu}_{\ell}}{2{\sigma}_{\ell}^{2}}\right)\xb7exp\left(-\frac{{\varphi}_{\text{SO}}}{2{\sigma}_{\text{SO}}^{2}}\right)$$

(1)

with

$${\varphi}_{\text{SO}}={cos}^{-1}\frac{{\overrightarrow{s}}_{n}\xb7{\overrightarrow{\mu}}_{\text{SO}}}{\mid {\overrightarrow{s}}_{n}\mid \xb7\mid {\overrightarrow{\mu}}_{\text{SO}}\mid}$$

(2)

Every association graph edge weight *ω*_{edge} is based on the inter-segment measures and is computed by

$${\omega}_{\text{edge}}=exp\left(-\frac{{({\varphi}_{\phi}-{\mu}_{\varphi})}^{2}}{2{\sigma}_{\varphi}^{2}}\right)\xb7exp\left(-\frac{{\varphi}_{\text{SR}}^{2}}{2{\sigma}_{\text{SR}}^{2}}\right)$$

(3)

with

$${\varphi}_{\phi}={cos}^{-1}\frac{{\overrightarrow{s}}_{n}\xb7{\overrightarrow{s}}_{m}}{\mid {\overrightarrow{s}}_{n}\mid \xb7\mid {\overrightarrow{s}}_{m}\mid}$$

(4)

and

$${\varphi}_{\text{SR}}={cos}^{-1}\frac{{\overrightarrow{s}}_{n}\xb7{\overrightarrow{\mu}}_{\text{SR}}}{\mid {\overrightarrow{s}}_{n}\mid \xb7\mid {\overrightarrow{\mu}}_{\text{SR}}\mid}$$

(5)

Only vertices with *ω*_{vertex} > 0.1 and edges with *ω*_{edge} > 0.1 are added to the association graph. This eliminates label assignments with low probability of being correct and reduces the size of the association graph, which consequently reduces the computing time when searching for the maximum clique.

The maximum clique in the association graph is found with an algorithm based on the one used for finding the maximum clique in the matching problem (described above). A simple extension modifies the algorithm such that it incorporates the weights *ω* that were assigned to the vertices and edges of the association graph. The clique that maximizes the sum Ω = Σ* _{i} ω_{vertexi}* + Σ

The first step consists of pruning the target-tree from short branches. A fixed threshold value of 5 mm is used to make sure that no essential branches are pruned away, yet branches that are likely to be false are removed. This reduces the problem size and shortens the overall computation time. Next, parallel edges are added to the target tree.

Some of the measurements contained in the population average depend on the absolute position and orientation of the target tree. To make use of these measurements, the target tree first has to undergo the same affine transformation that was applied to the trees used for building the population average. For that reason the method initially labels only the trachea, left main bronchus, and right main bronchus – using position and orientation-independent measures only. After these three labels are assigned the tree is registered as described above, and the algorithm proceeds with assigning labels to the remaining segments.

To reduce the required computing time, only a sub-tree is labeled during one labeling step. A sequence of labeling steps is illustrated in Figure 5. Every labeling step starts from a segment that already has its final label assigned to it (marked with an ‘s’ in Figure 5). Terminal segments (marked with a ‘t’ in Figure 5) are used as guides only and do not receive their final label at this point. The segments in between the start segment and the terminal segments receive their final labels.

Stepwise labeling. Reducing computing time by splitting the task into sub-problems. Segments labeled during a step are marked gray. The labels ‘s’ and ‘t’ mark start- and terminal-segments, respectively.

Applying this stepwise labeling results in a significant speedup of the labeling process. A complete tree is labeled in a few seconds, whereas an attempt of labeling an entire tree in a single step can take several hours. At the same time, the accuracy of the assigned labels is preserved.

Branching patterns vary between different subjects. For example trifurcations may appear as real trifurcations in some subjects, but in other subjects they may appear as two bifurcations that follow each other within a short distance. These variations are tolerated well by the algorithm because the population average does not only represent the mean of the population, but it also includes information about its variability. For example the population average lists the topological distance between RB1 and RB2 as being between 1 and 2, which covers the occurrence of a trifurcation as well as the various possible permutations of two bifurcations.

The presented algorithm also tolerates missing branches well. What happens in such a case is that the total weight of the max-weighted clique of the association graph gets smaller. But the one clique with the greatest weight does still represent the sought matching between population average and target tree.

Figure 6 shows typical labeling results for three different subjects.

Scans from a total of 17 subjects, 10 healthy and 7 diseased, were available for validation. Each subject was scanned twice, one scan at functional residual capacity (FRC, 55% lung volume), and one scan at total lung capacity (TLC, 85% lung volume). Scanning was performed at regular dose (120 kVp, 100 mAs), at a voxel size of 0.68 × 0.68 × 0.6mm^{3} and a volume size of 512 × 512 × 500–600 slices.

In each volume the airway-tree was segmented and skeletonized by automated methods [10], and the graph representation of the airway trees was then available to the matching process.

An interactive computer program was developed that allows human experts to perform tree matching by hand. Each pair of FRC/TLC trees was matched independently by three different human experts. Since for each tree pair the FRC and the TLC tree originated from the same subject, it was possible to match branchpoints beyond the anatomically named points. A match between two branchpoints was only taken as a reference if a majority of human observers (i.e., at least two out of three) agreed on it.

The automated matching program was run on all 17 tree pairs. The input trees were taken from the segmentation and skeletonization program “as is”; no pre-processing (e.g., pruning) took place. All 17 tree pairs were matched with the automated program using the same standard parameters. No hand-adjusting of parameters was performed. For every tree pair the result of the automated matching program was validated against the independent reference described in the previous sub-section.

Table I lists the validation results for the matching algorithm. A total of 92.9% of the verifiable matches agreed with the independent standard. The numbers for correct and incorrect matches are based on “verifiable” matches only because we can not make a validity statement about the “computer matches not in reference”, i.e., matches in this group are not verifiable because none of the involved branchpoints appears in the experts’ matches. The relatively high values for “Reference matches not in computer matches” are caused by the type of optimization that was chosen — a high specificity/low sensitivity is favored over a high sensitivity/low specificity. Future work will aim at increasing sensitivity without sacrificing specificity. The “Computer matches not in reference” are mainly peripheral matches that are difficult to match by hand.

ACCURACY ASSESSMENT OF BRANCHPOINT MATCHING. THE 7.1% INCORRECT MATCHES COMPARE WELL TO THE AVERAGE OF 7.5% INTER-OBSERVER DISAGREEMENT.

It is interesting to compare the 7.1% incorrect matches with the intra-observer disagreement. The human experts disagreed with each other on an average of 7.5% of the branchpoint correspondences. For some tree pairs the human expert disagreement was as high as 28.6%. We are aware that the inter-observer disagreement and the error rate of the automated algorithm are not directly comparable. But the inter-observer disagreement gives some indication what the human error might be, which in turn is comparable to the error rate of the automated methods.

Validation of the branchpoint labeling algorithm was performed with in vivo data sets. The accuracy of the algorithm was evaluated by comparing the automated results against an independent standard provided by a human expert. Validation of the anatomical labeling was performed based on the same data sets that were used for the validation of the branchpoint matching algorithm.

An application was written that allowed human experts to perform the tree labeling by hand. Using this tool, all 17 TLC (total lung capacity) trees were hand-labeled by a human expert. These hand-labeled trees were then used as the gold standard for the validation of the automated method.

The leave-one-out (jackknife) method was used for testing the automated labeling. All trees but one were used for building the population average, and the automated algorithm was then run on the one tree left out. This procedure was repeated for all 17 TLC trees.

Table II lists the validation results for the labeling algorithm. 97.1% of the assigned segment labels are correct, while 2.9% of the assigned labels could definitively be identified as wrong. The wrongly labeled segments are almost always among the highest generation segments that receive anatomical labels (e.g., LB8, LB9, etc.). The reason for that is that these segments are the most difficult ones to label because there are no further named segments below them that help guiding the labeling process. The “Computer label not found in the reference set” are difficult to classify since some of them may be correct (but they were not labeled by the human expert), while others may be wrong. The “Reference label not found among computer labels” reflects branches that were labeled by the human expert but not by the computer. There are two possible reasons why this may happen. On one hand our automated labeling algorithm only assigned a label if the probability of it being correct is relatively high. We chose this strategy because we feel that a high specificity/low sensitivity is preferable over a low specificity/high sensitivity. Another reason for segments appearing in the last column of Table II is that the human expert assigned some labels that do not occur in the majority of subjects across the population. For example “Sub-RB6” is a segment that only about 15% of the population have. Our algorithm does not currently label these “rare” segments.

It is notable that the automated labeling identified several human errors. After reviewing the cases of disagreement between the independent standard and the automated result, five cases could be identified where a label was misplaced by the human expert.

Two methods have been presented, one for the matching of corresponding branchpoints and one for the anatomical labeling of human airway trees.

The matching of branchpoints works on in-vivo trees from two different intra-subject scans and is performed without any human interaction. The algorithm proved to be robust against false branches. Validation against a standard built from independent hand-matches done by human experts (17 in-vivo tree pairs used) showed a 92.9% agreement between computer matches and expert matches.

Anatomical labeling of human airway trees is capable of assigning all 32 anatomical segment labels commonly used and tolerates false branches well. The method can by applied to trees from in-vivo CT scans without the need for any manual interaction or pre-processing. Validation showed that a total of 97.1% of the automatically assigned segment labels agreed with the labels assigned by an independent human expert.

Introducing a workable airway nomenclature for the automatic labelling of the extracted human airway tree is a fundamental step in the development of uniform descriptors for complex, 3D-image datasets. This allows for the intra-and inter-study comparison of image-derived airway measurements, important for understanding the human airway in health and disease.

The anatomical labeling is now routinely used in a number of physiologic studies at the University of Iowa Hospitals and Clinics. In one current project the airway geometry (segment lengths, diameters, branching angles, etc.) is studied and compared between different stages of the breathing lung (lung volumes). In this study anatomical labels are used for matching corresponding lung parts. Another example is a study where the airway geometry, and in particular the airway wall-thickness is measured and compared between normal subjects and patients suffering from asthma. Certain airway paths throughout the lung are selected for measurements and comparison. These paths are identified by their anatomical labels. Branchpoint matching is currently used as input in an ongoing research project at the Biomedical Engineering Department of the University of Iowa where the gray level images of a breathing lung are registered against each other [16]. In this project the matched branchpoints serve as landmark points.

The authors would like to thank Martin Urschler, Technical University Graz, Austria, who wrote the applications that helped the human experts create the independent standards used for the validation. We would also like to thank Katherine Carlson-Lamoreux, Jennifer Dempsey, Deepa Gopalakrishnan, Baojun Li, Kang Li, and Soumik Ukil, who provided expert branchpoint matching.

This work was supported in part by the NIH grant HL-064368.

Juerg Tschirren, Department of Electrical and Computer Engineering, The University of Iowa, Iowa City, IA, USA.

Geoffrey McLennan, University of Iowa, Dept. of Radiology, Iowa City, IA, USA.

Kálmán Palágyi, Department of Image Processing and Computer Graphics, University of Szeged, Hungary.

Eric A. Hoffman, University of Iowa, Dept. of Radiology, Iowa City, IA, USA.

Milan Sonka, Department of Electrical and Computer Engineering, The University of Iowa, Iowa City, IA, USA (email: ude.awoiu@aknos-nalim)

1. Boyden EA. Segmental anatomy of the lungs. McGraw-Hill; 1955.

2. Wood SA, Zerhouni EA, Hoford JD, Hoffman EA, Mitzner W. Measurement of three-dimensional lung tree structures by using computed tomography. Journal of Applied Physiology. 1995;79:1687–1697. [PubMed]

3. Pisupati C, Wolff L, Mitzner W, Zerhouni E. Tracking 3-D pulmonary tree structures. Mathematical Methods in Biomedical Image Analysis, 1996; Proceedings of the Workshop; Jun, 1996. pp. 160–169.

4. Pisupati C, Wolff L, Mitzner W, Zerhouni E. Geometric Tree Matching with applications to 3D Lung Structures. ACM Symposium on Computational Geometry; Philadelphia, PA. Jun, 1996.

5. Park Y. PhD dissertation. Osaka University, Japan: Department of Informatics and Mathematical Science; Jan, 2002. Registration of linear structures in 3-D medical images.

6. Pelillo M, Siddiqi K, Zucker SW. Matching hierarchical structures using association graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1999 Nov;21:1105–1120.

7. Mori K, Suenaga Y, Toriwaki J. Automated anatomical labeling of the bronchial branch and its application to the virtual bronchoscopy. Medical Imaging, IEEE Transactions. 2000 Feb;19:103–114. [PubMed]

8. Kitaoka H, Park Y, Tschirren J, Reinhardt JM, Sonka M, McLennan G, Hoffman EA. Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images. MICCAI 2002, Tokyo, Japan. 2002 Sep;:1–11.

9. Tschirren J. PhD dissertation. The University of Iowa; Aug, 2003. Segmentation, anatomical labeling, branchpoint matching, and quantitative analysis of human airway trees in volumetric CT images.

10. Tschirren J, Hoffman EA, McLenna G, Sonka M. Segmentation and Quantitative Analysis of Intrathoracic Airway Trees in Low-Dose CT Scans. Medical Imaging, IEEE Transactionsn. 2004 submitted.

11. Palágyi K, Tschirren J, Sonka M. Quantitative analysis of intrathoracic airway trees: methods and validation. Proc. 18th Int. Conf. Information Processing in Medical Imaging, IPMI 2003; Ambleside, UK, Lecture Notes in Computer Science 2732, Springer. 2003. pp. 222–233. [PubMed]

12. Palágyi K, Hoffman EA, Sonka M. Tubular Tree Structures: Quantitative Analysis from Volumetric Images. Medical Imaging, IEEE Transactions. 2004 submitted.

13. Ballard DH, Brown CM. Computer Vision. Prentice Hall PTR; 1982.

14. Garey MR, Johnson DS. Computers and intractability, a guide to the theory of NP-completeness. W. H. Freeman and Company; 1979.

15. Carraghan R, Pardalos PM. An exact algorithm for the maximum clique problem. Operations Research Letters. 1990 Nov;9:375–382.

16. Pan Y, Kumar D, Hoffman EA, Christensen GE, McLennan G, Song JH, Ross A, Simon BA, Reinhardt JM. Proc SPIE Conf Medical Imaging. San Diego, CA: 2005. Regional lung expansion via 3D image registration. in press.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |