Research article

Automatic liver segmentation on Computed Tomography using random walkers for treatment planning

Mehrdad Moghbel¹[*], Syamsiah Mashohor¹, Rozi Mahmud², M. Iqbal Bin Saripan¹

¹Department of Computer & Communication Systems, Faculty of Engineering, University Putra Malaysia, 43400 Serdang, Selangor, Malaysia

²Cancer Resource & Education Center, University Putra Malaysia, 43400 Serdang, Selangor, Malaysia

EXCLI J 2016;15:Doc500

Abstract

Segmentation of the liver from Computed Tomography (CT) volumes plays an important role during the choice of treatment strategies for liver diseases. Despite lots of attention, liver segmentation remains a challenging task due to the lack of visible edges on most boundaries of the liver coupled with high variability of both intensity patterns and anatomical appearances with all these difficulties becoming more prominent in pathological livers. To achieve a more accurate segmentation, a random walker based framework is proposed that can segment contrast-enhanced livers CT images with great accuracy and speed. Based on the location of the right lung lobe, the liver dome is automatically detected thus eliminating the need for manual initialization. The computational requirements are further minimized utilizing rib-caged area segmentation, the liver is then extracted by utilizing random walker method. The proposed method was able to achieve one of the highest accuracies reported in the literature against a mixed healthy and pathological liver dataset compared to other segmentation methods with an overlap error of 4.47 % and dice similarity coefficient of 0.94 while it showed exceptional accuracy on segmenting the pathological livers with an overlap error of 5.95 % and dice similarity coefficient of 0.91.

Keywords: image segmentation, random walker, CT imaging, liver segmentation

Introduction

Liver segmentation is a prerequisite for many clinical and research applications, segmentation of the liver from Computed Tomography (CT) volumes plays an important role in the choice of treatment strategies for liver diseases (Chen et al., 2011[10]). Liver segmentation is difficult as the liver shape is variable and displays low attenuation compared to the neighboring organs, making segmentation of the liver a complex problem. Being a soft organ, liver shape is highly dependent on adjacent organs within the abdomen. Moreover, many pathologies can have a strong effect on the appearance and the shape of the liver while most of the time clearly defined edges are not visible on many sides of the liver. In particular, the intensity difference between the liver and the diaphragm or the spleen or the stomach are very small. Although there are formulas that estimate the liver volume by utilizing the age, weight and the height of the patient, these formulas are highly inaccurate in the case of pathological livers. Joyeux et al. (2003[24]) showed that the correlations between the calculated liver volume by these formulas and the volumes of the liver lobes or anatomical segments in pathological livers were very low.

Despite lots of attention, fully automatic liver segmentation from a CT volume remains a challenging task (Anter et al., 2013[3]), mainly because of the variability of the liver shape and the intensity patterns inside and in the neighborhood of the liver. On the other hand, working inside a liver envelope yields better results in case of segmenting and classifying the lesions inside the liver, previous works have indeed shown that the segmentation of liver lesions was more accurate when done inside liver only, in particular for automatic methods (Taieb et al., 2008[50]; Schmidt et al., 2008[42]; Qi et al., 2008[39]; Ben-Dan and Shenhav, 2008[7]; Shimizu et al., 2008[44]; Smeets et al., 2008[47]; Kubota, 2008[26]; Wong et al., 2008[56]; Moltz et al., 2008[35]; Stawiaski et al., 2008[49]; Zhou et al., 2008[58]).

To address these concerns, a challenge was presented to different researchers by The Medical Image Computing and Computer Assisted Intervention Society (MICCAI) to segment liver on clinical bases (Heimann et al., 2009[19]). From this challenge, it can be concluded that three main approaches have been proposed and considered for segmentation of the liver envelope namely region growing strategies, probabilistic atlases and statistical shape models.

Region growing strategies are data-driven approaches that iteratively construct a region of interest (ROI) defined at pixel level beginning with an initial set of seeds. Such approaches iteratively cluster neighboring voxels by deciding whether these voxels are to be added to the ROI at any given step. Because of this definition, region growing strategies do not rely on a specific prior model but adapt to each image depending on the seeds given by the user. Despite their simple concept, region growing approaches can still provide satisfactory results compared to more evolved approaches, the method proposed by Rusko et al. (2007[40]) indeed offered one of the best results during the MICCAI segmentation challenge.

Probabilistic atlases utilize both the prior shape and the spatial location information to achieve a refined segmentation. Using probabilistic atlases (PA), Park et al. (2003[38]) segmented the liver by optimizing a Markov random field (MRF) formula dependent on intensity distributions computed through the registration of a PA by thin plates wrapping. Zhou et al. (2008[58]) proposed a segmentation of the liver using a threshold of the probabilities of segmentation being the liver, where this probability is defined at voxel level through PA and an intensity model. Shimizu et al. (2007[45]) proposed a segmentation technique for 12 abdominal organs inside the abdominal cavity, this technique begins with a rough segmentation obtained through PA and priors on intensity distributions inside each organ, utilizing a level-set algorithm for enhancing the final segmentation. Linguraru et al. (2009[32]) proposed a segmentation of pathologic livers and spleens on contrast-enhanced images, an initial segmentation is obtained through series of rigid, affine and nonlinear registrations of one PA, the segmentation is then refined using geodesic active contours and an estimation of the distribution parameters inside the liver.

