朱錦杰

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

0 引言

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

1 配準算法原理

1.1 主方向貼合算法

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

1.2 最近點迭代算法

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

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

Yk=C(X,Y)

(1)

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

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

(2)

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

H(X)=R(X)+T

(3)

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

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

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

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

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

1.3 改進的ICP算法

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

(4)

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

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

1)經過主方向貼合算法粗配準之后的源點云為P′,目標點云集合為Q′,分別計算出每個點的法向量。

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

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

2 實驗驗證

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

(5)

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

2.1 實驗一

2.1.1粗配準

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

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

(a)二維顯示

(a)二維顯示

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

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

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

2.1.2精配準

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

表格1 配準耗時、誤差對比

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

(a)二維顯示

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

2.2 實驗二

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

表格2 配準耗時、誤差對比

(a)背面效果

(a)未配準前

3 結束語

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