第六章計算機視覺三維測量與建模點云濾波與分割南京航空航天大學研究生教育教學改革專項（優質教學資源建設）項目資助01采樣點云特性】9隨著數據采集設備的不斷更新發展，三維點云的獲取變得越米越便捷，采集數據的設備包括數碼攝像機、結構光掃描儀、LiDAR掃描儀以及彩色深度（RGBD）攝像機等，然而數據獲取方式的差異也使采樣點云具有不同的屬性，同時包括各種潛在的數據缺陷，是表面重建工作需要面臨的重要挑戰。接下來概括描達采樣點云通常存在的一些典型問題，如圖6.1所示，以一個點云片段的截面為例。采樣點云特性嗓音（Noise）點云噪聲通常是指數據點隨機分布在靠近真實表面位置的情況典型的噪聲受以下因素的影響：傳感器的系統性問題、觀測目標的材料散射特性、深度值測量質量、傳感器與目標之間的距離等。0102外點（Outliers）外點也叫作異常值或者野值，它是指遠商真實表面的采樣點。小點的產生通常是由于在數據采集的過程中出現了結構性的錯誤。主要表現為隨機地分布生真實表面周團的離散點，通常這部分點的密度低于正常采樣數據的密度。外點也可以是戲群存在的，比如以較高密度點集群存在于遠離真實表面的位置。03采樣缺失（Missing）采樣缺失是由于在掃描過程中傳感器的采樣范圍有限、目標具有高吸收特性、目標形狀遮擋等因素造成的。這使得部分目標表面沒有采樣數據，主采樣密度為零的區域。采樣點云特性密度不均（UnevenDensity）對目標物表面進行掃描采樣時，點云在對應物體表面約密度分布被理解為采樣密度。三維掃描產生的點云通常會具有采樣密度不均勻的特點，這可能是由于采樣目標與掃描儀的距離變化、掃描儀攝影方向變換、采樣目標的自身形態特征等因素引起的。0405配準錯位（Misalignment）有時數據采集不是一次性完成的，而是利用多角度或者多頻次的采樣拼接得到整個目標場景的點云數據的。采樣點云特性采樣點云特性】9從程序實現的角度出發，將待估計距離直接用平方項進行比較，避免開平方運算的消耗,可大大提高算法效率。幾乎所有的ANN方法都基于對全空間的劃分，迅速找到查詢點所在的子空間,并將查詢點與子空間內的數據點進行比較計算。對于具體的應用而言,鄰域查詢還被分為兩種類型的查詢,即:找到離查詢點p，最近的k個點，不考慮這些點的分布范圍；找到距p，小于半徑r的至多k個點,此時查詢結果的個數可能小于k個。采樣點云特性在這些結構當中，八叉樹和KD樹是三維點云數據組織中應用最為廣泛的兩種。八叉樹數據結構是由二維空間的四叉樹數據結構推廣到三維空間而形成的，它是種樹形結構，在空間分解上具有很強的優勢。采樣點云特性KD樹是一種用于組織＆維空間中離散數據點的數據結構，它是一種二叉搜索樹，在最鄰近搜索上具有非常高的效率。采樣點云特性02點云濾波增強】96.1節所述的建模算法對掃描點云的采樣密度、表面法向量和噪聲分布等特性都有一定的要求，雖然許多隱式建模算法都可以容忍一定程度的點云密度的稀疏分布和法向量的方向翻轉錯誤的情況，但當存在大面積連續的法向量估計錯誤時，表面重建結果會有顯著的缺陷。因此，準確的法向量估計以及優化的點云空間結構，對于表面建模工作具有十分重要的意義。在本節中，將介紹與點云結構增強相結合的法向量估計優化算法,可以提高離散點云數據質量。點云濾波增強點云的法向量信息對于采樣點云的平面擬合、特征提取、表面分割、表面建模以及信息提取等研究來說有極其重要的作用。光滑表面在每一點上的法向量都有唯一的定義，即垂直于該點的空間切面的方向，在一個給定的點上切面空間的直觀表示是一個局部表面近似。表面法向量可以是有向的，其中每個法向量始終指向表面的內側或外側；法向量估計的結果也可能是無向的，即具體指向不確定。有向的法向量為重建算法提供了非常有用的線索，然而如果與點云相關的某些信息是不存在的，那么要得到一個方向明確的法向量是非常困難的。點云濾波增強主成分分析算法確定法向量的指向點云濾波增強最小生成樹(MST)算法使用Kruskal算法生成MST的方法可以稱為“加邊法”，初始最小生成樹的邊數為0，每迭代一次就選擇一條滿足條件的最小代價邊，加入最小生成樹的邊集合里。具體步驟如下：（1）把圖中的所有邊按代價從小到大排序；（2）把圖中的n個頂點視為獨立的由n棵樹組成的森林；（3）按權值從小到大選擇邊，所選的邊連接的兩個頂點應屬于兩棵不同的樹，則成為最小生成樹的一條邊，并將這兩棵樹合并為一棵樹；（4）重復上一步，直到所有頂點都在一棵樹內或者有1-1條邊為止。點云濾波增強一點的局部歐氏坐標系點云濾波增強01基于統計學的方法一種簡單的基于統計學方法的原理是假設點云里的所有點到其鄰域點的平均距離值的概率服從高斯分布，其形狀由均值和標準差決定。在算法處理時，首先將輸入點云數據中的每一個點到其鄰近點的距離分布情況進行計算，得到各點到它所有鄰近點的平均距離。然后，將平均距離在標準差范園之外的點定義為離群點，進而將這些離群點從點云中刪除。02基于表面重采樣的方法經典的表面重采樣方法從計算機圖形研究領域被推廣到了三維點云處理領域。基于表面重采樣的方法將點投影到估計的局部曲面。點云濾波增強03基于深度學習的方法它通過將點斑投影到一個基于學習得到的局部框架下，并在有監咨的環境中使用卷積神經網絡(ConvolutionalNeuralNetwork,CNN)將點斑移動到曲面上來，達到去噪的效果。另一種方法使用PCPNet將噪聲點云投影映射到一個千凈的點云曲面。此外，也有學者以人造目標為對象，研究用基于深度學習的方法提取邊特征，然后在保持邊特征的前提下對點云進行重采樣。點云濾波增強異常值（Outliers）檢測在許多領域都被應用，比如統計分析、機器學習、模式識別和數據壓縮等。采樣點云數據通常具有不同的點密度，此外測量誤差會引起稀疏的異常值和退化的結果。點云濾波增強主成分分析（PrincipalComponentAnalysis,PCA）算法是典型的協方差矩陣估計算法，它對觀測噪聲十分飯感，當噪聲強烈或有異常點存在時，所計算的結果會存在嚴重誤差。因此，下面提出了基于局部優化投影采樣算法的點云增強算法來滅小噪聲和異常點給法向量估計帶來的不利影響。點云濾波增強】9點云濾波增強03點云超體素分割】9點云分割的目的是將點云集合中的點分割成具有感知意義的符合目標邊界劃分性質的若干區域子集。在同一個區域中的點應該擁有相同的性質。該技術在機器視覺中有很多應用，例如，智能交通、現代測繪和自動導航。超體素（SuperVoxel）是一種集合,超體素聚類分割的目的不是完整地分割出某種特定目標,而是對點云實施一種過分割（OverSegmentation）。點云超體素分割】9依據馬爾可夫隨機場或條件隨機場條件，基于圖的算法將點云內部的上下文關系與對象級的類別先驗知識合并在一起，近些年來獲得了廣泛的研究應用。雖然這些技術的使用取得了顯著的進展，但有一個缺點，即在這些圖上進行推理的計算成本通常會隨肴圖的節點數量的增加而急劇增大。這意味著求解以每個點為一個節點的圖變得非常困難，這限制了算法在需要實時分割的應用中的使用。點云超體素分割超體素分割可以提供超體素過分割形式的節點，代替原始的點，減少了進行推理時必須考慮的節點數量，從而減小了后續處理算法的計算成本。基于超體素的后續分割或建模算法必須考慮重構數量，并且信息損失最小。點云超體素分割分割方法利用了觀測數據點之間的三維幾何關系，有時也包含附加的投影顏色或深度信息，分段區域內必須具有空間連接性的約束。點云的體素類型包含規則格網化的體素，這類體素可以認為是一種對空間規則劃分的具有等尺寸的立方體。另一類體素是不規則的過分割形式的體素，在本節討論的超體素指的就是不規則的過分割超體素。點云超體素分割】9首先考慮相似性度量，通常它是以法向量、曲率和離散度等屬性信息構成的特征空間中的特征向量來進行計算的，當點云數據的附加信息中具有影像紋理亮度時，亮度參數也被包含到點的特征向量中。下一步對所有點進行聚類判斷，不同于傳統的后均值聚類算法對將每個點與所有聚類中心做判斷，本算法中的原始點只與3倍搜索半徑內的種子點做相似性判斷。之后的運算與化均值聚類相似，利用相似性度量和距離度量判別聚類關系，并迭代更新聚類中心的位置，直到察類結果收斂。點云超體素分割構建鄰接關系圖。構建鄰接關系圖是VCCS的一個關鍵步驟，這一步能夠確保各個超體素不會跨越在空間中不相連的對象的邊界。在體素云化的三維空間中，有3種相鄰的形式，分別是6相鄰、18相鄰和26相鄰，它們分別共享一個面或邊，以及面、邊或頂點。0102選擇種子點。點云超體素分割設計特征空間和度量函數。0304基于約束的迭代聚類。05更新聚類中心，再選代直至收斂。點云超體素分割點云超體素分割04目標級別分割】9點云分割是將擁有相似特征的同質點劃分為獨立的區域，這些分割的區域具有語義層面同屬的意義。分割結果將有助于從多個方面分析一個場景，例如，定位識別物體和場景事件理解。良好的三維點云分割算法應當具有以下三條性質。第一，算法要能夠使用幾種不同種類的特征，例如，樹與車這兩種目標物有者不同的特征。當特征的數量變多時，分割算法要能夠學會如何自動地調整它們；第二，針對那些在采樣稀疏區域的點，分割算法需要能夠根據應用領域的先驗信息推斷點的類別；第三，良好的分割算法需要適用于數據采集時使用的不同類型的傳感器，因為不同的傳感器會產生不同質量的數據。目標級別分割人類可以輕松地從三維空間中感知物體的形狀、大小和類別性質。然而,計算機自動從三維點云中分割物體是一項困難的任務。點云數據通常是充滿噪聲的和無序的。基于影像匹配和三維重建獲得的三維點云，由于有標定參數的誤差和同名像素匹配的誤差，因此會存在比較明顯的表面噪聲;而用三維掃描儀獲取的三維數據，由于具有不同的線速率和角速率，因此點的采樣密度一般也是不均勻的。目標級別分割另外，表面形狀可以是擁有尖銳特征的任意形狀并且在數據中也沒有統計學分布規律。受觀測條件的限制，有時候前景和背景混雜在一起,還有遮擋造成的數據缺失，這些問題都為點云目標自動分割帶來了很大的困難。目標級別分割01基于邊緣的目標分割目標的邊緣描繪了物體的形狀特征。基于邊緣的目標分割方法探測點云中的多個域的邊界來得到分割點云。基于區域特性的目標分割方法利用應用領域的先驗信息，合并那些有相似性質的鄰近點，獲取獨立的區域。基于區域特性的目標分割方法比基于邊緣的目標分割方法更加準確，但是它有過分割和分割不足的問題，在確定區域邊界時也不夠準確。基于區域特性的目標分割方法可分為兩類：種子區域方法（自底向上）和非種子區域方法（自頂向下)。0203基于區域特性的目標分割基于特征空間聚類的方法基于特征空間聚類的方法是基于點云的獨立特征，使用模式識別中的聚類算法對點云進行分割的算法。目標級別分割三維霍夫變換平面檢測。三維霍夫變換平面檢測是將二維的直線檢測原理推廣到三維空間中的平面檢測，算法的關鍵在于尋找合適的平面基元的參數化表達式。在極坐標系下，使用原點到平面的距離和法線指向，構建平面方程0102隨機抽樣一致性檢。目標級別分割01基于體素表示的點云分割深度學習方法目標的邊緣描繪了物體的形狀特征。基于邊緣的目標分割方法探測點云中的多個域的邊界來得到分割點云。基于區域特性的目標分割方法利用應用領域的先驗信息，合并那些有相似性質的鄰近點，獲取獨立的區域。基于區域特性的目標分割方法比基于邊緣的目標分割方法更加準確，但是它有過分割和分割不足的問題，在確定區域邊界時也不夠準確。基于區域特性的目標分割方法可分為兩類：種子區域方法（自底向上）和非種子區域方法（自頂向下)。02基于映射影像表示的點云分割深度學習方法目標級別分割（1）MV3D網絡從不同的數據中提取3類特征，即提取俯視圖特征、前視圖特征和影像特征。（2）設計候選區域網絡。（3）把候選區域分別與提取的特征進行整合，從而把俯視圖候選區域投影到前視圖和影像中。（4）融合網絡。網絡最后使用整合后的數據得到最終的目標檢測框。02基于映射影像表示的點云分割深度學習方法目標級別分割03面向點設計的深度學習模型在自動駕駛領域中，車載載體常配有機械式的激光雷達IiDAR，也稱為線掃式LiDAR。這類LDAR的核心硬件是由若干組可以旋轉的激光發射器和接收器組成的，發射器發射的一條激光束稱為“線”，激光束多使用在900nm左右的近紅外波段。設備類型有單線、4線、16線、32線、40線、64線和128線等不同配置。04面向自動駕駛類LiDAR點云的目標檢測分割