朱錦杰

(山東省地質(zhì)礦產(chǎn)勘查開發(fā)局八○一水文地質(zhì)工程地質(zhì)大隊,山東 濟南 250014)

0 引言

伴隨著科學(xué)技術(shù)的發(fā)展,新的測繪技術(shù)也在慢慢崛起。其中,三維激光掃描儀的誕生為推動測繪朝著高新技術(shù)發(fā)展做出了貢獻(xiàn)。三維激光掃描儀通過無接觸式測量,獲取大量具有三維坐標(biāo)信息的點云數(shù)據(jù),通過配準(zhǔn)匹配構(gòu)建三維點云模型,從而實現(xiàn)被測物體三維展示[1-5]。其中關(guān)鍵技術(shù)是點云如何實現(xiàn)高精度匹配配準(zhǔn),形成表面無噪點的點云模型,這是制約著點云模型大規(guī)模應(yīng)用的一道障礙。關(guān)于配準(zhǔn)算法的研究國內(nèi)外專家學(xué)者做過深入分析探討,常規(guī)模型如全局搜索思想的配準(zhǔn)方法,隨機抽樣一致(random sample consensus,RANSAC)點云配準(zhǔn)算法,主方向貼合算法,最近點迭代(iterative closest point,ICP)算法等。常規(guī)一種算法難以滿足點云配準(zhǔn)的要求,可將多種算法綜合各自優(yōu)點實現(xiàn)高精度配準(zhǔn),如文獻(xiàn)[2]中提及利用向量夾角提取特征點后通過快速點特征直方圖(fast point feature histograms,FPFH)描述特征點,并在ICP算法中加入KD-tree完成最終配準(zhǔn);文獻(xiàn)[3]在ICP算法中利用二次搜索求出最近距離,提高傳統(tǒng)ICP算法的效率;文獻(xiàn)[4]中涉及在主成分分析法(principal component analysis,PCA)的基礎(chǔ)上完成初始配準(zhǔn),但PCA算法要求待配準(zhǔn)點云有較高的重疊度;綜合已有研究資料表明配準(zhǔn)過程一般包括兩個步驟,粗配準(zhǔn)與精配準(zhǔn)。本文在研究了多種配準(zhǔn)算法之后,嘗試將主方向貼合算法與改進的ICP算法組合。將主方向貼合算法作為粗配準(zhǔn),得到粗配準(zhǔn)之后的點云數(shù)據(jù);利用改進的ICP算法作為精配準(zhǔn),最終實現(xiàn)點云三維模型的精確構(gòu)建。以某三維激光掃描建模工程為例,通過外業(yè)獲取的點云數(shù)據(jù),經(jīng)過粗配準(zhǔn)與精配準(zhǔn)兩個過程,實現(xiàn)了三維模型的構(gòu)建,同時驗證該組合方法在點云配準(zhǔn)方面的有效性。

1 配準(zhǔn)算法原理

1.1 主方向貼合算法

該算法的基本思想是解算每個點的特征向量,特征向量中有兩個成正交的分矩陣。這兩個矩陣能夠描述該點的主要位置信息,并能夠保存主要信息以簡化點云描述部分不對稱存在[12-13]。為了提高主方向貼合算法的配準(zhǔn)效果,在算法運行前先粗略地針對兩站點云進行粗處理,剔除噪聲點云并將重疊區(qū)域進行提取,其目的是為了提高點云的配準(zhǔn)精度與效果。

1.2 最近點迭代算法

ICP算法經(jīng)過這幾十年的發(fā)展已日趨成熟,特別是國內(nèi)外學(xué)者針對該算法提出了不同的改進算法。但是該算法使用起來還具有一定的局限性,如點云的重疊率較高,噪點點云數(shù)據(jù)不能太多。否則配準(zhǔn)的點云效果較差,優(yōu)勢不明顯[14]。這就需要在利用ICP算法之前,使用粗配準(zhǔn)算法將點云數(shù)據(jù)粗略配準(zhǔn)。上文中提及的主方向貼合算法的粗配準(zhǔn)能夠作為ICP算法的輸入數(shù)據(jù)。從而充分發(fā)揮ICP算法的優(yōu)勢實現(xiàn)點云模型的精確配準(zhǔn)。國外專家Besl等人提出了該算法無需控制點即可實現(xiàn)點云的配準(zhǔn),每一次迭代過程中都會重新計算迭代誤差,直至迭代差值小于某一閾值。當(dāng)這一數(shù)據(jù)值滿足要求時,迭代結(jié)束,并且此時的特征向量及坐標(biāo)轉(zhuǎn)換配準(zhǔn)參數(shù)是唯一解[15]。

