Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

There is a growing use of quantitative computed tomography (QCT) to assess the lung both in terms of parenchymal characteristics as well as characteristics of the bronchial tree [1,2,3,4,5]. With the labeling of the extracted airway tree [6, 7] allowing for the comparison of spatially matched airway segments across individuals, it has been demonstrated that new insights into airway phenotypes can emerge. This is evidenced by the recent observation that, on average, the airway walls of smokers with chronic obstructive pulmonary disease (COPD) actually have thinner rather than thicker airways [8]. There are numerous large multi-center studies incorporating lung imaging as a study component including SPIROMICS [9], COPDGene [10], MESA Lung [11], Severe Asthma Research Project (SARP) [2], CANCOLD [12], and more. To our knowledge, there have been no fully automated methods developed for airway tree segmentation, free of the need for user review to assure that the airway tree has been extracted so as to include a standardized set of bronchial segments. When there is a failure of even a fraction of the segmentations, the airway tree masks must be manually reviewed for all subjects which is extremely cumbersome when evaluating many thousands of image data sets. To simplify the review process and the subsequent use of the many resulting metrics, the radiology center of the SARP has standardized on the airway paths passing through 6 segmental bronchial segments (RB1, RB4, RB10, LB1, LB4, LB10) and continuing two generations beyond these segmental bronchi [1]. This has more recently been reduced to 5 segments as LB4 is often subject to cardiogenic oscillation-derived blurring. In this paper, we present a new airway tree segmentation method which has, in a preliminary evaluation, been shown to reliably extract the bronchial segments along these 5 standardized paths up to two generations beyond the segmental level without the requirement of manual intervention.

Several methods for segmentation of airway trees have been reported in the literature. For example, Sonka et al. [13] used a rule-based approach for segmentation of airway trees using the underlying information of its anatomy; others have applied intensity-based classification and fuzzy logic, where voxels undergo a competitive process determining the regions of their belonging [14, 15]. Other image processing techniques such as region growing using intensity-based voxel connectivity [16,17,18,19], mathematical morphology [20, 21], gradient vector flow [22], central-axis analysis [23,24,25,26], energy minimization [27], graph-based approaches [28], etc. have been applied for airway segmentation. Also, there are several hybrid methods [29, 30] combining multiple approaches listed above. Key performance metrics of an airway segmentation algorithm are primarily related to answering the following questions—(1) on an average, how much manual post-correction time is needed to generate acceptable airway segmentation results, (2) how many airway branches at segmental, children, and grandchildren levels are correctly identified, and (3) performance on lower radiation dose CT scans.

Fig. 1.
figure 1

Illustration of challenges with CT-based segmentation of airway trees. Reduced contrast of airway walls (indicated by white arrows) between airway and lung parenchyma due to noise and partial voxel volume. These low contrast airway walls are possible sites of leakages during segmentation. (Contrast settings: level = −450 HU, window = 1200 HU).

Full size image
Fig. 2.
figure 2

CT values of airway walls at proximal and distal locations. Airway wall intensity values were reduced from −332 HU at a proximal location to as low as −829 HU at a distal location. (Contrast settings: level = −450 HU, window = 1200 HU).

Full size image

Major challenges with chest CT airway tree segmentation emerge from the following facts. Although airway lumen and wall voxels are expected to receive the values of −1,000 HU and −450 HU [31], respectively, due to noise and partial voxel volume effects, reduced contrast appears at several locations on the airway wall creating possible sites for leakages during segmentation (see Fig. 1). Generally, a simple thresholding method [32] fails to work for airway segmentation up to the target level of segmental bronchi and two generations beyond [6]. Also, the CT values of an airway wall along a branch decrease (become more negative) in the proximal-to-distal direction (see Fig. 2) adding further challenges to a simple threshold-based approach of airway segmentation. Moreover, limited spatial resolution and image reconstruction artifacts, especially using sharp kernels, often cause thin airway walls to appear perforated and discontinuous resulting in leakages or early termination of airway lumen growth [15].

