路面點云的并行簡化研究

孫大林 唐好選

摘 要：為有效解決大規(guī)模路面激光點云簡化過程中的時間延遲問題，在加速簡化過程的同時準確保留特征點，研究了基于斜率差的掃描線點云簡化算法及2種并行加速方式。首先從路面掃描線點云的分布特點出發(fā)，以相鄰點間連線的斜率差作為識別特征點的基準，實現(xiàn)了串行簡化算法。同時，在研究算法的流程并提取出可并行步驟的基礎上，分別設計實現(xiàn)了利用多核CPU的并行簡化算法和利用GPU的并行簡化算法。前者依靠OpenMP技術，實現(xiàn)的是一種多線程并行;后者在CUDA框架下實現(xiàn)，屬于CPU和GPU結合的異構并行計算。在實驗階段的實際路面點云上驗證算法執(zhí)行效果的同時，設計了3種算法在不同規(guī)模點云數(shù)據(jù)上的性能測試。通過繪制性能曲線，分析比較了2種并行算法的并行效果優(yōu)劣。最終實現(xiàn)的利用GPU的并行簡化算法與串行算法比較取得了100左右的加速比。

關鍵詞：點云精簡;GPU并行計算;OpenMP

文章編號：2095-2163（2019）04-0307-06 中圖分類號：TP391 文獻標志碼：A

0 引 言

目前，中國公路網(wǎng)絡已經(jīng)十分發(fā)達，從過去的高速建設期步入了以管理養(yǎng)護為主的管養(yǎng)期。而對于里程數(shù)已居于全球第二的中國路網(wǎng)來說，單純依靠人工進行路況檢測和養(yǎng)護顯然需要大量人力成本。同時還存在著效率欠佳、受天氣狀態(tài)影響等局限。因此引入裝載高精度激光傳感器的車載移動測量系統(tǒng)，來對路面信息進行建模及缺陷檢測就成為了解決本領域諸多局限的關鍵技術。根據(jù)《公路技術情況評定標準》JTGH20-2007中關于自動化路面狀態(tài)檢測部分的相關要求，車載移動測量系統(tǒng)在工作時需保證一定的速度。而在實際路面環(huán)境下，激光掃描設備采集到的路面點云規(guī)模龐大，對于建模而言將面臨巨大的時間消耗和硬件成本，且由于路面作為被掃描對象的客觀狀態(tài)是總體平整、局部波動的，即很大一部分的點云對于建模工作而言是冗余的。為此將如何合理簡化路面點云，一方面旨在減少需要處理的點云總數(shù)，另一方面力求突出更能體現(xiàn)局部狀態(tài)的特征點，就顯得尤為重要。

針對上述問題，提出使用并行計算技術。在研究點云簡化算法的基礎上，根據(jù)算法結構對可并行部分使用了并行處理，以提高算法執(zhí)行效率。依此思路，分別設計實現(xiàn)了基于多核CPU的并行算法和基于GPU的并行算法，并通過實驗測試對算法的性能進行了分析。

1 相關工作

近年來，針對不同類型的點云簡化已展開了一些研究。首先是對隨機分布的點云進行簡化的研究，本文雖然是聚焦于車載激光設備獲取的路面掃描線點云，但對前者隨機點云簡化的諸多方法也有著研究上的積極融合與借鑒。比較典型的成果有：文獻[1]將機器學習K-means聚類算法引入到點云的簡化過程中，對于隨機散亂點云，可以很好地提取到特征點，并通過刪除冗余來維持均勻合適的點集規(guī)模。文獻[2]和文獻[3]都使用了Kd-tree分割點云數(shù)據(jù)空間。前者針對不均勻分布點云，使用了Kd-tree建立點間的拓撲關系，從而劃定簡化的邊界，同時還結合局部法向量變化和已保留點作為閾值簡化區(qū)域內的點云。算法有效減少了不均勻分布點云在簡化率過高時產(chǎn)生的空洞。后者首先在空間域對點云進行全局聚類，構建Kd-tree，并以部分初始節(jié)點作為初始化聚類中心，然后利用主成分分析法對其做出多次深入細分，最終把有特征點的聚類映射到高斯球獲得的分類結果作為精簡結果。另據(jù)研究可知，由于簡化的關鍵在于識別和保留特征點，也有很多研究立足于此而陸續(xù)發(fā)表了一系列成果。較早的則當屬Moenning等人設計的可以在調用階段修改密度參數(shù)的簡化算法。在簡化過程中，結合色差和曲率變化決定每個點的特征權值，再依靠權值大小保留特征點，從而精簡點云規(guī)模[4]。此外，還涌現(xiàn)了把主曲率這一點云的幾何特征作為識別特征點的基準的方法，也就是通過對點云進行最小二乘拋物面擬合求出主曲率，并根據(jù)點的主曲率Hausdorff距離提取及保留特征點[5]。與此類似的是結合了邊緣特征和法向量特征的方法，即通過區(qū)分邊緣特征點和平滑區(qū)域特征點來分別進行簡化處理，首先識別并保存前者，從而保證點云模型框架的設計完整性。然后依據(jù)鄰近點的法向量變化在平滑區(qū)域保留一定的特征點[6]。上述算法的簡化率和適用范圍各有不同，但都能較好地保留原始點云的幾何特征。

