An Improved K-Means Clustering Method for Liver Segmentation

An Improved K-Means Clustering Method for Liver Segmentation

Ina Singh Neelakshi Gupta

Amritsar College of Engineering and Technology Assistant Professor

Meharbanpur, Punjab Amritsar College of Engineering and Technology Meharbanpur, Punjab

Abstract – Determining liver accurately from CT scans is the primary and crucial step for an automated liver segmentation. The knowledge of the liver structure, liver surface and liver volume is required for liver segmentation. The boundaries of the various organs are nor clearly visible as a result of complex structure of the human body. This paper proposes an ant colony based k-means method which reduces the initial clusters problem of k-means clustering method. In this proposed method level set methods have also been used to improve the contours of the liver region. The paper aims in comparing the traditional k-means method and improved k- means method using ant colony optimization on the basis of geometric accuracy and elapsed time. Experimental results obtained on 15 CT scan images show that the proposed approach obtained better segmentation results than the already existing one. The results provided an increase in the geometric accuracy and a decrease in elapsed time which clearly show that the results are better than those obtained with existing technique.

Keywords -Active Contours, Ant colony optimization, Liver Segmentation, Region of Interest.

1. INTRODUCTION

   Liver is an essential organ of vertebrates and some other animals located in the upper right quadrant of the abdomen. The liver has a wide range of functions which include breakdown and synthesis of simple and complex molecules. Liver performs a large number of operations in the human body. Yet, there is no technique or device that can compensate for the lack of the liver. The sole available option is liver transplantation, which is really a major and risky surgery. Although transplantation from cadavers utilized to be the initial choice, transplantation from living donors has changed into a selection of treatment due to the shortage of corpse intended for dissection in recent years. Before the beginning of surgical procedure, the livers that fit in with the living donor and

   the recipient are analysed: to recognize the liver region, to determine the mismatch in size, to measure accurate liver volume, and to analyze the vascular structure. A successful treatment depends on easy and robust preoperative understanding but challenging to understand the complex inner structure. For any local treatments it is necessary to identify and precisely localize the liver surface, segments, tumors, and topography of blood vessels. Many research groups have developed different approaches for liver and tumour segmentation. They gave different approaches and algorithms for automatic liver segmentation.

2. LITERATURE SURVEY

   Sara Saatchi et al. [10] proposed a novel concept of ACO and integrated its learning mechanism with k-means algorithm to solve image clustering problem. The learning mechanism of the proposed algorithm is obtained by using the defined parameter used with ants called pheromone, by which undesired solutions of the K-means algorithm is reduced. The proposed method improves the K-means algorithm by making it less dependent on the initial parameters such as randomly chosen initial cluster centers and hence more stable. C. Immaculate Mary et al. [11] cluster refinement from k-means with ant colony optimization. The proposed technique was tested in medical domain and shows that refined initial starting points and post processing refinement clusters lead to improved solutions. Jue lu et al. [12] combined ACO and k-means clustering to improve clustering accuracy and speed up algorithm convergence. P.S Shelokar et al. [13] presented ant colony optimization methodology for optimally clustering objects into clusters. The algorithm employs distributed agents which adapt the way the real ants find shortest path from nest to food source and back.

