凹凸型分割算法适用于颜色类似、棱角分明的物体场景分割。LCCP方法不依赖点云颜色，只使用空间信息和法线信息。

算法流程：

1、基于超体聚类的过分割；

2、在超体聚类的基础上再聚类。

算法思路：

1、基于CC和SC判断凹凸性，CC是利用相邻两片中心连线向量与法向量的夹角来判断两片是凹还是凸，SC判别阈值与两体素的夹角。

 若α1>α2，则为凹，反之，则为凸。

2、在标记完各个小区域凹凸关系后，则采用区域增长算法将小区域聚类成较大物体。

3、滤除多余噪点，即可获得点云分割结果。

 示例代码：

//超体聚类+LCCP
//#include "stdafx.h"#include <stdlib.h>  
#include <cmath>  
#include <limits.h>  
#include <boost/format.hpp>  
#include <fstream> #include <pcl/console/parse.h>  
#include <pcl/io/pcd_io.h>  
#include <pcl/visualization/pcl_visualizer.h>  
#include <pcl/visualization/point_cloud_color_handlers.h>  
#include <pcl/visualization/cloud_viewer.h>#include <pcl/filters/passthrough.h>  
#include <pcl/segmentation/supervoxel_clustering.h>  #include <pcl/segmentation/lccp_segmentation.h>  #define Random(x) (rand() % x)typedef pcl::PointXYZRGBA PointT;
typedef pcl::LCCPSegmentation<PointT>::SupervoxelAdjacencyList SuperVoxelAdjacencyList;int main(int argc, char ** argv)
{//输入点云  pcl::PointCloud<PointT>::Ptr input_cloud_ptr(new pcl::PointCloud<PointT>);pcl::PCLPointCloud2 input_pointcloud2;if (pcl::io::loadPCDFile("E:\\PercipioVision\\depth2pointcloud\\testdata\\test-Cloud1.pcd", input_pointcloud2)){PCL_ERROR("ERROR: Could not read input point cloud ");return (3);}pcl::fromPCLPointCloud2(input_pointcloud2, *input_cloud_ptr);PCL_INFO("Done making cloud\n");//粒子距离，体素大小，空间八叉树的分辨率，类kinect或xtion获取的数据，0.008左右合适float voxel_resolution = 2.0f;//晶核距离，种子的分辨率，一般可设置为体素分辨率的50倍以上float seed_resolution = 100.0f;//颜色容差，针对分割场景，如果分割场景中各个物体之间的颜色特征差异明显，可设置较大float color_importance = 0.1f;//设置较大且其他影响较小时，基本按照空间分辨率来决定体素分割float spatial_importance = 1.0f;//针对分割场景，如果分割场景中各个物体连通处的法线特征差异明显，可设置较大，//但在实际使用中，需要针对数据的结构适当考虑，发现估计的准确性等因素float normal_importance = 4.0f;bool use_single_cam_transform = false;bool use_supervoxel_refinement = false;unsigned int k_factor = 0;//voxel_resolution is the resolution (in meters) of voxels used、seed_resolution is the average size (in meters) of resulting supervoxels  pcl::SupervoxelClustering<PointT> super(voxel_resolution, seed_resolution);super.setUseSingleCameraTransform(use_single_cam_transform);super.setInputCloud(input_cloud_ptr);//Set the importance of color for supervoxels. super.setColorImportance(color_importance);//Set the importance of spatial distance for supervoxels.super.setSpatialImportance(spatial_importance);//Set the importance of scalar normal product for supervoxels. super.setNormalImportance(normal_importance);std::map<uint32_t, pcl::Supervoxel<PointT>::Ptr> supervoxel_clusters;PCL_INFO("Extracting supervoxels\n");super.extract(supervoxel_clusters);PCL_INFO("Getting supervoxel adjacency\n");std::multimap<uint32_t, uint32_t> supervoxel_adjacency;super.getSupervoxelAdjacency(supervoxel_adjacency);pcl::PointCloud<pcl::PointNormal>::Ptr sv_centroid_normal_cloud = pcl::SupervoxelClustering<PointT>::makeSupervoxelNormalCloud(supervoxel_clusters);//LCCP分割float concavity_tolerance_threshold = 20;float smoothness_threshold = 0.2;uint32_t min_segment_size = 0;bool use_extended_convexity = false;bool use_sanity_criterion = false;PCL_INFO("Starting Segmentation\n");pcl::LCCPSegmentation<PointT> lccp;//设置CC判断的依据lccp.setConcavityToleranceThreshold(concavity_tolerance_threshold);//设置是否使用阶梯检测，这个条件会检测两个超体素之间是否是一个step。//如果两个超体素之间的面到面距离>expected_distance + smoothness_threshold_*voxel_resolution_则这个两个超体素被判定为unsmooth并被标记为凹。lccp.setSmoothnessCheck(true, voxel_resolution, seed_resolution, smoothness_threshold);//设置CC判断中公共距离被判定为凸的个数lccp.setKFactor(k_factor);//输入超体分割后的点云lccp.setInputSupervoxels(supervoxel_clusters, supervoxel_adjacency);lccp.setMinSegmentSize(min_segment_size);lccp.segment();PCL_INFO("Interpolation voxel cloud -> input cloud and relabeling\n");pcl::PointCloud<pcl::PointXYZL>::Ptr sv_labeled_cloud = super.getLabeledCloud();pcl::PointCloud<pcl::PointXYZL>::Ptr lccp_labeled_cloud = sv_labeled_cloud->makeShared();lccp.relabelCloud(*lccp_labeled_cloud);SuperVoxelAdjacencyList sv_adjacency_list;lccp.getSVAdjacencyList(sv_adjacency_list);// 根据label值提取点云int j = 0;pcl::PointCloud<pcl::PointXYZL>::Ptr ColoredCloud2(new pcl::PointCloud<pcl::PointXYZL>);ColoredCloud2->height = 1;ColoredCloud2->width = lccp_labeled_cloud->size();ColoredCloud2->resize(lccp_labeled_cloud->size());for (int i = 0; i < lccp_labeled_cloud->size(); i++) {if (lccp_labeled_cloud->points[i].label == 3) {ColoredCloud2->points[j].x = lccp_labeled_cloud->points[i].x;ColoredCloud2->points[j].y = lccp_labeled_cloud->points[i].y;ColoredCloud2->points[j].z = lccp_labeled_cloud->points[i].z;ColoredCloud2->points[j].label = lccp_labeled_cloud->points[i].label;j++;}}pcl::io::savePCDFileASCII("E:\\PercipioVision\\depth2pointcloud\\testdata\\3.pcd", *ColoredCloud2);// Configure Visualizer//pcl::visualization::PCLVisualizer viewer = pcl::visualization::PCLVisualizer("3D Viewer", false);//viewer.addPointCloud(lccp_labeled_cloud, "Segmented point cloud");pcl::io::savePCDFileASCII("E:\\PercipioVision\\depth2pointcloud\\testdata\\分割后合并.pcd", *lccp_labeled_cloud);return 0;
}