Statistical Shape Models (SSM) define a mesh for the liver envelope along with possible deformations of the nodes describing the liver boundary (Heimann et al., 2007[17]). However, the high variability of liver shapes is highly challenging because of the difficulties in defining an SSM that captures the large variations of the liver shapes. Consequently, later authors introduced an additional step in order to improve the limited transformations of SSM. However, the contribution of SSM remains significant as a recent review (Tomoshige et al., 2014[53]) showed that an SSM with a subsequent free deformation step offered one of the best results for automatic liver segmentation. Lamecker et al. (2004[27]) constructed an SSM of the liver that was used for segmentation of livers with lesions using models of gray-level profiles along surface normals to fit the SSM on new images.

Kainmüller et al. (2007[25]) proposed free forms to define the SSM, this approach proved to be one of the best during the MICCAI segmentation challenge. Heimann et al. (2006[20]) introduced an SSM to segment the liver without major pathologies while mainly following the approach proposed by Lamecker et al. (2004[27]), adding a multi-resolution algorithm and active shape models. Heimann et al. (2007[17][18][21]) later improved his approach with an automatic initialization of the shape model and by replacing the active shape models by a more complex technique.

Okada et al. (2008[37]) introduced a segmentation approach combining PA and SSM to segment the liver. An initial segmentation is done using PA and then the segmentation is refined with SSM. Ling et al. (2008[31]) proposed a segmentation using a hierarchical shape model, where liver boundaries are detected using learning based approaches.

In this paper, a segmentation method based on fast random walkers (Andrews et al., 2010[2]) is proposed for segmenting contrast-enhanced CT images in a clinical prospect with potential applications for diagnosis and as a first step for the segmentation of the liver lesions (Moghbel et al., 2016[34]) as the contrast-enhanced CT images remain the main medium for diagnosing liver pathologies.

Materials and Methods

Figure 1(Fig. 1) represents the flowchart of the proposed segmentation algorithm. The detailed workflow of the proposed segmentation framework is discussed in the following sections.

Background removal and filtering

As CT images contain parts of the imaging table along the patient's body, it is required to remove these unwanted portions of the image. To do so, body boundaries are detected by utilizing a Canny edge detector (Russ, 2011[41]). The body is then detected by selecting the morphologically filled region with the largest area in the slice. For increasing the level of edge detail in the image a series of Top-Hat and Bottom-Hat enhancements (Russ, 2011[41]) are applied to the image, Top-hat emphasizes the edges present on the image while the bottom-hat decreases the undesired distortions on the image. The Top-Hat image is added to the original image while the Bottom-Hat image is subtracted from the image. To remove noise in the images a 3×3 median filter is utilized. The main reason median filtering was chosen for the preprocessing step of this algorithm is because median filters have the useful property of retaining edge information within an image as seen in Figure 2(Fig. 2). Mean filters and Gaussian filters tend to blur the edges in an image. This is because the median filter does not create new unrealistic pixel values when the window lays over an edge.

Liver Dome Detection

As liver sits just below the right lung, initial liver contour (liver dome) can be easily detected by searching from the lung lobe above. As lungs are mostly filled by air and air has the lowest attenuation coefficient in CT images, the lung area is often black resulting in easy detection of the lung lobes with reasonable accuracy. After the middle point of the right lung is detected, if there was a significant decrease (experimentally equal to 10 % on average CT series) in the area of the lung lobe going from superior to the inferior direction in two consecutive slices emergence of the liver dome is implied, as illustrated in Figure 3(Fig. 3). Although the set threshold can result in missing one slice (with a relative small liver dome) in some series, a tradeoff between accuracy and robustness are nevertheless unavoidable.

Ribcage removal

Since the main body of the liver is protected by the rib cage and to minimize the computational requirements of the segmentation algorithm and in order to remove the bulk of intercostal muscles between ribs, De'Boor algorithm (De Boor, 1972[13]) is utilized for ribcage contour segmentation. The centroid or center point of gravity of each rib in each slice is calculated, then all the points are joined by de Boor's algorithm, to achieve a smooth curve an experimental B-spline order of 3 is utilized. In any axial CT image, especially those towards the caudal direction, there might be slices not containing all the ribs, without enough centroid points a suitable curve enclosing the liver cannot be calculated. To avoid this situation, in case of a steep decrease in the area of segmented CT slice, detected rib centroids in previous and subsequent slices are overlaid on the slice being processed and the B-spline is re-calculated thus avoiding the under segmented slice. Figure 4(Fig. 4) shows a CT slice before and after rib cage removal.

Proposed segmentation method

Graph-Cut (GC) based segmentation is an alternative to boundary based segmentation methods, being a semi-automatic segmentation the user is required to provide the seeds representing the background and the object to be segmented, GC represents the image pixels as nodes on a graph with weighted edges representing the adjacency between the pixels. By finding the minimum cost function between all possible cuts of the graph, the GC segments the image into background and the object (Boykov et al., 2001[8]). The main disadvantage of regular GC segmentation is the bad handling of weak edges and noisy images, to overcome this limitation many methods have been proposed to enhance the basic GC algorithm. One of such methods receiving a wide interest in medical imaging is the random walker algorithm (Andrews et al., 2010[2]; Cui et al., 2013[12]; Grady and Sinop, 2008[16]). Random walkers segmentation was proposed by Grady (2006[15]), it is a supervised segmentation method meaning that a set of labels must be defined for each object prior to segmentation, this can be done interactively by the operator or be assigned automatically according to a predefined criterion. Random walker method segments the image by calculating the probability