針對數(shù)據(jù)點云X,這其中包括該數(shù)據(jù)集中計算的對應(yīng)點云,利用ICP算法構(gòu)成目標(biāo)點云集合Yk。該過程就是ICP算法的核心思想,以下為描述該計算的主要過程

Yk=C(X,Y)

(1)

利用四元數(shù)算法Sysf估算點云集合X、Yk,計算出配準(zhǔn)參數(shù)如式(2)所示。

(H,d)=Sysf(X,Yk)

(2)

通過變換矩陣H將點云集合X中每個數(shù)據(jù)點旋轉(zhuǎn)平移變換,如式(3)所示:

H(X)=R(X)+T

(3)

式(1)～式(3)為經(jīng)典ICP算法的主要流程,該算法搜尋最近點并不斷逼近最佳值,通過四元數(shù)算法獲取參考點云與目標(biāo)點云之間的配準(zhǔn)參數(shù)。

假設(shè)目標(biāo)數(shù)據(jù)和參考數(shù)據(jù)分別為X、Y,其迭代的步驟如下:

1)尋找最近點。由公式Y(jié)k=C(X,Y)對點云數(shù)X中的每個數(shù)據(jù)點,計算其在點云數(shù)據(jù)Y中的最近點,構(gòu)成點集Yk。

3)更新數(shù)據(jù)集。由公式H(X)=R(X)+T,利用變換矩陣H對數(shù)據(jù)集X進行更新[10]。

ICP算法還需要滿足的要求是對于兩個數(shù)據(jù)集,其中一個數(shù)據(jù)是另一個數(shù)據(jù)的嚴(yán)格子集,那么才能夠使得兩個待配準(zhǔn)的點云數(shù)據(jù)總體上在某一種度量準(zhǔn)則下達(dá)到最佳配準(zhǔn)。在進行三維數(shù)據(jù)掃描時,無法一次性的獲取物體表面的全部點云數(shù)據(jù),往往要從不同的角度下采集物體的局部數(shù)據(jù),這些數(shù)據(jù)僅僅是部分相互重疊的,所以,ICP算法得到的結(jié)果可能不會是全局最優(yōu)化,這就需要對迭代初始相對位置的要求較高,不能夠與真實的位置相差過大。

1.3 改進的ICP算法

經(jīng)典ICP算法如上文介紹實現(xiàn)流程,以歐式距離為限制條件搜尋源點云P中的某個點pi在目標(biāo)點云Q中的對應(yīng)點qi,并將對應(yīng)點計算的旋轉(zhuǎn)矩陣R與平移矩陣T,使得按照式(4)計算的誤差最小。

(4)

式中E(R,T)為誤差函數(shù)。

按照式(4)的計算方式將目標(biāo)點云與源點云所有數(shù)據(jù)參與計算,但存在噪點導(dǎo)致計算效率降低。為此在傳統(tǒng)ICP算法基礎(chǔ)之上,加入法向量夾角閾值刪除未參加配準(zhǔn)的噪點,來優(yōu)化算法的執(zhí)行效率。流程如下:

1)經(jīng)過主方向貼合算法粗配準(zhǔn)之后的源點云為P′,目標(biāo)點云集合為Q′,分別計算出每個點的法向量。

2)針對P′中的每個點在Q′中查找對應(yīng)的歐氏距離最近點,記為點對N,隨后設(shè)置法向量閾值為fθ,假如N的法向量夾角小于閾值,保留該點對,否則視為匹配失敗點對,將其剔除,剔除的點對記為N′。

3)根據(jù)點對集合N′利用奇異值分級法計算變換矩陣(R、T),并根據(jù)誤差函數(shù)E(R,T)求出最優(yōu)的變換旋轉(zhuǎn)矩陣。

