PCL Developers blog

Alexander Velizhev and Sergey Ushakov

project:Automated feature extraction
mentor:Alexander Velizhev

About me

My name is Sergey and this page is about me, my mentor Alexander and the project on which I intend to work. I’m a student at the Lomonosov Moscow State University. I’m engaged in object segmentation in 3D point clouds. In addition, I’m fond of casual game development and all that is relevant to computer graphics. I was fortunate to become a participant of the TRCS, within which the growing region algorithm will be embeded. I am also going to implement the object segmentation algorithm based on graphcut(for more details see below). During my work, I will cover here every stage of development and share with you my success, failure and experience.


First of all I’m going to implement:

Then I’m going to implement a graphcut based object segmentation(as described in “Min-Cut Based Segmentation of Point Clouds”). In short the idea is following:

  • to construct a graph from points
  • to segment object/background points for a given possible rough object center by energy minimization

Recent status updates

Code for Min Cut Segmentation
Friday, May 11, 2012

Hi everybody. I have committed the code for min cut segmentation. At the moment only basic functionality can be used. I wanted to make a generalization for adding points that are known to be points of the background. Right now this option is turned off. It works fine but I just wanted to run more tests for this functionality.

So my next step will be to test this option. After that I will start to write tutorials for the code that I’ve added(RegionGrowing, RegionGrowingRGB, MinCutSegmentation). Exams are nearing so I will pay less time for working on the TRCS. But this is temporary. I hope that I will finish additional functionality, that I mentioned, before the beginning of the exams.

More results of segmentation
Wednesday, May 02, 2012

Hi everybody. I have ran some tests and results are terrific. The algorithm works well even for very noisy point clouds. Here are some results:

There were some problems with the min cut algorithm. The best known is the algorithm proposed by Yuri Boykov, Olga Veksler and Ramin Zabih(based on their article “Fast Approximate Energy Minimization via Graph Cuts”). But it has some license constraints. So I used it only for testing at the beginning of the work. My code is using boykov_kolmogorov_max_flow algorithm from boost graph library. At the beginning I tried to use push_relabel_max_flow from BGL but it works a little bit strange. For the same unary and binary potentials(data and smooth costs) push_relabel_max_flow gives worse results then boykov_kolmogorov_max_flow does. So I’ve decided to give preference to the last one.

Right now I’m going to make some last changes in the code to fit the adopted rules.

Forgot to tell there are some problems with Online 3D point cloud viewer. I have already wrote about it to the authors. The problem appears only in Mozilla Firefox, it works fine with Google Chrome. So I hope everybody is able to see my point clouds.

Debugging and varying weights
Tuesday, April 24, 2012

Hi everybody. I have finally finished the work on the code for min cut segmentation. It took so long because of some bugs. The simplest mistakes are always hard to find. Any way. the code is ready and I even have some results of segmentation. The algorithm requires point clouds with cutted floor planes etc. So first of all I have deleted the floor plane. You can see the result in the point cloud viewer.

Right now I am trying to find the best unary and binary potentials(edge weights), because those that were mentioned in the article are not good enough. I hope that at the end of this week I wil be able to find them and upload the resulting code.

BGL usage
Friday, April 06, 2012

Finally! I have figured out how to use the push_ralabel_max_flow. Documentation of the BGL is not the best(ordinary users won’t understand how all this works). But I have managed to launch a few simple examples and it looks great.

So right now I will change the code a little so that it would work with the real point clouds. It won’t take much time so I hope that in a few days I will be able to post some results of the segmentation using PCL web viewer.

Min-Cut Segmentation
Monday, April 02, 2012

Hi everybody. I have wrote the code for building the graph. Right now it uses triangulation algorithm from PCL. But I intend to write my own code for this later, because triangulation from PCL requires normals and their calculation can slow down the graph building. My variant will simply find K nearest points and add edges between initial point and its neighbours, as suggested in the article. Constructing the graph this way can cause existance of several connected components. But this problem can be solved easily by connecting points from different components with the edge.

Right now I am inspecting Boost Graph Library for the necessary algorithms. I have found several algorithms for finding the maximum flow in the graph, but I think that I will use push_relabel_max_flow algorithm because it is the fastest one. I have never used BGL algorithms for finding maximum flow, so right now I am trying to run some simple examples for small graphs.

One more important thing is that we have decided to generalize the algorithm. It will allow user to specify points that belong to backrgound/object. Not only one point that belongs to object as said in the base algorithm. The idea is based on the interactive application that was described in the artcile.