that a random walker starting at pixel 'i' first reaching a pixel labeled L.

The principle of random walker segmentation is the construction of an undirected graph G= (V, E) where the nodes v ϵ V correspond to image pixels and e ∊ E ⊑ V ⨯ V. Weight W_ij is assigned to edge e_ij connecting nodes v_i and v_j based on the following equation:

Where g_i is the intensity at the pixel i and g_j is the intensity at pixel j. β is a scaling parameter set according to image contrast and ω is a regularization parameter that amounts to penalizing the gradient norm of P^L (ω = 0 results in no regularization). In order to increase the performance on complex CT images, the local spatial similarity between local pixels is incorporated into the weighting function, with this addition the weighting function transforms to:

Where the intensity relationship is denoted by w_ij (same as Eq. 1) and local spatial relation

is expressed by:

Where (x_i, y_i) are the spatial coordinates of the i^th pixel and (x_j, y_j) are the spatial coordinates of the adjacent j^th pixel and λ_s ^{represents the scale factor of}

spread.

Weight W_ij can be described as the probability of the random walker crossing a particular edge, random walkers will cross edges more easily in case of more homogeneous edges created by a lower edge weight and thus region labels are decided more by the pixel distance to seeds labeled L and less by image features. Greater values of edge weight create less homogeneous edges thus making it harder for random walkers to cross edges and the region labels are decided more by the locations of strong edges.

With the help of the circuit theory, Grady (2006[15]) showed that the connections between random walkers on a graph correspond to a combinatorial analog of the Dirichlet problem thus dramatically reducing calculation time by providing a convenient and simple method for the label probabilities computation.

A Dirichlet problem can be defined as the problem of finding a harmonic function subject to certain boundary values. A Dirichlet integral could be represented as:

The harmonic function minimizing the Dirichlet integral and satisfying the boundary condition can be achieved by the following Laplace equation:

Let's denote v_m as a set of seeded pixels and v_u the set of unseeded pixels, such that v_u∩ v_{m =}∅ and v_u∪ v_{m =}v. It was shown that all of the probabilities

that each node (pixel) v_i ∊ v_u being assigned to label L can be obtained with the minimization of:

Where the probabilities of seeds P^L are assigned as:

Where combinatorial Laplacian matrix of L is defined as:

Where d_v is the degree of the vertex of edge v_i (sum of weights of all the edges e_ij connecting v_i), for 2D images the vertices will have a degree of 4 or 8 and for 3D images the vertices could have a degree from 6 up to 26. Eq. 4 can be rewritten as:

Where C is a diagonal matrix edge weights assigned to its diagonal and A is the incidence matrix defined as:

Eq. 9 can be decomposed as:

Where x_U represents the probabilities of seeded and x_M represents the probabilities of unseeded nods, critical points are determined by differentiating D[x_U] with respect to x_U as:

Which represents a system of linear equations where |L_U| represents the unknowns. Using Eq. 7, the combinatorial Dirichlet solution can be found by solving the following equation for all labels:

Only L ˗ 1 systems must be solved as the sum of all probabilities at a node will be equal to zero:

After minimizing

for each label L, the segmented region is obtained by calculating maximum probability of the label by:

The workflow of the random walker method for image I can be summarized as:

1. Provide a set of marked pixels with L labels corresponding to desired segmentation regions

2. Map the image features such as intensities, texture information or other image features to edge weights and built the Laplacian matrix

3. Perform the random walker and obtain segmentation label for each region.

In a study comparing different segmentation methods for positron emission tomography (PET) images random walker were found to provide the most accurate results (Bağci et al., 2011[5]), in case of CT images random walker were more accurate than other segmentation methods such as level sets (Chen et al., 2011[9]) and in case of brain MRI random walker performed accurately (Choubey and Agrawal, 2012[11]). Figure 5(Fig. 5) shows segmented pathological livers with the random walker algorithm and the corresponding probability

it should be noted that the values are pixel specific and are mapped to gray-scale and displayed for easy visualization.

Seed implementation

After detection of the liver dome, seeds are implanted automatically according to the position of the liver dome with respect to the image. There are up to a total number of 1200 different seeded pixels for each slice with half of them representing the liver and the other half representing the other organs present in the slice.

As the liver changes considerably in shape and size, it is desired to have an approximate knowledge of these variations within a series to be able to implement a more robust seeing arrangement. In order to determine the approximate size of the liver, two slices after the detected liver dome are segmented using random walker algorithm. After these slices are segmented, the mean and the deviation of the intensity variation is calculated for these slices, then the right lung mask calculated for the slice just before the liver dome is used as a template and the rest of the CT series are masked based on that. Afterward, the number of the pixels falling within the pre-calculated liver mean and deviation are calculated, the slice with the highest number of pixels falling into the criteria is designated as the middle liver slice (biggest liver slice) and the slice with the lowest number of pixels is designated as the last slice, it should be noted that based on observations, the number of the pixels in the lower parts of the liver are usually around 100 (experimentally derived on standard 512×512 CT images), thus the threshold for detecting the last slice of the liver is set. This middle and last liver slice selection is done in order to have more control over the seeding arrangement and avoiding any overlapping of the seeds.

Datasets

