Point Cloud Library (PCL)  1.7.0
/tmp/buildd/pcl-1.7-1.7.0/segmentation/include/pcl/segmentation/min_cut_segmentation.h
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