grabcut.h
Go to the documentation of this file.
00001 /*
00002  * Software License Agreement (BSD License)
00003  *
00004  *  Point Cloud Library (PCL) - www.pointclouds.org
00005  *  Copyright (c) 2012-, Open Perception, Inc.
00006  *
00007  *  All rights reserved.
00008  *
00009  *  Redistribution and use in source and binary forms, with or without
00010  *  modification, are permitted provided that the following conditions
00011  *  are met:
00012  *
00013  *   * Redistributions of source code must retain the above copyright
00014  *     notice, this list of conditions and the following disclaimer.
00015  *   * Redistributions in binary form must reproduce the above
00016  *     copyright notice, this list of conditions and the following
00017  *     disclaimer in the documentation and/or other materials provided
00018  *     with the distribution.
00019  *   * Neither the name of Willow Garage, Inc. nor the names of its
00020  *     contributors may be used to endorse or promote products derived
00021  *     from this software without specific prior written permission.
00022  *
00023  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00024  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00025  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00026  *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
00027  *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00028  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00029  *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00030  *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00031  *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00032  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00033  *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00034  *  POSSIBILITY OF SUCH DAMAGE.
00035  *
00036  * $Id$
00037  *
00038  */
00039 
00040 #ifndef PCL_SEGMENTATION_GRABCUT
00041 #define PCL_SEGMENTATION_GRABCUT
00042 
00043 #include <pcl/point_cloud.h>
00044 #include <pcl/pcl_base.h>
00045 #include <pcl/point_types.h>
00046 #include <pcl/segmentation/boost.h>
00047 #include <pcl/search/search.h>
00048 
00049 namespace pcl
00050 {
00051   namespace segmentation
00052   {
00053     namespace grabcut
00054     {
00061       class BoykovKolmogorov
00062       {        
00063         public:
00064           typedef int vertex_descriptor;
00065           typedef double edge_capacity_type;
00066         
00068           BoykovKolmogorov (std::size_t max_nodes = 0);
00070           virtual ~BoykovKolmogorov () {}
00072           size_t 
00073           numNodes () const { return nodes_.size (); }
00075           void 
00076           reset ();
00078           void 
00079           clear ();
00081           int 
00082           addNodes (std::size_t n = 1);
00084           void 
00085           addConstant (double c) { flow_value_ += c; }
00087           void 
00088           addSourceEdge (int u, double cap);
00090           void 
00091           addTargetEdge (int u, double cap);
00094           void 
00095           addEdge (int u, int v, double cap_uv, double cap_vu = 0.0);
00097           double
00098           solve ();
00100           bool 
00101           inSourceTree (int u) const { return (cut_[u] == SOURCE); }
00103           bool 
00104           inSinkTree (int u) const { return (cut_[u] == TARGET); }
00106           double
00107           operator() (int u, int v) const;
00108 
00109         protected:
00111           typedef enum { FREE = 0x00, SOURCE = 0x01, TARGET = 0x02 } nodestate;
00113           typedef std::map<int, double> capacitated_edge;
00115           typedef std::pair<capacitated_edge::iterator, capacitated_edge::iterator> edge_pair;
00117           void 
00118           preAugmentPaths ();
00120           void 
00121           initializeTrees ();
00123           std::pair<int, int> 
00124           expandTrees ();
00126           void 
00127           augmentPath (const std::pair<int, int>& path, std::deque<int>& orphans);
00129           void 
00130           adoptOrphans (std::deque<int>& orphans);
00132           void clearActive ();
00134           inline bool 
00135           isActiveSetEmpty () const { return (active_head_ == TERMINAL); }
00137           inline bool 
00138           isActive (int u) const { return ((u == active_head_) || (active_list_[u].first != TERMINAL)); }
00140           void 
00141           markActive (int u);
00143           void 
00144           markInactive (int u);
00146           std::vector<double> source_edges_; 
00148           std::vector<double> target_edges_; 
00150           std::vector<capacitated_edge> nodes_; 
00152           double flow_value_;
00154           std::vector<unsigned char> cut_;  
00155 
00156         private:
00158           static const int TERMINAL = -1;
00160           std::vector<std::pair<int, edge_pair> > parents_; 
00162           std::vector<std::pair<int, int> > active_list_; 
00163           int active_head_, active_tail_;
00164       };
00165 
00167       struct Color
00168       {
00169         Color () : r (0), g (0), b (0) {}
00170         Color (float _r, float _g, float _b) : r(_r), g(_g), b(_b) {}
00171         Color (const pcl::RGB& color) : r (color.r), g (color.g), b (color.b) {}
00172         
00173         template<typename PointT>
00174         Color (const PointT& p)
00175         {
00176           r = static_cast<float> (p.r);
00177           g = static_cast<float> (p.g);
00178           b = static_cast<float> (p.b);
00179         }
00180         
00181         template<typename PointT> 
00182         operator PointT () const
00183         { 
00184           PointT p;
00185           p.r = static_cast<uint32_t> (r);
00186           p.g = static_cast<uint32_t> (g);
00187           p.b = static_cast<uint32_t> (b);
00188           return (p);
00189         }
00190         
00191         float r, g, b;
00192       };
00194       typedef pcl::PointCloud<Color> Image;
00200       float 
00201       colorDistance (const Color& c1, const Color& c2);
00203       enum TrimapValue { TrimapUnknown = -1, TrimapForeground, TrimapBackground };
00205       enum SegmentationValue { SegmentationForeground = 0, SegmentationBackground };      
00207       struct Gaussian
00208       {
00209         Gaussian () {}
00211         Color mu;
00213         Eigen::Matrix3f covariance;
00215         float determinant;
00217         Eigen::Matrix3f inverse;                        
00219         float pi;
00221         float eigenvalue;
00223         Eigen::Vector3f eigenvector;
00224       };
00225       
00226       class GMM
00227       {
00228         public:
00230           GMM () : gaussians_ (0) {}
00232           GMM (std::size_t K) : gaussians_ (K) {}
00234           ~GMM () {}
00236           std::size_t 
00237           getK () const { return gaussians_.size (); }
00239           void 
00240           resize (std::size_t K) { gaussians_.resize (K); }
00242           Gaussian& 
00243           operator[] (std::size_t pos) { return (gaussians_[pos]); }
00245           const Gaussian& 
00246           operator[] (std::size_t pos) const { return (gaussians_[pos]); }
00248           float 
00249           probabilityDensity (const Color &c);
00251           float 
00252           probabilityDensity(std::size_t i, const Color &c);
00253       
00254         private:
00256           std::vector<Gaussian> gaussians_;      
00257       };
00258 
00260       class GaussianFitter
00261       {
00262         public:
00263         GaussianFitter (float epsilon = 0.0001)
00264           : sum_ (Eigen::Vector3f::Zero ())
00265           , accumulator_ (Eigen::Matrix3f::Zero ())
00266           , count_ (0)
00267           , epsilon_ (epsilon)
00268         { }
00269       
00271         void 
00272         add (const Color &c);
00274         void 
00275         fit (Gaussian& g, std::size_t total_count, bool compute_eigens = false) const;
00277         float
00278         getEpsilon () { return (epsilon_); }
00283         void
00284         setEpsilon (float epsilon) { epsilon_ = epsilon; }
00285       
00286         private:
00288         Eigen::Vector3f sum_;
00290         Eigen::Matrix3f accumulator_;
00292         uint32_t count_;        
00294         float epsilon_;
00295       };
00296 
00298       void 
00299       buildGMMs (const Image &image, 
00300                  const std::vector<int>& indices,
00301                  const std::vector<SegmentationValue> &hardSegmentation,
00302                  std::vector<std::size_t> &components,
00303                  GMM &background_GMM, GMM &foreground_GMM);
00305       void 
00306       learnGMMs (const Image& image, 
00307                  const std::vector<int>& indices,
00308                  const std::vector<SegmentationValue>& hard_segmentation,
00309                  std::vector<std::size_t>& components,
00310                  GMM& background_GMM, GMM& foreground_GMM);
00311     }
00312   };
00313   
00322   template <typename PointT>
00323   class GrabCut : public pcl::PCLBase<PointT>
00324   {
00325     public:
00326       typedef typename pcl::search::Search<PointT> KdTree;
00327       typedef typename pcl::search::Search<PointT>::Ptr KdTreePtr;
00328       typedef typename PCLBase<PointT>::PointCloudConstPtr PointCloudConstPtr;
00329       typedef typename PCLBase<PointT>::PointCloudPtr PointCloudPtr;
00330       using PCLBase<PointT>::input_;
00331       using PCLBase<PointT>::indices_;
00332       using PCLBase<PointT>::fake_indices_;
00333     
00335       GrabCut (uint32_t K = 5, float lambda = 50.f)
00336         : K_ (K)
00337         , lambda_ (lambda)
00338         , initialized_ (false)
00339         , nb_neighbours_ (9)
00340       {}
00342       virtual ~GrabCut () {};
00343       // /// Set input cloud
00344       void
00345       setInputCloud (const PointCloudConstPtr& cloud);
00347       void
00348       setBackgroundPoints (const PointCloudConstPtr& background_points);
00350       void
00351       setBackgroundPointsIndices (int x1, int y1, int x2, int y2);
00353       void
00354       setBackgroundPointsIndices (const PointIndicesConstPtr& indices);
00356       virtual void 
00357       refine ();
00359       virtual int 
00360       refineOnce ();
00362       float
00363       getLambda () { return (lambda_); }
00367       void
00368       setLambda (float lambda) { lambda_ = lambda; }
00370       uint32_t
00371       getK () { return (K_); }
00375       void
00376       setK (uint32_t K) { K_ = K; }
00380       inline void
00381       setSearchMethod (const KdTreePtr &tree) { tree_ = tree; }
00383       inline KdTreePtr
00384       getSearchMethod () { return (tree_); }
00388       void
00389       setNumberOfNeighbours (int nb_neighbours) { nb_neighbours_ = nb_neighbours; }
00391       int
00392       getNumberOfNeighbours () const { return (nb_neighbours_); }
00398       void
00399       extract (std::vector<pcl::PointIndices>& clusters);
00400 
00401     protected:
00402       // Storage for N-link weights, each pixel stores links to nb_neighbours      
00403       struct NLinks
00404       {
00405         NLinks () : nb_links (0), indices (0), dists (0), weights (0) {}
00406         
00407         int nb_links;
00408         std::vector<int> indices;
00409         std::vector<float> dists;
00410         std::vector<float> weights;
00411       };
00412       bool
00413       initCompute ();    
00414       typedef pcl::segmentation::grabcut::BoykovKolmogorov::vertex_descriptor vertex_descriptor;
00415       // /** Update hard segmentation after running GraphCut, \return the number of pixels that have
00416       //   * changed from foreground to background or vice versa. 
00417       //   */
00418       // int 
00419       // updateHardSegmentation ();
00421       void 
00422       computeBeta ();
00424       void 
00425       computeL ();
00427       void 
00428       computeNLinks ();
00430       float 
00431       computeNLink (uint32_t x1, uint32_t y1, uint32_t x2, uint32_t y2);
00433       void 
00434       setTrimap (const PointIndicesConstPtr &indices, segmentation::grabcut::TrimapValue t);
00435       int
00436       updateHardSegmentation ();
00438       virtual void 
00439       fitGMMs ();
00441       void 
00442       initGraph ();
00444       void
00445       addEdge (vertex_descriptor v1, vertex_descriptor v2, float capacity, float rev_capacity);
00447       void
00448       setTerminalWeights (vertex_descriptor v, float source_capacity, float sink_capacity);
00450       inline bool
00451       isSource (vertex_descriptor v) { return (graph_.inSourceTree (v)); }
00453       uint32_t width_;
00455       uint32_t height_;
00456       // Variables used in formulas from the paper.
00458       uint32_t K_;
00460       float lambda_;            
00462       float beta_;
00464       float L_;
00466       KdTreePtr tree_;
00468       int nb_neighbours_;
00470       bool initialized_;
00472       std::vector<NLinks> n_links_;
00474       segmentation::grabcut::Image::Ptr image_;
00475       std::vector<segmentation::grabcut::TrimapValue> trimap_;
00476       std::vector<std::size_t> GMM_component_;
00477       std::vector<segmentation::grabcut::SegmentationValue> hard_segmentation_;
00478       // Not yet implemented (this would be interpreted as alpha)
00479       std::vector<float> soft_segmentation_;    
00480       segmentation::grabcut::GMM background_GMM_, foreground_GMM_;
00481       // Graph part
00483       pcl::segmentation::grabcut::BoykovKolmogorov graph_;
00485       std::vector<vertex_descriptor> graph_nodes_;
00486   };
00487 }
00488 
00489 #include <pcl/segmentation/impl/grabcut.hpp>
00490 
00491 #endif


pcl
Author(s): Open Perception
autogenerated on Wed Aug 26 2015 15:24:34