精华内容
下载资源
问答
  • 使得同一划分内的点云拥有相似的特征,点云的有效分割往往是许多应用的前提, 例如逆向工作,CAD领域对零件的不同扫描表面进行分割, 然后才能更好的进行空洞修复曲面重建,特征描述提取, 进而进行基于3D内容的...

    点云分割

    博文末尾支持二维码赞赏哦 _

    点云分割是根据空间,几何和纹理等特征对点云进行划分,
    使得同一划分内的点云拥有相似的特征,点云的有效分割往往是许多应用的前提,
    例如逆向工作,CAD领域对零件的不同扫描表面进行分割,
    然后才能更好的进行空洞修复曲面重建,特征描述和提取,
    进而进行基于3D内容的检索,组合重用等。
    
    点云的分割与分类也算是一个大Topic了,这里因为多了一维就和二维图像比多了许多问题,
    点云分割又分为区域提取、线面提取、语义分割与聚类等。
    同样是分割问题,点云分割涉及面太广,确实是三言两语说不清楚的。
    只有从字面意思去理解了,遇到具体问题再具体归类。
    一般说来,点云分割是目标识别分类的基础。
    

     

    分割:

    区域声场、
    Ransac线面提取、
    NDT-RANSAC、
    K-Means、
    Normalize Cut、
    3D Hough Transform(线面提取)、
    连通分析。
    

    分类:

    基于点的分类,
    基于分割的分类,
    监督分类与非监督分类
    

    语义分类:

    获取场景点云之后,如何有效的利用点云信息,如何理解点云场景的内容,
    进行点云的分类很有必要,需要为每个点云进行Labeling。
    可以分为基于点的分类方法和基于分割的分类方法。
    从方法上可以分为基于监督分类的技术或者非监督分类技术,
    深度学习也是一个很有希望应用的技术
    
    
    

     

    随机采样一致性 采样一致性算法 sample_consensus

     

    
     
    在计算机视觉领域广泛的使用各种不同的采样一致性参数估计算法用于排除错误的样本,
    样本不同对应的应用不同,例如剔除错误的配准点对,分割出 处在模型上的点集,
    PCL中以随机采样一致性算法(RANSAC)为核心,
    
    同时实现了五种类似与随机采样一致形算法的随机参数估计算法:
        1. 例如随机采样一致性算法(RANSAC)、
        2. 最大似然一致性算法(MLESAC)、
        3. 最小中值方差一致性算法(LMEDS)等,
    所有估计参数算法都符合一致性原则。
    在PCL中设计的采样一致性算法的应用主要就是对点云进行分割,根据设定的不同的几个模型,
    估计对应的几何参数模型的参数,在一定容许的范围内分割出在模型上的点云。 
    

     

     

    RANSAC随机采样一致性算法的介绍

     

    
     
    RANSAC是“RANdom SAmple Consensus(随机抽样一致)”的缩写。
    
    它可以从一组包含“局外点”的观测数据集中,通过迭代方式估计数学模型的参数。
    
    它是一种不确定的算法——它有一定的概率得出一个合理的结果;
    
    为了提高概率必须提高迭代次数。
    数据分两种:
       有效数据(inliers)和
       无效数据(outliers)。
       
     偏差不大的数据称为有效数据,
     偏差大的数据是无效数据。
     
     如果有效数据占大多数,无效数据只是少量时,
     我们可以通过最小二乘法或类似的方法来确定模型的参数和误差;
     如果无效数据很多(比如超过了50%的数据都是无效数据),
     最小二乘法就 失效了,我们需要新的算法。
    
    
    一个简单的例子是从一组观测数据中找出合适的2维直线。
    假设观测数据中包含局内点和局外点,
    其中局内点近似的被直线所通过,而局外点远离于直线。
    简单的最 小二乘法不能找到适应于局内点的直线,原因是最小二乘法尽量去适应包括局外点在内的所有点。
    相反,RANSAC能得出一个仅仅用局内点计算出模型,并且概 率还足够高。
    但是,RANSAC并不能保证结果一定正确,为了保证算法有足够高的合理概率,我们必须小心的选择算法的参数。
    包含很多局外点的数据集   RANSAC找到的直线(局外点并不影响结果)
    

     

    RANSAC算法概述

     

    
     
    RANSAC算法的输入是一组观测数据,一个可以解释或者适应于观测数据的参数化模型,一些可信的参数。
    RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点,
    并用下述方法进行验证:
    
    1.有一个模型适应于假设的局内点,即所有的未知参数都能从假设的局内点计算得出。
    2.用1中得到的模型去测试所有的其它数据,如果某个点适用于估计的模型,认为它也是局内点。
    3.如果有足够多的点被归类为假设的局内点,那么估计的模型就足够合理。
    4.然后,用所有假设的局内点去重新估计模型,因为它仅仅被初始的假设局内点估计过。
    5.最后,通过估计局内点与模型的错误率来评估模型。
    

    算法

    伪码形式的算法如下所示:
    

    输入:

    data —— 一组观测数据
    model —— 适应于数据的模型
    n —— 适用于模型的最少数据个数
    k —— 算法的迭代次数
    t —— 用于决定数据是否适应于模型的阀值
    d —— 判定模型是否适用于数据集的数据数目
    

    输出:

    best_model —— 跟数据最匹配的模型参数(如果没有找到好的模型,返回null)
    best_consensus_set —— 估计出模型的数据点
    best_error —— 跟数据相关的估计出的模型错误
    
          开始:
    iterations = 0
    best_model = null
    best_consensus_set = null
    best_error = 无穷大
    while ( iterations < k )
        maybe_inliers = 从数据集中随机选择n个点
        maybe_model = 适合于maybe_inliers的模型参数
        consensus_set = maybe_inliers
    
        for ( 每个数据集中不属于maybe_inliers的点 )
        if ( 如果点适合于maybe_model,且错误小于t )
          将点添加到consensus_set
        if ( consensus_set中的元素数目大于d )
        已经找到了好的模型,现在测试该模型到底有多好
        better_model = 适合于consensus_set中所有点的模型参数
        this_error = better_model究竟如何适合这些点的度量
        if ( this_error < best_error )
          我们发现了比以前好的模型,保存该模型直到更好的模型出现
          best_model =  better_model
          best_consensus_set = consensus_set
          best_error =  this_error
        增加迭代次数
    返回 best_model, best_consensus_set, best_error    
    

     

    最小中值法(LMedS)

     

    
     
    LMedS的做法很简单,就是从样本中随机抽出N个样本子集,使用最大似然(通常是最小二乘)
    对每个子集计算模型参数和该模型的偏差,记录该模型参
    数及子集中所有样本中偏差居中的那个样本的偏差(即Med偏差),
    最后选取N个样本子集中Med偏差最小的所对应的模型参数作为我们要估计的模型参数。
    

     

    在PCL中sample_consensus模块支持的几何模型:

     

    
     
    1.平面模型   SACMODEL_PLANE  参数  [normal_x normal_y normal_z d]
    
    2.线模型     SACMODEL_LINE   参数   
    [point_on_line.x point_on_line.y point_on_line.z line_direction.x line_direction.y line_direction.z]
    
    3.平面圆模型 SACMODEL_CIRCLE2D  参数 [center.x center.y radius]
    
    4.三维圆模型 SACMODEL_CIRCLE3D
        参数  [center.x, center.y, center.z, radius, normal.x, normal.y, normal.z]
        
    5.球模型    SACMODEL_SPHERE
    
    6.圆柱体模型 SACMODEL_CYLINDER 参数
    [point_on_axis.x point_on_axis.y point_on_axis.z axis_direction.x axis_direction.y axis_direction.z radius]
    
    7.圆锥体模型 SACMODEL_CONE  参数
    [apex.x, apex.y, apex.z, axis_direction.x, axis_direction.y, axis_direction.z, opening_angle]
    
    8.平行线     SACMODEL_PARALLEL_LINE 参数同 线模型 
    

     

    PCL中Sample_consensus模块及类的介绍

     

    
     
    PCL中Sample_consensus库实现了随机采样一致性及其泛化估计算法,
    例如平面,柱面,等各种常见的几何模型,用不同的估计算法和不同的
    几何模型自由的结合估算点云中隐含的具体几何模型的系数,
    实现对点云中所处的几何模型的分割,线,平面,柱面 ,和球面都可以在PCL 库中实现,
    平面模型经常被用到常见的室内平面的分割提取中, 比如墙,地板,桌面,
    其他模型常应用到根据几何结构检测识别和分割物体中,
    一共可以分为两类:
      一类是针对采样一致性及其泛化函数的实现,
      一类是几个不同模型的具体实现,例如:平面,直线,圆球等
    
    
    pcl::SampleConsensusModel< PointT >是随机采样一致性估计算法中不同模型实现的基类,
    所有的采样一致性估计模型都继承于此类,定义了采样一致性模型的相关的一般接口,具体实现由子类完成,其继承关系
    

    模型

    pcl::SampleConsensusModel< PointT >
      |
      |
      |
      |_______________->pcl::SampleConsensusModelPlane< PointT >
          ->pcl::SampleConsensusModelLine< PointT >
          ->pcl::SampleConsensusModelCircle2D< PointT > 实现采样一致性 计算二维平面圆周模型
          ->pcl::SampleConsensusModelCircle3D< PointT >  实现采样一致性计算的三维椎体模型
          ->pcl::SampleConsensusModelSphere< PointT >
          ->pcl::SampleConsensusModelCone< PointT ,PointNT >
          ->pcl::SampleConsensusModelCylinder< PointT ,PointNT >
          ->pcl::SampleConsensusModelRegistration< PointT >			
          ->pcl::SampleConsensusModelStick< PointT >
    

    pcl::SampleConsensus< T > 是采样一致性算法的基类

    1. SampleConsensus (const SampleConsensusModelPtr &model, double threshold, bool random=false)
      其中model设置随机采样性算法使用的模型,threshold 阀值 
    2.设置模型      void     setSampleConsensusModel (const SampleConsensusModelPtr &model)
    3.设置距离阈值  void     setDistanceThreshold (double threshold)
    4.获取距离阈值  double   getDistanceThreshold ()
    5.设置最大迭代次数 void  setMaxIterations (int max_iterations)
    6.获取最大迭代次数 int   getMaxIterations ()
    

     

    1.随机采样一致性 球模型 和 平面模型

     

    pcl::SampleConsensusModelSphere pcl::SampleConsensusModelPlane

     

    
     
    在没有任何参数的情况下,三维窗口显示创建的原始点云(含有局内点和局外点),
    如图所示,很明显这是一个带有噪声的菱形平面,
    噪声点是立方体,自己要是我们在产生点云是生成的是随机数生在(0,1)范围内。


    github

     

    #include <iostream>
    #include <pcl/console/parse.h>
    #include <pcl/filters/extract_indices.h>          // 由索引提取点云
    #include <pcl/io/pcd_io.h>
    #include <pcl/point_types.h>
    #include <pcl/sample_consensus/ransac.h>          // 采样一致性
    #include <pcl/sample_consensus/sac_model_plane.h> // 平面模型
    #include <pcl/sample_consensus/sac_model_sphere.h>// 球模型
    #include <pcl/visualization/pcl_visualizer.h>     // 可视化
    #include <boost/thread/thread.hpp>
    
    /*
    输入点云
    返回一个可视化的对象
    */
    boost::shared_ptr<pcl::visualization::PCLVisualizer>
    simpleVis (pcl::PointCloud<pcl::PointXYZ>::ConstPtr cloud)
    {
      // --------------------------------------------
      // -----打开3维可视化窗口 加入点云----
      // --------------------------------------------
      boost::shared_ptr<pcl::visualization::PCLVisualizer> viewer (new pcl::visualization::PCLVisualizer ("3D Viewer"));
      viewer->setBackgroundColor (0, 0, 0);//背景颜色 黑se
      viewer->addPointCloud<pcl::PointXYZ> (cloud, "sample cloud");//添加点云
      viewer->setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 3, "sample cloud");//点云对象大小
      //viewer->addCoordinateSystem (1.0, "global");//添加坐标系
      viewer->initCameraParameters ();//初始化相机参数
      return (viewer);
    }
    
    /******************************************************************************
     对点云进行初始化,并对其中一个点云填充点云数据作为处理前的的原始点云,
     其中大部分点云数据是基于设定的圆球和平面模型计算
      而得到的坐标值作为局内点,有1/5的点云数据是被随机放置的组委局外点。
     ******************************************************************************/
    int
    main(int argc, char** argv)
    {
      // 初始化点云对象
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);  //存储源点云
      pcl::PointCloud<pcl::PointXYZ>::Ptr final1 (new pcl::PointCloud<pcl::PointXYZ>);  //存储提取的局内点
    
      // 填充点云数据
      cloud->width    = 500;                //填充点云数目
      cloud->height   = 1;                  //无序点云
      cloud->is_dense = false;
      cloud->points.resize (cloud->width * cloud->height);
      for (size_t i = 0; i < cloud->points.size (); ++i)
      {
        if (pcl::console::find_argument (argc, argv, "-s") >= 0 || pcl::console::find_argument (argc, argv, "-sf") >= 0)
        {
    //根据命令行参数用 x^2 + y^2 + Z^2 = 1 设置一部分点云数据,此时点云组成 1/4 个球体 作为内点
          cloud->points[i].x = 1024 * rand () / (RAND_MAX + 1.0);
          cloud->points[i].y = 1024 * rand () / (RAND_MAX + 1.0);
          if (i % 5 == 0)
            cloud->points[i].z = 1024 * rand () / (RAND_MAX + 1.0);   //此处对应的点为局外点
          else if(i % 2 == 0)//正值
            cloud->points[i].z =  sqrt( 1 - (cloud->points[i].x * cloud->points[i].x)
                                          - (cloud->points[i].y * cloud->points[i].y));
          else//负值
            cloud->points[i].z =  - sqrt( 1 - (cloud->points[i].x * cloud->points[i].x)
                                            - (cloud->points[i].y * cloud->points[i].y));
        }
        else
        { //用x+y+z=1设置一部分点云数据,此时 用点云组成的菱形平面作为内点
          cloud->points[i].x = 1024 * rand () / (RAND_MAX + 1.0);
          cloud->points[i].y = 1024 * rand () / (RAND_MAX + 1.0);
          if( i % 2 == 0)
            cloud->points[i].z = 1024 * rand () / (RAND_MAX + 1.0);   //对应的局外点
          else
            cloud->points[i].z = -1 * (cloud->points[i].x + cloud->points[i].y);
        }
      }
    
      std::vector<int> inliers;  //存储局内点集合的点的索引的向量
    
      //创建随机采样一致性对象
      pcl::SampleConsensusModelSphere<pcl::PointXYZ>::Ptr
        model_s(new pcl::SampleConsensusModelSphere<pcl::PointXYZ> (cloud));   //针对球模型的对象
      pcl::SampleConsensusModelPlane<pcl::PointXYZ>::Ptr
        model_p (new pcl::SampleConsensusModelPlane<pcl::PointXYZ> (cloud));   //针对平面模型的对象
      if(pcl::console::find_argument (argc, argv, "-f") >= 0)
      {  //根据命令行参数,来随机估算对应平面模型,并存储估计的局内点
        pcl::RandomSampleConsensus<pcl::PointXYZ> ransac (model_p);
        ransac.setDistanceThreshold (.01);    //与平面距离小于0.01 的点称为局内点考虑
        ransac.computeModel();                //执行随机参数估计
        ransac.getInliers(inliers);           //存储估计所得的局内点
      }
      else if (pcl::console::find_argument (argc, argv, "-sf") >= 0 )
      { 
       //根据命令行参数  来随机估算对应的圆球模型,存储估计的内点
        pcl::RandomSampleConsensus<pcl::PointXYZ> ransac (model_s);
        ransac.setDistanceThreshold (.01);
        ransac.computeModel();
        ransac.getInliers(inliers);
      }
    
      // 复制估算模型的所有的局内点到final中
      pcl::copyPointCloud<pcl::PointXYZ>(*cloud, inliers, *final1);
    
      // 创建可视化对象并加入原始点云或者所有的局内点
      boost::shared_ptr<pcl::visualization::PCLVisualizer> viewer;
      if (pcl::console::find_argument (argc, argv, "-f") >= 0 || pcl::console::find_argument (argc, argv, "-sf") >= 0)
        viewer = simpleVis(final1);
      else
        viewer = simpleVis(cloud);
      while (!viewer->wasStopped ())
      {
        viewer->spinOnce (100);
        boost::this_thread::sleep (boost::posix_time::microseconds (100000));
      }
      return 0;
    }

    2.分割平面 平面模型分割 基于随机采样一致性

     pcl::SACSegmentation pcl::SACMODEL_PLANE

    github

     

    #include <iostream>
    #include <pcl/ModelCoefficients.h>
    #include <pcl/io/pcd_io.h>
    #include <pcl/point_types.h>
    #include <pcl/sample_consensus/method_types.h>
    #include <pcl/sample_consensus/model_types.h>
    #include <pcl/segmentation/sac_segmentation.h>
    #include <pcl/visualization/pcl_visualizer.h>     // 可视化
    #include <pcl/filters/extract_indices.h>//按索引提取点云
    #include <boost/make_shared.hpp>
    int
     main (int argc, char** argv)
    {
     // 新建点云 
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
      // 随机生成点云
      cloud->width  = 15;
      cloud->height = 1;//无序点云
      cloud->points.resize (cloud->width * cloud->height);
      // 生成
      for (size_t i = 0; i < cloud->points.size (); ++i)
      {
        cloud->points[i].x = 1024 * rand () / (RAND_MAX + 1.0f);
        cloud->points[i].y = 1024 * rand () / (RAND_MAX + 1.0f);
        cloud->points[i].z = 1.0;//都在z=1平面上
      }
    
      // 设置一些外点 , 即重新设置几个点的z值,使其偏离z为1的平面
      cloud->points[0].z = 2.0;
      cloud->points[3].z = -2.0;
      cloud->points[6].z = 4.0;
      // 打印点云信息
      std::cerr << "Point cloud data: " << cloud->points.size () << " points" << std::endl;
      for (size_t i = 0; i < cloud->points.size (); ++i)
        std::cerr << "    " << cloud->points[i].x << " "
                            << cloud->points[i].y << " "
                            << cloud->points[i].z << std::endl;
    // 模型系数
      pcl::ModelCoefficients::Ptr coefficients (new pcl::ModelCoefficients);
      pcl::PointIndices::Ptr inliers (new pcl::PointIndices);//内点索引
     // pcl::PointIndices::Ptr outliers (new pcl::PointIndices);//外点索引
    // 创建一个点云分割对象
      pcl::SACSegmentation<pcl::PointXYZ> seg;
      // 是否优化模型系数
      seg.setOptimizeCoefficients (true);
      // 设置模型 和 采样方法
      seg.setModelType (pcl::SACMODEL_PLANE);// 平面模型
      seg.setMethodType (pcl::SAC_RANSAC);// 随机采样一致性算法
      seg.setDistanceThreshold (0.01);//是否在平面上的阈值
    
      seg.setInputCloud (cloud);//输入点云
      seg.segment (*inliers, *coefficients);//分割 得到平面系数 已经在平面上的点的 索引
     // seg.setNegative(true);//设置提取内点而非外点
      //seg.segment(*inliers, *coefficients);//分割 得到平面系数 已经在平面上的点的 索引
    
      if (inliers->indices.size () == 0)
      {
        PCL_ERROR ("Could not estimate a planar model for the given dataset.");
        return (-1);
      }
    // 打印平面系数
      std::cerr << "Model coefficients: " << coefficients->values[0] << " " 
                                          << coefficients->values[1] << " "
                                          << coefficients->values[2] << " " 
                                          << coefficients->values[3] << std::endl;
    //打印平面上的点
      std::cerr << "Model inliers: " << inliers->indices.size () << std::endl;
      for (size_t i = 0; i < inliers->indices.size (); ++i)
        std::cerr << inliers->indices[i] << "    " << cloud->points[inliers->indices[i]].x << " "
                                                   << cloud->points[inliers->indices[i]].y << " "
                                                   << cloud->points[inliers->indices[i]].z << std::endl;
    
    
    // 3D点云显示 源点云 绿色
      pcl::visualization::PCLVisualizer viewer ("3D Viewer");
      viewer.setBackgroundColor (255, 255, 255);//背景颜色 白色
      //pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> color_handler(cloud, 1.0, 1.0, 0.0);
      //viewer.addPointCloud (cloud, color_handler, "raw point");//添加点云
      //viewer.setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 1, "raw point");
      //viewer.addCoordinateSystem (1.0);
      viewer.initCameraParameters ();
    
    //按照索引提取点云  内点
      pcl::ExtractIndices<pcl::PointXYZ> extract_indices;//索引提取器
      extract_indices.setIndices (boost::make_shared<const pcl::PointIndices> (*inliers));//设置索引
      extract_indices.setInputCloud (cloud);//设置输入点云
      pcl::PointCloud<pcl::PointXYZ>::Ptr output (new pcl::PointCloud<pcl::PointXYZ>);
      extract_indices.filter (*output);//提取对于索引的点云 内点
      std::cerr << "output point size : " << output->points.size () << std::endl;
    
    //平面上的点云 红色
      pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> output_handler(output, 255, 0, 0);
      viewer.addPointCloud (output, output_handler, "plan point");//添加点云
      viewer.setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 3, "plan point");
    
    
    // 外点 绿色
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_other(new pcl::PointCloud<pcl::PointXYZ>);
      // *cloud_other = *cloud - *output;
      // 移去平面局内点,提取剩余点云
      extract_indices.setNegative (true);
      extract_indices.filter (*cloud_other);
      std::cerr << "other point size : " << cloud_other->points.size () << std::endl;
    
      pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> cloud_other_handler(cloud_other, 0, 255, 0);
      viewer.addPointCloud (cloud_other, cloud_other_handler, "other point");//添加点云
      viewer.setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 2, "other point");
    
    
        while (!viewer.wasStopped()){
            viewer.spinOnce(100);
            boost::this_thread::sleep(boost::posix_time::microseconds(100000));
        }
    
      return (0);
    }

     

     

     

    3.圆柱体分割依据法线信息分割 平面上按圆柱体模型分割得到圆柱体点云

    pcl::SACSegmentationFromNormals

    圆柱体分割 依据法线信息分割
    先分割平面 得到平面上的点云
    在平面上的点云中 分割圆柱体点云
    实现圆柱体模型的分割:
    采用随机采样一致性估计从带有噪声的点云中提取一个圆柱体模型。

    github

     

    #include <pcl/ModelCoefficients.h>//模型系数
    #include <pcl/io/pcd_io.h>
    #include <pcl/point_types.h>
    #include <pcl/filters/extract_indices.h>//按索引提取点云
    #include <pcl/filters/passthrough.h>// 直通滤波器
    #include <pcl/features/normal_3d.h>// 法线特征
    #include <pcl/sample_consensus/method_types.h>
    #include <pcl/sample_consensus/model_types.h>
    #include <pcl/segmentation/sac_segmentation.h>//随机采用分割
    #include <pcl/visualization/pcl_visualizer.h> // 可视化
    
    typedef pcl::PointXYZ PointT;
    int main (int argc, char** argv)
    {
      // 所需要的对象 All the objects needed
      pcl::PCDReader reader;//PCD文件读取对象
      pcl::PassThrough<PointT> pass;//直通滤波对象
      pcl::NormalEstimation<PointT, pcl::Normal> ne;//法线估计对象
      pcl::SACSegmentationFromNormals<PointT, pcl::Normal> seg;//依据法线 分割对象
      pcl::PCDWriter writer;//PCD文件写对象
      pcl::ExtractIndices<PointT> extract;//点 提取对象
      pcl::ExtractIndices<pcl::Normal> extract_normals;    ///点法线特征 提取对象
      pcl::search::KdTree<PointT>::Ptr tree (new pcl::search::KdTree<PointT> ());
    
      // 数据对象 Datasets
      pcl::PointCloud<PointT>::Ptr cloud (new pcl::PointCloud<PointT>);
      pcl::PointCloud<PointT>::Ptr cloud_filtered (new pcl::PointCloud<PointT>);
      pcl::PointCloud<pcl::Normal>::Ptr cloud_normals (new pcl::PointCloud<pcl::Normal>);//法线特征
      pcl::PointCloud<PointT>::Ptr cloud_filtered2 (new pcl::PointCloud<PointT>);
      pcl::PointCloud<pcl::Normal>::Ptr cloud_normals2 (new pcl::PointCloud<pcl::Normal>);//法线特征
      pcl::ModelCoefficients::Ptr coefficients_plane (new pcl::ModelCoefficients), coefficients_cylinder (new pcl::ModelCoefficients);//模型系数
      pcl::PointIndices::Ptr inliers_plane (new pcl::PointIndices), inliers_cylinder (new pcl::PointIndices);//内点索引
    
      // 读取桌面场景点云 Read in the cloud data
      reader.read ("../../surface/table_scene_mug_stereo_textured.pcd", *cloud);
      std::cerr << "PointCloud has: " << cloud->points.size () << " data points." << std::endl;
    
      // 直通滤波,将Z轴不在(0,1.5)范围的点过滤掉,将剩余的点存储到cloud_filtered对象中
      pass.setInputCloud (cloud);
      pass.setFilterFieldName ("z");// Z轴
      pass.setFilterLimits (0, 1.5);// 范围
      pass.filter (*cloud_filtered);
      std::cerr << "PointCloud after filtering has: " << cloud_filtered->points.size () << " data points." << std::endl;
    
      // 过滤后的点云进行法线估计,为后续进行基于法线的分割准备数据
      ne.setSearchMethod (tree);
      ne.setInputCloud (cloud_filtered);
      ne.setKSearch (50);
      ne.compute (*cloud_normals);//计算法线特征
    
      // Create the segmentation object for the planar model and set all the parameters
      // 同时优化模型系数
      seg.setOptimizeCoefficients (true);
      seg.setModelType (pcl::SACMODEL_NORMAL_PLANE);//平面模型
      seg.setNormalDistanceWeight (0.1);  // 法线信息权重
      seg.setMethodType (pcl::SAC_RANSAC);//随机采样一致性算法
      seg.setMaxIterations (100);         //最大迭代次数
      seg.setDistanceThreshold (0.03);    //设置内点到模型的距离允许最大值
      seg.setInputCloud (cloud_filtered); //输入点云
      seg.setInputNormals (cloud_normals);//输入法线特征
      //获取平面模型的系数和处在平面的内点
      seg.segment (*inliers_plane, *coefficients_plane);//分割 得到内点索引 和模型系数
      std::cerr << "Plane coefficients: " << *coefficients_plane << std::endl;
    
      // 从点云中抽取分割 处在平面上的点集 内点
      extract.setInputCloud (cloud_filtered);
      extract.setIndices (inliers_plane);
      extract.setNegative (false);
      // 存储分割得到的平面上的点到点云文件
      pcl::PointCloud<PointT>::Ptr cloud_plane (new pcl::PointCloud<PointT> ());
      extract.filter (*cloud_plane);//平面上的点云
      std::cerr << "PointCloud representing the planar component: " << cloud_plane->points.size () << " data points." << std::endl;
      writer.write ("table_scene_mug_stereo_textured_plane.pcd", *cloud_plane, false);
    
      // 提取 得到平面上的点云 (外点) 以及其法线特征
      extract.setNegative (true);//除去内点
      extract.filter (*cloud_filtered2);//得到外点
      extract_normals.setNegative (true);
      extract_normals.setInputCloud (cloud_normals);
      extract_normals.setIndices (inliers_plane);
      extract_normals.filter (*cloud_normals2);//提取外点对应的法线特征
    
      // 在平面上的点云 分割 圆柱体 
      seg.setOptimizeCoefficients (true);   //设置对估计模型优化
      seg.setModelType (pcl::SACMODEL_CYLINDER);//设置分割模型为圆柱形
      seg.setMethodType (pcl::SAC_RANSAC);      //参数估计方法 随机采样一致性算法
      seg.setNormalDistanceWeight (0.1);        //设置表面法线权重系数
      seg.setMaxIterations (10000);             //设置迭代的最大次数10000
      seg.setDistanceThreshold (0.05);          //设置内点到模型的距离允许最大值
      seg.setRadiusLimits (0, 0.1);             //设置估计出的圆柱模型的半径的范围
      seg.setInputCloud (cloud_filtered2);      //输入点云
      seg.setInputNormals (cloud_normals2);     //输入点云对应的法线特征
    
      // 获取符合圆柱体模型的内点 和 对应的系数
      seg.segment (*inliers_cylinder, *coefficients_cylinder);
      std::cerr << "Cylinder coefficients: " << *coefficients_cylinder << std::endl;
    
      // 写文件到
      extract.setInputCloud (cloud_filtered2);
      extract.setIndices (inliers_cylinder);
      extract.setNegative (false);//得到圆柱体点云
      pcl::PointCloud<PointT>::Ptr cloud_cylinder (new pcl::PointCloud<PointT> ());
      extract.filter (*cloud_cylinder);
      if (cloud_cylinder->points.empty ()) 
        std::cerr << "Can't find the cylindrical component." << std::endl;
      else
      {
          std::cerr << "PointCloud representing the cylindrical component: " << cloud_cylinder->points.size () << " data points." << std::endl;
          writer.write ("table_scene_mug_stereo_textured_cylinder.pcd", *cloud_cylinder, false);
      }
    
    // 3D点云显示 绿色
      pcl::visualization::PCLVisualizer viewer ("3D Viewer");
      viewer.setBackgroundColor (255, 255, 255);//背景颜色 白色
      //viewer.addCoordinateSystem (1.0);
      viewer.initCameraParameters ();
    //平面上的点云 红色
      pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> cloud_plane_handler(cloud_plane, 255, 0, 0);
      viewer.addPointCloud (cloud_plane, cloud_plane_handler, "plan point");//添加点云
      viewer.setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 2, "plan point");
    //  圆柱体模型的内点 绿色
      pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> cloud_cylinder_handler(cloud_cylinder, 0, 255, 0);
      viewer.addPointCloud (cloud_cylinder, cloud_cylinder_handler, "cylinder point");//添加点云
      viewer.setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 3, "cylinder point");
    
        while (!viewer.wasStopped()){
            viewer.spinOnce(100);
            boost::this_thread::sleep(boost::posix_time::microseconds(100000));
        }
    
      return (0);
    }
    

     

     

     

     

    4 .欧氏距离分割 平面模型分割平面 平面上按 聚类得到 多个点云团

     

    具体的实现方法大致是(原理是将一个点云团聚合成一类):
        1. 找到空间中某点p10,用kdTree找到离他最近的n个点,判断这n个点到p10的距离。
    	将距离小于阈值r的点p12,p13,p14....放在类Q里
        2. 在 Q\p10 里找到一点p12,重复1
        3. 在 Q\p10,p12 找到一点,重复1,找到p22,p23,p24....全部放进Q里
        4. 当 Q 再也不能有新点加入了,则完成搜索了
    
    因为点云总是连成片的,很少有什么东西会浮在空中来区分。
    但是如果结合此算法可以应用很多东东。
    
       1. 半径滤波(统计学滤波)删除离群点 体素格下采样等
       2. 采样一致找到桌面(平面)或者除去滤波
       3. 提取除去平面内点的 外点 (桌上的物体就自然成了一个个的浮空点云团)
       4. 欧式聚类 提取出我们想要识别的东西

    github

     

    #include <pcl/ModelCoefficients.h>//模型系数
    #include <pcl/point_types.h>//点云基本类型
    #include <pcl/io/pcd_io.h>//io
    #include <pcl/filters/extract_indices.h>//根据索引提取点云
    #include <pcl/filters/voxel_grid.h>//体素格下采样
    #include <pcl/features/normal_3d.h>//点云法线特征
    #include <pcl/kdtree/kdtree.h>//kd树搜索算法
    #include <pcl/sample_consensus/method_types.h>//采样方法
    #include <pcl/sample_consensus/model_types.h>//采样模型
    #include <pcl/segmentation/sac_segmentation.h>//随机采用分割
    #include <pcl/segmentation/extract_clusters.h>//欧式聚类分割
    #include <pcl/visualization/pcl_visualizer.h> // 可视化
    
    /******************************************************************************
     打开点云数据,并对点云进行滤波重采样预处理,然后采用平面分割模型对点云进行分割处理
     提取出点云中所有在平面上的点集,并将其存盘
    ******************************************************************************/
    int 
    main (int argc, char** argv)
    {
      // 读取桌面场景点云
      pcl::PCDReader reader;
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>), cloud_f (new pcl::PointCloud<pcl::PointXYZ>);
      reader.read ("../../Filtering/table_scene_lms400.pcd", *cloud);
      std::cout << "PointCloud before filtering has: " << cloud->points.size () << " data points." << std::endl; //*
    // 之前可进行 统计学滤波去除外点
      // //体素格滤波下采样 1cm×1cm×1cm
      pcl::VoxelGrid<pcl::PointXYZ> vg;//体素格滤波下采样
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_filtered (new pcl::PointCloud<pcl::PointXYZ>);
      vg.setInputCloud (cloud);
      vg.setLeafSize (0.01f, 0.01f, 0.01f);
      vg.filter (*cloud_filtered);
      std::cout << 	"PointCloud after filtering has: " << 
    	       	cloud_filtered->points.size ()     << 
    		" data points." << std::endl; //*
       //创建平面模型分割的对象并设置参数
      pcl::SACSegmentation<pcl::PointXYZ> seg;
      pcl::PointIndices::Ptr inliers (new pcl::PointIndices);
      pcl::ModelCoefficients::Ptr coefficients (new pcl::ModelCoefficients);//系数
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_plane (new pcl::PointCloud<pcl::PointXYZ> ());
      pcl::PCDWriter writer;
      seg.setOptimizeCoefficients (true);
      seg.setModelType (pcl::SACMODEL_PLANE);    //分割模型 平面模型
      seg.setMethodType (pcl::SAC_RANSAC);       //随机采样一致性 参数估计方法
      seg.setMaxIterations (100);                //最大的迭代的次数
      seg.setDistanceThreshold (0.02);           //设置符合模型的内点 阀值
    
      int i=0, nr_points = (int) cloud_filtered->points.size ();//下采样前点云数量
    
      while (cloud_filtered->points.size () > 0.3 * nr_points)
    // 模型分割 直到 剩余点云数量在30%以上 确保模型点云较好
      {
        // Segment the largest planar component from the remaining cloud
        seg.setInputCloud (cloud_filtered);
        seg.segment (*inliers, *coefficients);//分割
        if (inliers->indices.size () == 0)
        {
          std::cout << "Could not estimate a planar model for the given dataset." << std::endl;
          break;
        }
    
        pcl::ExtractIndices<pcl::PointXYZ> extract;//按索引提取点云
        extract.setInputCloud (cloud_filtered);
        extract.setIndices (inliers);//提取符合平面模型的内点
        extract.setNegative (false);
        // 平面模型内点
        extract.filter (*cloud_plane);
        std::cout << "PointCloud representing the planar component: " << 
    		  cloud_plane->points.size () << 
    		  " data points." << std::endl;
        // 移去平面局内点,提取剩余点云
        extract.setNegative (true);
        extract.filter (*cloud_f);
        *cloud_filtered = *cloud_f;//剩余点云
      }
    
      // 桌子平面上 的点云团 使用 欧式聚类的算法 kd树搜索 对点云聚类分割
      pcl::search::KdTree<pcl::PointXYZ>::Ptr tree (new pcl::search::KdTree<pcl::PointXYZ>);
      tree->setInputCloud (cloud_filtered);// 桌子平面上其他的点云
      std::vector<pcl::PointIndices> cluster_indices;// 点云团索引
      pcl::EuclideanClusterExtraction<pcl::PointXYZ> ec;// 欧式聚类对象
      ec.setClusterTolerance (0.02);                    // 设置近邻搜索的搜索半径为2cm
      ec.setMinClusterSize (100);                       // 设置一个聚类需要的最少的点数目为100
      ec.setMaxClusterSize (25000);                     // 设置一个聚类需要的最大点数目为25000
      ec.setSearchMethod (tree);                        // 设置点云的搜索机制
      ec.setInputCloud (cloud_filtered);
      ec.extract (cluster_indices);           //从点云中提取聚类,并将点云索引保存在cluster_indices中
    
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_cluster_all (new pcl::PointCloud<pcl::PointXYZ>);
      //迭代访问点云索引cluster_indices,直到分割处所有聚类
      int j = 0;
      for (std::vector<pcl::PointIndices>::const_iterator it = cluster_indices.begin (); it != cluster_indices.end (); ++it)
      {
        pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_cluster (new pcl::PointCloud<pcl::PointXYZ>);
        for (std::vector<int>::const_iterator pit = it->indices.begin (); pit != it->indices.end (); ++pit)
        	cloud_cluster->points.push_back (cloud_filtered->points[*pit]); //获取每一个点云团 的 点
    
        cloud_cluster->width = cloud_cluster->points.size ();
        cloud_cluster->height = 1;
        cloud_cluster->is_dense = true;
    
        std::cout << "PointCloud representing the Cluster: " << cloud_cluster->points.size () << " data points." << std::endl;
        std::stringstream ss;
        ss << "cloud_cluster_" << j << ".pcd";
        // writer.write<pcl::PointXYZ> (ss.str (), *cloud_cluster, false); //*
        j++;
    
      *cloud_cluster_all += *cloud_cluster;
      }
      pcl::io::savePCDFileASCII("cloud_cluster_all", *cloud_cluster_all);
    
    
    // 3D点云显示 绿色
      pcl::visualization::PCLVisualizer viewer ("3D Viewer");
      viewer.setBackgroundColor (255, 255, 255);//背景颜色 白色
      //viewer.addCoordinateSystem (1.0);
      viewer.initCameraParameters ();
    //平面上的点云 红色
      pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> cloud_plane_handler(cloud_plane, 255, 0, 0);
      viewer.addPointCloud (cloud_plane, cloud_plane_handler, "plan point");//添加点云
      viewer.setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 2, "plan point");
    
    //  桌上的物体就自然成了一个个的浮空点云团 绿色
      pcl::visualization::PointCloudColorHandlerCustom<pcl::PointXYZ> cloud_cluster_handler(cloud_cluster_all, 0, 255, 0);
      viewer.addPointCloud (cloud_cluster_all, cloud_cluster_handler, "cloud_cluster point");//添加点云
      viewer.setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 3, "cloud_cluster point");
    
        while (!viewer.wasStopped()){
            viewer.spinOnce(100);
            boost::this_thread::sleep(boost::posix_time::microseconds(100000));
        }
      return (0);
    }
    

     

     

     

    5 .基于法线差值和曲率差值的区域聚类分割算法

    pcl::RegionGrowing

    区域生成的分割法
    区 域生长的基本 思想是: 将具有相似性的像素集合起来构成区域。
    首先对每个需要分割的区域找出一个种子像素作为生长的起点,
    然后将种子像素周围邻域中与种子有相同或相似性质的像素 
    (根据事先确定的生长或相似准则来确定)合并到种子像素所在的区域中。
    而新的像素继续作为种子向四周生长,
    直到再没有满足条件的像素可以包括进来,一个区 域就生长而成了。
    
    区域生长算法直观感觉上和欧几里德算法相差不大,
    都是从一个点出发,最终占领整个被分割区域,
    欧几里德算法是通过距离远近,
    对于普通点云的区域生长,其可由法线、曲率估计算法获得其法线和曲率值。
    通过法线和曲率来判断某点是否属于该类。

    算法的主要思想是:

    	首先依据点的曲率值对点进行排序,之所以排序是因为,
    	区域生长算法是从曲率最小的点开始生长的,这个点就是初始种子点,
    	初始种子点所在的区域即为最平滑的区域,
    	从最平滑的区域开始生长可减少分割片段的总数,提高效率,
    	设置一空的种子点序列和空的聚类区域,选好初始种子后,
    	将其加入到种子点序列中,并搜索邻域点,
    	对每一个邻域点,比较邻域点的法线与当前种子点的法线之间的夹角,
    	小于平滑阀值的将当前点加入到当前区域,
    	然后检测每一个邻域点的曲率值,小于曲率阀值的加入到种子点序列中,
    	删除当前的种子点,循环执行以上步骤,直到种子序列为空.
    

    其算法可以总结为:

        0. 计算 法线normal 和 曲率curvatures,依据曲率升序排序;
        1. 选择曲率最低的为初始种子点,种子周围的临近点和种子点云相比较;
        2. 法线的方向是否足够相近(法线夹角足够 r p y),法线夹角阈值;
        3. 曲率是否足够小( 表面处在同一个弯曲程度 ),区域差值阈值;
        4. 如果满足2,3则该点可用做种子点;
        5. 如果只满足2,则归类而不做种;
        从某个种子出发,其“子种子”不再出现,则一类聚集完成
        类的规模既不能太大也不能太小.
    
    
      显然,上述算法是针对小曲率变化面设计的。
    尤其适合对连续阶梯平面进行分割:比如SLAM算法所获得的建筑走廊。

    github

     

    #include <iostream>
    #include <vector>
    #include <pcl/point_types.h>
    #include <pcl/io/pcd_io.h>//文件io
    #include <pcl/search/search.h>
    #include <pcl/search/kdtree.h>//搜索 kd树
    #include <pcl/features/normal_3d.h>//计算点云法线曲率特征
    #include <pcl/visualization/cloud_viewer.h>//可视化
    #include <pcl/filters/passthrough.h>//直通滤波器
    #include <pcl/segmentation/region_growing.h>//区域增长点云分割算法
    
    int
    main (int argc, char** argv)
    { 
      //点云的类型
      pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);
      //打开点云pdc文件 载入点云
      if ( pcl::io::loadPCDFile <pcl::PointXYZ> ("../region_growing_tutorial.pcd", *cloud) == -1)
      {
        std::cout << "Cloud reading failed." << std::endl;
        return (-1);
      }
     //设置搜索的方式或者说是结构 kd树 搜索
      pcl::search::Search<pcl::PointXYZ>::Ptr tree = boost::shared_ptr<pcl::search::Search<pcl::PointXYZ> > (new pcl::search::KdTree<pcl::PointXYZ>);
       //求法线 和 曲率 
      pcl::PointCloud <pcl::Normal>::Ptr normals (new pcl::PointCloud <pcl::Normal>);
      pcl::NormalEstimation<pcl::PointXYZ, pcl::Normal> normal_estimator;
      normal_estimator.setSearchMethod (tree);
      normal_estimator.setInputCloud (cloud);
      normal_estimator.setKSearch (50);//临近50个点
      normal_estimator.compute (*normals);
    
       //直通滤波在Z轴的0到1米之间 剔除 nan 和 噪点
      pcl::IndicesPtr indices (new std::vector <int>);
      pcl::PassThrough<pcl::PointXYZ> pass;
      pass.setInputCloud (cloud);
      pass.setFilterFieldName ("z");
      pass.setFilterLimits (0.0, 1.0);
      pass.filter (*indices);
      //区域增长聚类分割对象 <点,法线>
      pcl::RegionGrowing<pcl::PointXYZ, pcl::Normal> reg;
      reg.setMinClusterSize (50);     //最小的聚类的点数
      reg.setMaxClusterSize (1000000);//最大的聚类的点数
      reg.setSearchMethod (tree);     //搜索方式
      reg.setNumberOfNeighbours (30); //设置搜索的邻域点的个数
      reg.setInputCloud (cloud);      //输入点
      //reg.setIndices (indices);
      reg.setInputNormals (normals);  //输入的法线
      reg.setSmoothnessThreshold (3.0 / 180.0 * M_PI);//设置平滑度 法线差值阈值
      reg.setCurvatureThreshold (1.0);                //设置曲率的阀值
    
      std::vector <pcl::PointIndices> clusters;
      reg.extract (clusters);//提取点的索引
    
      std::cout << "点云团数量 Number of clusters is equal to " << clusters.size () << std::endl;//点云团 个数
      std::cout << "First cluster has " << clusters[0].indices.size () << " points." << endl;
      std::cout << "These are the indices of the points of the initial" <<
        std::endl << "cloud that belong to the first cluster:" << std::endl;
    /* 
     int counter = 0;
      while (counter < clusters[0].indices.size ())
      {
        std::cout << clusters[0].indices[counter] << ", ";//索引
        counter++;
        if (counter % 10 == 0)
          std::cout << std::endl;
      }
      std::cout << std::endl;
     */ 
      //可视化聚类的结果
      pcl::PointCloud <pcl::PointXYZRGB>::Ptr colored_cloud = reg.getColoredCloud ();
      pcl::visualization::CloudViewer viewer ("Cluster viewer");
      viewer.showCloud(colored_cloud);
      while (!viewer.wasStopped ())
      {
      }
    
      return (0);
    }

     

     

     

    6.基于颜色差值的区域聚类分割算法 pcl::RegionGrowingRGB

    基于颜色的区域生长分割法
    除了普通点云之外,还有一种特殊的点云,成为RGB点云
    。显而易见,这种点云除了结构信息之外,还存在颜色信息。
    将物体通过颜色分类,是人类在辨认果实的 过程中进化出的能力,
    颜色信息可以很好的将复杂场景中的特殊物体分割出来。
    比如Xbox Kinect就可以轻松的捕捉颜色点云。
    基于颜色的区域生长分割原理上和基于曲率,法线的分割方法是一致的。
    只不过比较目标换成了颜色,去掉了点云规模上 限的限制。
    可以认为,同一个颜色且挨得近,是一类的可能性很大,不需要上限来限制。
    所以这种方式比较适合用于室内场景分割。
    尤其是复杂室内场景,颜色分割 可以轻松的将连续的场景点云变成不同的物体。
    哪怕是高低不平的地面,设法用采样一致分割器抽掉平面,
    颜色分割算法对不同的颜色的物体实现分割。
    
    算法分为两步:
    
    (1)分割,当前种子点和领域点之间色差小于色差阀值的视为一个聚类
    
    (2)合并,聚类之间的色差小于色差阀值和并为一个聚类,
      且当前聚类中点的数量小于聚类点数量的与最近的聚类合并在一起
    

    github

     

    #include <iostream>
    #include <vector>
    #include <pcl/point_types.h>
    #include <pcl/io/pcd_io.h>
    #include <pcl/search/search.h>
    #include <pcl/search/kdtree.h>//搜索 kd树
    #include <pcl/visualization/cloud_viewer.h>//可视化
    #include <pcl/filters/passthrough.h>//直通滤波器
    #include <pcl/segmentation/region_growing_rgb.h>//基于颜色的区域增长点云分割算法
    
    int
    main (int argc, char** argv)
    {
      // 搜索算法
      pcl::search::Search <pcl::PointXYZRGB>::Ptr tree = boost::shared_ptr<pcl::search::Search<pcl::PointXYZRGB> > (new pcl::search::KdTree<pcl::PointXYZRGB>);
      //点云的类型
      pcl::PointCloud <pcl::PointXYZRGB>::Ptr cloud (new pcl::PointCloud <pcl::PointXYZRGB>);
      if ( pcl::io::loadPCDFile <pcl::PointXYZRGB> ("../region_growing_rgb_tutorial.pcd", *cloud) == -1 )
      {
        std::cout << "Cloud reading failed." << std::endl;
        return (-1);
      }
      //存储点云索引 的容器
      pcl::IndicesPtr indices (new std::vector <int>);
      //直通滤波在Z轴的0到1米之间 剔除 nan 和 噪点
      pcl::PassThrough<pcl::PointXYZRGB> pass;// 
      pass.setInputCloud (cloud);
      pass.setFilterFieldName ("z");
      pass.setFilterLimits (0.0, 1.0);
      pass.filter (*indices);//直通滤波后的的点云的索引 避免拷贝
      
     //基于颜色的区域生成的对象
      pcl::RegionGrowingRGB<pcl::PointXYZRGB> reg;
      reg.setInputCloud (cloud);
      reg.setIndices (indices);   //点云的索引
      reg.setSearchMethod (tree);
      reg.setDistanceThreshold (10);//距离的阀值
      reg.setPointColorThreshold (6);//点与点之间颜色容差
      reg.setRegionColorThreshold (5);//区域之间容差
      reg.setMinClusterSize (600);    //设置聚类的大小
      std::vector <pcl::PointIndices> clusters;
      reg.extract (clusters);//
    
      pcl::PointCloud <pcl::PointXYZRGB>::Ptr colored_cloud = reg.getColoredCloud ();
      pcl::visualization::CloudViewer viewer ("Cluster viewer");
      viewer.showCloud (colored_cloud);
      while (!viewer.wasStopped ())
      {
        boost::this_thread::sleep (boost::posix_time::microseconds (100));
      }
    
      return (0);
    }

     

     

     

     

    7.最小分割算法 (分割点云) 基于距离加权的最小图分割算法

    pcl::MinCutSegmentation

    最小分割算法  (分割点云)
    该算法是将一幅点云图像分割为两部分:
    前景点云(目标物体)和背景物体(剩余部分)
    The Min-Cut (minimum cut) algorithm最小割算法是图论中的一个概念,
    其作用是以某种方式,将两个点分开,当然这两个点中间可能是通过无数的点再相连的。
    
    如果要分开最左边的点和最右边的点,红绿两种割法都是可行的,
    但是红线跨过了三条线,绿线只跨过了两条。
    单从跨线数量上来论可以得出绿线这种切割方法更优 的结论。
    但假设线上有不同的权值,那么最优切割则和权值有关了。
    当你给出了点之间的 “图” ,以及连线的权值时,
    最小割算法就能按照要求把图分开。
    
    
    所以那么怎么来理解点云的图呢?
    显而易见,切割有两个非常重要的因素,
    第一个是获得点与点之间的拓扑关系,这种拓扑关系就是生成一张 “图”。
    第二个是给图中的连线赋予合适的权值。
    只要这两个要素合适,最小割算法就会正确的分割出想要的结果。
    点云是分开的点。只要把点云中所有的点连起来就可以了。
    
    连接算法如下:
    	   1. 找到每个点临近的n个点
    	   2. 将这n个点和父点连接
    	   3. 找到距离最小的两个块(A块中某点与B块中某点距离最小),并连接
    	   4. 重复3,直至只剩一个块
    	   
    经过上面的步骤现在已经有了点云的“图”,只要给图附上合适的权值,就满足了最小分割的前提条件。
    物体分割比如图像分割给人一个直观印象就是属于该物体的点,应该相互之间不会太远。
    也就是说,可以用点与点之间的欧式距离来构造权值。
    所有线的权值可映射为线长的函数。 
    
    cost = exp(-(dist/cet)^2)  距离越远 cost越小 越容易被分割
    
    我们知道这种分割是需要指定对象的,也就是我们指定聚类的中心点(center)以及聚类的半径(radius),
    当然我们指定了中心点和聚类的半径,那么就要被保护起来,保护的方法就是增加它的权值.
    
    dist2Center / radius
    
    dist2Center = sqrt((x-x_center)^2+(y-y_center)^2)

    github

     

    #include <pcl/io/pcd_io.h>
    #include <pcl/search/kdtree.h>
    #include <pcl/features/normal_3d.h>
    #include <pcl/segmentation/region_growing.h>
    #include <pcl/segmentation/min_cut_segmentation.h>
    #include <iostream>
    #include <pcl/segmentation/region_growing_rgb.h>
    
    int
    main(int argc, char** argv)
    {
        //申明点云的类型
        pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
        // 法线
        pcl::PointCloud<pcl::Normal>::Ptr normals(new pcl::PointCloud<pcl::Normal>);
    
        if (pcl::io::loadPCDFile<pcl::PointXYZ>("../min_Cut_Based.pcd", *cloud) != 0)
        {
            return -1;
        }
           // 申明一个Min-cut的聚类对象
        pcl::MinCutSegmentation<pcl::PointXYZ> clustering;
        clustering.setInputCloud(cloud);//设置输入
        //创建一个点云,列出所知道的所有属于对象的点 
        // (前景点)在这里设置聚类对象的中心点(想想是不是可以可以使用鼠标直接选择聚类中心点的方法呢?)
        pcl::PointCloud<pcl::PointXYZ>::Ptr foregroundPoints(new pcl::PointCloud<pcl::PointXYZ>());
        pcl::PointXYZ point;
        point.x = 100.0;
        point.y = 100.0;
        point.z = 100.0;
        foregroundPoints->points.push_back(point);
        clustering.setForegroundPoints(foregroundPoints);//设置聚类对象的前景点
           
        //设置sigma,它影响计算平滑度的成本。它的设置取决于点云之间的间隔(分辨率)
        clustering.setSigma(0.02);// cet cost = exp(-(dist/cet)^2) 
        // 设置聚类对象的半径.
        clustering.setRadius(0.01);// dist2Center / radius
    
             //设置需要搜索的临近点的个数,增加这个也就是要增加边界处图的个数
        clustering.setNumberOfNeighbours(20);
    
            //设置前景点的权重(也就是排除在聚类对象中的点,它是点云之间线的权重,)
        clustering.setSourceWeight(0.6);
    
        std::vector <pcl::PointIndices> clusters;
        clustering.extract(clusters);
    
        std::cout << "Maximum flow is " << clustering.getMaxFlow() << "." << std::endl;
    
        int currentClusterNum = 1;
        for (std::vector<pcl::PointIndices>::const_iterator i = clusters.begin(); i != clusters.end(); ++i)
        {
            //设置聚类后点云的属性
            pcl::PointCloud<pcl::PointXYZ>::Ptr cluster(new pcl::PointCloud<pcl::PointXYZ>);
            for (std::vector<int>::const_iterator point = i->indices.begin(); point != i->indices.end(); point++)
                cluster->points.push_back(cloud->points[*point]);
            cluster->width = cluster->points.size();
            cluster->height = 1;
            cluster->is_dense = true;
    
               //保存聚类的结果
            if (cluster->points.size() <= 0)
                break;
            std::cout << "Cluster " << currentClusterNum << " has " << cluster->points.size() << " points." << std::endl;
            std::string fileName = "cluster" + boost::to_string(currentClusterNum) + ".pcd";
            pcl::io::savePCDFileASCII(fileName, *cluster);
    
            currentClusterNum++;
        }
    
    }

    8.基于不同领域半径估计的法线的差异类 欧氏聚类 分割 点云

    pcl::DifferenceOfNormalsEstimation

     

     

     

    基于不同领域半径估计的 法线的差异类分割点云
    步骤:
    	1. 估计大领域半径 r_l 下的 法线    
    	2. 估计small领域半径 r_s 下的 法线 
    	3. 法线的差异  det(n,r_l, r_s) = (n_l - n_s)/2
    	4. 条件滤波器 
    	5. 欧式聚类 法线的差异

    github

     

    #include <string>
    
    #include <pcl/point_types.h>
    #include <pcl/io/pcd_io.h>
    #include <pcl/search/organized.h>
    #include <pcl/search/kdtree.h>//搜索 kd树
    #include <pcl/features/normal_3d_omp.h>//计算点云法线曲率特征
    #include <pcl/filters/conditional_removal.h>//条件滤波器
    #include <pcl/segmentation/extract_clusters.h>//根据点云索引提取对应的点云
    #include <pcl/features/don.h>//基于不同领域半径估计的 法线的差异类
    #include <pcl/segmentation/supervoxel_clustering.h>
    using namespace pcl;
    using namespace std;
    
    int
    main (int argc, char *argv[])
    {
      //small领域半径 The smallest scale to use in the DoN filter.
      double scale1;
    
      //大领域半径 The largest scale to use in the DoN filter.
      double scale2;
    
      ///The minimum DoN magnitude to threshold by
      double threshold;
    
      // 欧式聚类提取 segment scene into clusters with given distance tolerance using euclidean clustering
      double segradius;
    
      if (argc < 6)
      {
        cerr << "usage: " << argv[0] << " inputfile smallscale largescale threshold segradius" << endl;
        exit (EXIT_FAILURE);
      }
    
      /// the file to read from.
      string infile = argv[1];
      /// small scale
      istringstream (argv[2]) >> scale1;
      /// large scale
      istringstream (argv[3]) >> scale2;
      istringstream (argv[4]) >> threshold;   // 法线的差异  threshold for DoN magnitude
      istringstream (argv[5]) >> segradius;   //  欧式聚类 threshold for radius segmentation
    
      // Load cloud in blob format
      pcl::PCLPointCloud2 blob;
      pcl::io::loadPCDFile (infile.c_str (), blob);
      pcl::PointCloud<PointXYZRGB>::Ptr cloud (new pcl::PointCloud<PointXYZRGB>);
      pcl::fromPCLPointCloud2 (blob, *cloud);
    
      // Create a search tree, use KDTreee for non-organized data.
      pcl::search::Search<PointXYZRGB>::Ptr tree;
      if (cloud->isOrganized ())
      {
        tree.reset (new pcl::search::OrganizedNeighbor<PointXYZRGB> ());
      }
      else
      {
        tree.reset (new pcl::search::KdTree<PointXYZRGB> (false));
      }
    
      // Set the input pointcloud for the search tree
      tree->setInputCloud (cloud);
    
      if (scale1 >= scale2)
      {
        cerr << "Error: Large scale must be > small scale!" << endl;
        exit (EXIT_FAILURE);
      }
    
      //   Compute normals using both small and large scales at each point
      pcl::NormalEstimationOMP<PointXYZRGB, PointNormal> ne;
      ne.setInputCloud (cloud);
      ne.setSearchMethod (tree);
    
      /**
       * NOTE: setting viewpoint is very important, so that we can ensure
       * normals are all pointed in the same direction!
       */
      ne.setViewPoint (std::numeric_limits<float>::max (), std::numeric_limits<float>::max (), std::numeric_limits<float>::max ());
      
    // 估计small领域半径 r_s 下的 法线 calculate normals with the small scale
      cout << "Calculating normals for scale..." << scale1 << endl;
      pcl::PointCloud<PointNormal>::Ptr normals_small_scale (new pcl::PointCloud<PointNormal>);
      ne.setRadiusSearch (scale1);
      ne.compute (*normals_small_scale);
    
      // 估计大领域半径 r_l 下的 法线  calculate normals with the large scale
      cout << "Calculating normals for scale..." << scale2 << endl;
      pcl::PointCloud<PointNormal>::Ptr normals_large_scale (new pcl::PointCloud<PointNormal>);
      ne.setRadiusSearch (scale2);
      ne.compute (*normals_large_scale);
    
      // Create output cloud for DoN results
      PointCloud<PointNormal>::Ptr doncloud (new pcl::PointCloud<PointNormal>);
      copyPointCloud<PointXYZRGB, PointNormal>(*cloud, *doncloud);
    
      cout << "Calculating DoN... " << endl;
      // Create DoN operator
      pcl::DifferenceOfNormalsEstimation<PointXYZRGB, PointNormal, PointNormal> don;
      don.setInputCloud (cloud);
      don.setNormalScaleLarge (normals_large_scale);
      don.setNormalScaleSmall (normals_small_scale);
    
      if (!don.initCompute ())
      {
        std::cerr << "Error: Could not initialize DoN feature operator" << std::endl;
        exit (EXIT_FAILURE);
      }
      // Compute DoN
      don.computeFeature (*doncloud);
    
      // Save DoN features
      pcl::PCDWriter writer;
      writer.write<pcl::PointNormal> ("don.pcd", *doncloud, false); 
    
      // Filter by magnitude
      cout << "Filtering out DoN mag <= " << threshold << "..." << endl;
      //创建条件定义对象  曲率
      pcl::ConditionOr<PointNormal>::Ptr range_cond (new pcl::ConditionOr<PointNormal> () );
      range_cond->addComparison (pcl::FieldComparison<PointNormal>::ConstPtr (// 曲率 大于 
                                   new pcl::FieldComparison<PointNormal> ("curvature", pcl::ComparisonOps::GT, threshold))
                                 );
      // Build the filter
      // pcl::ConditionalRemoval<PointNormal> condrem(*range_cond);
      pcl::ConditionalRemoval<PointNormal> condrem;//创建条件滤波器
      condrem.setCondition (range_cond);    //并用条件定义对象初始化      
      condrem.setInputCloud (doncloud);
      pcl::PointCloud<PointNormal>::Ptr doncloud_filtered (new pcl::PointCloud<PointNormal>);
      // Apply filter
      condrem.filter (*doncloud_filtered);
      doncloud = doncloud_filtered;
    
    
      // Save filtered output
      std::cout << "Filtered Pointcloud: " << doncloud->points.size () << " data points." << std::endl;
      writer.write<pcl::PointNormal> ("don_filtered.pcd", *doncloud, false); 
    
      // Filter by magnitude
      cout << "Clustering using EuclideanClusterExtraction with tolerance <= " << segradius << "..." << endl;
    
      pcl::search::KdTree<PointNormal>::Ptr segtree (new pcl::search::KdTree<PointNormal>);
      segtree->setInputCloud (doncloud);
    
      std::vector<pcl::PointIndices> cluster_indices;
      pcl::EuclideanClusterExtraction<PointNormal> ec;
    
      ec.setClusterTolerance (segradius);
      ec.setMinClusterSize (50);
      ec.setMaxClusterSize (100000);
      ec.setSearchMethod (segtree);
      ec.setInputCloud (doncloud);
      ec.extract (cluster_indices);
    
      int j = 0;
      for (std::vector<pcl::PointIndices>::const_iterator it = cluster_indices.begin (); it != cluster_indices.end (); ++it, j++)
      {
        pcl::PointCloud<PointNormal>::Ptr cloud_cluster_don (new pcl::PointCloud<PointNormal>);
        for (std::vector<int>::const_iterator pit = it->indices.begin (); pit != it->indices.end (); ++pit)
        {
          cloud_cluster_don->points.push_back (doncloud->points[*pit]);
        }
    
        cloud_cluster_don->width = int (cloud_cluster_don->points.size ());
        cloud_cluster_don->height = 1;
        cloud_cluster_don->is_dense = true;
    
        //Save cluster
        cout << "PointCloud representing the Cluster: " << cloud_cluster_don->points.size () << " data points." << std::endl;
        stringstream ss;
        ss << "don_cluster_" << j << ".pcd";
        writer.write<pcl::PointNormal> (ss.str (), *cloud_cluster_don, false);
      }
    }

    9.超体聚类是一种图像的分割方法 pcl::SupervoxelClustering

    超体聚类  
    超体聚类是一种图像的分割方法。
    
    超体(supervoxel)是一种集合,集合的元素是“体”。
    与体素滤波器中的体类似,其本质是一个个的小方块。
    与大部分的分割手段不同,超体聚 类的目的并不是分割出某种特定物体,超
    体是对点云实施过分割(over segmentation),将场景点云化成很多小块,并研究每个小块之间的关系。
    这种将更小单元合并的分割思路已经出现了有些年份了,在图像分割中,像 素聚类形成超像素,
    以超像素关系来理解图像已经广为研究。本质上这种方法是对局部的一种总结,
    纹理,材质,颜色类似的部分会被自动的分割成一块,有利于后 续识别工作。
    比如对人的识别,如果能将头发,面部,四肢,躯干分开,则能更好的对各种姿态,性别的人进行识别。
    
    点云和图像不一样,其不存在像素邻接关系。所以,超体聚类之前,
    必须以八叉树对点云进行划分,获得不同点团之间的邻接关系。
    与图像相似点云的邻接关系也有很多,如面邻接,线邻接,点邻接。
    
    超体聚类实际上是一种特殊的区域生长算法,和无限制的生长不同,
    超体聚类首先需要规律的布置区域生长“晶核”。晶核在空间中实际上是均匀分布的,
    并指定晶核距离(Rseed)。再指定粒子距离(Rvoxel)。
    再指定最小晶粒(MOV),过小的晶粒需要融入最近的大晶粒。

    github

     

     

     

    #include <pcl/console/parse.h>
    #include <pcl/point_cloud.h>
    #include <pcl/point_types.h>
    #include <pcl/io/pcd_io.h>
    #include <pcl/visualization/pcl_visualizer.h>
    #include <pcl/segmentation/supervoxel_clustering.h>
    
    //VTK include needed for drawing graph lines
    #include <vtkPolyLine.h>
    
    // 数据类型
    typedef pcl::PointXYZRGBA PointT;
    typedef pcl::PointCloud<PointT> PointCloudT;
    typedef pcl::PointNormal PointNT;
    typedef pcl::PointCloud<PointNT> PointNCloudT;
    typedef pcl::PointXYZL PointLT;
    typedef pcl::PointCloud<PointLT> PointLCloudT;
    
    //可视化
    void addSupervoxelConnectionsToViewer (PointT &supervoxel_center,
                                           PointCloudT &adjacent_supervoxel_centers,
                                           std::string supervoxel_name,
                                           boost::shared_ptr<pcl::visualization::PCLVisualizer> & viewer);
    
    
    int
    main (int argc, char ** argv)
    {
    //解析命令行
     // if (argc < 2)
     // {
        pcl::console::print_error ("Syntax is: %s <pcd-file> \n "
                                    "--NT Dsables the single cloud transform \n"
                                    "-v <voxel resolution>\n-s <seed resolution>\n"
                                    "-c <color weight> \n-z <spatial weight> \n"
                                    "-n <normal_weight>\n", argv[0]);
      //  return (1);
      //}
    
      //打开点云
      PointCloudT::Ptr cloud = boost::shared_ptr <PointCloudT> (new PointCloudT ());
      pcl::console::print_highlight ("Loading point cloud...\n");
      if (pcl::io::loadPCDFile<PointT> ("../milk_cartoon_all_small_clorox.pcd", *cloud))
      {
        pcl::console::print_error ("Error loading cloud file!\n");
        return (1);
      }
    
    
      bool disable_transform = pcl::console::find_switch (argc, argv, "--NT");
    
      float voxel_resolution = 0.008f;  //分辨率
      bool voxel_res_specified = pcl::console::find_switch (argc, argv, "-v");
      if (voxel_res_specified)
        pcl::console::parse (argc, argv, "-v", voxel_resolution);
    
      float seed_resolution = 0.1f;
      bool seed_res_specified = pcl::console::find_switch (argc, argv, "-s");
      if (seed_res_specified)
        pcl::console::parse (argc, argv, "-s", seed_resolution);
    
      float color_importance = 0.2f;
      if (pcl::console::find_switch (argc, argv, "-c"))
        pcl::console::parse (argc, argv, "-c", color_importance);
    
      float spatial_importance = 0.4f;
      if (pcl::console::find_switch (argc, argv, "-z"))
        pcl::console::parse (argc, argv, "-z", spatial_importance);
    
      float normal_importance = 1.0f;
      if (pcl::console::find_switch (argc, argv, "-n"))
        pcl::console::parse (argc, argv, "-n", normal_importance);
    
    //如何使用SupervoxelClustering函数
      pcl::SupervoxelClustering<PointT> super (voxel_resolution, seed_resolution);
      if (disable_transform)//如果设置的是参数--NT  就用默认的参数
      super.setUseSingleCameraTransform (false);
      super.setInputCloud (cloud);
      super.setColorImportance (color_importance); //0.2f
      super.setSpatialImportance (spatial_importance); //0.4f
      super.setNormalImportance (normal_importance); //1.0f
    
      std::map <uint32_t, pcl::Supervoxel<PointT>::Ptr > supervoxel_clusters;
    
      pcl::console::print_highlight ("Extracting supervoxels!\n");
      super.extract (supervoxel_clusters);
      pcl::console::print_info ("Found %d supervoxels\n", supervoxel_clusters.size ());
    
      boost::shared_ptr<pcl::visualization::PCLVisualizer> viewer (new pcl::visualization::PCLVisualizer ("3D Viewer"));
      viewer->setBackgroundColor (0, 0, 0);
    
      PointCloudT::Ptr voxel_centroid_cloud = super.getVoxelCentroidCloud ();//获得体素中心的点云
      viewer->addPointCloud (voxel_centroid_cloud, "voxel centroids");
      viewer->setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE,2.0, "voxel centroids");     //渲染点云
      viewer->setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_OPACITY,0.95, "voxel centroids");
    
      PointLCloudT::Ptr labeled_voxel_cloud = super.getLabeledVoxelCloud ();
      viewer->addPointCloud (labeled_voxel_cloud, "labeled voxels");
      viewer->setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_OPACITY,0.8, "labeled voxels");
    
      PointNCloudT::Ptr sv_normal_cloud = super.makeSupervoxelNormalCloud (supervoxel_clusters);
    
      //We have this disabled so graph is easy to see, uncomment to see supervoxel normals
      //viewer->addPointCloudNormals<PointNormal> (sv_normal_cloud,1,0.05f, "supervoxel_normals");
    
      pcl::console::print_highlight ("Getting supervoxel adjacency\n");
    
      std::multimap<uint32_t, uint32_t> supervoxel_adjacency;
      super.getSupervoxelAdjacency (supervoxel_adjacency);
      //To make a graph of the supervoxel adjacency, we need to iterate through the supervoxel adjacency multimap
      //为了使整个超体形成衣服图,我们需要遍历超体的每个临近的个体
      std::multimap<uint32_t,uint32_t>::iterator label_itr = supervoxel_adjacency.begin ();
      for ( ; label_itr != supervoxel_adjacency.end (); )
      {
        //First get the label
        uint32_t supervoxel_label = label_itr->first;
        //Now get the supervoxel corresponding to the label
        pcl::Supervoxel<PointT>::Ptr supervoxel = supervoxel_clusters.at (supervoxel_label);
    
        //Now we need to iterate through the adjacent supervoxels and make a point cloud of them
        PointCloudT adjacent_supervoxel_centers;
        std::multimap<uint32_t,uint32_t>::iterator adjacent_itr = supervoxel_adjacency.equal_range (supervoxel_label).first;
        for ( ; adjacent_itr!=supervoxel_adjacency.equal_range (supervoxel_label).second; ++adjacent_itr)
        {
          pcl::Supervoxel<PointT>::Ptr neighbor_supervoxel = supervoxel_clusters.at (adjacent_itr->second);
          adjacent_supervoxel_centers.push_back (neighbor_supervoxel->centroid_);
        }
        //Now we make a name for this polygon
        std::stringstream ss;
        ss << "supervoxel_" << supervoxel_label;
        //This function is shown below, but is beyond the scope of this tutorial - basically it just generates a "star" polygon mesh from the points given
    //从给定的点云中生成一个星型的多边形,
        addSupervoxelConnectionsToViewer (supervoxel->centroid_, adjacent_supervoxel_centers, ss.str (), viewer);
        //Move iterator forward to next label
        label_itr = supervoxel_adjacency.upper_bound (supervoxel_label);
      }
    
      while (!viewer->wasStopped ())
      {
        viewer->spinOnce (100);
      }
      return (0);
    }
    
    //VTK可视化构成的聚类图
    void
    addSupervoxelConnectionsToViewer (PointT &supervoxel_center,
                                      PointCloudT &adjacent_supervoxel_centers,
                                      std::string supervoxel_name,
                                      boost::shared_ptr<pcl::visualization::PCLVisualizer> & viewer)
    {
      vtkSmartPointer<vtkPoints> points = vtkSmartPointer<vtkPoints>::New ();
      vtkSmartPointer<vtkCellArray> cells = vtkSmartPointer<vtkCellArray>::New ();
      vtkSmartPointer<vtkPolyLine> polyLine = vtkSmartPointer<vtkPolyLine>::New ();
    
      //Iterate through all adjacent points, and add a center point to adjacent point pair
      PointCloudT::iterator adjacent_itr = adjacent_supervoxel_centers.begin ();
      for ( ; adjacent_itr != adjacent_supervoxel_centers.end (); ++adjacent_itr)
      {
        points->InsertNextPoint (supervoxel_center.data);
        points->InsertNextPoint (adjacent_itr->data);
      }
      // Create a polydata to store everything in
      vtkSmartPointer<vtkPolyData> polyData = vtkSmartPointer<vtkPolyData>::New ();
      // Add the points to the dataset
      polyData->SetPoints (points);
      polyLine->GetPointIds  ()->SetNumberOfIds(points->GetNumberOfPoints ());
      for(unsigned int i = 0; i < points->GetNumberOfPoints (); i++)
        polyLine->GetPointIds ()->SetId (i,i);
      cells->InsertNextCell (polyLine);
      // Add the lines to the dataset
      polyData->SetLines (cells);
      viewer->addModelFromPolyData (polyData,supervoxel_name);
    }

    10.使用渐进式形态学滤波器 识别地面

    pcl::ProgressiveMorphologicalFilter

     

    github

    #include <iostream>
    #include <pcl/io/pcd_io.h>
    #include <pcl/point_types.h>
    #include <pcl/filters/extract_indices.h>// 根据点云索引提取对应的点云
    #include <pcl/segmentation/progressive_morphological_filter.h>
    
    int
    main(int argc, char** argv)
    {
        pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
        pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_filtered(new pcl::PointCloud<pcl::PointXYZ>);
        pcl::PointIndicesPtr ground(new pcl::PointIndices);
    
        pcl::PCDReader reader;
        reader.read<pcl::PointXYZ>("../samp11-utm.pcd", *cloud);
    
        std::cerr << "Cloud before filtering: " << std::endl;
        std::cerr << *cloud << std::endl;
    
        // 创建形态学滤波器对象
        pcl::ProgressiveMorphologicalFilter<pcl::PointXYZ> pmf;
        pmf.setInputCloud(cloud);
        // 设置过滤点最大的窗口尺寸
        pmf.setMaxWindowSize(20);
        // 设置计算高度阈值的斜率值
        pmf.setSlope(1.0f);
        // 设置初始高度参数被认为是地面点
        pmf.setInitialDistance(0.5f);
        // 设置被认为是地面点的最大高度
        pmf.setMaxDistance(3.0f);
        pmf.extract(ground->indices);
    
        //根据点云索引提取对应的点云
        pcl::ExtractIndices<pcl::PointXYZ> extract;
        extract.setInputCloud(cloud);
        extract.setIndices(ground);
        extract.filter(*cloud_filtered);
    
        std::cerr << "Ground cloud after filtering: " << std::endl;
        std::cerr << *cloud_filtered << std::endl;
    
        pcl::PointCloud<pcl::PointXYZRGB>::Ptr cloud_filtered_RGB(new pcl::PointCloud<pcl::PointXYZRGB>);
        cloud_filtered_RGB->resize(cloud_filtered->size());
        cloud_filtered_RGB->is_dense = false;
    
        for (size_t i = 0 ; i < cloud_filtered->points.size() ; ++i)
        {
            cloud_filtered_RGB->points[i].x = cloud_filtered->points[i].x;
            cloud_filtered_RGB->points[i].y = cloud_filtered->points[i].y;
            cloud_filtered_RGB->points[i].z = cloud_filtered->points[i].z;
    
            cloud_filtered_RGB->points[i].r = 0;
            cloud_filtered_RGB->points[i].g = 255;
            cloud_filtered_RGB->points[i].b = 0;
        }
    
        pcl::io::savePCDFileBinary("cloud_groud.pcd", *cloud_filtered_RGB);
    
        // 提取非地面点
        extract.setNegative(true);
        extract.filter(*cloud_filtered);
    
        std::cerr << "Object cloud after filtering: " << std::endl;
        std::cerr << *cloud_filtered << std::endl;
    
        pcl::io::savePCDFileBinary("No_groud.pcd", *cloud_filtered);
    
        return (0);
    }

     

     

    展开全文
  •   渐进一致采样法 (PROSAC) 是对经典的 RANSAC 中采样的一种优化。相比经典的 RANSAC 方法均匀地从整个集合中采样,PROSAC 方法是从不断增大的最佳对应点集合中进行采样的。所以这种方法可以节省计算量,提高运行...

    方法简介

      渐进一致采样法1 (PROSAC) 是对经典的 RANSAC2 中采样的一种优化。相比经典的 RANSAC 方法均匀地从整个集合中采样,PROSAC 方法是从不断增大的最佳对应点集合中进行采样的。所以这种方法可以节省计算量,提高运行速度。

    详细内容

    1. 引入

      假设: 具有更高相似性的数据点更可能是类内点(根据相似性进行排序的半随机采样不会比完全随机采样的效果更差)

    1.1. 标记说明

      NN 个数据点的集合记作 UN\mathcal{U}_N,根据评价函数 qqUN\mathcal{U}_N 内数据点被降排序为:
    ui,ujUN:i&lt;jq(ui)q(uj)\textbf{u}_i,\textbf{u}_j\in{\mathcal{U}_N}:i&lt;j\Rightarrow{q(\textbf{u}_i)\geq q(\textbf{u}_j)}
      评价最好的 nn 个数据点集合记作 Un\mathcal{U}_n
      从数据集 Un\mathcal{U}_n 中的采样点集合记作 M\mathcal{M},其元素个数为 M=m|\mathcal{M}|=m
      采样点集合的评价函数被定义为其所有元素评价函数值中最小的评价函数值:
    q(M)=minuiMq(ui)q(\mathcal{M})=\mathop{\min}\limits_{\textbf{u}_i\in{\mathcal{M}}}q(\textbf{u}_i)

    2. 算法

      由于 PROSAC 不是从所有数据点中进行随机采样,而是需要先对数据点进行排序,然后在评价函数值最高的数据点子集中进行随机采样,这个子集被称为假设生成集,并且这个假设生成集的元素数量是不断增大的。那么现在就会面临两个问题:

    1. 假设生成集的大小如何确定?
    2. 采样过程的停止策略是什么?

    2.1 生长函数和采样

      生长函数是用来确定假设生成集的大小的。它既不能过分乐观地依赖评价函数的预排序作用,也不能太消极地对所有数据点都相同看待。用 P{ui}P\{\textbf{u}_i\} 表示 ui\textbf{u}_i正确点的概率,我们对这个概率和评价函数之间的联系做一个最小的假设,即单调性假设:
    i&lt;jq(ui)q(uj)P{ui}P{uj}i&lt;j\Rightarrow q(\textbf{u}_i)\geq q(\textbf{u}_j) \Rightarrow P\{\textbf{u}_i\}\geq P\{\textbf{u}_j\}
      用 {Mi}i=1TN\{\mathcal{M}_i\}_{i=1}^{T_N} 表示 TNT_N 次采样点集合的序列,且每次采样都是从 NN 个数据点中选取其中的 mm 个,即 MiUN\mathcal{M}_i\in \mathcal{U}_N。用 {M(i)}i=1TN\{\mathcal{M}_{(i)}\}_{i=1}^{T_N} 表示根据评价函数排序之后的序列,则有:
    i&lt;jq(M(i))q(M(j))i&lt;j\Rightarrow q(\mathcal{M}_{(i)})\geq q(\mathcal{M}_{(j)})
      用 TnT_n 表示 {Mi}i=1TN\{\mathcal{M}_i\}_{i=1}^{T_N} 中所有元素都来源于 Un\mathcal{U}_n 的采样点集合 Mi\mathcal{M}_i 的平均个数,则有:
    Tn=TN(nm)(Nm)=TNi=0m1niNiT_n=T_N\frac{\binom{n}{m}}{\binom{N}{m}}=T_N\prod_{i=0}^{m-1}\frac{n-i}{N-i} Tn+1Tn=i=0m1n+1iNii=0m1Nini=n+1n+1m\frac{T_{n+1}}{T_n}=\prod_{i=0}^{m-1}\frac{n+1-i}{N-i}\prod_{i=0}^{m-1}\frac{N-i}{n-i}=\frac{n+1}{n+1-m}
      最终它们之间的递归关系为:
    Tn+1=n+1n+1mTnT_{n+1}=\frac{n+1}{n+1-m}T_n
      平均来说有 TnT_n 个采样点集合只包含 Un\mathcal{U}_n 的数据点,有 Tn+1T_{n+1} 个采样点集合只包含 Un+1\mathcal{U}_{n+1} 的数据点。由于 Un+1=Un{un+1}\mathcal{U}_{n+1}=\mathcal{U}_n\cup \{\textbf{u}_{n+1}\},所以就有 Tn+1TnT_{n+1}-T_n 个采样点集合包括一个数据点 un+1\textbf{u}_{n+1}m1m-1 个来源于 Un\mathcal{U}_n 的数据点。所以让 nnmm 一直取值到 N1N-1,这样就可以随机且高效地得到采样点集合 M(i)M_{(i)}.
      由于 TnT_n 的值一般不是整数,我们令 Tm=1T&#x27;_m=1,并且有:
    Tn+1=Tn+Tn+1TnT&#x27;_{n+1}=T&#x27;_n+\lceil T_{n+1}-T_n\rceil
      其中 ceil 括号表示取大于或等于括号中值的最小整数。所以生长函数可以被定义为:
    g(t)=min{n:Tnt}g(t)=\min\{n:T&#x27;_n\geq t\}
      这样第 tt 个采样点集合 Mt\mathcal{M}_t 可以表示为:
    Mt={ug(t)Mt}\mathcal{M}_t=\{\textbf{u}_{g(t)}\cup \mathcal{M}&#x27;_t\}
      其中 MtUg(t)1\mathcal{M}&#x27;_t\subset \mathcal{U}_{g(t)-1} 是一个包含 m1m-1 个来源于 Ug(t)1\mathcal{U}_{g(t)-1} 的数据点的集合,这样参数 TNT_N就表示需要多少次采样,PROSAC 算法的效果会和 RANSAC 算法保持一致。

    2.2 停止策略

      如果集合 Un\mathcal{U}_{n^*} 中的类内点数 InI_{n^*} 满足下面的条件,PROSAC 算法就停止:

    • 非随机性——nn^* 个数据点中的类内点恰好也是任意一个错误模型的类内点的概率小于 Ψ\Psi (一般设为 5%5\%)
    • 极大性——存在一个解在 Un\mathcal{U}_{n^*} 中有比 InI_{n^*} 更多的类内点的情况,并且这种情况在 kk 次采样后还未被发现的概率小于 ηo\eta_o (一般设为 5%5\%)

      非随机性可以防止由类外点产生的模型也和算法一致。随机类内点集合的元素个数的分布是二项分布:
    PnR(i)=βim(1β)ni+m(nmim)P_n^R(i)=\beta^{i-m}(1-\beta)^{n-i+m}\binom{n-m}{i-m}
      其中 β\beta 是与一个错误模型相对应的点不在采样点集合中的概率,并且该采样点集合包含一个类外点。(上面的公式可以这样理解:错误模型是由 mm 个采样点确定的,得到与该模型相对应的点有 imi\geq m 个【ii 个点就是错误模型认为的类内点,也就是所谓的随机类内点集合】,那么不在采样点集合 M\mathcal{M} 中的点有 imi-m 个,数据集中的一个点是这样的点的概率为 β\beta,所以可以得到随机类内点集合(Un\subset \mathcal{U}_n)的元素个数为 ii 的概率就是 PnR(I).P_n^R(I).
      最少的类内点数 InminI_n^{\min} 可以通过下面的式子得到(也就是限制随机类内点集合元素数量较大的概率):
    Inmin=min{j:i=jnPnR(i)&lt;Ψ}I_n^{\min}=\min \{j:\sum_{i=j}^nP_n^R(i)&lt;\Psi\}
      在 Un\mathcal{U}_{n^*} 中发现一个非随机的结果必须要满足:
    InInminI_{n^*}\geq I_{n^*}^{\min}
      极大性定义了需要多少次采样才能保证解的置信度,这也是 RANSAC 算法中唯一的停止策略。从 Un\mathcal{U}_n 中采样得到的 mm 个点都来自于类内点的概率为:
    PIn=(Inm)(nm)=j=0m1InjnjεnmP_{I_n}=\frac{\binom{I_n}{m}}{\binom{n}{m}}=\prod_{j=0}^{m-1}\frac{I_n-j}{n-j}\approx \varepsilon_n^m
      其中 InI_nUn\mathcal{U}_n 中类内点的数量,εn=In/n\varepsilon_n=I_n/n 表示类内点数的比例。那么 kk 次采样也没有一次采样都是类内点的概率为(g(k)ng(k)\leq n):
    η=(1PIn)k\eta=(1-P_{I_n})^k
      所以在给定概率阈值 ηo\eta_o 的后,采样次数需要满足下面的条件:
    kn(ηo)log(ηo)/log(1PIn)k_{n^*}(\eta_o)\geq \log(\eta_o)/\log(1-P_{I_{n^*}})
      最终 nn^* 的大小是在满足 InInminI_{n^*}\geq I_{n^*}^{\min} 的条件下最小化 kn(ηo)k_{n^*}(\eta_o) 得到的。

      PROSAC算法
    PROSAC算法伪代码

    3. 实验

      作者在基于 SIFT 的图像匹配中使用了 PROSAC 算法,并和 RANSAC 进行了对比,详细的实验内容和参数参考文献[1],下面的图片完全是为了好看才放在这里的。
    运动分割PROSAC
      下面补充我自己做的实验内容(代码链接):

      参考链接:

    1. RANSAC算法原理与源码解析
    2. openCV中的findHomography函数分析以及RANSAC算法的详解
    3. 要点初见:OpenCV3中ORB特征提取算法的实现与分析

      这里说明一下,实验的内容是计算单映矩阵,并实现对图像中特征点的匹配,并将模板区域在场景图中标出(参考上述链接1)。实现的效果如下图所示:
    在这里插入图片描述
    代码注意事项:

    • 代码使用 OpenCV3,使用 OpenCV2 的朋友参考上面的链接,修改部分代码就可以运行
    • 代码中没有实现对 β\beta 的动态估计
    • 代码中对 kn(ηo)k_{n^*}(\eta_o)nn^* 的计算可能不能用于其他任务中
    • 代码中排序的程序可以根据自己的需求进行修改
    • PROSAC代码的关键部分是自己写的,所以一定有很多错误以及性能上的不足,希望大家指出

    4. 结论

      这种方法可以非常有效地节省运算量和时间。由于减少了一个相关性阈值参数,所以可以对多种情况的检测有比较好的鲁棒性。
      这里抱怨一下,这篇论文对于我来说实在是太难读懂了,一大堆从句让人抓狂。不过还是挺佩服这两个作者的,几乎所有的 RANSAC 相关的论文都是他们写的。

    参考文献


    1. O. Chum and J. Matas, “Matching with PROSAC – Progressive Sample Consensus,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2005. ↩︎

    2. M.A. Fischler and R.C. Bolles, “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography,” Comm. ACM, vol. 24, no. 6, pp. 381- 395,1981. ↩︎

    展开全文
  • 集成方法:渐进梯度回归树GBRT(迭代决策树)

    万次阅读 多人点赞 2017-03-08 11:29:52
    http://blog.csdn.net/pipisorry/article/details/60776803单决策树C4.5由于功能太简单,并且非常容易出现过拟合的现象,...在最近几年的paper上,如iccv这种重量级会议,iccv 09年的里面有不少文章都是与Boosting

    http://blog.csdn.net/pipisorry/article/details/60776803

    单决策树C4.5由于功能太简单,并且非常容易出现过拟合的现象,于是引申出了许多变种决策树,就是将单决策树进行模型组合,形成多决策树,比较典型的就是迭代决策树GBRT和随机森林RF。在最近几年的paper上,如iccv这种重量级会议,iccv 09年的里面有不少文章都是与Boosting和随机森林相关的。模型组合+决策树相关算法有两种比较基本的形式:随机森林RF与GBDT,其他比较新的模型组合+决策树算法都是来自这两种算法的延伸。首先说明一下,GBRT这个算法有很多名字,但都是同一个算法:GBRT (Gradient BoostRegression Tree) 渐进梯度回归树,GBDT (Gradient BoostDecision Tree) 渐进梯度决策树,MART (MultipleAdditive Regression Tree) 多决策回归树,Tree Net决策树网络。

    GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree),是一种迭代的决策树算法,该算法由多棵决策树组成,所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力(generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。GBRT是回归树,不是分类树(尽管GBDT调整后也可用于分类但不代表GBDT的树是分类树)。其核心就在于,每一棵树是从之前所有树的残差中来学习的。为了防止过拟合,和Adaboosting一样,也加入了boosting这一项。

    GBDT主要由三个概念组成:Regression Decistion Tree(即DT),Gradient Boosting(即GB),Shrinkage (算法的一个重要演进分枝,目前大部分源码都按该版本实现)。搞定这三个概念后就能明白GBDT是如何工作的,要继续理解它如何用于搜索排序则需要额外理解RankNet概念。

    Gradient Tree Boosting或Gradient Boosted Regression Trees(GBRT)是一个boosting的泛化表示,它使用了不同的loss函数。GBRT是精确、现成的过程,用于解决回归/分类问题。Gradient Tree Boosting模型则用于许多不同的领域:比如:网页搜索Ranking、ecology等。

    GBRT优缺点

    GBRT的优点是:
        天然就可处理不同类型的数据(=各种各样的features)
        预测能力强
        对空间外的异常点处理很健壮(通过健壮的loss函数)
    GBRT的缺点是:
        扩展性不好,因为boosting天然就是顺序执行的,很难并行化

    回归树是如何工作的?

    我们以对人的性别判别/年龄预测为例来说明,每个instance都是一个我们已知性别/年龄的人,而feature则包括这个人上网的时长、上网的时段、网购所花的金额等。
        分类树,我们知道C4.5分类树在每次分枝时,是穷举每一个feature的每一个阈值,找到使得按照feature<=阈值,和feature>阈值分成的两个分枝的熵最大的feature和阈值(熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1),按照该标准分枝得到两个新节点,用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点,或达到预设的终止条件,若最终叶子节点中的性别不唯一,则以多数人的性别作为该叶子节点的性别。
        回归树总体流程类似,不过在每个节点(不一定是叶子节点)都会得一个预测值,以年龄为例,该预测值等于属于这个节点的所有人年龄的平均值{Note: 分裂点最优值是分裂点所有x对应y值的均值c,因内部最小平方误差最小[统计学习方法 5.5CART算法]}。分枝时穷举每一个feature的每个阈值找最好的分割点,但衡量最好的标准不再是最大熵,而是最小化均方差--即(每个人的年龄-预测年龄)^2 的总和 / N,或者说是每个人的预测误差平方和 除以 N。这很好理解,被预测出错的人数越多,错的越离谱,均方差就越大,通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一(这太难了)或者达到预设的终止条件(如叶子个数上限),若最终叶子节点上人的年龄不唯一,则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

    [统计学习方法 5.5CART算法]

    算法原理

    不是每棵树独立训练

    Boosting,迭代,即通过迭代多棵树来共同决策。这怎么实现呢?难道是每棵树独立训练一遍,比如A这个人,第一棵树认为是10岁,第二棵树认为是0岁,第三棵树认为是20岁,我们就取平均值10岁做最终结论?--当然不是!且不说这是投票方法并不是GBDT,只要训练集不变,独立训练三次的三棵树必定完全相同,这样做完全没有意义。之前说过,GBDT是把所有树的结论累加起来做最终结论的,所以可以想到每棵树的结论并不是年龄本身,而是年龄的一个累加量。

    GBDT的核心就在于,每一棵树学的是之前所有树结论和的残差,这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁,但第一棵树的预测年龄是12岁,差了6岁,即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习,如果第二棵树真的能把A分到6岁的叶子节点,那累加两棵树的结论就是A的真实年龄;如果第二棵树的结论是5岁,则A仍然存在1岁的残差,第三棵树里A的年龄就变成1岁,继续学。这就是Gradient Boosting在GBDT中的意义。

    残差提升

    算法流程解释1


    0.给定一个初始值

    1.建立M棵决策树(迭代M次){Note: 每次迭代生成一棵决策树}

    2.对函数估计值F(x)进行Logistic变换(Note:只是归一化而已)

    3.对于K各分类进行下面的操作(其实这个for循环也可以理解为向量的操作,每个样本点xi都对应了K种可能的分类yi,所以yi,F(xi),p(xi)都是一个K维向量)

    4.求得残差减少的梯度方向

    5.根据每个样本点x,与其残差减少的梯度方向,得到一棵由J个叶子节点组成的决策树

    6.当决策树建立完成后,通过这个公式,可以得到每个叶子节点的增益(这个增益在预测时候用的)

           每个增益的组成其实也是一个K维向量,表示如果在决策树预测的过程中,如果某个样本点掉入了这个叶子节点,则其对应的K个分类的值是多少。比如GBDT得到了三棵决策树,一个样本点在预测的时候,也会掉入3个叶子节点上,其增益分别为(假设为3分类问题):

    (0.5, 0.8, 0.1), (0.2, 0.6, 0.3), (0.4, .0.3, 0.3),那么这样最终得到的分类为第二个,因为选择分类2的决策树是最多的。

    7.将当前得到的决策树与之前的那些决策树合并起来,作为一个新的模型(跟6中的例子差不多)

    算法流程解释2

    梯度提升

    不同于前面的残差提升算法,这里使用loss函数的梯度近似残差(对于平方loss其实就是残差,一般loss函数就是残差的近似)。解决残差计算困难问题。

    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    GBRT示例1(残差)

            年龄预测,简单起见训练集只有4个人,A,B,C,D,他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生;C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练,会得到如下图1所示结果:


            现在我们使用GBDT来做这件事,由于数据太少,我们限定叶子节点做多有两个,即每棵树只有一个分枝,并且限定只学两棵树。我们会得到如下图2所示结果: 


            在第一棵树分枝和图1一样,由于A,B年龄较为相近,C,D年龄较为相近,他们被分为两拨,每拨用平均年龄作为预测值。此时计算残差(残差的意思就是: A的预测值 + A的残差 = A的实际值),所以A的残差就是16-15=1(注意,A的预测值是指前面所有树累加的和,这里前面只有一棵树所以直接是15,如果还有树则需要都累加起来作为A的预测值)。进而得到A,B,C,D的残差分别为-1,1,-1,1。然后我们拿残差替代A,B,C,D的原值,到第二棵树去学习,如果我们的预测值和它们的残差相等,则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的,第二棵树只有两个值1和-1,直接分成两个节点。此时所有人的残差都是0,即每个人都得到了真实的预测值。换句话说,现在A,B,C,D的预测值都和真实年龄一致了。

    A: 14岁高一学生,购物较少,经常问学长问题;预测年龄A = 15 – 1 = 14

    B: 16岁高三学生;购物较少,经常被学弟问问题;预测年龄B = 15 + 1 = 16

    C: 24岁应届毕业生;购物较多,经常问师兄问题;预测年龄C = 25 – 1 = 24

    D: 26岁工作两年员工;购物较多,经常被师弟问问题;预测年龄D = 25 + 1 = 26 

    问题

     1)既然图1和图2 最终效果相同,为何还需要GBDT呢?
        答案是过拟合。过拟合是指为了让训练集精度更高,学到了很多”仅在训练集上成立的规律“,导致换一个数据集当前规律就不适用了。其实只要允许一棵树的叶子节点足够多,训练集总是能训练到100%准确率的(大不了最后一个叶子上只有一个instance)。在训练精度和实际精度(或测试精度)之间,后者才是我们想要真正得到的。
        我们发现图1为了达到100%精度使用了3个feature(上网时长、时段、网购金额),其中分枝“上网时长>1.1h” 很显然已经过拟合了,这个数据集上A,B也许恰好A每天上网1.09h, B上网1.05小时,但用上网时间是不是>1.1小时来判断所有人的年龄很显然是有悖常识的;
        相对来说图2的boosting虽然用了两棵树 ,但其实只用了2个feature就搞定了,后一个feature是问答比例,显然图2的依据更靠谱。(当然,这里是故意做的数据,所以才能靠谱得如此) Boosting的最大好处在于,每一步的残差计算其实变相地增大了分错instance的权重,而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。就像我们做互联网,总是先解决60%用户的需求凑合着,再解决35%用户的需求,最后才关注那5%人的需求,这样就能逐渐把产品做好,因为不同类型用户需求可能完全不同,需要分别独立分析。
    2)Gradient呢?不是“G”BDT么?
     到目前为止,我们的确没有用到求导的Gradient。在当前版本GBDT描述中,的确没有用到Gradient,该版本用残差作为全局最优的绝对方向(lz可能不知道具体步长吧?),并不需要Gradient求解。

    那么哪里体现了Gradient呢?其实回到第一棵树结束时想一想,无论此时的cost function是什么,是均方差还是均差,只要它以误差作为衡量标准,残差向量(-1, 1, -1, 1)都是它的全局最优方向,这就是Gradient。

    lz补充一句,均方差的梯度不就是残差吗,这就是梯度!(其它的loss函数就不一定了,但是残差向量总是全局最优的,梯度一般都是残差的近似)

     3)这是boosting?Adaboost?
    这是boosting,但不是Adaboost。GBDT不是Adaboost Decistion Tree。就像提到决策树大家会想起C4.5,提到boost多数人也会想到Adaboost。Adaboost是另一种boost方法,它按分类对错,分配不同的weight,计算cost function时使用这些weight,从而让“错分的样本权重越来越大,使它们更被重视”。Bootstrap也有类似思想,它在每一步迭代时不改变模型本身,也不计算残差,而是从N个instance训练集中按一定概率重新抽取N个instance出来(单个instance可以被重复sample),对着这N个新的instance再训练一轮。由于数据集变了迭代模型训练结果也不一样,而一个instance被前面分错的越厉害,它的概率就被设的越高,这样就能同样达到逐步关注被分错的instance,逐步完善的效果。Adaboost的方法被实践证明是一种很好的防止过拟合的方法,但至于为什么至今没从理论上被证明。GBDT也可以在使用残差的同时引入Bootstrap re-sampling,GBDT多数实现版本中也增加的这个选项,但是否一定使用则有不同看法。re-sampling一个缺点是它的随机性,即同样的数据集合训练两遍结果是不一样的,也就是模型不可稳定复现,这对评估是很大挑战,比如很难说一个模型变好是因为你选用了更好的feature,还是由于这次sample的随机因素。

    GBRT示例2(残差)

    选取回归树的分界点建立回归树

    使用残差继续训练新的回归树


    GBRT适用范围

            该版本的GBRT几乎可用于所有的回归问题(线性/非线性),相对logistic regression仅能用于线性回归,GBRT的适用面非常广。亦可用于二分类问题(设定阈值,大于阈值为正例,反之为负例)。

    搜索引擎排序应用RankNet

            搜索排序关注各个doc的顺序而不是绝对值,所以需要一个新的cost function,而RankNet基本就是在定义这个cost function,它可以兼容不同的算法(GBDT、神经网络...)。
            实际的搜索排序使用的是Lambda MART算法,必须指出的是由于这里要使用排序需要的cost function,LambdaMART迭代用的并不是残差。Lambda在这里充当替代残差的计算方法,它使用了一种类似Gradient*步长模拟残差的方法。这里的MART在求解方法上和之前说的残差略有不同,其区别描述见这里。
             搜索排序也需要训练集,但多数用人工标注实现,即对每个(query, doc)pair给定一个分值(如1, 2, 3, 4),分值越高越相关,越应该排到前面。RankNet就是基于此制定了一个学习误差衡量方法,即cost function。RankNet对任意两个文档A,B,通过它们的人工标注分差,用sigmoid函数估计两者顺序和逆序的概率P1。然后同理用机器学习到的分差计算概率P2(sigmoid的好处在于它允许机器学习得到的分值是任意实数值,只要它们的分差和标准分的分差一致,P2就趋近于P1)。这时利用P1和P2求的两者的交叉熵,该交叉熵就是cost function。
            有了cost function,可以求导求Gradient,Gradient即每个文档得分的一个下降方向组成的N维向量,N为文档个数(应该说是query-doc pair个数)。这里仅仅是把”求残差“的逻辑替换为”求梯度“。每个样本通过Shrinkage累加都会得到一个最终得分,直接按分数从大到小排序就可以了。

    [【机器学习】迭代决策树GBRT(渐进梯度回归树)]

    皮皮blog



    python sklearn实现

    分类

    sklearn.ensemble.GradientBoostingClassifier(loss='deviance', learning_rate=0.1, n_estimators=100, subsample=1.0, criterion='friedman_mse', min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_depth=3, min_impurity_split=1e-07, init=None, random_state=None, max_features=None, verbose=0, max_leaf_nodes=None, warm_start=False, presort='auto')

    超过2个分类时,需要在每次迭代时引入n_classes的回归树,因此,总的索引树为(n_classes * n_estimators)。对于分类数目很多的情况,强烈推荐你使用 RandomForestClassifier 来替代GradientBoostingClassifier

    回归

    sklearn.ensemble.GradientBoostingRegressor(loss='ls', learning_rate=0.1, n_estimators=100, subsample=1.0, criterion='friedman_mse', min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_depth=3, min_impurity_split=1e-07, init=None, random_state=None, max_features=None, alpha=0.9, verbose=0, max_leaf_nodes=None, warm_start=False, presort='auto')

    参数:

    n_estimators : int (default=100) 迭代次数,也就是弱学习器的个数

    The number of boosting stages to perform. Gradient boostingis fairly robust to over-fitting so a large number usuallyresults in better performance.

    The plot on the left shows the train and test error at each iteration.The train error at each iteration is stored in thetrain_score_ attributeof the gradient boosting model. The test error at each iterations can be obtainedvia the staged_predict method which returns agenerator that yields the predictions at each stage. Plots like these can be usedto determine the optimal number of trees (i.e. n_estimators) by early stopping.

    ../../_images/sphx_glr_plot_gradient_boosting_regression_001.png

    控制树的size

    回归树的基础学习器(base learners)的size,定义了可以被GB模型捕获的各种交互的level。通常,一棵树的深度为h,可以捕获h阶的影响因子(interactions)。控制各个回归树的size有两种方法。
    1 指定max_depth=h,那么将会长成深度为h的完整二元树。这样的树至多有2^h个叶子,以及2^h-1中间节点。
    2 另一种方法:你可以通过指定叶子节点的数目(max_leaf_nodes)来控制树的size。这种情况下,树将使用最优搜索(best-first search)的方式生成,并以最高不纯度(impurity)的方式展开。如果树的max_leaf_nodes=k,表示具有k-1个分割节点,可以建模最高(max_leaf_nodes-1)阶的interactions。

    我们发现,max_leaf_nodes=k 与 max_depth=k-1 进行比较,训练会更快,只会增大一点点的训练误差(training error)。参数max_leaf_nodes对应于gradient boosting中的变量J,与R提供的gbm包的参数interaction.depth相关,为:max_leaf_nodes == interaction.depth + 1。

    数学公式Mathematical formulation

    GBRT considers additive models of the following form:

    F(x) = \sum_{m=1}^{M} \gamma_m h_m(x)

    where h_m(x) are the basis functions which are usually called weak learners in the context of boosting. Gradient Tree Boosting uses decision trees of fixed size as weak learners. Decision trees have a number of abilities that make them valuable for boosting, namely the ability to handle data of mixed type and the ability to model complex functions.

    Similar to other boosting algorithms GBRT builds the additive model in a forward stage wise fashion: 前向分步算法

    F_m(x) = F_{m-1}(x) + \gamma_m h_m(x)

    At each stage the decision tree h_m(x) is chosen to minimize the loss function L given the current modelF_{m-1} and its fit F_{m-1}(x_i)

    F_m(x) = F_{m-1}(x) + \arg\min_{h} \sum_{i=1}^{n} L(y_i,F_{m-1}(x_i) - h(x))   

    Note: 应该是F_{m-1}(x_i) + h(x)吧,残差为yi - (F_{m-1}(x_i) + h(x))训练下一个回归树

    The initial model F_{0} is problem specific, for least-squares regression one usually chooses the mean of the target values.

    Note:

    The initial model can also be specified via the init argument. The passed object has to implement fit and predict.

    Gradient Boosting attempts to solve this minimization problem numerically via steepest descent: The steepest descent direction is the negative gradient of the loss function evaluated at the current model F_{m-1} which can be calculated for any differentiable loss function:

    F_m(x) = F_{m-1}(x) + \gamma_m \sum_{i=1}^{n} \nabla_F L(y_i,F_{m-1}(x_i))    Note: 这里使用的是残差的近似--梯度来计算残差的。

    Where the step length \gamma_m is chosen using line search:

    \gamma_m = \arg\min_{\gamma} \sum_{i=1}^{n} L(y_i, F_{m-1}(x_i)- \gamma \frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)})

    The algorithms for regression and classification only differ in the concrete loss function used.

    loss函数

    回归

    • 最小二乘法Least squares(’ls’):最自然的选择,因为它的计算很简单。初始模型通过target的平均值来给出。
    • 最小绝对偏差Least absolute deviation (’lad’):一个健壮的loss函数,用于回归。初始模型通过target的中值来给出。
    • Huber (‘huber’): Another robust loss function that combinesleast squares and least absolute deviation; use alpha tocontrol the sensitivity with regards to outliers (see [F2001] formore details).
    • Quantile (‘quantile’):A loss function for quantile regression.Use 0 < alpha < 1 to specify the quantile. This loss functioncan be used to create prediction intervals(see Prediction Intervals for Gradient Boosting Regression).

    分类

    • Binomial deviance ('deviance'): The negative binomiallog-likelihood loss function for binary classification (providesprobability estimates). The initial model is given by thelog odds-ratio.
    • Multinomial deviance ('deviance'): The negative multinomiallog-likelihood loss function for multi-class classification withn_classes mutually exclusive classes. It providesprobability estimates. The initial model is given by theprior probability of each class. At each iteration n_classesregression trees have to be constructed which makes GBRT ratherinefficient for data sets with a large number of classes.
    • Exponential loss ('exponential'): The same loss functionas AdaBoostClassifier. Less robust to mislabeledexamples than 'deviance'; can only be used for binaryclassification.

    正则化

    缩减Shrinkage

     Shrinkage(缩减)的思想认为,每次走一小步逐渐逼近结果的效果,要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树,它认为每棵树只学到了真理的一小部分,累加的时候只累加一小部分,通过多学几棵树弥补不足。用方程来看更清晰,即
    没用Shrinkage时:(yi表示第i棵树上y的预测值, y(1~i)表示前i棵树y的综合预测值)
    y(i+1) = 残差(y1~yi), 其中: 残差(y1~yi) =  y真实值 - y(1 ~ i)
    y(1 ~ i) = SUM(y1, ..., yi)

    Shrinkage不改变第一个方程,只把第二个方程改为:
    y(1 ~ i) = y(1 ~ i-1) + step * yi
    即Shrinkage仍然以残差作为学习目标,但对于残差学习出来的结果,只累加一小部分(step*残差)逐步逼近目标,step一般都比较小,如0.01~0.001(注意该step非gradient的step),导致各个树的残差是渐变的而不是陡变的。直觉上这也很好理解,不像直接用残差一步修复误差,而是只修复一点点,其实就是把大步切成了很多小步。本质上,Shrinkage为每棵树设置了一个weight,累加时要乘以这个weight,但和Gradient并没有关系。这个weight就是step。就像Adaboost一样,Shrinkage能减少过拟合发生也是经验证明的,目前还没有看到从理论的证明

    [f2001]提出了一种简单的正则化策略,它通过一个因子v将每个弱学习器的贡献进行归一化(为什么学习率v能将每个弱学习器的贡献进行归一化?)。

    F_m(x) = F_{m-1}(x) + \nu \gamma_m h_m(x)

    参数v也被称为学习率(learning rate),因为它可以对梯度下降的步长进行调整;它可以通过learning_rate参数进行设定。

    参数learning_rate会强烈影响到参数n_estimators(即弱学习器个数)。learning_rate的值越小,就需要越多的弱学习器数来维持一个恒定的训练误差(training error)常量。经验上,推荐小一点的learning_rate会对测试误差(test error)更好。[HTF2009]推荐将learning_rate设置为一个小的常数(e.g. learning_rate <= 0.1),并通过early stopping机制来选择n_estimators。我们可以在[R2007]中看到更多关于learning_rate与n_estimators的关系。

    子抽样Subsampling

    [F1999]提出了随机梯度boosting,它将bagging(boostrap averaging)与GradientBoost相结合。在每次迭代时,基础分类器(base classifer)都在训练数据的一个子抽样集中进行训练。子抽样以放回抽样。subsample的典型值为:0.5。

    下图展示了shrinkage的效果,并在模型的拟合优度(Goodness of Fit)上进行子抽样(subsampling)。我们可以很清楚看到:shrinkage的效果比no-shrinkage的要好。

    减小variance策略1:使用shrinkage的子抽样可以进一步提升模型准确率。而不带shinkage的子抽样效果差些。

    ../_images/sphx_glr_plot_gradient_boosting_regularization_0011.png

    减小variance策略2:对features进行子抽样(类比于RandomForestClassifier中的随机split)。子抽样features的数目可以通过max_features参数进行控制。注意:使用小的max_features值可以极大地降低运行时长。

    out-of-bag估计

    随机梯度boosting允许计算测试偏差(test deviance)的out-of-bag估计,通过计算没有落在bootstrap样本中的其它样本的偏差改进(i.e. out-of-bag示例)。该提升存在属性oob_improvement_中。oob_improvement_[i]表示在添加第i步到当前预测中时,OOB样本中的loss的提升。OOB估计可以被用于模型选择,例如:决定最优的迭代数。OOB估计通常很少用,我们推荐你使用交叉验证(cross-validation),除非当cross-validation十分耗时的时候。

    示例:[Gradient Boosting regularization; Gradient Boosting Out-of-Bag estimates; OOB Errors for Random Forests]

    内省Interpretation

    单颗决策树可以通过内省进行可视化树结构。然而,GradientBoost模型由成百的回归树组成,不能轻易地通过对各棵决策树进行内省来进行可视化。幸运的是,已经提出了许多技术来归纳和内省GradientBoost模型。

    feature重要程度

    通常,features对于target的结果预期的贡献不是均等的;在许多情况下,大多数features都是不相关的。当内省一个模型时,第一个问题通常是:在预测我们的target时,哪些features对结果预测来说是重要的。

    单棵决策树天生就可以通过选择合适的split节点进行特征选择(feature selection)。该信息可以用于计算每个feature的重要性;基本思想是:如果一个feature经常用在树的split节点上,那么它就越重要。这个重要性的概率可以延伸到决策树家族ensembles方法上,通过对每棵树的feature求简单平均即可。

    GradientBoosting模型的重要性分值,可以通过feature_importances_属性来访问:

    >>> from sklearn.datasets import make_hastie_10_2
    >>> from sklearn.ensemble import GradientBoostingClassifier
    
    >>> X, y = make_hastie_10_2(random_state=0)
    >>> clf = GradientBoostingClassifier(n_estimators=100, learning_rate=1.0,
    ...     max_depth=1, random_state=0).fit(X, y)
    >>> clf.feature_importances_  
    array([ 0.11,  0.1 ,  0.11,  ...

    示例:Gradient Boosting regression

    局部依赖

    局部依赖图(Partial dependence plots :PDP)展示了target结果与一些目标特征(target feature)之间的依赖;边缘化(marginalizing)所有其它特征(’complement’ features)。另外,我们可以内省这两者的局部依赖性。

    由于人的认知的有限,目标特征的size必须设置的小些(通常:1或2),目标特征可以在最重要的特征当中进行选择。

    下图展示了关于California居住情况的、4个one-way和一个two-way的局部依赖图示例:

    ../_images/sphx_glr_plot_partial_dependence_0011.png

    one-way的PDP图告诉我们,target结果与target特征之间的相互关系(e.g. 线性/非线性)。左上图展示了中等收入(median income)在房价中位数(median house price)上的分布;我们可以看到它们间存在线性关系。     带有两个target特征的PDP,展示了和两个特征的相关关系。例如:上图最后一张小图中,两个变量的PDP展示了房价中位数(median house price)与房龄(house age)和平均家庭成员数(avg. occupants)间的关系。我们可以看到两个特征间的关系:对于AveOccup>2的,房价与房龄(HouseAge)几乎完全独立。而AveOccup<2的,房价则强烈依赖年齡。

    partial_dependence模块

    提供了一个很方便的函数:plot_partial_dependence 来创建one-way以及two-way的局部依赖图。下例,我们展示了如何创建一个PDP:两个two-way的PDP,feature为0和1,以及一个在这两个feature之间的two-way的PDP:

    >>> from sklearn.datasets import make_hastie_10_2
    >>> from sklearn.ensemble import GradientBoostingClassifier
    >>> from sklearn.ensemble.partial_dependence import plot_partial_dependence
    
    >>> X, y = make_hastie_10_2(random_state=0)
    >>> clf = GradientBoostingClassifier(n_estimators=100, learning_rate=1.0, max_depth=1, random_state=0).fit(X, y)
    >>> features = [0, 1, (0, 1)]
    >>> fig, axs = plot_partial_dependence(clf, X, features) 

    对于多分类的模块,我们需要设置类的label,通过label参数来创建PDP:

    >>> from sklearn.datasets import load_iris
    >>> iris = load_iris()
    >>> mc_clf = GradientBoostingClassifier(n_estimators=10, max_depth=1).fit(iris.data, iris.target)
    >>> features = [3, 2, (3, 2)]
    >>> fig, axs = plot_partial_dependence(mc_clf, X, features, label=0) 

    如果你需要一个局部依赖函数的原始值,而非你使用partial_dependence函数绘制的图:

    >>> from sklearn.ensemble.partial_dependence import partial_dependence
    
    >>> pdp, axes = partial_dependence(clf, [0], X=X)
    >>> pdp  
    array([[ 2.46643157,  2.46643157, ...
    >>> axes  
    [array([-1.62497054, -1.59201391, ...

    该函数需要两个参数:

    • grid: 它控制着要评估的PDP的target特征的值
    • X: 它提供了一个很方便的模式来从训练数据集上自动创建grid。

    返回值axis:

    -如果给定了X,那么通过这个函数返回的axes给出了每个target特征的axis.

    对于在grid上的target特征的每个值,PDP函数需要边缘化树的不重要特征的预测。在决策树中,这个函数可以用来评估有效性,不需要训练集数据。对于每个grid点,会执行一棵加权树的遍历:如果一个split节点涉及到’target’特征,那么接下去的左、右分枝,每个分枝都会通过根据进入该分枝的训练样本的fraction进行加权。最终,通过访问所有叶子的平均加权得到局部依赖。对于树的ensemble来说,每棵树的结果都会被平均。

    注意点:

    • 带有loss=’deviance’的分类,它的target结果为logit(p)
    • 初始化模型后,target结果的预测越精确;PDP图不会包含在init模型中

    示例:Partial Dependence Plots

    from: http://blog.csdn.net/pipisorry/article/details/60776803

    ref: [Sklearn: Gradient Tree Boosting]*

    [sklearn中的gbt(gbdt/gbrt)]*

    [GBDT(MART) 迭代决策树入门教程 | 简介 ]*

    [统计学习方法 8.4提升树]

    [Ensemble methods]

    [Boosting Decision Tree入门教程 http://www.schonlau.net/publication/05stata_boosting.pdf]

    [LambdaMART用于搜索排序入门教程 http://research.microsoft.com/pubs/132652/MSR-TR-2010-82.pdf]


    展开全文
  • 渐进增强与优雅降级

    2013-12-27 00:54:22
    最后讲到了渐进增强,于是突然想到了渐进增强优雅降级这个问题,感觉有点嚼头。 优雅降级(graceful degradation):一开始就构建站点的完整功能,然后针对浏览器测试修复。 渐进增强(progressive ...

    前几天围观大猫的博文,谈到用户体验的问题,地址。最后讲到了渐进增强,于是突然想到了渐进增强和优雅降级这个问题,感觉有点嚼头。
    优雅降级(graceful degradation):一开始就构建站点的完整功能,然后针对浏览器测试和修复。

    渐进增强(progressive enhancement):一开始只构建站点的最少特性,然后不断针对各浏览器追加功能。

    优雅降级:

    使用优雅降级方案,Web站点在所有新式浏览器中都能正常工作,如果用户使用的是老式浏览器,则代码会检查以确认它们是否能正常工作。由于IE独特的盒模型布局问题,绝大多数Web设计师和开发者都通过专门的样式表或针对不同版本的IE的hack实践过优雅降级了;
    使用优雅降级技术时,你必须首先完整的实现了网站,其中包括所有的功能和效果。然后再为那些无法支持所有功能的浏览器增加候选方案,使之在旧式浏览器上以某种形式降级体验却不至于完全失效。

    渐进增强:

    从被所有浏览器支持的基本功能开始,逐步地添加那些只有新式浏览器才支持的功能。渐进增强是值得所有开发者采用的做法。渐进增强方案并不假定所有用户都支持javascript,而总是提供一种候补方法,确保用户可以访问(主要的)内容。
    使用渐进增强时,无需为了一个已成型的网站在旧式浏览器下正常工作而做逆向工程。首先,只需要为所有的设备和浏览器准备好清晰且语义化的HTML以及完善的内容,然后再以无侵入(unobtrusive)的方式向页面增加无害于基础浏览器的额外样式和功能。当浏览器升级时,它们会自动地呈现出来并发挥作用。

    想让网站在任何环境下看起来都保持一致是不可能的,不管为此付出多少努力,结局依旧会令你失望。与其试图让IE看起来堪比年轻它十岁的浏览器,不如努力改善网站的可访问性,或是进行更多的可用性测试,而不仅仅是让页面看起来“更靓一点”。
    某些CSS3特性在不支持它的浏览器中简直是“无法模拟实现”的,但若使用渐进增强,就无需为了能让你的网站适合所有人而放弃这些技术。仅仅因为部分人不愿或不能升级浏览器,却让使用新型浏览器的用户无法享受CSS3所提供的伟大技术,这是毫无道理可言的。

    我们应该先让网站能够正常工作于尽可能旧的浏览器上,然后不断为它在新型浏览器上实现更多的增强和改进。随着时间的推移,当越来越多的人开始升级浏览器而浏览器本身的支持度也不断提升时,就会有越来越多的人体验到这些增强和改进,它持续有效的使网站越来越好,却如需你刻意做什么。只需要一次实现,它就让网站的体验与时俱进。

    展开全文
  • 渐进式 Web 应用是利用现代浏览器的特性...本教程将用实例一个演示应用程序,一步一步向你展示关于渐进式 Web 应用程序你应该知道的一切。为了不从零开始,我们打算用我们最近做过的一个自拍应用程序,并逐步创建它。
  • 文章目录一、写在前面的话二、数据库的事务三、分布式环境的各种问题三、CAPBASE理论四、一致性协议(1)两阶段提交(2)三阶段提交(3)Paxos算法五、写在最后的话 一、写在前面的话 在分布式来临之前,主流是...
  • PLSQL循序渐进全面学习教程(全)

    千次阅读 2018-02-01 18:12:01
    日期格式日期型函数:   1 、默认格式为 DD-MON-YY.     2 、 SYSDATE 是一个求系统时间的函数    3 、 DUAL [ 'dju:el]  是一个伪表,有人称之为空表,但不确切。  SQL>  SELECT SYSDATE...
  • 如果说通过TravisCI实现博客的自动化部署,是持续集成这个概念在工作以外的一种延伸,那么今天这篇文章想要大家分享的,则是我自身寻求技术转型突破的一种挣扎。前段时间Paul同我聊到Web技术的发展趋势,Paul...
  • 循序渐进全球化 镜像识别

    千次阅读 2010-03-22 11:15:00
    循序渐进全球化镜像识别本页内容概述说明示例Win32 中的镜像镜像 .NET Framework网页中的镜像 概述说明对于从右向左 (RTL) 的语言,不但文本对齐文本阅读顺序沿着从右向左的方向,而且 UI元素布局也应
  • 循序渐进学习 Python logging (2) - 高级教程
  • 渐进增强(progressive enhancement):一开始只构建站点的最少特性,然后不断针对各浏览器追加功能。 优雅降级: 使用优雅降级方案,Web站点在所有新式浏览器中都能正常工作,如果用户使用的是老式浏览器,则...
  • 在前端设计的过程中,我们都必须涉及到的一个问题,那就是浏览器的兼容问题。这个对用户体验的关注度是非常高的,于是就在网络上...渐进增强(progressive enhancement):一开始只构建站点的最少特性,然后不断针对
  • 如果两个物体完全一致,卷积完全重合,重合度为1,这时可以认为它就是同一个物体。 以上描述的两个物体,在算法中一般 指的是 卷积核 被卷积图片,卷积结果就是其两者的重合度。 看下深度学习中的池化层...
  • 这个是在网上查到的有关于“优雅降级”渐进增强”的解释。 优雅降级(graceful degradation): 一开始就构建站点的完整功能,然后针对浏览器测试修复。 渐进增强(progressive enhancement):一开始只构建...
  • 基于片元的渐进式三维点云上采样

    千次阅读 2020-05-06 00:09:34
    然而,处理三维点云是一项挑战,因为与图像不同,三维点云的数据是无序、非结构化不规则的。此外,点云通常是客户级设备扫描得到的,往往会有稀疏、有噪声不完整的情况。因此,对于三维点云的上采样技术研究非常...
  • PL/Sql循序渐进全面学习教程

    千次阅读 2007-03-15 16:00:00
    PL/Sql循序渐进全面学习教程--Oracle(1)课程 一 PL/SQL 基本查询与排序 本课重点: 1、写SELECT语句进行数据库查询 2、进行数学运算 3、处理空值 4、使用别名ALIASES 5、连接列 6、在SQL PLUS中编辑缓冲
  • 神经网络结构搜索是谷歌的AutoML的一个具体分支。约翰斯霍普金斯大学刘晨曦博士Alan Yullie 教授,以及Google AI的李飞飞、李佳等多名研究者提出渐进式神经网络结构搜索技术,论文被ECCV 2018接收作为Oral。...
  • <br /> 简单的说,敏捷开发是一种以人为核心、迭代、循序渐进的开发方法。在敏捷开发中,软件项目的构建被切分成多个子项目,各个子项目的成果都经过测试,具备集成和可运行的特征。换言之,就是把一个大项目...
  • PL/Sql循序渐进全面学习教程--Oracle

    千次阅读 2005-06-27 16:24:00
     注意:可以嵌套、可以在SELECT, WHERE, ORDER BY中出现。  语法:function_name (column|expression, [arg1, arg2,...])  二、字符型函数  1、LOWER 转小写  2、UPPER  3、INITCAP 首字母大写  4、...
  •  注意:可以嵌套、可以在SELECT, WHERE, ORDER BY中出现。  语法:function_name (column|expression, [arg1, arg2,...])  二、字符型函数  1、LOWER 转小写  2、UPPER  3、INITCAP 首字母...
  •  四、ORACLE 日期格式日期型函数:    1、默认格式为DD-MON-YY.  2、SYSDATE是一个求系统时间的函数  3、DUAL['dju:el] 是一个伪表,有人称之为空表,但不确切。  SQL> SELECT SYSDATE  2 FROM SYS.DUAL; ...
  • DL:理解探究采用深度学习算法预测时导致每次运行结果不一致的问题 目录 理解探究采用深度学习算法预测时导致每次运行结果不一致的问题 《How to Get Reproducible Results with Keras》的解读与翻译 ...
  • 前言:CVPR2018会议论文集已经公示(CVPR2018全部论文集链接),本文对显著目标检测领域的6篇进行了整理,将这几篇论文的主体思想汇总起来,供大家一起学习。 一、论文列表: 1.《Flow Guided Recurrent Neural ...
  • 用Flow提升前端代码健壮

    千次阅读 2018-04-27 10:58:26
    它的学习曲线没有TypeScript来得高,虽然内容也很多,但半天学个大概,就可以渐进式地开始使用 Flow从头到尾只是个 检查工具 不是新的程序语言或超集语言,所以它可以与各种现有的JavaScript代码兼容,如果你哪...
  • 企业的绩效考核指标设置不合理,考核标准模糊,难以量化,难以操作,考核指标繁琐与单一(片面)、确实与溢出的现象并存,导致绩效考核难以执行,同时忽略了指标间的内在逻辑关系与内在的一致性,以及各指标对总体绩效...
  • 本文描述了日渐流行的微服务架构模式。微服务背后大的理念是将大型、复杂且历时长久的应用在架构上设计为内聚的服务,...你应该致力于将系统分解为服务,以解决下面所讨论的开发部署问题。一些服务可能确实会很微小,
  • 关于本文 本文将逐步引导您使用 ...除了 Ajax 技术最佳实践之外,您还将了解 Ajax 如何通过渐进增强原理改善用户体验。 本文假设您已经牢固掌握 HTML CSS,基本了解 JavaScript Ajax 编程技术。示例应用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,575
精华内容 7,030
关键字:

一致性和渐进有效性