3. EFFECTIVENESS OF ANT COLONY OPTIMIZATION WITH K-MEANS CLUSTERING

   Ant-based clustering and sorting was originally introduced for tasks in robotics. Then a algorithm was modified to be applicable to numerical data analysis, and it has subsequently been employed for data-mining, graph- partitioning and text-mining. Such ant-based methods show their effectiveness and efficiency in a couple of test cases. However, the ant-based clustering approach is generally immature and leaves big space for improvements. Along with your considerations, however, the standard ant- based clustering performs well; the algorithm contains large amount of parameters like pheromone, agent memory, quantity of agents, quantity of iterations and cluster retrieval etc. For these parameters more assumptions have already been made within the last works. To date, ants are used to cluster the data points. Here, for initially we've used ants to refine the clusters. The clusters from the aforementioned section are believed as input to the ACO based refinement step. The fundamental reason for our refinement is, in virtually any clustering algorithm the obtained clusters won't give 100% quality. You could have some errors called misclustering. That's, a data item could possibly be wrongly clustered. These types of errors could possibly be avoided by using the refinement

   algorithm. Inside this approach, just one ant can be utilized to refine the clusters. This ant is permitted to go for a random walk on the clusters. Whenever it crosses a group, it'll pick something from the cluster and drop it into another cluster while moving. The pick and drop probability is calculated as given:

   Picking probability = ( k1/ k1 + f ) 2

   Dropping Probability = ( f/ k2 + f ) 2

   Here, could be the entropy value of the clusters calculated before that has been picked and dropped, while k1 and k2 are threshold constants (picking-up threshold and dropping threshold, respectively). If the dropping probability is less compared to picking probability then your item is dropped into another cluster and the entropy value is calculated again. This random walk is repeated for N level of times. From the next section, it is shown our refinement algorithm improves the cluster quality. The algorithm is given as:

   1. Choose numerous clusters k

   2. Initialize cluster centers 1k predicated on mean.

   3. For each data point, compute the cluster center it is closest to (using some distance measure) and assign the data point to the cluster.

   4. Re-compute cluster centers (mean of data points in cluster)

   5. Stop when no new re-assignments occur.

   6. Ant based refinement

      1. Input the clusters from improved k-means.

      2. For i = 1 to N do

         1. Allow ant go for a random walk to select something

         2. Calculate the pick and drop probability

         3. Decide to drop the item.

         4. Re-calculate the entropy value to check whether the standard is improving.

      3. Repeat till convergence.

