Point Cloud Library (PCL)
1.7.0
|
00001 /* 00002 * Software License Agreement (BSD License) 00003 * 00004 * Point Cloud Library (PCL) - www.pointclouds.org 00005 * 00006 * All rights reserved. 00007 * 00008 * Redistribution and use in source and binary forms, with or without 00009 * modification, are permitted provided that the following conditions 00010 * are met: 00011 * 00012 * * Redistributions of source code must retain the above copyright 00013 * notice, this list of conditions and the following disclaimer. 00014 * * Redistributions in binary form must reproduce the above 00015 * copyright notice, this list of conditions and the following 00016 * disclaimer in the documentation and/or other materials provided 00017 * with the distribution. 00018 * * Neither the name of the copyright holder(s) nor the names of its 00019 * contributors may be used to endorse or promote products derived 00020 * from this software without specific prior written permission. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00023 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00024 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 00025 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 00026 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 00027 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 00028 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 00029 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 00030 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00031 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 00032 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00033 * POSSIBILITY OF SUCH DAMAGE. 00034 * 00035 * $Id:$ 00036 * 00037 */ 00038 00039 #ifndef PCL_MIN_CUT_SEGMENTATION_H_ 00040 #define PCL_MIN_CUT_SEGMENTATION_H_ 00041 00042 #include <pcl/segmentation/boost.h> 00043 #if (BOOST_VERSION >= 104400) 00044 #include <pcl/pcl_base.h> 00045 #include <pcl/point_cloud.h> 00046 #include <pcl/point_types.h> 00047 #include <pcl/search/search.h> 00048 #include <string> 00049 #include <set> 00050 00051 namespace pcl 00052 { 00053 /** \brief This class implements the segmentation algorithm based on minimal cut of the graph. 00054 * The description can be found in the article: 00055 * "Min-Cut Based Segmentation of Point Clouds" 00056 * \author: Aleksey Golovinskiy and Thomas Funkhouser. 00057 */ 00058 template <typename PointT> 00059 class PCL_EXPORTS MinCutSegmentation : public pcl::PCLBase<PointT> 00060 { 00061 public: 00062 00063 typedef pcl::search::Search <PointT> KdTree; 00064 typedef typename KdTree::Ptr KdTreePtr; 00065 typedef pcl::PointCloud< PointT > PointCloud; 00066 typedef typename PointCloud::ConstPtr PointCloudConstPtr; 00067 00068 using PCLBase <PointT>::input_; 00069 using PCLBase <PointT>::indices_; 00070 using PCLBase <PointT>::initCompute; 00071 using PCLBase <PointT>::deinitCompute; 00072 00073 public: 00074 00075 typedef boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::directedS > Traits; 00076 00077 typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, 00078 boost::property< boost::vertex_name_t, std::string, 00079 boost::property< boost::vertex_index_t, long, 00080 boost::property< boost::vertex_color_t, boost::default_color_type, 00081 boost::property< boost::vertex_distance_t, long, 00082 boost::property< boost::vertex_predecessor_t, Traits::edge_descriptor > > > > >, 00083 boost::property< boost::edge_capacity_t, double, 00084 boost::property< boost::edge_residual_capacity_t, double, 00085 boost::property< boost::edge_reverse_t, Traits::edge_descriptor > > > > mGraph; 00086 00087 typedef boost::property_map< mGraph, boost::edge_capacity_t >::type CapacityMap; 00088 00089 typedef boost::property_map< mGraph, boost::edge_reverse_t>::type ReverseEdgeMap; 00090 00091 typedef Traits::vertex_descriptor VertexDescriptor; 00092 00093 typedef boost::graph_traits< mGraph >::edge_descriptor EdgeDescriptor; 00094 00095 typedef boost::graph_traits< mGraph >::out_edge_iterator OutEdgeIterator; 00096 00097 typedef boost::graph_traits< mGraph >::vertex_iterator VertexIterator; 00098 00099 typedef boost::property_map< mGraph, boost::edge_residual_capacity_t >::type ResidualCapacityMap; 00100 00101 typedef boost::property_map< mGraph, boost::vertex_index_t >::type IndexMap; 00102 00103 typedef boost::graph_traits< mGraph >::in_edge_iterator InEdgeIterator; 00104 00105 public: 00106 00107 /** \brief Constructor that sets default values for member variables. */ 00108 MinCutSegmentation (); 00109 00110 /** \brief Destructor that frees memory. */ 00111 virtual 00112 ~MinCutSegmentation (); 00113 00114 /** \brief This method simply sets the input point cloud. 00115 * \param[in] cloud the const boost shared pointer to a PointCloud 00116 */ 00117 virtual void 00118 setInputCloud (const PointCloudConstPtr &cloud); 00119 00120 /** \brief Returns normalization value for binary potentials. For more information see the article. */ 00121 double 00122 getSigma () const; 00123 00124 /** \brief Allows to set the normalization value for the binary potentials as described in the article. 00125 * \param[in] sigma new normalization value 00126 */ 00127 void 00128 setSigma (double sigma); 00129 00130 /** \brief Returns radius to the background. */ 00131 double 00132 getRadius () const; 00133 00134 /** \brief Allows to set the radius to the background. 00135 * \param[in] radius new radius to the background 00136 */ 00137 void 00138 setRadius (double radius); 00139 00140 /** \brief Returns weight that every edge from the source point has. */ 00141 double 00142 getSourceWeight () const; 00143 00144 /** \brief Allows to set weight for source edges. Every edge that comes from the source point will have that weight. 00145 * \param[in] weight new weight 00146 */ 00147 void 00148 setSourceWeight (double weight); 00149 00150 /** \brief Returns search method that is used for finding KNN. 00151 * The graph is build such way that it contains the edges that connect point and its KNN. 00152 */ 00153 KdTreePtr 00154 getSearchMethod () const; 00155 00156 /** \brief Allows to set search method for finding KNN. 00157 * The graph is build such way that it contains the edges that connect point and its KNN. 00158 * \param[in] search search method that will be used for finding KNN. 00159 */ 00160 void 00161 setSearchMethod (const KdTreePtr& tree); 00162 00163 /** \brief Returns the number of neighbours to find. */ 00164 unsigned int 00165 getNumberOfNeighbours () const; 00166 00167 /** \brief Allows to set the number of neighbours to find. 00168 * \param[in] number_of_neighbours new number of neighbours 00169 */ 00170 void 00171 setNumberOfNeighbours (unsigned int neighbour_number); 00172 00173 /** \brief Returns the points that must belong to foreground. */ 00174 std::vector<PointT, Eigen::aligned_allocator<PointT> > 00175 getForegroundPoints () const; 00176 00177 /** \brief Allows to specify points which are known to be the points of the object. 00178 * \param[in] foreground_points point cloud that contains foreground points. At least one point must be specified. 00179 */ 00180 void 00181 setForegroundPoints (typename pcl::PointCloud<PointT>::Ptr foreground_points); 00182 00183 /** \brief Returns the points that must belong to background. */ 00184 std::vector<PointT, Eigen::aligned_allocator<PointT> > 00185 getBackgroundPoints () const; 00186 00187 /** \brief Allows to specify points which are known to be the points of the background. 00188 * \param[in] background_points point cloud that contains background points. 00189 */ 00190 void 00191 setBackgroundPoints (typename pcl::PointCloud<PointT>::Ptr background_points); 00192 00193 /** \brief This method launches the segmentation algorithm and returns the clusters that were 00194 * obtained during the segmentation. The indices of points that belong to the object will be stored 00195 * in the cluster with index 1, other indices will be stored in the cluster with index 0. 00196 * \param[out] clusters clusters that were obtained. Each cluster is an array of point indices. 00197 */ 00198 void 00199 extract (std::vector <pcl::PointIndices>& clusters); 00200 00201 /** \brief Returns that flow value that was calculated during the segmentation. */ 00202 double 00203 getMaxFlow () const; 00204 00205 /** \brief Returns the graph that was build for finding the minimum cut. */ 00206 typename boost::shared_ptr<typename pcl::MinCutSegmentation<PointT>::mGraph> 00207 getGraph () const; 00208 00209 /** \brief Returns the colored cloud. Points that belong to the object have the same color. */ 00210 pcl::PointCloud<pcl::PointXYZRGB>::Ptr 00211 getColoredCloud (); 00212 00213 protected: 00214 00215 /** \brief This method simply builds the graph that will be used during the segmentation. */ 00216 bool 00217 buildGraph (); 00218 00219 /** \brief Returns unary potential(data cost) for the given point index. 00220 * In other words it calculates weights for (source, point) and (point, sink) edges. 00221 * \param[in] point index of the point for which weights will be calculated 00222 * \param[out] source_weight calculated weight for the (source, point) edge 00223 * \param[out] sink_weight calculated weight for the (point, sink) edge 00224 */ 00225 void 00226 calculateUnaryPotential (int point, double& source_weight, double& sink_weight) const; 00227 00228 /** \brief This method simply adds the edge from the source point to the target point with a given weight. 00229 * \param[in] source index of the source point of the edge 00230 * \param[in] target index of the target point of the edge 00231 * \param[in] weight weight that will be assigned to the (source, target) edge 00232 */ 00233 bool 00234 addEdge (int source, int target, double weight); 00235 00236 /** \brief Returns the binary potential(smooth cost) for the given indices of points. 00237 * In other words it returns weight that must be assigned to the edge from source to target point. 00238 * \param[in] source index of the source point of the edge 00239 * \param[in] target index of the target point of the edge 00240 */ 00241 double 00242 calculateBinaryPotential (int source, int target) const; 00243 00244 /** \brief This method recalculates unary potentials(data cost) if some changes were made, instead of creating new graph. */ 00245 bool 00246 recalculateUnaryPotentials (); 00247 00248 /** \brief This method recalculates binary potentials(smooth cost) if some changes were made, instead of creating new graph. */ 00249 bool 00250 recalculateBinaryPotentials (); 00251 00252 /** \brief This method analyzes the residual network and assigns a label to every point in the cloud. 00253 * \param[in] residual_capacity residual network that was obtained during the segmentation 00254 */ 00255 void 00256 assembleLabels (ResidualCapacityMap& residual_capacity); 00257 00258 protected: 00259 00260 /** \brief Stores the sigma coefficient. It is used for finding smooth costs. More information can be found in the article. */ 00261 double inverse_sigma_; 00262 00263 /** \brief Signalizes if the binary potentials are valid. */ 00264 bool binary_potentials_are_valid_; 00265 00266 /** \brief Used for comparison of the floating point numbers. */ 00267 double epsilon_; 00268 00269 /** \brief Stores the distance to the background. */ 00270 double radius_; 00271 00272 /** \brief Signalizes if the unary potentials are valid. */ 00273 bool unary_potentials_are_valid_; 00274 00275 /** \brief Stores the weight for every edge that comes from source point. */ 00276 double source_weight_; 00277 00278 /** \brief Stores the search method that will be used for finding K nearest neighbors. Neighbours are used for building the graph. */ 00279 KdTreePtr search_; 00280 00281 /** \brief Stores the number of neighbors to find. */ 00282 unsigned int number_of_neighbours_; 00283 00284 /** \brief Signalizes if the graph is valid. */ 00285 bool graph_is_valid_; 00286 00287 /** \brief Stores the points that are known to be in the foreground. */ 00288 std::vector<PointT, Eigen::aligned_allocator<PointT> > foreground_points_; 00289 00290 /** \brief Stores the points that are known to be in the background. */ 00291 std::vector<PointT, Eigen::aligned_allocator<PointT> > background_points_; 00292 00293 /** \brief After the segmentation it will contain the segments. */ 00294 std::vector <pcl::PointIndices> clusters_; 00295 00296 /** \brief Stores the graph for finding the maximum flow. */ 00297 boost::shared_ptr<mGraph> graph_; 00298 00299 /** \brief Stores the capacity of every edge in the graph. */ 00300 boost::shared_ptr<CapacityMap> capacity_; 00301 00302 /** \brief Stores reverse edges for every edge in the graph. */ 00303 boost::shared_ptr<ReverseEdgeMap> reverse_edges_; 00304 00305 /** \brief Stores the vertices of the graph. */ 00306 std::vector< VertexDescriptor > vertices_; 00307 00308 /** \brief Stores the information about the edges that were added to the graph. It is used to avoid the duplicate edges. */ 00309 std::vector< std::set<int> > edge_marker_; 00310 00311 /** \brief Stores the vertex that serves as source. */ 00312 VertexDescriptor source_; 00313 00314 /** \brief Stores the vertex that serves as sink. */ 00315 VertexDescriptor sink_; 00316 00317 /** \brief Stores the maximum flow value that was calculated during the segmentation. */ 00318 double max_flow_; 00319 00320 public: 00321 EIGEN_MAKE_ALIGNED_OPERATOR_NEW 00322 }; 00323 } 00324 00325 #ifdef PCL_NO_PRECOMPILE 00326 #include <pcl/segmentation/impl/min_cut_segmentation.hpp> 00327 #endif 00328 00329 #endif 00330 #endif