傳統(tǒng)方法的點云分割以及PCL中分割模塊
點擊上方“小白學(xué)視覺”，選擇加"星標"或“置頂”
重磅干貨，第一時間送達
三維點云分割是將同屬性的點云物體分割出來，以便于單獨對該點云物體處理，但是由于點云數(shù)據(jù)是一種高冗余度，且不均勻的數(shù)據(jù)結(jié)構(gòu)，所以點云分割具有一定挑戰(zhàn)性。
點云庫于（PCL）2011年推出以來，得到行業(yè)廣泛的應(yīng)用，該庫包含了最先進的3D感知算法，并包含了LIDAR和三維掃描儀的接口，這使得點云庫PCL在機器人領(lǐng)域持續(xù)不斷的發(fā)展壯大起來。至今為止已經(jīng)更新到了1.9.1版本。在圖像分割中常常用到前景與背景的分割處理，而在點云處理中，對于給定點云數(shù)據(jù)，分割的目標是將具有相似特征的點聚類成均勻區(qū)域，根據(jù)分割結(jié)果應(yīng)用于各個方面的場景分析，一般的方法時根據(jù)輸入點云的網(wǎng)格構(gòu)建圖形，使用邊界線的法線，平滑度或者是凹凸性等信息進行聚類分割，在文章【1】中調(diào)查了分割的方法有：凹凸性分割，分水嶺分析，層次聚類，區(qū)域增長以及頻譜聚類。這些方法不僅是應(yīng)用圖像，也廣泛的應(yīng)用于點云數(shù)據(jù)的分割。
在計算機視覺中，2D圖像的分割是一個很經(jīng)典的問題，并且已經(jīng)有著十幾年的研究歷史，其中基于傳統(tǒng)的方法比較流行有Graph Cuts[2],包含了Normalized Cuts和Min Cuts 這些方法的思想同樣適應(yīng)于3D點云的分割，并且這部分內(nèi)容在PCL中都已經(jīng)開源。
（1）魯棒性，比如樹木是具有與汽車相區(qū)別的特征的，當(dāng)點云數(shù)據(jù)的特征數(shù)量增加時，分割算法應(yīng)該具有一定的魯棒性，能夠?qū)W習(xí)如何自動的區(qū)分它們。
（2）其次分割應(yīng)該能夠根據(jù)其相鄰的信息推斷出稀疏點云中這些點的屬性或者判定出屬于哪個標簽。
（3）分割算法應(yīng)該能適用于不同的掃描器，即便是相同的場景在不同的掃描儀生成出的點云也是具有不同的屬性的，并且產(chǎn)生點云的質(zhì)量以及稀疏性的也是不一樣的。
點云數(shù)據(jù)雖然可以確定3D對象的形狀，大小和一些其他屬性，但是3D點云通常由于傳感器的限制，數(shù)據(jù)是嘈雜稀疏且無序的，比如激光雷達線性和角速率的變化，點的采集密度也是不均勻的，此外點云數(shù)據(jù)的表面形狀可以是任意的，是沒有數(shù)據(jù)統(tǒng)計分布呈現(xiàn)出來的。所以這就給點云的分割帶來一系列的問題。
Example scenes of (a) Cornell RGBD dataset, (b) VMR-Oakland dataset, ? KITTI dataset, and (d) Robotic 3D Scan Repository
如圖1 這些數(shù)據(jù)可分為兩類：Kinect捕獲的室內(nèi)數(shù)據(jù)集，以及由激光掃描儀（比如lidar）捕獲的室外數(shù)據(jù)集，將分割算法應(yīng)用于這些公共數(shù)據(jù)集使研究者們更加的了解分割算法的優(yōu)缺點。
（1）Cornell RGBD數(shù)據(jù)集： 該數(shù)據(jù)集具有52個標簽的具有RGB值的點云的室內(nèi)場（24個標記為辦公場景和28個標記的家庭場景）。使用RGBDSLAM [45]從原始RGB-D圖像創(chuàng)建點云數(shù)據(jù)。該數(shù)據(jù)集由大約550個視圖組成，具有2495個標簽對應(yīng)著27個種類的物體。
（2）VMR-Oakland數(shù)據(jù)集： 該數(shù)據(jù)集是通過移動平臺從CMU園區(qū)收集的帶有標記點云數(shù)據(jù)。使用激光掃描儀收集點云并以文本格式保存，每行中寫入三個實值坐標。并且提供訓(xùn)練集，和測試集。
（3） KITTI數(shù)據(jù)集：該數(shù)據(jù)集包括由360°Velodyne激光掃描儀捕獲的大量無組織點云數(shù)據(jù)。它是具有手動標記真值框的，如汽車，行人，電車，卡車和自行車等戶外的真值邊界框，用于訓(xùn)練集。
（4）Robotic 3D Scan Repository： 該數(shù)據(jù)集為室內(nèi)和室外環(huán)境提供3D點云數(shù)據(jù)集的集合。一些數(shù)據(jù)集包括熱量和顏色信息。這是3D點云數(shù)據(jù)的巨大集合，不僅可用于分割，還可用于不同其他算法使用。但是，這些數(shù)據(jù)集尚未標記，在將它們用作分割算法的輸入之前，可能是需要預(yù)處理步驟。
接下里將介紹五種傳統(tǒng)的分割算法：基于邊緣的方法，基于區(qū)域的方法，基于屬性的方法，基于模型的方法和基于圖優(yōu)化的方法。
01
基于邊緣的方法：邊緣是描述點云物體形狀的基本特征，這種方法檢測點云一些區(qū)域的邊界來獲取分割區(qū)域，這些方法的原理是定位出邊緣點的強度變化，論文【2】提出了一種邊緣檢測技術(shù)，通過計算梯度，檢測表面上單位法向量方向的變化來擬合線段。論文【3】是基于掃描線的分組進行快速分割，基于邊緣的方法雖然分割速度比較快但是準確度不能保證，因為邊緣對于噪聲和不均勻的或稀疏的點云非常敏感。
02
基于區(qū)域分割方法：基于區(qū)域的方法使用鄰域信息來將具有相似屬性的附近點歸類，以獲得到分割區(qū)域，并區(qū)分出不同區(qū)域之間的差異性?；趨^(qū)域的方法比基于邊緣的方法更準確。但是他們在分割過度或不足以及在如何準確確定區(qū)域邊界方面存在問題。研究者們將基于區(qū)域的方法分為兩類：種子區(qū)域（或自下而上）方法和非種子區(qū)域（或自上而下）方法。
種子區(qū)域方法：?基于種子的區(qū)域分割通過選擇多個種子點來開始做分割，從這些種子點為起始點，通過添加種子的鄰域點的方式逐漸形成點云區(qū)域，最初的算法是有論文【4】提出來，該算法主要包含了兩個步驟：
（1）基于每個點的曲率識別種子點，
（2）根據(jù)預(yù)定標準，該標準可以是點的相似度和點云的表面的相似度來生長種子點。
這種方法對噪聲點也非常敏感，并且耗時。但后續(xù)有很多基于這種方法的改進，比如對于激光雷達數(shù)據(jù)的區(qū)域增長的方法，提出了基于種子點的法向量和與生長平面的距離來生長種子點。種子區(qū)域方法高度依賴于選定的種子點。不準確選擇種子點會影響分割過程，并可能導(dǎo)致分割不足或過度。選擇種子點以及控制生長過程是耗時的。分割結(jié)果可能對所選的兼容性閾值敏感。另一個困難是決定是否在給定區(qū)域中添加點，因為這種方法對點云的噪聲也很敏感。
非種子區(qū)域方法：?這種方法時基于自上而下的方法。首先，所有點都分為一個區(qū)域。然后細分過程開始將其劃分為更小的區(qū)域。論文【5】使用這種方法指導(dǎo)聚類平面區(qū)域的過程，以重建建筑物的完整幾何形狀。該工作引入了基于局部區(qū)域的置信率為平面的分割方法。這種方法的局限性在于它也會可能過度分割，并且在分割其他對象（例如樹）時它不能很好地執(zhí)行。非種子區(qū)域方法的主要困難是決定細分的位置和方式。這些方法的另一個限制是它們需要大量的先驗知識（例如，對象模型，區(qū)域數(shù)量等），然后這些未知的先驗知識在復(fù)雜場景中通常是未知的。
03
基于屬性的方法：該方法是基于點云數(shù)據(jù)的屬性的一種魯棒性較好的分割方法，這種方法一般包括了兩個單獨的步驟：
第一步，基于屬性的計算。
第二步，將根據(jù)計算點的屬性進行聚類，這種聚類方法一般能適應(yīng)空間關(guān)系和點云的各種屬性，最終將不同的屬性的點云分割出來，但是這種方法局限性在于他們高度依賴派生屬性的質(zhì)量所以要求第一步能夠精確的計算點云數(shù)據(jù)的屬性，這樣才會在第二步中根據(jù)屬性的類別分割出最佳的效果。
論文【6】則是這種方法實現(xiàn)的，提出了一種基于特征空間聚類分析方法，在該方法中，使用一種自適應(yīng)斜率的鄰域系統(tǒng)導(dǎo)出法向量，使用點云數(shù)據(jù)的屬性，例如距離，點密度，點在水平或者垂直方向的分布，來定義測量點之間的領(lǐng)域，然后將每個方向上的法向量的斜率和點鄰域的數(shù)據(jù)之差作為聚類的屬性，這種方法可以消除異常值和噪聲的影響，基于屬性的方法是將點云分割相同屬性區(qū)域的高效方法，并且分割的結(jié)果靈活而準確。然而，這些方法依賴于點之間鄰域的定義和點云數(shù)據(jù)的點密度。當(dāng)處理大量輸入點的多維屬性時，這種方法的另一個限制是比較耗時。
04
基于模型的方法：該方法時基于幾何的形狀比如球形，圓錐，平面和圓柱形來對點云進行分組，那么根據(jù)這些幾個形狀，具有相同的數(shù)學(xué)表示的點將會被分割為同一組點，論文【7】中引入了一種眾所周知的算法RANSAC（RANdom SAmple Consensus）,RANSAC是強大的模型，用于檢測直線，圓等數(shù)學(xué)特征，這種應(yīng)用極為廣泛且可以認為是模型擬合的最先進技術(shù)，在3D點云的分割中需要改進的方法都是繼承了這種方法。基于模型的方法具有純粹的數(shù)學(xué)原理，快速且強大，具有異值性，這種方法的主要局限性在于處理不同點云是的不準確性。這種方法在點云庫中已經(jīng)實現(xiàn)了基于線，平面，圓等各種模型。
05
基于圖優(yōu)化的方法：圖優(yōu)化的方法在機器人的應(yīng)用中十分流行，眾所周知的方法是FH算法【7】，該方法簡單且高效，并且像Kruskal算法一樣用于在圖中查找最小生成樹。許多基于圖的方法的工作被投入到概率推理模型中，例如條件隨機場（CRF），使用CRF標記具有不同幾何表面基元的點的方法?；趫D優(yōu)化的方法在復(fù)雜的城市環(huán)境中成功地分割點云，具有接近實時的性能。為了與其他方法進行比較，基于圖形的方法可以對點云數(shù)據(jù)中的復(fù)雜場景進但是，這些方法通常無法實時運行。其中一些可能需要離線訓(xùn)練等步驟
以上將分割方法分為五類。但是，一般來說，有兩種基本方法。
第一種方法使用純數(shù)學(xué)模型和幾何推理技術(shù)，如區(qū)域增長或模型擬合，將線性和非線性模型擬合到點云數(shù)據(jù)。這種方法允許快速運行時間能實現(xiàn)良好的結(jié)果。這種方法的局限性在于在擬合物體時難以選擇模型的大小，對噪聲敏感并且在復(fù)雜場景中不能很好地工作。
第二種方法使用特征描述子的方法從點云數(shù)據(jù)中提取3D特征，并使用機器學(xué)習(xí)技術(shù)來學(xué)習(xí)不同類別的對象類型，然后使用結(jié)果模型對所獲取的數(shù)據(jù)進行分類。在復(fù)雜場景中，機器學(xué)習(xí)技術(shù)將優(yōu)于純粹基于幾何推理的技術(shù)。原因是由于噪聲，密度不均勻，點云數(shù)據(jù)中的遮擋，很難找到并將復(fù)雜的幾何圖元擬合到物體上。雖然機器學(xué)習(xí)技術(shù)可以提供更好的結(jié)果，但它們通常很慢并且依賴于特征提取過程的結(jié)果。
以上的這些算法在PCL的都已經(jīng)實現(xiàn)且都有現(xiàn)成的demo可以查看效果。
該模塊是在以上基本模塊的基礎(chǔ)上進行的研究，比如如何將點云數(shù)據(jù)構(gòu)造成kdtree或者Octree結(jié)構(gòu)使用FLANN（最近鄰搜索）的方式尋找點與周圍見之間的關(guān)系。
在PCL常用的聚類分割的類有以下幾種：
class pcl::ConditionalEuclideanClustering< PointT >
該類實現(xiàn)了用于設(shè)定的條件的歐式聚類的分類算法。
class pcl::CPCSegmentation< PointT >
對超體素圖進行分割的分割算法。它使用局部凹度引起的平面切割進行遞歸分割。使用局部約束的有向RANSAC進行分割。
CPC分割與LCCP分割是繼承的關(guān)系 ，具體論文【9】。
class pcl::EuclideanClusterExtraction< PointT >
歐幾里得聚類提取是歐幾里得意義上的聚類獲取分割的點云類。
class pcl::LabeledEuclideanClusterExtraction< PointT >
labeledeuclidenclusterextraction表示一個分段類，用于歐幾里得意義上的帶有標簽信息的聚類提取，
class pcl::ExtractPolygonalPrismData< PointT >
ExtractPolygonalPrismData使用一組表示平面模型的點索引，并與給定的高度一起生成三維多邊形棱柱。然后使用多邊形棱柱分割位于其內(nèi)部的所有點。
class pcl::GrabCut< PointT >
實現(xiàn)了GrabCut分割。
class pcl::segmentation::detail::RandomWalker< Graph, EdgeWeightMap, VertexColorMap >
實現(xiàn)隨機行走的優(yōu)化的分割方法，論文【10】
class pcl::LCCPSegmentation< PointT >
一種簡單的分割算法，將一個超體素圖分割成由凹邊界分隔的局部凸連接超體素組，論文【11】
class pcl::SACSegmentationFromNormals< PointT, PointNT >
結(jié)合點云的數(shù)據(jù)表面的法向量使用RANSAC方法的分割。
class pcl::SupervoxelClustering< PointT >
實現(xiàn)基于體素結(jié)構(gòu)、法線和RGB值的超體素算法。論文【12】。
【1】A. Shamir, Segmentation and shape extraction of 3D boundary meshes (state of the art report), in Eurographics, 2006
【2】 B. Bhanu, S. Lee,C. Ho, and T. Henderson, Range data processing:Representation of surfaces by edges. In proc.int. Pattern recognition conf, 1896
【3】X.Y. Jiang, H. Bunke, and U. Meier, Fast range image segmentation using high level segmentation primitives, In 3rd IEEE Workshop on Applications of Compute Vision, USA, 1996
【4】P.J. Besl, R.C. Jain, Segmentation through variable order surface fitting, IEEE Transaction on Pattern Analysis and Machine Intelligence 10, 1988.
【5】J. Chen, B.Chen, Architectural modeling from sparsely scanned range data. Int. J. Comput. Vision 78, 2008.
【6】S. Filin, N. Pfeifer, Segmentation of airborne data using a slope adaptive filter, ISPRS J. Photogramm. Remote Sens., vol. 60, pp. 71- 80, 2006.
【7】M. Fischler, R. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography Communications of the ACM
【8】P.F. Felzenszwalb, D.P. Huttenlocher, Efficient Graph-Based Image Segmentation, International Journal of Computer Vision, 59(2), 2004.
【9】M. Schoeler, J. Papon, F. Woergoetter Constrained Planar Cuts - Object?Partitioning for Point Clouds In Proceedings of the IEEE Conference on?Computer Vision and Pattern Recognition (CVPR) 2015
【10】Random Walks for Image Segmentation
【11】S. C. Stein, M. Schoeler, J. Papon, F. Woergoetter Object Partitioning?using Local Convexity In Proceedings of the IEEE Conference on?Computer Vision and Pattern Recognition (CVPR) 2014
【12】Voxel Cloud Connectivity Segmentation - Supervoxels from PointClouds In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2013
交流群
歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學(xué)影像、GAN、算法競賽等微信群（以后會逐漸細分），請掃描下面微信號加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三?+?上海交大?+?視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~