My GSoC project this year is Graph based segmentation algorithms using region adjacency graphs. Community binding period is coming to an end. I have experimented a bit with Region Adjacency Graphs (RAGs) and Minimum Spanning Trees (MSTs) with this ugly piece of Python code. I will try to describe in brief what I plan to do during this GSoC period.
Region Adjacency Graphs
Certain image segmentation algorithms have a tendency to over segment an image. They divide a region as perceived by humans into two or more regions. This is because they tend to favor small regions of similar color. But in the real world one object might have different shades of the same color or different colors all together. Here is an example using SLIC. In broad terms SLIC is k-means done on (X,Y, Z ) color space
We consider each of these regions as a vertex in a graph. Each region is connected to all the regions that touch it. Similar regions are joined with an edge of less weight. Dissimilar regions are joined with edges oh high weight. One measure of dissimilarity might be difference in the mean color. See the below example.
Processing The Region Adjacency Graphs
If we remove the edges with higher weights in an appropriate manner, the regions remaining connected would belong to the same object. Thus in this case the face, the hat, the hair might be finally one connected subgraph of regions. Over the next two weeks I will try to take an over segmented image and build its RAG. As a proof of concept of the underlying data structures and algorithms I will apply a threshold and remove the edges with weights higher than it. Later on I will move onto to more complicated selection procedures including N-cut and if my MST experiments yield good results an MST based procedure.
A Simple Programmer's Blog 
3 thoughts on “Graph based Image Segmentation”