Point Cloud Library (PCL) 1.12.0
Loading...
Searching...
No Matches
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
46namespace 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
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 {
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...
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.
shared_ptr< Supervoxel< PointT > > Ptr
Defines all the PCL implemented PointT point type structures.