Point Cloud Library (PCL)  1.11.1-dev
region_growing.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  * Author : Sergey Ushakov
36  * Email : mine_all_mine@bk.ru
37  *
38  */
39 
40 #pragma once
41 
42 #include <pcl/memory.h>
43 #include <pcl/pcl_base.h>
44 #include <pcl/pcl_macros.h>
45 #include <pcl/search/search.h>
46 #include <pcl/point_cloud.h>
47 #include <pcl/point_types.h>
48 #include <list>
49 #include <cmath>
50 #include <ctime>
51 
52 namespace pcl
53 {
54  /** \brief
55  * Implements the well known Region Growing algorithm used for segmentation.
56  * Description can be found in the article
57  * "Segmentation of point clouds using smoothness constraint"
58  * by T. Rabbania, F. A. van den Heuvelb, G. Vosselmanc.
59  * In addition to residual test, the possibility to test curvature is added.
60  */
61  template <typename PointT, typename NormalT>
62  class PCL_EXPORTS RegionGrowing : public pcl::PCLBase<PointT>
63  {
64  public:
65 
67  using KdTreePtr = typename KdTree::Ptr;
69  using NormalPtr = typename Normal::Ptr;
71 
76 
77  public:
78 
79  /** \brief Constructor that sets default values for member variables. */
80  RegionGrowing ();
81 
82  /** \brief This destructor destroys the cloud, normals and search method used for
83  * finding KNN. In other words it frees memory.
84  */
85 
86  ~RegionGrowing ();
87 
88  /** \brief Get the minimum number of points that a cluster needs to contain in order to be considered valid. */
89  int
90  getMinClusterSize ();
91 
92  /** \brief Set the minimum number of points that a cluster needs to contain in order to be considered valid. */
93  void
94  setMinClusterSize (int min_cluster_size);
95 
96  /** \brief Get the maximum number of points that a cluster needs to contain in order to be considered valid. */
97  int
98  getMaxClusterSize ();
99 
100  /** \brief Set the maximum number of points that a cluster needs to contain in order to be considered valid. */
101  void
102  setMaxClusterSize (int max_cluster_size);
103 
104  /** \brief Returns the flag value. This flag signalizes which mode of algorithm will be used.
105  * If it is set to true than it will work as said in the article. This means that
106  * it will be testing the angle between normal of the current point and it's neighbours normal.
107  * Otherwise, it will be testing the angle between normal of the current point
108  * and normal of the initial point that was chosen for growing new segment.
109  */
110  bool
111  getSmoothModeFlag () const;
112 
113  /** \brief This function allows to turn on/off the smoothness constraint.
114  * \param[in] value new mode value, if set to true then the smooth version will be used.
115  */
116  void
117  setSmoothModeFlag (bool value);
118 
119  /** \brief Returns the flag that signalize if the curvature test is turned on/off. */
120  bool
121  getCurvatureTestFlag () const;
122 
123  /** \brief Allows to turn on/off the curvature test. Note that at least one test
124  * (residual or curvature) must be turned on. If you are turning curvature test off
125  * then residual test will be turned on automatically.
126  * \param[in] value new value for curvature test. If set to true then the test will be turned on
127  */
128  virtual void
129  setCurvatureTestFlag (bool value);
130 
131  /** \brief Returns the flag that signalize if the residual test is turned on/off. */
132  bool
133  getResidualTestFlag () const;
134 
135  /** \brief
136  * Allows to turn on/off the residual test. Note that at least one test
137  * (residual or curvature) must be turned on. If you are turning residual test off
138  * then curvature test will be turned on automatically.
139  * \param[in] value new value for residual test. If set to true then the test will be turned on
140  */
141  virtual void
142  setResidualTestFlag (bool value);
143 
144  /** \brief Returns smoothness threshold. */
145  float
146  getSmoothnessThreshold () const;
147 
148  /** \brief Allows to set smoothness threshold used for testing the points.
149  * \param[in] theta new threshold value for the angle between normals
150  */
151  void
152  setSmoothnessThreshold (float theta);
153 
154  /** \brief Returns residual threshold. */
155  float
156  getResidualThreshold () const;
157 
158  /** \brief Allows to set residual threshold used for testing the points.
159  * \param[in] residual new threshold value for residual testing
160  */
161  void
162  setResidualThreshold (float residual);
163 
164  /** \brief Returns curvature threshold. */
165  float
166  getCurvatureThreshold () const;
167 
168  /** \brief Allows to set curvature threshold used for testing the points.
169  * \param[in] curvature new threshold value for curvature testing
170  */
171  void
172  setCurvatureThreshold (float curvature);
173 
174  /** \brief Returns the number of nearest neighbours used for KNN. */
175  unsigned int
176  getNumberOfNeighbours () const;
177 
178  /** \brief Allows to set the number of neighbours. For more information check the article.
179  * \param[in] neighbour_number number of neighbours to use
180  */
181  void
182  setNumberOfNeighbours (unsigned int neighbour_number);
183 
184  /** \brief Returns the pointer to the search method that is used for KNN. */
185  KdTreePtr
186  getSearchMethod () const;
187 
188  /** \brief Allows to set search method that will be used for finding KNN.
189  * \param[in] tree pointer to a KdTree
190  */
191  void
192  setSearchMethod (const KdTreePtr& tree);
193 
194  /** \brief Returns normals. */
195  NormalPtr
196  getInputNormals () const;
197 
198  /** \brief This method sets the normals. They are needed for the algorithm, so if
199  * no normals will be set, the algorithm would not be able to segment the points.
200  * \param[in] norm normals that will be used in the algorithm
201  */
202  void
203  setInputNormals (const NormalPtr& norm);
204 
205  /** \brief This method launches the segmentation algorithm and returns the clusters that were
206  * obtained during the segmentation.
207  * \param[out] clusters clusters that were obtained. Each cluster is an array of point indices.
208  */
209  virtual void
210  extract (std::vector <pcl::PointIndices>& clusters);
211 
212  /** \brief For a given point this function builds a segment to which it belongs and returns this segment.
213  * \param[in] index index of the initial point which will be the seed for growing a segment.
214  * \param[out] cluster cluster to which the point belongs.
215  */
216  virtual void
217  getSegmentFromPoint (int index, pcl::PointIndices& cluster);
218 
219  /** \brief If the cloud was successfully segmented, then function
220  * returns colored cloud. Otherwise it returns an empty pointer.
221  * Points that belong to the same segment have the same color.
222  * But this function doesn't guarantee that different segments will have different
223  * color(it all depends on RNG). Points that were not listed in the indices array will have red color.
224  */
226  getColoredCloud ();
227 
228  /** \brief If the cloud was successfully segmented, then function
229  * returns colored cloud. Otherwise it returns an empty pointer.
230  * Points that belong to the same segment have the same color.
231  * But this function doesn't guarantee that different segments will have different
232  * color(it all depends on RNG). Points that were not listed in the indices array will have red color.
233  */
235  getColoredCloudRGBA ();
236 
237  protected:
238 
239  /** \brief This method simply checks if it is possible to execute the segmentation algorithm with
240  * the current settings. If it is possible then it returns true.
241  */
242  virtual bool
243  prepareForSegmentation ();
244 
245  /** \brief This method finds KNN for each point and saves them to the array
246  * because the algorithm needs to find KNN a few times.
247  */
248  virtual void
249  findPointNeighbours ();
250 
251  /** \brief This function implements the algorithm described in the article
252  * "Segmentation of point clouds using smoothness constraint"
253  * by T. Rabbania, F. A. van den Heuvelb, G. Vosselmanc.
254  */
255  void
256  applySmoothRegionGrowingAlgorithm ();
257 
258  /** \brief This method grows a segment for the given seed point. And returns the number of its points.
259  * \param[in] initial_seed index of the point that will serve as the seed point
260  * \param[in] segment_number indicates which number this segment will have
261  */
262  int
263  growRegion (int initial_seed, int segment_number);
264 
265  /** \brief This function is checking if the point with index 'nghbr' belongs to the segment.
266  * If so, then it returns true. It also checks if this point can serve as the seed.
267  * \param[in] initial_seed index of the initial point that was passed to the growRegion() function
268  * \param[in] point index of the current seed point
269  * \param[in] nghbr index of the point that is neighbour of the current seed
270  * \param[out] is_a_seed this value is set to true if the point with index 'nghbr' can serve as the seed
271  */
272  virtual bool
273  validatePoint (int initial_seed, int point, int nghbr, bool& is_a_seed) const;
274 
275  /** \brief This function simply assembles the regions from list of point labels.
276  * Each cluster is an array of point indices.
277  */
278  void
279  assembleRegions ();
280 
281  protected:
282 
283  /** \brief Stores the minimum number of points that a cluster needs to contain in order to be considered valid. */
285 
286  /** \brief Stores the maximum number of points that a cluster needs to contain in order to be considered valid. */
288 
289  /** \brief Flag that signalizes if the smoothness constraint will be used. */
291 
292  /** \brief If set to true then curvature test will be done during segmentation. */
294 
295  /** \brief If set to true then residual test will be done during segmentation. */
297 
298  /** \brief Thershold used for testing the smoothness between points. */
300 
301  /** \brief Thershold used in residual test. */
303 
304  /** \brief Thershold used in curvature test. */
306 
307  /** \brief Number of neighbours to find. */
308  unsigned int neighbour_number_;
309 
310  /** \brief Serch method that will be used for KNN. */
312 
313  /** \brief Contains normals of the points that will be segmented. */
315 
316  /** \brief Contains neighbours of each point. */
317  std::vector<std::vector<int> > point_neighbours_;
318 
319  /** \brief Point labels that tells to which segment each point belongs. */
320  std::vector<int> point_labels_;
321 
322  /** \brief If set to true then normal/smoothness test will be done during segmentation.
323  * It is always set to true for the usual region growing algorithm. It is used for turning on/off the test
324  * for smoothness in the child class RegionGrowingRGB.*/
326 
327  /** \brief Tells how much points each segment contains. Used for reserving memory. */
328  std::vector<int> num_pts_in_segment_;
329 
330  /** \brief After the segmentation it will contain the segments. */
331  std::vector <pcl::PointIndices> clusters_;
332 
333  /** \brief Stores the number of segments. */
335 
336  public:
338  };
339 
340  /** \brief This function is used as a comparator for sorting. */
341  inline bool
342  comparePair (std::pair<float, int> i, std::pair<float, int> j)
343  {
344  return (i.first < j.first);
345  }
346 }
347 
348 #ifdef PCL_NO_PRECOMPILE
349 #include <pcl/segmentation/impl/region_growing.hpp>
350 #endif
pcl::search::Search
Generic search class.
Definition: search.h:74
pcl_macros.h
Defines all the PCL and non-PCL macros used.
pcl
Definition: convolution.h:46
point_types.h
pcl::RegionGrowing::normal_flag_
bool normal_flag_
If set to true then normal/smoothness test will be done during segmentation.
Definition: region_growing.h:325
pcl::RegionGrowing< PointT, pcl::Normal >::KdTreePtr
typename KdTree::Ptr KdTreePtr
Definition: region_growing.h:67
pcl::RegionGrowing::curvature_flag_
bool curvature_flag_
If set to true then curvature test will be done during segmentation.
Definition: region_growing.h:293
pcl::RegionGrowing::normals_
NormalPtr normals_
Contains normals of the points that will be segmented.
Definition: region_growing.h:314
pcl::RegionGrowing::clusters_
std::vector< pcl::PointIndices > clusters_
After the segmentation it will contain the segments.
Definition: region_growing.h:331
pcl::PCLBase
PCL base class.
Definition: pcl_base.h:69
pcl::PointCloud< pcl::Normal >
pcl::RegionGrowing::theta_threshold_
float theta_threshold_
Thershold used for testing the smoothness between points.
Definition: region_growing.h:299
pcl::RegionGrowing::residual_threshold_
float residual_threshold_
Thershold used in residual test.
Definition: region_growing.h:302
pcl::RegionGrowing< PointT, pcl::Normal >::NormalPtr
typename Normal::Ptr NormalPtr
Definition: region_growing.h:69
pcl::RegionGrowing::residual_flag_
bool residual_flag_
If set to true then residual test will be done during segmentation.
Definition: region_growing.h:296
pcl::RegionGrowing::num_pts_in_segment_
std::vector< int > num_pts_in_segment_
Tells how much points each segment contains.
Definition: region_growing.h:328
pcl::RegionGrowing::neighbour_number_
unsigned int neighbour_number_
Number of neighbours to find.
Definition: region_growing.h:308
pcl::comparePair
bool comparePair(std::pair< float, int > i, std::pair< float, int > j)
This function is used as a comparator for sorting.
Definition: region_growing.h:342
pcl::RegionGrowing::point_labels_
std::vector< int > point_labels_
Point labels that tells to which segment each point belongs.
Definition: region_growing.h:320
pcl::RegionGrowing::search_
KdTreePtr search_
Serch method that will be used for KNN.
Definition: region_growing.h:311
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::RegionGrowing::max_pts_per_cluster_
int max_pts_per_cluster_
Stores the maximum number of points that a cluster needs to contain in order to be considered valid.
Definition: region_growing.h:287
pcl::RegionGrowing
Implements the well known Region Growing algorithm used for segmentation.
Definition: region_growing.h:62
pcl::PointIndices
Definition: PointIndices.h:11
pcl::PointCloud::Ptr
shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:428
pcl::KdTree::Ptr
shared_ptr< KdTree< PointT > > Ptr
Definition: kdtree.h:68
pcl::RegionGrowing::min_pts_per_cluster_
int min_pts_per_cluster_
Stores the minimum number of points that a cluster needs to contain in order to be considered valid.
Definition: region_growing.h:284
pcl::RegionGrowing::smooth_mode_flag_
bool smooth_mode_flag_
Flag that signalizes if the smoothness constraint will be used.
Definition: region_growing.h:290
pcl::RegionGrowing::curvature_threshold_
float curvature_threshold_
Thershold used in curvature test.
Definition: region_growing.h:305
pcl::RegionGrowing::number_of_segments_
int number_of_segments_
Stores the number of segments.
Definition: region_growing.h:334
memory.h
Defines functions, macros and traits for allocating and using memory.
pcl::RegionGrowing::point_neighbours_
std::vector< std::vector< int > > point_neighbours_
Contains neighbours of each point.
Definition: region_growing.h:317
PCL_EXPORTS
#define PCL_EXPORTS
Definition: pcl_macros.h:337