Point Cloud Library (PCL)  1.11.1
min_cut_segmentation.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  *
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above
15  * copyright notice, this list of conditions and the following
16  * disclaimer in the documentation and/or other materials provided
17  * with the distribution.
18  * * Neither the name of the copyright holder(s) nor the names of its
19  * contributors may be used to endorse or promote products derived
20  * from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * $Id:$
36  *
37  */
38 
39 #pragma once
40 
41 #include <pcl/segmentation/boost.h>
42 #include <pcl/memory.h>
43 #include <pcl/pcl_base.h>
44 #include <pcl/pcl_macros.h>
45 #include <pcl/point_cloud.h>
46 #include <pcl/point_types.h>
47 #include <pcl/search/search.h>
48 #include <string>
49 #include <set>
50 
51 namespace pcl
52 {
53  /** \brief This class implements the segmentation algorithm based on minimal cut of the graph.
54  * The description can be found in the article:
55  * "Min-Cut Based Segmentation of Point Clouds"
56  * \author: Aleksey Golovinskiy and Thomas Funkhouser.
57  */
58  template <typename PointT>
60  {
61  public:
62 
64  using KdTreePtr = typename KdTree::Ptr;
67 
72 
73  public:
74 
75  using Traits = boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::directedS >;
76 
77  using mGraph = boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS,
78  boost::property< boost::vertex_name_t, std::string,
79  boost::property< boost::vertex_index_t, long,
80  boost::property< boost::vertex_color_t, boost::default_color_type,
81  boost::property< boost::vertex_distance_t, long,
82  boost::property< boost::vertex_predecessor_t, Traits::edge_descriptor > > > > >,
83  boost::property< boost::edge_capacity_t, double,
84  boost::property< boost::edge_residual_capacity_t, double,
85  boost::property< boost::edge_reverse_t, Traits::edge_descriptor > > > >;
86 
87  using CapacityMap = boost::property_map< mGraph, boost::edge_capacity_t >::type;
88 
89  using ReverseEdgeMap = boost::property_map< mGraph, boost::edge_reverse_t>::type;
90 
91  using VertexDescriptor = Traits::vertex_descriptor;
92 
93  using EdgeDescriptor = boost::graph_traits<mGraph>::edge_descriptor;
94 
95  using OutEdgeIterator = boost::graph_traits<mGraph>::out_edge_iterator;
96 
97  using VertexIterator = boost::graph_traits<mGraph>::vertex_iterator;
98 
99  using ResidualCapacityMap = boost::property_map< mGraph, boost::edge_residual_capacity_t >::type;
100 
101  using IndexMap = boost::property_map< mGraph, boost::vertex_index_t >::type;
102 
103  using InEdgeIterator = boost::graph_traits<mGraph>::in_edge_iterator;
104 
105  using mGraphPtr = shared_ptr<mGraph>;
106 
107  public:
108 
109  /** \brief Constructor that sets default values for member variables. */
111 
112  /** \brief Destructor that frees memory. */
113 
114  ~MinCutSegmentation ();
115 
116  /** \brief This method simply sets the input point cloud.
117  * \param[in] cloud the const boost shared pointer to a PointCloud
118  */
119  void
120  setInputCloud (const PointCloudConstPtr &cloud) override;
121 
122  /** \brief Returns normalization value for binary potentials. For more information see the article. */
123  double
124  getSigma () const;
125 
126  /** \brief Allows to set the normalization value for the binary potentials as described in the article.
127  * \param[in] sigma new normalization value
128  */
129  void
130  setSigma (double sigma);
131 
132  /** \brief Returns radius to the background. */
133  double
134  getRadius () const;
135 
136  /** \brief Allows to set the radius to the background.
137  * \param[in] radius new radius to the background
138  */
139  void
140  setRadius (double radius);
141 
142  /** \brief Returns weight that every edge from the source point has. */
143  double
144  getSourceWeight () const;
145 
146  /** \brief Allows to set weight for source edges. Every edge that comes from the source point will have that weight.
147  * \param[in] weight new weight
148  */
149  void
150  setSourceWeight (double weight);
151 
152  /** \brief Returns search method that is used for finding KNN.
153  * The graph is build such way that it contains the edges that connect point and its KNN.
154  */
155  KdTreePtr
156  getSearchMethod () const;
157 
158  /** \brief Allows to set search method for finding KNN.
159  * The graph is build such way that it contains the edges that connect point and its KNN.
160  * \param[in] tree search method that will be used for finding KNN.
161  */
162  void
163  setSearchMethod (const KdTreePtr& tree);
164 
165  /** \brief Returns the number of neighbours to find. */
166  unsigned int
167  getNumberOfNeighbours () const;
168 
169  /** \brief Allows to set the number of neighbours to find.
170  * \param[in] neighbour_number new number of neighbours
171  */
172  void
173  setNumberOfNeighbours (unsigned int neighbour_number);
174 
175  /** \brief Returns the points that must belong to foreground. */
176  std::vector<PointT, Eigen::aligned_allocator<PointT> >
177  getForegroundPoints () const;
178 
179  /** \brief Allows to specify points which are known to be the points of the object.
180  * \param[in] foreground_points point cloud that contains foreground points. At least one point must be specified.
181  */
182  void
183  setForegroundPoints (typename pcl::PointCloud<PointT>::Ptr foreground_points);
184 
185  /** \brief Returns the points that must belong to background. */
186  std::vector<PointT, Eigen::aligned_allocator<PointT> >
187  getBackgroundPoints () const;
188 
189  /** \brief Allows to specify points which are known to be the points of the background.
190  * \param[in] background_points point cloud that contains background points.
191  */
192  void
193  setBackgroundPoints (typename pcl::PointCloud<PointT>::Ptr background_points);
194 
195  /** \brief This method launches the segmentation algorithm and returns the clusters that were
196  * obtained during the segmentation. The indices of points that belong to the object will be stored
197  * in the cluster with index 1, other indices will be stored in the cluster with index 0.
198  * \param[out] clusters clusters that were obtained. Each cluster is an array of point indices.
199  */
200  void
201  extract (std::vector <pcl::PointIndices>& clusters);
202 
203  /** \brief Returns that flow value that was calculated during the segmentation. */
204  double
205  getMaxFlow () const;
206 
207  /** \brief Returns the graph that was build for finding the minimum cut. */
208  mGraphPtr
209  getGraph () const;
210 
211  /** \brief Returns the colored cloud. Points that belong to the object have the same color. */
213  getColoredCloud ();
214 
215  protected:
216 
217  /** \brief This method simply builds the graph that will be used during the segmentation. */
218  bool
219  buildGraph ();
220 
221  /** \brief Returns unary potential(data cost) for the given point index.
222  * In other words it calculates weights for (source, point) and (point, sink) edges.
223  * \param[in] point index of the point for which weights will be calculated
224  * \param[out] source_weight calculated weight for the (source, point) edge
225  * \param[out] sink_weight calculated weight for the (point, sink) edge
226  */
227  void
228  calculateUnaryPotential (int point, double& source_weight, double& sink_weight) const;
229 
230  /** \brief This method simply adds the edge from the source point to the target point with a given weight.
231  * \param[in] source index of the source point of the edge
232  * \param[in] target index of the target point of the edge
233  * \param[in] weight weight that will be assigned to the (source, target) edge
234  */
235  bool
236  addEdge (int source, int target, double weight);
237 
238  /** \brief Returns the binary potential(smooth cost) for the given indices of points.
239  * In other words it returns weight that must be assigned to the edge from source to target point.
240  * \param[in] source index of the source point of the edge
241  * \param[in] target index of the target point of the edge
242  */
243  double
244  calculateBinaryPotential (int source, int target) const;
245 
246  /** \brief This method recalculates unary potentials(data cost) if some changes were made, instead of creating new graph. */
247  bool
248  recalculateUnaryPotentials ();
249 
250  /** \brief This method recalculates binary potentials(smooth cost) if some changes were made, instead of creating new graph. */
251  bool
252  recalculateBinaryPotentials ();
253 
254  /** \brief This method analyzes the residual network and assigns a label to every point in the cloud.
255  * \param[in] residual_capacity residual network that was obtained during the segmentation
256  */
257  void
258  assembleLabels (ResidualCapacityMap& residual_capacity);
259 
260  protected:
261 
262  /** \brief Stores the sigma coefficient. It is used for finding smooth costs. More information can be found in the article. */
264 
265  /** \brief Signalizes if the binary potentials are valid. */
267 
268  /** \brief Used for comparison of the floating point numbers. */
269  double epsilon_;
270 
271  /** \brief Stores the distance to the background. */
272  double radius_;
273 
274  /** \brief Signalizes if the unary potentials are valid. */
276 
277  /** \brief Stores the weight for every edge that comes from source point. */
279 
280  /** \brief Stores the search method that will be used for finding K nearest neighbors. Neighbours are used for building the graph. */
282 
283  /** \brief Stores the number of neighbors to find. */
284  unsigned int number_of_neighbours_;
285 
286  /** \brief Signalizes if the graph is valid. */
288 
289  /** \brief Stores the points that are known to be in the foreground. */
290  std::vector<PointT, Eigen::aligned_allocator<PointT> > foreground_points_;
291 
292  /** \brief Stores the points that are known to be in the background. */
293  std::vector<PointT, Eigen::aligned_allocator<PointT> > background_points_;
294 
295  /** \brief After the segmentation it will contain the segments. */
296  std::vector <pcl::PointIndices> clusters_;
297 
298  /** \brief Stores the graph for finding the maximum flow. */
300 
301  /** \brief Stores the capacity of every edge in the graph. */
302  std::shared_ptr<CapacityMap> capacity_;
303 
304  /** \brief Stores reverse edges for every edge in the graph. */
305  std::shared_ptr<ReverseEdgeMap> reverse_edges_;
306 
307  /** \brief Stores the vertices of the graph. */
308  std::vector< VertexDescriptor > vertices_;
309 
310  /** \brief Stores the information about the edges that were added to the graph. It is used to avoid the duplicate edges. */
311  std::vector< std::set<int> > edge_marker_;
312 
313  /** \brief Stores the vertex that serves as source. */
315 
316  /** \brief Stores the vertex that serves as sink. */
318 
319  /** \brief Stores the maximum flow value that was calculated during the segmentation. */
320  double max_flow_;
321 
322  public:
324  };
325 }
326 
327 #ifdef PCL_NO_PRECOMPILE
328 #include <pcl/segmentation/impl/min_cut_segmentation.hpp>
329 #endif
typename KdTree::Ptr KdTreePtr
shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:429
Defines functions, macros and traits for allocating and using memory.
KdTreePtr search_
Stores the search method that will be used for finding K nearest neighbors.
bool unary_potentials_are_valid_
Signalizes if the unary potentials are valid.
boost::graph_traits< mGraph >::out_edge_iterator OutEdgeIterator
std::vector< std::set< int > > edge_marker_
Stores the information about the edges that were added to the graph.
boost::property_map< mGraph, boost::edge_capacity_t >::type CapacityMap
double radius_
Stores the distance to the background.
boost::graph_traits< mGraph >::edge_descriptor EdgeDescriptor
unsigned int number_of_neighbours_
Stores the number of neighbors to find.
std::vector< PointT, Eigen::aligned_allocator< PointT > > foreground_points_
Stores the points that are known to be in the foreground.
boost::graph_traits< mGraph >::in_edge_iterator InEdgeIterator
Traits::vertex_descriptor VertexDescriptor
#define PCL_MAKE_ALIGNED_OPERATOR_NEW
Macro to signal a class requires a custom allocator.
Definition: memory.h:63
VertexDescriptor sink_
Stores the vertex that serves as sink.
shared_ptr< KdTree< PointT > > Ptr
Definition: kdtree.h:70
shared_ptr< mGraph > mGraphPtr
double epsilon_
Used for comparison of the floating point numbers.
std::vector< pcl::PointIndices > clusters_
After the segmentation it will contain the segments.
This class implements the segmentation algorithm based on minimal cut of the graph.
Defines all the PCL implemented PointT point type structures.
mGraphPtr graph_
Stores the graph for finding the maximum flow.
boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::directedS > Traits
PCL base class.
Definition: pcl_base.h:72
bool binary_potentials_are_valid_
Signalizes if the binary potentials are valid.
boost::property_map< mGraph, boost::edge_reverse_t >::type ReverseEdgeMap
boost::property_map< mGraph, boost::edge_residual_capacity_t >::type ResidualCapacityMap
std::vector< VertexDescriptor > vertices_
Stores the vertices of the graph.
PointCloud represents the base class in PCL for storing collections of 3D points. ...
Definition: distances.h:55
bool graph_is_valid_
Signalizes if the graph is valid.
std::vector< PointT, Eigen::aligned_allocator< PointT > > background_points_
Stores the points that are known to be in the background.
boost::property_map< mGraph, boost::vertex_index_t >::type IndexMap
VertexDescriptor source_
Stores the vertex that serves as source.
boost::graph_traits< mGraph >::vertex_iterator VertexIterator
shared_ptr< const PointCloud< PointT > > ConstPtr
Definition: point_cloud.h:430
double inverse_sigma_
Stores the sigma coefficient.
std::shared_ptr< ReverseEdgeMap > reverse_edges_
Stores reverse edges for every edge in the graph.
std::shared_ptr< CapacityMap > capacity_
Stores the capacity of every edge in the graph.
boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, boost::property< boost::vertex_name_t, std::string, boost::property< boost::vertex_index_t, long, boost::property< boost::vertex_color_t, boost::default_color_type, boost::property< boost::vertex_distance_t, long, boost::property< boost::vertex_predecessor_t, Traits::edge_descriptor > > > > >, boost::property< boost::edge_capacity_t, double, boost::property< boost::edge_residual_capacity_t, double, boost::property< boost::edge_reverse_t, Traits::edge_descriptor > > > > mGraph
#define PCL_EXPORTS
Definition: pcl_macros.h:328
double max_flow_
Stores the maximum flow value that was calculated during the segmentation.
Defines all the PCL and non-PCL macros used.
double source_weight_
Stores the weight for every edge that comes from source point.
typename PointCloud::ConstPtr PointCloudConstPtr
Definition: pcl_base.h:77
Generic search class.
Definition: search.h:74