對于以逐掃描線形式存儲的點云，文獻[7]通過引入RANSAC直線估計算法估算每條掃描線的斜率，消除了各條掃描線上因路面顛簸導致的路面點云不規(guī)則起伏失真，由此將會得到有效的簡化率。文獻[8]則設計了基于不同尺度的點抽稀和線抽稀方法，通過分析掃描線上某點的高程和強度，識別并保留特征點，取得了不錯的效果?？紤]到與隨機點云上根據(jù)特征進行簡化的思路類似，掃描線點云也具備一些可以用來選取特征點的幾何特性。從這一角度出發(fā)，文獻[9]提出了掃描線點云的角度差簡化算法和弦差簡化算法，以及這2種特征結合的角度-弦差簡化算法，取得了不錯的效果。文獻[10]也研發(fā)提出了一種基于掃描線點云的自適應角度限制簡化算法。該方法通過限制掃描中心角度，移動簡化窗口來達到簡化目的。

結合本文致力研究的掃描線點云來自路面這一比較平整物體的基礎背景，研究可知必然存在不同于其它掃描線點云的高冗余，即非特征點數(shù)量占絕大部分。此時就需要簡化算法提供很高的簡化率，并且在面向大規(guī)模點云的同時，簡化算法的時間效率也將尤其顯得重要。下面將重點探討本文的簡化算法，以及算法設計過程中借助不同并行計算技術實現(xiàn)的優(yōu)化加速。

2 算法概述

車載激光測量設備獲取到的路面點云規(guī)模龐大，在空間上分布密集。為明確需要執(zhí)行簡化算法的點云數(shù)據(jù)的各項特點，文中將給出實驗環(huán)境下路面點云的相關參數(shù)，具體參數(shù)設置見表1。并且，對于每條掃描線上的點數(shù)，還將滿足如下公式：

其中，n為激光傳感器數(shù)量;FOV為橫向測量寬度;R為橫向采樣的間隔。根據(jù)表1中的參數(shù)和公式（1），計算得到每條掃描線的點數(shù)D為1 627。

在此基礎上，研究推得設備每秒采集到的總點數(shù)S為：

其中，Di為每個激光傳感器采集到的點數(shù)，f為每秒鐘掃描頻率。

根據(jù)式（1）、（2）計算得到車載系統(tǒng)每秒采集到的總點數(shù)S為3 254 000個。而如此可觀規(guī)模的點云數(shù)據(jù)則意味著后期建模時的大量時間消耗。但經(jīng)由分析可知在這些點中，有相當一部分點對于生成路面的三角網(wǎng)模型卻是冗余的。

因此，為了提高系統(tǒng)的建模速度，必須對點云數(shù)據(jù)進行簡化操作。在簡化后的特征點云上建模不但可以節(jié)省時間，也能使得路面三角剖分模型中各個三角形形態(tài)更趨標準，避免產(chǎn)生過小三角形或狹長三角形來導致模型精度走低。設計簡化算法的預期目標是在保留點云特征點的同時，還能大幅度減少冗余點數(shù)量。

2.1 串行算法流程