2 實驗驗證

文中評定最終配準(zhǔn)結(jié)果精度采用均方根誤差(RMSE),其計算公式為

(5)

其中,pj與qj分別表示目標(biāo)源點與目標(biāo)點中對應(yīng)點;n表示對應(yīng)點數(shù)量。

2.1 實驗一

2.1.1粗配準(zhǔn)

本文采用了主方向貼合法對點云數(shù)據(jù)進行粗配準(zhǔn),算法驗證所采用的數(shù)據(jù)格式為asc,數(shù)據(jù)來自某數(shù)據(jù)庫中的標(biāo)準(zhǔn)參考格式數(shù)據(jù),目標(biāo)點云數(shù)量為39 910個,參考點云數(shù)據(jù)量為39 930個。

由圖1配準(zhǔn)前的點云數(shù)據(jù)可知,目標(biāo)點云與參考點云二者之間重疊率較高,無須進行預(yù)處理可對點云數(shù)據(jù)求解特征向量與特征值的計算。利用MATLAB軟件編程實現(xiàn)主方向貼合算法,在編程實現(xiàn)過程中發(fā)現(xiàn)該算法思想簡單易于實現(xiàn)。最終通過程序?qū)崿F(xiàn)了主方向貼合算法,雖然數(shù)據(jù)量較大,但過程僅花費0.084 878 s,再次印證了該算法易于實現(xiàn)且較簡單的優(yōu)點。

(a)二維顯示

(a)二維顯示

主方向貼合法不同于RANSAC配準(zhǔn)算法中要求點云數(shù)據(jù)中點的數(shù)量必須相同,它是對點云數(shù)據(jù)分別計算的,所以可以對不同大小的點云數(shù)據(jù)進行計算。

雖然主方向貼合法有上述種種優(yōu)點,但是該算法的缺點也非常的明顯。如該算法在配準(zhǔn)之前,要求原始點云數(shù)據(jù)具有較大的重疊率,如重疊率較小則無法實現(xiàn)配準(zhǔn)。且該算法受噪點影響也較大,時常配準(zhǔn)效果不明顯,精度較差。必須在配準(zhǔn)之前去噪,本小節(jié)采用的標(biāo)準(zhǔn)庫中的點云數(shù)據(jù),是經(jīng)過去噪之后處理,所以在算法運行中有一定優(yōu)勢。同時在外業(yè)中增加點云重疊率等一系列操作,這樣才能打破該算法的局限性,提供應(yīng)用場景。

采取了人機結(jié)合的方式,即對于重疊區(qū)域小的兩個點云數(shù)據(jù),粗略地選取其可以重疊的部分,然后再對這一部分進行配準(zhǔn),得出的旋轉(zhuǎn)矩陣R、平移矩陣T再作用于原數(shù)據(jù),可以達(dá)到預(yù)期的效果。這種方式需要判斷出點云數(shù)據(jù)中重疊的區(qū)域,這就需要在采集數(shù)據(jù)同時收集相關(guān)的資料,方便在處理數(shù)據(jù)時判斷點云數(shù)據(jù)重疊區(qū)域的大體位置。本文在實例部分所用的點云數(shù)據(jù)就是重疊率小的數(shù)據(jù),需要在配準(zhǔn)前粗略地選取點云可以重疊的部分。

2.1.2精配準(zhǔn)

改進的ICP算法在主方向貼合算法運行之后的結(jié)果運行,設(shè)置閾值τ=0.000 000 1,經(jīng)過9次迭代之后配準(zhǔn)效果如3所示,精度統(tǒng)計如表1所示。改進的ICP迭代算法配準(zhǔn)效率高且配準(zhǔn)精度較傳統(tǒng)ICP方法高。

表格1 配準(zhǔn)耗時、誤差對比

調(diào)試之后,將圖像用Matlab顯示,由圖3可知,代碼編寫可行。整個運算過程中,每個數(shù)據(jù)的點的個數(shù)為40 000多個,迭代運行9次,一共耗時為0.190 162 s。不管是二維、三維配準(zhǔn)效果均滿足要求。同時由表1可知,改進的ICP迭代配準(zhǔn)算法較傳統(tǒng)ICP迭代算法在配準(zhǔn)耗時與精度方面均有提高。其中在相同點云數(shù)量配準(zhǔn)中,改進的ICP較傳統(tǒng)ICP配準(zhǔn)耗時縮減4倍有余,精度方面提高2倍有余,證明了本文的組合算法思想可信性。

