I came across a cute segmentation idea called “Grow Cut” [pdf]. This paper by Vladimir Vezhnevets and Vadim Konouchine presents a very simple idea that has very nice results. I always feel that the simplest ideas are the best! Below I give a brief description of the algorithm and link to the Matlab/C/mex code.

GrowCut Region Growing Algorithm

This algorithm is presented as an alternative to graph-cuts. The operation is very simple, and can be thought of with a biological metaphor: Imagine each image pixel is a “cell” of a certain type. These cells can be foreground, background, undefined, or others. As the algorithm proceeds, these cells compete to dominate the image domain. The ability of the cells to spread is related to the image pixel intensity.

The authors give some pseudocode that very concisely describes the algorithm.


//for every cell p
for all p in image
  //copy previous state
  labels_new = labels;
  strength_new = strength;
  // all neighbors q of p attack
  for all q neighbors
    if(attack_force*strength(q)>strength_new(p))
      labels_new(p) = labels(q)
      strength(p) = strength_new(q)
    end if
  end for
end for

Segmentation Results

Once implemented, this is a nice way to get segmentations. It is quite fast, and the initialization is very intuitive. Consider this picture of a lotus flower:

growcut image

I made an initialization by clicking 20 points in the flower and 30 points outside. I then made a “label map” where unlabeled pixels are 0 (gray), foreground pixels are 1 (white) and background pixels are -1 (black).

growcut seeds

Based on this simple initialization, we obtain a very decent segmentation:

growcut output

As you can see, it isn’t perfect, but it is quite good. Its possible to interactively refine the seed points to improve the segmentation, but I didn’t do that here.

Matlab Code Downloads

I implemented this code in Matlab (using mex files due to the extensive use of for loops). You can download this below with compiled binaries for mac, linux, and windows. Unzip the file and run >>growcut_test for a demo.

UPDATE: I’ve fixed some bugs thanks to reader, Lin. The code works much better now!

Source & Compiled Binaries (96k) [zip]
“GrowCut” Paper [pdf]

Please let me know if you find this useful, and if you make improvements! Also, check out these related segmentation posts:

Related Segmentation Posts

58 thoughts on “GrowCut Segmentation In Matlab

  1. @James
    Thanks Shawn,Amit for your good code!!
    I guess I figure out the trick of saving label image. Now it seems can save the ‘proper’ label image.

    ================================================
    % Clear All %
    clc; clear all; close all;

    %img=imread(‘brain.png’);
    img=imread(‘20130423_150526.jpg’);
    figure(‘name’,’Input Image’);imshow(img);

    imgGray=rgb2gray(img);
    figure(‘name’,’Gray Image’);imshow(imgGray);

    [m,n]=size(imgGray);
    nn=6;
    disp(‘Select foreground piexel’);
    [y,x]=ginput(nn);
    hold on;
    x=round(x);%foreground
    y=round(y);
    disp(‘Select background piexel’);
    [yb,xb]=ginput(nn);
    xb=round(xb);%background
    yb=round(yb);

    label1=zeros(m,n);
    for i=1:nn
    a1=x(i);%foreground
    b1=y(i);
    a2=xb(i);%background
    b2=yb(i);
    label1(a1,b1)=1;%foreground %
    label1(a2,b2)=-1;%background %
    end
    labels=double(label1+2);

    figure(‘name’,’labels Image’);imshow(labels,[]);
    imwrite(labels,gray,’BD_label22.tif’);

    imgLabel=double(imread(‘BD_label22.tif’));
    figure(‘name’,’Read Label Image’);imshow(imgLabel,[]);

    % Convert back to -1,0,1 range %
    imgLabelC=imgLabel-1;
    figure(‘name’,’Read Label Image Convert to -1,0,1 range’);imshow(imgLabelC,[]);
    ========================================================

    James :
    OH~ I will try to do that. Thanks!

    Shawn Lankton :
    Make sure the type of your labels image can support negative numbers. For example, a signed int

  2. Thanks Shawn,Amit for your good code!!
    I guess I figure out the trick of saving label image. Now it seems can save the ‘proper’ label image.

    ================================================
    % Clear All %
    clc; clear all; close all;

    %img=imread(‘brain.png’);
    img=imread(‘20130423_150526.jpg’);
    figure(‘name’,’Input Image’);imshow(img);

    imgGray=rgb2gray(img);
    figure(‘name’,’Gray Image’);imshow(imgGray);

    [m,n]=size(imgGray);
    nn=6;
    disp(‘Select foreground piexel’);
    [y,x]=ginput(nn);
    hold on;
    x=round(x);%foreground
    y=round(y);
    disp(‘Select background piexel’);
    [yb,xb]=ginput(nn);
    xb=round(xb);%background
    yb=round(yb);

    label1=zeros(m,n);
    for i=1:nn
    a1=x(i);%foreground
    b1=y(i);
    a2=xb(i);%background
    b2=yb(i);
    label1(a1,b1)=1;%foreground %
    label1(a2,b2)=-1;%background %
    end
    labels=double(label1+2);

    figure(‘name’,’labels Image’);imshow(labels,[]);
    imwrite(labels,gray,’BD_label22.tif’);

    imgLabel=double(imread(‘BD_label22.tif’));
    figure(‘name’,’Read Label Image’);imshow(imgLabel,[]);

    % Convert back to -1,0,1 range %
    imgLabelC=imgLabel-1;
    figure(‘name’,’Read Label Image Convert to -1,0,1 range’);imshow(imgLabelC,[]);
    ========================================================

  3. hi Shawn,
    i was trying to find the accuracy of the growcut algorithm, will u pls help me to plot a bar graph of the result of this code

  4. i download this folder Source & Compiled Binaries (96k) [zip]. but unable to compile. There is difficulty to access some file growcutmex, growcutmex.mexmaci,test.m,test_data.mat. please help

  5. hello Shawn Lankton
    i would like first to thank you for the release. when i run the code using Matlab 2012b I had this error

    message Error: Could not detect a compiler on local system
    which can compile the specified input file(s)
    Error using mex (line 206)
    Unable to complete successfully.

    Error in growcut (line 37)
    mex growcutmex.cpp;

    Error in growcut_test (line 12)
    [labels_out, strengths] = growcut(img,labels);

    how can i do to solve the problem.
    for notice i got the code from this URL
    http://www.mathworks.com/matlabcentral/fileexchange/19091-growcut-image-segmentation

Leave a Reply

Your email address will not be published.