Data used in this paper is provided by medical professionals from cancer imaging archive of the Frederick National Laboratory for Cancer Research (TCIA dataset, 2016[51]), 3Dircadb dataset provided by Research Institute against Digestive Cancer (IRCAD dataset, 2016[23]) and The Medical Image Computing and Computer Assisted Intervention Society (MICCAI) liver segmentation challenge (Sliver'07 dataset, 2016[46]). The algorithm is developed on pathological liver images with varying lesions from the cancer imaging archive dataset and then benchmarked against the Sliver'07 and 3Dircadb datasets. It should be noted that the Sliver'07 and 3Dircadb datasets are only used for benchmarking and are not used in the development. The developed framework showed exceptional accuracy in segmenting liver envelope while the typical runtime to segment a series of CT images was around 210 seconds. Only patients with pathologies were utilized from 3Dircadb data set in this study, totaling 15 patients with 120 lesions in total, making segmentation a difficult task and a good measure of segmentation accuracy, Figure 6(Fig. 6) illustrates a pathological case from 3Dircadb dataset.

In case of dataset acquired from the cancer imaging archive, all the patient data is confirmed to belong to cancerous cases by medical experts, while pixel spacing varied from 0.55 to 0.95 mm and slice thickness varied from 1 to 5 mm with all patient identification information removed, it should be noted that only contrast enhanced image data was utilized from this dataset.

In the case of Sliver'07 and 3Dircadb datasets utilized in this study for liver segmentation benchmarking, radiological experts manually outlined liver contours for all images on a slice-by-slice basis in order to determine the ground truth. The number of slices in each series, the slice thickness and the pixel spacing varied from 64 to 502, 0.5 to 5.0 mm and 0.54 to 0.87 mm respectively. The cases involved few healthy cases, but most of them are pathologic involving metastasis cysts and lesions of different sizes. The image resolution is 512×512 in all cases.

All internal structures of the liver such as vessels and lesions are included in the liver mask during manual segmentations. A vessel is considered as a part of liver if it is completely surrounded by liver tissue. If a vessel is partially enclosed by the liver (often the case where large veins-vena cava and portal vein enter or exit the liver), only the parts surrounded by liver tissue are included in segmentation. In the case of Sliver'07 dataset, in order to avoid inconsistency between transversal slices, a binary median filter of 3×3×3 size is performed as a post-processing step while a single expert examined the results and corrected them if necessary. In addition to all that, all patient and center related information in all the datasets were removed prior to making them public. The proposed segmentation is applied to the Sliver'07 and 3Dircadb datasets consisting of 35 series of enhanced CT series. It should be noted that the developed framework was run with Matlab 2013a on a personal computer with 8 GB of ram and an Intel i7 CPU. All the images utilized in this study are processed with a window level and settings recommendations for Abdominal CT imaging as illustrated in Figure 7(Fig. 7).

Statistical performance measures

Before any further discussion on the results, a brief introduction on five statistical performance measures utilized are given below, these statistical measures are commonly used in image segmentation validation. For calculating these statistics we need to consider the following notions:

True Positive (TP), means region segmented as object that proved to be the object.

False Positive (FP), means region segmented as object that proved not to be the object.

False Negative (FN), means region segmented as not object that proved to be the object.

True Negative (TN), means region segmented as not object that proved not to be the object.

Volumetric overlap error

Volumetric overlap error (VOE) expressed in percent, represents the number of pixels in the intersection of segmented region (A) and the ground truth (B), divided by the number of pixels in the union of A and B. A value of zero represents perfect segmentation while any increase in this value correlates to increased discrepancy between segmentation and ground truth. It can be calculated in percent from the following formula:

Precision or positive predictive value

Precision coefficient represents the overall performance of the algorithm in correctly segmenting the ROI pixels from the image. It can be calculated by the following formula:

Accuracy

Accuracy coefficient represents the overall performance of the algorithm in correctly including the pixels of the ROI inside the segmentation. It can be calculated by the following formula:

The accuracy of a segmentation system is the degree of closeness of segmentation to the ground truth. The precision of a segmentation system, related to reproducibility and repeatability is the degree to which repeated experiments under unchanged conditions yielding similar results. A measurement system can have high accuracy and low precision or any combinations of those, but a system is considered valid if both precision and accuracy are high.

Dice similarity coefficient

Dice similarity coefficient (DSC) also represents the overall performance of the algorithm in correctly including the pixels of the ROI inside the segmentation. It can be calculated by the following formula:

A value of 0 represents no overlap between the segmented region and ground truth while a value of 1 represents perfect segmentation.

Relative absolute volume difference

Relative absolute volume difference (RVD) expressed in percent, whereby the total volume of the segmented region is divided by the total volume of ground truth. It can be calculated by the following formula:

This measure should not be solely utilized to assess the performance of any segmentation method as a value of 0 (perfect segmentation) can also be obtained from an inaccurate segmentation, as long as the segmented region volume is equal to the volume of the ground truth.

Results and Discussion

The entire algorithm was able to segment an average series in 3.5 minutes utilizing a typical desktop computer. Average time required to segment a CT series with a slice thickness of 5 mm by an expert is around 30 minutes thus, our proposed method is approximately 9 times faster than manual segmentation while providing acceptable levels of accuracy. Table 1(Tab. 1) represents different statistical performance measures of the developed liver envelope segmentation approach in comparison to expert radiologist segmentation (ground truth) on Sliver'07 train dataset while Table 2(Tab. 2) represents different statistical performance measures of the developed approach in comparison to the expert radiologist segmentation on pathological livers from 3Dircadb dataset, it should be noted that negative values in RVD represent under-segmentation and positive values represent over-segmentation. Figure 8(Fig. 8) illustrates the difference in segmentation by the proposed method on pathological liver slices compared to radiologist segmentation.

From the statistical performance viewpoint, it can be assumed that the developed segmentation framework is amongst the more accurate segmentation methods developed and tested on the liver, achieving comparable result with most semi-automatic methods (Heimann et al., 2009[19]). In medical imaging two of the most accurate measures to ensure robustness and relative performance of the segmentation accuracy are overlap and dice, as these are measured with respect to the performance of the segmentation algorithm in achieving a proper segmentation with respect to the ground truth. In the case of Sliver'07 dataset, the proposed segmentation method was able to achieve an average DSC of 0.94 while the VOE is at 4.47 %, resulting a good overall average accuracy in extracting the liver envelope. As discussed earlier a segmentation method is considered valid if both precision and accuracy are high, the proposed method was able to achieve an average 0.95 and 0.99 in precision and accuracy respectively, clearly collaborating with the result of Dice Similarity Coefficient. Average DSC of 0.91 and VOE of 5.95 % was the performance of the proposed segmentation algorithm on pathological cases over the 3Dircadb dataset with an average 0.92 and 0.99 in precision and accuracy respectively. Considering that the 3Dircadb dataset consisted of many lesions making automatic segmentation considerably more difficult, these results are very promising. Table 3(Tab. 3) (References in Table 3: Maklad et al., 2013[33]; Beichel et al., 2007[6]; Goryawala et al., 2014[14]; Li et al., 2014[29]; Song et al., 2014[48]; Mostafa et al., 2015[36]; Shi et al., 2015[43]; Kainmüller et al., 2007[25]; Al-Shaikhli et al., 2015[1]; Wang et al., 2015[54]; Huang et al., 2014[22]; Xu et al., 2015[57]; Li et al., 2014[28]; Anter et al., 2014[4]; Wang et al., 2015[55]; Heimann et al., 2009[19]) compares the developed method with some of the more accurate methods proposed for liver segmentation.

While preparing the MICCAI challenge (Heimann et al., 2009[19]), the organizers observed that liver VOE of 6.4 % was the average performance of human segmentation (with medical training) compared to ground truth, thus it can be assumed that the performance of a method with an error rate equal or smaller than the mentioned 6.4 % is comparable to a human operator.

With a mean VOE of 4.47 % on mixed Sliver'07 dataset used by most other methods in the literature, the proposed segmentation method is comparable to other developed methods while the runtime of around 210-second means that the proposed method is viable as an alternative approach to manual segmentation by a radiologist. As discussed earlier, segmentation of segmentation of pathological livers is much more desirable. The proposed method was able to achieve a mean VOE of 5.95 % and a mean DSC of 0.91 on the very challenging 3Dircadb dataset while the other method that based its segmentation on pathological livers was able to achieve a mean DSC of 0.92 by a semi-automatic approach on a private dataset. Based on these results it can be assumed that the proposed method is comparable to human segmentation performance. Compared to most other segmentation approaches, our approach has the advantage of calculating the rib-caged area thus reducing the possibility of segmentation leakage and the inclusion of the muscle tissue as the liver, thus increasing the segmentation accuracy.

Although the relative volume difference (RVD) calculation and determining the liver volume is of importance as discussed earlier, segmentation algorithms still can achieve a high score in this area while being quite inaccurate as the algorithm can still give accurate volume calculations while the segmented region is widely inaccurate compared to the ground truth. This can be also observed from the overlap error of different segmentation methods, as a method with high overlap error can have a low relative volume difference error. Mean RVD of 2.38 % and 7.49 % has been achieved for Sliver'07 and 3Dircadb datasets respectively, making the proposed segmentation method comparable with other segmentation methods proposed.

The use of liver location estimation based on lungs effectively removes the need for any models to estimate the location of liver, enabling the random walker segmentation to segment the liver more accurately. In case any lesions are present inside the liver envelope, these lesions are also seeded and the ability of multi-region segmentation of the random walker means that these lesions will be also segmented with no regards to their location inside the liver, as segmenting the pathological livers in contrast-enhanced CT imaging are the main reason for taking the challenge of liver segmentation. Examples of challenging pathological livers segmented can be seen in Figure 9(Fig. 9).

These examples represent severe pathological disorders on livers that make segmentation a very challenging task compared to the data utilized in Sliver'07 challenge, as it can be seen the proposed segmentation algorithm was able to achieve satisfactory results. The main strength of the random walker algorithm compared to most other segmentation approaches is its ability to segment pathological livers accurately and within an acceptable time frame as the main goal of most liver segmentation methods is to increase the speed and the accuracy of liver lesion segmentation. The proposed method require no training thus removing the influence of different datasets on each other as segmentation on each slice is dependent on the liver segmentation from the previous slice compared to model-based and learning-based segmentations where pathological livers with large lesions represent the main disadvantage (Li et al., 2015[30]; Tibamoso and Rueda, 2009[52]; Rusko et al., 2007[40]; Tomoshige et al., 2014[53]; Okada et al., 2008[37]).

After the liver is extracted from the CT series, 3D virtualization can be utilized to help the physician in better visualizing the liver and possible lesions inside the liver, this is done as going through a CT series on a slice by slice basis is both tedious and time-consuming. Figure 10(Fig. 10) represents the 3D reconstruction of a segmented liver with pathologies.

Conclusions

Proper segmentation of liver envelope is the basis for any accurate CAD system utilized in lesion segmentation and classification while it is the basis of any surgery planning as accurate volume calculation and liver location visualization is the key in accurate prognosis. In this paper, random walker based segmentation for the liver envelope is proposed with the main goal of segmenting pathological livers in contrast-enhanced CT images. The proposed framework was able to achieve a mean VOE of 4.47 % and DSC of 0.94 on Sliver'07 dataset resulting in a performance comparable with human segmentation while in the case of pathological livers from 3Dircadb dataset, the mean overlap error was 5.9 % while DSC was 0.91. The proposed method is amongst the more accurate segmentation frameworks developed for liver envelope segmentation. Random walker has proved to be one of the most accurate segmentation approaches especially for medical imaging and can provide accurate segmentation in livers containing multiple lesions. Main disadvantage of the proposed method lays in the liver dome detection and last liver slice detection as some information might get lost as the algorithm might not consider some CT slices on top and bottom of the liver, although this affects final volume calculation minimally, further work can be done in order to enhance this selection of slices. The developed framework can also be easily applied to other organs within abdomen such as spleen, lungs, aorta and kidneys.

Conflict of interest

Authors declare that they have no conflict of interest.

References

1. Al-Shaikhli SDS, Yang MY, Rosenhahn B. Automatic 3D liver segmentation using sparse representation of global and local image information via level set formulation. arXiv preprint. 2015;150801521.

2. Andrews S, Hamarneh G, Saad A. Fast random walker with priors using precomputation for interactive medical image segmentation. In: International Conference on Medical Image Computing and Computer-Assisted Intervention (pp 9-16). Berlin: Springer-Verlag, 2010.

3. Anter AM, Azar AT, Hassanien AE, El-Bendary N, Elsoud MA. Automatic computer aided segmentation for liver and hepatic lesions using hybrid segmentations techniques. In: Federated Conference on Computer Science and Information Systems (pp 193-8). New York: IEEE, 2013.

4. Anter AM, Hassanien AE, Elsoud MA, Tolba MF. Neutrosophic sets and fuzzy c-means clustering for improving ct liver image segmentation. In: Proceedings of the Fifth International Conference on Innovations in Bio-Inspired Computing and Applications (pp 193-203). Berlin: Springer International Publishing, 2014.

5. Bağci U, Yao J, Caban J, Turkbey E, Aras O, Mollura DJ. A graph-theoretic approach for segmentation of PET images. In: Annual International Conference of the IEEE Engineering in Medicine and Biology Society (pp 8479-82). New York: IEEE, 2011.

6. Beichel R, Bauer C, Bornik A, Sorantin E, Bischof H. Liver segmentation in CT data: A segmentation refinement approach. In: Proceedings of 3D Segmentation in the Clinic: A Grand Challenge (pp 235-45). Brisbane: MICCAI, 2007.

7. Ben-Dan I, Shenhav E. Liver tumor segmentation in CT images using probabilistic methods. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 1-11). New York: MICCAI, 2008.

8. Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts. IEEE Trans Pattern Anal Mach Intell. 2001;23:1222-39.

9. Chen M, Helm E, Joshi N, Brady M. Random walk-based automated segmentation for the prognosis of malignant pleural mesothelioma. In: International Symposium on Biomedical Imaging: From Nano to Macro (pp 1978-81). New York: IEEE, 2011.

10. Chen Y, Chen W, Yin X, Ye X, Bao X, Luo L, et al. Improving low-dose abdominal CT images by weighted intensity averaging over large-scale neighborhoods. Eur J Radiol. 2011;42:49.

11. Choubey M, Agrawal S. An implementation of random walk algorithm to detect brain cancer in 2-d MRI. J Magn Reson Imaging. 2012;2:998-1001.

12. Cui Z, Li W, Pan G, Gao L. An improved random walker using spatial feature for image segmentation. In: Chinese Control and Decision Conference (pp 1479-82). New York: IEEE, 2013.

13. De Boor C. On calculating with B-splines. J Approx Theory. 1972;6:50-62.

14. Goryawala M, Gulec S, Bhatt R, McGoron AJ, Adjouadi M. A low-interaction automatic 3d liver segmentation method using computed tomography for selective internal radiation therapy. BioMed Res Int. 2014;3:1-12.

15. Grady L. Random walks for image segmentation. IEEE Trans Pattern Anal. 2006;28:1768-83.

