A Segmentation Method of Lung Cavities Using Region Aided Geometric Snakes

Abstract

Segmenting the lungs in medical images is a challenging and important task for many applications. In particular, automatic segmentation of lung cavities from multiple magnetic resonance (MR) images is very useful for oncological applications such as radiotherapy treatment planning. Largely changing lung shapes, low contrast and poorly defined boundaries make the lung cavities hard to be distinguished, even in the absence of prominent neighboring structures. In this paper, we utilized a modified geometric-based snake model which could greatly improve the model’s segmentation efficiency in capturing complex geometries and dealing with difficult initialization and weak edges. This model integrates the gradient flow forces with region constraints provided by fuzzy c-means clustering. The proposed model has been tested on a database of 30 MR images with 80 slices in each image. The obtained results are compared to manual segmentations of the lung provided by an expert radiologist and with those of previous works, showing encouraging results and high robustness of our approach.

Introduction

A Cochrane review of trials conducted over the last 40 years showed that radiotherapy treatment lowers the risk of the breast cancer coming back either in the remaining breast tissue or in lymph nodes that are treated [1]. The aim of radiotherapy treatment is to eradicate a tumor without causing severe damage to healthy tissue. It is through the use of radiotherapy treatment planning systems that specific treatment procedures are developed for individual patients. Such procedures include the specification of beam energy, beam direction; beam shaping and other specifications associated with developing an optimized treatment procedure that maximizes the dose to target volumes and minimizes the probability of normal tissue complications [2].

Standard radiotherapy after surgery for breast cancer is a challenging process because of the complex geometry of the target volume, which includes the breast, the adjacent lymph nodes, and the presence of critical organs such as the lungs [1]. In recent years, great advances have been made in the delivery of breast cancer radiotherapy planning, with intensity modulated radiation therapy (IMRT) being among the most promising new techniques [3, 4]. Advanced radiotherapy treatments with IMRT can deliver dose distributions that are more conformal to the tumor targets and that simultaneously minimize radiation damage to the surrounding normal tissues [5].

An essential part of a successful IMRT system for breast cancer treatment is the accurate segmentation of target volumes and organs at risk such as lungs in all images. There are different challenges as the objects of interest are commonly irregular, structures often overlap one another, and pathological abnormalities (e.g. cancerous tissues) often skew the normal characteristics of the objects of interest. Indeed, manual slice-by-slice segmentation of organs needing to be irradiated (cancerous tumors) or protected (e.g. lungs) during radiotherapy is time-consuming and can take several hours of physician time for a single plan [6]. Furthermore, it is not a trivial task to accurately define structures of interest on the images by visual inspection alone without using dedicated systems to complement visual diagnosis.

Instead, an automated segmentation process allows the planner to take critical anatomical structures explicitly into account through volume rendering, and therefore shape the blocks such that the critical organs are avoided as far as possible, while ensuring adequate coverage of the target structures.

Automatic segmentation of anatomical structures such as lungs in pulmonary magnetic resonance (MR) images is a fundamental but complicated task due to both the tremendous variability of object shapes and the variation in image quality. Acquisition artifacts, low contrast and poorly defined boundaries, especially weak edge effect, in these images make automated lung segmentation very challenging [7]. Further difficulties arise as the size, shape and texture of lungs vary considerably between patients, and among the images of a single patient, which is due to the possible presence of various diseases and the change of the anatomy with vertical position.

Several methods have been proposed for the segmentation of lungs from computed tomography (CT) images. Most algorithms utilize grey level thresholding operation followed by model-based active contour segmentation [8, 9]. In [8] a method for segmenting the lung regions in CT images based on a combination of thresholding and active contours was proposed. The initial active contour points were initialized by a threshold-based global segmentation algorithm. A lung segmentation technique in thoracic CT images was introduced in [9] that used multiple active contours. As with other methods, this approach was initiated by grey level thresholding of the images followed by edge detection. The obtained edge points were organized in strokes and a set of weights was assigned to each stroke. These weights then represented the soft assignment of the stroke to each of the active contour models. In [10] a knowledge-based, automatic method to segment CT images was presented. In this method, anatomic knowledge stored in a semantic network was utilized to guide low-level image processing routines.

Previous works have shown that MR images cannot be segmented as accurately as CT images due to different reasons such as non-uniform nature of the data [11]. Indeed in these images, optimal segmentation may not be achieved by using grey level information alone and a priori knowledge has to be incorporated in the process. Few investigations in the past have segmented the lung cavities from pulmonary MR images. Middleton and Damper [7] addressed MR image lung segmentation by using a combination of supervised neural network classifiers and parametric active contour models to delineate the lungs from multiple MR slices. The method was mainly comprised of two steps. Each individual image pixel was first classified as either a lung boundary or non-boundary point based on a neural network classifier. Then, the obtained edge-point image was processed by a deformable model to obtain the final lung boundaries.

Ray et al. [12] tackled the same problem by using a parametric active contour which could merge multiple contours for segmenting the total lung air. This method utilized an external force field based on partial differential equations with boundary condition which was defined by the initial positions of the evolving contours.

