Point Cloud Library (PCL)  1.10.0
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/pcl_base.h>
43 #include <pcl/pcl_macros.h>
44 #include <pcl/point_cloud.h>
45 #include <pcl/point_types.h>
46 #include <pcl/search/search.h>
47 #include <string>
48 #include <set>
49 
50 namespace pcl
51 {
52  /** \brief This class implements the segmentation algorithm based on minimal cut of the graph.
53  * The description can be found in the article:
54  * "Min-Cut Based Segmentation of Point Clouds"
55  * \author: Aleksey Golovinskiy and Thomas Funkhouser.
56  */
57  template <typename PointT>
59  {
60  public:
61 
63  using KdTreePtr = typename KdTree::Ptr;
66 
71 
72  public:
73 
74  using Traits = boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::directedS >;
75 
76  using mGraph = boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS,
77  boost::property< boost::vertex_name_t, std::string,
78  boost::property< boost::vertex_index_t, long,
79  boost::property< boost::vertex_color_t, boost::default_color_type,
80  boost::property< boost::vertex_distance_t, long,
81  boost::property< boost::vertex_predecessor_t, Traits::edge_descriptor > > > > >,
82  boost::property< boost::edge_capacity_t, double,
83  boost::property< boost::edge_residual_capacity_t, double,
84  boost::property< boost::edge_reverse_t, Traits::edge_descriptor > > > >;
85 
86  using CapacityMap = boost::property_map< mGraph, boost::edge_capacity_t >::type;
87 
88  using ReverseEdgeMap = boost::property_map< mGraph, boost::edge_reverse_t>::type;
89 
90  using VertexDescriptor = Traits::vertex_descriptor;
91 
92  using EdgeDescriptor = boost::graph_traits<mGraph>::edge_descriptor;
93 
94  using OutEdgeIterator = boost::graph_traits<mGraph>::out_edge_iterator;
95 
96  using VertexIterator = boost::graph_traits<mGraph>::vertex_iterator;
97 
98  using ResidualCapacityMap = boost::property_map< mGraph, boost::edge_residual_capacity_t >::type;
99 
100  using IndexMap = boost::property_map< mGraph, boost::vertex_index_t >::type;
101 
102  using InEdgeIterator = boost::graph_traits<mGraph>::in_edge_iterator;
103 
105 
106  public:
107 
108  /** \brief Constructor that sets default values for member variables. */
110 
111  /** \brief Destructor that frees memory. */
112 
113  ~MinCutSegmentation ();
114 
115  /** \brief This method simply sets the input point cloud.
116  * \param[in] cloud the const boost shared pointer to a PointCloud
117  */
118  void
119  setInputCloud (const PointCloudConstPtr &cloud) override;
120 
121  /** \brief Returns normalization value for binary potentials. For more information see the article. */
122  double
123  getSigma () const;
124 
125  /** \brief Allows to set the normalization value for the binary potentials as described in the article.
126  * \param[in] sigma new normalization value
127  */
128  void
129  setSigma (double sigma);
130 
131  /** \brief Returns radius to the background. */
132  double
133  getRadius () const;
134 
135  /** \brief Allows to set the radius to the background.
136  * \param[in] radius new radius to the background
137  */
138  void
139  setRadius (double radius);
140 
141  /** \brief Returns weight that every edge from the source point has. */
142  double
143  getSourceWeight () const;
144 
145  /** \brief Allows to set weight for source edges. Every edge that comes from the source point will have that weight.
146  * \param[in] weight new weight
147  */
148  void
149  setSourceWeight (double weight);
150 
151  /** \brief Returns search method that is used for finding KNN.
152  * The graph is build such way that it contains the edges that connect point and its KNN.
153  */
154  KdTreePtr
155  getSearchMethod () const;
156 
157  /** \brief Allows to set search method for finding KNN.
158  * The graph is build such way that it contains the edges that connect point and its KNN.
159  * \param[in] search search method that will be used for finding KNN.
160  */
161  void
162  setSearchMethod (const KdTreePtr& tree);
163 
164  /** \brief Returns the number of neighbours to find. */
165  unsigned int
166  getNumberOfNeighbours () const;
167 
168  /** \brief Allows to set the number of neighbours to find.
169  * \param[in] number_of_neighbours new number of neighbours
170  */
171  void
172  setNumberOfNeighbours (unsigned int neighbour_number);
173 
174  /** \brief Returns the points that must belong to foreground. */
175  std::vector<PointT, Eigen::aligned_allocator<PointT> >
176  getForegroundPoints () const;
177 
178  /** \brief Allows to specify points which are known to be the points of the object.
179  * \param[in] foreground_points point cloud that contains foreground points. At least one point must be specified.
180  */
181  void
182  setForegroundPoints (typename pcl::PointCloud<PointT>::Ptr foreground_points);
183 
184  /** \brief Returns the points that must belong to background. */
185  std::vector<PointT, Eigen::aligned_allocator<PointT> >
186  getBackgroundPoints () const;
187 
188  /** \brief Allows to specify points which are known to be the points of the background.
189  * \param[in] background_points point cloud that contains background points.
190  */
191  void
192  setBackgroundPoints (typename pcl::PointCloud<PointT>::Ptr background_points);
193 
194  /** \brief This method launches the segmentation algorithm and returns the clusters that were
195  * obtained during the segmentation. The indices of points that belong to the object will be stored
196  * in the cluster with index 1, other indices will be stored in the cluster with index 0.
197  * \param[out] clusters clusters that were obtained. Each cluster is an array of point indices.
198  */
199  void
200  extract (std::vector <pcl::PointIndices>& clusters);
201 
202  /** \brief Returns that flow value that was calculated during the segmentation. */
203  double
204  getMaxFlow () const;
205 
206  /** \brief Returns the graph that was build for finding the minimum cut. */
207  mGraphPtr
208  getGraph () const;
209 
210  /** \brief Returns the colored cloud. Points that belong to the object have the same color. */
212  getColoredCloud ();
213 
214  protected:
215 
216  /** \brief This method simply builds the graph that will be used during the segmentation. */
217  bool
218  buildGraph ();
219 
220  /** \brief Returns unary potential(data cost) for the given point index.
221  * In other words it calculates weights for (source, point) and (point, sink) edges.
222  * \param[in] point index of the point for which weights will be calculated
223  * \param[out] source_weight calculated weight for the (source, point) edge
224  * \param[out] sink_weight calculated weight for the (point, sink) edge
225  */
226  void
227  calculateUnaryPotential (int point, double& source_weight, double& sink_weight) const;
228 
229  /** \brief This method simply adds the edge from the source point to the target point with a given weight.
230  * \param[in] source index of the source point of the edge
231  * \param[in] target index of the target point of the edge
232  * \param[in] weight weight that will be assigned to the (source, target) edge
233  */
234  bool
235  addEdge (int source, int target, double weight);
236 
237  /** \brief Returns the binary potential(smooth cost) for the given indices of points.
238  * In other words it returns weight that must be assigned to the edge from source to target point.
239  * \param[in] source index of the source point of the edge
240  * \param[in] target index of the target point of the edge
241  */
242  double
243  calculateBinaryPotential (int source, int target) const;
244 
245  /** \brief This method recalculates unary potentials(data cost) if some changes were made, instead of creating new graph. */
246  bool
247  recalculateUnaryPotentials ();
248 
249  /** \brief This method recalculates binary potentials(smooth cost) if some changes were made, instead of creating new graph. */
250  bool
251  recalculateBinaryPotentials ();
252 
253  /** \brief This method analyzes the residual network and assigns a label to every point in the cloud.
254  * \param[in] residual_capacity residual network that was obtained during the segmentation
255  */
256  void
257  assembleLabels (ResidualCapacityMap& residual_capacity);
258 
259  protected:
260 
261  /** \brief Stores the sigma coefficient. It is used for finding smooth costs. More information can be found in the article. */
263 
264  /** \brief Signalizes if the binary potentials are valid. */
266 
267  /** \brief Used for comparison of the floating point numbers. */
268  double epsilon_;
269 
270  /** \brief Stores the distance to the background. */
271  double radius_;
272 
273  /** \brief Signalizes if the unary potentials are valid. */
275 
276  /** \brief Stores the weight for every edge that comes from source point. */
278 
279  /** \brief Stores the search method that will be used for finding K nearest neighbors. Neighbours are used for building the graph. */
281 
282  /** \brief Stores the number of neighbors to find. */
283  unsigned int number_of_neighbours_;
284 
285  /** \brief Signalizes if the graph is valid. */
287 
288  /** \brief Stores the points that are known to be in the foreground. */
289  std::vector<PointT, Eigen::aligned_allocator<PointT> > foreground_points_;
290 
291  /** \brief Stores the points that are known to be in the background. */
292  std::vector<PointT, Eigen::aligned_allocator<PointT> > background_points_;
293 
294  /** \brief After the segmentation it will contain the segments. */
295  std::vector <pcl::PointIndices> clusters_;
296 
297  /** \brief Stores the graph for finding the maximum flow. */
299 
300  /** \brief Stores the capacity of every edge in the graph. */
301  std::shared_ptr<CapacityMap> capacity_;
302 
303  /** \brief Stores reverse edges for every edge in the graph. */
304  std::shared_ptr<ReverseEdgeMap> reverse_edges_;
305 
306  /** \brief Stores the vertices of the graph. */
307  std::vector< VertexDescriptor > vertices_;
308 
309  /** \brief Stores the information about the edges that were added to the graph. It is used to avoid the duplicate edges. */
310  std::vector< std::set<int> > edge_marker_;
311 
312  /** \brief Stores the vertex that serves as source. */
314 
315  /** \brief Stores the vertex that serves as sink. */
317 
318  /** \brief Stores the maximum flow value that was calculated during the segmentation. */
319  double max_flow_;
320 
321  public:
323  };
324 }
325 
326 #ifdef PCL_NO_PRECOMPILE
327 #include <pcl/segmentation/impl/min_cut_segmentation.hpp>
328 #endif
pcl::MinCutSegmentation::mGraphPtr
shared_ptr< mGraph > mGraphPtr
Definition: min_cut_segmentation.h:104
pcl::search::Search
Generic search class.
Definition: search.h:73
pcl_macros.h
Defines all the PCL and non-PCL macros used.
pcl::MinCutSegmentation::graph_is_valid_
bool graph_is_valid_
Signalizes if the graph is valid.
Definition: min_cut_segmentation.h:286
pcl
This file defines compatibility wrappers for low level I/O functions.
Definition: convolution.h:45
point_types.h
pcl::MinCutSegmentation::ResidualCapacityMap
boost::property_map< mGraph, boost::edge_residual_capacity_t >::type ResidualCapacityMap
Definition: min_cut_segmentation.h:98
pcl::PCLBase::PointCloudConstPtr
typename PointCloud::ConstPtr PointCloudConstPtr
Definition: pcl_base.h:74
pcl::MinCutSegmentation::IndexMap
boost::property_map< mGraph, boost::vertex_index_t >::type IndexMap
Definition: min_cut_segmentation.h:100
pcl::MinCutSegmentation::graph_
mGraphPtr graph_
Stores the graph for finding the maximum flow.
Definition: min_cut_segmentation.h:298
pcl::MinCutSegmentation::background_points_
std::vector< PointT, Eigen::aligned_allocator< PointT > > background_points_
Stores the points that are known to be in the background.
Definition: min_cut_segmentation.h:292
pcl::MinCutSegmentation::Traits
boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::directedS > Traits
Definition: min_cut_segmentation.h:74
pcl::MinCutSegmentation::ReverseEdgeMap
boost::property_map< mGraph, boost::edge_reverse_t >::type ReverseEdgeMap
Definition: min_cut_segmentation.h:88
pcl::MinCutSegmentation::binary_potentials_are_valid_
bool binary_potentials_are_valid_
Signalizes if the binary potentials are valid.
Definition: min_cut_segmentation.h:265
pcl::PCLBase
PCL base class.
Definition: pcl_base.h:69
pcl::MinCutSegmentation::vertices_
std::vector< VertexDescriptor > vertices_
Stores the vertices of the graph.
Definition: min_cut_segmentation.h:307
pcl::MinCutSegmentation::mGraph
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
Definition: min_cut_segmentation.h:84
pcl::PointCloud
PointCloud represents the base class in PCL for storing collections of 3D points.
Definition: projection_matrix.h:52
pcl::MinCutSegmentation::inverse_sigma_
double inverse_sigma_
Stores the sigma coefficient.
Definition: min_cut_segmentation.h:262
pcl::MinCutSegmentation::reverse_edges_
std::shared_ptr< ReverseEdgeMap > reverse_edges_
Stores reverse edges for every edge in the graph.
Definition: min_cut_segmentation.h:304
pcl::MinCutSegmentation::VertexIterator
boost::graph_traits< mGraph >::vertex_iterator VertexIterator
Definition: min_cut_segmentation.h:96
pcl::MinCutSegmentation::capacity_
std::shared_ptr< CapacityMap > capacity_
Stores the capacity of every edge in the graph.
Definition: min_cut_segmentation.h:301
pcl::MinCutSegmentation::source_
VertexDescriptor source_
Stores the vertex that serves as source.
Definition: min_cut_segmentation.h:313
pcl::MinCutSegmentation
This class implements the segmentation algorithm based on minimal cut of the graph.
Definition: min_cut_segmentation.h:58
pcl::MinCutSegmentation::KdTreePtr
typename KdTree::Ptr KdTreePtr
Definition: min_cut_segmentation.h:63
PCL_MAKE_ALIGNED_OPERATOR_NEW
#define PCL_MAKE_ALIGNED_OPERATOR_NEW
Macro to signal a class requires a custom allocator.
Definition: pcl_macros.h:371
pcl::MinCutSegmentation::max_flow_
double max_flow_
Stores the maximum flow value that was calculated during the segmentation.
Definition: min_cut_segmentation.h:319
pcl::MinCutSegmentation::source_weight_
double source_weight_
Stores the weight for every edge that comes from source point.
Definition: min_cut_segmentation.h:277
pcl::MinCutSegmentation::edge_marker_
std::vector< std::set< int > > edge_marker_
Stores the information about the edges that were added to the graph.
Definition: min_cut_segmentation.h:310
pcl::MinCutSegmentation::search_
KdTreePtr search_
Stores the search method that will be used for finding K nearest neighbors.
Definition: min_cut_segmentation.h:280
pcl::MinCutSegmentation::InEdgeIterator
boost::graph_traits< mGraph >::in_edge_iterator InEdgeIterator
Definition: min_cut_segmentation.h:102
pcl::MinCutSegmentation::radius_
double radius_
Stores the distance to the background.
Definition: min_cut_segmentation.h:271
pcl::MinCutSegmentation::sink_
VertexDescriptor sink_
Stores the vertex that serves as sink.
Definition: min_cut_segmentation.h:316
pcl::PointCloud::Ptr
shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:415
pcl::MinCutSegmentation::CapacityMap
boost::property_map< mGraph, boost::edge_capacity_t >::type CapacityMap
Definition: min_cut_segmentation.h:86
pcl::MinCutSegmentation::number_of_neighbours_
unsigned int number_of_neighbours_
Stores the number of neighbors to find.
Definition: min_cut_segmentation.h:283
pcl::KdTree::Ptr
shared_ptr< KdTree< PointT > > Ptr
Definition: kdtree.h:69
pcl::MinCutSegmentation::clusters_
std::vector< pcl::PointIndices > clusters_
After the segmentation it will contain the segments.
Definition: min_cut_segmentation.h:295
pcl::MinCutSegmentation::unary_potentials_are_valid_
bool unary_potentials_are_valid_
Signalizes if the unary potentials are valid.
Definition: min_cut_segmentation.h:274
pcl::MinCutSegmentation::OutEdgeIterator
boost::graph_traits< mGraph >::out_edge_iterator OutEdgeIterator
Definition: min_cut_segmentation.h:94
pcl::PointCloud::ConstPtr
shared_ptr< const PointCloud< PointT > > ConstPtr
Definition: point_cloud.h:416
pcl::MinCutSegmentation::foreground_points_
std::vector< PointT, Eigen::aligned_allocator< PointT > > foreground_points_
Stores the points that are known to be in the foreground.
Definition: min_cut_segmentation.h:289
pcl::MinCutSegmentation::epsilon_
double epsilon_
Used for comparison of the floating point numbers.
Definition: min_cut_segmentation.h:268
pcl::MinCutSegmentation::EdgeDescriptor
boost::graph_traits< mGraph >::edge_descriptor EdgeDescriptor
Definition: min_cut_segmentation.h:92
PCL_EXPORTS
#define PCL_EXPORTS
Definition: pcl_macros.h:253
pcl::MinCutSegmentation::VertexDescriptor
Traits::vertex_descriptor VertexDescriptor
Definition: min_cut_segmentation.h:90
pcl::shared_ptr
boost::shared_ptr< T > shared_ptr
Alias for boost::shared_ptr.
Definition: pcl_macros.h:90