16. Grady L, Sinop AK. Fast approximate random walker segmentation using eigenvector precomputation. In: Conference on Computer Vision and Pattern Recognition (pp 1-8). New York: IEEE, 2008.

17. Heimann T, Meinzer HP, Wolf I. A statistical deformable model for the segmentation of liver CT volumes 3D Segmentation in the clinic: A grand challenge (pp 161-6). Brisbane: MICCAI, 2007.

18. Heimann T, Münzing S, Meinzer HP, Wolf I. A shape-guided deformable model with evolutionary algorithm initialization for 3D soft tissue segmentation. In: Information Processing in Medical Imaging (pp 1-12). IPMI, 2007b.

19. Heimann T, Van Ginneken B, Styner MA, Arzhaeva Y, Aurich V, Bauer C, et al. Comparison and evaluation of methods for liver segmentation from CT datasets. IEEE Trans Med Imaging. 2009;28:1251-65.

20. Heimann T, Wolf I, Meinzer HP. Active shape models for a fully automated 3D segmentation of the liver an evaluation on clinical data. In: Medical Image Computing and Computer-Assisted Intervention (pp 41-8). Copenhagen: MICCAI, 2006.

21. Heimann T, Wolf I, Meinzer HP. Automatic generation of 3D statistical shape models with optimal landmark distributions. Methods Inf Med. 2007;46:275-81.

