李運川,王曉紅,陳思吉,葛義攀,李 闖

(1.貴州大學(xué)礦業(yè)學(xué)院,貴州 貴陽 550025; 2.貴州大學(xué)林學(xué)院,貴州 貴陽 550025)

0 引 言

點云配準(zhǔn)是指將不同視角獲取的同一物體點云數(shù)據(jù)變換到統(tǒng)一坐標(biāo)系的過程[1]，該技術(shù)在三維重建[2]、逆向工程[3]、文物保護[4]、地質(zhì)災(zāi)害[5]、無人駕駛[6]等領(lǐng)域具有廣泛應(yīng)用。為了解決點云配準(zhǔn)問題，國內(nèi)外研究者提出了多種算法[7-8]。其中，具有代表性的算法有采樣一致性初始配準(zhǔn)算法(Sample Consensus Initial Aligment, SAC-IA)[9]、四點快速匹配算法(4-Points Fast Matching Aligment, 4PCS)[10]、迭代最近點算法(Iterative Closest Point, ICP)[11-14]和正態(tài)分布變換算法(Normal Distributions Transform, NDT)[15-17]等。

同時，針對點云配準(zhǔn)算法存在錯誤匹配點對、精度不高等不足，國內(nèi)外研究者實現(xiàn)了多種改進算法。陳學(xué)偉等人[18]利用采樣一致性初始配準(zhǔn)算法(SAC-IA)實現(xiàn)兩點云的粗配準(zhǔn)，然后利用KD樹加速查找對應(yīng)點對，并使用方向向量閾值去除錯誤對應(yīng)點對，以此改進ICP算法，從而實現(xiàn)精配準(zhǔn)。實驗表明該算法具有相對較好的配準(zhǔn)精度和收斂速度。王宗躍等人[19]提出了基于多核CPU的海量點云并行K近鄰算法，該算法利用多核CPU的多線程并行特性，提高了K鄰近搜索速度。張蕾等人[20]提出了一種基于距離約束改進的ICP算法，該算法利用鄰近點法來獲取配準(zhǔn)點，并使用這些配準(zhǔn)點的重心作為參照點，求取各個配準(zhǔn)點到配準(zhǔn)點重心之間的距離，再結(jié)合點對距離約束來剔除錯誤配準(zhǔn)點對，最后，進行點云配準(zhǔn)。該算法在配準(zhǔn)速度和精度方面均有所提高。鐘瑩等人[21]在匹配點對集中，通過增加閾值來降低噪聲對配準(zhǔn)的影響，并對點與點之間的方向向量夾角設(shè)定閾值，從而達到提高配準(zhǔn)精度、剔除錯誤匹配點對的目的。

針對點云配準(zhǔn)中存在錯誤匹配點對、精度不高等問題，本文采用基于OpenMP的多核并行技術(shù)[22-23]來提升配準(zhǔn)算法速度，并引入動態(tài)閾值和配準(zhǔn)點重心約束來剔除錯誤匹配點對，以此來提升配準(zhǔn)精度，從而完成點云配準(zhǔn)。通過對ICP、SAC-IA+ICP算法和本文算法進行點云配準(zhǔn)實驗，并從算法速度、精度等方面進行對比分析，來驗證本文算法的可行性。

1 本文點云配準(zhǔn)算法的流程

本文的點云配準(zhǔn)算法包括2個過程：粗配準(zhǔn)和精配準(zhǔn)。在粗配準(zhǔn)階段，首先進行點云下采樣，然后利用基于OpenMP的多核并行技術(shù)，來計算點云查詢點的法向量、FPFH特征，以及并行查找對應(yīng)點對，最后計算出粗配準(zhǔn)變換參數(shù)，從而實現(xiàn)粗配準(zhǔn)。精配準(zhǔn)采用改進的ICP算法逐步獲取最佳配準(zhǔn)結(jié)果。本文點云配準(zhǔn)算法的流程如圖1所示。

圖1 本文點云配準(zhǔn)算法的流程

2 粗配準(zhǔn)算法

本文采用改進的SAC-IA算法進行點云粗配準(zhǔn)，改進點主要體現(xiàn)在利用OpenMP并行加速提取點云查詢點的法向量、FPFH等特征，以及對對應(yīng)點對的并行查找。

