Min-Cut-PCL-Cpp (50%)

Min-Cut Based Segmentation

Aleksey Golovinskiy, Thomas Funkhouser, Min-Cut Based Segmentation of Point Clouds, ICCV 2009

In this tutorial we will learn how to use the min-cut based segmentation algorithm implemented in the pcl::MinCutSegmentation class.

This algorithm makes a binary segmentation of the given input cloud.

Having objects center and its radius the algorithm divides the cloud on two sets:

• foreground

• background points

• (points that belong to the object and those that do not belong).

Theoretical Primer

The idea of this algorithm is as follows:

1. For the given point cloud algorithm constructs the graph that contains every single point of the cloud as a set of vertices and two more vertices called source and sink.

• Every vertex of the graph that corresponds to the point is connected with source and sink with the edges.

• In addition to these, every vertex (except source and sink) has edges that connect the corresponding point with its nearest neighbours.

2. Algorithm assigns weights for every edge. There are three different types of weight. Let’s examine them:

First of all it assigns weight to the edges between clouds points. This weight is called smooth cost and is calculated by the formula:

smoothCost=e^{-(\frac{dist}{ \sigma })^2}

• Here dist is the distance between points. The farther away the points are, the more is probability that the edge will be cut.

Next step the algorithm sets data cost.

• It consists of foreground and background penalties.

• The first one is the weight for those edges that connect clouds points with the source vertex and has the constant user-defined value.

• The second one is assigned to the edges that connect points with the sink vertex and is calculated by the formula:

backgroundPenalty=(\frac{distanceToCenter}{radius})

• Here distanceToCenter is the distance to the expected center of the object in the horizontal plane:

distanceToCenter=\sqrt{(x-centerX)^2+(y-centerY)^2}

Radius that occurs in the formula is the input parameter for this algorithm and can be roughly considered as the range from objects center outside of which there are no points that belong to foreground (objects horizontal radius).

3. After all the preparations the search of the minimum cut is made. Based on an analysis of this cut, cloud is divided on foreground and background points.