分析本文研究場景下點云分布特點，可得其直觀表征是全部點云都是離散分布在逐條等距的掃描線上的，這樣就使得對每條掃描線點云進行簡化就可以得到全部點云的簡化。而對于分布在一條掃描線上的點之間，利用相鄰點間的斜率差關系可以衡量每個點對于描述路面特征的重要性，即與左、右點間線段斜率差大的可以判定為是特征點將其保留，斜率差小的點則視為連續(xù)的平整路面點進行簡化。同時為了不把連續(xù)平整路面的點全部簡化去掉，導致特征點云出現(xiàn)空洞，可設定固定步長值用來保證能在平整的掃描線片段上取到一定數(shù)量的點。這里，針對掃描線上相鄰點間斜率差關系的示意則如圖1所示。

對于每組點間的斜率差Δ而言，發(fā)生變動的只有式（4）中的分子部分?；谛甭什畹乃惴ú⒉恍枰獪蚀_的斜率差值，而是不同組點斜率差變化的程度與閾值的關系，因此在算法實現(xiàn)時對其做出簡化處理，以式（4）分子部分代替斜率差。

綜上論述分析，研究中采用的基于斜率差的掃描線點云簡化算法的設計步驟可分述如下：

輸入：原始點云數(shù)據(jù)

輸出：簡化后的特征點云數(shù)據(jù)

Step1 設定斜率差閾值η，確定需要保留點的步長M。

Step2 從第一個點開始，指針P1，P2，P3分別指向3個連續(xù)的點。

Step3 計算Δ=z3-2z2+z1，其中z1，z2，z3分別是P1，P2，P3的高程坐標，設定計數(shù)器N值為0。

Step4 如果Δ<η，刪除點P2，并把計數(shù)器N加一。

Step5 如果Δ≥η，或者計算器N 等于步長 M，則保留P2，并把計數(shù)器N清零。

Step6 判斷所有點是否已處理完畢。若是，則當前掃描線已結束簡化，可轉入處理下一條掃描線數(shù)據(jù);否則將P1，P2，P3向后移動一個點的距離，再跳至Step3。

2.2 利用多核CPU的點云簡化算法并行加速

分析實際應用場景中點云的采集和存儲模式，發(fā)現(xiàn)在y軸方向上看，點云是被等距分成逐條掃描線進行保存的。也就是說，同一條掃描線上的點云數(shù)據(jù)，其y坐標是一樣的，x坐標均勻變化布滿整條掃描線長度。同步處理不同掃描線點云并不會引起訪存沖突。與此同時，再次考慮到前述簡化算法是逐掃描線執(zhí)行的，那么采用并行方法一次處理多條掃描線點云將會有效提高修補算法的運行速度。設計的并行算法借助OpenMP來研發(fā)實現(xiàn)，采用動態(tài)調度機制將計算任務迭代分配到各個線程，保證計算任務在各線程間做到均勻分布。而在各線程內部，對調度分配輸送的掃描線點云數(shù)據(jù)依然執(zhí)行2.1節(jié)中的串行簡化算法?？芍苯釉谠键c云數(shù)據(jù)各條掃描線上進行簡化，并不需要引入并行后的合并操作。因此采用并行方法一次簡化多條掃描線點云，就可有效提高簡化算法的執(zhí)行速度。

以使用4核CPU的4線程執(zhí)行為例，此時并行執(zhí)行模式為同時做4條掃描線點云的簡化，其并行簡化算法的設計流程如圖2所示。

2.3 利用GPU的點云簡化算法并行加速

在GPU上進行算法的并行加速，主要是依托CUDA編程框架。CUDA是一種利用GPU解決復雜計算問題的并行計算架構。經(jīng)由分析探得，一個完整的CUDA程序是由一系列的運行于GPU上的Kernel函數(shù)和運行于主機CPU端的串行處理步驟共同構建而成，因此利用GPU并不只是單純使用GPU，而是一種CPU和GPU的異構計算模型。其中，CPU端的串行代碼的研究包括在Kernel啟動前預籌的數(shù)據(jù)準備、設備初始化以及在Kernel之間定制的一部分串行化計算。適用于CUDA框架的問題需要具備重復性計算多、分支判斷少的特點，而本課題面向的大規(guī)模掃描線點云簡化顯然能夠符合這些要求。

設計時，CUDA程序需要包含6個步驟，設計內容詳見如下。

（1）初始化GPU設備Device。

（2）輸入數(shù)據(jù)。

（3）復制數(shù)據(jù)到Device數(shù)據(jù)，需要提前分配好空間。

（4）執(zhí)行Kernel核函數(shù)。

（5）復制得到的結果到Host內存。

