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