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