22. Huang C, Li X, Jia F. Automatic liver segmentation using multiple prior knowledge models and free–form deformation. In: Proceedings of the VISCERAL organ segmentation and landmark detection benchmark at the international symposium on biomedical imaging (pp 22-4). New York: IEEE, 2014.

23. IRCAD dataset. http://www.ircad.fr/research/3dircadb. Accessed 22 June 2016.

24. Joyeux H, Berticelli J, Chemouny S, Masson B, Borianne P. Mesure semi-automatique des différents lobes hépatiques application à la recherche d’une corrélation entre volumes des lobes du foie. Ann Chir. 2003;4:251-5.

25. Kainmüller D, Lange T, Lamecker H. Shape constrained automatic segmentation of the liver based on a heuristic intensity model. In: Proceedings of 3D Segmentation in the Clinic: A Grand Challenge (pp 109-16). Brisbane: MICCAI, 2007.

26. Kubota T. Efficient automated detection and segmentation of medium and large liver tumors: CAD approach. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 1-12). New York: MICCAI, 2008.

27. Lamecker H, Lange T, Seebass M. Segmentation of the liver using a 3D statistical shape model (pp 4-9). Berlin: Konrad-Zuse-Zentrum für Informationstechnik, 2004.

28. Li C, Li A, Wang X, Feng D, Eberl S, Fulham M. A new statistical and Dirichlet integral framework applied to liver segmentation from volumetric CT images. In: 13th International Conference on IEEE Control Automation Robotics & Vision (pp 642-7). ICARCV, 2014.

29. Li D, Liu L, Chen J, Li H, Yin Y. A multistep liver segmentation strategy by combining level set based method with texture analysis for CT images. In: 2014 IEEE International Conference on Orange Technologies (pp 109-12). New York: IEEE, 2014b.

30. Li D, Liu L, Kapp DS, Xing L. Automatic liver contouring for radiotherapy treatment planning. Phys Med Biol. 2015;19:461-83.

31. Ling H, Zhou SK, Zheng Y, Georgescu B, Suehling M, Comaniciu D. Hierarchical, learning-based automatic liver segmentation. In: IEEE Conference on Computer Vision and Pattern Recognition CVPR (pp 1-8). New York: IEEE, 2008.

32. Linguraru MG, Sandberg JK, Li Z, Pura JA, Summers RM. Atlas-based automated segmentation of spleen and liver using adaptive enhancement estimation. In: Yang G, Hawkes J, Rueckert D, Noble A, Taylor C (eds): Medical Image Computing and Computer-Assisted Intervention, MICCAI (pp 1001-8), Berlin: Springer-Verlag, 2009.

33. Maklad AS, Matsuhiro M, Suzuki H, Kawata Y, Niki N, Moriyama N, et al. Blood vessel-based liver segmentation through the portal phase of a CT dataset. In: SPIE, International Society for Optics and Photonics: Medical Imaging I (pp 420-8). Bellingham, WA: SPIE, 2013.

34. Moghbel M, Mashohor S , Mahmud R, Saripan MIB. Automatic liver tumor segmentation on computed tomography for patient treatment planning and monitoring. EXCLI J. 2016;15:406-23.

35. Moltz JH, Bornemann L, Dicken V, Peitgen H. Segmentation of liver metastases in CT scans by adaptive thresholding and morphological processing. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 195-203). New York: MICCAI, 2008.

36. Mostafa A, Fouad A, Elfattah MA, Hassanien AE, Hefny H, Zhu SY, et al. CT liver segmentation using artificial bee colony optimisation. Procedia Computer Science. 2015:1622-30.

37. Okada T, Shimada R, Hori M, Nakamoto M, Chen Y-W, Nakamura H, et al. Automated segmentation of the liver from 3D CT images using probabilistic atlas and multilevel statistical shape model. Acad Radiol. 2008:1390-403.

38. Park H, Bland PH, Meyer CR. Construction of an abdominal probabilistic atlas and its application in segmentation. IEEE Trans Med Imaging. 2003:483-92.

39. Qi Y, Xiong W, Leow WK, Tian Q, Zhou J, Liu J, et al. Semi-automatic segmentation of liver tumors from CT scans using Bayesian rule-based 3D region growing. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 201-11). New York: MICCAI, 2008.

40. Rusko L, Bekes G, Nemeth G, Fidrich M. Fully automatic liver segmentation for contrast-enhanced CT images. In: Proceedings of 3D Segmentation in the Clinic: A Grand Challenge (pp 143-50). Brisbane: MICCAI, 2007.

41. Russ JC. The image processing handbook. Boca Raton, FL: CRC Press, 2011.

