點雲演算法招聘

Ⅰ 標題 點雲數據三種採集方法的優缺點

格點采樣、均勻采樣、幾何采樣。
1.格點采樣：優點：效率非常高。采樣點分布比較均勻，但是均勻性沒有均價采樣高，可以通過格點的尺寸控制點間距。缺點：不能精確控制采樣點個數。
2.均勻采樣：優點：采樣點分布均勻。缺點：演算法時間復雜度有些高，因為每次采樣一個點，都要計算集合到集合之間的距離。
3.幾何采樣：優點：計算效率高，采樣點局部分布是均勻的，穩定性高：通過幾何特徵區域的劃分，使得采樣結果抗噪性更強。
點雲數據（point cloud data）是指在一個三維坐標系統中的一組向量的集合。掃描資料以點的形式記錄，每一個點包含有三維坐標，有些可能含有顏色信息（RGB）或反射強度信息。

Ⅱ 激光點雲預處理研究概述

       3D點雲數據的預處理是利用有效點雲信息進行三維重建及障礙物感知的基礎，是3D點雲配准、3D點雲拼接環節的前提。一般的 3D 點雲預處理工作包括地面點雲去除、點雲濾波和點雲分割。在三維點雲數據處理過程中，點雲數據離群點、雜訊點的剔除以及點雲數據的配准不僅是點雲數據處理中的重要環節，也是後期對點雲數據進行特徵提取完成檢測環節的基礎。

        在進行目標物體分割時，將離散的三維數據點聚類的判斷依據為點與點之間距離是否接近，而在激光雷達點雲數據中，有很大一部分數據屬於地面點數據，並且地面點雲呈現為紋理狀，這對後續障礙物點雲的分類，識別帶來干擾，如果不將這些地面點數據去除，在進行目標物體分割時會導致分割演算法失效，因此需要先進行過濾。所以，地面點雲數據去除是減少數據量以及提高分割演算法准確度的有效手段。

       因此為了提高去除地面點雲演算法的准確性和魯棒性，許多學者提出了大量研究方法，這些方法主要有以下兩類：基於柵格圖方法的地面去除研究、基於三維激光雷達原始掃描線數據的地面去除研究。

       通過激光雷達掃描得到的點雲包含大部分地面點，常用的柵格圖方法地面濾除點雲方法有柵格高度差法、法向量方法和高度法。柵格高度法首先根據柵格大小生成網格，計算每個網格最低點與最高點的高度差，比較h與預設高度差閾值大小，對網格進行分類，最後根據網格對網格內的點進行分類。法向量法是基於計算出地面法向量為豎直向下或向上的假設，即地面點法向量值為(0,0,1)或(0,0,-1)。方法過程是計算點法向量並設定點分類的法向量閾值。高度法去除地面點雲，是最常用且耗時最小的方法。根據激光雷達安裝位置與姿態，可以根據設定閾值直接將點雲分為地面點和障礙物點。

       基於柵格圖的點雲處理方式是通過將三維點雲數據投影到地面，建立多個柵格單元，採用連通區域標記演算法或者鄰域膨脹策略對目標進行聚類，這類方法被廣泛應用在激光雷達三維建模中。一是因為三維點雲向二維平面投影過程極大地壓縮了數據量，能夠提高演算法處理的實時性；二是因為點雲向柵格圖的映射，將復雜的三維點雲處理問題轉化為圖像處理問題，可以使用成熟的圖像處理相關演算法，提高了演算法處理的時間效率。柵格法簡單可靠、計算效率高，但是柵格單元參數固定且往往憑經驗確定，遠距離目標點雲較為稀疏往往會出現過分割，而近距離目標點雲較為稠密又會出現欠分割，演算法嚴重依賴於閾值參數的選擇，且往往需要逐幀進行分析，必然損失部分實時性。

       由於三維激光雷達的原始三維數據包含了詳細的空間信息，所以也可以用來進行相關點雲數據處理。激光掃描線在地面和障礙物形成的角度值存在顯著的不同，可作為分離地面點的重要依據。激光雷達中的多個激光器水平掃描周圍環境中的物體，在兩個相鄰物體之間形成的角度很小，而同一物體的角度值很大。這啟示了我們可以充分利用這一特性，大於角度閾值可認為這兩點是同一物體，較好地處理了相鄰目標欠分割的問題。通過將非地面點雲分割為不同物體，然後進行目標物體的識別，可以為無人車提供更加詳細的車輛、行人等障礙物信息，在運動中避免與不同類型的障礙物發生碰撞並進行及時避讓。地面點雲欠分割會導致目標漏檢，過分割又會對後續的識別等操作帶來影響。利用激光雷達產生點雲的幾何特性，研究人員提出了多種特徵構建的方法，基於三維激光雷達原始掃描線數據的地面去除研究屬於其中較為常用的方法。

       激光雷達在採集三維點雲數據的過程中，會受到各類因素的影響，所以在獲取數據時，就會出現一些雜訊。其實在實際工作中除了自身測量的誤差外，還會受到外界環境的影響如被測目標被遮擋，障礙物與被測目標表面材質等影響因素；另外，一些局部大尺度雜訊由於距離目標點雲較遠，無法使用同一種方法對其進行濾波。

       雜訊就是與目標信息描述沒有任何關聯的點，對於後續整個三維場景的重建起不到任何用處的點。但是在實際的點雲數據處理演算法中，把雜訊點和帶有特徵信息的目標點區別開來是很不容易的，去噪過程中由於許多外在因素總是不可避免的伴隨著一些特徵信息的丟失。一個好的點雲濾波演算法不僅實時性要求高，而且在去噪的同時也要很好的保留模型的特徵信息[88]。就需要把點雲數據的雜訊點特徵研究透徹，才能夠提出效果更好的去噪演算法。

       點雲數據是一種非結構化的數據格式，激光雷達掃描得到的點雲數據受物體與雷達距離的影響，分布具有不均勻性，距離雷達近的物體點雲數據分布密集，距離雷達遠的物體點雲數據分布稀疏。此外，點雲數據具有無序和非對稱的特徵，這就導致點雲數據在數據表徵時缺乏明確統一的數據結構，加劇了後續點雲的分割識別等處理的難度。神經網路作為一種端到端的網路結構，往往處理的數據是常規的輸入數據，如序列、圖像、視頻和3D數據等，無法對點集這樣的無序性數據直接進行處理，在用卷積操作處理點雲數據時，卷積直接將點雲的形狀信息舍棄掉，只對點雲的序列信息進行保留。

       點雲濾波是當前三維重建技術領域的研究熱點，同時也是許多無人駕駛應用數據處理過程中至關重要的一步。3D點雲濾波方法主要可以分為以下三類，主要包括基於統計濾波、基於鄰域濾波以及基於投影濾波。

       由於統計學概念特別符合點雲的特性，因此，許多國內外學者都將統計學方法引用到點雲濾波技術中，Kalogerakis 等人將一種穩健統計模型框架運用到點雲濾波中，取得了非常好的濾波效果。在這個統計模型框架中，通過使用最小二乘迭代方法來估計曲率張量，並在每次迭代的時候根據每個點周圍的領域來為樣本分配權重，從而細化每個點周圍的每一個鄰域。然後利用計算獲得的曲率以及統計權重來重新校正正態分布。通過全局能量的最小化並通過計算出的曲率和法線來把離群點去掉，並且能較好的保持點雲的紋理特徵。

       基於鄰域的點雲濾波技術，就是通過使用一種相似性度量的方法來度量點和其他周圍鄰域對濾波效率與結果影響比較大點的相似性，從而來確定濾波點的位置。一般來說，可以通過點雲的位置、法線和區域位置來度量其相似性。1998年，Tomasi等人將雙邊濾波器擴展到 3D 模型去噪，由於雙邊濾波器具有維持邊緣平滑的特點，所以在除去點雲數據雜訊的同時也能較好的保持細節。但是，由於該方法是通過一個網格生成的過程來去噪的，而在生成網格的過程就會引入額外的雜訊。相比較於規則格網、不規則三角網等數據結構，體元是真3D的結構並且隱含有鄰域關系，能夠有效的防止生成網格的過程中引入雜訊，但該方法的需要設置的參數比較多，不能滿足實際工業運用。

       基於投影濾波技術通過不同的投影測量來調整點雲中每個點的位置，從而實現雜訊點雲的去除。但是，如果輸入的點雲特別不均勻，經過局部最優投影處理後的點雲將變得更散亂。孫渡等人提出了一種基於多回波及 Fisher 判別的濾波演算法。首先結合格網劃分思想劃分點雲網格，在每個網格內，通過點雲數據的回波次數和強度進行劃分，分出待定的樣本；其次，利用Fisher判別的分析法將點雲投影到一維空間內，通過判定臨界值將植被點雲與地面點雲分離，實現陡坡點雲的濾波，但是，該方法只針對點雲中含有回波強度的屬性才有效，對於不包含回波強度信息的點雲，該方法失去作用。

       為彌補點雲本身的無序性、不對稱性、非結構化和信息量不充分等缺陷，在對點雲進行特徵識別及語義分割等操作之前，需先對點雲進行數據形式的變換操作。常用的點雲形式變換方法有網格化點雲、體素化點雲、將點雲進行球面映射等。

       體素化是為了保持點雲表面的特徵點的同時濾除不具備特徵的冗餘的點雲數據。由於常用的法向量計算取決於相鄰點的數量，並且兩個雲點的解析度也不同。所以具有相同體素大小的體素化就是為了在兩個不同解析度的點雲中生成等效的局部區域。在實際進行點雲配准演算法的過程中，由於用於配準的源點雲數據與目標點雲數據的數量比較龐大、點雲密集，並且這些原始點雲數據中含有許多點雲對於描述物體形狀特徵沒有任何作用的點，如果使用演算法直接對源點雲與目標點雲進行配置的話，整個過程將耗費大量時間，所以必須對點雲進行下采樣的同時仍保留住可以體現形狀輪廓特徵的那部分點雲。

       由於點雲本身的稀疏性、無序性和非均勻分布的特點，在利用深度全卷積神經網路結構對激光雷達點雲數據進行語義分割時，端到端的卷積神經網路無法直接對無序排布點雲進行操作。為使端到端的神經網路在無序性分布的點雲數據上具有通用性，需先對點雲數據進行映射，常見的投影方式有基於平面的投影、基於圓柱面的投影以及基於球面的點雲投影方式。

