Point Cloud Library (PCL) 1.14.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{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
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 {
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
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 */
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.
shared_ptr< Supervoxel< PointT > > Ptr
Defines all the PCL implemented PointT point type structures.