2.1 基于OpenMP加速特征提取

在利用SAC-IA算法進行粗配準(zhǔn)時，提取點云查詢點的法向量、FPFH等特征以及查找對應(yīng)點對的時候，各查詢點的相關(guān)計算存在時間復(fù)雜度高的問題，尤其在查找對應(yīng)點對時花費了粗配準(zhǔn)的大部分時間，而利用OpenMP的多核并行優(yōu)勢，正好可以解決時間復(fù)雜度高的問題。此外，各點云查詢點的特征提取是相互獨立的，可以同時進行，這與OpenMP的多核并行特性不謀而合。

通過上述分析，本文利用OpenMP來實現(xiàn)SAC-IA算法中所涉及的點云查詢點的法向量、FPFH等特征提取，以及對應(yīng)點對的查找這3個部分的并行加速處理，從而提升粗配準(zhǔn)算法的速度。其具體過程如下所示，并且可以用圖2清晰地表示其流程。

1)第1個并行域?qū)崿F(xiàn)點云查詢點的法向量的并行加速提取，由于每個點云查詢點的法向量計算是相互獨立的，可以利用多核多線程并行加速提取法向量特征。

2)在第2個并行域中，基于步驟1求得的法向量特征信息，對點云查詢點的FPFH特征進行并行加速提取，由于每個點云查詢點的FPFH計算相互獨立，因此每個線程負責(zé)并行加速提取FPFH特征。

3)基于前2個步驟提取的法向量、FPFH特征信息，在第3個并行域中，實現(xiàn)對應(yīng)點對的并行加速查找，由于對應(yīng)點對查找中存在多個可以并行的循環(huán)操作，這正好可以利用OpenMP來并行加速這些循環(huán)操作。

圖2 基于OpenMP加速特征提取

2.2 改進的SAC-IA算法

本文采用OpenMP來改進SAC-IA算法，以此改進算法加速計算源點云P和目標(biāo)點云Q的粗配準(zhǔn)變換參數(shù)。本文改進的SAC-IA算法的主要步驟包括：點云下采樣、基于OpenMP實現(xiàn)點云查詢點的法向量和FPFH特征的并行加速提取、基于OpenMP并行加速查找對應(yīng)點對、計算粗配準(zhǔn)變換參數(shù)R、T，其大致思路如下：

Step1對點云進行下采樣，并基于OpenMP并行加速提取點云查詢點的法向量、FPFH等特征；從源點云P中選取N個樣本點，為了盡量保證所選的樣本點具有不同的FPFH特征，樣本點兩兩之間的距離應(yīng)大于預(yù)先給定的最小距離閾值dmin。

Step2基于OpenMP并行加速查找對應(yīng)點對，在目標(biāo)點云Q中查找與源點云P中所選樣本點具有相同或相似FPFH特征的一個或多個點，從這些點中隨機選取一個點作為源點云P在目標(biāo)點云中的匹配點，從而獲得N對匹配點對。

Step3計算Step2所獲得的N對匹配點對之間的剛體變換參數(shù),然后通過求解匹配點變換后的距離誤差和函數(shù)L(li)來判斷當(dāng)前剛體變換參數(shù)的性能；此處的距離誤差和函數(shù)L(li)多使用Huber罰函數(shù)表示，其公式如式(1)和式(2)所示：

(1)

(2)

其中，ml為預(yù)先給定值，li為第i組匹配點變換之后的距離差。

Step4重復(fù)Step1～Step3，并對比所有的剛體變換參數(shù)，使得距離誤差和函數(shù)L(li)的值最小，從中找到一組最優(yōu)粗配準(zhǔn)變換參數(shù)R、T。

Step5利用Step4獲得的最優(yōu)粗配準(zhǔn)變換參數(shù)R、T，將源點云P配準(zhǔn)到目標(biāo)點云Q，獲得新的點云P。

3 精配準(zhǔn)算法

在第2章中實現(xiàn)了點云粗配準(zhǔn)，這就為當(dāng)前的精配準(zhǔn)提供了較好的初始姿態(tài)。接下來，將采用一種改進的ICP算法來實現(xiàn)點云精配準(zhǔn)，即在ICP算法的基礎(chǔ)上引入配準(zhǔn)點重心約束和動態(tài)閾值來剔除錯誤對應(yīng)點對，從而獲得更高的配準(zhǔn)精度和更好的配準(zhǔn)效果。

