基于改進(jìn)的ICP與主方向貼合的點(diǎn)云配準(zhǔn)算法

朱錦杰

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

0 引言

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

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

1.1 主方向貼合算法

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

1.2 最近點(diǎn)迭代算法

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

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

Yk=C(X,Y)

(1)

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

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

(2)

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

H(X)=R(X)+T

(3)

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

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

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

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

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

1.3 改進(jìn)的ICP算法

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

(4)

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

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

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

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

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

2 實(shí)驗(yàn)驗(yàn)證

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

(5)

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

2.1 實(shí)驗(yàn)一

2.1.1粗配準(zhǔn)

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

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

(a)二維顯示

(a)二維顯示

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

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

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

2.1.2精配準(zhǔn)

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

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

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

(a)二維顯示

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

2.2 實(shí)驗(yàn)二

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

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

(a)背面效果

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

3 結(jié)束語

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