In this paper, we present a novel iterative algorithm for airway segmentation using multi-scale leakage detection and volume freezing techniques. The method is fully automated requiring no manual inputs or post-editing steps. It uses simple intensity-based connectivity and iteratively grows an airway tree starting with an initial seed inside the trachea and a conservative threshold value. During an iteration it executes the following sequential steps—apply region growing and generate a leakage-corrected segmentation; freeze the segmented volume; and shift the threshold toward a more generous value for the next iteration. This iterative strategy of airway tree growing continues until a convergence occurs. Several leakage detection methods have been applied for CT-based airway segmentation [6, 33]. Tschirren et al. [6] used topological features [34] for leakage detection; specifically, they used the criterion that a leaked volume includes complex topological features, e.g., tunnels. Others have used geometric rule-based approaches for leakage detection for airway tree segmentation [33]. In this paper, we present a new approach of leakage detection using scale analysis along an airway branch and a measure of distance metric based tortuosity [35] to detect spongy leakages. Moreover, the iterative airway segmentation algorithm introduces a unique notion of volume freezing and active seed selection strategy to progressively shift the segmentation strategy from a conservative to a generous thresholding scheme. The algorithm requires no threshold-related parameter. During an iteration, the CT intensity threshold used for region growing is automatically computed that barely causes a leakage in the airway segmentation.

2 Methods and Algorithms

The basic principle of the overall method is described in Sect. 2.1. The major steps in the algorithm, namely, crude segmentation, leakage detection, setup for next iteration and termination criterion are discussed in Sects. 2.2 to 2.4, respectively.

2.1 Basic Principle

The airway segmentation algorithm presented in this paper uses simple intensity-based connectivity together with new methods of leakage detection and volume freezing to iteratively grow an airway tree in a chest CT image starting with an initial seed inside the trachea. The method is fully automated requiring no manual post correction steps. A block diagram of major steps of the algorithm is presented in Fig. 3. Also, schematic illustrations of results after different intermediate steps are shown in Fig. 4.

Fig. 3.
figure 3

A block-diagram of major steps of the iterative algorithm of airway segmentation from human chest CT scans presented in this paper.

Full size image
Fig. 4.
figure 4

Schematic description of intermediate results of the new airway segmentation algorithm. (a) Initial segmentation using intensity-based region growing. (b) Centerline Extraction (Green) of (a) and leakage detection and correction using branch pruning. (c) Frozen airway segmentation volume after leakage-correction. In subsequent iterations, connectivity paths are prohibited to enter inside the frozen region. (d) New active seeds (yellow dots) at every new branch not pruned for leakage-correction. (e) The segmentation result after the next iteration. (Color figure online)

Full size image

The initial seed selection inside the trachea is automatically performed using the algorithm by Mori et al. [16]. The method applies compactness and size analysis of connected air-space in the upper quartile of axial slices in an acquired chest CT scan to locate the trachea. Finally, the seed is located at the centroid of the trachea. After locating the seed point, the method applies a simple threshold-based connectivity analysis to compute the initial segmentation. The threshold value is automatically selected as the lowest CT intensity triggering an airway segmentation leakage. The results of initial segmentation are illustrated in Fig. 4(a), which includes apparent leakages together with several valid airway branches.

The next and crucial step is to locate and correct for leakages in the initial rough segmentation. This step is based on analysis of scale and a geodesic distance-based measure of tortuosity along centerline paths of the initial airway tree segmentation. The centerline of the segmented region is computed using a centered minimum-cost path approach recently developed by Jin et al. [36]. In Fig. 4(b), the centerline is shown using green lines. A scale analysis [37] is performed along the centerline to detect a leakage. Normally the scale, i.e., local diameter of an airway branch follows a quasi-non-increasing pattern along its centerline path in the proximal-to-distal direction. Thus, a leakage in an airway segmentation can be characterized as a rapid inflation in scale values along a centerline path of the segmented region. Although, this scale analysis method successfully detects solid leakages, it often fails to locate a spongy leakage because the scale is small everywhere inside a spongy region. To detect a spongy leakage, we use distance metric tortuosity, defined as the ratio between its geodesic length [38] and the Euclidean distance between its end points. Normally, the Euclidean distance between the end points of the centerline of an airway branch is similar in value to its geodesic length. However, inside a spongy leakage region, a centerline path grows in an uncontrolled manner. Therefore, the geodesic length of a centerline segment inside a spongy region increases rapidly as compared to the Euclidean distance between its end points. This simple strategy successfully detects all complex and spongy leaks in airway segmentation. The results of leakage detection are schematically shown in Fig. 4(b).

