點雲加演算法

1. 點雲重建有哪些經典的演算法

三維重構演算法得看你用什麼感測器了，如果是雙目相機，那一般都是極線幾何加視覺特徵配準的演算法了，優化就用bundleadjustment。如果是單目，較早的有PTAM,DTAM，近幾年structfrommotion比較火。如果是用Kinect之類的RGBD相機，比較好的有微軟的KinectFusion，PCL的開源KinFu，以及MIT的加強版Kintinuous。如果用激光，那一般都是當SLAM做了，前端嘛就各種ICP配准演算法了，後端的話，三維中主要還是用圖優化來做。

2. 點雲數據UDP數據包解析演算法舉例

# fill pcl msg

fields = [PointField('x', 0, PointField.FLOAT32, 1),

             PointField('y', 4, PointField.FLOAT32, 1),

             PointField('z', 8, PointField.FLOAT32, 1),

              PointField('intensity', 12, PointField.FLOAT32, 1)]

包括激光點的三維坐標、多次回波信息、強度信息、掃描角度、分類信息、飛行航帶信息、飛行姿態信息、項目信息、GPS信息、數據點顏色信息等

C–class（所屬類）

F一flight（航線號）

T一time（GPS時間）

I一intensity（回波強度）

R一return（第幾次回波）

N一number of return（回波次數）

A一scan angle（掃描角）

RGB一red green blue（RGB顏色值）

點雲數據UDP數據包解析演算法舉例

以某一個UDP數據包中Block 3中的Channel 5為例,具體的線束分布請參考附錄I:

1)由附錄I可知,Channel 5對應的水平角度偏移量為-1.042°,垂直角度為3.04°。

2)水平角度為轉子此時的角度加上水平角度偏移量=(Azimuth Angle 3+(-1.042))度

(注意 我們定義從上往下看時,順時針為水平角度正方向)。

3)解析UDP包Channel 5 Unit 3的值,其高位2個bytes構成的距離值乘以4mm即可得到以毫米為單位的真實世界的測距值。

至此,這一個測距點表示的測距方向和測距距離都得到了解析,可以在極坐標系或者直角坐標系中畫出此次測距對應的障礙物點位置。對每個UDP包中所有的測距數據都做這樣的解析,即可畫出實時的激光雷達測距點雲。

3.2 GPS數據UDP包

每一個GPS數據包都含有42 bytes乙太網包頭及512 bytes UDP數據。所有的多位元組值均為小端位元組序Little Endian。GPS數據包每秒被觸發一次,端

口10110。

在接收到GPS數據前,激光雷達內部的1Hz的信號上升沿會觸發一個GPS數據包。GPS數據包中的初始時間為000101000000(yymmddhhmmss,年,

月,日,時,分,秒)。如果GPRMC信息在開始時沒有被提供,此非真實的GPS時間會隨著內部1Hz信號更新。如果雷達接收到PPS信號和GPRMC數

據,本地的1Hz信號會被鎖定到PPS信號。GPS數據包還是通過內部1Hz信號上升沿觸發。同時,GPS數據包中的時間會被更新為GPRMC信息中的真實

時間。

GPS模塊首先會發送PPS信號,再發送GPRMC信息。雷達可以從中提取出UTC信息,並把6 bytes的UTC時間(年:月:日:時:分:秒)輸入到點雲

數據包中。用戶可以通過相加點雲數據包中4 bytes的時間戳和6 bytes的UTC時間來獲得此數據包的絕對時間。

一旦雷達獲取到GPS信號,數據包中的GPS時間就會根據接收到的GPRMC信息進行更新。如果GPS模塊停止發送數據,雷達依然會根據內部1Hz信號上

升沿觸發GPS數據包,並且數據包中GPS時間會根據之前得到的真實GPS時間計時。

3. ICP演算法的三維點雲演算法

三維激光掃描技術的快速發展,使其在各個領域得到廣泛應用。由於物理上的一些限制,一次三維激光掃描不能獲取掃描物體的全部數據,因此要對掃描點雲進行拼接。首先,對最常用的ICP演算法進行一系列研究,ICP演算法的前提條件是具有一個良好的配准初值,文中在配准初值的選取上採用主成分分析法,為後續ICP演算法的工作提供一個良好前提條件,增加點集預處理,點對查找上增加各種限制,採用kd-tree加速查找,以此對演算法進行改進,並通過實例來驗證本演算法的有效性及合理性。

4. 點雲數據處理

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

（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/

5. 點雲概念與點雲處理

點雲概念

點雲與三維圖像的關系 ：三維圖像是一種特殊的信息表達形式，其特徵是表達的空間中三個維度的數據，表現形式包括：深度圖（以灰度表達物體與相機的距離），幾何模型（由CAD軟體建立），點雲模型（所有逆向工程設備都將物體采樣成點雲）。和二維圖像相比，三維圖像藉助第三個維度的信息，可以實現天然的物體——背景解耦。點雲數據是最為常見也是最基礎的三維模型。點雲模型往往由測量直接得到，每個點對應一個測量點，未經過其他處理手段，故包含了最大的信息量。這些信息隱藏在點雲中需要以其他提取手段將其萃取出來，提取點雲中信息的過程則為三維圖像處理。

點雲的概念 ：點雲是在同一空間參考系下表達目標空間分布和目標表面特性的海量點集合，在獲取物體表面每個采樣點的空間坐標後，得到的是點的集合，稱之為「點雲」（Point Cloud）。

點雲的獲取設備 ：RGBD設備是獲取點雲的設備，比如PrimeSense公司的PrimeSensor、微軟的Kinect、華碩的XTionPRO。

