孫大林 唐好選

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

關(guān)鍵詞：點(diǎn)云精簡(jiǎn);GPU并行計(jì)算;OpenMP

文章編號(hào)：2095-2163（2019）04-0307-06 中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

0 引 言

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

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

1 相關(guān)工作

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

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

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

2 算法概述

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

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

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

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

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

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

2.1 串行算法流程

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

對(duì)于每組點(diǎn)間的斜率差Δ而言，發(fā)生變動(dòng)的只有式（4）中的分子部分。基于斜率差的算法并不需要準(zhǔn)確的斜率差值，而是不同組點(diǎn)斜率差變化的程度與閾值的關(guān)系，因此在算法實(shí)現(xiàn)時(shí)對(duì)其做出簡(jiǎn)化處理，以式（4）分子部分代替斜率差。

綜上論述分析，研究中采用的基于斜率差的掃描線點(diǎn)云簡(jiǎn)化算法的設(shè)計(jì)步驟可分述如下：

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

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

Step1 設(shè)定斜率差閾值η，確定需要保留點(diǎn)的步長(zhǎng)M。

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

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

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

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

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

2.2 利用多核CPU的點(diǎn)云簡(jiǎn)化算法并行加速

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

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

2.3 利用GPU的點(diǎn)云簡(jiǎn)化算法并行加速

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

設(shè)計(jì)時(shí)，CUDA程序需要包含6個(gè)步驟，設(shè)計(jì)內(nèi)容詳見如下。

（1）初始化GPU設(shè)備Device。

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

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

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

（5）復(fù)制得到的結(jié)果到Host內(nèi)存。

（6）釋放掉申請(qǐng)的Device內(nèi)存。

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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]袁小翠， 吳祿慎， 陳華偉. 特征保持點(diǎn)云數(shù)據(jù)精簡(jiǎn)[J]. 光學(xué)精密工程， 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]朱煜， 康寶生， 李洪安，等. 一種改進(jìn)的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法[J]. 計(jì)算機(jī)應(yīng)用， 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直線估計(jì)方法在路面三維點(diǎn)云優(yōu)化中的應(yīng)用[J]. 紅外與激光工程， 2012， 41（11）：3108-3112.

[8]劉如飛， 王鵬. 保留路面特征的車載激光點(diǎn)云非均勻壓縮方法[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.