[PCL self study: segmentation4] point cloud segmentation based on Min cut

One 、 be based on Min-Cut Point cloud segmentation for

   In this section , We will learn how to use in pcl::MinCutSegmentation Class based on min-cut Segmentation algorithm . The algorithm performs binary segmentation for a given input point cloud . According to the center of the object and its radius , The algorithm divides the cloud into two groups : Front attractions and background points ( Points belonging to the object and points not belonging to the object ).

Two 、Min-Cut Principle analysis

   The idea of this algorithm needs the knowledge of graph theory , as follows ：
  1. For a given point cloud algorithm , It constructs a graph , It contains every point in the cloud as a set of vertices , And two other vertices called source and sink . Each vertex corresponding to this point in the graph is connected to the source , Connect and converge with the edge . besides , Each vertex ( Except source and sink ) All have edges that connect the corresponding point to its nearest neighbor .
  2. The algorithm assigns weights to each edge . There are three different types of weights . Let's look at
① First , It gives weight to the edges between the point clouds . This weight is called smoothing cost , Calculate by formula

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

   there dist Is the distance between points . The farther away the point , The greater the probability that the edge will be cut .

② next step , Algorithm setting data overhead . It consists of foreground penalty and background penalty . The first is the weights of the edges that connect the point cloud to the source vertex , These edges have user-defined constant values . The second edge assigned to the connection point and the convergence vertex , And calculated by the formula

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

   there distanceToCenter Is the distance between the object and the desired center in the horizontal plane

      $distanceToCenter=\sqrt{(x-centerX{)}^2+(y-centerY{)}^2}$
   The radius appearing in the formula is the input parameter of the algorithm , It can be roughly regarded as the range of points outside the center of the object that do not belong to the foreground ( The horizontal radius of an object ).
  3. After all the preparations have been completed , Look for the smallest cut . On this basis , Divide the front scenic spots and background points of the cloud .
The specific principle can be understood by referring to this paper . “Min-Cut Based Segmentation of Point Clouds”.

It should be noted that ： The effect of this method is not as good as that described in the paper , And the parameters have been compared . Suitable for learning ideas , Not suitable for direct use .

3、 ... and 、 Sample code

#include <iostream>
#include <vector>
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/filters/filter_indices.h> // for pcl::removeNaNFromPointCloud
#include <pcl/segmentation/min_cut_segmentation.h>

int main ()
{
    
//  load pcd Point cloud in file 
  pcl::PointCloud <pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud <pcl::PointXYZ>);
  if ( pcl::io::loadPCDFile <pcl::PointXYZ> ("min_cut_segmentation_tutorial.pcd", *cloud) == -1 )
  {
    
    std::cout << "Cloud reading failed." << std::endl;
    return (-1);
  }
//  Select a valid point to split 
  pcl::IndicesPtr indices (new std::vector <int>);
  pcl::removeNaNFromPointCloud(*cloud, *indices);
// pcl::MinCutSegmentation The template class has only one parameter PointT, This parameter indicates which type of point will be used .
  pcl::MinCutSegmentation<pcl::PointXYZ> seg;
  seg.setInputCloud (cloud);
  seg.setIndices (indices);
//  Provide the necessary segmentation in the point cloud for the algorithm d Point and index of 
  pcl::PointCloud<pcl::PointXYZ>::Ptr foreground_points(new pcl::PointCloud<pcl::PointXYZ> ());
  pcl::PointXYZ point;
  point.x = 68.97;
  point.y = -18.55;
  point.z = 0.57;
  foreground_points->points.push_back(point);
  seg.setForegroundPoints (foreground_points);
//  As mentioned earlier , The algorithm requires that the point known as the center of the object .
  seg.setSigma (0.25);
  seg.setRadius (3.0433856);
  seg.setNumberOfNeighbours (14);
  seg.setSourceWeight (0.8);

//  Classify the divided points 
  std::vector <pcl::PointIndices> clusters;
  seg.extract (clusters);

  std::cout << "Maximum flow is " << seg.getMaxFlow () << std::endl;

//  Show point cloud 
  pcl::PointCloud <pcl::PointXYZRGB>::Ptr colored_cloud = seg.getColoredCloud ();
  pcl::visualization::CloudViewer viewer ("Cluster viewer");
  viewer.showCloud(colored_cloud);
  while (!viewer.wasStopped ())
  {
    
  }

  return (0);
}

The segmentation effect is as follows ：

The elder's This article The algorithm is tried , The results show that the algorithm is not effective .

---

【 About bloggers 】
   Stanford rabbit , male , Master of engineering, Tianjin University . Since graduation, I have been engaged in optical three-dimensional imaging and point cloud processing . Because the three-dimensional processing library used in work is the internal library of the company , Not universally applicable , So I learned to open source by myself PCL Library and its related mathematical knowledge for use . I would like to share the self-study process with you .
Bloggers lack of talent and knowledge , Not yet able to guide , If you have any questions, please leave a message in the comments section for everyone to discuss .