Point Cloud Library (PCL)  1.7.0
/tmp/buildd/pcl-1.7-1.7.0/segmentation/include/pcl/segmentation/region_growing.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  * Author : Sergey Ushakov
00036  * Email  : mine_all_mine@bk.ru
00037  *
00038  */
00039 
00040 #ifndef PCL_REGION_GROWING_H_
00041 #define PCL_REGION_GROWING_H_
00042 
00043 #include <pcl/pcl_base.h>
00044 #include <pcl/search/search.h>
00045 #include <pcl/point_cloud.h>
00046 #include <pcl/point_types.h>
00047 #include <list>
00048 #include <math.h>
00049 #include <time.h>
00050 
00051 namespace pcl
00052 {
00053   /** \brief
00054     * Implements the well known Region Growing algorithm used for segmentation.
00055     * Description can be found in the article
00056     * "Segmentation of point clouds using smoothness constraint"
00057     * by T. Rabbania, F. A. van den Heuvelb, G. Vosselmanc.
00058     * In addition to residual test, the possibility to test curvature is added.
00059     */
00060   template <typename PointT, typename NormalT>
00061   class PCL_EXPORTS RegionGrowing : public pcl::PCLBase<PointT>
00062   {
00063     public:
00064 
00065       typedef pcl::search::Search <PointT> KdTree;
00066       typedef typename KdTree::Ptr KdTreePtr;
00067       typedef pcl::PointCloud <NormalT> Normal;
00068       typedef typename Normal::Ptr NormalPtr;
00069       typedef pcl::PointCloud <PointT> PointCloud;
00070 
00071       using PCLBase <PointT>::input_;
00072       using PCLBase <PointT>::indices_;
00073       using PCLBase <PointT>::initCompute;
00074       using PCLBase <PointT>::deinitCompute;
00075 
00076     public:
00077 
00078       /** \brief Constructor that sets default values for member variables. */
00079       RegionGrowing ();
00080 
00081       /** \brief This destructor destroys the cloud, normals and search method used for
00082         * finding KNN. In other words it frees memory.
00083         */
00084       virtual
00085       ~RegionGrowing ();
00086 
00087       /** \brief Get the minimum number of points that a cluster needs to contain in order to be considered valid. */
00088       int
00089       getMinClusterSize ();
00090 
00091       /** \brief Set the minimum number of points that a cluster needs to contain in order to be considered valid. */
00092       void
00093       setMinClusterSize (int min_cluster_size);
00094 
00095       /** \brief Get the maximum number of points that a cluster needs to contain in order to be considered valid. */
00096       int
00097       getMaxClusterSize ();
00098 
00099       /** \brief Set the maximum number of points that a cluster needs to contain in order to be considered valid. */
00100       void
00101       setMaxClusterSize (int max_cluster_size);
00102 
00103       /** \brief Returns the flag value. This flag signalizes which mode of algorithm will be used.
00104         * If it is set to true than it will work as said in the article. This means that
00105         * it will be testing the angle between normal of the current point and it's neighbours normal.
00106         * Otherwise, it will be testing the angle between normal of the current point
00107         * and normal of the initial point that was chosen for growing new segment.
00108         */
00109       bool
00110       getSmoothModeFlag () const;
00111 
00112       /** \brief This function allows to turn on/off the smoothness constraint.
00113         * \param[in] value new mode value, if set to true then the smooth version will be used.
00114         */
00115       void
00116       setSmoothModeFlag (bool value);
00117 
00118       /** \brief Returns the flag that signalize if the curvature test is turned on/off. */
00119       bool
00120       getCurvatureTestFlag () const;
00121 
00122       /** \brief Allows to turn on/off the curvature test. Note that at least one test
00123         * (residual or curvature) must be turned on. If you are turning curvature test off
00124         * then residual test will be turned on automatically.
00125         * \param[in] value new value for curvature test. If set to true then the test will be turned on
00126         */
00127       virtual void
00128       setCurvatureTestFlag (bool value);
00129 
00130       /** \brief Returns the flag that signalize if the residual test is turned on/off. */
00131       bool
00132       getResidualTestFlag () const;
00133 
00134       /** \brief
00135         * Allows to turn on/off the residual test. Note that at least one test
00136         * (residual or curvature) must be turned on. If you are turning residual test off
00137         * then curvature test will be turned on automatically.
00138         * \param[in] value new value for residual test. If set to true then the test will be turned on
00139         */
00140       virtual void
00141       setResidualTestFlag (bool value);
00142 
00143       /** \brief Returns smoothness threshold. */
00144       float
00145       getSmoothnessThreshold () const;
00146 
00147       /** \brief Allows to set smoothness threshold used for testing the points.
00148         * \param[in] theta new threshold value for the angle between normals
00149         */
00150       void
00151       setSmoothnessThreshold (float theta);
00152 
00153       /** \brief Returns residual threshold. */
00154       float
00155       getResidualThreshold () const;
00156 
00157       /** \brief Allows to set residual threshold used for testing the points.
00158         * \param[in] residual new threshold value for residual testing
00159         */
00160       void
00161       setResidualThreshold (float residual);
00162 
00163       /** \brief Returns curvature threshold. */
00164       float
00165       getCurvatureThreshold () const;
00166 
00167       /** \brief Allows to set curvature threshold used for testing the points.
00168         * \param[in] curvature new threshold value for curvature testing
00169         */
00170       void
00171       setCurvatureThreshold (float curvature);
00172 
00173       /** \brief Returns the number of nearest neighbours used for KNN. */
00174       unsigned int
00175       getNumberOfNeighbours () const;
00176 
00177       /** \brief Allows to set the number of neighbours. For more information check the article.
00178         * \param[in] neighbour_number number of neighbours to use
00179         */
00180       void
00181       setNumberOfNeighbours (unsigned int neighbour_number);
00182 
00183       /** \brief Returns the pointer to the search method that is used for KNN. */
00184       KdTreePtr
00185       getSearchMethod () const;
00186 
00187       /** \brief Allows to set search method that will be used for finding KNN.
00188         * \param[in] search search method to use
00189         */
00190       void
00191       setSearchMethod (const KdTreePtr& tree);
00192 
00193       /** \brief Returns normals. */
00194       NormalPtr
00195       getInputNormals () const;
00196 
00197       /** \brief This method sets the normals. They are needed for the algorithm, so if
00198         * no normals will be set, the algorithm would not be able to segment the points.
00199         * \param[in] norm normals that will be used in the algorithm
00200         */
00201       void
00202       setInputNormals (const NormalPtr& norm);
00203 
00204       /** \brief This method launches the segmentation algorithm and returns the clusters that were
00205         * obtained during the segmentation.
00206         * \param[out] clusters clusters that were obtained. Each cluster is an array of point indices.
00207         */
00208       virtual void
00209       extract (std::vector <pcl::PointIndices>& clusters);
00210 
00211       /** \brief For a given point this function builds a segment to which it belongs and returns this segment.
00212         * \param[in] index index of the initial point which will be the seed for growing a segment.
00213         * \param[out] cluster cluster to which the point belongs.
00214         */
00215       virtual void
00216       getSegmentFromPoint (int index, pcl::PointIndices& cluster);
00217 
00218       /** \brief If the cloud was successfully segmented, then function
00219         * returns colored cloud. Otherwise it returns an empty pointer.
00220         * Points that belong to the same segment have the same color.
00221         * But this function doesn't guarantee that different segments will have different
00222         * color(it all depends on RNG). Points that were not listed in the indices array will have red color.
00223         */
00224       pcl::PointCloud<pcl::PointXYZRGB>::Ptr
00225       getColoredCloud ();
00226 
00227       /** \brief If the cloud was successfully segmented, then function
00228         * returns colored cloud. Otherwise it returns an empty pointer.
00229         * Points that belong to the same segment have the same color.
00230         * But this function doesn't guarantee that different segments will have different
00231         * color(it all depends on RNG). Points that were not listed in the indices array will have red color.
00232         */
00233       pcl::PointCloud<pcl::PointXYZRGBA>::Ptr
00234       getColoredCloudRGBA ();
00235 
00236     protected:
00237 
00238       /** \brief This method simply checks if it is possible to execute the segmentation algorithm with
00239         * the current settings. If it is possible then it returns true.
00240         */
00241       virtual bool
00242       prepareForSegmentation ();
00243 
00244       /** \brief This method finds KNN for each point and saves them to the array
00245         * because the algorithm needs to find KNN a few times.
00246         */
00247       virtual void
00248       findPointNeighbours ();
00249 
00250       /** \brief This function implements the algorithm described in the article
00251         * "Segmentation of point clouds using smoothness constraint"
00252         * by T. Rabbania, F. A. van den Heuvelb, G. Vosselmanc.
00253         */
00254       void
00255       applySmoothRegionGrowingAlgorithm ();
00256 
00257       /** \brief This method grows a segment for the given seed point. And returns the number of its points.
00258         * \param[in] initial_seed index of the point that will serve as the seed point
00259         * \param[in] segment_number indicates which number this segment will have
00260         */
00261       int
00262       growRegion (int initial_seed, int segment_number);
00263 
00264       /** \brief This function is checking if the point with index 'nghbr' belongs to the segment.
00265         * If so, then it returns true. It also checks if this point can serve as the seed.
00266         * \param[in] initial_seed index of the initial point that was passed to the growRegion() function
00267         * \param[in] point index of the current seed point
00268         * \param[in] nghbr index of the point that is neighbour of the current seed
00269         * \param[out] is_a_seed this value is set to true if the point with index 'nghbr' can serve as the seed
00270         */
00271       virtual bool
00272       validatePoint (int initial_seed, int point, int nghbr, bool& is_a_seed) const;
00273 
00274       /** \brief This function simply assembles the regions from list of point labels.
00275         * \param[out] clusters clusters that were obtained during the segmentation process.
00276         * Each cluster is an array of point indices.
00277         */
00278       void
00279       assembleRegions ();
00280 
00281     protected:
00282 
00283       /** \brief Stores the minimum number of points that a cluster needs to contain in order to be considered valid. */
00284       int min_pts_per_cluster_;
00285 
00286       /** \brief Stores the maximum number of points that a cluster needs to contain in order to be considered valid. */
00287       int max_pts_per_cluster_;
00288 
00289       /** \brief Flag that signalizes if the smoothness constraint will be used. */
00290       bool smooth_mode_flag_;
00291 
00292       /** \brief If set to true then curvature test will be done during segmentation. */
00293       bool curvature_flag_;
00294 
00295       /** \brief If set to true then residual test will be done during segmentation. */
00296       bool residual_flag_;
00297 
00298       /** \brief Thershold used for testing the smoothness between points. */
00299       float theta_threshold_;
00300 
00301       /** \brief Thershold used in residual test. */
00302       float residual_threshold_;
00303 
00304       /** \brief Thershold used in curvature test. */
00305       float curvature_threshold_;
00306 
00307       /** \brief Number of neighbours to find. */
00308       unsigned int neighbour_number_;
00309 
00310       /** \brief Serch method that will be used for KNN. */
00311       KdTreePtr search_;
00312 
00313       /** \brief Contains normals of the points that will be segmented. */
00314       NormalPtr normals_;
00315 
00316       /** \brief Contains neighbours of each point. */
00317       std::vector<std::vector<int> > point_neighbours_;
00318 
00319       /** \brief Point labels that tells to which segment each point belongs. */
00320       std::vector<int> point_labels_;
00321 
00322       /** \brief If set to true then normal/smoothness test will be done during segmentation.
00323         * It is always set to true for the usual region growing algorithm. It is used for turning on/off the test
00324         * for smoothness in the child class RegionGrowingRGB.*/
00325       bool normal_flag_;
00326 
00327       /** \brief Tells how much points each segment contains. Used for reserving memory. */
00328       std::vector<int> num_pts_in_segment_;
00329 
00330       /** \brief After the segmentation it will contain the segments. */
00331       std::vector <pcl::PointIndices> clusters_;
00332 
00333       /** \brief Stores the number of segments. */
00334       int number_of_segments_;
00335 
00336     public:
00337       EIGEN_MAKE_ALIGNED_OPERATOR_NEW
00338   };
00339 
00340   /** \brief This function is used as a comparator for sorting. */
00341   inline bool
00342   comparePair (std::pair<float, int> i, std::pair<float, int> j)
00343   {
00344     return (i.first < j.first);
00345   }
00346 }
00347 
00348 #ifdef PCL_NO_PRECOMPILE
00349 #include <pcl/segmentation/impl/region_growing.hpp>
00350 #endif
00351 
00352 #endif