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. sir,
    i have a question about growcut segmentation that you use lotus image for segmntation,find result
    but we use that algotrithm in another image m,we will not get proper result,
    sir any program setting for that we run on different image
    plz send reply as early as possibl

  2. @tariq With grow-cut you must be careful with your initializations. If at first your segmentation is incorrect, try adding some additional initialization points both inside and outside your object. As shown in the post, the ‘inside’ initialization points should have a value of 1 and the ‘outside’ initialization points should have a value of 0.

  3. Hi Shawn,

    Just a quick comment regarding maxC… if it is indeed the maximum value of the cost function, if you’re using the L2-norm in RGB space, shouldn’t the max be sqrt(3*(255^2))? I’m not sure where you got the 441 figure from… as 256^2 is 65536, unless you considered a perceptually uniform colour space, but judging from your code, it is RGB data.

    In any case, that was just my two cents. Your code is actually quite good, and I actually stumbled upon this posting by accident. I was looking for something else all together, and found this GrowCut entry you made. I’m considering using it for another application I’m developing.

    Thanks,
    – Ray.

  4. Hi Shawn,

    Never mind about that previous post… I just didn’t bother to crunch in the number myself. Your 441 figure is in fact sqrt(3*255^2)… thanks!

    @Jhon, the 441.673 figure is the greatest possible L2 norm between the darkest and brightest colours… in this case, it’s black and white, so sqrt((255-0)^2 + (255-0^2 + (255-0)^2) = sqrt(3*(255^2)) = 441.673.

    Hope this helps,
    – Ray.

  5. Hi Shawn, i am interestied in it.
    but i have some questions,like what is the “strength” ?
    how do i get “strength” in this method ?

    Thanks!!

  6. hello shawn,
    i am very beginner at image processing. I am trying to understand your code, but to use it for other pictures, i should have another label maps. How could you assign a label map just by clicking? I didn’t understand…
    thanks a lot!

  7. hello Mr.Shawn

    I tried to construct labels picture, but I found it very difficult to built labels picture for each picture I am going to segment. could you please provide me by the code to construct the labels picture just by clicking?
    thanks alot.

  8. Hi Shawn, I tried the algorithm and find good results for some simple images. But when applied to image with fuzzy or semi-transparent edge, the semi-transparent part was lost. How to improve this?

  9. Hi Shawn..im doing project in Grow cut segmentation..But i need matlab code for refine the seed points to improve the segmentation..Can you guide me??

  10. Hello sir, can u send me some more example images for my references…… please sir…….

  11. @Jay
    type following code to create label image.
    Here nn=6 which means you can choose first 6 piexel as foreground piexel and next 6 piexel as background piexel. You can choose more piexel by changing nn value.

    img=imread(‘brain.png’)
    imshow(img);
    nn=6;
    [y,x]=ginput(nn);
    hold on;
    x=round(x);
    y=round(y);
    disp(‘Select background piexel’);
    [yb,xb]=ginput(nn);
    xb=round(xb);
    yb=round(yb);
    label1=zeros(m,n);
    for i=1:nn
    a1=x(i);
    b1=y(i);a2=xb(i);
    b2=yb(i);
    label1(a2,b2)=-1;
    label1(a1,b1)=1;
    end
    labels=double(label1);

  12. sir,
    is it possible to extract a particular cartoon character from pictures and save it without background information

  13. good morning sir

    in the GROWCUT algorithm, assert function is not present in the zip file.

    can you send me the assert function for testing the algorithm please.

  14. can growcut algorithm be used for nuclei segmentation of medical images. can this algorithm segment multiple objects or cells in a single image. can this algorithm handle overlapping of nuclei or cells.

  15. I think you could easily modify the code to have more than two competing regions. Check the original paper – I believe the authors discuss this.

    Overlapping cells would be a challenge for this algorithm. For that you may consider shape-constrained active contours.

  16. There are many algorithms that use seeded region-growing. This one in particular plays off the idea of cellular autonomy. Not sure if it’s the same as what you’re calling, “Seeded Region Growing Segmentation.”

  17. Hi Shawn
    I think that your algorithm is just what I need to proceed in my Bachelor Thesis, but I cannot get the function to work on my Mac. When I try to run the test-script I get following error message:

    ??? Undefined function or method ‘growcutmex’ for input arguments of type ‘double’.

    Error in ==> growcut at 29
    [l s] = growcutmex(img,labels);

    Error in ==> test at 8
    [labels_out, strengths] = growcut(img,labels);

    It appears that it cannot find growcutmex even though it is in the directory. Do you know if anyone else have had this problem when running the script on a Mac and do you have any idea to what I could do to make it work?

    Thanks, Sarah

  18. @ amit
    I think that I have already downloaded all the files, but for some reason the mex file does not work. I have had this problem with another mex file and in that cases it was because I needed the *.mexmaci64 file and not just the *.mexmaci file.
    I do not think that I have C++ compiler, but I must admit that I do not know for sure.

  19. @Sandra the code is implemented in mex (meaning that the codes are a combination of C++ and MATLAB). If you implement GrowCut in pure-MATLAB it will be very slow because it’s highly-dependent on for loops.

    All of the codes I used are provided above for download.

  20. @kiran
    @ Kiran : Did you get any idea on how to proceed on with segmenting overlapped cells? I too work on that :) i have tried watershed segmenting techniques which results in over segmentation and also here we cant go for marker controlled watershed too :(…. please share some info if you get know any :) and also try this paper — i have tried implementing bt i don get proper results — check if you can :) http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1026672&tag=1
    If you do not have access to this link– text me on –> biomedicaltalks@gmail.com :)

  21. hello sir,
    can i know how to apply measures like local consistency error,global consistency error or rand index,variation of information etc,…which are used for measuring performance….
    kindly mail me at sumanthshaan@yahoo.com

  22. Shawn, I’ve downloaded your code and the paper you have linked to just to learn and play with the code so I can understand the theory.

    What’s the difference between your grow-cut algorithm and region-growing algorithm available in Matlab file exchange?

    http://www.mathworks.com/matlabcentral/fileexchange/19084-region-growing/content/regiongrowing.m

    Sorry, if my question seem stupid as I’m totally new to image processing & vision. I’ll learn your code and possibly try and port it into Java.

  23. Hi – Not sure how the Matlab codes work, but the GrowCut algorithm uses seeding in a unique way that (in my experience) produces better results than the build-in Matlab function. It also provides the opportunity to build in new “similarity” measures (beyond color similarity). For instance you could extend this method to compare tensors, textures, etc. Hope that’s helpful.

  24. Hello Shawn , i am a beginner in Image Processing .Would you please explain me what line number and paragraph of code in “glowcutmex.cpp” should be edit and what the purpose of each editing , if i need to take glow-cut segmentation with another image

    Pardon for my poor english and thank you for your kind.
    Knotto.

  25. Sir, I tried above code to create label image, but i am getting the error
    ??? Error using ==> growcut
    labels and image must be the same size

  26. Hi, I ran this code to create the label image, when imshow(labels,[]); it is correct comprised of -1, 0, 1. But, when save as imwrite(labels,’labe22.png’); The label image become 0~255 and can not used in growcut.

    Error using growcut (line 25)
    labels must be comprised of -1, 0, 1

    Is it a way to save the -1, 0, 1 value to label image? Thanks.-James

    ====
    img=imread(‘brain.png’)
    imshow(img);
    nn=6;
    [y,x]=ginput(nn);
    hold on;
    x=round(x);
    y=round(y);
    disp(‘Select background piexel’);
    [yb,xb]=ginput(nn);
    xb=round(xb);
    yb=round(yb);
    label1=zeros(m,n);
    for i=1:nn
    a1=x(i);
    b1=y(i);a2=xb(i);
    b2=yb(i);
    label1(a2,b2)=-1;
    label1(a1,b1)=1;
    end
    labels=double(label1);
    figure(‘name’,’labels Image’);imshow(labels,[]);
    imwrite(labels,’labe22.png’);
    imgLabel=imread(‘BD_label22.png’);
    figure(‘name’,’Read Label Image’);imshow(imgLabel,[]);

  27. James :
    Hi, I ran this code to create the label image, when imshow(labels,[]); it is correct comprised of -1, 0, 1. But, when save as imwrite(labels,’labe22.png’); The label image become 0~255 and can not used in growcut.
    Error using growcut (line 25)
    labels must be comprised of -1, 0, 1
    Is it a way to save the -1, 0, 1 value to label image? Thanks.-James
    ====
    img=imread(‘brain.png’)
    imshow(img);
    nn=6;
    [y,x]=ginput(nn);
    hold on;
    x=round(x);
    y=round(y);
    disp(‘Select background piexel’);
    [yb,xb]=ginput(nn);
    xb=round(xb);
    yb=round(yb);
    label1=zeros(m,n);
    for i=1:nn
    a1=x(i);
    b1=y(i);a2=xb(i);
    b2=yb(i);
    label1(a2,b2)=-1;
    label1(a1,b1)=1;
    end
    labels=double(label1);
    figure(‘name’,’labels Image’);imshow(labels,[]);
    imwrite(labels,’labe22.png’);
    imgLabel=imread(‘BD_label22.png’);
    figure(‘name’,’Read Label Image’);imshow(imgLabel,[]);

    labelsimage
    [IMG]http://imageshack.us/a/img706/1852/labelsimage.jpg[/IMG]

    readlabelimage
    [IMG]http://imageshack.us/a/img853/2483/readlabelimage.jpg[/IMG]

  28. I think when imwrite the “-1” value of label image has been remove or set to 0. I do not know how to correct it. any idea?

  29. I try to chnage -1 to 128 and 1 to 255,but when imwrite it will be saved as 0~255 gray image with only 1 and 255!!! 128 has been move to 255.Seems imwrite will save array to binary image 0 or 255.

    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

Leave a Reply

Your email address will not be published.