After leakage detection, the leakage-correction step works as follows. First, each centerline branch associated with a leakage is pruned, and the leakage-corrected centerline representation of the airway tree is computed. Subsequently, the leakage-corrected airway volume is obtained by dilating individual centerline branches with local scales (Fig. 4(c)). This segmentation volume after the current iteration is considered as a frozen region, and no connectivity paths in subsequent iterations are allowed to enter into it. This step is crucial for developing an iterative-threshold-shift strategy starting with a conservative threshold and progressing toward more generous values. The end point of an airway centerline branch that is not associated with a leak is used as an active seed for further airway growth in following iterations (Fig. 4(d)). Here, it is necessary to ensure that an active seed at the end of a valid branch is not buried inside the frozen volume, which would arrest any further airway segmentation growth. An efficient solution using distance analysis in the dilation process is developed analytically guaranteeing that an active seed is never buried inside the frozen volume. After computing the frozen airway segmentation volume and active seeds, the process enters in to the next iteration. This iterative process continues until convergence, i.e., no new active seed can be detected after an iteration. Individual steps of our airway segmentation algorithm are presented in following sections.

2.2 Initial Rough Segmentation

The algorithm presented here uses simple intensity-based region growing to compute an initial rough segmentation of the airway tree volume. Such an initial segmentation is only a rough estimation, which may include one or more leakages. Two major requisites in this step are—(1) identification of seed points and (2) determination of the intensity threshold value. As discussed in the previous section, only one seed is used in the first iteration, which is automatically located inside the trachea using the algorithm by Mori et al. [16]. In a subsequent iteration, active seed(s) located during the previous iteration are used; the method of locating active seeds is described in Sect. 2.4.

During an iteration, airway segmentation volume is independently grown from each seed point. Let s denote a seed point and let \(t_{s}\) denote the intensity value of the seed point. The threshold value for airway region growing from s is automatically selected as the lowest intensity value triggering a segmentation leakage. For efficient computation of the optimum threshold, a binary search process between \(t_{s}\) and \(t_{s}\) + \(\varDelta _{max}\) is performed. For all experiments presented in this paper, a value of 200 HU is used as \(\varDelta _{max}\). It should be noted that the final threshold value is independent of the choice of \(\varDelta _{max}\).

It was noted that, often, the intensity-based region growing algorithm leaves small tunnels and cavities inside the segmented region. These cavities and tunnels are filled using a mathematical morphological closing operation with a structure element of \(5\times 5\times 5\). This step is imperative to ensure that an initial segmented volume does not contain small holes which would add significant errors in centerline computation, scale analysis, and tortuosity estimation. After filling small tunnels and cavities, the initial rough segmentation is passed to the next module for leakage detection.

2.3 Leakage Detection

The leakage detection method presented in this paper is based on analysis of scale and distance metric tortuosity along airway centerline branches. As described in the previous section, during an iteration, initial rough segmentation of an airway subtree volume is computed from a seed point; let s denote the seed point and V be the initial subtree volume computed from s. First, a centerline tree is computed for V with s as the root using a robust and efficient centerline detection algorithm recently developed by Jin et al. [36]. The centerline detection method uses fuzzy distance transform (FDT) [39] and collision-impact [40] based centered minimum cost paths to locate individual centerline branches. It generates a partially ordered representation of centerline branches. Let \(\langle \pi _{1}, \, \pi _{2}, \, \dots , \, \pi _{n} \rangle \) be the breadth-first traversal of the partially ordered centerline tree, where \(\pi _{i}\) is a centerline branch, and \(\bigcup _{i=1}^{N} \, \pi _{i}\) represents the entire centerline tree. Individual centerline branches are examined for leakages in the order of their breadth-first traversal. If a leakage is detected on a centerline branch \(\pi _{i}\), the exact leakage point p on the branch is located and it is pruned up to that point. Moreover, the centerline branches descendant to point p are removed from the center tree. Centerline branches are examined for two types of leakages—(1) solid leakages and (2) spongy leakages. The methods for detecting these two specific types of leakages are described in the following.

Fig. 5.
figure 5

Detection of a solid leakage using scale analysis along an airway centerline path. (a) Initial rough segmentation of an airway tree with a solid leakage. The centerline path for current checking of leakages is shown in red. (b) Computed scale profile along the centerline path. (c) Leakage detection on the median filtered scale profile. See text for detail. (d) Leakage-corrected airway tree. (Color figure online)

Full size image