參考：

周天添等（基於深度神經網路的激光雷達點雲語義分割演算法研究）

李宏宇（激光雷達的點雲數據處理研究）

范小輝（基於激光雷達的行人目標檢測與識別）

Ⅲ 點雲數據處理

三維計算視覺研究內容包括：

（1）三維匹配：兩幀或者多幀點雲數據之間的匹配，因為激光掃描光束受物體遮擋的原因，不可能通過一次掃描完成對整個物體的三維點雲的獲取。因此需要從不同的位置和角度對物體進行掃描。三維匹配的目的就是把相鄰掃描的點雲數據拼接在一起。三維匹配重點關注匹配演算法，常用的演算法有 最近點迭代演算法 ICP 和各種全局匹配演算法。

（2）多視圖三維重建：計算機視覺中多視圖一般利用圖像信息，考慮多視幾何的一些約束，相關研究目前很火，射影幾何和多視圖幾何是視覺方法的基礎。在攝影測量中類似的存在共線方程，光束平差法等研究。這里也將點雲的多視匹配放在這里，比如人體的三維重建，點雲的多視重建不僅強調逐幀的匹配，還需要考慮不同角度觀測產生誤差累積，因此也存在一個優化或者平差的過程在裡面。通常是通過觀測形成閉環進行整體平差實現，多視圖重建強調整體優化。可以只使用圖像，或者點雲，也可以兩者結合（深度圖像）實現。重建的結果通常是Mesh網格。