The work presented here is part of a larger effort to develop automated organ segmentation methods that speed up, optimize and improve the accuracy of the breast cancer treatment planning process. In this way, it is crucially important to accurately segment different organs such as lungs to facilitate the quantitative analysis and visualization of the clinically significant features toward the diagnosis, treatment planning and follow-up evaluation. Among several different segmentation methods, those that are deformation-based are especially appealing for our application because they can provide smooth boundary and accurately capture the high-curvature features of the lung regions of different patients. This is due to the active contour models’ ability to segment anatomical structures by exploiting mixed image data constraints together with a priori knowledge about the location, size, and shape of the structures.

On the other hand, the energy function used by classical active contours (snakes) is normally based on the intensity gradients in the image so the snake will lock onto strong edges. Our MR images, however, are often too complex for gradient information alone to be reliable. Intensities often vary non-uniformly throughout a single structure and the boundary between neighboring structures may be noisy. Thus, the appropriate active contour model has to be very carefully chosen and initialized to avoid it getting trapped at non-target boundaries. This is where a less local-based (edge-based) snake i.e. moving toward a global-based (region-based) approach is of great benefit.

Geometric-based active contours [13] have shown several advantages over parametric-based models [14, 7, 12], such as computational simplicity and the ability to change curve topology during deformation. Indeed, geometric-based models avoid the need to reparameterize the curves and are based on the theory of curve evolution in time according to intrinsic geometric measures of the image. Moreover, these models can have much larger capture areas than parametric snakes and their implementation by level-set methods provides accuracy and stability. Nevertheless, geometric-based models still suffer from two shortcomings. First, they allow leakage into neighboring image regions when confronted with weak edges, and second, they may rest at local maximums in noisy images.

To take advantage of geometric-based model capabilities and also handle both these problems, here, we utilize a robust region-aided geometric snake (RAGS) which introduces a new diffused region force into the standard geometric model definition [15]. This extra region force gives the snake a global complementary view of the lung boundary information within the image. However, as the RAGS performance depends on the quality of the region produced, here, we utilized the RAGS in conjunction with Fuzzy C-Means (FCM) segmentation algorithm instead of Comaniciu and Meer [16] technique which was used in [15] to cope with difficulties such as lung weak edges, fuzzy boundaries and noisy regions in our MR images. To examine the effectiveness of the proposed segmentation algorithm and show improvements over the standard RAGS, we demonstrate our results on region maps obtained from both the FCM and Comaniciu and Meer segmentation algorithms.

To obtain a region of interest for lung segmentation, the heart is first located. Then, this located region and the anatomical knowledge are both exploited to automatically initialize active contours. Following a Gaussian image smoothing, the snake’s forces are then computed to evolve the initial snakes toward desired lung boundaries. At the end of snake evolution, the obtained contours are used to initialize both the contiguous previous and next slices. This step is successively repeated by moving forward and backward until all MR slices can be segmented.

In the next sections, details of our method are explained and then we compare our geometric-based method’s efficiency with some of the previous approaches [7, 12] which used parametric-based models.

Materials and methods

Our automated lung segmentation algorithm has been developed using 30 MR images obtained from a 0.35_T open MR imaging system at Bristol Hematology and Oncology Centre. Each image consists of 80 grey-scale slices, each with resolution 256 × 256, taken in the transverse plane using T₁_weighted spin echo [17]. The slices are numbered from slice 1 upwards, i.e. slice 1 is the lowermost slice. Figure 1 shows three slices from one of our images which correspond to the three pulmonary regions, i.e. lower, medium and upper. As the lung is essentially a bag of air in the body, it shows up as a low-intensity region in MR images. The lungs are clearly visible in Fig. 1b and (c) as two large, low-intensity regions.

Fig. 1

Typical MR slices: (a) lower lung region slice, (b) middle lung region slice, and (c) upper lung region slice

Figure 2 demonstrates another MR image where 6 typical alternate medium lung region slices are selected to be shown. As is evident from Figs. 1 and 2, there are different challenges that an automated segmentation algorithm has to deal with. The lung boundaries can be either poorly defined or obscured by surrounding tissues with almost similar grey values. In these cases, there is a possibility to compensate missing or occluded lung boundaries by extracting the relevant information from the adjacent slices. Indeed, as is usually the case in medical imaging applications, the large variability of lung shapes and sizes across MR slices itself and different MR images make the boundaries difficult to be readily distinguished even in the absence of strong edges from neighboring structures. Another challenge is that most lung boundaries have weak edges. Thus, the segmentation algorithm requires having the ability to cope with weak edge leakage problem as well.

Fig. 2

Typical MR slices: (a) lower lung region slice (slice number 5), (b) middle lung region slice (slice number 12), (c) middle lung region slice (slice number 13), (d) middle lung region slice (slice number 14), (e) middle lung region slice (slice number 15), and (f) upper lung region slice (slice number 70)

Therefore, low-level image processing algorithms have to be applied together with higher-level techniques such as deformable models in order to achieve an efficient segmentation technique. In fact, the deformable nature of most internal structures such as lungs suggests that an active contour based segmentation will be an appropriate technique for identification of lung outlines.

To assess the accuracy of our automatic segmentation technique, we require some indication of ground truth in the form of already segmented images. Thus, an experienced radiologist manually segmented the left and right lung borders on every slice of our 30 MR images in the dataset. Figure 3 illustrates two typical slices (slice numbers 40 and 72) from one of our MR images and their corresponding manually segmented results.

Fig. 3

Manual image segmentation of 2 MR slices: (a) a middle lung region slice, (b) manually segmented lung outlines, (c) an upper lung region slice, and (d) manually segmented lung outlines

Image segmentation based on geometric active contours

