|Home | About | Journals | Submit | Contact Us | Français|
The segmentation of the human airway tree from volumetric multidetector-row computed tomography images is an important prerequisite for many clinical applications and physiologic studies. We present a new airway segmentation method based on fuzzy connectivity. Small adaptive regions of interest are used that follow the airway branches as they are segmented. This method works on various types of scans (low dose and regular dose, normal subjects and diseased subjects) without the need for the user to manually adjust any parameters. Comparison with a commonly used region-growing segmentation algorithm shows that this method retrieves a significantly higher count of airway branches. In an additional processing step, this method provides accurate cross-sectional airway measurements that are conducted in the original gray-level volume. Validation on a phantom shows that subvoxel accuracy is achieved for all airway sizes and airway orientations. The utility of the reported method is demonstrated in a comparative analysis of normal and cystic fibrosis airway trees.
Information regarding airway structure, including branching geometry, rate of tapering, wall thickness, and lumenal diameter, makes up important parameters in the detection of disease processes as well as in the introduction of interventional devices, such as endobronchial valves and stents, and for the guidance of transbronchial biopsies. Two-dimensional, in-plane analysis of airways has major limitations, primarily because airways do not traverse the lung perpendicular to the scanning plane. Furthermore, two-dimensional data in isolation do not provide information such as the generation number of the observed airway segment or information needed to detect early signs of dilation such as in bronchiectasis. With the introduction of new multidetector-row computed tomography (MDCT) technology, it is now possible to acquire a volumetric image of the lung in approximately 5 s. To take advantage of the three-dimensional nature of these datasets and to allow for low-dose imaging, it has become imperative to develop new and improved airway segmentation algorithms that provide accurate quantitative information regarding the bronchial tree.
Previous work on airway segmentation includes mainly region growing–based methods (1–4), morphology-based methods (5–7), and combinations of the two (8–10). Other proposed methods include rule-based methods (11, 12), energy function minimization (7), and region of interest (ROI) modification–based techniques (13). Schlathölter and coworkers (14) used a front-propagation algorithm for segmenting airway trees. Branchpoints are detected when the front splits up. Diameters are measured during the segmentation and a leak is identified if the diameter suddenly increases.
There are many reasons why airway tree segmentation is difficult to achieve in a robust fashion from clinical-quality or low-dose CT images. Some of the reasons are anatomy related, for example, airway obstructions; others are caused by heart beat–induced movement artifacts and image reconstruction artifacts. The conventional region-growing methods rely on the existing contrast between the air (black on CT) and the airway wall (bright on CT). If this contrast locally decreases, for example, because of an imaging artifact or a thin airway wall, the region-growing approach may allow the growing process to jump from the inside of the airway to the pulmonary parenchyma, which frequently carries similar gray-level properties on CT images. Once the growth starts outside of an airway lumen (the growing “leaks”), there is nothing to stop it and large parts of the lungs are erroneously marked as the airway tree. Consequently, one of the biggest problems when segmenting airway trees by automated methods is leakage into the extralumenal regions.
Another common problem with previously proposed airway segmentation algorithms is their difficulties with segmenting low-dose scans and scans of heavily diseased lungs—for example, lungs of patients with emphysema. In the case of low-dose scans, the segmentation either stops early or leaks. The user then must run the segmentation algorithm several times in an attempt to find an optimal combination of parameters. In the case of diseased lungs, heavy leaking is not unusual.
The quantitative measurement step follows the segmentation step, and its purpose is to accurately find the location of the inner airway wall in order to conduct geometric measurements. These measurements have often been done manually (15, 16). Semiautomated and automated methods (6, 17–22) have been presented. Reinhardt and coworkers (18, 19) showed that the accuracy of the full-width half-maximum approach, which has traditionally been used for airway sizing, depends in a nonlinear way on airway lumen diameter, airway wall thickness, and scanner characteristics. The full-width half-maximum approach is accurate only for large-diameter airways with thick walls. They proposed a model-based system using a two-dimensional Gaussian function to model the point spread function of the scanner. Prêteux and coworkers (6, 20) approximated the inner airway wall with a polynomial, but concluded that their method produces a sharply increased error for small airways. Saba and coworkers (21) used a three-dimensional model of the airway and the point spread function of the scanner and conducted measurements in two dimensions. The results were compared with those of the full-width/half-maximum method in a Plexiglas phantom and showed better subpixel accuracy for the inner border and equivalent results for the outer wall border.
Our new airway segmentation method, reported below, offers fully automated and reliable identification of airway trees from CT volumes. The need for human operators to manually optimize segmentation parameters has been eliminated. The algorithm works without a change on different types of scans—for example, low dose and regular dose—and on diseased subjects and normal subjects, and the run time does not exceed a few minutes per volume. The quantitative airway size measurements step provides accurate airway dimensions (minor and major diameters, and cross-sectional area) for airway segments of all sizes that can be reliably visualized by the current CT technology and all possible spatial orientations (including in-plane, relative to the scanning direction). Again, the measurements are performed fully automatically, with no manual intervention.
The segmentation algorithm presented here is based on fuzzy connectivity as proposed by Udupa and Samarasekera (23) and Herman and Carvalho (24). During the execution of this algorithm, growth of the foreground region and growth of the background region compete against each other. This method has the great advantage that it can overcome lack of image contrast between the airways and the airway walls and the effects of noise. The disadvantage is its relatively high computational complexity. Computing time can be reduced by splitting the segmentation space into a number of smaller subspaces and by keeping the search space as tight as possible around the airway segments.
The desire to keep the segmentation within a small area, together with the need to detect possible leaks at their root, led to the idea of using a relatively small adaptive ROI that follows the airway tree branches as they are segmented. The ROI has a cylindric shape and adapts its geometric dimensions, its orientation, and position to the predicted size, orientation, and position of the airway branch to be segmented. This has two main advantages:
Figure 1 illustrates the concept. Using a cylindrically shaped ROI (vs. the more common cubical ROI used in other three-dimensional image segmentation tasks) has the advantage that the ROI adapts better to the target shape, which is close to cylindric. This means fewer “useless” background voxels need be analyzed and the computing time can be shortened. A similar approach was independently used by Kitasaka and coworkers (13).
Figure 2 (p. 503) compares typical segmentation results obtained by the conventional region-growing method and the proposed method.
The process of quantitative analysis of airway segments uses the results of the airway tree segmentation. Consequently, approximate surfaces of the airway tree segments together with the airway tree centerlines are used to guide the accurate detection of the airway walls. The process is divided into three steps (Figure 3 [p. 503):
The cost function employed in the dynamic programming uses weighted first and second derivatives of the gray-level image (25). The weighting factor ω allows accurate control of the border position with respect to the correct airway wall location in the CT image (Figure 4 [p. 503). The value of the weighting constant is determined in a training step using CT-scanned objects of several known diameters.
Validation of the airway segmentation would ideally be based on a “gold standard” provided by a human expert who would perform hand-tracings of all discernible airway segments for several airway trees. Unfortunately, this approach is not feasible because of the extreme labor intensity of the hand-tracing task.
Alternatively, a validation scheme was developed that is based on anatomic labeling and compares the segmentation result of the newly proposed algorithm with the result of a region growing–based segmentation algorithm that was previously published and that was specifically developed for airway tree segmentation (26). Low-dose CT scans (SOMATOM Sensation 16-slice MDCT scanner [120 kV; 50 mA; voxel size, 0.68 × 0.68 × 0.6 mm3]; Siemens Medical Solutions, Malvern, PA) from 22 different patients were used, and a human expert assigned as many anatomic labels as possible to every segmentation result. Thirty-two unique anatomic labels are commonly used in human airway trees and the same level of labeling was attempted for the reported validation. The 32 labels represent an international standard used for anatomic labeling of airways for bronchoscopic and other purposes (27). For every CT scan, the two segmentation algorithms were compared on the basis of the number of discerned airway segments.
The newly proposed algorithm was run only once on every CT dataset, using the same parameter settings for all datasets. The region-growing algorithm was run 12 times on every dataset, using different combinations of user-adjustable input parameters. The best region-growing result was hand-selected (by visually inspecting all segmentation results and choosing the one result with the highest number of branches and no significant leaks). This best region-growing result was then used for the anatomic labeling.
On average, the newly proposed segmentation method identified 27.0 ± 4.4 anatomically named segments per tree (mean ± SD), whereas the region-growing algorithm returned 21.3 ± 8.7 named segments. The new method significantly outperformed the region-growing method (p = 0.011). Across all tested trees there were 132 anatomically named segments that were segmented by the new method, but missed by the region-growing algorithm. On the other hand, there were only three named segments that were exclusively segmented by the region-growing method. In the most extreme single CT dataset, the new method found 23 extra named segments compared with the region-growing method. In contrast to that, the region-growing algorithm never identified more than one extra named segment per tree in comparison with the new method.
Validation of the quantitative analysis method would ideally be based on in vivo scans. The problem with this approach is that no accurate, reliable, and independent reference measurements are available. Therefore, a physical phantom made of Plexiglas tubes was used for validation of the quantitative analysis method. The phantom contains seven tubes of known diameters ranging from 0.98 to 19.25 mm. Because the lumen of the smallest tube was invisible on the CT scans, the smallest tube was excluded and the analysis was based on the remaining six tubes. The space between the individual tubes was filled up with dried potato flakes, which closely resemble the density of lung parenchyma at functional residual capacity when scanned with a CT scanner. The phantom was scanned at four different angles (0°, 5°, 30°, and 90°), rotated in the coronal plane. Three different scan settings were used on a Siemens SOMATOM Sensation 16-slice MDCT scanner (low dose [120 kV, 50 mA], regular dose [120 kV, 100 mA], and high dose [120 kV, 200 mA]), all at a voxel size of 0.39 × 0.39 × 0.6 mm3.
In the performed phantom validation studies, the average absolute deviation from the nominal diameter never exceeded 0.26 mm. This, in comparison with the voxel size of 0.391 × 0.391 × 0.6 mm3, shows that the method works at subvoxel accuracy. This is possible because the gray image is resampled before the border is detected.
Figure 5 (p. 504) shows the utility of the presented method for comparison of airway diameters in normal and cystic fibrosis (CF) airways. Figure 5 provides a straightened axial image of a path starting in the trachea and passing through the left main bronchus (LMB), and segments LLB6, TriLLB, and LB8, and ending in an unnamed sixth-generation segment. Figure 5a shows a path through a normal airway tree, and Figure 5b shows an anatomically identical path through the airway tree of a patient with CF. The inner and outer wall borders determined by the described method are visualized in all locations along the path except at bifurcations. Figure 5c shows a comparison of normalized airway diameters for the two subjects. To allow direct comparison between the two trees of differently sized subjects, the chart has been normalized in two ways. The airway diameter has been normalized so that the average tracheal diameter for both subjects became identical. Similarly, the lengths between trachea and the end location in the sixth-generation airway were normalized so that individual tree segments match each other. From Figure 5c, the differences in relative airway diameter between the normal subject and the patient with CF are clearly visible, starting already with LLB6 in this case.
Compared with region growing–based airway tree segmentation, the reported segmentation algorithm not only identifies more airway segments (higher mean number of retrieved segments), but it does so more consistently (smaller SD). This difference becomes especially apparent with trees such as the one depicted in Figure 2 (p. 503), where the new method returns a markedly better result. The new segmentation method always returns all segments of the first three generations (0 SD), whereas the region-growing method misses branches of generation numbers as low as two (main bronchi) in some cases. It is also notable that the new algorithm achieves this result without the need for the user to hand-optimize parameters. In contrast, the parameters for the region-growing algorithm were hand-optimized to obtain the best possible result.
The segmentation result is mostly unaffected by the choice of the initial seed point. In some cases, minor leaks into the surrounding lung parenchyma may occur. This is the case if a leak is “solid”—that is, it does not have any holes and consequently it is not recognized as a leak. However, this happens relatively rarely, and if it does then such a leak is normally restricted to a relatively small area. We never observed high-volume leaks such as those often seen in region growing–based segmentation results.
The segmentation method is sensitive to motion artifacts such as cardiogenic bronchial motion, as well as airway obstructions caused, for example, by mucus. If one of these artifacts causes an airway lumen to be completely obstructed, then the segmentation of the affected airway branch will not be continued at this point (the same happens with region growing–based algorithms). It is mostly the airways at the sublobar level that are affected by these artifacts. This limitation needs to be addressed.
The quantitative analysis achieves subvoxel accuracy, on average. Only a few isolated measurements show a deviation of about 1 voxel from the nominal value.
It is interesting to note that no considerable difference in the average accuracy can be observed between measurements on airways that run perpendicular to the scan plane (phantom at ϕ = 0°) and airways that run in-plane (phantom at ϕ = 90°).
A scan of a Plexiglas-and-potato-flakes phantom is, of course, not an ideal substitute for an in vivo scan of a human lung. It would certainly be desirable to do a similar validation on in vivo data. Unfortunately, no precise reference measurements (with an accuracy of 0.5 mm or better) are available for in vivo data. The phantom used here is the best currently available reference.
The demonstrated ability of the presented method to quantitatively assess the airway tree morphology in vivo has been demonstrated in a comparison of airway diameter as a normalized function of distance along the bronchial tree. The presented method allows the design of a broad range of quantitative studies and is able to support large data volume analyses. We expect that the availability of a robust method will facilitate many new biologically and clinically meaningful studies, especially those requiring analysis of large numbers of subjects in multicenter trials and studies requiring robust objective quantification, especially using lower dose imaging methods.
A segmentation algorithm has been developed that works fully in three dimensions. It is able to detect segmentation leaks and correct them as they occur. The developed application is user friendly—there are no parameters that must be tuned at run time. The algorithm was tested on a total of 22 low-dose scans. The new segmentation algorithm proved to be considerably more robust than region growing–based airway segmentation algorithms, because parameters that must be tuned by the user have been completely eliminated. In many cases, the new algorithm outperforms region growing–based segmentation methods. For many of the scans region growing–based methods provide usable results only after several runs of the algorithm and considerable tuning of parameters.
The proposed method for the quantitative analysis of airway tree segments works fully in three dimensions and performs the measurements in the original gray-scale volume for increased accuracy. Information from anatomic labeling is used, which makes it possible to perform measurements on specific anatomic segments named by the user. The algorithm was verified on a series of high-resolution scans taken from a physical phantom. The phantom contains Plexiglas tubes with known diameters ranging from 1.98 to 19.25 mm. The validation showed that the proposed method delivers subvoxel accuracy for all scan directions (including in-plane airways).
Obtaining a complete segmented and anatomically labeled airway tree scanned at total lung capacity takes about 2 min ± 30 s (measured on a 3.2-GHz Pentium 4 Xeon system), depending on the size of the tree. Obtaining cross-sectional measurements along a path similar to that shown in Figure 5 (p. 504) requires an additional 1 min of processing time.
The cystic fibrosis CT scan was provided by Dr. T. Robinson (Stanford University Medical Center).
Supported in part by National Institutes of Health grant HL-064368.
The color figures for this article are on pp. 503–504.
Conflict of Interest Statement: J.T. was a Ph.D. student at the University of Iowa while the work presented in this article was performed. He is now an employee of VIDA Diagnostics. E.A.H. is a shareholder of VIDA Diagnostics, which seeks to commercialize software discussed in this article. G.M. is cofounder of VIDA Diagnostics. M.S. is cofounder of VIDA Diagnostics.