4. RESULTS AND DISCUSSIONS

   In this paper, the effectiveness of ant colony optimization with k-means clustering for liver segmentation from CT images was analysed. The liver images were collected from various medical sites. The implementation of the framework is completed in MATLAB. The performance metrics like Geometric Accuracy and Elapsed Time are computed for quantitative comparison.

   For qualitative analysis, output images of the implemented framework are shown in Fig 1(a-(i). The images show the original image, then k-means clustering is placed on the image using four clusters which helps to generate a preliminary contour of the CT image. Then level set and ACO are applied that assist in optimizing the k-clusters. The particular level set minimizes the gradient of the energy. Iterations occur till the energy is minimized and a final segmented image is obtained. From the figure it can be seen that the original energy of the level set function is above zero. After applying the level set, the energy is minimized and drops below zero i.e. negative energy is obtained showing the minimum energy.

   1. (b) (c)

(d) (e)

(f) (g)

Fig 1: (a) Original image of abdominal CT, (b) Image after applying K-Means Clustering with k=4,

(c) Image showing the edge detection function, (d) Image showing initial level set energy, (e) Image showing Final level set energy, (f) Image depicting the active contour of the CT scan image, (g) Final segmented image after applying K-means, level

set and ant colony optimization.

Quantitative Analysis

The quantitative results are presented in tables which gives the comparison between the existing and proposed technique on basis of Geometric Accuracy and Elapsed Time. The results were taken on 15 CT scan images which were obtained from various medical sites such as Dicom Library. The images were processed using image processing and optimization toolbox of MATLAB. The existing technique uses Level Set Method and K-Means Clustering whereas proposed technique uses Ant Colony Optimization along with K-Means Clustering and Level Set Method in order to improve the existing results.

Geometric Accuracy Analysis:

Table below shows the comparative output of the existing and proposed technique on basis of Geometric Accuracy. The results were taken on fifteen CT images.

The figure below shows the graphical implementation of the above table. The graph clearly depicts that the results of the proposed technique are much better than those obtained from the existing technique.

Comparative analysis on basis of G-Accuracy

Time Analysis

Table below shows the comparative output of the existing and proposed technique on basis of Geometric Accuracy. The results were taken on fifteen CT images. The time is calculated from the start of iteration to the end of iterations

The figure below shows the graphical implementation of the above table. The graph clearly depicts that the results of the proposed technique are much better than those obtained from the existing technique.

Conclusion and Future Scope

Comparative analysis on basis of Elapsed Time

In this paper, an improved method for automatic and unsupervised liver segmentation is presented. The principle advantages of the proposed technique are, first it does not need training data. Second, it is capable to segment livers effectively with high accuracy. Thirdly, it is a fully automated segmentation technique in which the user need not define the Region of Interest for segmentation. The technique itself is capable of identifying the required region and segmenting it. Finally, the proposed framework is robust and requires less computational time for execution. The improved K-means Clustering method solved the initial clusters problem by refining the clusters using ant colony optimization. . Both quantitative and qualitative analyses are in favor of hybrid k-means (k- means with ACO). The experimental results gave an improved value for G-accuracy and a decrease in computational time. In future, K-means clustering method can be tested using different optimization techniques such as seeker optimization and particle swarm optimization techniques.

REFERENCE

1. Evgin Goceri and et al., Fully automated liver segmentation from SPIR image series, Computers in biology and medicine, Vol.53, 265-278, Elsevier 2014.

2. Haibin Ling et al., Hierarchical, learning based automatic liver segmentation, IEEE 2008.

3. Amir H. Forouzan et al., Liver Segmentation by intensity analysis and anatomical information in multi-slice CT images, Springer 2009.

4. Gang Chen and et al., Improved level set for liver segmentation and perfusion analysis in MRIs, Information Technology in Biomedicine, Vol.13, 94-103, IEEE 2009.

5. S.Esneault, Liver Vessel Segmentation using a Hybrid Geometrical Moments/Graph Cuts Methods, Biomedical Engineering, Vol.57, 276-283, IEEE 2010.

6. Zhaoxiao Yuan and et al., A novel automatic liver segmentation technique for MR images, Image and Signal Processing, Vol. 3, 1281-1286, IEEE 2010.

7. O. Gambino and et al., Automatic Volumetric Liver segmentation using Texture based region growing, Complex ,Intelligent and Intensive Systems, 146-152, IEEE 2011.

8. A. Militzer and et al., Automatic detection and segmentation of focal liver lesions in contrast enhanced CT images, Signal, Image and Video Processing, Vol.7, 163- 172, IEEE 2010.

9. Laurent Massoptier and Sergio Casciaro, A new fully automatic and robust algorithm for fast segmentation of liver tissue and tumors from CT scans, European Radiology, Vol. 18, 1658-1665, Springer 2008.

10. Sara Saatchi et al. Hybridization of the Ant Colony Optimization with the K-Means Algorithm for Clustering, pp 511-520, Springer 2005.

11. C.Immaculate et al., Refinement of clusters from K-Means with Ant colony optimization, 28-32, Journal of Theoretical and Applied Information Technology 2013.

12. jue lu et al. A new hybrid clustering algorithm based on k- means and ant colony optimization, 1718-1721, ICCSEE 2013.

13. P.S. Shelokar et al., An ant colony approach fo clustering, 187-195, Elsevier 2004.

14. A.K. Mishra, Decoupled Active Contour for Boundary Detection ,Pattern Analysis and Machine Intelligence, Vol. 33, 310-324, IEEE 2011.

15. S.S. Kumar and et al., Automatic liver and lesions segmentation: a primary step in diagnosis of liver diseases, Pattern Recognition, 2524-2527, Springer 2011.

16. Shweta Gupta and Sumit Kumar, Variational Level Set Formulation and Filtering Techniques on CT Images, IJEST 2012.

17. Priyadarshini S. et al., Survey on segmentation of liver from CT images, IEEE 2012.

18. Abdalla Zidan, Level Set based CT liver image segmentation with watershed and artificial neural networks, International conference on hybrid intelligence systems, 96- 102, IEEE 2012.