大盤點！匯總點云分割算法，涉及RANSAC、歐式聚類、區(qū)域增長等
點云分割的目標是將點云數(shù)據(jù)中的點分成不同的組或類別，使每個組中的點都屬于同一種物體或區(qū)域。根據(jù)空間，幾何和紋理等特征對點云進行劃分，使同一劃分內(nèi)的點云擁有相似的特征。點云分割的目的是分塊，從而便于單獨處理。分割過程有助于從各個方面分析場景，例如定位和識別對象、分類和特征提取。
作者：PCIPG-zzl | 來源：計算機視覺工坊
添加微信：dddvisiona，備注：3D點云，拉你入群。文末附行業(yè)細分群。
點云的有效分割是許多應用的前提：
工業(yè)測量/逆向工程：對零件表面提前進行分割，再進行后續(xù)重建、計算特征等操作。
遙感領域：對地物進行提前分割，再進行分類識別等工作
點云分類（Point Cloud Classification）：點云分類是將點云中的每個點分配到預定義的類別或標簽中的任務。點云分類可用于識別點云中的不同物體或地物，例如識別建筑物、樹木、汽車等。為每個點分配一個語義標記。點云的分類是將點云分類到不同的點云集。同一個點云集具有相似或相同的屬性，例如地面、樹木、人等。點云分類也叫做點云語義分割。實例分割（Instance Segmentation）：實例分割是一種更高級的任務，它不僅要求識別點云中的不同物體或類別，還需要為每個物體中的每個點分配一個唯一的標識符，以區(qū)分不同實例。這使得實例分割能夠精確地區(qū)分出多個相同類別的物體，例如在一個點云場景中區(qū)分出多輛汽車或多棵樹。點云語義分割是指把一個大規(guī)模場景下的點云按照不同的類別給每個點云一個語義標簽，比如城市高速公路，所有的路燈會有一個相同的語義標簽，所有的路面會有 一個相同的語義標簽，所有的樹木會有同一個語義標簽。點云實例分割是在語義分割的基礎之上，把所有的路燈再一個一個分開，區(qū)別出來每一個路燈。這里也推薦「3D視覺工坊」新課程《三維點云處理：算法與實戰(zhàn)匯總》。
（Random Sample Consensus）隨機采樣一致性算法，采用迭代的方式從一組包含離群的被觀測數(shù)據(jù)中估算出數(shù)學模型的參數(shù)。RANSAC算法假設數(shù)據(jù)中包含正確數(shù)據(jù)和異常數(shù)據(jù)（或稱為噪聲），正確數(shù)據(jù)記為內(nèi)點（inliers），異常數(shù)據(jù)記為外點（outliers）
要得到一個直線模型，需要兩個點唯一確定一個直線方程。所以第一 步隨機選擇兩個點。
通過這兩個點，可以計算出這兩個點所表示的模型方程y=ax+b。
將所有的數(shù)據(jù)點套到這個模型中計算誤差。
找到所有滿足誤差閾值的點。
然后我們再重復1~4這個過程，直到達到一定迭代次數(shù)后，選出那個被 支持的最多的模型，作為問題的解。
RANSAC算法與最小二乘法區(qū)別RANSAC 算法：適用性：RANSAC主要用于處理包含噪音和異常值的數(shù)據(jù)集。它通過隨機采樣和迭代的方式來找到最佳擬合模型，忽略了外點的影響，因此在數(shù)據(jù)中含有大量噪音或少量異常值的情況下表現(xiàn)較好。步驟：RANSAC通過隨機選擇內(nèi)點樣本進行模型擬合，并通過計算內(nèi)點和模型之間的誤差來判斷外點。它迭代地選擇具有最大內(nèi)點數(shù)的模型作為最終擬合模型。優(yōu)點：魯棒性較強，能夠在存在噪音和異常值的情況下仍然得到合理的模型估計。最小二乘法：適用性：最小二乘法假設數(shù)據(jù)中的噪音較小，且異常值較少。它通過最小化數(shù)據(jù)點與模型之間的誤差平方和來得到最佳擬合模型，適用于數(shù)據(jù)比較干凈的情況。求解：最小二乘法可以直接求解或優(yōu)化模型參數(shù)的解析解，對于線性問題尤其有效。然而，在存在較多噪音或異常值時，最小二乘法容易受到這些數(shù)據(jù)點的影響，導致估計結(jié)果不準確。優(yōu)點：在數(shù)據(jù)相對干凈，噪音較小的情況下，最小二乘法能夠得到精確的模型估計。RANSAC算法被廣泛應用在計算機視覺領域和數(shù)學領域，例如直線擬合、平面擬合、計算圖像或點云間的變換矩陣、計算基礎矩陣等方面，使用的非常多?？傊?，RANSAC和最小二乘法適用于不同類型的數(shù)據(jù)情況。RANSAC適用于含有噪音和異常值的數(shù)據(jù)，能夠通過迭代的方式找到魯棒性較強的模型。最小二乘法適用于相對干凈的數(shù)據(jù)，能夠得到精確的模型估計，但容易受到噪音和異常值的影響。在實際應用中，根據(jù)數(shù)據(jù)的特點選擇合適的方法以獲得準確的模型估計。
pcl::ModelCoefficients::Ptr?coefficients(new?pcl::ModelCoefficients);pcl::PointIndices::Ptr?inliers(new?pcl::PointIndices);??//inliers用來存儲直線上點的索引pcl::SACSegmentation<pcl::PointXYZ>?seg;//創(chuàng)建一個分割器seg.setOptimizeCoefficients(true);??????//可選擇配置，設置模型系數(shù)需要優(yōu)化seg.setModelType(pcl::SACMODEL_LINE);???//設置目標幾何形狀seg.setMethodType(pcl::SAC_RANSAC);?????//擬合方法：隨機采樣法seg.setDistanceThreshold(0.05);?????????//設置誤差容忍范圍，也就是閾值seg.setMaxIterations(500);??????????????//最大迭代次數(shù)，不設置的話默認迭代50次seg.setInputCloud(cloud);???????????????//輸入點云seg.segment(*inliers,?*coefficients);???//擬合點云
歐式聚類算法（Euclidean Clustering）是一種將點云數(shù)據(jù)分割成不同聚類（簇）的算法。它是點云分割中的一種常用方法，旨在將距離比較近的點分為同一簇，從而識別出不同的物體或結(jié)構(gòu)。這個算法主要適用于包含較小噪音和具有一定距離差異的點云數(shù)據(jù)。基本思想：
選擇一個種子點（Seed Point）作為當前簇的起始點。
遍歷所有未分類的點，計算它們與種子點的距離。如果距離小于設定的閾值，將其歸為同一簇。
對于同一簇中的點，重復步驟2，將與當前簇內(nèi)任一點距離小于閾值的點加入簇。
切換到下一個未分類的點，作為新的種子點，繼續(xù)重復步驟2和3。
當所有點都被分類為某個簇，聚類過程結(jié)束。
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);?//?2cmec.setMinClusterSize?(100);ec.setMaxClusterSize?(25000);ec.setSearchMethod?(tree);ec.setInputCloud?(cloud_filtered);ec.extract?(cluster_indices);
一個桌子的場景圖經(jīng)過歐式聚類算法效果如下圖所示。
區(qū)域生長算法（Region Growing）是一種用于圖像處理和分割的算法，主要用于將點云中的點分成不同的區(qū)域，從而識別出具有相似特性的區(qū)域。區(qū)域生長算法基于相似性原則，將相似度高的點聚集在一起，形成連續(xù)的區(qū)域。算法步驟：1.初始化：選擇一個種子點，并將其標記為“已訪問”。2.根據(jù)設定的相似性準則，計算當前點與種子的相似度。3.如果當前點與種子相似度超過設定閾值，則將其標記為當前區(qū)域的一部分，并將其加入當前區(qū)域。4.遍歷當前點的鄰居（相鄰點），對每個鄰居執(zhí)行以下步驟：如果鄰居未被訪問過且與當前區(qū)域的相似度超過設定閾值，則將其標記為“已訪問”并添加到當前區(qū)域。遞歸地對鄰居的鄰居進行相似性判斷，將相似的像素或點添加到當前區(qū)域。5.重復步驟4，直到當前區(qū)域不能再生長為止。6.如果還存在未訪問的點，選擇一個未訪問的點作為新的種子，重復上述步驟。7.當所有點都被分配到區(qū)域后，分割過程結(jié)束。這里也推薦「3D視覺工坊」新課程《三維點云處理：算法與實戰(zhàn)匯總》。
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);
算法是針對小曲率變化面設計的，尤其適合對連續(xù)階梯平面進行分割
https://blog.csdn.net/luolaihua2018/article/details/120113848https://pcl.readthedocs.io/projects/tutorials/en/master/index.html#sample-consensus
