Point Cloud Library (PCL) 1.14.0
Loading...
Searching...
No Matches
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#pragma once
42
43#include <boost/version.hpp>
44
45#include <pcl/features/normal_3d.h>
46#include <pcl/memory.h>
47#include <pcl/pcl_base.h>
48#include <pcl/pcl_macros.h>
49#include <pcl/point_cloud.h>
50#include <pcl/point_types.h>
51#include <pcl/octree/octree_search.h>
52#include <pcl/octree/octree_pointcloud_adjacency.h>
53#include <pcl/search/search.h>
54#include <boost/ptr_container/ptr_list.hpp> // for ptr_list
55
56
57
58//DEBUG TODO REMOVE
59#include <pcl/common/time.h>
60
61
62namespace pcl
63{
64 /** \brief Supervoxel container class - stores a cluster extracted using supervoxel clustering
65 */
66 template <typename PointT>
68 {
69 public:
71 voxels_ (new pcl::PointCloud<PointT> ()),
72 normals_ (new pcl::PointCloud<Normal> ())
73 { }
74
75 using Ptr = shared_ptr<Supervoxel<PointT> >;
76 using ConstPtr = shared_ptr<const Supervoxel<PointT> >;
77
78 /** \brief Gets the centroid of the supervoxel
79 * \param[out] centroid_arg centroid of the supervoxel
80 */
81 void
83 {
84 centroid_arg = centroid_;
85 }
86
87 /** \brief Gets the point normal for the supervoxel
88 * \param[out] normal_arg Point normal of the supervoxel
89 * \note This isn't an average, it is a normal computed using all of the voxels in the supervoxel as support
90 */
91 void
93 {
94 normal_arg.x = centroid_.x;
95 normal_arg.y = centroid_.y;
96 normal_arg.z = centroid_.z;
97 normal_arg.normal_x = normal_.normal_x;
98 normal_arg.normal_y = normal_.normal_y;
99 normal_arg.normal_z = normal_.normal_z;
100 normal_arg.curvature = normal_.curvature;
101 }
102
103 /** \brief The normal calculated for the voxels contained in the supervoxel */
105 /** \brief The centroid of the supervoxel - average voxel */
107 /** \brief A Pointcloud of the voxels in the supervoxel */
109 /** \brief A Pointcloud of the normals for the points in the supervoxel */
111
112 public:
114 };
115
116 /** \brief Implements a supervoxel algorithm based on voxel structure, normals, and rgb values
117 * \note Supervoxels are oversegmented volumetric patches (usually surfaces)
118 * \note Usually, color isn't needed (and can be detrimental)- spatial structure is mainly used
119 * - J. Papon, A. Abramov, M. Schoeler, F. Woergoetter
120 * Voxel Cloud Connectivity Segmentation - Supervoxels from PointClouds
121 * In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2013
122 * \ingroup segmentation
123 * \author Jeremie Papon (jpapon@gmail.com)
124 */
125 template <typename PointT>
126 class PCL_EXPORTS SupervoxelClustering : public pcl::PCLBase<PointT>
127 {
128 //Forward declaration of friended helper class
129 class SupervoxelHelper;
130 friend class SupervoxelHelper;
131 public:
132 /** \brief VoxelData is a structure used for storing data within a pcl::octree::OctreePointCloudAdjacencyContainer
133 * \note It stores xyz, rgb, normal, distance, an index, and an owner.
134 */
136 {
137 public:
139 xyz_ (0.0f, 0.0f, 0.0f),
140 rgb_ (0.0f, 0.0f, 0.0f),
141 normal_ (0.0f, 0.0f, 0.0f, 0.0f),
142
143 owner_ (nullptr)
144 {}
145
146 /** \brief Gets the data of in the form of a point
147 * \param[out] point_arg Will contain the point value of the voxeldata
148 */
149 void
150 getPoint (PointT &point_arg) const;
151
152 /** \brief Gets the data of in the form of a normal
153 * \param[out] normal_arg Will contain the normal value of the voxeldata
154 */
155 void
156 getNormal (Normal &normal_arg) const;
157
158 Eigen::Vector3f xyz_;
159 Eigen::Vector3f rgb_;
160 Eigen::Vector4f normal_;
161 float curvature_{0.0f};
162 float distance_{0.0f};
163 int idx_{0};
164 SupervoxelHelper* owner_;
165
166 public:
168 };
169
171 using LeafVectorT = std::vector<LeafContainerT *>;
172
179
180 using PCLBase <PointT>::initCompute;
181 using PCLBase <PointT>::deinitCompute;
182 using PCLBase <PointT>::input_;
183
184 using VoxelAdjacencyList = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, std::uint32_t, float>;
185 using VoxelID = VoxelAdjacencyList::vertex_descriptor;
186 using EdgeID = VoxelAdjacencyList::edge_descriptor;
187
188 public:
189
190 /** \brief Constructor that sets default values for member variables.
191 * \param[in] voxel_resolution The resolution (in meters) of voxels used
192 * \param[in] seed_resolution The average size (in meters) of resulting supervoxels
193 */
194 SupervoxelClustering (float voxel_resolution, float seed_resolution);
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
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<std::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 void
254 setInputCloud (const typename pcl::PointCloud<PointT>::ConstPtr& cloud) override;
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<std::uint32_t,typename Supervoxel<PointT>::Ptr > &supervoxel_clusters);
268
269 ////////////////////////////////////////////////////////////
270 /** \brief Returns a deep copy of the voxel centroid cloud */
272 getVoxelCentroidCloud () const;
273
274 /** \brief Returns labeled cloud
275 * Points that belong to the same supervoxel have the same label.
276 * Labels for segments start from 1, unlabeled points have label 0
277 */
279 getLabeledCloud () const;
280
281 /** \brief Returns labeled voxelized cloud
282 * Points that belong to the same supervoxel have the same label.
283 * Labels for segments start from 1, unlabeled points have label 0
284 */
286 getLabeledVoxelCloud () const;
287
288 /** \brief Gets the adjacency list (Boost Graph library) which gives connections between supervoxels
289 * \param[out] adjacency_list_arg BGL graph where supervoxel labels are vertices, edges are touching relationships
290 */
291 void
292 getSupervoxelAdjacencyList (VoxelAdjacencyList &adjacency_list_arg) const;
293
294 /** \brief Get a multimap which gives supervoxel adjacency
295 * \param[out] label_adjacency Multi-Map which maps a supervoxel label to all adjacent supervoxel labels
296 */
297 void
298 getSupervoxelAdjacency (std::multimap<std::uint32_t, std::uint32_t> &label_adjacency) const;
299
300 /** \brief Static helper function which returns a pointcloud of normals for the input supervoxels
301 * \param[in] supervoxel_clusters Supervoxel cluster map coming from this class
302 * \returns Cloud of PointNormals of the supervoxels
303 *
304 */
306 makeSupervoxelNormalCloud (std::map<std::uint32_t,typename Supervoxel<PointT>::Ptr > &supervoxel_clusters);
307
308 /** \brief Returns the current maximum (highest) label */
309 int
310 getMaxLabel () const;
311
312 private:
313 /** \brief This method simply checks if it is possible to execute the segmentation algorithm with
314 * the current settings. If it is possible then it returns true.
315 */
316 virtual bool
317 prepareForSegmentation ();
318
319 /** \brief This selects points to use as initial supervoxel centroids
320 * \param[out] seed_indices The selected leaf indices
321 */
322 void
323 selectInitialSupervoxelSeeds (Indices &seed_indices);
324
325 /** \brief This method creates the internal supervoxel helpers based on the provided seed points
326 * \param[in] seed_indices Indices of the leaves to use as seeds
327 */
328 void
329 createSupervoxelHelpers (Indices &seed_indices);
330
331 /** \brief This performs the superpixel evolution */
332 void
333 expandSupervoxels (int depth);
334
335 /** \brief This sets the data of the voxels in the tree */
336 void
337 computeVoxelData ();
338
339 /** \brief Reseeds the supervoxels by finding the voxel closest to current centroid */
340 void
341 reseedSupervoxels ();
342
343 /** \brief Constructs the map of supervoxel clusters from the internal supervoxel helpers */
344 void
345 makeSupervoxels (std::map<std::uint32_t,typename Supervoxel<PointT>::Ptr > &supervoxel_clusters);
346
347 /** \brief Stores the resolution used in the octree */
348 float resolution_;
349
350 /** \brief Stores the resolution used to seed the superpixels */
351 float seed_resolution_;
352
353 /** \brief Distance function used for comparing voxelDatas */
354 float
355 voxelDataDistance (const VoxelData &v1, const VoxelData &v2) const;
356
357 /** \brief Transform function used to normalize voxel density versus distance from camera */
358 void
359 transformFunction (PointT &p);
360
361 /** \brief Contains a KDtree for the voxelized cloud */
362 typename pcl::search::KdTree<PointT>::Ptr voxel_kdtree_;
363
364 /** \brief Octree Adjacency structure with leaves at voxel resolution */
365 typename OctreeAdjacencyT::Ptr adjacency_octree_;
366
367 /** \brief Contains the Voxelized centroid Cloud */
368 typename PointCloudT::Ptr voxel_centroid_cloud_;
369
370 /** \brief Contains the Voxelized centroid Cloud */
371 typename NormalCloudT::ConstPtr input_normals_;
372
373 /** \brief Importance of color in clustering */
374 float color_importance_{0.1f};
375 /** \brief Importance of distance from seed center in clustering */
376 float spatial_importance_{0.4f};
377 /** \brief Importance of similarity in normals for clustering */
378 float normal_importance_{1.0f};
379
380 /** \brief Whether or not to use the transform compressing depth in Z
381 * This is only checked if it has been manually set by the user.
382 * The default behavior is to use the transform for organized, and not for unorganized.
383 */
384 bool use_single_camera_transform_;
385 /** \brief Whether to use default transform behavior or not */
386 bool use_default_transform_behaviour_{true};
387
388 /** \brief Internal storage class for supervoxels
389 * \note Stores pointers to leaves of clustering internal octree,
390 * \note so should not be used outside of clustering class
391 */
392 class SupervoxelHelper
393 {
394 public:
395 /** \brief Comparator for LeafContainerT pointers - used for sorting set of leaves
396 * \note Compares by index in the overall leaf_vector. Order isn't important, so long as it is fixed.
397 */
399 {
400 bool operator() (LeafContainerT* const &left, LeafContainerT* const &right) const
401 {
402 const VoxelData& leaf_data_left = left->getData ();
403 const VoxelData& leaf_data_right = right->getData ();
404 return leaf_data_left.idx_ < leaf_data_right.idx_;
405 }
406 };
407 using LeafSetT = std::set<LeafContainerT*, typename SupervoxelHelper::compareLeaves>;
408 using iterator = typename LeafSetT::iterator;
409 using const_iterator = typename LeafSetT::const_iterator;
410
411 SupervoxelHelper (std::uint32_t label, SupervoxelClustering* parent_arg):
412 label_ (label),
413 parent_ (parent_arg)
414 { }
415
416 void
417 addLeaf (LeafContainerT* leaf_arg);
418
419 void
420 removeLeaf (LeafContainerT* leaf_arg);
421
422 void
423 removeAllLeaves ();
424
425 void
426 expand ();
427
428 void
429 refineNormals ();
430
431 void
432 updateCentroid ();
433
434 void
435 getVoxels (typename pcl::PointCloud<PointT>::Ptr &voxels) const;
436
437 void
438 getNormals (typename pcl::PointCloud<Normal>::Ptr &normals) const;
439
440 using DistFuncPtr = float (SupervoxelClustering<PointT>::*)(const VoxelData &, const VoxelData &);
441
442 std::uint32_t
443 getLabel () const
444 { return label_; }
445
446 Eigen::Vector4f
447 getNormal () const
448 { return centroid_.normal_; }
449
450 Eigen::Vector3f
451 getRGB () const
452 { return centroid_.rgb_; }
453
454 Eigen::Vector3f
455 getXYZ () const
456 { return centroid_.xyz_;}
457
458 void
459 getXYZ (float &x, float &y, float &z) const
460 { x=centroid_.xyz_[0]; y=centroid_.xyz_[1]; z=centroid_.xyz_[2]; }
461
462 void
463 getRGB (std::uint32_t &rgba) const
464 {
465 rgba = static_cast<std::uint32_t>(centroid_.rgb_[0]) << 16 |
466 static_cast<std::uint32_t>(centroid_.rgb_[1]) << 8 |
467 static_cast<std::uint32_t>(centroid_.rgb_[2]);
468 }
469
470 void
471 getNormal (pcl::Normal &normal_arg) const
472 {
473 normal_arg.normal_x = centroid_.normal_[0];
474 normal_arg.normal_y = centroid_.normal_[1];
475 normal_arg.normal_z = centroid_.normal_[2];
476 normal_arg.curvature = centroid_.curvature_;
477 }
478
479 void
480 getNeighborLabels (std::set<std::uint32_t> &neighbor_labels) const;
481
482 VoxelData
483 getCentroid () const
484 { return centroid_; }
485
486 std::size_t
487 size () const { return leaves_.size (); }
488 private:
489 //Stores leaves
490 LeafSetT leaves_;
491 std::uint32_t label_;
492 VoxelData centroid_;
493 SupervoxelClustering* parent_;
494 public:
495 //Type VoxelData may have fixed-size Eigen objects inside
497 };
498
499 //Make boost::ptr_list can access the private class SupervoxelHelper
500#if BOOST_VERSION >= 107000
501 friend void boost::checked_delete<> (const typename pcl::SupervoxelClustering<PointT>::SupervoxelHelper *) BOOST_NOEXCEPT;
502#else
503 friend void boost::checked_delete<> (const typename pcl::SupervoxelClustering<PointT>::SupervoxelHelper *);
504#endif
505
506 using HelperListT = boost::ptr_list<SupervoxelHelper>;
507 HelperListT supervoxel_helpers_;
508
509 //TODO DEBUG REMOVE
510 StopWatch timer_;
511 public:
513 };
514
515}
516
517#ifdef PCL_NO_PRECOMPILE
518#include <pcl/segmentation/impl/supervoxel_clustering.hpp>
519#endif
PCL base class.
Definition pcl_base.h:70
PointCloud represents the base class in PCL for storing collections of 3D points.
shared_ptr< PointCloud< PointT > > Ptr
shared_ptr< const PointCloud< PointT > > ConstPtr
Simple stopwatch.
Definition time.h:59
VoxelData is a structure used for storing data within a pcl::octree::OctreePointCloudAdjacencyContain...
Implements a supervoxel algorithm based on voxel structure, normals, and rgb values.
VoxelAdjacencyList::edge_descriptor EdgeID
std::vector< LeafContainerT * > LeafVectorT
pcl::PointCloud< PointT > PointCloudT
boost::adjacency_list< boost::setS, boost::setS, boost::undirectedS, std::uint32_t, float > VoxelAdjacencyList
VoxelAdjacencyList::vertex_descriptor VoxelID
~SupervoxelClustering() override
This destructor destroys the cloud, normals and search method used for finding neighbors.
Supervoxel container class - stores a cluster extracted using supervoxel clustering.
pcl::PointXYZRGBA centroid_
The centroid of the supervoxel - average voxel.
pcl::PointCloud< Normal >::Ptr normals_
A Pointcloud of the normals for the points in the supervoxel.
shared_ptr< const Supervoxel< PointT > > ConstPtr
void getCentroidPoint(PointXYZRGBA &centroid_arg)
Gets the centroid of the supervoxel.
shared_ptr< Supervoxel< PointT > > Ptr
pcl::PointCloud< PointT >::Ptr voxels_
A Pointcloud of the voxels in the supervoxel.
pcl::Normal normal_
The normal calculated for the voxels contained in the supervoxel.
void getCentroidPointNormal(PointNormal &normal_arg)
Gets the point normal for the supervoxel.
Octree adjacency leaf container class- stores a list of pointers to neighbors, number of points added...
DataT & getData()
Returns a reference to the data member to access it without copying.
Octree pointcloud voxel class which maintains adjacency information for its voxels.
Octree pointcloud search class
search::KdTree is a wrapper class which inherits the pcl::KdTree class for performing search function...
Definition kdtree.h:62
shared_ptr< KdTree< PointT, Tree > > Ptr
Definition kdtree.h:75
Defines all the PCL implemented PointT point type structures.
Define methods for measuring time spent in code blocks.
#define PCL_MAKE_ALIGNED_OPERATOR_NEW
Macro to signal a class requires a custom allocator.
Definition memory.h:63
Defines functions, macros and traits for allocating and using memory.
IndicesAllocator<> Indices
Type used for indices in PCL.
Definition types.h:133
shared_ptr< Indices > IndicesPtr
Definition pcl_base.h:58
Defines all the PCL and non-PCL macros used.
A point structure representing normal coordinates and the surface curvature estimate.
A point structure representing Euclidean xyz coordinates, together with normal coordinates and the su...
A point structure representing Euclidean xyz coordinates, and the RGBA color.
A point structure representing Euclidean xyz coordinates, and the RGB color.
Comparator for LeafContainerT pointers - used for sorting set of leaves.