點雲的內容 ：根據激光測量原理得到的點雲，包括三維坐標（XYZ）和激光反射強度（Intensity），強度信息與目標的表面材質、粗糙度、入射角方向，以及儀器的發射能量，激光波長有關。

根據攝影測量原理得到的點雲，包括三維坐標（XYZ）和顏色信息（RGB）。

結合激光測量和攝影測量原理得到點雲，包括三維坐標（XYZ）、激光反射強度（Intensity）和顏色信息（RGB）。

點雲的屬性 ：空間解析度、點位精度、表面法向量等。

點雲存儲格式 ：*.pts; *.asc ; *.dat; .stl ; [1] .imw；.xyz； .las。LAS格式文件已成為LiDAR數據的工業標准格式，LAS文件按每條掃描線排列方式存放數據,包括激光點的三維坐標、多次回波信息、強度信息、掃描角度、分類信息、飛行航帶信息、飛行姿態信息、項目信息、GPS信息、數據點顏色信息等。

C–class（所屬類）

F一flight（航線號）

T一time（GPS時間）

I一intensity（回波強度）

R一return（第幾次回波）

N一number of return（回波次數）

A一scan angle（掃描角）

RGB一red green blue（RGB顏色值）

點雲的數據類型 ：

（1）pcl::PointCloudpcl::PointXYZ

PointXYZ 成員：float x，y，z;表示了xyz3D信息，可以通過points[i].data[0]或points[i].x訪問點X的坐標值

（2）pcl::PointCloudpcl::PointXYZI

PointXYZI成員：float x, y, z, intensity; 表示XYZ信息加上強度信息的類型。

（3）pcl::PointCloudpcl::PointXYZRGB

PointXYZRGB 成員：float x,y,z,rgb; 表示XYZ信息加上RGB信息，RGB存儲為一個float。

（4）pcl::PointCloudpcl::PointXYZRGBA

PointXYZRGBA 成員：float x , y, z; uint32_t rgba; 表示XYZ信息加上RGBA信息，RGBA用32bit的int型存儲的。

（5） PointXY 成員：float x,y;簡單的二維x-y點結構

（6）Normal結構體：表示給定點所在樣本曲面上的法線方向，以及對應曲率的測量值，用第四個元素來佔位，兼容SSE和高效計算。

點雲的處理

點雲處理的三個層次 ：Marr將圖像處理分為三個層次，低層次包括圖像強化，濾波，關鍵點/邊緣檢測等基本操作。中層次包括連通域標記（label），圖像分割等操作。高層次包括物體識別，場景分析等操作。工程中的任務往往需要用到多個層次的圖像處理手段。

PCL官網對點雲處理方法給出了較為明晰的層次劃分，如圖所示。

此處的common指的是點雲數據的類型，包括XYZ，XYZC，XYZN，XYZG等很多類型點雲，歸根結底，最重要的信息還是包含在pointpcl::point::xyz中。可以看出，低層次的點雲處理主要包括濾波（filters），關鍵點（keypoints）/邊緣檢測。點雲的中層次處理則是特徵描述（feature），分割（segmention）與分類。高層次處理包括配准（registration），識別（recognition）。可見，點雲在分割的難易程度上比圖像處理更有優勢，准確的分割也為識別打好了基礎。

低層次處理方法:

①濾波方法：雙邊濾波、高斯濾波、條件濾波、直通濾波、隨機采樣一致性濾波。②關鍵點：ISS3D、Harris3D、NARF，SIFT3D

中層次處理方法：

①特徵描述：法線和曲率的計算、特徵值分析、SHOT、PFH、FPFH、3D Shape Context、Spin Image

②分割與分類：

分割：區域生長、Ransac線面提取、全局優化平面提取

K-Means、Normalize Cut（Context based）

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

分類：基於點的分類，基於分割的分類，基於深度學習的分類（PointNet，OctNet）

高層次處理方法：

①配准：點雲配准分為粗配准（Coarse Registration）和精配准（Fine Registration）兩個階段。

精配準的目的是在粗配準的基礎上讓點雲之間的空間位置差別最小化。應用最為廣泛的精配准演算法應該是ICP以及ICP的各種變種（穩健ICP、point to plane ICP、Point to line ICP、MBICP、GICP、NICP）。

粗配準是指在點雲相對位姿完全未知的情況下對點雲進行配准，可以為精配准提供良好的初始值。當前較為普遍的點雲自動粗配准演算法包括基於窮舉搜索的配准演算法和基於特徵匹配的配准演算法。

基於窮舉搜索的配准演算法：遍歷整個變換空間以選取使誤差函數最小化的變換關系或者列舉出使最多點對滿足的變換關系。如RANSAC配准演算法、四點一致集配准演算法（4-Point Congruent Set, 4PCS）、Super4PCS演算法等……

基於特徵匹配的配准演算法：通過被測物體本身所具備的形態特性構建點雲間的匹配對應，然後採用相關演算法對變換關系進行估計。如基於點FPFH特徵的SAC-IA、FGR等演算法、基於點SHOT特徵的AO演算法以及基於線特徵的ICL等…

②SLAM圖優化

Ceres（Google的最小二乘優化庫，很強大）， g2o、LUM、ELCH、Toro、SPA

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

③三維重建

泊松重建、 Delaunay triangulations、表面重建，人體重建，建築物重建，樹木重建。結構化重建：不是簡單的構建一個Mesh網格，而是為場景進行分割，為場景結構賦予語義信息。場景結構有層次之分，在幾何層次就是點線面。實時重建：重建植被或者農作物的4D（3D+時間）生長態勢；人體姿勢識別；表情識別；

④點雲數據管理：點雲壓縮，點雲索引（KD、Octree），點雲LOD（金字塔），海量點雲的渲染