Shawn Lankton Online
Archive for March, 2008
03 10th, 2008
I’ve been living in Atlanta for years and years now, and the city holds a special place in my heart. I went out yesterday to take some pictures in my neighborhood, the “No-No” district. This is the area just North of North Ave. on the South side of Midtown. “No-No” is my little joke since my hood is just North of the area city marketeers are now referring to as “So-No” (South of North). Atlanta is starting to feel more like London and New York already!
Enjoy, and let me know what you think!
03 8th, 2008
Matlab is a great programming language/environment because of its ease of use, great visualization, and rapid prototyping abilities. Raw speed is not one of its strong suits. MEX (Matlab Executables) are the answer. These functions allow you to program in C or C++ (ultra fast languages), but be able to call and use them from Matlab programs. This post is a short intro to mex files which should get you up and running.
What This Post Teaches
In this post, I show how to create a mex file, how to set up inputs and outputs, how to get access to Matlab objects, and how to manipulate them. I also give a skeleton mex program that might be helpful. There is a lot more to learn, and I’d refer you to the mex manual regardless.
03 6th, 2008
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.
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
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:
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).
Based on this simple initialization, we obtain a very decent segmentation:
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.
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 made a bug-fix thanks to a note from a reader, Lin. The code works much better now!
Please let me know if you find this useful, and if you make improvements! Also, if you’re interested in segmentation, check out these other algorithms:
Mean-Shift Image Segmentation
Localized Active Contours
Classic “Chan-Vese” Active Contours