Solid leakages are characterized by the rapid scale inflation along an airway centerline branch. In general, local scales along an airway tree branch are quasi-non-increasing in the proximal-to-distal direction. Thus, a solid leakage can be detected by locating sudden increase in scale values along an airway centerline branch. This process is illustrated in Fig. 5. The scale at a centerline voxel on a skeletal branch is computed using a star-line approach which determines the length of the shortest object intercept through the centerline voxel [41]. Computed scale profile along a centerline branch of Fig. 5(a) is shown in Fig. 5(b). This computed scale profile is passed through a median filtering (window size = 5) to smooth small noisy dents and protrusions; the scale profile after smoothing is shown in Fig. 5(c). The leakage detection algorithm is applied on the smoothened scale profile, and it works as follows. Let \(p_{c}\) be a voxel on a centerline branch \(p_{0}, \, p_{1}, \, \dots , \, p_{c-1}, \, p_{c}, \, p_{c+1}, \, \dots \). The ratio between the scale at \(p_{c}\) and that at each of its predecessors \(p_{i} \, \in \, p_{0}, \, p_{1}, \, \dots , \, p_{c-1}\) is checked in the proximal-to-distal direction. A leakage on the branch is confirmed on the target branch at or prior to \(p_{c}\), if a voxel \(p_{l}\) (\(l<c\)) is found whose scale ratio with \(p_{c}\) exceeds a predefined threshold value of 2. Finally, the exact location of leakage is detected by finding the minimum scale voxel \(p_{min}\) on the centerline branch between \(p_{c}\) to \(p_{l}\) (see Fig. 5(c)), and the branch is pruned up to \(p_{min}\). Final results after leakage detection and correction are shown in Fig. 5(d).

After a centerline path is checked for solid leakages, it is further checked for spongy leakages. Such leakage regions contain tunnels and cavities which are not completely filled by the morphological closing operation on initial rough segmentation discussed in Sect. 2.2. Inside these regions, the centerline path propagates in an aimless and uncontrolled manner and the scale-analysis of solid leakage detection fails to detect such spongy leakages due to holes. To detect such leakages, we use distance metric toruosity, defined as the ratio between its geodesic length and the Euclidean distance between its end points. Normally, the Euclidean distance between the end points of the centerline of an airway branch is similar in value to its geodesic length. Due to meandering nature of centerline path in a spongy leakage, the geodesic length of a centerline segment increases rapidly as compared to the Euclidean distance between its end points. By applying a predefined threshold of 2 to the tortuosity of a centerline path, it can be discerned if it is part of a spongy region and pruned. This process is schematically described in Fig. 6.

Fig. 6.
figure 6

Detection of a spongy leakage using tortuosity of an airway centerline branch. (a) The tortuosity of each centerline path (between black points) is checked in a breadth-first manner. A centerline branch with a high tortuosity is located (geodesic length: red, euclidean distance: blue). (b) The centerline paths and their descendants are removed during leakage correction. (Color figure online)

Full size image

2.4 Setup for Next Iteration

During each iteration of the new airway segmentation algorithm, it augments the airway tree, and adds active seeds at the end of each newly added airway branch without a leakage. The leakage detection and correction step, described in the previous section, produces a centerline representation of the newly added leakage-free region of the airway tree. The purpose of the current step is to use the verified centerline to—(1) dilate each centerline to fill the augmented airway tree volume and (2) freeze the newly augmented airway tree volume while preserving the active seed voxel at the end of each augmented centerline branch without a leakage. The purpose of volume freezing is to avoid any new leakage while segmenting forward tree branches at a more generous threshold. Preservation of active seed is essential to ensure new growth for forward airway tree volume.

Using the scale information determined as part of the thickness analysis in the leakage detection step, the volume representation of the airway tree can be reconstructed by dilating along the verified centerline using local scale. The reconstructed airway segmentation volume after the current iteration is dilated by a \(3\times 3\times 3\) structure element, marked as frozen, and no connectivity paths in subsequent iterations are allowed to enter inside the frozen volume. This step is crucial to design a strategy of iteratively shifting the threshold intensity value starting with a conservative one and then progressing towards more generous threshold values. The dilation step is needed to stop connectivity paths from entering into the narrow region (mostly including partial-volume voxels) between the segmented airway volume and the surrounding airway wall.