3.1 配準(zhǔn)點重心約束

由于在點云數(shù)據(jù)的采集過程中不可避免地摻有噪聲，且點云數(shù)據(jù)重疊區(qū)域的拓撲結(jié)構(gòu)并不是完全一致的，因此，在確定初始匹配點對的時候，往往存在一對多或錯誤對應(yīng)的情況，這會使得點云配準(zhǔn)的精度降低或者無法配準(zhǔn)。為此，本文以“配準(zhǔn)點重心”(按式(3)計算)為參照點，計算初始匹配點對與配準(zhǔn)點重心的距離差值，若距離差值大于設(shè)定的動態(tài)閾值，則視為錯誤匹配點對，予以剔除；反之，則保留為正確匹配點對，以此實現(xiàn)錯誤匹配點對的剔除，公式如式(4)所示：

(3)

(4)

3.2 動態(tài)閾值

通過文獻分析，本文發(fā)現(xiàn)剔除錯誤匹配點對時所用的閾值是固定閾值，而固定閾值法的缺陷在于固定閾值不夠靈活，它只適用于某個點云模型配準(zhǔn)，適應(yīng)性較差，對于多種點云模型時，這會導(dǎo)致誤剔除率增大。對此，本文以動態(tài)閾值作為約束條件，當(dāng)參與配準(zhǔn)的點云模型發(fā)生變化或ICP算法不斷迭代時，閾值也會自動變化進行適配，從而更好地剔除錯誤匹配點對。動態(tài)閾值法的具體原理如下：

Step1按照公式(5)計算初始匹配點對集中的各對匹配點到各自的配準(zhǔn)點重心的距離。

(5)

其中，ai和bi為源點云和目標(biāo)點云中第i個對應(yīng)點到配準(zhǔn)點重心的距離，N為初始匹配點對集中匹配點對的數(shù)目。

Step2按照公式(6)計算各對匹配點到各自的配準(zhǔn)點重心的距離的差值，以及該距離差值的平均值。

(6)

Step3利用公式(7)和公式(8)計算各對匹配點到各自的配準(zhǔn)點重心的距離的差值的中誤差。

(7)

(8)

其中，m為各對匹配點到各自的配準(zhǔn)點重心的距離的差值的中誤差，N為初始匹配點對數(shù)目。

Step4設(shè)定閾值。通過實驗可以發(fā)現(xiàn)：先采用測量中通用的2m為閾值，將2m作為閾值時，僅剔除了較少的錯誤匹配點對，收斂速度也無明顯增加；而閾值設(shè)置為1.5m時,剔除了較多錯誤匹配點對，收斂速度得到一定的提高；故設(shè)定1.5m為閾值。

3.3 改進的ICP算法

源點云為P，目標(biāo)點云為Q。改進的ICP算法步驟如下：

Step1對原始點云進行下采樣。利用VoxelGrid濾波器對源點云P和目標(biāo)點云Q進行下采樣，獲得精簡后的源點云P和目標(biāo)點云Q。

Step2確定初始對應(yīng)點對集。對精簡后的源點云P中的每一個點，按照歐氏距離最近的原則，在目標(biāo)點云Q中用KD樹加速查找對應(yīng)點，從而得到初始對應(yīng)點對集。

Step3計算配準(zhǔn)點重心。對初始對應(yīng)點對集，分別計算源點云P和目標(biāo)點云Q的配準(zhǔn)點重心。

Step4剔除錯誤對應(yīng)點對。利用“配準(zhǔn)點重心約束”剔除錯誤對應(yīng)點對，得到正確對應(yīng)點對集。

Step5求解剛體變換矩陣。在Step4所獲得的正確對應(yīng)點對集上，使用奇異值分解法求得使目標(biāo)函數(shù)最小的剛體變換矩陣(R,T)，計算公式如式(9)：

(9)

其中，(pi,qi)是正確匹配點對集中的第i對匹配點對，N為正確匹配點對的數(shù)目。

