Point Cloud Library (PCL)  1.11.0
grabcut_segmentation.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2012-, Open Perception, Inc.
6  *
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following
17  * disclaimer in the documentation and/or other materials provided
18  * with the distribution.
19  * * Neither the name of Willow Garage, Inc. nor the names of its
20  * contributors may be used to endorse or promote products derived
21  * from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  * $Id$
37  *
38  */
39 
40 #pragma once
41 
42 #include <pcl/memory.h>
43 #include <pcl/point_cloud.h>
44 #include <pcl/pcl_base.h>
45 #include <pcl/pcl_macros.h>
46 #include <pcl/point_types.h>
47 #include <pcl/segmentation/boost.h>
48 #include <pcl/search/search.h>
49 
50 namespace pcl
51 {
52  namespace segmentation
53  {
54  namespace grabcut
55  {
56  /** boost implementation of Boykov and Kolmogorov's maxflow algorithm doesn't support
57  * negative flows which makes it inappropriate for this context.
58  * This implementation of Boykov and Kolmogorov's maxflow algorithm by Stephen Gould
59  * <stephen.gould@anu.edu.au> in DARWIN under BSD does the trick however solwer than original
60  * implementation.
61  */
63  {
64  public:
65  using vertex_descriptor = int;
66  using edge_capacity_type = double;
67 
68  /// construct a maxflow/mincut problem with estimated max_nodes
69  BoykovKolmogorov (std::size_t max_nodes = 0);
70  /// destructor
71  virtual ~BoykovKolmogorov () {}
72  /// get number of nodes in the graph
73  std::size_t
74  numNodes () const { return nodes_.size (); }
75  /// reset all edge capacities to zero (but don't free the graph)
76  void
77  reset ();
78  /// clear the graph and internal datastructures
79  void
80  clear ();
81  /// add nodes to the graph (returns the id of the first node added)
82  int
83  addNodes (std::size_t n = 1);
84  /// add constant flow to graph
85  void
86  addConstant (double c) { flow_value_ += c; }
87  /// add edge from s to nodeId
88  void
89  addSourceEdge (int u, double cap);
90  /// add edge from nodeId to t
91  void
92  addTargetEdge (int u, double cap);
93  /// add edge from u to v and edge from v to u
94  /// (requires cap_uv + cap_vu >= 0)
95  void
96  addEdge (int u, int v, double cap_uv, double cap_vu = 0.0);
97  /// solve the max-flow problem and return the flow
98  double
99  solve ();
100  /// return true if \p u is in the s-set after calling \ref solve.
101  bool
102  inSourceTree (int u) const { return (cut_[u] == SOURCE); }
103  /// return true if \p u is in the t-set after calling \ref solve
104  bool
105  inSinkTree (int u) const { return (cut_[u] == TARGET); }
106  /// returns the residual capacity for an edge (use -1 for terminal (-1,-1) is the current flow
107  double
108  operator() (int u, int v) const;
109 
110  double
111  getSourceEdgeCapacity (int u) const;
112 
113  double
114  getTargetEdgeCapacity (int u) const;
115 
116  protected:
117  /// tree states
118  enum nodestate { FREE = 0x00, SOURCE = 0x01, TARGET = 0x02 };
119  /// capacitated edge
120  using capacitated_edge = std::map<int, double>;
121  /// edge pair
122  using edge_pair = std::pair<capacitated_edge::iterator, capacitated_edge::iterator>;
123  /// pre-augment s-u-t and s-u-v-t paths
124  void
126  /// initialize trees from source and target
127  void
129  /// expand trees until a path is found (or no path (-1, -1))
130  std::pair<int, int>
132  /// augment the path found by expandTrees; return orphaned subtrees
133  void
134  augmentPath (const std::pair<int, int>& path, std::deque<int>& orphans);
135  /// adopt orphaned subtrees
136  void
137  adoptOrphans (std::deque<int>& orphans);
138  /// clear active set
139  void clearActive ();
140  /// \return true if active set is empty
141  inline bool
142  isActiveSetEmpty () const { return (active_head_ == TERMINAL); }
143  /// active if head or previous node is not the terminal
144  inline bool
145  isActive (int u) const { return ((u == active_head_) || (active_list_[u].first != TERMINAL)); }
146  /// mark vertex as active
147  void
148  markActive (int u);
149  /// mark vertex as inactive
150  void
151  markInactive (int u);
152  /// edges leaving the source
153  std::vector<double> source_edges_;
154  /// edges entering the target
155  std::vector<double> target_edges_;
156  /// nodes and their outgoing internal edges
157  std::vector<capacitated_edge> nodes_;
158  /// current flow value (includes constant)
159  double flow_value_;
160  /// identifies which side of the cut a node falls
161  std::vector<unsigned char> cut_;
162 
163  private:
164  /// parents_ flag for terminal state
165  static const int TERMINAL; // -1
166  /// search tree (also uses cut_)
167  std::vector<std::pair<int, edge_pair> > parents_;
168  /// doubly-linked list (prev, next)
169  std::vector<std::pair<int, int> > active_list_;
170  int active_head_, active_tail_;
171  };
172 
173  /**\brief Structure to save RGB colors into floats */
174  struct Color
175  {
176  Color () : r (0), g (0), b (0) {}
177  Color (float _r, float _g, float _b) : r(_r), g(_g), b(_b) {}
178  Color (const pcl::RGB& color) : r (color.r), g (color.g), b (color.b) {}
179 
180  template<typename PointT>
181  Color (const PointT& p);
182 
183  template<typename PointT>
184  operator PointT () const;
185 
186  float r, g, b;
187  };
188  /// An Image is a point cloud of Color
190  /** \brief Compute squared distance between two colors
191  * \param[in] c1 first color
192  * \param[in] c2 second color
193  * \return the squared distance measure in RGB space
194  */
195  float
196  colorDistance (const Color& c1, const Color& c2);
197  /// User supplied Trimap values
199  /// Grabcut derived hard segmentation values
201  /// Gaussian structure
202  struct Gaussian
203  {
204  Gaussian () {}
205  /// mean of the gaussian
207  /// covariance matrix of the gaussian
208  Eigen::Matrix3f covariance;
209  /// determinant of the covariance matrix
210  float determinant;
211  /// inverse of the covariance matrix
212  Eigen::Matrix3f inverse;
213  /// weighting of this gaussian in the GMM.
214  float pi;
215  /// highest eigenvalue of covariance matrix
216  float eigenvalue;
217  /// eigenvector corresponding to the highest eigenvector
218  Eigen::Vector3f eigenvector;
219  };
220 
222  {
223  public:
224  /// Initialize GMM with ddesired number of gaussians.
225  GMM () : gaussians_ (0) {}
226  /// Initialize GMM with ddesired number of gaussians.
227  GMM (std::size_t K) : gaussians_ (K) {}
228  /// Destructor
229  ~GMM () {}
230  /// \return K
231  std::size_t
232  getK () const { return gaussians_.size (); }
233  /// resize gaussians
234  void
235  resize (std::size_t K) { gaussians_.resize (K); }
236  /// \return a reference to the gaussian at a given position
237  Gaussian&
238  operator[] (std::size_t pos) { return (gaussians_[pos]); }
239  /// \return a const reference to the gaussian at a given position
240  const Gaussian&
241  operator[] (std::size_t pos) const { return (gaussians_[pos]); }
242  /// \brief \return the computed probability density of a color in this GMM
243  float
245  /// \brief \return the computed probability density of a color in just one Gaussian
246  float
247  probabilityDensity(std::size_t i, const Color &c);
248 
249  private:
250  /// array of gaussians
251  std::vector<Gaussian> gaussians_;
252  };
253 
254  /** Helper class that fits a single Gaussian to color samples */
256  {
257  public:
258  GaussianFitter (float epsilon = 0.0001)
259  : sum_ (Eigen::Vector3f::Zero ())
260  , accumulator_ (Eigen::Matrix3f::Zero ())
261  , count_ (0)
262  , epsilon_ (epsilon)
263  { }
264 
265  /// Add a color sample
266  void
267  add (const Color &c);
268  /// Build the gaussian out of all the added color samples
269  void
270  fit (Gaussian& g, std::size_t total_count, bool compute_eigens = false) const;
271  /// \return epsilon
272  float
273  getEpsilon () { return (epsilon_); }
274  /** set epsilon which will be added to the covariance matrix diagonal which avoids singular
275  * covariance matrix
276  * \param[in] epsilon user defined epsilon
277  */
278  void
279  setEpsilon (float epsilon) { epsilon_ = epsilon; }
280 
281  private:
282  /// sum of r,g, and b
283  Eigen::Vector3f sum_;
284  /// matrix of products (i.e. r*r, r*g, r*b), some values are duplicated.
285  Eigen::Matrix3f accumulator_;
286  /// count of color samples added to the gaussian
287  std::uint32_t count_;
288  /// small value to add to covariance matrix diagonal to avoid singular values
289  float epsilon_;
291  };
292 
293  /** Build the initial GMMs using the Orchard and Bouman color clustering algorithm */
294  PCL_EXPORTS void
295  buildGMMs (const Image &image,
296  const std::vector<int>& indices,
297  const std::vector<SegmentationValue> &hardSegmentation,
298  std::vector<std::size_t> &components,
299  GMM &background_GMM, GMM &foreground_GMM);
300  /** Iteratively learn GMMs using GrabCut updating algorithm */
301  PCL_EXPORTS void
302  learnGMMs (const Image& image,
303  const std::vector<int>& indices,
304  const std::vector<SegmentationValue>& hard_segmentation,
305  std::vector<std::size_t>& components,
306  GMM& background_GMM, GMM& foreground_GMM);
307  }
308  };
309 
310  /** \brief Implementation of the GrabCut segmentation in
311  * "GrabCut — Interactive Foreground Extraction using Iterated Graph Cuts" by
312  * Carsten Rother, Vladimir Kolmogorov and Andrew Blake.
313  *
314  * \author Justin Talbot, jtalbot@stanford.edu placed in Public Domain, 2010
315  * \author Nizar Sallem port to PCL and adaptation of original code.
316  * \ingroup segmentation
317  */
318  template <typename PointT>
319  class GrabCut : public pcl::PCLBase<PointT>
320  {
321  public:
323  using KdTreePtr = typename KdTree::Ptr;
329 
330  /// Constructor
331  GrabCut (std::uint32_t K = 5, float lambda = 50.f)
332  : K_ (K)
333  , lambda_ (lambda)
334  , nb_neighbours_ (9)
335  , initialized_ (false)
336  {}
337  /// Destructor
338  ~GrabCut () {};
339  // /// Set input cloud
340  void
341  setInputCloud (const PointCloudConstPtr& cloud) override;
342  /// Set background points, foreground points = points \ background points
343  void
344  setBackgroundPoints (const PointCloudConstPtr& background_points);
345  /// Set background indices, foreground indices = indices \ background indices
346  void
347  setBackgroundPointsIndices (int x1, int y1, int x2, int y2);
348  /// Set background indices, foreground indices = indices \ background indices
349  void
351  /// Run Grabcut refinement on the hard segmentation
352  virtual void
353  refine ();
354  /// \return the number of pixels that have changed from foreground to background or vice versa
355  virtual int
356  refineOnce ();
357  /// \return lambda
358  float
359  getLambda () { return (lambda_); }
360  /** Set lambda parameter to user given value. Suggested value by the authors is 50
361  * \param[in] lambda
362  */
363  void
364  setLambda (float lambda) { lambda_ = lambda; }
365  /// \return the number of components in the GMM
367  getK () { return (K_); }
368  /** Set K parameter to user given value. Suggested value by the authors is 5
369  * \param[in] K the number of components used in GMM
370  */
371  void
373  /** \brief Provide a pointer to the search object.
374  * \param tree a pointer to the spatial search object.
375  */
376  inline void
377  setSearchMethod (const KdTreePtr &tree) { tree_ = tree; }
378  /** \brief Get a pointer to the search method used. */
379  inline KdTreePtr
380  getSearchMethod () { return (tree_); }
381  /** \brief Allows to set the number of neighbours to find.
382  * \param[in] nb_neighbours new number of neighbours
383  */
384  void
385  setNumberOfNeighbours (int nb_neighbours) { nb_neighbours_ = nb_neighbours; }
386  /** \brief Returns the number of neighbours to find. */
387  int
388  getNumberOfNeighbours () const { return (nb_neighbours_); }
389  /** \brief This method launches the segmentation algorithm and returns the clusters that were
390  * obtained during the segmentation. The indices of points belonging to the object will be stored
391  * in the cluster with index 1, other indices will be stored in the cluster with index 0.
392  * \param[out] clusters clusters that were obtained. Each cluster is an array of point indices.
393  */
394  void
395  extract (std::vector<pcl::PointIndices>& clusters);
396 
397  protected:
398  // Storage for N-link weights, each pixel stores links to nb_neighbours
399  struct NLinks
400  {
401  NLinks () : nb_links (0), indices (0), dists (0), weights (0) {}
402 
403  int nb_links;
404  std::vector<int> indices;
405  std::vector<float> dists;
406  std::vector<float> weights;
407  };
408  bool
409  initCompute ();
411  /// Compute beta from image
412  void
414  /// Compute beta from cloud
415  void
417  /// Compute L parameter from given lambda
418  void
419  computeL ();
420  /// Compute NLinks from image
421  void
423  /// Compute NLinks from cloud
424  void
426  /// Edit Trimap
427  void
429  int
431  /// Fit Gaussian Multi Models
432  virtual void
433  fitGMMs ();
434  /// Build the graph for GraphCut
435  void
436  initGraph ();
437  /// Add an edge to the graph, graph must be oriented so we add the edge and its reverse
438  void
439  addEdge (vertex_descriptor v1, vertex_descriptor v2, float capacity, float rev_capacity);
440  /// Set the weights of SOURCE --> v and v --> SINK
441  void
442  setTerminalWeights (vertex_descriptor v, float source_capacity, float sink_capacity);
443  /// \return true if v is in source tree
444  inline bool
446  /// image width
448  /// image height
450  // Variables used in formulas from the paper.
451  /// Number of GMM components
453  /// lambda = 50. This value was suggested the GrabCut paper.
454  float lambda_;
455  /// beta = 1/2 * average of the squared color distances between all pairs of 8-neighboring pixels.
456  float beta_;
457  /// L = a large value to force a pixel to be foreground or background
458  float L_;
459  /// Pointer to the spatial search object.
461  /// Number of neighbours
463  /// is segmentation initialized
465  /// Precomputed N-link weights
466  std::vector<NLinks> n_links_;
467  /// Converted input
469  std::vector<segmentation::grabcut::TrimapValue> trimap_;
470  std::vector<std::size_t> GMM_component_;
471  std::vector<segmentation::grabcut::SegmentationValue> hard_segmentation_;
472  // Not yet implemented (this would be interpreted as alpha)
473  std::vector<float> soft_segmentation_;
475  // Graph part
476  /// Graph for Graphcut
478  /// Graph nodes
479  std::vector<vertex_descriptor> graph_nodes_;
480  };
481 }
482 
483 #include <pcl/segmentation/impl/grabcut_segmentation.hpp>
pcl::segmentation::grabcut::BoykovKolmogorov::adoptOrphans
void adoptOrphans(std::deque< int > &orphans)
adopt orphaned subtrees
pcl::search::Search
Generic search class.
Definition: search.h:75
pcl_macros.h
Defines all the PCL and non-PCL macros used.
pcl
Definition: convolution.h:46
pcl::K
@ K
Definition: norms.h:54
pcl::segmentation::grabcut::BoykovKolmogorov::vertex_descriptor
int vertex_descriptor
Definition: grabcut_segmentation.h:65
pcl::segmentation::grabcut::GaussianFitter::fit
void fit(Gaussian &g, std::size_t total_count, bool compute_eigens=false) const
Build the gaussian out of all the added color samples.
point_types.h
pcl::GrabCut::image_
segmentation::grabcut::Image::Ptr image_
Converted input.
Definition: grabcut_segmentation.h:468
pcl::segmentation::grabcut::BoykovKolmogorov::getTargetEdgeCapacity
double getTargetEdgeCapacity(int u) const
pcl::GrabCut::computeBetaOrganized
void computeBetaOrganized()
Compute beta from image.
Definition: grabcut_segmentation.hpp:425
pcl::uint32_t
std::uint32_t uint32_t
Definition: types.h:58
pcl::segmentation::grabcut::BoykovKolmogorov::BoykovKolmogorov
BoykovKolmogorov(std::size_t max_nodes=0)
construct a maxflow/mincut problem with estimated max_nodes
Eigen
Definition: bfgs.h:10
pcl::GrabCut::getSearchMethod
KdTreePtr getSearchMethod()
Get a pointer to the search method used.
Definition: grabcut_segmentation.h:380
pcl::PCLBase::PointCloudConstPtr
typename PointCloud::ConstPtr PointCloudConstPtr
Definition: pcl_base.h:74
pcl::segmentation::grabcut::BoykovKolmogorov::source_edges_
std::vector< double > source_edges_
edges leaving the source
Definition: grabcut_segmentation.h:153
pcl::PCLBase::PointCloudPtr
typename PointCloud::Ptr PointCloudPtr
Definition: pcl_base.h:73
pcl::segmentation::grabcut::BoykovKolmogorov::addNodes
int addNodes(std::size_t n=1)
add nodes to the graph (returns the id of the first node added)
pcl::segmentation::grabcut::BoykovKolmogorov::addTargetEdge
void addTargetEdge(int u, double cap)
add edge from nodeId to t
pcl::GrabCut::trimap_
std::vector< segmentation::grabcut::TrimapValue > trimap_
Definition: grabcut_segmentation.h:469
pcl::segmentation::grabcut::BoykovKolmogorov::markActive
void markActive(int u)
mark vertex as active
pcl::segmentation::grabcut::BoykovKolmogorov::~BoykovKolmogorov
virtual ~BoykovKolmogorov()
destructor
Definition: grabcut_segmentation.h:71
pcl::segmentation::grabcut::TrimapForeground
@ TrimapForeground
Definition: grabcut_segmentation.h:198
pcl::segmentation::grabcut::GaussianFitter
Helper class that fits a single Gaussian to color samples.
Definition: grabcut_segmentation.h:256
pcl::segmentation::grabcut::BoykovKolmogorov::addEdge
void addEdge(int u, int v, double cap_uv, double cap_vu=0.0)
add edge from u to v and edge from v to u (requires cap_uv + cap_vu >= 0)
pcl::segmentation::grabcut::Gaussian::determinant
float determinant
determinant of the covariance matrix
Definition: grabcut_segmentation.h:210
pcl::segmentation::grabcut::GMM::GMM
GMM()
Initialize GMM with ddesired number of gaussians.
Definition: grabcut_segmentation.h:225
pcl::GrabCut::getLambda
float getLambda()
Definition: grabcut_segmentation.h:359
pcl::GrabCut
Implementation of the GrabCut segmentation in "GrabCut — Interactive Foreground Extraction using Iter...
Definition: grabcut_segmentation.h:320
pcl::segmentation::grabcut::GaussianFitter::setEpsilon
void setEpsilon(float epsilon)
set epsilon which will be added to the covariance matrix diagonal which avoids singular covariance ma...
Definition: grabcut_segmentation.h:279
pcl::segmentation::grabcut::GMM::~GMM
~GMM()
Destructor.
Definition: grabcut_segmentation.h:229
pcl::segmentation::grabcut::BoykovKolmogorov::numNodes
std::size_t numNodes() const
get number of nodes in the graph
Definition: grabcut_segmentation.h:74
pcl::segmentation::grabcut::GMM::probabilityDensity
float probabilityDensity(std::size_t i, const Color &c)
pcl::GrabCut::refineOnce
virtual int refineOnce()
Definition: grabcut_segmentation.hpp:194
pcl::segmentation::grabcut::GaussianFitter::getEpsilon
float getEpsilon()
Definition: grabcut_segmentation.h:273
pcl::GrabCut::setInputCloud
void setInputCloud(const PointCloudConstPtr &cloud) override
Provide a pointer to the input dataset.
Definition: grabcut_segmentation.hpp:80
pcl::segmentation::grabcut::TrimapUnknown
@ TrimapUnknown
Definition: grabcut_segmentation.h:198
pcl::PCLBase
PCL base class.
Definition: pcl_base.h:70
pcl::segmentation::grabcut::SegmentationForeground
@ SegmentationForeground
Definition: grabcut_segmentation.h:200
pcl::PCLBase::PointIndicesConstPtr
PointIndices::ConstPtr PointIndicesConstPtr
Definition: pcl_base.h:77
pcl::segmentation::grabcut::Gaussian::Gaussian
Gaussian()
Definition: grabcut_segmentation.h:204
pcl::segmentation::grabcut::BoykovKolmogorov::reset
void reset()
reset all edge capacities to zero (but don't free the graph)
pcl::GrabCut::computeL
void computeL()
Compute L parameter from given lambda.
Definition: grabcut_segmentation.hpp:495
pcl::PointCloud
PointCloud represents the base class in PCL for storing collections of 3D points.
Definition: projection_matrix.h:52
pcl::segmentation::grabcut::GaussianFitter::GaussianFitter
GaussianFitter(float epsilon=0.0001)
Definition: grabcut_segmentation.h:258
pcl::segmentation::grabcut::Color::Color
Color()
Definition: grabcut_segmentation.h:176
pcl::GrabCut::foreground_GMM_
segmentation::grabcut::GMM foreground_GMM_
Definition: grabcut_segmentation.h:474
pcl::PointXYZRGB
A point structure representing Euclidean xyz coordinates, and the RGB color.
Definition: point_types.hpp:629
pcl::GrabCut::refine
virtual void refine()
Run Grabcut refinement on the hard segmentation.
Definition: grabcut_segmentation.hpp:211
pcl::GrabCut::graph_
pcl::segmentation::grabcut::BoykovKolmogorov graph_
Graph for Graphcut.
Definition: grabcut_segmentation.h:477
pcl::GrabCut::background_GMM_
segmentation::grabcut::GMM background_GMM_
Definition: grabcut_segmentation.h:474
pcl::GrabCut::GrabCut
GrabCut(std::uint32_t K=5, float lambda=50.f)
Constructor.
Definition: grabcut_segmentation.h:331
pcl::GrabCut::setTerminalWeights
void setTerminalWeights(vertex_descriptor v, float source_capacity, float sink_capacity)
Set the weights of SOURCE --> v and v --> SINK.
Definition: grabcut_segmentation.hpp:155
pcl::segmentation::grabcut::Color::r
float r
Definition: grabcut_segmentation.h:186
pcl::segmentation::grabcut::Gaussian::eigenvector
Eigen::Vector3f eigenvector
eigenvector corresponding to the highest eigenvector
Definition: grabcut_segmentation.h:218
pcl::segmentation::grabcut::BoykovKolmogorov::addSourceEdge
void addSourceEdge(int u, double cap)
add edge from s to nodeId
pcl::segmentation::grabcut::BoykovKolmogorov::augmentPath
void augmentPath(const std::pair< int, int > &path, std::deque< int > &orphans)
augment the path found by expandTrees; return orphaned subtrees
pcl::GrabCut::setK
void setK(std::uint32_t K)
Set K parameter to user given value.
Definition: grabcut_segmentation.h:372
pcl::GrabCut::hard_segmentation_
std::vector< segmentation::grabcut::SegmentationValue > hard_segmentation_
Definition: grabcut_segmentation.h:471
pcl::segmentation::grabcut::GMM::getK
std::size_t getK() const
Definition: grabcut_segmentation.h:232
pcl::segmentation::grabcut::BoykovKolmogorov::flow_value_
double flow_value_
current flow value (includes constant)
Definition: grabcut_segmentation.h:159
pcl::GrabCut::getK
std::uint32_t getK()
Definition: grabcut_segmentation.h:367
pcl::GrabCut::isSource
bool isSource(vertex_descriptor v)
Definition: grabcut_segmentation.h:445
pcl::GrabCut::updateHardSegmentation
int updateHardSegmentation()
Definition: grabcut_segmentation.hpp:220
pcl::segmentation::grabcut::BoykovKolmogorov::expandTrees
std::pair< int, int > expandTrees()
expand trees until a path is found (or no path (-1, -1))
pcl::segmentation::grabcut::Color::b
float b
Definition: grabcut_segmentation.h:186
pcl::segmentation::grabcut::colorDistance
float colorDistance(const Color &c1, const Color &c2)
Compute squared distance between two colors.
pcl::segmentation::grabcut::SegmentationValue
SegmentationValue
Grabcut derived hard segmentation values.
Definition: grabcut_segmentation.h:200
pcl::segmentation::grabcut::Gaussian::covariance
Eigen::Matrix3f covariance
covariance matrix of the gaussian
Definition: grabcut_segmentation.h:208
pcl::segmentation::grabcut::BoykovKolmogorov::cut_
std::vector< unsigned char > cut_
identifies which side of the cut a node falls
Definition: grabcut_segmentation.h:161
pcl::GrabCut::fitGMMs
virtual void fitGMMs()
Fit Gaussian Multi Models.
Definition: grabcut_segmentation.hpp:184
pcl::segmentation::grabcut::learnGMMs
PCL_EXPORTS void learnGMMs(const Image &image, const std::vector< int > &indices, const std::vector< SegmentationValue > &hard_segmentation, std::vector< std::size_t > &components, GMM &background_GMM, GMM &foreground_GMM)
Iteratively learn GMMs using GrabCut updating algorithm.
pcl::GrabCut::setSearchMethod
void setSearchMethod(const KdTreePtr &tree)
Provide a pointer to the search object.
Definition: grabcut_segmentation.h:377
pcl::segmentation::grabcut::BoykovKolmogorov::preAugmentPaths
void preAugmentPaths()
pre-augment s-u-t and s-u-v-t paths
pcl::GrabCut::initialized_
bool initialized_
is segmentation initialized
Definition: grabcut_segmentation.h:464
pcl::segmentation::grabcut::buildGMMs
PCL_EXPORTS void buildGMMs(const Image &image, const std::vector< int > &indices, const std::vector< SegmentationValue > &hardSegmentation, std::vector< std::size_t > &components, GMM &background_GMM, GMM &foreground_GMM)
Build the initial GMMs using the Orchard and Bouman color clustering algorithm.
pcl::GrabCut::computeNLinksNonOrganized
void computeNLinksNonOrganized()
Compute NLinks from cloud.
Definition: grabcut_segmentation.hpp:333
pcl::GrabCut::width_
std::uint32_t width_
image width
Definition: grabcut_segmentation.h:447
pcl::segmentation::grabcut::TrimapValue
TrimapValue
User supplied Trimap values.
Definition: grabcut_segmentation.h:198
pcl::GrabCut::setBackgroundPointsIndices
void setBackgroundPointsIndices(int x1, int y1, int x2, int y2)
Set background indices, foreground indices = indices \ background indices.
pcl::GrabCut::nb_neighbours_
int nb_neighbours_
Number of neighbours.
Definition: grabcut_segmentation.h:462
pcl::segmentation::grabcut::Gaussian
Gaussian structure.
Definition: grabcut_segmentation.h:203
pcl::search::Search::Ptr
shared_ptr< pcl::search::Search< PointT > > Ptr
Definition: search.h:81
pcl::GrabCut::beta_
float beta_
beta = 1/2 * average of the squared color distances between all pairs of 8-neighboring pixels.
Definition: grabcut_segmentation.h:456
PCL_MAKE_ALIGNED_OPERATOR_NEW
#define PCL_MAKE_ALIGNED_OPERATOR_NEW
Macro to signal a class requires a custom allocator.
Definition: memory.h:63
pcl::GrabCut::vertex_descriptor
pcl::segmentation::grabcut::BoykovKolmogorov::vertex_descriptor vertex_descriptor
Definition: grabcut_segmentation.h:410
pcl::RGB
A structure representing RGB color information.
Definition: point_types.hpp:346
pcl::segmentation::grabcut::BoykovKolmogorov::addConstant
void addConstant(double c)
add constant flow to graph
Definition: grabcut_segmentation.h:86
pcl::GrabCut::GMM_component_
std::vector< std::size_t > GMM_component_
Definition: grabcut_segmentation.h:470
pcl::GrabCut::L_
float L_
L = a large value to force a pixel to be foreground or background.
Definition: grabcut_segmentation.h:458
pcl::segmentation::grabcut::SegmentationBackground
@ SegmentationBackground
Definition: grabcut_segmentation.h:200
pcl::segmentation::grabcut::BoykovKolmogorov::clearActive
void clearActive()
clear active set
pcl::segmentation::grabcut::BoykovKolmogorov::nodestate
nodestate
tree states
Definition: grabcut_segmentation.h:118
pcl::segmentation::grabcut::GaussianFitter::add
void add(const Color &c)
Add a color sample.
pcl::segmentation::grabcut::GMM
Definition: grabcut_segmentation.h:222
pcl::segmentation::grabcut::Gaussian::inverse
Eigen::Matrix3f inverse
inverse of the covariance matrix
Definition: grabcut_segmentation.h:212
pcl::segmentation::grabcut::Color::Color
Color(const pcl::RGB &color)
Definition: grabcut_segmentation.h:178
pcl::segmentation::grabcut::BoykovKolmogorov::edge_pair
std::pair< capacitated_edge::iterator, capacitated_edge::iterator > edge_pair
edge pair
Definition: grabcut_segmentation.h:122
pcl::GrabCut::setLambda
void setLambda(float lambda)
Set lambda parameter to user given value.
Definition: grabcut_segmentation.h:364
pcl::segmentation::grabcut::BoykovKolmogorov::getSourceEdgeCapacity
double getSourceEdgeCapacity(int u) const
pcl::GrabCut::computeNLinksOrganized
void computeNLinksOrganized()
Compute NLinks from image.
Definition: grabcut_segmentation.hpp:359
pcl::segmentation::grabcut::GMM::resize
void resize(std::size_t K)
resize gaussians
Definition: grabcut_segmentation.h:235
pcl::segmentation::grabcut::Gaussian::eigenvalue
float eigenvalue
highest eigenvalue of covariance matrix
Definition: grabcut_segmentation.h:216
pcl::GrabCut::height_
std::uint32_t height_
image height
Definition: grabcut_segmentation.h:449
pcl::segmentation::grabcut::BoykovKolmogorov::markInactive
void markInactive(int u)
mark vertex as inactive
pcl::GrabCut::setTrimap
void setTrimap(const PointIndicesConstPtr &indices, segmentation::grabcut::TrimapValue t)
Edit Trimap.
Definition: grabcut_segmentation.hpp:251
pcl::GrabCut::initGraph
void initGraph()
Build the graph for GraphCut.
Definition: grabcut_segmentation.hpp:268
pcl::PointCloud::Ptr
shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:428
pcl::GrabCut::getNumberOfNeighbours
int getNumberOfNeighbours() const
Returns the number of neighbours to find.
Definition: grabcut_segmentation.h:388
pcl::GrabCut::soft_segmentation_
std::vector< float > soft_segmentation_
Definition: grabcut_segmentation.h:473
pcl::segmentation::grabcut::BoykovKolmogorov::capacitated_edge
std::map< int, double > capacitated_edge
capacitated edge
Definition: grabcut_segmentation.h:120
pcl::segmentation::grabcut::GMM::probabilityDensity
float probabilityDensity(const Color &c)
pcl::segmentation::grabcut::Gaussian::pi
float pi
weighting of this gaussian in the GMM.
Definition: grabcut_segmentation.h:214
pcl::GrabCut::K_
std::uint32_t K_
Number of GMM components.
Definition: grabcut_segmentation.h:452
pcl::GrabCut::~GrabCut
~GrabCut()
Destructor.
Definition: grabcut_segmentation.h:338
pcl::segmentation::grabcut::BoykovKolmogorov::solve
double solve()
solve the max-flow problem and return the flow
pcl::GrabCut::KdTreePtr
typename KdTree::Ptr KdTreePtr
Definition: grabcut_segmentation.h:323
pcl::segmentation::grabcut::BoykovKolmogorov::edge_capacity_type
double edge_capacity_type
Definition: grabcut_segmentation.h:66
pcl::segmentation::grabcut::BoykovKolmogorov::clear
void clear()
clear the graph and internal datastructures
pcl::segmentation::grabcut::BoykovKolmogorov::isActive
bool isActive(int u) const
active if head or previous node is not the terminal
Definition: grabcut_segmentation.h:145
pcl::segmentation::grabcut::GMM::GMM
GMM(std::size_t K)
Initialize GMM with ddesired number of gaussians.
Definition: grabcut_segmentation.h:227
pcl::GrabCut::addEdge
void addEdge(vertex_descriptor v1, vertex_descriptor v2, float capacity, float rev_capacity)
Add an edge to the graph, graph must be oriented so we add the edge and its reverse.
Definition: grabcut_segmentation.hpp:149
pcl::segmentation::grabcut::BoykovKolmogorov::isActiveSetEmpty
bool isActiveSetEmpty() const
Definition: grabcut_segmentation.h:142
pcl::segmentation::grabcut::BoykovKolmogorov::inSinkTree
bool inSinkTree(int u) const
return true if u is in the t-set after calling solve
Definition: grabcut_segmentation.h:105
pcl::GrabCut::computeBetaNonOrganized
void computeBetaNonOrganized()
Compute beta from cloud.
Definition: grabcut_segmentation.hpp:386
pcl::segmentation::grabcut::Color
Structure to save RGB colors into floats.
Definition: grabcut_segmentation.h:175
pcl::segmentation::grabcut::Color::g
float g
Definition: grabcut_segmentation.h:186
pcl::GrabCut::extract
void extract(std::vector< pcl::PointIndices > &clusters)
This method launches the segmentation algorithm and returns the clusters that were obtained during th...
Definition: grabcut_segmentation.hpp:501
pcl::segmentation::grabcut::Color::Color
Color(float _r, float _g, float _b)
Definition: grabcut_segmentation.h:177
pcl::GrabCut::graph_nodes_
std::vector< vertex_descriptor > graph_nodes_
Graph nodes.
Definition: grabcut_segmentation.h:479
pcl::GrabCut::setNumberOfNeighbours
void setNumberOfNeighbours(int nb_neighbours)
Allows to set the number of neighbours to find.
Definition: grabcut_segmentation.h:385
pcl::segmentation::grabcut::BoykovKolmogorov
boost implementation of Boykov and Kolmogorov's maxflow algorithm doesn't support negative flows whic...
Definition: grabcut_segmentation.h:63
pcl::GrabCut::tree_
KdTreePtr tree_
Pointer to the spatial search object.
Definition: grabcut_segmentation.h:460
pcl::GrabCut::lambda_
float lambda_
lambda = 50. This value was suggested the GrabCut paper.
Definition: grabcut_segmentation.h:454
memory.h
Defines functions, macros and traits for allocating and using memory.
pcl::segmentation::grabcut::BoykovKolmogorov::initializeTrees
void initializeTrees()
initialize trees from source and target
pcl::GrabCut::n_links_
std::vector< NLinks > n_links_
Precomputed N-link weights.
Definition: grabcut_segmentation.h:466
pcl::segmentation::grabcut::BoykovKolmogorov::nodes_
std::vector< capacitated_edge > nodes_
nodes and their outgoing internal edges
Definition: grabcut_segmentation.h:157
PCL_EXPORTS
#define PCL_EXPORTS
Definition: pcl_macros.h:331
pcl::GrabCut::initCompute
bool initCompute()
Definition: grabcut_segmentation.hpp:86
pcl::segmentation::grabcut::TrimapBackground
@ TrimapBackground
Definition: grabcut_segmentation.h:198
pcl::GrabCut::setBackgroundPoints
void setBackgroundPoints(const PointCloudConstPtr &background_points)
Set background points, foreground points = points \ background points.
pcl::segmentation::grabcut::Gaussian::mu
Color mu
mean of the gaussian
Definition: grabcut_segmentation.h:206
pcl::segmentation::grabcut::BoykovKolmogorov::inSourceTree
bool inSourceTree(int u) const
return true if u is in the s-set after calling solve.
Definition: grabcut_segmentation.h:102
pcl::segmentation::grabcut::BoykovKolmogorov::target_edges_
std::vector< double > target_edges_
edges entering the target
Definition: grabcut_segmentation.h:155