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