Point Cloud Library (PCL)  1.13.1-dev
lccp_segmentation.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2014-, 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 the copyright holder(s) 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  */
37 
38 #pragma once
39 
40 #include <pcl/point_types.h>
41 #include <pcl/point_cloud.h>
42 #include <pcl/segmentation/supervoxel_clustering.h>
43 
44 #define PCL_INSTANTIATE_LCCPSegmentation(T) template class PCL_EXPORTS pcl::LCCPSegmentation<T>;
45 
46 namespace pcl
47 {
48  /** \brief A simple segmentation algorithm partitioning a supervoxel graph into groups of locally convex connected supervoxels separated by concave borders.
49  * \note If you use this in a scientific work please cite the following paper:
50  * S. C. Stein, M. Schoeler, J. Papon, F. Woergoetter
51  * Object Partitioning using Local Convexity
52  * In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2014
53  * \author Simon Christoph Stein and Markus Schoeler (mschoeler@gwdg.de)
54  * \ingroup segmentation
55  */
56  template <typename PointT>
58  {
59  /** \brief Edge Properties stored in the adjacency graph.*/
60  struct EdgeProperties
61  {
62  /** \brief Describes the difference of normals of the two supervoxels being connected*/
63  float normal_difference;
64 
65  /** \brief Describes if a connection is convex or concave*/
66  bool is_convex;
67 
68  /** \brief Describes if a connection is valid for the segment growing. Usually convex connections are and concave connection are not. Due to k-concavity a convex connection can be invalidated*/
69  bool is_valid;
70 
71  /** \brief Additional member used for the CPC algorithm. If edge has already induced a cut, it should be ignored for further cutting.*/
72  bool used_for_cutting;
73 
74  EdgeProperties () :
75  normal_difference (0), is_convex (false), is_valid (false), used_for_cutting (false)
76  {
77  }
78  };
79 
80  public:
81 
82  // Adjacency list with nodes holding labels (std::uint32_t) and edges holding EdgeProperties.
83  using SupervoxelAdjacencyList = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, std::uint32_t, EdgeProperties>;
84  using VertexIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::vertex_iterator;
85  using AdjacencyIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::adjacency_iterator;
86 
87  using VertexID = typename boost::graph_traits<SupervoxelAdjacencyList>::vertex_descriptor;
88  using EdgeIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::edge_iterator;
89  using OutEdgeIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::out_edge_iterator;
90  using EdgeID = typename boost::graph_traits<SupervoxelAdjacencyList>::edge_descriptor;
91 
93  virtual
95 
96  /** \brief Reset internal memory. */
97  void
98  reset ();
99 
100 
101  /** \brief Set the supervoxel clusters as well as the adjacency graph for the segmentation.Those parameters are generated by using the \ref SupervoxelClustering class. To retrieve the output use the \ref segment method.
102  * \param[in] supervoxel_clusters_arg Map of < supervoxel labels, supervoxels >
103  * \param[in] label_adjacency_arg The graph defining the supervoxel adjacency relations
104  * \note Implicitly calls \ref reset */
105  inline void
106  setInputSupervoxels (const std::map<std::uint32_t, typename pcl::Supervoxel<PointT>::Ptr> &supervoxel_clusters_arg,
107  const std::multimap<std::uint32_t, std::uint32_t> &label_adjacency_arg)
108  {
109  // Initialization
110  prepareSegmentation (supervoxel_clusters_arg, label_adjacency_arg); // after this, sv_adjacency_list_ can be used to access adjacency list
111  supervoxels_set_ = true;
112  }
113 
114  /** \brief Merge supervoxels using local convexity. The input parameters are generated by using the \ref SupervoxelClustering class. To retrieve the output use the \ref relabelCloud method.
115  * \note There are three ways to retrieve the segmentation afterwards: \ref relabelCloud, \ref getSegmentToSupervoxelMap and \ref getSupervoxelToSegmentMap. */
116  void
117  segment ();
118 
119  /** \brief Relabels cloud with supervoxel labels with the computed segment labels. labeled_cloud_arg should be created using SupervoxelClustering::getLabeledCloud.
120  * \param[in,out] labeled_cloud_arg Cloud to relabel */
121  void
122  relabelCloud (pcl::PointCloud<pcl::PointXYZL> &labeled_cloud_arg);
123 
124  /** \brief Get map<SegmentID, std::set<SuperVoxel IDs> >
125  * \param[out] segment_supervoxel_map_arg The output container. On error the map is empty. */
126  inline void
127  getSegmentToSupervoxelMap (std::map<std::uint32_t, std::set<std::uint32_t> >& segment_supervoxel_map_arg) const
128  {
130  {
131  segment_supervoxel_map_arg = seg_label_to_sv_list_map_;
132  }
133  else
134  {
135  PCL_WARN ("[pcl::LCCPSegmentation::getSegmentMap] WARNING: Call function segment first. Nothing has been done. \n");
136  segment_supervoxel_map_arg = std::map<std::uint32_t, std::set<std::uint32_t> > ();
137  }
138  }
139 
140  /** \brief Get map<Supervoxel_ID, Segment_ID>
141  * \param[out] supervoxel_segment_map_arg The output container. On error the map is empty. */
142  inline void
143  getSupervoxelToSegmentMap (std::map<std::uint32_t, std::uint32_t>& supervoxel_segment_map_arg) const
144  {
146  {
147  supervoxel_segment_map_arg = sv_label_to_seg_label_map_;
148  }
149  else
150  {
151  PCL_WARN ("[pcl::LCCPSegmentation::getSegmentMap] WARNING: Call function segment first. Nothing has been done. \n");
152  supervoxel_segment_map_arg = std::map<std::uint32_t, std::uint32_t> ();
153  }
154  }
155 
156  /** \brief Get map <SegmentID, std::set<Neighboring SegmentIDs> >
157  * \param[out] segment_adjacency_map_arg map < SegmentID, std::set< Neighboring SegmentIDs> >. On error the map is empty. */
158  inline void
159  getSegmentAdjacencyMap (std::map<std::uint32_t, std::set<std::uint32_t> >& segment_adjacency_map_arg)
160  {
162  {
163  if (seg_label_to_neighbor_set_map_.empty ())
165  segment_adjacency_map_arg = seg_label_to_neighbor_set_map_;
166  }
167  else
168  {
169  PCL_WARN ("[pcl::LCCPSegmentation::getSegmentAdjacencyMap] WARNING: Call function segment first. Nothing has been done. \n");
170  segment_adjacency_map_arg = std::map<std::uint32_t, std::set<std::uint32_t> > ();
171  }
172  }
173 
174  /** \brief Get normal threshold
175  * \return The concavity tolerance angle in [deg] that is currently set */
176  inline float
178  {
180  }
181 
182  /** \brief Get the supervoxel adjacency graph with classified edges (boost::adjacency_list).
183  * \param[out] adjacency_list_arg The supervoxel adjacency list with classified (convex/concave) edges. On error the list is empty. */
184  inline void
185  getSVAdjacencyList (SupervoxelAdjacencyList& adjacency_list_arg) const
186  {
188  {
189  adjacency_list_arg = sv_adjacency_list_;
190  }
191  else
192  {
193  PCL_WARN ("[pcl::LCCPSegmentation::getSVAdjacencyList] WARNING: Call function segment first. Nothing has been done. \n");
195  }
196  }
197 
198  /** \brief Set normal threshold
199  * \param[in] concavity_tolerance_threshold_arg the concavity tolerance angle in [deg] to set */
200  inline void
201  setConcavityToleranceThreshold (float concavity_tolerance_threshold_arg)
202  {
203  concavity_tolerance_threshold_ = concavity_tolerance_threshold_arg;
204  }
205 
206  /** \brief Determines if a smoothness check is done during segmentation, trying to invalidate edges of non-smooth connected edges (steps). Two supervoxels are unsmooth if their plane-to-plane distance DIST > (expected_distance + smoothness_threshold_*voxel_resolution_). For parallel supervoxels, the expected_distance is zero.
207  * \param[in] use_smoothness_check_arg Determines if the smoothness check is used
208  * \param[in] voxel_res_arg The voxel resolution used for the supervoxels that are segmented
209  * \param[in] seed_res_arg The seed resolution used for the supervoxels that are segmented
210  * \param[in] smoothness_threshold_arg Threshold (/fudging factor) for smoothness constraint according to the above formula. */
211  inline void
212  setSmoothnessCheck (bool use_smoothness_check_arg,
213  float voxel_res_arg,
214  float seed_res_arg,
215  float smoothness_threshold_arg = 0.1)
216  {
217  use_smoothness_check_ = use_smoothness_check_arg;
218  voxel_resolution_ = voxel_res_arg;
219  seed_resolution_ = seed_res_arg;
220  smoothness_threshold_ = smoothness_threshold_arg;
221  }
222 
223  /** \brief Determines if we want to use the sanity criterion to invalidate singular connected patches
224  * \param[in] use_sanity_criterion_arg Determines if the sanity check is performed */
225  inline void
226  setSanityCheck (const bool use_sanity_criterion_arg)
227  {
228  use_sanity_check_ = use_sanity_criterion_arg;
229  }
230 
231  /** \brief Set the value used for k convexity. For k>0 convex connections between p_i and p_j require k common neighbors of these patches that have a convex connection to both.
232  * \param[in] k_factor_arg factor used for extended convexity check */
233  inline void
234  setKFactor (const std::uint32_t k_factor_arg)
235  {
236  k_factor_ = k_factor_arg;
237  }
238 
239  /** \brief Set the value \ref min_segment_size_ used in \ref mergeSmallSegments
240  * \param[in] min_segment_size_arg Segments smaller than this size will be merged */
241  inline void
242  setMinSegmentSize (const std::uint32_t min_segment_size_arg)
243  {
244  min_segment_size_ = min_segment_size_arg;
245  }
246 
247  protected:
248 
249  /** \brief Segments smaller than \ref min_segment_size_ are merged to the label of largest neighbor */
250  void
252 
253  /** \brief Compute the adjacency of the segments */
254  void
256 
257  /** \brief Is called within \ref setInputSupervoxels mainly to reserve required memory.
258  * \param[in] supervoxel_clusters_arg map of < supervoxel labels, supervoxels >
259  * \param[in] label_adjacency_arg The graph defining the supervoxel adjacency relations */
260  void
261  prepareSegmentation (const std::map<std::uint32_t, typename pcl::Supervoxel<PointT>::Ptr> &supervoxel_clusters_arg,
262  const std::multimap<std::uint32_t, std::uint32_t> &label_adjacency_arg);
263 
264 
265  /** Perform depth search on the graph and recursively group all supervoxels with convex connections
266  * \note The vertices in the supervoxel adjacency list are the supervoxel centroids */
267  void
268  doGrouping ();
269 
270  /** \brief Assigns neighbors of the query point to the same group as the query point. Recursive part of \ref doGrouping. Grouping is done by a depth-search of nodes in the adjacency-graph.
271  * \param[in] queryPointID ID of point whose neighbors will be considered for grouping
272  * \param[in] group_label ID of the group/segment the queried point belongs to */
273  void
274  recursiveSegmentGrowing (const VertexID &queryPointID,
275  const unsigned int group_label);
276 
277  /** \brief Calculates convexity of edges and saves this to the adjacency graph.
278  * \param[in,out] adjacency_list_arg The supervoxel adjacency list*/
279  void
281 
282  /** \brief Connections are only convex if this is true for at least k_arg common neighbors of the two patches. Call \ref setKFactor before \ref segment to use this.
283  * \param[in] k_arg Factor used for extended convexity check */
284  void
285  applyKconvexity (const unsigned int k_arg);
286 
287  /** \brief Returns true if the connection between source and target is convex.
288  * \param[in] source_label_arg Label of one supervoxel connected to the edge that should be checked
289  * \param[in] target_label_arg Label of the other supervoxel connected to the edge that should be checked
290  * \param[out] normal_angle The angle between source and target
291  * \return True if connection is convex */
292  bool
293  connIsConvex (const std::uint32_t source_label_arg,
294  const std::uint32_t target_label_arg,
295  float &normal_angle);
296 
297  /// *** Parameters *** ///
298 
299  /** \brief Normal Threshold in degrees [0,180] used for merging */
301 
302  /** \brief Marks if valid grouping data (\ref sv_adjacency_list_, \ref sv_label_to_seg_label_map_, \ref processed_) is available */
304 
305  /** \brief Marks if supervoxels have been set by calling \ref setInputSupervoxels */
307 
308  /** \brief Determines if the smoothness check is used during segmentation*/
310 
311  /** \brief Two supervoxels are unsmooth if their plane-to-plane distance DIST > (expected_distance + smoothness_threshold_*voxel_resolution_). For parallel supervoxels, the expected_distance is zero. */
313 
314  /** \brief Determines if we use the sanity check which tries to find and invalidate singular connected patches*/
316 
317  /** \brief Seed resolution of the supervoxels (used only for smoothness check) */
319 
320  /** \brief Voxel resolution used to build the supervoxels (used only for smoothness check)*/
322 
323  /** \brief Factor used for k-convexity */
324  std::uint32_t k_factor_;
325 
326  /** \brief Minimum segment size */
327  std::uint32_t min_segment_size_;
328 
329  /** \brief Stores which supervoxel labels were already visited during recursive grouping.
330  * \note processed_[sv_Label] = false (default)/true (already processed) */
331  std::map<std::uint32_t, bool> processed_;
332 
333  /** \brief Adjacency graph with the supervoxel labels as nodes and edges between adjacent supervoxels */
335 
336  /** \brief map from the supervoxel labels to the supervoxel objects */
337  std::map<std::uint32_t, typename pcl::Supervoxel<PointT>::Ptr> sv_label_to_supervoxel_map_;
338 
339  /** \brief Storing relation between original SuperVoxel Labels and new segmantion labels.
340  * \note sv_label_to_seg_label_map_[old_labelID] = new_labelID */
341  std::map<std::uint32_t, std::uint32_t> sv_label_to_seg_label_map_;
342 
343  /** \brief map Segment Label to a set of Supervoxel Labels */
344  std::map<std::uint32_t, std::set<std::uint32_t> > seg_label_to_sv_list_map_;
345 
346  /** \brief map < SegmentID, std::set< Neighboring segment labels> > */
347  std::map<std::uint32_t, std::set<std::uint32_t> > seg_label_to_neighbor_set_map_;
348 
349  };
350 }
351 
352 #ifdef PCL_NO_PRECOMPILE
353 #include <pcl/segmentation/impl/lccp_segmentation.hpp>
354 #endif
A simple segmentation algorithm partitioning a supervoxel graph into groups of locally convex connect...
virtual ~LCCPSegmentation()
float voxel_resolution_
Voxel resolution used to build the supervoxels (used only for smoothness check)
std::map< std::uint32_t, std::set< std::uint32_t > > seg_label_to_sv_list_map_
map Segment Label to a set of Supervoxel Labels
bool supervoxels_set_
Marks if supervoxels have been set by calling setInputSupervoxels.
std::map< std::uint32_t, std::uint32_t > sv_label_to_seg_label_map_
Storing relation between original SuperVoxel Labels and new segmantion labels.
void setMinSegmentSize(const std::uint32_t min_segment_size_arg)
Set the value min_segment_size_ used in mergeSmallSegments.
typename boost::graph_traits< SupervoxelAdjacencyList >::vertex_iterator VertexIterator
void setSmoothnessCheck(bool use_smoothness_check_arg, float voxel_res_arg, float seed_res_arg, float smoothness_threshold_arg=0.1)
Determines if a smoothness check is done during segmentation, trying to invalidate edges of non-smoot...
typename boost::graph_traits< SupervoxelAdjacencyList >::edge_iterator EdgeIterator
boost::adjacency_list< boost::setS, boost::setS, boost::undirectedS, std::uint32_t, EdgeProperties > SupervoxelAdjacencyList
bool grouping_data_valid_
Marks if valid grouping data (sv_adjacency_list_, sv_label_to_seg_label_map_, processed_) is availabl...
void setKFactor(const std::uint32_t k_factor_arg)
Set the value used for k convexity.
void recursiveSegmentGrowing(const VertexID &queryPointID, const unsigned int group_label)
Assigns neighbors of the query point to the same group as the query point.
std::uint32_t k_factor_
Factor used for k-convexity.
void calculateConvexConnections(SupervoxelAdjacencyList &adjacency_list_arg)
Calculates convexity of edges and saves this to the adjacency graph.
void computeSegmentAdjacency()
Compute the adjacency of the segments.
bool use_smoothness_check_
Determines if the smoothness check is used during segmentation.
void getSegmentAdjacencyMap(std::map< std::uint32_t, std::set< std::uint32_t > > &segment_adjacency_map_arg)
Get map <SegmentID, std::set<Neighboring SegmentIDs> >
bool use_sanity_check_
Determines if we use the sanity check which tries to find and invalidate singular connected patches.
void relabelCloud(pcl::PointCloud< pcl::PointXYZL > &labeled_cloud_arg)
Relabels cloud with supervoxel labels with the computed segment labels.
void setInputSupervoxels(const std::map< std::uint32_t, typename pcl::Supervoxel< PointT >::Ptr > &supervoxel_clusters_arg, const std::multimap< std::uint32_t, std::uint32_t > &label_adjacency_arg)
Set the supervoxel clusters as well as the adjacency graph for the segmentation.Those parameters are ...
void mergeSmallSegments()
Segments smaller than min_segment_size_ are merged to the label of largest neighbor.
void prepareSegmentation(const std::map< std::uint32_t, typename pcl::Supervoxel< PointT >::Ptr > &supervoxel_clusters_arg, const std::multimap< std::uint32_t, std::uint32_t > &label_adjacency_arg)
Is called within setInputSupervoxels mainly to reserve required memory.
void segment()
Merge supervoxels using local convexity.
float concavity_tolerance_threshold_
*** Parameters *** ///
void getSegmentToSupervoxelMap(std::map< std::uint32_t, std::set< std::uint32_t > > &segment_supervoxel_map_arg) const
Get map<SegmentID, std::set<SuperVoxel IDs> >
float smoothness_threshold_
Two supervoxels are unsmooth if their plane-to-plane distance DIST > (expected_distance + smoothness_...
typename boost::graph_traits< SupervoxelAdjacencyList >::out_edge_iterator OutEdgeIterator
float seed_resolution_
Seed resolution of the supervoxels (used only for smoothness check)
std::uint32_t min_segment_size_
Minimum segment size.
std::map< std::uint32_t, bool > processed_
Stores which supervoxel labels were already visited during recursive grouping.
typename boost::graph_traits< SupervoxelAdjacencyList >::adjacency_iterator AdjacencyIterator
void setConcavityToleranceThreshold(float concavity_tolerance_threshold_arg)
Set normal threshold.
bool connIsConvex(const std::uint32_t source_label_arg, const std::uint32_t target_label_arg, float &normal_angle)
Returns true if the connection between source and target is convex.
float getConcavityToleranceThreshold() const
Get normal threshold.
void doGrouping()
Perform depth search on the graph and recursively group all supervoxels with convex connections.
void applyKconvexity(const unsigned int k_arg)
Connections are only convex if this is true for at least k_arg common neighbors of the two patches.
SupervoxelAdjacencyList sv_adjacency_list_
Adjacency graph with the supervoxel labels as nodes and edges between adjacent supervoxels.
void getSupervoxelToSegmentMap(std::map< std::uint32_t, std::uint32_t > &supervoxel_segment_map_arg) const
Get map<Supervoxel_ID, Segment_ID>
typename boost::graph_traits< SupervoxelAdjacencyList >::edge_descriptor EdgeID
typename boost::graph_traits< SupervoxelAdjacencyList >::vertex_descriptor VertexID
void getSVAdjacencyList(SupervoxelAdjacencyList &adjacency_list_arg) const
Get the supervoxel adjacency graph with classified edges (boost::adjacency_list).
void reset()
Reset internal memory.
std::map< std::uint32_t, typename pcl::Supervoxel< PointT >::Ptr > sv_label_to_supervoxel_map_
map from the supervoxel labels to the supervoxel objects
std::map< std::uint32_t, std::set< std::uint32_t > > seg_label_to_neighbor_set_map_
map < SegmentID, std::set< Neighboring segment labels> >
void setSanityCheck(const bool use_sanity_criterion_arg)
Determines if we want to use the sanity criterion to invalidate singular connected patches.
PointCloud represents the base class in PCL for storing collections of 3D points.
Definition: point_cloud.h:173
shared_ptr< Supervoxel< PointT > > Ptr
Defines all the PCL implemented PointT point type structures.