Chest radiographs are the most routinely acquired exams, which makes their use for diagnosis cost effective. In this paper we present a dynamic programming approach for automated heart segmentation on posterior-anterior (PA) chest radiographs. The goal of the proposed algorithm is to provide an accurate and reproducible method for heart segmentation, which can then be used to detect certain cardiac abnormalities. Our method has several advantages over previous methods, and provides superior performance to previously published results.
Heart segmentation in chest radiographs is a
challenging task. One major difficulty in segmenting the
heart is the low contrast found in the mediastinum and
diaphragmatic regions. These areas are difficult to
visualize even by radiologists. Other aspects that make the
problem challenging include: the significant variation in
heart size across patients, the presence of disease in the
lungs, and poor breadth holds by patients (leading to lower
contrast on the heart boundary). Despite the challenges,
development of an automated method for heart
segmentation could provide significant clinical value [
Several methods have been proposed [
Van Ginneken et al [4] discuss several approaches to
heart segmentation: active appearance model (AAM),
active shape model (ASM) and pixel classification. The
individual methods performed comparably well, though
significantly better performance was obtained when a
hybrid voting scheme was used to combine the three
methods. Shape models, such as the ASM, have the
drawback that their fitting routine can get caught in local
optima [
One important use of heart segmentation is the
measurement of the cardiothoracic ratio. The CTR is an
important measurement that can imply cardiomegaly
(abnormally large heart) [
We use an algorithm based on dynamic programming
(DP) to segment the heart. DP, an important algorithm in
Artificial Intelligence [
In the proposed algorithm we formulate the DP sub problem in an innovative way. The cost matrix is generated using image information assigning minimum cost to the pixels having heart edge characteristics. The cost matrix is generated in the polar domain since the heart shape is mostly circular. By using this method we allow the shape to vary in regions where enough information is present, but force the shape to be circular in regions of uncertainty.
In the next sections we describe our algorithm based on dynamic programming in detail, followed by a presentation of extensive experimental results and a conclusion.
We used the 247 chest radiographs from the JSRT
database to test the method. The JSRT database is
available publicly and consists of screen-film images
digitized with a 0.175mm pixel size and 2048×2048 image
size [
We first obtain the ribcage mask and the segmented lung
masks from the chest radiographs. This is done using a
method developed by Riverain Technologies. The lung
masks are then used to detect locations where the air,
heart, and diaphragm intersect as shown in Figure 3. These
locations are computed based on a curvature detection
method as discussed in [
The top row of the bounding box, as shown in Figure 3, is selected as the location where the heart and the left lung first meet. The bounding box column locations, as shown in Figure 4, are the locations along each lung mask that are at a maximum distance from the central column.
This bounding box is used to define a center and a radius around the approximate heart region. The center is selected as the midpoint of the bounding box and the radius is selected as half of the distance between the end column locations.
The border of the heart is roughly circular. For this reason we apply a polar transform defined in equations (1)-(3) to the approximate heart region.
( ) √ (
) ( ) (1) (2) where ( ) is the image in the Cartesian coordinate system and ( ) is the image in the polar coordinate system.
The polar transform is applied to the image as shown in Figure 5(a) using the center and radius as defined in the previous section. To ensure all of the heart is included, the radius is multiplied by a factor α. In this paper we selected a α value of 1.5. The polar domain image as shown in Figure 5(b) is used to compute a cost matrix for the purpose of dynamic programming.
In dynamic programming, the most important part is constructing the cost matrix. Each pixel in the cost matrix is assigned a local cost, where we use low cost values for pixels that have characteristics typical of the heart boundary. The local cost is defined as a linear combination of individual cost images: (4) where is the cost based on the gradient magnitude, is the weight assigned to , is the cost based on a smoothed gray scale image and is the weight assigned to . The gradient is calculated by computing the derivative along each column (derivative in the radial direction). The gray scale cost term is defined by first computing a nominal value for the heart-lung border. This is done for each column within a smoothed image. These nominal values are then used to measure each pixel’s deviation from the expected border value. Each local cost term is scaled to the unit interval prior to combining.
Given the local cost matrix, the next step is to compute the cumulative cost. The cumulative cost accounts for both the local and transitional costs. The transitional term weights the cost of going from one pixel to the next. The transitional cost we use increases with pixel distance, thus enforcing a smoother result. The total cumulative cost matrix is defined as follows: ( ) (
) ( ) ( ) ( ) ( ) (5) (6) where T represents the transition cost. The value “s” is the offset between pixels when going from one column to the next. The value of this offset is not allowed to be larger than a specified value, “k”, depending upon the desired path smoothness. The value of k for our experiments was set to 3 pixels.
Pixels outside the lung mask, or those having cost values above a maximum acceptable threshold, are set to the maximum cost value as shown in Figure 6. This causes a straight line to be the optimum path for these regions (circular arc in Cartesian domain).
We carried out two experiments to validate the proposed method. First, the algorithm output is compared to the manual outlines to evaluate the accuracy of the heart segmentation. In a second experiment, we compared CTR values extracted from the algorithm against those extracted from manual outlines. The specific aim of this experiment was to evaluate if a reliable CTR estimate can be obtained even with a low overlap score.
The overlap score, Ω, between the manually outlined heart boundary and the output of our method is defined in equation (7). where TP is the true positive area, FP is the false positive area, and FN is the false negative area.
Figure 8 illustrates a summary of the overlap scores obtained by our method.
Overlap Score Distribution on 247 images 0.2 0.4 0.6 Overlap Score 0.8 1
The CTR values are computed by detecting the internal diameter (ID) of the thorax and the transverse diameter of the heart (TD = MR+ML, Figure 1).
The ID value was derived from the ribcage mask. The TD values were computed using the heart mask derived from the algorithm output and the manual outlines.
A relative difference between the CTR values was computed using the above TD and ID values. Figure 9 shows a scatterplot comparing the overlap score with the relative CTR measure. From this plot we can deduce that a good CTR estimate can be obtained even with a low overlap score. An example of such a case is shown in (7) (8)
Some typical output segmentations are presented in Figure 12. As can be seen, our proposed method captures the actual heart contour fairly accurately in most of the cases.
An average overlap score of 0.867 ± 0.046 was obtained from the 247 JSRT images. We find that our method produces outputs that are close to the human observer, while comparing favorably to the other methods discussed in the survey paper [4]. The overlap scores in Table 1 are for the three hybrid methods discussed in [4]. These hybrid methods make use of multiple methods making them computationally intensive. In addition, these methods are supervised approaches whose outputs might not extend to more atypical cases. By comparison, our method is far less complex and has the advantage of making very few assumptions about the shape of the heart.
3 65 69 80 78 63 93
We presented an algorithm for segmenting the heart region using dynamic programming. The proposed algorithm provided an accurate and reproducible method for heart segmentation. The presented method makes few assumptions about the heart shape, has a simple implementation, and provides superior performance to previously published results.
Future work will involve the collection of more data, which is needed for further evaluation and the development of strategies for handling outlier cases. Also, additional image features for improving the local cost term will be explored.