基于改進的ICP與主方向貼合的點云配準算法

朱錦杰

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

0 引言

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

1 配準算法原理

1.1 主方向貼合算法

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

1.2 最近點迭代算法

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

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

Yk=C(X,Y)

(1)

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

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

(2)

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

H(X)=R(X)+T

(3)

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

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

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

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

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

1.3 改進的ICP算法

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

(4)

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

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

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

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

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

2 實驗驗證

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

(5)

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

2.1 實驗一

2.1.1粗配準

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

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

(a)二維顯示

(a)二維顯示

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

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

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

2.1.2精配準

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

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

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

(a)二維顯示

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

2.2 實驗二

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

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

(a)背面效果

(a)未配準前

3 結束語

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