The active contour is an energy-minimizing spline guided by external constraint forces and influenced by image forces, which pull it toward features such as edges and lines [14]. The energy is composed by terms that control its smoothness and attract it to the object edges, such as lung boundary. This work uses the framework of geometric active contours (geodesic snake) as in [18].

Let C(x,t) be a two dimensional active contour. The Euclidean curve shortening flow is given by:

$$C_t = \kappa \vec N$$

(1)

where t denotes the time, κ is the Euclidean curvature, and $\vec N$ is the inward unit normal of the contour. Now, let I : $\left[ {0,a} \right] \times \left[ {0,b} \right] \to R^ +$ be an input image in which the task of extracting an object contour is considered. The Euclidean length of a curve C is then given by [15]:

$$ L = {\int {{\left| {C\prime {\left( q \right)}} \right|}} }dq = {\int {ds} } $$

(2)

where ds is the Euclidean arc-length. The standard Euclidean Metric ds ² = dx ² + dy ² of the underlying space over which the evolution takes place is modified to a conformal metric $ds_g^2 = g\left( {\left| {\nabla I\left( {C\left( q \right)} \right)} \right|} \right)^2 \left( {dx^2 + dy^2 } \right)$ where the term g(.) represents a decreasing function such that $g{\left( r \right)} \to 0\begin{array}{*{20}c} {{}} & {{as\begin{array}{*{20}c} {{}} & {{r \to \infty }} \\ \end{array} }} \\ \end{array}$. Using this metric, a new length definition in Riemannian space is given by [15]:

$$ L_{R} = {\int\limits_0^1 {g{\left( {{\left| {\nabla I{\left( {C{\left( q \right)}} \right)}} \right|}} \right)}} }{\left| {C\prime {\left( q \right)}} \right|}dq $$

(3)

The steady state of the active contour is then achieved by searching for the minimum length curve in the modified Euclidean metric:

$$ \min {\int\limits_0^1 {g{\left( {{\left| {\nabla I{\left( {C{\left( q \right)}} \right)}} \right|}} \right)}} }{\left| {C\prime {\left( q \right)}} \right|}dq $$

(4)

The steady state is now reached by solving the following equation, showing how each point in the active contour should move in order to decrease the length. The Euler-Lagrange of (4) gives the right-hand side of (5):

$$C_t = g\left( {\left| {\nabla I} \right|} \right)\kappa \vec N - \left( {\nabla g\left( {\left| {\nabla I} \right|} \right).\vec N} \right)\vec N$$

(5)

Equation (5) has two terms. The first is the curvature term multiplied by the weighting function g(.). In application to shape modeling, the weighting factor could be an edge indication function that has larger values in homogeneous regions and very small values on the edges. Since (5) is slow, [19] added a constant inflation term to speed up the convergence. The constant flow is given by $C_t = \vec N$ showing each point on the contour moves in the direction of its normal at a constant speed and on its own can cause a smooth curve to evolve to a singular one. However, integrating this constant term into the geometric snake model lets the curvature flow remain regular as follows:

$$C_t = g\left( {\left| {\nabla I} \right|} \right)(\kappa + c)\vec N - \left( {\nabla g\left( {\left| {\nabla I} \right|} \right).\vec N} \right)\vec N$$

(6)

where c is a real constant making the contour shrink or expand to the object boundaries at a constant speed in the normal direction. The second term of (6) depends on the gradient of the conformal factor g(.) and acts like a doublet, which attracts the active contour closer to the feature of interest since the vectors of -∇g point toward the valleys of g(.), the middle of the boundaries. This -∇g increases the attraction of the active contour toward these boundaries. For an ideal edge, g(.) tends to zero. Thus, it tries to force the curve to stop at the edge, but the convergence quality still highly depends on this stopping term.

Despite their significant advantages, geometric snakes only use local features and suffer from sensitivity to local minimums. Thus, they can be affected by noisy pixels and also fail to recognize weaker edges for lack of a better global view of the image. The constant flow term can speed up convergence and push the snake into concavities easily when gradient values at object boundaries are large. But when the object boundary is indistinct or has gaps, it can also force the snake to pass through the boundary. As it was mentioned above, the second term in Eq. (5) attracts the contour closer to the object boundary and also pulls back the contour if it leaks through, yet the force may just not be strong enough since it still depends on the gradient values. It can not always prevent weak edge leakage.

Region-aided geometric active contours

According to our prior knowledge of the data, to make the geometric snake much more tolerant toward lung weak edges and MR image noise, we have been inspired by [15] to accurately segment our MR images based on the region-aided geometric snake model. This model integrates gradient flow forces with region constraints, composed of image region vector flow forces obtained through the diffusion of the region segmentation map. The extra region force gives the snake a global complementary view of the boundary information within the image which, along with the local gradient flow, helps detect fuzzy lung boundaries and overcome noisy regions. The resulting partial differential equation evolves the initial contour toward final boundaries under the influence of both internal forces and boundary-regional image forces, and is implemented via level sets.

Here, the gradient flow force is acquired as in other active contour formulations, e.g. [20, 21, 22, 23]. The region force can be generated by an image segmentation technique, e.g. [24, 25, 26]. In fact, the segmentation splits the image into several regions and the gradient of this segmentation map gives region constraints in the vicinity of the region boundary map R. The magnitude of this region boundary map is then proportional to the distance between any two adjacent regions. Then, we compute the gradient of the region boundary map ∇R, giving region constraints in the vicinity of the region boundaries.