（6）釋放掉申請的Device內存。

這里由于各條掃描線點云作為輸入數(shù)據(jù)是相互獨立的，可以直接利用這一點進行計算任務的分解。具體是在每一個GPU運算單元上執(zhí)行相同的Kernel核函數(shù)，而每個Kernel核函數(shù)的輸入數(shù)據(jù)都是不同的掃描線數(shù)據(jù)。并且研究中，在CUDA框架里，CPU端被稱為主機Host，GPU端被稱為設備Device。在完整的CUDA程序中，涉及到Host和Device兩邊的不同操作，同時也要考慮到數(shù)據(jù)搬運產(chǎn)生的額外時間消耗。

根據(jù)上述對CUDA框架下研發(fā)算法的相關分析，基于本文簡化算法設計的利用GPU的點云簡化算法的框架流程將如圖3所示。

其中，Kernel核函數(shù)即為執(zhí)行一條掃描線點云簡化算法的改寫。由于GPU不支持動態(tài)的數(shù)據(jù)結構，就使得在初始化設備Device時，要根據(jù)輸入數(shù)據(jù)的大小提前分配存儲空間，再結合上述對本文實驗場景下的掃描線點云分析，可知每條掃描線是定長的，即初始點數(shù)固定為1 627個，那么根據(jù)CUDA框架的Grid×Block×Thread三層線程編制模式，設計得到的Device端線程組織形式如圖4所示。

這里CUDA的線程組織使用的是二維形式，即圖4中Thread1在編程被調用時的序號為（0，0）。另外，GPU的stream multiprocessor在執(zhí)行時，會把32個thread合成一個稱作wrap線程數(shù)的單位進行統(tǒng)一調度，因此，設計的block內線程數(shù)為wrap大小的2倍，這樣既滿足了計算要求，也可使硬件并行效率達到了最小化。

3 實驗結果與分析

實驗的硬件環(huán)境為四核Intel（R） Core i5-5200U處理器，8 G內存;操作系統(tǒng)為Windows 7 64位。使用的GPU為Nvidia GeForce 940M。

在激光掃描儀采集到的實際點云數(shù)據(jù)上進行測試，結果如圖5所示。圖5（a）是實驗采集到的原始路面點云分布。圖5（b）為執(zhí)行簡化算法后的結果，由此可以看到在保留路面特征的基礎上，簡化了大部分冗余點云。

接下來，就將進行算法性能測試，選取從1萬到200萬規(guī)模的掃描線點云數(shù)據(jù)各10組，分別運行串行簡化算法、利用多核CPU的并行簡化算法和利用GPU的并行簡化算法，記錄平均時間消耗，運算結果數(shù)據(jù)參見表2。

由表2可知，其中的點集規(guī)模變化呈倍數(shù)增長，便于直觀比較隨此變化而帶來的不同時間消耗。根據(jù)下文的運算公式（5）及表2實驗數(shù)據(jù)繪制得到的算法性能折線則如圖6所示。

分析圖6可知，在點云簡化問題上利用多核CPU的并行加速也可獲得有限的加速效果，而相比串行算法而言，在點云規(guī)模增大時則基本保持著一倍左右的時間效率提升。

另外，在點集規(guī)模很小的時候，使用多線程并行來加速并不能達到加速效果，反而因為增加了線程切換等開銷而增加了時間消耗。只有當點集擴大到類似百萬這樣的規(guī)模時，才可真正體現(xiàn)出這樣的加速效果。但使用4核也只能達到略大于2的加速比，與理想狀態(tài)下的線性加速比4尚有一定距離。所以利用多核CPU的并行加速可以取得一定范圍內的漲幅和加速，但難以達到很好的加速效果。

在同樣的實驗點云數(shù)據(jù)上，又測試了利用GPU的并行簡化算法在各個規(guī)模點云上平均時間消耗，發(fā)現(xiàn)不僅是與串行算法相比取得了很好的加速效果，與利用多核CPU的并行簡化算法之間比較也呈現(xiàn)出很高的速度提升。為了更直觀比較2種并行算法加速效果，引入公式（5），可將其寫作如下形式：

根據(jù)公式（5）及表2中的實驗數(shù)據(jù)，繪制2種并行算法的加速比隨點云規(guī)模變化的柱形圖可如圖7所示。

