-
2022-03-21 22:24:53
用于视觉特征无监督学习的深度聚类 《Deep Clustering for Unsupervised Learning of Visual Features》 论文地址:https://arxiv.org/pdf/1807.05520.pdf
相关博客:
【自然语言处理】【聚类】基于神经网络的聚类算法DEC
【自然语言处理】【聚类】基于对比学习的聚类算法SCCL
【自然语言处理】【聚类】DCSC:利用基于对比学习的半监督聚类算法进行意图挖掘
【自然语言处理】【聚类】DeepAligned:使用深度对齐聚类发现新意图
【自然语言处理】【聚类】CDAC+:通过深度自适应聚类发现新意图
【计算机视觉】【聚类】DeepCluster:用于视觉特征无监督学习的深度聚类算法
【计算机视觉】【聚类】SwAV:基于对比簇分配的无监督视觉特征学习
【计算机视觉】【聚类】CC:对比聚类
【计算机视觉】【聚类】SeLa:同时进行聚类和表示学习的自标注算法
【自然语言处理】【聚类】ECIC:通过迭代分类增强短文本聚类
【自然语言处理】【聚类】TELL:可解释神经聚类一、简介
预训练卷积神经网络已经成为许多计算机视觉的基础部件,其能够产生良好的通用特征来改善模型在有限训练集上的泛化能力。 ImageNet \text{ImageNet} ImageNet是一个大规模的全监督数据集,用于卷积神经网络的预训练。然而,一些研究表明在 ImageNet \text{ImageNet} ImageNet上的state-of-the-art模型被极大的低估,基本上没有什么问题未被解决。以今天的标准来看 ImageNet \text{ImageNet} ImageNet的规模相对较小,仅包含了一百万张特定领域的图片。一个天然的方向是构建一个更大且更多样的数据集,但是需要大量的人工标注。因此,需要一个能够在互联网规模数据集上进行无监督训练的方法。
无监督学习已经被广泛的研究,且聚类、降维或者密度估计等算法也经常被应用于计算机视觉。一些研究已经证明,可以将基于密度估计的方法或者降维方法应用在深度模型上,并获得良好的视觉通用特征。尽管聚类算法在图像分类任务上取得了初步的成功,但还没有人在卷积神经网络上进行大规模端到端训练。一个主要的问题是,聚类算法是为固定特征上的线性模型设计的,很难在聚类的同时学习这些特征。例如,使用 K-Means \text{K-Means} K-Means来学习卷积神经网络将会导致平凡解,即特征全为0。
本文提出了一种用于大规模、端到端训练卷积神经网络的新颖聚类算法。使用这个聚类框架能够获取更好的通用视觉特征。整个方法如图1所示,其会在图像聚类和使用卷积神经网络预测簇分配间交替进行来更新参数。简单起见,本文仅专注研究 K-Means \text{K-Means} K-Means,但其他聚类方法也可以使用。尽管方法简单,本文的方法在 ImageNet \text{ImageNet} ImageNet分类和迁移任务上都比先前的无监督方法更好。
最后,本文通过修改实验中的训练集和网络结构等协议来验证整个框架的鲁棒性。实验结果显示,本文的方法对网络结构是具有鲁棒性的。
二、监督训练
现代计算机视觉都是基于统计学习的方法,需要好的图像特征。因此,卷积神经网络是将原始图像映射成固定维度向量的流行选择。定义 f θ f_\theta fθ为卷积神经网络映射, θ \theta θ是模型参数集合。本文应用 f θ f_\theta fθ将图像映射成特征向量。给定一个大小为 N N N的图像训练集 X = { x 1 , x 2 , … , x N } X=\{x_1,x_2,\dots,x_N\} X={x1,x2,…,xN},期望寻找到最优参数 θ ∗ \theta^* θ∗,使 f θ ∗ f_{\theta^*} fθ∗能够产生良好的通用特征。
每个图片 x n x_n xn关联一个介于 { 0 , 1 } k \{0,1\}^k {0,1}k的标签 y n y_n yn。通常来说,会使用监督学习的方式来预测图片属于预定义 k k k个类别中的某一类别,从而获得最优参数 θ ∗ \theta^* θ∗。在特征映射函数 f θ ( x n ) f_\theta(x_n) fθ(xn)的基础上添加一个参数化分类器 g W g_W gW来预测正确标签。其中,分类器参数 W W W和映射函数参数 θ \theta θ通过下面的损失函数来优化
min θ , W 1 N ∑ n = 1 N l ( g W ( f θ ( x n ) ) , y n ) (1) \mathop{\text{min}}_{\theta,W}\frac{1}{N}\sum_{n=1}^N\mathcal{l}(g_W(f_\theta(x_n)),y_n) \tag{1} minθ,WN1n=1∑Nl(gW(fθ(xn)),yn)(1)
其中, l l l是多项式 logistic \text{logistic} logistic损失函数。三、通过聚类进行无监督学习
不进行任何学习,直接从高斯分布中采样 θ \theta θ, f θ f_\theta fθ并不能产生良好的特征。然而,这些随机特征在标准的迁移任务中高于平均水平。例如,在一个随机初始化 AlexNet \text{AlexNet} AlexNet后拼接多层感知机能够在 ImageNet \text{ImageNet} ImageNet上实现12%的准确率。随机卷积神经网络的良好表现与卷积结构密切相关,因为其对输入信号有很强的先验。本文的想法是利用弱监督信号来引导卷积神经网络的判别能力。因此,本方法对卷积神经网络的输出进行聚类,然后使用聚类的簇分配来优化等式(1)。
研究表明聚类算法的选择并不关键。因此,本文选择标准聚类算法 K-Means \text{K-Means} K-Means。本文使用 K-Means \text{K-Means} K-Means聚类卷积神经网络的输出特征 f θ ( x n ) f_\theta(x_n) fθ(xn)。更准确的说,通过求解下面的公式来联合学习簇中心矩阵 C ∈ R d × k C\in\mathbb{R}^{d\times k} C∈Rd×k,每个图片 n n n会被分配簇 y n y_n yn:
min C ∈ R d × k 1 N ∑ n = 1 N min y n ∈ { 0 , 1 } k ∥ f θ ( x n ) − C y n ∥ 2 2 such that y n ⊤ 1 k = 1 (2) \mathop{\text{min}}_{C\in\mathbb{R}^{d\times k}}\frac{1}{N}\sum_{n=1}^N\mathop{\text{min}}_{y_n\in\{0,1\}^k}\parallel f_\theta(x_n)-Cy_n\parallel_2^2\;\text{such that}\quad y_n^\top1_k=1\tag{2} minC∈Rd×kN1n=1∑Nminyn∈{0,1}k∥fθ(xn)−Cyn∥22such thatyn⊤1k=1(2)
求解上面的公式能够得到最优簇分配 ( y n ∗ ) n ≤ N (y_n^*)_{n\leq N} (yn∗)n≤N和簇中心矩阵 C ∗ C^* C∗。这个簇分配后续被用作伪标签,而簇中心矩阵并没有被使用。 总体来说, DeepCluster \text{DeepCluster} DeepCluster交替使用等式 ( 2 ) (2) (2)进行聚类来产生伪标签,并使用等式 ( 1 ) (1) (1)来预测伪标签,用于更新卷积神经网络的参数。但是,这种交替可能会导致平凡解。
四、避免平凡解
平凡解不仅出现在无监督神经网络学习中,而是对于任何联合学习判别分类器和标签的方法。即使只使用线性模型,判别聚类的方法也存在这个问题。常见的解决方案是,对每个簇中的最小样本数量进行限制和惩罚。但是,这种方法需要在整个数据集上计算,不适用于大规模数据集上的卷积神经网络。本小节会给出一个简单且可伸缩的变通方法。
1. 空簇
对于一个学习类别间决策边界的模型,一个最优的决策边界是将所有输入分配至单个簇中。导致这种问题的原因是,缺乏一个机制来防止空簇的出现。一种常见的技巧是在 K-Means \text{K-Means} K-Means阶段自动重新分配簇。具体来说,当一个簇为空时,随机选择一个非空簇,并将簇中心添加一个随机扰动作为空簇的新中心。然后,将属于非空簇的样本重新分配至两个簇。
2. 参数平凡化
在一个极端化的场景中,除一个簇外,所有簇都只有一个实例。此时,最小化等式 ( 1 ) (1) (1)将导致参数平凡化,即卷积神经网络会无视输入并产生相同的输出。这个问题在类别高度不平衡的监督图像分类中也会出现。解决这个问题的策略是基于类别的均匀分配进行图像采样。这相当于将等式 ( 1 ) (1) (1)中某个输入对损失函数的贡献权重设置为其分配簇尺寸大小的倒数。
更多相关内容 -
Velodyne Lidar点云聚类算法
2019-04-01 17:12:19输入Velodyne Lidar数据,对点云进行聚类,基于Qt图像界面开发,算法满足实时性,分割效果好,可用于16线,32线,64线激光雷达数据. -
基于机载LiDAR点云多层聚类的单木信息提取及其精度评价.pdf
2021-08-18 22:13:02基于机载LiDAR点云多层聚类的单木信息提取及其精度评价.pdf -
基于法向量密度聚类的LiDAR点云屋顶面提取.pdf
2021-08-19 21:48:57基于法向量密度聚类的LiDAR点云屋顶面提取.pdf -
基于模糊C均值聚类的机载LiDAR点云滤波.pdf
2021-08-20 00:00:30基于模糊C均值聚类的机载LiDAR点云滤波.pdf -
c均值聚类算法matlab代码-CrownSeg:通过以RGB,高光谱和LiDAR作为输入进行聚类的树冠图像分割
2021-05-23 14:52:24使用聚类技术从RGB,高光谱和LiDAR图像中分割树冠 数据集 培训输入(GeoTIFF格式) 37张RGB图像(320,320,3) 43张高光谱图像(80,80,420) 43张LiDAR图像(80,80) 43张LiDAR PointCloud 3D地图(20665,20665,20665... -
结合TIN约束与密度聚类的机载LiDAR道路点云提取.pdf
2021-08-19 00:02:58结合TIN约束与密度聚类的机载LiDAR道路点云提取.pdf -
Udacity传感器融合笔记(二)lidar 点云处理
2020-11-16 15:40:14本篇博客主要记录lidar点云的分割以及聚类。 1.Segmentation 点云分割 对于lidar反馈回来的数据,我们总是希望从中准确的找到那些是障碍物,那些是道路点。为此,udacity课程中使用了RANSAC算法来进行点云的分割,将...本篇博客主要记录lidar点云的分割以及聚类。
1.Segmentation 点云分割
对于lidar反馈回来的数据,我们总是希望从中准确的找到那些是障碍物,那些是道路点。为此,udacity课程中使用了RANSAC算法来进行点云的分割,将lidar点云分为障碍物点(外点)和道路点(内点)两类。
1.1 RANSAC
对于RANSAC算法(随即抽样一致算法),初次接触是在高博的视觉SLAM14讲中,该算法可以从一组包含“局外点”的数据中通过迭代的方式估计数学模型的参数,从而找到符合模型的“局内点”。这里不多做介绍,详细原理可以推荐一篇博客
RANSAC深度解析
在udacity的课程中,也对RANSAC的原理进行了简要介绍和仿真。RANSAC是一种检测数据中异常值的方法。 RANSAC运行最大迭代次数,并返回最合适的模型。 每次迭代都会随机选择数据的子样本,并通过它拟合模型,例如直线或平面。 然后,将具有最大数量的内部值或最低噪声的迭代用作最佳模型。一种类型的RANSAC选择适合的最小点子集。 对于一条线,这将是两个点,对于平面,则将是三个点。 然后,通过迭代遍历每个剩余点并计算其与模型的距离,来计算内部数。 距模型一定距离内的点计为内部值。 那么,具有最大内部数的迭代就是最佳模型。 这也是udacity课程中实现的版本。RANSAC的其他方法可以对模型点的某些百分比进行采样,例如占总点数的20%,然后对其拟合一条线。 然后计算该行的误差,误差最小的迭代就是最佳模型。 由于不需要考虑每次迭代的每个点,因此该方法可能具有一些优点。
1.2 RANSAC仿真
接下来是ransac的仿真部分代码,这里只记录平面点云的RANSAC分割main函数
int main () { // Create viewer 创建可视化窗口 pcl::visualization::PCLVisualizer::Ptr viewer = initScene(); // Create data 创建点云数据 pcl::PointCloud<pcl::PointXYZ>::Ptr cloud = CreateData3D(); // TODO: Change the max iteration and distance tolerance arguments for Ransac function 设定最大迭代次数和距离阈值 std::unordered_set<int> inliers = Ransac(cloud, 100, 0.5); pcl::PointCloud<pcl::PointXYZ>::Ptr cloudInliers(new pcl::PointCloud<pcl::PointXYZ>()); pcl::PointCloud<pcl::PointXYZ>::Ptr cloudOutliers(new pcl::PointCloud<pcl::PointXYZ>()); for(int index = 0; index < cloud->points.size(); index++) { //对点云进行分割 pcl::PointXYZ point = cloud->points[index]; if(inliers.count(index)) cloudInliers->points.push_back(point); else cloudOutliers->points.push_back(point); } // Render 2D point cloud with inliers and outliers,对分割后的点云进行渲染 内点绿色,外点红色 if(inliers.size()) { renderPointCloud(viewer,cloudInliers,"inliers",Color(0,1,0)); renderPointCloud(viewer,cloudOutliers,"outliers",Color(1,0,0)); } else { //其他背景黑色 renderPointCloud(viewer,cloud,"data"); } while (!viewer->wasStopped ()) { viewer->spinOnce (); } }
加载pcd函数
//加载pcd文件 pcl::PointCloud<pcl::PointXYZ>::Ptr CreateData3D() { ProcessPointClouds<pcl::PointXYZ> pointProcessor; //创建pointProcessor return pointProcessor.loadPcd("../../../sensors/data/pcd/simpleHighway.pcd"); //加载data中的pcd文件 }
创建可视化窗口并初始化
//创建窗口并初始化函数 pcl::visualization::PCLVisualizer::Ptr initScene() { pcl::visualization::PCLVisualizer::Ptr viewer(new pcl::visualization::PCLVisualizer ("2D Viewer"));//创建可视化窗口 viewer->setBackgroundColor (0, 0, 0); //背景颜色黑色 viewer->initCameraParameters(); //初始化窗口参数 viewer->setCameraPosition(0, 0, 15, 0, 1, 0);//窗口位置及视角 viewer->addCoordinateSystem (1.0);//创建坐标系 return viewer; }
RANSAC算法
std::unordered_set<int> Ransac(pcl::PointCloud<pcl::PointXYZ>::Ptr cloud, int maxIterations, float distanceTol) { std::unordered_set<int> inliersResult; //创建关联容器 用于储存内点 std::unordered_set是SLT中的一种容器,基于RB-Tree结构,有机会后面介绍 srand(time(NULL)); auto startTime = std::chrono::steady_clock::now(); // TODO: Fill in this function //算法步骤 // For max iterations // Randomly sample subset and fit line // Measure distance between every point and fitted line // If distance is smaller than threshold count it as inlier // Return indicies of inliers from fitted line with most inliers while(maxIterations--) { std::unordered_set<int> inliers; //内点容器 while(inliers.size()<3) inliers.insert(rand()%(cloud->points.size())); //随机选3个点组成平面插入进inlier中 float x1,x2,x3,y1,y2,y3,z1,z2,z3; auto itr = inliers.begin();//将inlier的开始地址赋给itr x1 = cloud->points[*itr].x; y1 = cloud->points[*itr].y; z1 = cloud->points[*itr].z; itr++; x2 = cloud->points[*itr].x; y2 = cloud->points[*itr].y; z2 = cloud->points[*itr].z; itr++; x3 = cloud->points[*itr].x; y3 = cloud->points[*itr].y; z3 = cloud->points[*itr].z; //三点平面公式计算 a b c d float a = (y2-y1)*(z3-z1)-(z2-z1)*(y3-y1); float b = (z2-z1)*(x3-x1)-(x2-x1)*(z3-z1); float c = (x2- x1)*(y3-y1)-(y2-y1)*(x3-x1); float d = -(a*x1+b*y1+c*z1); for(int index = 0;index < cloud->points.size(); index++) { if(inliers.count(index) > 0) continue; pcl::PointXYZ point = cloud->points[index]; float x3 = point.x; float y3 = point.y; float z3 = point.z; //计算点到平面距离公式 float d = fabs(a*x3+b*y3+c*z3+d)/sqrt(a*a+ b*b+c*c); if(d <= distanceTol) inliers.insert(index); //小于阈值,判定为内点 } if(inliers.size() > inliersResult.size()) { inliersResult = inliers; //返回最优结果 } } auto endTime = std::chrono::steady_clock::now(); auto elapsedTime = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime); std::cout << "Ransac took " << elapsedTime.count() << " milliseconds" << std::endl; return inliersResult; }
结果如图 红色为障碍物,绿色为道路点
在课程的工程中,直接调用了PCL库中的RANSAC功能进行点云的分割。其原理与仿真一致。
在lidar障碍物检测工程中的对应部分
std::pair<typename pcl::PointCloud<PointT>::Ptr, typename pcl::PointCloud<PointT>::Ptr> ProcessPointClouds<PointT>::SegmentPlane(typename pcl::PointCloud<PointT>::Ptr cloud, int maxIterations, float distanceThreshold) { // Time segmentation process auto startTime = std::chrono::steady_clock::now(); // TODO:: Fill in this function to find inliers for the cloud. //过滤之后的点云数据 //创建分割对象 -- 检测平面参数 pcl::SACSegmentation<PointT> seg; pcl::PointIndices::Ptr inliers {new pcl::PointIndices}; //存储内点的点索引集合对象inliers pcl::ModelCoefficients::Ptr coefficients{new pcl::ModelCoefficients}; seg.setOptimizeCoefficients(true); //设置对估计的模型系数需要进行优化 seg.setModelType(pcl::SACMODEL_PLANE); //设置模型类型,检测平面 seg.setMethodType(pcl::SAC_RANSAC); //设置方法(随机样本一致性) seg.setMaxIterations(maxIterations); //最大迭代次数 seg.setDistanceThreshold(distanceThreshold); //距离阈值 seg.setInputCloud(cloud); seg.segment(*inliers,*coefficients); //分割操作 if(inliers->indices.size() == 0) { std::cout<<"could not estimate a planar model for the given dataset."<<std::endl; } auto endTime = std::chrono::steady_clock::now(); auto elapsedTime = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime); std::cout << "plane segmentation took " << elapsedTime.count() << " milliseconds" << std::endl; std::pair<typename pcl::PointCloud<PointT>::Ptr, typename pcl::PointCloud<PointT>::Ptr> segResult = SeparateClouds(inliers,cloud); return segResult; }
这个函数在environment.cpp文件中被调用
std::pair<pcl::PointCloud<pcl::PointXYZI>::Ptr,pcl::PointCloud<pcl::PointXYZI>::Ptr> segmentCloud = pointProcessorI.SegmentPlane(inputCloud,25,0.3)
inputCloud为输入点云,是经过滤波处理后的,20为最大迭代次数,0.3为判定阈值,小于阈值的点判定为内点。在SegmentPlane函数最后有这样一条语句
std::pair<typename pcl::PointCloud<PointT>::Ptr, typename pcl::PointCloud<PointT>::Ptr> segResult = SeparateClouds(inliers,cloud);
这条语句中调用了SeparateClouds函数,这个函数也在processPointCloud.cpp文件中,函数功能是将提取点云并存为平面点云和目标物点云
std::pair<typename pcl::PointCloud<PointT>::Ptr, typename pcl::PointCloud<PointT>::Ptr> ProcessPointClouds<PointT>::SeparateClouds(pcl::PointIndices::Ptr inliers, typename pcl::PointCloud<PointT>::Ptr cloud) { // TODO: Create two new point clouds, one cloud with obstacles and other with segmented plane typename pcl::PointCloud<PointT>::Ptr obstCloud (new pcl::PointCloud<PointT> ()); //目标点云指针 typename pcl::PointCloud<PointT>::Ptr planeCloud (new pcl::PointCloud<PointT> ());//平面点云指针 for(int index: inliers->indices) planeCloud->points.push_back(cloud->points[index]); pcl::ExtractIndices<PointT> extract; //ExtractIndices通过分割算法提取部分点云数据子集的下标索引 extract.setInputCloud (cloud); //设置输入点云 extract.setIndices(inliers); //提取内点 extract.setNegative(true); //提取外点,继续处理 extract.filter(*obstCloud);//将外点(即目标点)提取至obstCloud std::pair<typename pcl::PointCloud<PointT>::Ptr, typename pcl::PointCloud<PointT>::Ptr> segResult(obstCloud, planeCloud);//储存两种点云 return segResult; }
2.聚类Clustering
在对点云进行分割后,工程已经可以将lidar的返回点云数据分割成目标物(障碍物)点云和平面(车道平面)点云,接下来要完成的任务就是将障碍物的点云进行聚类,将属于一个障碍物的点云归为一类。课程中使用的聚类方法是欧氏距离聚类,这个算法是根据点之间的紧密程度来关联点组。 为了有效地进行最近邻居搜索,可以使用KD-Tree数据结构,该结构平均可以将查找时间从O(n)加快到O(log(n))。相关资料可以参考以下文章:
KD-Tree与欧式距离聚类
udacity的工程中使用的是PCL库的欧式聚类算法,但同样对采用KD-Tree结构进行欧式聚类的方法进行的简要介绍和仿真。这里不过多记录,直接看工程中的实现部分
在environment.cpp函数中下面语句调用了Clustering函数std::vector<pcl::PointCloud<pcl::PointXYZI>::Ptr> cloudClusters = pointProcessorI.Clustering(segmentCloud.first,0.53,10,500); //障碍物点云,采用KdTree将其进行欧式聚类
Clustering函数有三个参数
参数1为输入点云,这里segmentCloud.first表示是障碍物点云,我们对障碍物点云进行聚类
参数2为设置欧式聚类的近邻搜索的搜索半径,半径越大,搜索范围越大
参数3、4为一个类中点的上限和下限Clustering函数定义如下
std::vector<typename pcl::PointCloud<PointT>::Ptr> ProcessPointClouds<PointT>::Clustering(typename pcl::PointCloud<PointT>::Ptr cloud, float clusterTolerance, int minSize, int maxSize) { // Time clustering process auto startTime = std::chrono::steady_clock::now(); std::vector<typename pcl::PointCloud<PointT>::Ptr> clusters; // TODO:: Fill in the function to perform euclidean clustering to group detected obstacles typename pcl::search::KdTree<PointT>::Ptr tree(new pcl::search::KdTree<PointT>); //kd树,是一种分割k维数据空间的数据结构。 tree->setInputCloud(cloud); //输入点云 std::vector<pcl::PointIndices> clusterIndices; //找到簇的索引 pcl::EuclideanClusterExtraction<PointT> ec; ec.setClusterTolerance(clusterTolerance); //设置近邻搜索的搜索半径 ec.setMinClusterSize(minSize); //设置一个类所需要的最少点 ec.setMaxClusterSize(maxSize); //设置一个类点云的上限 ec.setSearchMethod(tree); //设置点云的搜索机制,此处为KdTree ec.setInputCloud(cloud); ec.extract(clusterIndices); //从点云中提取聚类,并保存在点云索引clusterIndices中 for(pcl::PointIndices getIndices : clusterIndices) { typename pcl::PointCloud<PointT>::Ptr cloudCluster (new pcl::PointCloud<PointT>); for(int index : getIndices.indices) cloudCluster->push_back(cloud->points[index]); cloudCluster->width = cloudCluster->points.size(); cloudCluster->height = 1; cloudCluster->is_dense = true; clusters.push_back(cloudCluster); } auto endTime = std::chrono::steady_clock::now(); auto elapsedTime = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime); std::cout << "clustering took " << elapsedTime.count() << " milliseconds and found " << clusters.size() << " clusters" << std::endl; return clusters; //返回聚类 }
拿聚类仿真的图片来说明以下效果吧,同样颜色的点被分为一类。这也是KD-Tree的数据结构
至此,点云的分割和聚类操作已经完成,为方便观看,接下来要对一类的点云进行修饰,用一个立方体将一类的点云数据框起来, 这部分代码相对简单,直接上代码Box ProcessPointClouds<PointT>::BoundingBox(typename pcl::PointCloud<PointT>::Ptr cluster) { // Find bounding box for one of the clusters PointT minPoint, maxPoint; pcl::getMinMax3D(*cluster, minPoint, maxPoint ); Box box; box.x_min = minPoint.x; box.y_min = minPoint.y; box.z_min = minPoint.z; box.x_max = maxPoint.x; box.y_max = maxPoint.y; box.z_max = maxPoint.z; return box; }
这部分在传感器融合的第一篇文章中也记录过,不再赘述。
最后的结果就是下面这样
绿色点为车道平面点云 障碍物的点云分别渲染成了不同颜色,并对一类的点云,用立方体进行包围。每一个立方体就代表一个障碍物。
-
结合无人机载LiDAR点云法向量的K-means 聚类精简.pdf
2021-08-18 23:52:16结合无人机载LiDAR点云法向量的K-means 聚类精简.pdf -
类似matlab矩阵功能的c代码-vtkCloudPoint:vtk聚类(dbscan)和匹配(icp)LiDAR云点
2021-05-19 22:25:04类似matlab矩阵功能的c代码 ...聚类结果基于聚类半径和聚类长宽比的剔除 聚类质心和真值物方值的匹配 各种预处理数据输出 ##bugs known## 聚类效率捉急 分布式?应该可以 但是软件对象是standalone版本的 -
基于KD树聚类的机载LiDAR数据输电线提取方法
2020-02-08 14:49:25基于KD树聚类的机载LiDAR数据输电线提取方法,梁静,张继贤,论文提出并实现了一种基于kd树近邻域点云聚类法从LiDAR点云数据中自动提取多根电力线。首先利用高程直方图统计法去除地面点,接着� -
基于欧氏聚类的改进激光雷达障碍物检测方法
2021-01-26 00:10:45为了解决此问题,提出一种基于点云射线角度约束的改进欧氏聚类算法,使障碍物检测更加快速准确,所提算法有效解决了点云密度不均匀导致的检测障碍物成功率较低的问题,同时对所提算法进行实车实验。实验结果表明,与传统... -
地面点云分割与欧式聚类.zip
2021-02-10 09:21:29地面点云分割与欧式聚类.zip -
LiDAR点云数据及其处理
2021-06-15 14:07:14点云数据是LiDAR的主要数据,尤其是早期的LiDAR数据处理都是针对点云数据进行的。机载LiDAR激光脚点的分布是按照时间序列进行采样和存储的,其在地面上的分布不是规则的,其空间分布呈现为离散的数据“点云”。这些...点云数据是LiDAR的主要数据,尤其是早期的LiDAR数据处理都是针对点云数据进行的。机载LiDAR激光脚点的分布是按照时间序列进行采样和存储的,其在地面上的分布不是规则的,其空间分布呈现为离散的数据“点云”。这些点中,有些点位于真实地形表面上,有些位于不同的地物上(房屋、管线、烟囱等),还有些落在植被上(数木、灌木、草)等。
激光脚点分布LiDAR点云数据中信息的分类提取,即点云数据的分类工作在整个 LiDAR数据后处理过程中占 60%-80%的工作量,但目前还没有一种全能的方法能有效的提取复杂地形中的各种信息。且现有的分类算法的具体操作细节也由于版权问题极少公开,这也增加了分类算法研究的难度。机载LiDAR数据采集具有一定的盲目性,激光脚点的位置是随机的,不能保证地形特征点和地物特征点能有数据,这给激光脚点性质的判别带来了很大的困难,使机载LiDAR数据的分类很困难。
LiDAR点云数据的分类可分为一级分类和二级分类,一级分类主要指区分地面点和地物点,而二级分类是指在一级分类的基础上对地物点集的再分类,主要分类类别包括有植被、建筑物、道路信息和电力线等等。一般的分类方法还停留在一级分类上。
国外 LiDAR点云的分类算法的研究起步较早,发展的分类方法理论基础主要分成四类:基于坡度理论的分类方法、最小区域分类方法、基于面理论的分类方法和聚类/分割算法。
1、坡度理论
计算相异的两点间的坡度值或高差,当这个坡度值或高差超过设定的阈值时,就认为其中的较高点就是地物点(如图 2-27(a)所示)。这种理论的基础是假设陡坡只会出现在地物数据集中。
2、最小区域理论设定一个水平面,并在其垂直方向上设置一定区域作为缓冲区,包含在这个三维缓冲区域内的点都划为地面点集(如图2-27(b)所示)。
3、面理论
不同于最小区域理论,面理论选择的面是一个由参数计算的不规则的面,在面上也设定一个缓冲区,包含在这个三维缓冲区域内的点划为地面点集(如图 2-27(c)所示)。
4、聚类/分割算法
用周围邻近区点域进行分类时,聚类/分割算法的理论依据是一个类中所有的点共同来描述一个完整的物体,而非物体中单独的面(如图2-27(d)所示)。聚类算法是由 Filin(2002) 和 Roggero(2002)提出,分割算法是由 Lee, Schenk 和 Sithole(2002)提出。目前基于面理论的分类方法使用得最广泛。依据模拟近似地面方法的不同,可以再将分类方法细分为两种:
1、内插的分类方法
线性加权最小二乘内插模拟近似地面(Kraus and Pfeifer,1999), 计算点到初始模拟面的高差。通常情况下,地物点到初始模拟面的高差为正,而地面点到初始模拟面的高差则为负。在重新计算近似地面时,正高差的权较小,甚至为负;负高差将获取较大的权,甚至接近 1。将分级的概念融合到内插中可以得到一种新的分类方法(Pfeifer et al,2001)。进一步改进,用标准化最小二乘取代最小二乘得到另外一种新方法,但此方法需要预先获取一些参数的值(Lee 和 Younan, 2003)。2、基于数学形态学原理的分类方法
利用数学形态学的操作运算来获取近似地面,如开运算。数学形态学的方法从概念上来讲,是简单易操作的。只要激光点云数据分辨率足够好,开运算就能有效地剔除地面物信息。如果数据分辨率太低,就需要较大的操作窗口来提出地物信息,相应的一些地面突出特征也会被抹平(Qi Chen,2007)。
图2-27 国外分类方法的分类原理示意图
(a)坡度理论;(b) 最小区域理论;© 面理论;(d) 聚类/分割理论
[参考文献] 王丽英. 机载LiDAR数据误差处理理论与方法[M]. 测绘出版社, 2013 -
Lidar_Obstacle_Detection_for_article:用于传感器融合系列(一、二)——激光雷达点云的分割、聚类原理及...
2021-05-11 11:24:16传感器融合自动驾驶汽车课程 欢迎参加自动驾驶汽车的传感器融合课程。 在本课程中,我们将讨论传感器融合,这是从多个传感器获取数据并将其组合以使我们对周围世界有更好了解的过程。 我们将主要集中在激光雷达和... -
无人驾驶汽车系统入门(三十一)——点云分割和聚类算法详解
2021-03-22 17:26:19无人驾驶汽车系统入门(三十一)——点云分割和聚类算法详解 本篇详细讲解点云处理中的基本分割和聚类的算法原理。 Lidar基本常识 lidar的分辨率要高于radar,但是radar可以直接测量目标的速度。通过融合两者,...无人驾驶汽车系统入门(三十一)——点云分割和聚类算法详解
本篇详细讲解点云处理中的基本分割和聚类的算法原理。
Lidar基本常识
lidar的分辨率要高于radar,但是radar可以直接测量目标的速度。通过融合两者,可以获得对目标较好的位置和速度估计。
激光雷达坐标系:右手法则,大拇指朝上为z,食指朝前为x,中指朝左为y, lidar的解析度很大程度上取决于线数,其解析度指标分为横向解析度和纵向解析度,横向解析度即一条激光束扫描一圈(360度)的反射点的数量,作为参考,Velodyne的16线激光雷达的横向解析度为1800个反射点,即:
360 1800 = 0.2 d e g r e e / p o i n t \frac{360}{1800} = 0.2 \ degree/point 1800360=0.2 degree/point
也就是说这一款雷达横向上每0.2度有一个反射点。纵向解析度即雷达的线束数量,线束越多解析度越高。
常用的point cloud处理工具:
- PCL: 主要用于点云滤波、分割和聚类
- OpenCV
- ROS:提供了一些点云数据表示、消息格式、坐标变化、可视化工具
- Eigen:线性运算库,可用于描述各类变换,通常用于点云的坐标变换(点云SLAM里用的比较多)
传统的点云感知算法处理流程:
- 点云滤波:降采样点云以加速后续计算
- 点云分割:分别提取出地面点和非地面点
- 点云聚类:将非地面点通过空间关系聚类成点云簇
- 目标轮廓拟合:使用设定形状(如bounding box)将点云簇拟合
本文详细讲解基础的点云分割和点云聚类算法。
点云滤波和降采样
为什么做滤波(filter)和降采样?
滤波是点云预处理的步骤,可以显著减低后续处理的计算复杂度,有些滤波方法还能够滤除点云中的噪点。PCL提供多种点云滤波方法的实现,其中应用最多的是体素滤波:Voxel grid filter. 体素滤波即将空间按照一定尺寸(比如说 1 m × 1 m × 1 m 1m \times 1m \times 1m 1m×1m×1m)的立方体格进行划分,每个立方格内仅保留一个点。下图是voxel size为0.3m的降采样结果。
PCL提供各类成熟的点云滤波方法,以体素滤波为例:
typename pcl::VoxelGrid<PointT> voxel_filter; voxel_filter.setInputCloud(cloud); voxel_filter.setLeafSize(filterRes, filterRes, filterRes); typename pcl::PointCloud<PointT>::Ptr ds_cloud(new pcl::PointCloud<PointT>); voxel_filter.filter(*ds_cloud);
点云分割:RANSAC 算法
RANSAC: RANdom SAmple Consensus, 通过随机采样和迭代的方法用一种模型(比如说直线模型、平面模型)拟合一群数据,在点云处理中通常用于点云数据的分割,以最简单的直线拟合为例:
给定平面内若干个点的集合 P n : { ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x n , y n ) } P_n: \{(x_0, y_0), (x_1, y_1), ... , (x_n, y_n)\} Pn:{(x0,y0),(x1,y1),...,(xn,yn)},要求得一条直线 L : a x + b y + c = 0 L: ax+by+c=0 L:ax+by+c=0 使得拟合尽可能多的点,也就是 n n n 个点到直线 L L L 的距离和最短;RANSAC的做法是通过一定的迭代次数(比如1000次),在每次迭代中随机在点集 P n P_n Pn 中选取两个点 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x1, y1), (x2, y2) (x1,y1),(x2,y2),计算 a , b , c a, b, c a,b,c:
a = y 1 − y 2 , b = x 2 − x 1 , c = x 1 ∗ y 2 − x 2 ∗ y 1 a = y1 - y2, \\ b = x2 - x1, \\ c = x1*y2 -x2*y1 a=y1−y2,b=x2−x1,c=x1∗y2−x2∗y1
接着遍历 P n P_n Pn 每一个点 ( x i , y i ) (x_i, y_i) (xi,yi)到直线 L L L 的距离 d i s t dist dist,
d i s t = f a b s ( a ∗ x i + b ∗ y i + c ) s q r t ( a ∗ a + b ∗ b ) dist = \frac{fabs(a * x_i + b * y_i + c)}{sqrt(a*a + b*b)} dist=sqrt(a∗a+b∗b)fabs(a∗xi+b∗yi+c)
当 d i s t dist dist小于我们给定的一个距离阈值 D t h r e s h o l d D_{threshold} Dthreshold,则认为点在L上,穿过点最多的直线即为RANSAC搜索的最优(拟合)的直线。平面拟合同理。
PCL中已经成熟地实现了各类模型地RANSAC拟合,以平面拟合为例:
// cloud are input cloud, maxIterations and // distanceThreshold are hyperparameters pcl::ModelCoefficients::Ptr coefficients (new pcl::ModelCoefficients ()); pcl::PointIndices::Ptr inliers(new pcl::PointIndices()); pcl::SACSegmentation<PointT> seg; seg.setOptimizeCoefficients(true); seg.setModelType(pcl::SACMODEL_PLANE); seg.setMethodType(pcl::SAC_RANSAC); seg.setMaxIterations(maxIterations); seg.setDistanceThreshold(distanceThreshold); seg.setInputCloud(cloud); // the indices in inliers are the points in line seg.segment(*inliers, *coefficients);
点云聚类之用于加速邻近点搜索的数据结构——KD树
KD树是一种用于加速最邻近搜索的二叉树,主要通过划分区域以实现加速,以2D的KD树为例,只需考虑x和y两个划分,假定点集如下:
{ ( 7 , 2 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 2 , 3 ) } \{(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)\} {(7,2),(5,4),(9,6),(4,7),(8,1),(2,3)}
往kd树中插入一个点 ( 7 , 2 ) (7,2) (7,2),在x方向对平面进行划分如下(横轴为x,纵轴为y):
接着依次插入第二个和第三个点,第二个点是 ( 5 , 4 ) (5, 4) (5,4), 5小于7所有该点在左边, ( 9 , 6 ) (9, 6) (9,6)的 x x x大于7所以在右边,基于y对空间进行第二次划分(图中蓝线):
2D KD树的划分顺序为: x->y->x->y…, 所以到第四个点 ( 4 , 7 ) (4, 7) (4,7), 其 x x x小于 ( 7 , 2 ) (7, 2) (7,2)所以在根节点的左边, y y y大于 ( 5 , 4 ) (5, 4) (5,4)的 y y y所以在它的右边,依次类推得到对二维空间的划分图:
构造的树如下:
因为按区域进行了划分,kd树显著的降低了搜索的步数,以上图为例,假定我们聚类的距离阈值为4,要搜索出点 ( 2 , 3 ) (2,3) (2,3)的距离阈值内的点,先从根节点 ( 7 , 2 ) (7, 2) (7,2)开始,算得距离大于4,类似于插入点的流程,查找左边的点 ( 5 , 4 ) (5, 4) (5,4), 算得距离小于4,得到一个近距离点,接着搜索,虽然 ( 2 , 3 ) (2,3) (2,3)在 ( 5 , 4 ) (5,4) (5,4)左侧,但是为其本身,且无叶子节点,所以左侧搜索结束,看 ( 5 , 4 ) (5,4) (5,4)右侧节点,计算得 ( 4 , 7 ) (4, 7) (4,7)到目标点的距离大于4,搜索结束。
以下是一个用c++实现的2维KD树的例子:
// Structure to represent node of kd tree struct Node{ std::vector<float> point; int id; Node* left; Node* right; Node(std::vector<float> arr, int setId) : point(arr), id(setId), left(NULL), right(NULL){} }; struct KdTree { Node* root; KdTree(): root(NULL){} void insert(std::vector<float> point, int id){ recursive_insert(&root, 0, point, id); } void recursive_insert(Node **root, int depth, std::vector<float> point, int id){ if (*root!= NULL){ int i = depth%2; if(point[i] < (*root)->point[i]){ // left recursive_insert(&(*root)->left, depth+1, point, id); } else{ //right recursive_insert(&(*root)->right, depth+1, point, id); } }else{ *root = new Node(point, id); } } void recursive_search(Node * node, int depth, std::vector<int> &ids, std::vector<float> target, float distanceTol){ if(node != NULL){ // compare current node to target if ((node->point[0] >= (target[0]-distanceTol)) && (node->point[0] <= (target[0]+distanceTol)) && (node->point[1] >= (target[1]-distanceTol)) && (node->point[1] <= (target[1]+distanceTol))){ float dis = sqrt((node->point[0]-target[0]) * (node->point[0]-target[0]) + (node->point[1]-target[1]) * (node->point[1]-target[1])); if (dis <= distanceTol){ ids.push_back(node->id); } } if((target[depth%2] - distanceTol)<node->point[depth%2]){ // go to left recursive_search(node->left, depth + 1, ids, target, distanceTol); } if((target[depth%2] + distanceTol)>node->point[depth%2]){ // go to right recursive_search(node->right, depth+1, ids, target, distanceTol); } } } // return a list of point ids in the tree that are within distance of target std::vector<int> search(std::vector<float> target, float distanceTol){ std::vector<int> ids; recursive_search(root, 0, ids, target, distanceTol); return ids; } };
欧几里得聚类算法
点云聚类中常用的欧几里得聚类算法就是基于KD树实现的,聚类的目的是搜索出点云中“聚在一起”的点云簇,从而得到感知目标的位置和轮廓,以2D点欧几里得聚类为例,其处理过程如下:
std::vector<std::vector<int>> euclideanCluster(const std::vector<std::vector<float>>& points, KdTree* tree, float distanceTol){ std::vector<std::vector<int>> clusters; std::vector<bool> processed(points.size(), false); for (int i = 0; i < points.size(); ++i) { if (processed[i] == true){ continue; } else{ std::vector<int> cluster; Proximity(cluster, points, processed, distanceTol, tree, i); clusters.push_back(cluster); } } return clusters; } // 递归聚类 void Proximity(std::vector<int> & cluster, std::vector<std::vector<float>> point, std::vector<bool> &processed, float distanceTol, KdTree* tree, int ind){ processed[ind] = true; cluster.push_back(ind); std::vector<int> nearby_points = tree->search(point[ind], distanceTol); for (int i = 0; i < nearby_points.size(); ++i) { if(processed[nearby_points[i]]){ continue; } else { Proximity(cluster, point, processed, distanceTol, tree, nearby_points[i]); } } }
PCL中的欧几里得聚类
以上是关于KD树和欧几里得聚类的基本介绍,实际业务中我们并不需要自行实现欧几里得聚类,而且采用PCL中实现的欧几里得聚类,其基本用法如下:
template<typename PointT> std::vector<typename pcl::PointCloud<PointT>::Ptr> ProcessPointClouds<PointT>::Clustering(typename pcl::PointCloud<PointT>::Ptr cloud, float clusterTolerance, int minSize, int maxSize) { std::vector<typename pcl::PointCloud<PointT>::Ptr> clusters; // perform euclidean clustering to group detected obstacles typename pcl::search::KdTree<PointT>::Ptr kd_tree(new pcl::search::KdTree<PointT>()); kd_tree->setInputCloud(cloud); typename pcl::EuclideanClusterExtraction<PointT> eu_cluster; eu_cluster.setClusterTolerance(clusterTolerance); eu_cluster.setMinClusterSize(minSize); eu_cluster.setMaxClusterSize(maxSize); eu_cluster.setSearchMethod(kd_tree); eu_cluster.setInputCloud(cloud); std::vector<pcl::PointIndices> cluster_list; eu_cluster.extract(cluster_list); for (auto cluster_indices : cluster_list){ typename pcl::PointCloud<PointT>::Ptr cluster_points (new pcl::PointCloud<PointT>()); for(auto ind : cluster_indices.indices){ cluster_points->points.push_back(cloud->points[ind]); } cluster_points->width = cluster_points->points.size(); cluster_points->height = 1; cluster_points->is_dense = true; clusters.push_back(cluster_points); } return clusters; }
更详细的ros实现可以参考我的这篇博客:https://blog.csdn.net/AdamShan/article/details/83015570?spm=1001.2014.3001.5501
-
Lidar_For_AD_references:有关自动驾驶激光雷达点云处理的参考文献列表
2021-05-07 02:38:35LiDAR Pointcloud聚类/语义分割/平面提取 任务:道路/地面提取,平面提取,语义分割,开放集实例分割,聚类 3D点云的快速分割:自动驾驶汽车应用的LiDAR数据范例ICRA 2017 [ , ] 用于自动驾驶的时间序列LIDAR数据... -
SFND_Lidar_Obstacle_Detection
2021-02-10 17:52:42在该项目中,我从激光雷达传感器获得了一组点云数据,我实现了分段和聚类以检测车辆周围的物体。 没有预处理方法的原始点云为: 使用RANSAC进行细分 RANSAC代表随机样本共识,是一种检测数据中异常值的方法。 RANSAC... -
基于VG-DBSCAN算法的大场景散乱点云去噪
2021-02-12 05:16:20针对城市环境下三维激光雷达(LiDAR)点云数据密度不均匀、离群噪点多而不利于后期点云帧间匹配的问题,提出一种应用于城市环境下大规模散乱LiDAR点云的离群噪点滤除算法。该算法对传统的基于密度的噪声应用空间聚类... -
代码实战 | 用LeGO-LOAM实现BFS点云聚类和噪点剔除
2021-11-23 00:45:25LeGO-LOAM的软件框架分为五个部分: 分割聚类:这部分主要操作是分离出地面点云;同时,对剩下的点云进行聚类,剔除噪声(数量较少的点云簇,被标记为噪声); 特征提取:对分割后的点云(排除地面点云部分)进行边缘点... -
融合航空影像和LIDAR点云的建筑物探测及轮廓提取
2021-02-11 21:58:48通过分析机载雷达(LIDAR)点云数据与航空影像数据特点,提出了融合机载LIDAR点云和航空影像的建筑物轮廓探测方法。分别提取机载点云和航空影像中的部分建筑轮廓线,将轮廓线拟合成直线段的建筑物轮廓边,并以两相邻... -
Lidar 激光雷达与自动驾驶
2021-10-10 13:05:48激光雷达(/升aɪ d ɑːr /,也LIDAR,或激光雷达;有时LADAR)是用于确定的方法的范围由与靶向的物体(可变距离)激光并测量时间的反射光返回到接收器。由于激光返回时间的差异和不同的激光波长,激光雷达还可用于... -
读自动驾驶激光雷达物体检测技术(Lidar Obstacle Detection)(4):Clustering(欧式聚类)
2020-05-31 14:53:11在第(3)实现了地面点与障碍物的分离,此部分要实现的是聚类,聚类是指把不同物体的点云分别组合聚集起来, 从而能让你跟踪汽车, 行人等多个目标. 其中一种对点云数据进行分组和聚类的方法称为欧氏聚类。 欧式聚类... -
基于K平面的机载LiDAR数据分类,用于准确的建筑物屋顶测量
2021-04-08 12:32:54提出了一种基于k平面聚类算法的新分类方法,该方法将建筑物屋顶的点云从机载光检测测距仪(LiDAR)获得。 在激光点聚类的操作中,将点云中激光点的3D坐标直接用作聚类对象。 根据所获得的聚类解生成簇中激光点的拟合... -
lidar点云边缘线提取
2015-04-15 09:54:07基于坡度和聚类的算法,提取lidar点云的地物边缘线。最终得到地物的轮廓 -
航空影像辅助的机载LiDAR植被点云分类
2021-02-03 17:49:12在生成数字正射影像的基础上,首先利用K均值(K-means)聚类算法对影像进行聚类和图像增强,然后将增强后的影像和对应区域的点云数据进行融合,最后通过影像处理结果对机载LiDAR植被点云进行分类。选取某城市的机载LiDAR... -
基于车载LiDAR数据的道路边界精细提取
2020-05-02 00:33:12根据道路在车载激光点云数据中的表达特征,提出一种基于轨迹线辅助下的K均值聚类算法,开展针对道路边界线的自动精细提取研究,算法描述为:先进行数据预处理,将复杂轨迹简化成单一轨迹;再利用轨迹辅助,通过插入截面,将... -
pcl欧式聚类
2021-08-25 23:52:37https://github.com/nz-is/LiDAR-Obstacle-Detection 有windows系统 报错:123个 https://github.com/eazydammy/lidar-obstacle-detection