The end point of an airway centerline branch without a leakage is used as an active seed for further airway tree growth in the next iteration. Here, it is necessary to ensure that active seeds at the end of valid branches are not buried during the dilation process which would disable any further airway segmentation growth in subsequent iterations. Here, an efficient solution using distance analysis is presented that analytically guarantees that an active seed is never buried during the dilation process. Essentially, the method adds a simple constraint on the dilation process during airway tree volume reconstruction from corrected the centerline tree.

$$\begin{aligned} V_{airway}= \{p | \exists q \in S_{centerline} \, s.t. \, D(p,q)< scale(q) \, and \, D(p,q) < D(p,p_{end})\}, \end{aligned}$$
(1)

where p is any voxel; \(S_{centerline}\) is the airway centerline branch being reconstructed; \(scale(\cdot )\) is the scale function at centerline voxels; and \(p_{end}\) is the end voxel of \(S_{centerline}\). After reconstructing segmented airway volume, computing and marking the frozen volume, and identifying the active seeds, the process enters in to the next iteration. Finally, the process terminates when no new active seed is detected in an iteration.

3 Experimental and Results

The experiments were aimed to examine the branch-level accuracy of the new airway segmentation method at segmental, sub-segmental, and one level beyond. The method was applied on chest CT scans of fifteen normal non-smoking subjects (previously acquired under IRB approval; age: 21–48 Yrs, mean: 28.5 Yrs; 7 female) at total lung capacity (TLC: 90% vital capacity) using a volume-controlled breath-hold maneuver. CT scans were acquired on a Siemens Definition Flash 128 (at 120 kV with effective mAs of 200), with images reconstructed at 0.5 mm slice thickness using a standard B35 kernel. Airway segmentation results on a CT image using the new method after different iterations are shown in Fig. 7.

Fig. 7.
figure 7

Results of airway tree segmentation using the new iterative multi-scale leakage detection algorithm after the first (a), second (b), third (c), and the final (d) iterations.

Full size image
Fig. 8.
figure 8

(a) An airway tree representation including segmental (red), sub-segmental (green), and one level beyond (pink). (b) The five anatomic airway paths used in our experiments. (Color figure online)

Full size image

For quantitative experiment, we examined the branch level accuracy of the new segmentation method along five standardized airway paths passing through segmental bronchial segments (RB1, RB4, RB10, LB1, LB10) and continuing two generations beyond these segmental bronchi [1]. An airway tree up to segmental level and two-generations beyond is shown in Fig. 8(a). Branches at segmental level and two-generations beyond along the five anatomic airway paths, used in our experiments, are shown in Fig. 8(b).

To examine the branch-level accuracy of the new method, its segmentation results were compared with the matching airway segmentation results obtained by an expert user’s manual editing (both removal of leakage volumes and addition of missing branches) on the airway segmentation results computed using the algorithm [6] provided within the Apollo pulmonary workstation software (VIDA Diagnostics, Coralville, IA). During comparative examination, a blinded expert user compared every branch at the segmental level and two-generations beyond along each of the five anatomic paths on 3-D visual representations of two airway segmentation results—one using the new method and the other being the manually edited one. No leakage was observed in the automatic segmentation results using the new method on any of the fifteen data sets used in this experiment. Numbers of branches observed at segmental, subsegmental, and one-generation beyond levels were 5 ± 0 (mean ± std.), 10 ± 0, and 15.6 ± 1.5776, respectively compared to the reference method which were 5 ± 0, 10 ± 0, and 15.4 ± 1.3499. The new automatic method successfully detected all branches at the segmental level and two-generations beyond, which were detected in the manually edited results. Moreover, in one data set, the new method detected an additional valid branch at the second generation beyond the segmental level, which was not detected in the manually edited results.

4 Conclusions

An iterative airway segmentation algorithm using new methods of multi-scale leakage detection and volume freezing has been presented, which is suitable for airway analysis in CT-based large cross-sectional and longitudinal studies. The method is fully automated requiring no intensity threshold parameter, manual interaction or post editing enhancing its suitability across different CT scanners and imaging protocols. It was observed in a pilot study that the new method matches the performance of manually edited airway segmentation or excels in terms of branch-level accuracy on chest CT data of fifteen normal non-smoking subjects at total lung capacity at the segmental level and two generations beyond when focusing on a standardized set of paths within the airway tree. Additionally, no leakage was observed in the segmentation results by the new algorithm. Accuracy and reproducibility of the method is currently being examined on larger data sets from two on-going multi-center NIH studies.