ISSN : 0975-2927
EISSN : 0975-9166
RAVINDRA S. HEGADI1*, BASAVARAJ A GOUDANNAVAR2
1Department of Computer Science, Karnatak University, Dharwad, India
2Department of Computer Science, Karnatak University, Dharwad, India
* Corresponding Author : ravindrahegadi@rediffmail.com
Received : 29-09-2011 Accepted : 03-11-2011 Published : 07-11-2011
Volume : 3 Issue : 3 Pages : 168 - 171
Int J Mach Intell 3.3 (2011):168-171
DOI : http://dx.doi.org/10.9735/0975-2927.3.3.168-171
Conflict of Interest : None declared
Medical images do not contain sharp edges. Therefore segmentation of these images is a challenging. In this paper we propose the algorithm for interactive segmentation of endoscopic images using extension of original graph-cut method. In this work a more powerful, iterative version of the optimization is used; the power of the iterative algorithm is used to simplify substantially the user interaction and a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colors of foreground pixels. This method is expected to be successful on a wide variety of images with foreground objects. The proposed algorithm is tested on endoscopic images containing tumors. The results of the proposed algorithm are encouraging.
Endoscopy, interactive image segmentation, foreground extraction, Convergence of iterative minimization, Gaussian Mixture Model labeling, image editing.
The technique of endoscopy has expanded the understanding of numerous gastrointestinal diseases since from its wide spread use in the late 1960s. As the video endoscope containing the intensity light source, suction equipment, guided camera, etc, passes under direct vision, through the esophagus and the stomach into a portion of duodenum, it transmits the video clipping of tissues for the display, the storage and the analysis. Endoscopy of lower gastrointestinal system provides real time image information and is being used increasingly to identify abnormalities and disorders of the colon.
Colonic polypoid lesions are the most common pathology found during endoscopy. The abnormality of polyps and tumors are mainly detected when the surface of the lipoma is eroded or irregular in contrast to a smooth surface. Normally, the creases of colon haustra, which are seen as contours in the endoscopic image, are smooth and are of arc shapes. However, the presence of polyps or tumors will lead to the shape of these contours being seen as distorted. Such distorted shape is reflected by the change of curvature sign along a normal smooth contour of the same curvature sign. Thus the possible presence of abnormality can be detected, if the contour’s curvature is analyzed. This approach is used by Krishnan for the intestinal abnormality detection from Endoscopic images based on the Canny’s method [10] for edge detection followed by curvature analysis.
Many graph based approaches for image segmentation can be found in literature. A graph cuts based active contours (GCBAC) approach was used [13] to segment medical images. This method is a combination of active contours and the optimization tool of graph cuts. It differs fundamentally from traditional active contours in that it uses graph cuts to iteratively deform the contour. Consequently, it has ability to jump over local minima and provide a more global result, it guarantee continuity and lead to smooth contours free of self-crossing and uneven spacing problems and this method easily extends to the segmentation of three and higher dimensional objects. In addition, the algorithm is suitable for interactive correction and is shown to always converge. The proposed method has successfully extracted the tumour regions from endoscopic images containing cancer tumours.
A normalized cuts based segmentation is used to segment abnormal region [14] from endoscopic images. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. These methods perform segmentation of the images through hierarchical partitioning instead of performing single flat partition. The other image features such as image brightness, color and texture are considered while performing segmentation. This method has shown good segmentation results for different types of medical images.
The method "GrabCut" proposed by C. Rother et al. [1] addresses the problem of efficient, interactive extraction of a foreground object in a complex environment whose background cannot be trivially subtracted. The aim is to achieve high performance at the cost of only modest interactive effort on the part of the user. This method can usually perform accurate segmentation of object from background.
The "GrabCut" method is based on graph cut which is proposed by Boykov and Jolly [2] . Two enhancements to the graph cut mechanism have been made: "iterative estimation" and "incomplete labeling" which together allow a considerably reduced degree of user interaction for a given quality of result. This allows GrabCut to put a light load on the user, whose interaction consists simply of dragging a rectangle around the desired object. In doing so, the user is indicating a region of background, and is free of any need to mark a foreground region.
We selected the images which contain a region of interest, which will act as foreground object and the other part as background. The initial information given about the foreground and the background are given by the user as a rectangular selection around the object of interest. Pixels outside this selection are treated as known background and the pixels inside are marked as unknown. From this data we want to create a model that we can use to determine if the unknown pixels are either foreground or background. In the Grab Cut algorithm this is done by creating K components of multivariate Gaussian Mixture Models (GMM) for the two regions. K components for the known background and K components for the region that could be the foreground, giving total 2K components. The GMM component has the same dimensions as the color space and is derived from the color statistics in each cluster. In order to get good segmentation we want to find components with low variance since this makes the cluster easier to separate from the others. There are a lot of ways to create clusters with this property. The decision was to test the color quantization technique described by Orchard and Bauman that were suggested in Implementing Grab Cut by Justin F. Talbot and Xiaoqian which works well.
The basic steps for the Grab Cut algorithm are as follows.
(i) The user input three things: The foreground, background, and the unknown part of the image that can be either foreground or background. This is normally done by selecting the rectangle around the object of interest and mark the region inside that rectangle as unknown. Pixel outside this rectangle will then be marked as known background.
(ii) The computer creates an initial image segmentation, where the unknown pixels are placed in the foreground class and all known background pixels are classified as background.
(iii) The foreground and background are modeled as Gaussian Mixture Models (GMIs) using the Orchard-Baumann clustering algorithm.
(iv) Every pixel in the foreground assigned most probable Gaussian Component in the foreground GMMs. The same process id done with the pixels in the background but with components of the background GMMs.
(v) New GMMs are learned from the pixel sets that where created in the previous step.
(vi) A graph is built and Graph Cut is used to find a new classification of foreground and background pixels.
(vii) Repeat step (iv)-(vi) until the classification converges.
The image is taken to consist of pixels zn in RGB color space. As it is impractical to construct adequate color space histograms, the GMMs is used to model the color data. Each GMM, one for the background and one for the foreground, is taken to be a full-covariance Gaussian mixture with K components.
In GMM each cluster is mathematically represented by a parametric Gaussian distribution. The entire data set is modeled by a mixture of these distributions. An individual distribution used to model a specific cluster is often referred to as a component distribution. Suppose there are K components (clusters). Each component is a Gaussian distribution parameterized by μk, Σk. Denote the data by X, X
. The density of component k is
The prior probability (weight) of component k is . The mixture density is
The parameters of GMM are estimated by the maximum likelihood (ML) criterion using the Expectation-Maximization (EM) algorithm. [Fig-1] shows an image and its GMM labeling.
The image is an array z = (z1, . . . , zn, . . . , zN) of grey values, indexed by n. The segmentation of the image is expressed as an array of "opacity" values at each pixel. For hard segmentation αn ∈ {0, 1}, with 0 for background and 1 for foreground.
describes the parameters of GMMs. In order to deal with the GMM tractably, in the optimization framework, an additional vector k = {k1, . . . ,kn, . . . ,kN} is introduced, with kn ∈ {1, . . .K}, assigning, to each pixel, a unique GMM component, one component either from the background or the foreground model, according as αn = 0 or 1.
The Gibbs energy for segmentation is defined as:
E(, k,
, z) = U (
, k,
, z) + V (
, z)
The data term U is defined according to color GMM models, as
U (, k,
, z) = ∑n D(αn, kn,
, zn)
Where D(αn, kn, , zn) = - log p(zn | αn, kn,
) - log π(αn, kn), so that
D(αn, kn, , zn) = - log π(αn, kn) +
log det ∑(αn, kn)
+ [ zn - µ(αn, kn) ]T ∑(αn, kn)-1 [ zn - µ(αn, kn) ]
The smoothness term V is computed using Euclidean distance in color space:
V(, z) =
where [φ] denotes the indicator function taking values 0, 1 for a predicate φ, C is the set of pairs of neighboring pixels. This energy encourages coherence in regions of similar color value. In practice, good results are obtained by defining pixels to be neighbors if they are adjacent either horizontally/vertically or diagonally (8-way connectivity). By optimizing performance the constant y was obtained as 50 and β is chosen to be:
Now that the energy model is fully defined, the segmentation can be estimated as a global minimum:
E(αn, kn,
, zn)
Minimization is done using a standard minimum cut algorithm [3] .
The new energy minimization scheme in Grab Cut works iteratively, in place of the previous one-shot algorithm [2] . This has the advantage of allowing automatic refinement of the opacities , as newly labeled pixels to refine the color GMM parameters
. The minimization algorithm is described below, which is modified from [1] .
The following procedure is applied when updating the GMM component in step (v) of algorithm: For a given GMM component k in, say, the foreground model, the subset of pixels F(k) = {zn : kn = k and an = 1} is defined. The mean μ(α, k) and covariance ∑(α, k) are estimated in standard fashion as the sample mean and covariance of pixel values in F(k) and weights are , where |s| denotes the size of a set S.
(i) Initialize background pixel to α = 0 and unknown region (draw box) to α = 1.
(ii) Initialize two sets of GMMs.
(iii) Assign GMM labels to each pixel. (Which set of GMMs is determined by α)
(iv) Graph cut minimize (a optimized, GMM labels changed to corresponding set of GMM)
E(
, k,
, z)
(v) Update GMM parameters
U(
, k,
, z)
(vi) Repeat from step (iii) until convergence
A demonstration of minimization is shown in [Fig-2] . (a) shows the energy E for this example converges over 12 iterations. The GMM in RGB color space (side-view showing R, G) at initialization is shown in (b) and after convergence is in (c). K = 5 mixture components were used for both background (red) and foreground (blue). Initially both GMMs overlap considerably as in (b), but are better separated after convergence in (c), as the foreground/background labeling has become accurate.
The implementation in MATLAB was tested using some different endoscopic images in order to evaluate the performance and the correctness of the segmentation. In [Fig-3] the segmentation of cancerous tumor is shown. Here the proposed algorithm could accurately segment the cancer growth part from the endoscopic image leaving the normal part as background. The initial, user-labeling is often sufficient to allow the entire segmentation to be completed automatically. In [Fig-4] a malignant cancerous tumor has been segmented from the endoscopic image using the proposed method.
Grab Cut works well when the object of interest has another color distribution compared to the background. If that's not the case the segmentation could be problematic at least with the statistical models that are proposed. The algorithm could segment the abnormal region from the medical images effectively. The result from the algorithm could be adjusted by a final touch up by the user that may improve the result. It will be necessary to do so for certain image. This algorithm for foreground extraction can produce segmentations of good quality for moderately difficult images with a rather modest degree of user effort. The algorithm can be used from segmenting other medical images such as CT scan, X-ray, MRI, ultra-sound and mammograms for ROI extraction.
[1] Rother C., Kolmogorov V. and Blake A. (2004) ACM Transactions on Graphics, 23(3), 309-314.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[2] Boycov Y. and Jolly M. (2001) Proc. IEEE Int. Conf. on Computer Vision, 1, 105-112.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[3] Kolmogorov V. and Zabih R. (2002) In Proc. ECCV., LNCS 2352, 65-81.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[4] Collobert R., Bengio S., Mariéthoz J. and Torch (2002) Technical Report IDIAP-RR 02-46.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[5] Refael Gonzalez, Richard and Woods E. (2002) Digital Image Processing, Pearson Edition Asia, 2nd Edition.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[6] Boykov Y., Veksler O. and Zabih R., (2001) IEEE Trans. Pattern Anal. Mach. Intell., 23 (11), 1222–1239.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[7] Grady L. and Funka-Lea G. (2004) In ECCV Workshops CVAMIA and MMBIA, 230–245.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[8] Baykov Y. and Jolly M. P. (2001) Proceedings. Eighth IEEE International Conference on Computer Vision, 1, 105-112.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[9] Hernandez G. and Herrmann H.J. (1996) CVGIP: Graphical Model and Image, 82-89.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[10] Hegadi et. al. (2004) 11th International Conference on Neural Information Processing, LNCS 3314, 834-842.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[11] Boykov Y. and Jolly M.P. (2000) In Medical Image Computing and Computer-Assisted Intervention, 276–286.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[12] Carsten Rother et. al (2004) ACM Transactions on Graphics (SIGGRAPH), 23 (3).
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[13] B.V. Dhandra and Ravindra S. Hegadi (2007) IEEE Int. Conf. on Advances in Computer Vision and Information Technology (ACVIT), Aurangabad, India, 923-931.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[14] Ravindra S. Hegadi (2010) Australian Journal of Intelligent Information Processing Systems, 12 (4), 46-50.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
 | Fig. 1- Gaussian Mixture Model labeling of a color image. |
 | Fig. 2- Convergence of iterative minimization |
 | Fig. 3- Segmentation of endoscopic image using proposed method a. Selection of region of interest to be segmented from the image b. Extraction of tumor from the image using proposed method c. Foreground and background together to examine the accuracy of the segmentation. |
 | Fig. 4- Segmentation of malignant cancerous tumor from endoscopic image using proposed method |