42. Schmidt G, Binnig G, Kietzmann M, Kim J. Cognition network technology for a fully automated 3d segmentation of liver tumors. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 125-33). New York: MICCAI, 2008.

43. Shi C, Cheng Y, Liu F, Wang Y, Bai J, Tamura S. A hierarchical local region-based sparse shape composition for liver segmentation in ct scans. Pattern Recogn. 2015:88-106.

44. Shimizu A, Narihira T, Furukawa D, Kobatake H, Nawano S, Shinozaki K. Ensemble segmentation using AdaBoost with application to liver tumor extraction from a CT volume. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 1-11). New York: MICCAI, 2008.

45. Shimizu A, Ohno R, Ikegami T, Kobatake H, Nawano S, Smutek D. Segmentation of multiple organs in non-contrast 3D abdominal CT images. Int J Comput Assist Radiol Surg. 2007:135-42.

46. Sliver’07 dataset. http://www.Sliver07.org. Accessed 26 June 2016.

47. Smeets D, Stijnen B, Loeckx D, De Dobbelaer B, Suetens P. Segmentation of liver metastases using a level set method with spiral-scanning technique and supervised fuzzy pixel classification. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 43-55). New York: MICCAI, 2008.

48. Song H, Zhang Q, Wang S. Liver segmentation based on SKFCM and improved GrowCut for CT images. In: IEEE International Conference on Bioinformatics and Biomedicine (pp 331-34). New York: IEEE, 2014.

49. Stawiaski J, Decenciere E, Bidault F. Interactive liver tumor segmentation using graph-cuts and watershed. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 1-12). New York: MICCAI, 2008.

50. Taieb Y, Eliassaf O, Freiman M, Joskowicz L, Sosna J. An iterative bayesian approach for liver analysis: tumors validation study. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 1-7). New York: MICCAI, 2008.

51. TCIA dataset. http://www.cancerimagingarchive.net. Accessed 22 June 2016.

52. Tibamoso G, Rueda A. Semi-automatic liver segmentation from computed tomography (ct) scans based on deformable surfaces. In: Sliver’07 results [online] (pp 1-5). MICCAI, 2009.

53. Tomoshige S, Oost E, Shimizu A, Watanabe H, Nawano S. A conditional statistical shape model with integrated error estimation of the conditions;application to liver segmentation in non-contrast CT images. Med Image Anal. 2014;18:130-43.

54. Wang G, Zhang S, Xie H, Metaxas DN, Gu L. A homotopy-based sparse representation for fast and accurate shape prior modeling in liver surgical planning. Med Image Anal. 2015;19:176-86.

55. Wang X, Yang J, Ai D, Zheng Y, Tang S, Wang Y. Adaptive Mesh Expansion Model (AMEM) for liver segmentation from CT image. PLoS One. 2015;10:e0118064.

56. Wong D, Liu J, Fengshou Y, Tian Q, Xiong W, Zhou J, et al. A semi-automated method for liver tumor segmentation based on 2D region growing with knowledge-based constraints. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 159-69). New York: MICCAI, 2008.

57. Xu Z, Burke RP, Lee CP, Baucom RB, Poulose BK, Abramson RG, et al. Efficient multi-atlas abdominal segmentation on clinically acquired CT with SIMPLE context learning. Med Image Anal. 2015;24:18-27.

58. Zhou J, Xiong W, Tian Q, Qi Y, Liu J, Leow WK, et al. Semi-automatic segmentation of 3D liver tumors from CT scans using voxel classification and propagational learning. In: Proceedings of the Grand Challenge Liver Tumor Segmentation 2008 (pp 1-10). New York: MICCAI, 2008.

Figure 1: Flowchart of the proposed segmentation

Figure 2: Results of median filtering, original image (a) applied to a CT image (b), median filter (c)

Figure 3: Liver location with respect to lung (green) (a), CT slice just before liver dome (b) detected liver dome in red (c)

Figure 4: Original CT image (a), CT image after ribcage removal (b)

Figure 5: Segmented pathological liver with the random walker algorithm with red line representing the segmentation (a,c,e,g) and the corresponding visualized probability P^L_i (b,d,f,h) with white representing highest and black representing the lowest probability

Figure 6: Healthy (left) versus pathological liver (right) from 3Dircadb dataset (lesions represented in green)

Figure 7: CT image with window level and settings recommendations for Abdominal CT (a), CT image with dynamic window level and settings (b)

Figure 8: Examples of segmented liver with the proposed framework, with green line representing ground truth and red representing the proposed segmentation

Figure 9: Examples of difficult cases with lesions on liver border segmented using random walker algorithm

Figure 10: Example of 3D representation of a segmented liver by the proposed method (a,b) (liver in light green) and the segmented liver with visible lesions (c,d)

Table 1: Statistical performance of the developed liver envelope segmentation approach in comparison to ground truth on Sliver'07 dataset

Table 2: Statistical performance of the developed liver envelope segmentation approach in comparison to expert radiologist segmentation on 3Dircadb dataset

Table 3: Comparison between the developed method and some of the more accurate methods published on liver segmentation

[*] Corresponding Author:

Mehrdad Moghbel, Department of Computer & Communication Systems, Faculty of Engineering, University Putra Malaysia, 43400 Serdang, Selangor, Malaysia, eMail: mehrdad2275@gmail.com