（3）3D SLAM：點雲匹配（最近點迭代演算法 ICP、正態分布變換方法 NDT）+位姿圖優化（ g2o 、LUM、ELCH、Toro、SPA）；實時3D SLAM演算法 （LOAM）；Kalman濾波方法。3D SLAM通常產生3D點雲，或者Octree Map。基於視覺（單目、雙目、魚眼相機、深度相機）方法的SLAM，比如orbSLAM，lsdSLAM...

（4）目標識別：無人駕駛汽車中基於激光數據檢測場景中的行人、汽車、自行車、以及道路和道路附屬設施（行道樹、路燈、斑馬線等）。

（5）形狀檢測與分類：點雲技術在逆向工程中有很普遍的應用。構建大量的幾何模型之後，如何有效的管理，檢索是一個很困難的問題。需要對點雲（Mesh）模型進行特徵描述，分類。根據模型的特徵信息進行模型的檢索。同時包括如何從場景中檢索某類特定的物體，這類方法關注的重點是模型。

（6）語義分類：獲取場景點雲之後，如何有效的利用點雲信息，如何理解點雲場景的內容，進行點雲的分類很有必要，需要為每個點雲進行Labeling。可以分為基於點的方法，基於分割的分類方法。從方法上可以分為基於監督分類的技術或者非監督分類技術，深度學習也是一個很有希望應用的技術。

（7）立體視覺與立體匹配 ZNCC

（8）SFM（運動恢復結構）

1、點雲濾波方法（數據預處理）：

雙邊濾波、高斯濾波、條件濾波、直通濾波、隨機采樣一致性濾波。

VoxelGrid

2、關鍵點

ISS3D、Harris3D、NARF

SIFT3D、

3、特徵和特徵描述

法線和曲率計算 NormalEstimation 、特徵值分析Eigen-Analysis、 EGI

PFH、FPFH、3D Shape Context、Spin Image

4、 點雲匹配

ICP 、穩健ICP、point to plane ICP、Point to line ICP、MBICP、GICP

NDT 3D 、Multil-Layer NDT

FPCS、KFPCS、SAC-IA

Line Segment Matching 、ICL

5、點雲分割與分類

分割：區域生長、Ransac線面提取、NDT-RANSAC、

K-Means、Normalize Cut（Context based）

3D Hough Transform(線、面提取)、連通分析、

分類：基於點的分類，基於分割的分類；監督分類與非監督分類

6、SLAM圖優化

g2o 、LUM、ELCH、Toro、SPA

SLAM方法：ICP、MBICP、IDC、likehood Field、 Cross Correlation 、NDT

7、目標識別、檢索

Hausdorff 距離計算（人臉識別）

8、變化檢測

基於八叉樹的變化檢測

9. 三維重建

泊松重建、Delaunay triangulations

表面重建，人體重建，建築物重建，樹木重建。

實時重建：重建植被或者農作物的4D（3D+時間）生長態勢；人體姿勢識別；表情識別；

10.點雲數據管理

點雲壓縮，點雲索引（KD、Octree），點雲LOD（金字塔），海量點雲的渲染

點雲驅動的計算機圖形學主要研究應用

http://vcc.szu.e.cn/research/2015/Points/