分析圖7可知，除了在小規(guī)模點集上加速效果表現(xiàn)平平外，在擴大點集規(guī)模后，利用GPU的并行算法的加速比S有了顯著提高。在模擬實驗用到最大規(guī)模、即200萬點的點集里，S超過了100。體現(xiàn)在時間消耗上就是相當于將耗時超過0.3 s的操作加速到耗時約0.003 s。由于實際要處理的點集是每秒掃描得到325萬多點，一段路面在文件形式上可能會是TB大小數(shù)量級的離散數(shù)據(jù)文件。這樣的加速效果就給后續(xù)的路面三角網(wǎng)模型構建省下許多時間。

特別地，點集規(guī)模不需要特別大的情況下，并行加速取得的加速比S就已十分明顯，且隨著點集規(guī)模擴大，S增加的幅度也在逐漸加大。究其原因在于前期設定的定長掃描線點數(shù)，使得點集規(guī)模擴大，加入計算的GPU運算單元數(shù)量就越多，同時再加上算法本身的特點，這些運算單元之間都是充分并行的，因此就取得了最終可觀的加速比。在本文應用場景下，可以直接用激光傳感器獲得的每條線1 627點作為定長進行CUDA線程編制的設計（可見2.3節(jié)圖4）。而對于其它同類型的掃描線點云，則可以根據(jù)每條線上的點數(shù)設計實驗環(huán)境的顯卡最為適宜的線程組織形式。

4 結束語

本文在研究掃描線點云簡化算法的基礎上，根據(jù)算法結構對可并行部分輔以并行處理，分別使用基于多核CPU的并行和基于GPU的并行兩種模式，提高了算法執(zhí)行效率。同時又提供了實際路面點云上的實驗分析，上述2種并行算法分別對比串行算法取得了一定的加速效果。其中，利用GPU的并行模式在大規(guī)模點云上得到了100左右的加速比。比較時間效率可知，對于掃描線點云簡化這類重復計算量很大、但分支判斷很少的問題，應用GPU進行并行優(yōu)化可以取得相當高的加速比。綜上研究可知，通過設計并行的簡化算法，在正確保留足夠多的特征點的基礎上，大幅減少了時間消耗，而且也為后續(xù)路面三角網(wǎng)構建和缺陷識別等操作節(jié)省了時間。

參考文獻

[1]SHI Baoquan， LIANG Jin， LIU Qing. Adaptive simplification of point cloud using k-means clustering[J]. Computer-Aided Design， 2011， 43（8）：910-922.

[2]XIAO Zhaoxia， HUANG Wenming. Kd-tree based nonuniform simplification of 3D point cloud[C]// 2009 Third International Conference on Genetic and Evolutionary Computing. Guilin， China：IEEE， 2009：339-342.

[3]袁小翠， 吳祿慎， 陳華偉. 特征保持點云數(shù)據(jù)精簡[J]. 光學精密工程， 2015， 23（9）：2666-2676.

[4]MOENNING C， DODGSON N A. A new point cloud simplification algorithm[C]// 3rd IASTED International Conference on Visualization，Imaging， and Image Processing. Spain：ACTA press， 2003：1027-1033.

[5]朱煜， 康寶生， 李洪安，等. 一種改進的點云數(shù)據(jù)精簡方法[J]. 計算機應用， 2012， 32（2）：521-523，544.

[6]SONG Hao， FENG H Y. A progressive point cloud simplification algorithm with preserved sharp edge data[J].The International Journal of Advanced Manufacturing Technology， 2009， 45（5-6）：583-592.

[7]曹毓， 馮瑩， 楊云濤，等. RANSAC直線估計方法在路面三維點云優(yōu)化中的應用[J]. 紅外與激光工程， 2012， 41（11）：3108-3112.

[8]劉如飛， 王鵬. 保留路面特征的車載激光點云非均勻壓縮方法[J]. 遙感信息， 2017， 32（1）：100-103.

[9]WANG Gefang， LV Yanmei， HAN Ning， et al. Simplification method and application of 3D laser scan point cloud data[C]// Proceedings of the 1st International Conference on Mechanical Engineering and Material Science.Shanghai，China：Atlantis press，2012：266-268.

[10]GUO J， LIU J Y， ZHANG Y L， et al. Filtering of ground point cloud based on scanning line and self-adaptive angle-limitation algorithm[J]. Journal of Computer Applications， 2011， 31（8）：2243-2245.