(a)二維顯示

改進的ICP迭代算法的精髓在于閾值設(shè)置的大小。該值設(shè)置的大小又決定了運算時間,二者之間看似矛盾。但可通過調(diào)整閾值并考慮計算時間來權(quán)衡。特別是過小的閾值,直接造成增加幾何量級的迭代計算,帶來的后果就是計算時間的增加。所以如何選取合適的閾值,成為改進的ICP迭代算法成功實現(xiàn)的關(guān)鍵因素,而確定閾值可通過實驗經(jīng)驗確定,也可通過誤差反向傳播定律等方法實現(xiàn)。改進的ICP算法思想明確,簡單且易編程實現(xiàn),但是其特性也決定了該算法運行所需的條件較高,為了實現(xiàn)它就必須達(dá)到所規(guī)定的條件。因此,必須在運用改進的ICP算法之前,先對點云數(shù)據(jù)進行粗配準(zhǔn),給出一個比較理想的初始對應(yīng)位置。

2.2 實驗二

根據(jù)上文提及的外業(yè)采集數(shù)據(jù)流程,采集對象為某一大學(xué)正門。該校門高度12.3 m,寬度8.45 m,厚度2.70 m,為鋼筋與混凝土結(jié)構(gòu)。通過實地調(diào)查,采用四站全包圍方式進行點云采集?？商崆巴ㄟ^(real-time kinematic,RTK)測量方式施測圖根點作為標(biāo)靶,作為將點云模型轉(zhuǎn)換至當(dāng)?shù)乜臻g坐標(biāo)系的參考點。將該校門點云數(shù)據(jù)去噪之后的背面效果展示,如圖4(a)所示,正面效果如圖4(b)所示。為運行IICP算法,利用專業(yè)的點云數(shù)據(jù)處理軟件拼接,效果如圖5(a)所示。為配準(zhǔn)點云數(shù)據(jù)首先確定重疊區(qū)域為門內(nèi)測;其次運用主方向貼合算法進行粗配準(zhǔn);最后利用IICP算法將粗配準(zhǔn)之后的點云數(shù)據(jù)精確配準(zhǔn)得到如圖5(b)所示的效果。最終對配準(zhǔn)的結(jié)果精度驗證與評定工作,經(jīng)過統(tǒng)計該次配準(zhǔn)的誤差為0.059 3。即在本文要求精度需要達(dá)到對應(yīng)點之間的距離不大于30 mm的條件下,點云數(shù)據(jù)中未達(dá)到配準(zhǔn)要求的點所占的比率為0.059 3。表2統(tǒng)計了改進ICP與傳統(tǒng)ICP在配準(zhǔn)耗時與精度兩方面統(tǒng)計,與實驗一結(jié)論相似。改進的ICP迭代配準(zhǔn)算法在精度與耗時中均由于傳統(tǒng)ICP算法,再次證明了改進的ICP算在配準(zhǔn)中的優(yōu)勢性。

表格2 配準(zhǔn)耗時、誤差對比

(a)背面效果

(a)未配準(zhǔn)前

3 結(jié)束語

本文在經(jīng)典ICP算法的基礎(chǔ)之上,研究了改進的ICP算法與主方向貼合算法的結(jié)合實現(xiàn)點云配準(zhǔn),并深入分析二者的適用條件,利用MATLAB編程軟件實現(xiàn)了這兩種算法。通過外業(yè)實測點云數(shù)據(jù),并利用實驗一與實驗二過程。陳述了粗配準(zhǔn)中利用主方向貼合算法,精配準(zhǔn)中利用改進的ICP迭代算法。這兩種實驗的成功都是基于點云重疊率較大的情況下實現(xiàn)。兩次實驗的點云數(shù)據(jù)重疊率較大,這為粗配準(zhǔn)與精配準(zhǔn)提供了有利條件,下一步將嘗試?yán)玫椭丿B率實現(xiàn)點云的有效建模實驗。