While the snake evolves in a homogeneous region, it does so mainly base on the gradient flow force. If the snake tries to step from one region into another, it must concur with the region force since it breaks the region criteria, which probably indicates a leakage. The capture area of the pure region force is quite small. A gradient vector diffusion method was proposed in [26] to extend the gradient map further away from the edges for a larger capture field. We use this same concept to diffuse the region boundary gradient map resulting in region forces with a larger capture area along the region boundaries. Thus, we obtain a two dimensional vector field $\left[ {\tilde R\left( z \right) = \left( {u\left( z \right),v\left( z \right)} \right),z = \left( {x,y} \right)} \right]$ by solving the equilibrium state of the following equations:

$$\left\{ \begin{aligned} & p\left( {\left| {\nabla R} \right|} \right)\nabla ^2 u - q\left( {\left| {\nabla R} \right|} \right)\left( {u - \nabla R_u } \right) = 0 \\ & p\left( {\left| {\nabla R} \right|} \right)\nabla ^2 v - q\left( {\left| {\nabla R} \right|} \right)\left( {v - \nabla R_v } \right) = 0 \\ \end{aligned} \right.$$

(7)

where ∇² is the Laplacian operator with dimensions u and v, and p(.) and q(.) are weighting functions that control the amount of diffusion, and ∇R _u are ∇R _v the components of vector field ∇R along the u and v directions. These are selected so that p(.) gets smaller as q(.) becomes larger with the desirable property of little smoothing in the proximity of large gradients and the vector field will be nearly equal to the gradient of region map. The following functions are used for diffusing the region gradient vectors:

$$\left\{ \begin{aligned} & p\left( {\left| {\nabla R} \right|} \right) = e^{ - \left( {\left| {\frac{{\nabla R}}{M}} \right|} \right)} \\ & q\left( {\left| {\nabla R} \right|} \right) = 1 - p\left( {\left| {\nabla R} \right|} \right) \\ \end{aligned} \right.$$

(8)

where M is a constant which acts as a tradeoff between field smoothness and gradient conformity. The RAGS definition is obtained by considering the diffused region force as an extra external force of the snake [15]. In this way, the original internal and external forces of Eq. (6) can be defined as:

$$\left\{ \begin{aligned} & F_{in} = g\left( {\left| {\nabla I} \right|} \right)\kappa \vec N \\ & F_{ex} = g\left( {\left| {\nabla I} \right|} \right)c\vec N - \nabla g\left( {\left| {\nabla I} \right|} \right) \\ \end{aligned} \right.$$

(9)

where g(.) is the stopping function as before. Now, we can add the diffused region force $\tilde R$ obtained in Eq. (7) to the external term as follows:

$$F_{ex} = \alpha g\left( {\left| {\nabla I} \right|} \right)\vec N + \beta \tilde R - \nabla g\left( {\left| {\nabla I} \right|} \right)$$

(10)

where α is a new constant incorporating c and causes behavior that is similar to c in [21]. Constants α and β control a tradeoff between gradient and region forces. As only the forces in the normal direction deform the curve, the evolving curve is represented as follows:

$$C_t = \left[ {\left( {F_{in} + F_{ex} } \right).\vec N} \right]\vec N$$

(11)

Therefore, the final RAGS formulation becomes:

$$C_t = \left[ {g\left( {\left| {\nabla I} \right|} \right)\left( {\kappa + \alpha } \right) - \nabla g\left( {\left| {\nabla I} \right|} \right).\vec N + \beta \tilde R.\vec N} \right]\vec N$$

(12)

Here, we utilize the level set implementation of RAGS. Level sets explain a moving front and are the basis for the numerical algorithm for curve evolution according to functions of curvature [27, 28]. Let C be a level set of a function of: ϕ:$\left[ {0,a} \right] \times \left[ {0,b} \right] \to R,$ i.e. C is embedded into the zero level set with ϕ an implicit, intrinsic, and parameter-free representation of curve C. Given a planar curve that evolves as follows:

$$C_t = f\vec N$$

(13)

where f is computed on the level sets. By embedding the evolution of C in that of ϕ, topological changes of C are handled automatically and accuracy and stability are achieved using the proper numerical algorithm. The internal curvature and external pressure terms of the RAGS formulation in Eq. (12) can be easily transferred to a level set representation:

$$\left\{ \begin{aligned} & \varphi _t = g\left( {\left| {\nabla I} \right|} \right)\kappa \left| {\nabla \varphi } \right| \\ & \varphi _t = g\left( {\left| {\nabla I} \right|} \right)c\left| {\nabla \varphi } \right| \\ \end{aligned} \right.$$

(14)

The external forces in Eq. (12) are static vector fields derived from image data which do not change as the active contour deforms. Static force fields are defined on the spatial positions rather than the active contour itself. Since $\vec N$ is the inward normal, the level set representation of the inward unit normal is given by $N = - \frac{{\nabla \varphi }}{{\left| {\nabla \varphi } \right|}}$. Then we have:

$$f.\vec N = - \frac{1}{{\left| {\nabla \varphi } \right|}}\left( {f.\nabla \varphi } \right)$$

(15)

This leads to the level set representation of RAGS as:

$$\varphi _t = g\left( {\left| {\nabla I} \right|} \right)\left( {\kappa + \alpha } \right)\left| {\nabla \varphi } \right| + \nabla g\left( {\left| {\nabla I} \right|} \right).\nabla \varphi - \beta \tilde R.\nabla \varphi $$

(16)

where g(.) is the stopping function as before. We should point out that, the theory of boundary detection by the geometric or geodesic snake can be applied to any general edge detector function, with a stopping function g tending to zero when reaching edges. Let f be an edge detector. Then, the decreasing function g can be any decreasing function of f such that $g \to 0\begin{array}{*{20}c} {{}} & {{as\begin{array}{*{20}c} {{}} & {{f \to \infty .}} \\ \end{array} }} \\ \end{array}$ In this work, as our images are gray level images, f and g are defined as:

$$f = \left| {\nabla \left( {Gauss^ * I} \right)} \right|\quad and\quad g = \left( {1 + f} \right)^{ - 1} $$

(17)

where Gauss represents a Gaussian smoothing filter.

Fuzzy C-Means image segmentation

The ideal segmentation of an image is usually application-dependent. Unlike hard segmentation methods, which force pixels to belong exclusively to one class, soft segmentations such FCM allow pixels to belong to multiple classes with varying degrees of membership [25, 27]. FCM has been used with some success in the soft or fuzzy segmentation of MR images [28, 29]. It clusters data by computing a measure of membership, called the fuzzy membership at each pixel for a specified number of classes. The fuzzy membership function reflects the degree of similarity between the data value at that location and the prototypical data value or centroid of its class.

FCM is formulated as the minimization of the following objective function with respect to the membership functions u and the centroids v [30]:

$$J_{FCM} = \sum\limits_{j \in \Omega } {\sum\limits_{k = 1}^C {\mu _{jk}^q } } \left\| {y_j - v_k } \right\|^2 $$

(18)

Here, Ω is the set of pixel locations in the image domain, q is a parameter that is constrained to be greater than one, u _jk is the membership value at pixel location j for class k. The observed image intensity at location j is shown by y _j , v _k is the centroid of the class k, and the total number of classes is represented by C. The parameter q is the weighting exponent which controls the fuzziness of the resulting clusters. For q = 1, J _FCM reduces to the classical within-group sum of the squared errors objective function and FCM becomes equivalent to the K-means clustering algorithm [31]. A commonly used value is q = 2.

The FCM objective function in Eq. (18) is minimized when high membership values are assigned to pixels whose intensities are close to the centroid for its particular class and low membership values are assigned when the pixel intensity is far from the centroid.

Template matching-based snake initialization

The deformable nature of most human internal structures such as lungs might suggest that a carefully chosen active contour model, i.e. the RAGS, would be more appropriate for identification of lung boundaries. However, as there are many non-target boundaries in a typical MR slice, a careful initialization is necessary to avoid snakes getting trapped at non-target boundaries. Generally, the initial contours should be defined so that they are close enough to the desired outlines to avoid having snakes trapped in local minima of the energy that do not correspond to the actual boundaries of the lungs.

Here, the snake’s performance is optimal when the initial contour is placed inside the lung region. This is due to the fact that much less distinct features exist in the more homogeneous inner region of the lungs than in the outside region. In fact, the initial contours must be large enough so that they are not too far from the desired boundaries and small enough so that they have more freedom to move inside homogeneous regions toward the desired outlines.

As lung contours are often similar from one slice to the next, we can alleviate the difficult task of separate initialization of each slice by using the final obtained contours in one slice as the initial snakes of the adjacent one. However, prior to the segmentation algorithm, a matching process is employed to choose a middle lung region slice named best matched slice with clear lung regions and the heart. Having found this slice, suitable initial (starting) contours can be adjusted and refined using active contour model to rapidly find the lungs cavities.

Template Matching is a technique used to isolate certain features in an image [32]. This can be implemented as a correlation of the original image and a suitable template. The best match is located based on some criterion of optimality. According to the size of the heart region in our MR images, we generated a 70 × 70 pixel template image by averaging the heart region in 80 middle lung region slices selected from our image dataset. To have a robust method against the changes in image amplitude such as those caused by changing lighting conditions, the normalized correlation coefficient (CC) is utilized:

$$\gamma = \frac{{\sum\limits_{x,y} {\left[ {f\left( {x,y} \right) - \bar f} \right]\left[ {g\left( {x,y} \right) - \bar g} \right]} }}{{\left\{ {\sum\limits_{x,y} {\left[ {f\left( {x,y} \right) - \bar f} \right]^2 \sum\limits_{x,y} {\left[ {g\left( {x,y} \right) - \bar g} \right]} ^2 } } \right\}^{0.5} }}$$

(19)

where f and g represent the original slice and the template respectively, $\bar f$ denotes the slice pixels mean value in the region which is defined by the template location and similarly $\bar t$ is the template pixels mean value. We measured the normalized correlation coefficients for each MR slice to present an indication of the match between the template image and each individual pixel in the slice under consideration.

Figure 4a illustrates the best matched slice of one of our MR images (shown in Figs. 2 and 3) where the point with the highest CC value is also marked. Here, we consider this point’s coordinate as potential location of the heart centre. Fig. 4c shows the obtained CC values on all 80 slices of the processed MR image. As is evident, the best match occurred between the template image and the slice number 26.

Fig. 4

Snake initialization based on template matching: (a) the best matched slice along with the highest CC point marked in white, (b) initial snakes defined by the highest CC point, and (c) CC values for all the slices of a typical MR image

Having found the best matched slice for each MR image, the initial snakes can be defined as arbitrary oval contours within the lung regions using the obtained heart location and our prior anatomical knowledge of the lungs. Fig. 4b shows the initial snakes placed inside the lung cavities for the best matched slice illustrates in Fig. 4a.

Finally, an outline of our proposed algorithm can be summarized in the following four steps:

• 1. The MR image’s best matching slice, i.e. a middle lung region slice with clearly detectable heart and the lungs regions is first located using template matching.

• 2. Initial snakes are then automatically placed inside the matched slice’s lung regions that are to be segmented.

• 3. Following a Gaussian image smoothing, the snake’s forces are computed to evolve the initial snakes toward desired lung boundaries.

• 4. At the end of snakes’ evolution, the obtained contours are used to initialize both the contiguous previous and next slices. This step is successively repeated by moving forward and backward until all MR slices can be segmented.

It is worth nothing that, during first iteration the final obtained contours from segmenting the best matched slice are used to initialize both previous and next MR slices while from second iteration onward, each new slice is initialized solely based on its either previous or next slice’s identified contours.

Results

We have applied the proposed segmentation algorithm to capture lung cavities in each slice of our 30 MR images. As it was mentioned in “Image segmentation based on geometric active contours”, each MR image consists of 80 two-dimensional (2D) grey level slices. Having found the best matched slice for each MR image, the same initial contours were automatically defined within the lungs. The RAGS propagate under the influence of one internal and three external forces, i.e. the internal curvature flow force, the pressure force generated by the constant gradient flow, the gradient of the edge stopping force and the diffused region vector force derived from region constraints. These latter constraints are derived from any region segmentation approaches.

Following a Gaussian smoothing pre-processing step, the map of stopping function g(.) and gradient magnitude map of this stopping function ∇g are obtained. The term ∇g attracts the contours further to the boundary and also presents a backward force when the contours step through the edge.

Now we need to compute the region forces, which are generated from segmented images. The segmentation algorithm provides an extra region force which gives the snake a global complementary view of the lung boundary information within the image. In fact, the segmentation algorithm define a region map to help the snake speed up the convergence while evolving in a homogenous area, or pull back the snake while it attempts to step across lung boundaries. In this work, we exploited FCM segmentation algorithm with fixed q = 2 parameter for all experiments. The reasonable value of this parameter was tuned experimentally and according to our prior knowledge of MR image characteristics. The pixels of the input MR images were divided into four clusters. The first cluster includes pixels in the background and inside lung cavities, whereas the remaining three clusters represent the other existent structures in each image.

Figure 5(a–c) illustrate a typical medium MR slice, its Gaussian smoothed image (σ=1) and the FCM segmentation result, respectively. Having segmented this slice into a set of regions, a region identification technique was followed to assign a unique label to each segmented region. Here, we used an 8-neighborhood connected component labeling region identification technique [31]. The connected component labeling provides the ability to assign a unique label to each segmented region and thus measure various features for each individual region. To avoid potential interference from non-target small minor segmented regions, i.e. the isolated regions which were obtained due to the noise and other artifacts, a cleaning operator was used. This cleaning filter was implemented as an experimentally adjusted connected region size threshold of 1000 pixels which removed all regions with a size under this threshold value. Figure 5d shows the segmented image (Fig. 5c) after this post-processing stage was applied, and the correspondent region map is illustrated in Fig. 5e.

Fig. 5

Region-aided segmentation results for a typical middle lung region slice: (a) original slice, (b) Gaussian-smoothed result, (c) FCM segmentation result, (d) post-processing stage using connected component labeling, (e) the obtained region map, and (f) final extracted lung boundaries

After generating all the external forces, we could build up the initial level set function based on the initial contours and evolve the level set according the underlying forces till the zero level set reach the steady state. Figure 5f displays the final identified lung boundaries using the RAGS snake. Similarly, Figs. 6(a–f) show different intermediate and final results for a typical upper MR slice.

Fig. 6

Region-aided segmentation results for a typical upper lung region slice: (a) original slice, (b) Gaussian-smoothed result, (c) FCM segmentation result, (d) post-processing stage using connected component labeling, (e) the obtained region map, and (f) final extracted lung boundaries

The excellent performance and versatility of our proposed method is shown in Figs. 7 and 8, which display typical examples of the segmentation that can be achieved. In all cases, the algorithm could successfully detect lung boundaries without user interaction and parameter modification with fixed initial contours used for the best matched slice. Most segmentations required approximately 200 iterations for convergence, dependent primarily on the size of the lungs in the image.

Fig. 7

Experimental results of automatic lung segmentation for 8 medium and lower lung region slices, with final identified boundaries shown in white: (a) initial snakes overlaid on the best matched slice (slice no. 23), (b) final boundaries (slice no. 23), (c) final boundaries (slice no. 20), (d) final boundaries (slice no. 17), (e) final boundaries (slice no. 14), (f) final boundaries (slice no. 11), (g) final boundaries (slice no. 8), and (h) final boundaries (slice no. 5), and (i), final boundaries (slice no. 2)

Fig. 8

Experimental results of automatic lung segmentation for 8 medium and upper lung region slices, with final identified boundaries shown in white: (a) initial snakes overlaid on the best matched slice (slice no. 23), (b) final boundaries (slice no. 29), (c) final boundaries (slice no. 35), (d) final boundaries (slice no. 41), (e) final boundaries (slice no. 47), (f) final boundaries (slice no. 53), (g) final boundaries (slice no. 59), and (h) final boundaries (slice no. 65), and (i), final boundaries (slice no. 72)

Figure 7a illustrates the selected best matched slice, initial contours and the extracted lung boundaries superimposed on the original image. Figure 7(b–h) show the segmented slices when moving forward from the best matched slice (Fig. 7a) toward upper lung regions. As was already mentioned, the final converged snakes in each slice are used as the initial snakes of the next slice. Similarly, Fig. 8(b–h) illustrate the final segmented slices when moving backward from the best matched slice (Fig. 8a) toward lower lung regions.

As it can be seen from Figs. 7 and 8, the proposed method achieved a good segmentation in the lower, middle and upper pulmonary regions. However in a few instances, in slices from the middle lung region, where lung superposition or visual merging of the lungs occurred (Fig. 8e), the method failed to distinguish the two separate lungs and a global contour was obtained. This erroneous result did not however interfere with segmentation of the subsequent slices and the desired boundaries were accurately located in the following slices (Fig. 8f). On the other hand, there were a couple of lower lung region slices at the bottom of lungs that could not be segmented as accurate as the other slices (Fig. 7(h, i)). This problem was mainly due to the fact that the lung cavities tend to be poorly represented in these more extreme slices.

Overall, as is evident from Figs 5, 6, 7 and 8, the proposed segmentation method is robust enough to efficiently deal with pronounced cavities and different shapes for each lung. Thus the segmentation results can be rendered together to show the total segmentation of the lungs.

To emphasize the effectiveness of the proposed technique and to perform a quantitative evaluation, the well known Pratt’s Figure of Merit (FOM) [32] was utilized. The FOM is a dimensionless number between zero and one which attempts to balance three types of errors that can produce erroneous edge maps, i.e. missing valid edge points, failure to localize edge points and classification of noise fluctuations as edge points. Here, the edge means the boundary of segmented lung regions. In fact, FOM quantifies the comparison between ideal edges and detected edges of an image, and its maximum attainable value will be one for an ideal segmentation. The FOM is defined as follows:

$$R = \frac{1}{{I_{Max} }}\sum\limits_{i = 1}^{I_{Area} } {\frac{1}{{1 + ad^2 }}} $$

(20)

where I _Max is the maximum of I _Area and I _Ideal . I _Area represents the total number of actual edge pixels, i.e. those edge pixels that were found. I _Ideal denotes the total number of ideal pixels in the image, i.e. the number of edge pixels in the reference image. The parameter a is a scaling constant while d is the distance from an actual edge point to the nearest ideal edge point (in this paper a=0.9). The scaling factor is used to penalize edges that are localized but offset from the true position. The FOM is normalized with the maximum of the actual I _Ideal < I _Area and ideal number of edge pixels in order to ensure a penalty for smeared (i.e. I _Ideal < I _Area ) or fragmented edges (i.e I _Area < I _Ideal ).

The FOM of the proposed segmentation method was measured based on the provided ground truth set (“Image segmentation based on geometric active contours”) and the automated segmentation results of our 30 MR images. Figure 9 shows the FOMs obtained for all MR images. As is evident, the similarity between our proposed lung segmentation method and the manual lung outlines was very high, best on middle and upper slices, and dropping on the beginning lower slices. The mean FOM was obtained on each MR image separately where the maximum and minimum FOM values were acquired equal to 0.950 and 0.787 for MR images 13 and 23, respectively.

Fig. 9

Average FOM values for 30 MR images

Another potential quantitative measure of performance would be to use the rates of the two possible types of classification errors. Taking a positive example to be a lung boundary pixel and a negative example as a non lung boundary pixel, these two measures can be defined as the ratio of false positives/negatives to the total number of negative/positive examples. There was, however, a problem with these measures in this work as there were usually many fewer lung boundary pixels than non lung boundary pixels in each image slice. Thus the sensitivity of these two measures is incommensurate and a small change in the false positive error rate is relatively more important than a comparable change in the false negative error rate.

To cope with this problem, we have used precision and recall [33] as other performance measures to assess the quality of our proposed segmentation method. These measures are defined as:

$${\text{Precision = }}{{{\text{True Positives}}} \mathord{\left/{\vphantom {{{\text{True Positives}}} {{\text{True Positives}}}}} \right.\kern-\nulldelimiterspace} {{\text{True Positives}}}}{\text{ + False Positives}}$$

(21)

$${\text{Recall = }}{{{\text{True Positives}}} \mathord{\left/{\vphantom {{{\text{True Positives}}} {{\text{True Positives}}}}} \right.\kern-\nulldelimiterspace} {{\text{True Positives}}}}{\text{ + False Negatives}}$$

(22)

Recall measures the proportion of the positive examples that are correctly identified, while precision evaluates the proportion of the nominated positive examples that are correct. Thus unlike, the false positive rate, it is not dominated by the large number of non lung boundary pixels. Table 2 shows the accuracy of the segmentation achieved using the proposed method for each of the 30 MR images in terms of mean precision and recall values. The precision and recall values are calculated from the region enclosed by the snake. That is, in Eqs. (21) and (22), a pixel which is inside the contour for both the automated proposed method and the ground truth is counted as a true positive. False positive pixels are inside the lung boundary found by the snake but outside the ground truth boundary. False negative pixels are outside the lung boundary found be the snake but inside the ground truth boundary.

This method of quantifying the results can be regarded as the complement of the FOM measure and seems to be a fair indication of performance as sometimes a snake could give a very good segmentation of the lungs without being located precisely along the boundary indicated by the ground truth segmentation (it could miss by one pixel at all points). Table 1 summarizes the individual measured performance values for each MR image.

Table 1 Comparison of manual and automated lung segmentation in terms of precision and recall measures for each MR image

Discussion

In this paper, a new approach, for fully automatic segmentation of lung regions in pulmonary MR images is proposed. MR image segmentation is an important but inherently difficult problem in medical image processing and usually it can not be solved using conventional techniques. The solution proposed here is to use a modified geometric-based snake for simultaneously segmentation of both lungs.

Our proposed method starts by choosing the MR image’s best matched slice using template matching approach followed by snake initialization. No user intervention is required to initialize the contours since the initialization is fully automatic. Following a Gaussian image pre-processing, the snakes’ forces are computed to evolve the initial snakes toward desired lung boundaries. At the end of snakes’ evolution, the obtained contours are used to initialize the both contiguous previous and next slices. This step is successively repeated by moving forward and backward until all MR slices can be segmented.

To evaluate the effectiveness of our proposed technique and compare the results with those of the standard RAGS and most related previous works, two set of quantitative measures, i.e. precision-recall and FOM values were calculated. We applied the standard RAGS algorithm on region maps obtained from both the under-segmentation and over-segmentation options of the Comaniciu and Meer algorithm [16].

The method proposed by Middleton and Damper [7] was mainly comprised of two steps i.e. a supervised pixel classification using neural networks and a parametric-based active contour model to outline the lung regions. In this way, a set of images was used as training set to build and tune the classification algorithm. To be truly effective, supervised training algorithms require a representative samples covering most of the cases (ideally all) in order to perform well in practice.

Table 2 illustrates an overall perspective of the Middleton and Damper [7] results which were reported in terms of precision and recall criteria for 13 MR images. Each of these MR images was composed of approximately 35 slices. This table also summarizes maximum, minimum and average values of precision and recall criteria against our MR dataset and the corresponding values reported in [7]. It is evident that in terms of precision all three methods represent almost similar results, although our method significantly outperforms both the Middleton and Damper and standard RAGS approaches in terms of recall criterion. It should be noted that in contrast to Middleton and Damper’s work, the standard RAGS and our method were assessed against a larger MR image dataset comprising 30 images with 80 slices in each image and they do not require any training.

Table 2 Comparison of our lung segmentation results with those of Middleton and Damper [7] method and the standard RAGS

To segment the lung cavities, Ray et al. [12] exploited another parametric-based model which could merge multiple contours for segmenting the total lung air. This method utilized an external force field based on partial differential equations with boundary condition which was defined by the initial positions of the evolving contours. This work was validated in terms of FOM values against an image dataset of 10 MR images with 118 slices in each image and the author reported a mean FOM value of 0.691 against their 10 MR images. On the other hand, the standard RAGS and our method could achieve mean FOM values of 0.754 and 0.880 respectively which are highly superior to the reported value in [12].

The lung cavities can be obscured by surrounding tissue of similar gray value, and some neighboring structures may induce strong edges in close proximity to the lung boundaries. Indeed, largely changing lung shapes and the lung’s weak or fuzzy edges make the boundaries hard to be distinguished, even in the absence of prominent neighboring structures. Although, some correct boundary information can be partially extracted from the adjacent slices, but the segmentation algorithm must be selected carefully to prevent the weak-edge leakage problem.

Therefore, in contrast to both previous methods i.e. [7] and [12] which used parametric active contours, our proposed algorithm exploited a geometric based active contour model. Geometric active contours have shown several advantages over parametric active contours, such as computational simplicity and the ability to change curve topology during deformation. On the other hand, although, geometric based deformable models had brought tremendous impacts on shape representation and analysis in medical image analysis, some problems remain including the handling of boundary leakage and the lack of global understanding of boundaries.

Thus, in this paper, we utilized a robust geometric-based active contour which could significantly improve the active contour performance in capturing complex geometries and dealing with difficult initialization, weak edges and broken boundaries. This model integrates the gradient flow forces with region constraints provided by FCM region generation algorithm. The FCM approach was straightforward to implement and had fixed parameters, but most importantly it allowed us to segment the images.

Experimental results show that the proposed model not only is much more robust toward the lung weak edges, but also has better convergence quality. This can be clearly seen from our results, which are superior to those of previous works [7] and [12]. There were, however, a couple of lower lung region slices being at the bottom of lungs that could not be segmented as accurately as could be the other slices. This problem was mainly due to the fact that the lung cavities tend to be poorly represented in these extreme slices. Overall, as is evident from Figs. 5, 6, 7 and 8, the proposed method is robust enough to efficiently deal with pronounced lung cavities and different shapes for each lung.

We consider our proposed method’s results to be highly encouraging. Efforts were made to reduce the amount of a priori knowledge used, so as to keep the method as generic as possible. This makes our method worth serious consideration for further development as an automated tool for image segmentation in medicine. Since, after the segmentation step, several 2D shapes representing the lung regions at different levels (slices) are available, the future work will include the extension of the proposed method to 3D for the analysis of the complete MR data set toward a more efficient treatment planning system.