PlanarGC  1.0.2
 All Data Structures Functions Variables Enumerations Enumerator Friends Pages
Tutorial: CutSegment

CutSegment finds a minimal cut in an image where every image pixel represents a graph vertex. We assume a 4-connected grid (cf. CutGrid) and that the capacity of an edge only depends on the image information at the two linked pixels.

photo.PNG
Example of an image 'I'
photoSel.PNG
Example of a preselected source and sink set 'L'

In order to compute the cut, the following steps have to be performed:

  1. Define the gradient dependent capacity.
  2. Compute the maximum flow with respect to a connected source and sink set.
  3. Extract the minimal cut as a pixel-based representation.

In the following sections, we explain these steps with respect to the graph sketched in the images above.

Gradient Dependent Capacity

When we define the capacity of each edge, we can either do this by using the GAC approach already implemented or by overwriting the CutSegment::gradient(double,double) method. In this example we follow the latter approach:

class MyCutSegment : public CutSegment {
public:
MyCutSegment(int width, int height) : CutSegment(width,height) {};
double gradient(double color1, double color2);
};
double MyCutSegment::gradient(double color1, double color2) {
double diff, weight;
diff = color1-color2;
weight = exp(-sqrt(diff*diff));
return weight;
}

If you also want to handle color images correctly, you should also overwrite the CutSegment::gradient(double[3],double[3]) method.

Maximum Flow

Now, we have to compute the maximum flow. In order to do this via the newly defined MyCutSegment, we have to load the image and the preselected source and sink set into MyCutSegment:

int width=128, height=128; // width and height of the variable I and L
MyCutSegment segment_cut(width,height);
segment_cut.setImageData(I); // load image I
segment_cut.setSourceSink(L,0,128); // define source and sink via L

We assumed here, that the image is already loaded row-wise in the variable I. In L, a pre-labeling is stored row-wise where the value '0' indicates the pre-selected source set an '128' the pre-selected sink-set. Both areas have to form connected components within L. Otherwise, only one component is considered.

Now that the problem is formulated, we have to compute the value of the maximum flow. This is the most time consuming method of the class and is called via

double flow;
flow = segment_cut.segment();

Minimal Cut

For most applications, we are not only interested in the value of the minimum cut, but also in the segmentation itself. The classical way in describing this is to assign a binary labeling to each pixel. This labeling can be provided via CutSegment::getLabel or CutSegment::getLabels

label = segment_cut.getLabel(1,2); // returns 'CutPlanar::LABEL_SINK'
labels = new CutPlanar::ELabel[width*height];
segment_cut.getLabels(labels);

The complete code can be seen here: cutsegment.cpp.

© 2009 - 2013 by Eno Töppe, Frank R. Schmidt
generated by Doxygen