Step6更新源點云。使用Step5得到的剛體變換矩陣R、T，將源點云P配準(zhǔn)到目標(biāo)點云Q，獲得新的源點云P；然后，重復(fù)Step2～Step6進行迭代計算，直到達到最大迭代次數(shù)、均方誤差MSE小于誤差閾值δ或者相鄰兩次變換矩陣差值小于所設(shè)閾值ε(見式(10))，則停止迭代，然后輸出最終剛體變換參數(shù)。

(10)

其中，pi為第k次迭代后的更新源點云Pk中的第i個點，qi為目標(biāo)點云Qk中的第i個點；N是正確匹配點對數(shù)目；MSEk是第k次迭代后目標(biāo)點云與更新源點云之間的平均距離平方和(即均方誤差)；MSEk-MSEk+1為2次迭代誤差。

Step7按照最終的剛體變換參數(shù)R、T，將源點云P配準(zhǔn)到目標(biāo)點云Q。

4 實驗與分析

4.1 實驗環(huán)境與數(shù)據(jù)

本實驗利用斯坦福大學(xué)3D模型庫數(shù)據(jù)進行實驗，實驗所采用的軟硬件環(huán)境為：3.40 GHz的AMD Ryzen 5 2600的CPU，8 GB內(nèi)存；64位的Windows10操作系統(tǒng)，以及Visual Studio 2017，并結(jié)合點云庫PCL1.9.1實現(xiàn)本文點云配準(zhǔn)算法。

4.2 點云配準(zhǔn)實驗

為了進行對比實驗，本文使用了馬、兔、頭像這3組點云數(shù)據(jù)。選擇這3組數(shù)據(jù)來完成本文實驗的原因有3點：1)該數(shù)據(jù)是點云配準(zhǔn)算法研究中的經(jīng)典數(shù)據(jù)，且適用于本文研究；2)該數(shù)據(jù)的數(shù)據(jù)量都在幾萬到十萬個點之間，可以用來驗證本文算法的速度性能；3)該數(shù)據(jù)沒有噪聲，可以用于人為添加噪聲來驗證算法的抗噪性。在具體實驗中，首先，采用本文點云粗配準(zhǔn)算法對點云數(shù)據(jù)進行粗配準(zhǔn)處理；然后，采用本文點云精配準(zhǔn)算法進行點云精配準(zhǔn)。同時，與ICP、SAC-IA+ICP算法進行對比實驗。圖3(a)是待配準(zhǔn)馬點云模型，圖3(b)、圖3(c)分別是ICP、SAC-IA+ICP算法配準(zhǔn)結(jié)果，圖3(d)是本文算法配準(zhǔn)結(jié)果。圖4(a)是待配準(zhǔn)兔點云模型，圖4(b)、圖4(c)分別是ICP、SAC-IA+ICP算法配準(zhǔn)結(jié)果，圖4(d)是本文算法配準(zhǔn)結(jié)果。圖5(a)是待配準(zhǔn)頭像點云模型，圖5(b)、圖5(c)分別是ICP、SAC-IA+ICP算法配準(zhǔn)結(jié)果，圖5(d)是本文算法配準(zhǔn)結(jié)果。

(a) 待配準(zhǔn)點云 (b) ICP (c) SAC-IA+ICP (d) 本文算法

(a) 待配準(zhǔn)點云 (b) ICP (c) SAC-IA+ICP (d) 本文算法

(a) 待配準(zhǔn)點云 (b) ICP (c) SAC-IA+ICP (d) 本文算法

4.3 實驗分析

4.3.1 配準(zhǔn)效果分析

由圖3(a)～圖5(a)可以直觀地發(fā)現(xiàn)待配準(zhǔn)的馬、兔、頭像點云數(shù)據(jù)的初始姿態(tài)存在明顯偏差；從圖3(b)～圖3(d)、圖4(b)～圖4(d)和圖5(b)～圖5(d)的配準(zhǔn)結(jié)果可以看出，對于初始姿態(tài)并不好的待配準(zhǔn)點云，相較于ICP、SAC-IA+ICP算法，本文算法實現(xiàn)了更好的配準(zhǔn)效果。

4.3.2 配準(zhǔn)精度分析

