Sparse Field Active Contours
Active contour methods for image segmentation allow a contour to deform iteratively to partition an image into regions. Active contours are often implemented with level sets. The primary drawback, however, is that they are slow to compute. This post presents a technical report describing, in detail, the sparse field method (SFM) proposed by Ross Whitaker [pdf], which allows one to implement level set active contours very efficiently. The algorithm is described in detail, specific notes are given about implementation, and source code is provided.
Fast Level Sets Demo
The links below point to the technical report and a demo written in C++/MEX that can be run directly in MATLAB. The demo implements the Chan-Vese segmentation energy, but many energies can be minimized using the provided framework.
Sparse Field Method – Technical Report [pdf]
Sparse Field Method – Matlab Demo [zip]
To run the MATLAB demo, simply unzip the file and run:
>>sfm_chanvese_demo
at the command line. On the first run, this will compile the MEX code on your machine and then run the demo. If the MEX compile fails, please check your MEX setup. The demo is for a 2D image, but the codes work for 3D images as well.
My hope is that other researchers wishing to quickly implement Whitaker’s method can use this information to easily understand the intricacies of the algorithm which, in my opinion, were not presented clearly in Whitaker’s original paper. Personally, these codes have SUBSTANTIALLY sped up my segmentations, and are allowing me to make much faster progress towards completing my PhD!
Thanks to Ernst Schwartz and Andy for helping to find small bugs in the codes and documentation. (they’re fixed now!)
For more information regarding active contour, segmentation, and computer vision, check here: Computer Vision Posts
good! I make it!
Thanks for the detailed implementation. I’ve been trying to implement the sparse field method based on Whitaker’s paper which is not very detailed. You’re technical report is perfect! Thanks.
Thanks Shawn, this is really helpful.
I’ve been frustrated for a while that Whitaker’s original explanation of SFM is confusingly brief, and that every subsequent description I’ve managed to find is a Copy-And-Paste job (even in “Insight into Images”, ed Yoo).
I’ve not tried your code, but your tech report is perfect for me: I knew it would be straightforward, but just couldn’t get there myself.
Thanks again.
I think there is a tiny tiny typo in Procedure 1: in line 10, the label(q) should be set to -1 rather than 1, I think!
@Andy
Yes, you’re right. Thanks! FIXED now.
@Shawn, sorry, I’m really not trying to find typos, I promise – I’ve just been implementing it and I spotted another one :D Procedure 2, lines 27-28: the conditions are the wrong way around. It should be ‘>’ on line 27 and ‘<=' on line 28.
Also, for the sake of consistency, I think it would make the description more robust if you standardized the way that a layer's membership is defined: sometimes it is [ (x-0.5)..(x+0.5) ), other times it is ( (x-0.5)..(x+0.5) ], other times it is [ (x-0.5)..(x+0.5) ]. I say this only because I've implemented an 'N layers' version of your code, and I spotted that sometimes you flip your convention.
Regards,
Andy.
Thanks again for finding more typos! They are fixed now.
The way the list membership works is consistent if you put the layers on a number line. Basically, “exterior” bounds are inclusive and “interior” bounds are exclusive. This gives points a (slight) preference towards being on interior layers. However, I expect that the convention doesn’t matter much.
hi,i have read your publication about [Localizing Region]-Based Active Contours and the code. But i was confused when i read the part of “Multiple Interacting Contours” of the article, i did not know how it works. I will appreciate greatly If you can send the code to my E-Mail(jun.c81@gmail.com)to show me “how two contours can interact with each other to find the correct segmentation”.
hi, i have read your publication spear field method, and its very clear and helpful, i only have a doubt. How are the pixels of the image divided for this 5 level sets lists? how can we get these values between -2.5 and 2.5 for the pixels?? thank you
@Jun.C
Hi Jun. The formulas are given quite clearly in the paper. Essentially, the two contours compare their “evolution force” to all “evolution forces” nearby. That way, curve segments near each other will move together, toward the best joint energy, and curve segments that are far apart move individually. -cheers!
@Luis M
The pixels of the image are not placed in the 5 lists [-2 -1 0 1 2]. Instead, the lists represent the surface $\phi$ that embeds the contour. The image pixels are left in their original domain, and remain unaltered throughout the segmentation.
Hi.. I am a student who is trying to implement your coding. Can you plz tell me what mu1 and m2 in the Chan-Vese Energy equation are? I seem to have got stuck there. It would be helpful if you can tell me how to code that in c#
@Prashanth
mu_1 and mu_2 refer to the mean of image points inside and outside of the contour as stated in the Chan-Vese paper “Active Contours Without Edges.”
Also, in Procedure 2, line 9, what do you mean by maximum of points q within N(p). By points, you refer to a coordinate if I am correct? If that is the case, how can you choose the maximum of 3 coordinates?
Here I mean the maximum of I(q) for q within N(p).
Hi Shawn, Nice work, thanks.
I have one question. Could we implement images gradient based energies into this framework. Could I do this by implementing the functions (yezzi energy for example) given in “energy3c.h”.
Thanks,
Eranga
@Eran
Absolutely you can use this framework to implement other energies!
In fact, I plan to release an energy3c.cpp soon with many well-known energies.
However, the Yezzi Energy: E = (u-v)^2
is a region-based energy. Caselles is a good example of an image-gradient-based energy.
Dear Shawn,
First of all allow me to thank you for your nice work. I am applying your MATLAB code based on active contoure without edges on my project.
Could you please say why you did not use the Dirace function in your MATLAB code?
Best Regards,
Farshad
@farshad. Instead of using a “smooth” dirac as described in the paper, I use a discrete approximation. Specifically,
d(0) = 1, and
d(anything else) = 0.
Dear Shawn,
I am very grateful to you for this code. It is great work. Could I use this active contour to drive based on image edge information as well. If so Could you please tell me which function to call.
Thanks a bunch..
Sen Gen
@sen You can definitely use the codes to perform edge-based segmentation, but you must write your the new energy in the energy3c.cpp file.
Hi Shawn,
First of all thanks for sharing your code. I’m using it to track migrating cells and it works great. However, it could be better for my application if the contour lines weren’t allowed to merge. Is there a way to modify your code so that contours lines can’t merge? Any advice/suggestions are greatly appreciated.
Thanks,
Monica
Hi Shawn,
I am very interested in sparse field Active Contour, and I want to do something with it. It all codes in the above files(Sparse Field Method – Matlab Demo [zip] ), If I want to do something ,Can I only write something new in energy3c.cpp or other file of C, then I create the DLL to replace the old DLL??
@Quinn All of the source is provided. You can feel free to modify any of the files to implement specific behaviors, but typically new energies can be implemented by modifying solely energy3c.cpp.
Shawn,
Have this question: I need to segment out a region surrounded by multiple shades of boundary. That would mean we need multiple uout (mean of exterior pixels intensity). Or is there a way to restrict uout to a localised region?How do I use your code?
I had the same thought! Please see this paper: Localizing Region-Based Active Contours (publications page). I hope to publish my codes for this soon.
Thank you very much for sharing with us, it is very good job!
Hi Shawn,
Thanks for sharing the Sparse Field Active Contours algo.
Since bulk of the algo is written in C++ and the .m files are only used as wrappers, I am trying to convert this algo as a standalone Windows application – i.e. trying to remove all the Matlab dependencies.
For this I’m plan on compiling the C++ code in VC++ 2008 and then convert all the Matlab .m files to C++ code.
However, when I compile the C++ code (energy3c.cpp, llist.cpp, lsops3c.cpp, and sfm_local_chanvese_mex.cpp) in VC++ 2008, the compiler gives an error where it reports a dependency on “matrix.h” – which is a Matlab header file. (used for “mxArray” in “Sparse3c.h”).
Would you know how to remove the dependency of “matrix.h” and other Matlab specific dependencies, so that one can compile and execute the entire algo as a stanadalone VC++ application?
Thanks again.
Rajeev
@Rajeev Thanks for your interest. There are several Matlab libraries used in the code. In general, Matlab MEX programs use the internal Matlab “Matrix” data-structures. You can easily strip these out and use simple data arrays. This is the underlying data-type in the data-structures in the “Matrix” element.
Thanks Shawn – appreciate your quick response.
I had wanted to know if there were any other dependencies other than the “Matrix” data structure (I haven’t looked exhaustively at the C++ code). From your response it seems there aren’t, which answers my question.
I’ll post the converted code soon.
Rajeev
Trying to run it. There is no “sfm_chanvese_demo” file. But that is not a real problem. I got an error about function “fat_contour”. Matlab can not find it =(
@fralik
Oh! Found it here http://www.mathworks.com/matlabcentral/fileexchange/26101-active-contours-a-new-distribution-metric-for-image-segmentation
Thanks Shawn,
Your code is good.The “localized_seg_demo.m” run well.I’m trying this now.
I have the same problem but already find the “fat_contour”.However,I have another problem at:??? Error using ==> delete Error in ==> visualize_phi at 6 delete(h1); I don’t know why the error is occur!
Thanks for your contributions.I am a new student in the domain of active contours.I study carefully of your code which implementing the paper”Active contours without edges”, and have a question:
In CV model, there has two parameters, lamda1 and lamda2, but in your code, you just replace it with “F./max(abs(F))”, why?
Best Regards!
@morris
Hi. Welcome to the field! In my implementation, I set lambda1=lambda2=0, but I use this F./max(abs(F)) factor is related to a weight CV refer to as mu. The idea is to weight the “image terms” so that they have a maximum value of 1. This allows the “intrinsic terms” to affect the shape of the curve on equal footing. (as a side note, CV also have a fourth term weighted by eta. I set eta to 0). Cheers!
@grace
I have the same problem with you.Try to do this:
%delete(h1);
%delete(h2);
Cheers!
j’ai un problem a l’evolution de l’equation
la fonction de dirac est tres petit
hello
i read localized_seg.zip
whose paper is this cod?
please say me its paper title
@hamid reza tajik
The paper is called “A level-set approach to 3D reconstruction from range data.” Get it here [pdf]
First of all allow me to thank you for your nice work and response me.
I read the papers with titles”A level-set approach to 3D reconstruction from range data” and “Active Contours Without Edges” and download the “regionbased_seg.zip” and read it.
but none of formules that are in this code,is not in this paper.
on the top of the this code be writen ” This code implements the paper: “Active Contours Without Edges”, is it true?
is this code for the paper”Active Contours Without Edges”?
if it is,please guide me more about the its implimentation.
i set the lambda1,2=0.,but …
is it true mu=F./max(abs(F))?
i read the paper “a level set approach for computing solutions to incompressible two phase flow” too and i undrestood some parts but i didnt undrestand line 46 to 63 of this code”region_seg.m”.
thanks and regards.
Hi Shawn,
Do you need a specific compiler to compile the mex file? I’m using MATLAB 2010 with Vista 32bit and the included lcc compiler, and i get an unsuccessful compilation with several errors.
Would really appreciate a quick response… thanks!
@Aki
Any compiler should work, though some are pickier than others. I originally wrote and tested the code on Linux (gcc), OSX (gcc), and Windows XP (MSVC++). The code works on those platforms/compilers.
Unfortunately, I don’t have Vista, so I can’t help you debug, but you should be able to track it down by following the error messages. The heart of the code should be relatively error-free. I’d hunt for something more high-level that’s causing the errors (such as referencing back and forth to Matlab, etc.).
If you find the error, let me know and I’ll try to re-post the correction.
After taking a (quick) look at the problematic parts of the code, I think the problem is that LCC is a C-compiler, and has problems with the placement of some of the variable declarations… does that sound about right to you?
@hamid reza tajik
region_seg.m is rather old and has some errors. Look through the comments on this page for an explanation of why I divide F by it’s maximum and notes about other formulae used
The paper “A level set approach for computing solutions to incompressible two phase flow” outlines the sparse field method. The codes here use the sparse field method to implement the segmentation energy presented in “Active contours without edges.”
@Aki
You should definitely be using a C++ compiler. Although the code doesn’t make use of objects, it uses many C++ syntax conventions.
Hi,
I installed WATCOM C++ 1.8 and it compiled without any issues. I did have to download fat_contour.m separately as it doesn’t seem to be included in your zip file.
A small change I had to make to fat_contour.m, because of the introduction of the ~ symbol to handle unused output arguments (in 2009b onwards), was to rewrite
h1 = contour(phi,[0 0],c1,’linewidth’,t1,’linestyle’,'–’);
etc. as
[~,h1] = contour(phi,[0 0],c1,’linewidth’,t1,’linestyle’,'–’);
Thought I would mention it here… thanks for your help!
@Aki
Great! I’m glad you got it working, and thanks for the tip on fat_contour. I’ll try to update that and include it in the zip file.
A gaff in my last post… of course the ~ notation is not recognised in matlab versions prior to 2009b, so obviously to maintain compatibility in both directions
[dummy, h1] = contour(phi,[0 0],c1,’linewidth’,t1,’linestyle’,’–’);
but of course, you know that
Hi Shawn,
Thanks very much for sharing your code! I’ve been tinkering with your Sparse Field Method program. Just wondering why I get slightly different results running the method for example 10 times with 1000 iterations (using each previous time as the new initialisation) rather than 1 time with 10000 iterations? Struggling to get to grips with the maths but does a new initialisation change part of the energy minimisation equation? Any help would be greatly appreciated!
- Ian