Point Cloud Library (PCL)  1.14.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{0.0f};
64 
65  /** \brief Describes if a connection is convex or concave*/
66  bool is_convex{false};
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{false};
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{false};
73 
74  EdgeProperties () = default;
75  };
76 
77  public:
78 
79  // Adjacency list with nodes holding labels (std::uint32_t) and edges holding EdgeProperties.
80  using SupervoxelAdjacencyList = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, std::uint32_t, EdgeProperties>;
81  using VertexIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::vertex_iterator;
82  using AdjacencyIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::adjacency_iterator;
83 
84  using VertexID = typename boost::graph_traits<SupervoxelAdjacencyList>::vertex_descriptor;
85  using EdgeIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::edge_iterator;
86  using OutEdgeIterator = typename boost::graph_traits<SupervoxelAdjacencyList>::out_edge_iterator;
87  using EdgeID = typename boost::graph_traits<SupervoxelAdjacencyList>::edge_descriptor;
88 
90  virtual
92 
93  /** \brief Reset internal memory. */
94  void
95  reset ();
96 
97 
98  /** \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.
99  * \param[in] supervoxel_clusters_arg Map of < supervoxel labels, supervoxels >
100  * \param[in] label_adjacency_arg The graph defining the supervoxel adjacency relations
101  * \note Implicitly calls \ref reset */
102  inline void
103  setInputSupervoxels (const std::map<std::uint32_t, typename pcl::Supervoxel<PointT>::Ptr> &supervoxel_clusters_arg,
104  const std::multimap<std::uint32_t, std::uint32_t> &label_adjacency_arg)
105  {
106  // Initialization
107  prepareSegmentation (supervoxel_clusters_arg, label_adjacency_arg); // after this, sv_adjacency_list_ can be used to access adjacency list
108  supervoxels_set_ = true;
109  }
110 
111  /** \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.
112  * \note There are three ways to retrieve the segmentation afterwards: \ref relabelCloud, \ref getSegmentToSupervoxelMap and \ref getSupervoxelToSegmentMap. */
113  void
114  segment ();
115 
116  /** \brief Relabels cloud with supervoxel labels with the computed segment labels. labeled_cloud_arg should be created using SupervoxelClustering::getLabeledCloud.
117  * \param[in,out] labeled_cloud_arg Cloud to relabel */
118  void
119  relabelCloud (pcl::PointCloud<pcl::PointXYZL> &labeled_cloud_arg);
120 
121  /** \brief Get map<SegmentID, std::set<SuperVoxel IDs> >
122  * \param[out] segment_supervoxel_map_arg The output container. On error the map is empty. */
123  inline void
124  getSegmentToSupervoxelMap (std::map<std::uint32_t, std::set<std::uint32_t> >& segment_supervoxel_map_arg) const
125  {
127  {
128  segment_supervoxel_map_arg = seg_label_to_sv_list_map_;
129  }
130  else
131  {
132  PCL_WARN ("[pcl::LCCPSegmentation::getSegmentMap] WARNING: Call function segment first. Nothing has been done. \n");
133  segment_supervoxel_map_arg = std::map<std::uint32_t, std::set<std::uint32_t> > ();
134  }
135  }
136 
137  /** \brief Get map<Supervoxel_ID, Segment_ID>
138  * \param[out] supervoxel_segment_map_arg The output container. On error the map is empty. */
139  inline void
140  getSupervoxelToSegmentMap (std::map<std::uint32_t, std::uint32_t>& supervoxel_segment_map_arg) const
141  {
143  {
144  supervoxel_segment_map_arg = sv_label_to_seg_label_map_;
145  }
146  else
147  {
148  PCL_WARN ("[pcl::LCCPSegmentation::getSegmentMap] WARNING: Call function segment first. Nothing has been done. \n");
149  supervoxel_segment_map_arg = std::map<std::uint32_t, std::uint32_t> ();
150  }
151  }
152 
153  /** \brief Get map <SegmentID, std::set<Neighboring SegmentIDs> >
154  * \param[out] segment_adjacency_map_arg map < SegmentID, std::set< Neighboring SegmentIDs> >. On error the map is empty. */
155  inline void
156  getSegmentAdjacencyMap (std::map<std::uint32_t, std::set<std::uint32_t> >& segment_adjacency_map_arg)
157  {
159  {
160  if (seg_label_to_neighbor_set_map_.empty ())
162  segment_adjacency_map_arg = seg_label_to_neighbor_set_map_;
163  }
164  else
165  {
166  PCL_WARN ("[pcl::LCCPSegmentation::getSegmentAdjacencyMap] WARNING: Call function segment first. Nothing has been done. \n");
167  segment_adjacency_map_arg = std::map<std::uint32_t, std::set<std::uint32_t> > ();
168  }
169  }
170 
171  /** \brief Get normal threshold
172  * \return The concavity tolerance angle in [deg] that is currently set */
173  inline float
175  {
177  }
178 
179  /** \brief Get the supervoxel adjacency graph with classified edges (boost::adjacency_list).
180  * \param[out] adjacency_list_arg The supervoxel adjacency list with classified (convex/concave) edges. On error the list is empty. */
181  inline void
182  getSVAdjacencyList (SupervoxelAdjacencyList& adjacency_list_arg) const
183  {
185  {
186  adjacency_list_arg = sv_adjacency_list_;
187  }
188  else
189  {
190  PCL_WARN ("[pcl::LCCPSegmentation::getSVAdjacencyList] WARNING: Call function segment first. Nothing has been done. \n");
192  }
193  }
194 
195  /** \brief Set normal threshold
196  * \param[in] concavity_tolerance_threshold_arg the concavity tolerance angle in [deg] to set */
197  inline void
198  setConcavityToleranceThreshold (float concavity_tolerance_threshold_arg)
199  {
200  concavity_tolerance_threshold_ = concavity_tolerance_threshold_arg;
201  }
202 
203  /** \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.
204  * \param[in] use_smoothness_check_arg Determines if the smoothness check is used
205  * \param[in] voxel_res_arg The voxel resolution used for the supervoxels that are segmented
206  * \param[in] seed_res_arg The seed resolution used for the supervoxels that are segmented
207  * \param[in] smoothness_threshold_arg Threshold (/fudging factor) for smoothness constraint according to the above formula. */
208  inline void
209  setSmoothnessCheck (bool use_smoothness_check_arg,
210  float voxel_res_arg,
211  float seed_res_arg,
212  float smoothness_threshold_arg = 0.1)
213  {
214  use_smoothness_check_ = use_smoothness_check_arg;
215  voxel_resolution_ = voxel_res_arg;
216  seed_resolution_ = seed_res_arg;
217  smoothness_threshold_ = smoothness_threshold_arg;
218  }
219 
220  /** \brief Determines if we want to use the sanity criterion to invalidate singular connected patches
221  * \param[in] use_sanity_criterion_arg Determines if the sanity check is performed */
222  inline void
223  setSanityCheck (const bool use_sanity_criterion_arg)
224  {
225  use_sanity_check_ = use_sanity_criterion_arg;
226  }
227 
228  /** \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.
229  * \param[in] k_factor_arg factor used for extended convexity check */
230  inline void
231  setKFactor (const std::uint32_t k_factor_arg)
232  {
233  k_factor_ = k_factor_arg;
234  }
235 
236  /** \brief Set the value \ref min_segment_size_ used in \ref mergeSmallSegments
237  * \param[in] min_segment_size_arg Segments smaller than this size will be merged */
238  inline void
239  setMinSegmentSize (const std::uint32_t min_segment_size_arg)
240  {
241  min_segment_size_ = min_segment_size_arg;
242  }
243 
244  protected:
245 
246  /** \brief Segments smaller than \ref min_segment_size_ are merged to the label of largest neighbor */
247  void
249 
250  /** \brief Compute the adjacency of the segments */
251  void
253 
254  /** \brief Is called within \ref setInputSupervoxels mainly to reserve required memory.
255  * \param[in] supervoxel_clusters_arg map of < supervoxel labels, supervoxels >
256  * \param[in] label_adjacency_arg The graph defining the supervoxel adjacency relations */
257  void
258  prepareSegmentation (const std::map<std::uint32_t, typename pcl::Supervoxel<PointT>::Ptr> &supervoxel_clusters_arg,
259  const std::multimap<std::uint32_t, std::uint32_t> &label_adjacency_arg);
260 
261 
262  /** Perform depth search on the graph and recursively group all supervoxels with convex connections
263  * \note The vertices in the supervoxel adjacency list are the supervoxel centroids */
264  void
265  doGrouping ();
266 
267  /** \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.
268  * \param[in] queryPointID ID of point whose neighbors will be considered for grouping
269  * \param[in] group_label ID of the group/segment the queried point belongs to */
270  void
271  recursiveSegmentGrowing (const VertexID &queryPointID,
272  const unsigned int group_label);
273 
274  /** \brief Calculates convexity of edges and saves this to the adjacency graph.
275  * \param[in,out] adjacency_list_arg The supervoxel adjacency list*/
276  void
278 
279  /** \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.
280  * \param[in] k_arg Factor used for extended convexity check */
281  void
282  applyKconvexity (const unsigned int k_arg);
283 
284  /** \brief Returns true if the connection between source and target is convex.
285  * \param[in] source_label_arg Label of one supervoxel connected to the edge that should be checked
286  * \param[in] target_label_arg Label of the other supervoxel connected to the edge that should be checked
287  * \param[out] normal_angle The angle between source and target
288  * \return True if connection is convex */
289  bool
290  connIsConvex (const std::uint32_t source_label_arg,
291  const std::uint32_t target_label_arg,
292  float &normal_angle);
293 
294  /// *** Parameters *** ///
295 
296  /** \brief Normal Threshold in degrees [0,180] used for merging */
298 
299  /** \brief Marks if valid grouping data (\ref sv_adjacency_list_, \ref sv_label_to_seg_label_map_, \ref processed_) is available */
300  bool grouping_data_valid_{false};
301 
302  /** \brief Marks if supervoxels have been set by calling \ref setInputSupervoxels */
303  bool supervoxels_set_{false};
304 
305  /** \brief Determines if the smoothness check is used during segmentation*/
307 
308  /** \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. */
310 
311  /** \brief Determines if we use the sanity check which tries to find and invalidate singular connected patches*/
312  bool use_sanity_check_{false};
313 
314  /** \brief Seed resolution of the supervoxels (used only for smoothness check) */
315  float seed_resolution_{0.0f};
316 
317  /** \brief Voxel resolution used to build the supervoxels (used only for smoothness check)*/
318  float voxel_resolution_{0.0f};
319 
320  /** \brief Factor used for k-convexity */
321  std::uint32_t k_factor_{0};
322 
323  /** \brief Minimum segment size */
324  std::uint32_t min_segment_size_{0};
325 
326  /** \brief Stores which supervoxel labels were already visited during recursive grouping.
327  * \note processed_[sv_Label] = false (default)/true (already processed) */
328  std::map<std::uint32_t, bool> processed_;
329 
330  /** \brief Adjacency graph with the supervoxel labels as nodes and edges between adjacent supervoxels */
332 
333  /** \brief map from the supervoxel labels to the supervoxel objects */
334  std::map<std::uint32_t, typename pcl::Supervoxel<PointT>::Ptr> sv_label_to_supervoxel_map_;
335 
336  /** \brief Storing relation between original SuperVoxel Labels and new segmantion labels.
337  * \note sv_label_to_seg_label_map_[old_labelID] = new_labelID */
338  std::map<std::uint32_t, std::uint32_t> sv_label_to_seg_label_map_;
339 
340  /** \brief map Segment Label to a set of Supervoxel Labels */
341  std::map<std::uint32_t, std::set<std::uint32_t> > seg_label_to_sv_list_map_;
342 
343  /** \brief map < SegmentID, std::set< Neighboring segment labels> > */
344  std::map<std::uint32_t, std::set<std::uint32_t> > seg_label_to_neighbor_set_map_;
345 
346  };
347 }
348 
349 #ifdef PCL_NO_PRECOMPILE
350 #include <pcl/segmentation/impl/lccp_segmentation.hpp>
351 #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.