從表1可以看出，相較于ICP、SAC-IA+ICP算法，本文算法在進行馬、兔、頭像點云模型配準(zhǔn)時，在配準(zhǔn)速度提升的情況下，配準(zhǔn)精度也獲得了提升。與ICP算法相比，在馬、兔、頭像點云配準(zhǔn)中，本文算法配準(zhǔn)精度都至少提升了35%；與SAC-IA+ICP算法相比，在馬、兔、頭像點云配準(zhǔn)中，本文算法配準(zhǔn)精度分別提升了20%、3.5%和4.9%。本文算法之所以獲得配準(zhǔn)精度的提升，是由于在ICP算法中引入基于動態(tài)閾值的配準(zhǔn)點重心約束，從而剔除了錯誤匹配點對，使得因錯誤匹配點對的存在而引起配準(zhǔn)效果不佳的問題得到改善。

表1 配準(zhǔn)精度

4.3.3 配準(zhǔn)時間分析

從表2可以看出，與ICP、SAC-IA+ICP算法相比，本文算法在提升配準(zhǔn)精度的情況下，速度也得到了提升。相較于ICP算法，本文算法在進行馬、兔、頭像點云配準(zhǔn)時，配準(zhǔn)速度分別提升了12%、46%、17%；相較于SAC-IA+ICP算法，本文算法在進行馬、兔、頭像點云配準(zhǔn)時，配準(zhǔn)速度分別提升了6.9%、29%、12%。在配準(zhǔn)過程中，為了剔除ICP算法中的錯誤匹配點對，本文引入動態(tài)閾值的配準(zhǔn)點重心約束，這確實增加了單次迭代的耗時，但總的配準(zhǔn)耗時降低了。究其原因，一方面是由于迭代次數(shù)減少了，另一方面要歸功于利用OpenMP實現(xiàn)點云查詢點的法向量、FPFH等特征的并行加速提取以及對應(yīng)點對的并行查找，從而降低了算法耗時。此外，在整個算法中，對點云進行了精簡，這減少了配準(zhǔn)的計算量，同時加入了KD樹，這加快了對應(yīng)點的搜索速度，從而提升了本文配準(zhǔn)算法的速度。

表2 配準(zhǔn)時間

4.3.4 抗噪性分析

如圖6(a)所示，本文以兔點云為實驗對象，然后給其分別添加10%、20%、30%和40%的高斯噪聲，來驗證本文算法的抗噪性。圖6(b)和圖6(c)分別是SAC-IA+ICP和本文算法在帶有不同比例高斯噪聲下的配準(zhǔn)結(jié)果。通過表3可以看出，隨著高斯噪聲比例的增加，SAC-IA+ICP和本文算法的配準(zhǔn)精度都不斷上升，而且本文算法與SAC-IA+ICP算法的配準(zhǔn)精度能夠保持一致，這說明本文算法具有與SAC-IA+ICP算法相當(dāng)?shù)目乖胄浴?/p>

(a) 輸入數(shù)據(jù)

(b) SAC-IA+ICP算法

(c) 本文算法圖6 高斯噪聲下的點云配準(zhǔn)

表3 不同高斯噪聲比例下的配準(zhǔn)精度

5 結(jié)束語

點云配準(zhǔn)是三維重建、逆向工程、文物保護、計算機視覺、自動駕駛等領(lǐng)域的關(guān)鍵技術(shù)，點云配準(zhǔn)算法的配準(zhǔn)精度、速度會直接影響后續(xù)處理的質(zhì)量。針對點云配準(zhǔn)中存在錯誤對應(yīng)點對、精度不高等問題，在粗配準(zhǔn)階段，本文采用基于OpenMP的多核并行技術(shù)，來并行加速提取點云查詢點的法向量、FPFH等特征，以及對對應(yīng)點對的并行查找，從而提升了配準(zhǔn)過程的速度；在精配準(zhǔn)階段，引入基于動態(tài)閾值的配準(zhǔn)點重心約束，結(jié)合點對距離約束來剔除錯誤匹配點對，從而達到提升整個配準(zhǔn)算法精度的目的。實驗結(jié)果表明，相較于ICP、SAC-IA+ICP算法，本文算法在提升配準(zhǔn)精度的情況下，配準(zhǔn)速度也得到了提升；在抗噪性方面，本文算法具有與SAC-IA+ICP算法相當(dāng)?shù)目乖胄?。此外，本文算法的速度還具有提升空間，因此在下一步工作中，將考慮利用CUDA并行加速點云配準(zhǔn)算法，以此實現(xiàn)算法速度的更大提升。