Point Cloud Library (PCL)  1.8.0
supervoxel_clustering.h
1 
2 /*
3  * Software License Agreement (BSD License)
4  *
5  * Point Cloud Library (PCL) - www.pointclouds.org
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  * Author : jpapon@gmail.com
37  * Email : jpapon@gmail.com
38  *
39  */
40 
41 #ifndef PCL_SEGMENTATION_SUPERVOXEL_CLUSTERING_H_
42 #define PCL_SEGMENTATION_SUPERVOXEL_CLUSTERING_H_
43 
44 #include <pcl/features/normal_3d.h>
45 #include <pcl/pcl_base.h>
46 #include <pcl/point_cloud.h>
47 #include <pcl/point_types.h>
48 #include <pcl/octree/octree.h>
49 #include <pcl/octree/octree_pointcloud_adjacency.h>
50 #include <pcl/search/search.h>
51 #include <pcl/segmentation/boost.h>
52 
53 
54 
55 //DEBUG TODO REMOVE
56 #include <pcl/common/time.h>
57 
58 
59 namespace pcl
60 {
61  /** \brief Supervoxel container class - stores a cluster extracted using supervoxel clustering
62  */
63  template <typename PointT>
64  class Supervoxel
65  {
66  public:
68  voxels_ (new pcl::PointCloud<PointT> ()),
69  normals_ (new pcl::PointCloud<Normal> ())
70  { }
71 
72  typedef boost::shared_ptr<Supervoxel<PointT> > Ptr;
73  typedef boost::shared_ptr<const Supervoxel<PointT> > ConstPtr;
74 
75  /** \brief Gets the centroid of the supervoxel
76  * \param[out] centroid_arg centroid of the supervoxel
77  */
78  void
80  {
81  centroid_arg = centroid_;
82  }
83 
84  /** \brief Gets the point normal for the supervoxel
85  * \param[out] normal_arg Point normal of the supervoxel
86  * \note This isn't an average, it is a normal computed using all of the voxels in the supervoxel as support
87  */
88  void
90  {
91  normal_arg.x = centroid_.x;
92  normal_arg.y = centroid_.y;
93  normal_arg.z = centroid_.z;
94  normal_arg.normal_x = normal_.normal_x;
95  normal_arg.normal_y = normal_.normal_y;
96  normal_arg.normal_z = normal_.normal_z;
97  normal_arg.curvature = normal_.curvature;
98  }
99 
100  /** \brief The normal calculated for the voxels contained in the supervoxel */
102  /** \brief The centroid of the supervoxel - average voxel */
104  /** \brief A Pointcloud of the voxels in the supervoxel */
106  /** \brief A Pointcloud of the normals for the points in the supervoxel */
108 
109  public:
110  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
111  };
112 
113  /** \brief Implements a supervoxel algorithm based on voxel structure, normals, and rgb values
114  * \note Supervoxels are oversegmented volumetric patches (usually surfaces)
115  * \note Usually, color isn't needed (and can be detrimental)- spatial structure is mainly used
116  * - J. Papon, A. Abramov, M. Schoeler, F. Woergoetter
117  * Voxel Cloud Connectivity Segmentation - Supervoxels from PointClouds
118  * In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2013
119  * \ingroup segmentation
120  * \author Jeremie Papon (jpapon@gmail.com)
121  */
122  template <typename PointT>
123  class PCL_EXPORTS SupervoxelClustering : public pcl::PCLBase<PointT>
124  {
125  //Forward declaration of friended helper class
126  class SupervoxelHelper;
127  friend class SupervoxelHelper;
128  public:
129  /** \brief VoxelData is a structure used for storing data within a pcl::octree::OctreePointCloudAdjacencyContainer
130  * \note It stores xyz, rgb, normal, distance, an index, and an owner.
131  */
132  class VoxelData
133  {
134  public:
136  xyz_ (0.0f, 0.0f, 0.0f),
137  rgb_ (0.0f, 0.0f, 0.0f),
138  normal_ (0.0f, 0.0f, 0.0f, 0.0f),
139  curvature_ (0.0f),
140  owner_ (0)
141  {}
142 
143  /** \brief Gets the data of in the form of a point
144  * \param[out] point_arg Will contain the point value of the voxeldata
145  */
146  void
147  getPoint (PointT &point_arg) const;
148 
149  /** \brief Gets the data of in the form of a normal
150  * \param[out] normal_arg Will contain the normal value of the voxeldata
151  */
152  void
153  getNormal (Normal &normal_arg) const;
154 
155  Eigen::Vector3f xyz_;
156  Eigen::Vector3f rgb_;
157  Eigen::Vector4f normal_;
158  float curvature_;
159  float distance_;
160  int idx_;
161  SupervoxelHelper* owner_;
162 
163  public:
164  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
165  };
166 
168  typedef std::vector <LeafContainerT*> LeafVectorT;
169 
175  typedef boost::shared_ptr<std::vector<int> > IndicesPtr;
176 
180 
181  typedef boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, uint32_t, float> VoxelAdjacencyList;
182  typedef VoxelAdjacencyList::vertex_descriptor VoxelID;
183  typedef VoxelAdjacencyList::edge_descriptor EdgeID;
184 
185  public:
186 
187  /** \brief Constructor that sets default values for member variables.
188  * \param[in] voxel_resolution The resolution (in meters) of voxels used
189  * \param[in] seed_resolution The average size (in meters) of resulting supervoxels
190  */
191  SupervoxelClustering (float voxel_resolution, float seed_resolution);
192 
193  PCL_DEPRECATED ("SupervoxelClustering constructor with flag for using the single camera transform is deprecated. Default behavior is now to use the transform for organized clouds, and not use it for unorganized. To force use/disuse of the transform, use the setUseSingleCameraTransform(bool) function.")
194  SupervoxelClustering (float voxel_resolution, float seed_resolution, bool);
195 
196  /** \brief This destructor destroys the cloud, normals and search method used for
197  * finding neighbors. In other words it frees memory.
198  */
199  virtual
201 
202  /** \brief Set the resolution of the octree voxels */
203  void
204  setVoxelResolution (float resolution);
205 
206  /** \brief Get the resolution of the octree voxels */
207  float
208  getVoxelResolution () const;
209 
210  /** \brief Set the resolution of the octree seed voxels */
211  void
212  setSeedResolution (float seed_resolution);
213 
214  /** \brief Get the resolution of the octree seed voxels */
215  float
216  getSeedResolution () const;
217 
218  /** \brief Set the importance of color for supervoxels */
219  void
220  setColorImportance (float val);
221 
222  /** \brief Set the importance of spatial distance for supervoxels */
223  void
224  setSpatialImportance (float val);
225 
226  /** \brief Set the importance of scalar normal product for supervoxels */
227  void
228  setNormalImportance (float val);
229 
230  /** \brief Set whether or not to use the single camera transform
231  * \note By default it will be used for organized clouds, but not for unorganized - this parameter will override that behavior
232  * The single camera transform scales bin size so that it increases exponentially with depth (z dimension).
233  * This is done to account for the decreasing point density found with depth when using an RGB-D camera.
234  * Without the transform, beyond a certain depth adjacency of voxels breaks down unless the voxel size is set to a large value.
235  * Using the transform allows preserving detail up close, while allowing adjacency at distance.
236  * The specific transform used here is:
237  * x /= z; y /= z; z = ln(z);
238  * This transform is applied when calculating the octree bins in OctreePointCloudAdjacency
239  */
240  void
241  setUseSingleCameraTransform (bool val);
242 
243  /** \brief This method launches the segmentation algorithm and returns the supervoxels that were
244  * obtained during the segmentation.
245  * \param[out] supervoxel_clusters A map of labels to pointers to supervoxel structures
246  */
247  virtual void
248  extract (std::map<uint32_t,typename Supervoxel<PointT>::Ptr > &supervoxel_clusters);
249 
250  /** \brief This method sets the cloud to be supervoxelized
251  * \param[in] cloud The cloud to be supervoxelize
252  */
253  virtual void
254  setInputCloud (const typename pcl::PointCloud<PointT>::ConstPtr& cloud);
255 
256  /** \brief This method sets the normals to be used for supervoxels (should be same size as input cloud)
257  * \param[in] normal_cloud The input normals
258  */
259  virtual void
260  setNormalCloud (typename NormalCloudT::ConstPtr normal_cloud);
261 
262  /** \brief This method refines the calculated supervoxels - may only be called after extract
263  * \param[in] num_itr The number of iterations of refinement to be done (2 or 3 is usually sufficient)
264  * \param[out] supervoxel_clusters The resulting refined supervoxels
265  */
266  virtual void
267  refineSupervoxels (int num_itr, std::map<uint32_t,typename Supervoxel<PointT>::Ptr > &supervoxel_clusters);
268 
269  ////////////////////////////////////////////////////////////
270  /** \brief Returns an RGB colorized cloud showing superpixels
271  * Otherwise it returns an empty pointer.
272  * Points that belong to the same supervoxel have the same color.
273  * But this function doesn't guarantee that different segments will have different
274  * color(it's random). Points that are unlabeled will be black
275  * \note This will expand the label_colors_ vector so that it can accomodate all labels
276  */
277  PCL_DEPRECATED ("SupervoxelClustering::getColoredCloud is deprecated. Use the getLabeledCloud function instead. examples/segmentation/example_supervoxels.cpp shows how to use this to display and save with colorized labels.")
278  typename pcl::PointCloud<PointXYZRGBA>::Ptr
279  getColoredCloud () const
280  {
281  return boost::make_shared<pcl::PointCloud<PointXYZRGBA> > ();
282  }
283 
284  /** \brief Returns a deep copy of the voxel centroid cloud */
286  getVoxelCentroidCloud () const;
287 
288  /** \brief Returns labeled cloud
289  * Points that belong to the same supervoxel have the same label.
290  * Labels for segments start from 1, unlabled points have label 0
291  */
293  getLabeledCloud () const;
294 
295  /** \brief Returns an RGB colorized voxelized cloud showing superpixels
296  * Otherwise it returns an empty pointer.
297  * Points that belong to the same supervoxel have the same color.
298  * But this function doesn't guarantee that different segments will have different
299  * color(it's random). Points that are unlabeled will be black
300  * \note This will expand the label_colors_ vector so that it can accomodate all labels
301  */
302  PCL_DEPRECATED ("SupervoxelClustering::getColoredVoxelCloud is deprecated. Use the getLabeledVoxelCloud function instead. examples/segmentation/example_supervoxels.cpp shows how to use this to display and save with colorized labels.")
305  {
306  return boost::make_shared<pcl::PointCloud<PointXYZRGBA> > ();
307  }
308 
309  /** \brief Returns labeled voxelized cloud
310  * Points that belong to the same supervoxel have the same label.
311  * Labels for segments start from 1, unlabled points have label 0
312  */
314  getLabeledVoxelCloud () const;
315 
316  /** \brief Gets the adjacency list (Boost Graph library) which gives connections between supervoxels
317  * \param[out] adjacency_list_arg BGL graph where supervoxel labels are vertices, edges are touching relationships
318  */
319  void
320  getSupervoxelAdjacencyList (VoxelAdjacencyList &adjacency_list_arg) const;
321 
322  /** \brief Get a multimap which gives supervoxel adjacency
323  * \param[out] label_adjacency Multi-Map which maps a supervoxel label to all adjacent supervoxel labels
324  */
325  void
326  getSupervoxelAdjacency (std::multimap<uint32_t, uint32_t> &label_adjacency) const;
327 
328  /** \brief Static helper function which returns a pointcloud of normals for the input supervoxels
329  * \param[in] supervoxel_clusters Supervoxel cluster map coming from this class
330  * \returns Cloud of PointNormals of the supervoxels
331  *
332  */
334  makeSupervoxelNormalCloud (std::map<uint32_t,typename Supervoxel<PointT>::Ptr > &supervoxel_clusters);
335 
336  /** \brief Returns the current maximum (highest) label */
337  int
338  getMaxLabel () const;
339 
340  private:
341  /** \brief This method simply checks if it is possible to execute the segmentation algorithm with
342  * the current settings. If it is possible then it returns true.
343  */
344  virtual bool
345  prepareForSegmentation ();
346 
347  /** \brief This selects points to use as initial supervoxel centroids
348  * \param[out] seed_indices The selected leaf indices
349  */
350  void
351  selectInitialSupervoxelSeeds (std::vector<int> &seed_indices);
352 
353  /** \brief This method creates the internal supervoxel helpers based on the provided seed points
354  * \param[in] seed_indices Indices of the leaves to use as seeds
355  */
356  void
357  createSupervoxelHelpers (std::vector<int> &seed_indices);
358 
359  /** \brief This performs the superpixel evolution */
360  void
361  expandSupervoxels (int depth);
362 
363  /** \brief This sets the data of the voxels in the tree */
364  void
365  computeVoxelData ();
366 
367  /** \brief Reseeds the supervoxels by finding the voxel closest to current centroid */
368  void
369  reseedSupervoxels ();
370 
371  /** \brief Constructs the map of supervoxel clusters from the internal supervoxel helpers */
372  void
373  makeSupervoxels (std::map<uint32_t,typename Supervoxel<PointT>::Ptr > &supervoxel_clusters);
374 
375  /** \brief Stores the resolution used in the octree */
376  float resolution_;
377 
378  /** \brief Stores the resolution used to seed the superpixels */
379  float seed_resolution_;
380 
381  /** \brief Distance function used for comparing voxelDatas */
382  float
383  voxelDataDistance (const VoxelData &v1, const VoxelData &v2) const;
384 
385  /** \brief Transform function used to normalize voxel density versus distance from camera */
386  void
387  transformFunction (PointT &p);
388 
389  /** \brief Contains a KDtree for the voxelized cloud */
390  typename pcl::search::KdTree<PointT>::Ptr voxel_kdtree_;
391 
392  /** \brief Octree Adjacency structure with leaves at voxel resolution */
393  typename OctreeAdjacencyT::Ptr adjacency_octree_;
394 
395  /** \brief Contains the Voxelized centroid Cloud */
396  typename PointCloudT::Ptr voxel_centroid_cloud_;
397 
398  /** \brief Contains the Voxelized centroid Cloud */
399  typename NormalCloudT::ConstPtr input_normals_;
400 
401  /** \brief Importance of color in clustering */
402  float color_importance_;
403  /** \brief Importance of distance from seed center in clustering */
404  float spatial_importance_;
405  /** \brief Importance of similarity in normals for clustering */
406  float normal_importance_;
407 
408  /** \brief Whether or not to use the transform compressing depth in Z
409  * This is only checked if it has been manually set by the user.
410  * The default behavior is to use the transform for organized, and not for unorganized.
411  */
412  bool use_single_camera_transform_;
413  /** \brief Whether to use default transform behavior or not */
414  bool use_default_transform_behaviour_;
415 
416  /** \brief Internal storage class for supervoxels
417  * \note Stores pointers to leaves of clustering internal octree,
418  * \note so should not be used outside of clustering class
419  */
420  class SupervoxelHelper
421  {
422  public:
423  /** \brief Comparator for LeafContainerT pointers - used for sorting set of leaves
424  * \note Compares by index in the overall leaf_vector. Order isn't important, so long as it is fixed.
425  */
427  {
428  bool operator() (LeafContainerT* const &left, LeafContainerT* const &right) const
429  {
430  const VoxelData& leaf_data_left = left->getData ();
431  const VoxelData& leaf_data_right = right->getData ();
432  return leaf_data_left.idx_ < leaf_data_right.idx_;
433  }
434  };
435  typedef std::set<LeafContainerT*, typename SupervoxelHelper::compareLeaves> LeafSetT;
436  typedef typename LeafSetT::iterator iterator;
437  typedef typename LeafSetT::const_iterator const_iterator;
438 
439  SupervoxelHelper (uint32_t label, SupervoxelClustering* parent_arg):
440  label_ (label),
441  parent_ (parent_arg)
442  { }
443 
444  void
445  addLeaf (LeafContainerT* leaf_arg);
446 
447  void
448  removeLeaf (LeafContainerT* leaf_arg);
449 
450  void
451  removeAllLeaves ();
452 
453  void
454  expand ();
455 
456  void
457  refineNormals ();
458 
459  void
460  updateCentroid ();
461 
462  void
463  getVoxels (typename pcl::PointCloud<PointT>::Ptr &voxels) const;
464 
465  void
466  getNormals (typename pcl::PointCloud<Normal>::Ptr &normals) const;
467 
468  typedef float (SupervoxelClustering::*DistFuncPtr)(const VoxelData &v1, const VoxelData &v2);
469 
470  uint32_t
471  getLabel () const
472  { return label_; }
473 
474  Eigen::Vector4f
475  getNormal () const
476  { return centroid_.normal_; }
477 
478  Eigen::Vector3f
479  getRGB () const
480  { return centroid_.rgb_; }
481 
482  Eigen::Vector3f
483  getXYZ () const
484  { return centroid_.xyz_;}
485 
486  void
487  getXYZ (float &x, float &y, float &z) const
488  { x=centroid_.xyz_[0]; y=centroid_.xyz_[1]; z=centroid_.xyz_[2]; }
489 
490  void
491  getRGB (uint32_t &rgba) const
492  {
493  rgba = static_cast<uint32_t>(centroid_.rgb_[0]) << 16 |
494  static_cast<uint32_t>(centroid_.rgb_[1]) << 8 |
495  static_cast<uint32_t>(centroid_.rgb_[2]);
496  }
497 
498  void
499  getNormal (pcl::Normal &normal_arg) const
500  {
501  normal_arg.normal_x = centroid_.normal_[0];
502  normal_arg.normal_y = centroid_.normal_[1];
503  normal_arg.normal_z = centroid_.normal_[2];
504  normal_arg.curvature = centroid_.curvature_;
505  }
506 
507  void
508  getNeighborLabels (std::set<uint32_t> &neighbor_labels) const;
509 
510  VoxelData
511  getCentroid () const
512  { return centroid_; }
513 
514  size_t
515  size () const { return leaves_.size (); }
516  private:
517  //Stores leaves
518  LeafSetT leaves_;
519  uint32_t label_;
521  SupervoxelClustering* parent_;
522  public:
523  //Type VoxelData may have fixed-size Eigen objects inside
524  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
525  };
526 
527  //Make boost::ptr_list can access the private class SupervoxelHelper
528  friend void boost::checked_delete<> (const typename pcl::SupervoxelClustering<PointT>::SupervoxelHelper *);
529 
530  typedef boost::ptr_list<SupervoxelHelper> HelperListT;
531  HelperListT supervoxel_helpers_;
532 
533  //TODO DEBUG REMOVE
534  StopWatch timer_;
535  public:
536  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
537 
538  };
539 
540 }
541 
542 #ifdef PCL_NO_PRECOMPILE
543 #include <pcl/segmentation/impl/supervoxel_clustering.hpp>
544 #endif
545 
546 #endif
A point structure representing normal coordinates and the surface curvature estimate.
pcl::octree::OctreePointCloudAdjacency< PointT, LeafContainerT > OctreeAdjacencyT
pcl::PointCloud< PointT >::Ptr voxels_
A Pointcloud of the voxels in the supervoxel.
Octree adjacency leaf container class- stores a list of pointers to neighbors, number of points added...
pcl::PointXYZRGBA centroid_
The centroid of the supervoxel - average voxel.
Octree pointcloud voxel class which maintains adjacency information for its voxels.
void getCentroidPointNormal(PointNormal &normal_arg)
Gets the point normal for the supervoxel.
pcl::Normal normal_
The normal calculated for the voxels contained in the supervoxel.
VoxelAdjacencyList::vertex_descriptor VoxelID
pcl::PointCloud< PointT > PointCloudT
boost::shared_ptr< std::vector< int > > IndicesPtr
A point structure representing Euclidean xyz coordinates, and the RGBA color.
boost::shared_ptr< const Supervoxel< PointT > > ConstPtr
Supervoxel container class - stores a cluster extracted using supervoxel clustering.
boost::shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:428
pcl::PointCloud< pcl::PointXYZRGBA >::Ptr getColoredVoxelCloud() const
Returns an RGB colorized voxelized cloud showing superpixels Otherwise it returns an empty pointer...
boost::shared_ptr< KdTree< PointT, Tree > > Ptr
Definition: kdtree.h:79
Defines all the PCL implemented PointT point type structures.
PCL base class.
Definition: pcl_base.h:68
pcl::octree::OctreePointCloudSearch< PointT > OctreeSearchT
VoxelData is a structure used for storing data within a pcl::octree::OctreePointCloudAdjacencyContain...
std::vector< LeafContainerT * > LeafVectorT
boost::shared_ptr< const PointCloud< PointT > > ConstPtr
Definition: point_cloud.h:429
pcl::search::KdTree< PointT > KdTreeT
void getCentroidPoint(PointXYZRGBA &centroid_arg)
Gets the centroid of the supervoxel.
PointCloud represents the base class in PCL for storing collections of 3D points. ...
Implements a supervoxel algorithm based on voxel structure, normals, and rgb values.
pcl::PointCloud< Normal > NormalCloudT
Comparator for LeafContainerT pointers - used for sorting set of leaves.
A point structure representing Euclidean xyz coordinates, together with normal coordinates and the su...
DataT & getData()
Returns a reference to the data member to access it without copying.
boost::shared_ptr< OctreeAdjacencyT > Ptr
Octree pointcloud search class
Definition: octree_search.h:58
VoxelAdjacencyList::edge_descriptor EdgeID
Simple stopwatch.
Definition: time.h:65
pcl::octree::OctreePointCloudAdjacencyContainer< PointT, VoxelData > LeafContainerT
pcl::PointCloud< Normal >::Ptr normals_
A Pointcloud of the normals for the points in the supervoxel.
PCL_EXPORTS int save(const std::string &file_name, const pcl::PCLPointCloud2 &blob, unsigned precision=5)
Save point cloud data to a binary file when available else to ASCII.
A point structure representing Euclidean xyz coordinates, and the RGB color.
boost::shared_ptr< Supervoxel< PointT > > Ptr
boost::adjacency_list< boost::setS, boost::setS, boost::undirectedS, uint32_t, float > VoxelAdjacencyList
Define methods for measuring time spent in code blocks.