陳金廣,郭秋夢(mèng),馬麗麗,徐步高

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,西安 710048)

1 引言

點(diǎn)云拼接在三維物體重建中有著廣泛的應(yīng)用,如逆向工程、移動(dòng)機(jī)器人、航天航空、指紋識(shí)別、計(jì)算機(jī)視覺等眾多領(lǐng)域.在對(duì)三維物體進(jìn)行測(cè)量的過程中,掃描設(shè)備可能會(huì)受到視野上的限制,或是受到噪聲、光照等的影響,使得掃描設(shè)備在同一視角下無法獲取待測(cè)物體的全部點(diǎn)云信息.因此,需要從多視角對(duì)待測(cè)物體進(jìn)行測(cè)量,從而重建出完整的三維物體模型.

目前使用最為廣泛的點(diǎn)云拼接算法是1992年Besl等[1]提出的迭代最近點(diǎn)算法(Iterative Closest Points,ICP),其目的是在兩片點(diǎn)云之間尋找距離最近的點(diǎn),計(jì)算最優(yōu)剛體變換矩陣,直到滿足某種度量準(zhǔn)則下的最優(yōu)匹配.Chen等在傳統(tǒng)的ICP算法的基礎(chǔ)上提出了一種新的點(diǎn)云拼接算法[2],該方法能夠提高算法的收斂速度,減少迭代耗時(shí)及迭代次數(shù),兩者的不同之處在于前者提出的是將點(diǎn)與點(diǎn)之間的距離作為鄰近點(diǎn),而后者則利用點(diǎn)與面之間的距離作為鄰近點(diǎn).文獻(xiàn)[3]提出與圖像信息相結(jié)合的快速點(diǎn)云拼接方法,對(duì)平移和旋轉(zhuǎn)兩種變換分別求解.通過改進(jìn)的ICP算法得到平移變換,而旋轉(zhuǎn)矩陣則是由拍攝圖像與幾何知識(shí)相結(jié)合而得到的.此方法大大降低了計(jì)算復(fù)雜度,但利用相機(jī)拍攝得到的圖像必須存在較大部分的重疊,否則需要通過人工操作提供匹配點(diǎn),操作過程繁瑣.文獻(xiàn)[4]提出的動(dòng)態(tài)分層匹配標(biāo)識(shí)點(diǎn)算法,將帶標(biāo)識(shí)點(diǎn)的點(diǎn)云分別建立最小包圍盒,通過4個(gè)方向進(jìn)行分層搜索,以最后搜索到的標(biāo)識(shí)點(diǎn)為頂點(diǎn),建立動(dòng)態(tài)矩陣,并記錄相應(yīng)的標(biāo)識(shí)點(diǎn)對(duì),但此方法不僅費(fèi)時(shí)而且增加了算法的復(fù)雜性.文獻(xiàn)[5]提出一種將三維激光掃描技術(shù)與測(cè)量技術(shù)相結(jié)合的研究思路,通過對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行處理、配準(zhǔn)、拼接、去噪等步驟實(shí)現(xiàn)三維物體重建.

目前點(diǎn)云拼接技術(shù)按照拼接過程可以分為粗拼接和精確拼接,粗拼接是將不同坐標(biāo)系下的點(diǎn)云數(shù)據(jù)統(tǒng)一到同一坐標(biāo)系下,隨后進(jìn)行配準(zhǔn),為精確拼接提供初始值;精確拼接則是通過ICP算法對(duì)坐標(biāo)變換參數(shù)進(jìn)行迭代優(yōu)化,使拼接誤差最小,滿足所需的收斂精度.粗拼接一般可分為兩類,一類是借助輔助設(shè)備的拼接方法,包括轉(zhuǎn)臺(tái)法[6-8]、標(biāo)識(shí)點(diǎn)法[9,10]、定標(biāo)球法[11].轉(zhuǎn)臺(tái)法是使回轉(zhuǎn)臺(tái)傾斜一定的角度,通過旋轉(zhuǎn)待測(cè)物體來獲取測(cè)量數(shù)據(jù),但此方法對(duì)測(cè)量設(shè)備的精度要求較高,且定位精度難以保證;標(biāo)識(shí)點(diǎn)法是在不同的視圖中建立三個(gè)基準(zhǔn)點(diǎn),通過這三個(gè)基準(zhǔn)點(diǎn)對(duì)齊三維測(cè)量數(shù)據(jù),此方法的計(jì)算較為簡(jiǎn)單,但是在尋找基準(zhǔn)點(diǎn)時(shí)較為繁瑣,并且會(huì)影響其定位精度及測(cè)量的真實(shí)度.文獻(xiàn)[10]提出利用標(biāo)識(shí)點(diǎn)對(duì)多視圖進(jìn)行約束的高精度粗拼接算法,此方法是在掃描過程中構(gòu)建標(biāo)識(shí)點(diǎn)多視圖網(wǎng)格,并兩兩拼接,然后利用光束法平差技術(shù)優(yōu)化此網(wǎng)格,得到全局控制點(diǎn),并保存坐標(biāo)系下的三維點(diǎn)云數(shù)據(jù),最后將全局控制點(diǎn)與坐標(biāo)系下的三維點(diǎn)云數(shù)據(jù)進(jìn)行拼接,得到完整的三維模型.另一類是基于曲面特征的拼接方法,包括三點(diǎn)法、雙切曲線法等.三點(diǎn)法是Zhang等[12]通過兩片點(diǎn)云中的三個(gè)點(diǎn)所形成的平面來確定坐標(biāo)變換參數(shù),此方法的不足之處在于點(diǎn)云數(shù)量過多時(shí)計(jì)算效率下降,分辨率不高.雙切曲線法是由Wyngaerd等[13]人提取待測(cè)物體曲線的表面特征,通過匹配雙曲線之間對(duì)應(yīng)點(diǎn)的關(guān)系來確立點(diǎn)云之間的關(guān)系,此方法操作簡(jiǎn)單,但對(duì)于表面特征不明顯的待測(cè)物體效果欠佳.目前國(guó)內(nèi)外關(guān)于點(diǎn)云的拼接算法力求改善拼接精度,許多學(xué)者針對(duì)對(duì)應(yīng)點(diǎn)之間的搜索問題提出了不同的搜索策略,但一定程度上仍存在問題,比如點(diǎn)云表面曲率變化較大時(shí),會(huì)導(dǎo)致平面投影點(diǎn)與真正的對(duì)應(yīng)點(diǎn)之間存在較大的偏差,此偏差會(huì)直接影響兩片點(diǎn)云的拼接精度,另外在處理此偏差的過程中無疑增加了計(jì)算機(jī)的計(jì)算量等諸如此類的問題.也正是因?yàn)榇嬖谶@樣的問題,故而需要對(duì)點(diǎn)云拼接算法進(jìn)行改進(jìn).國(guó)內(nèi)外的相關(guān)工作為本文的點(diǎn)云拼接算法研究提供了方向,本文算法致力于提高拼接精度,減少迭代次數(shù)及迭代耗時(shí),因而提出了一種改進(jìn)的ICP算法對(duì)多視點(diǎn)云進(jìn)行拼接,通過多次實(shí)驗(yàn)驗(yàn)證了其正確性及有效性.

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

針對(duì)點(diǎn)云的拼接問題,國(guó)內(nèi)外的研究學(xué)者對(duì)此提出了很多解決方案,其中就有Besl提出的ICP算法,此算法是對(duì)目標(biāo)點(diǎn)集P尋找與之存在一一對(duì)應(yīng)關(guān)系的參考點(diǎn)集Q中距離最近的點(diǎn)構(gòu)成的集合,建立點(diǎn)與點(diǎn)之間的映射關(guān)系,根據(jù)這種映射關(guān)系計(jì)算兩點(diǎn)集之間的變換參數(shù),最終求出相應(yīng)的平移向量和旋轉(zhuǎn)矩陣,直到滿足所需的收斂精度并達(dá)到點(diǎn)云拼接的目的為止.

ICP算法的實(shí)現(xiàn)[1]一般分為以下5個(gè)步驟:

(1)假設(shè)給定點(diǎn)云P為目標(biāo)點(diǎn)云,用表示,點(diǎn)云數(shù)量為NP,給定點(diǎn)云Q為參考點(diǎn)云,用表示,點(diǎn)云數(shù)量為NQ,并滿足NP≤NQ.確定點(diǎn)云P、Q之間存在映射關(guān)系的對(duì)應(yīng)點(diǎn)對(duì),并構(gòu)成集合,搜索方法主要包括點(diǎn)到點(diǎn)、點(diǎn)到切平面、K-D樹搜索、八叉樹搜索等.

(2)根據(jù)搜索到的對(duì)應(yīng)點(diǎn)對(duì)集合求出初始旋轉(zhuǎn)矩陣T1和平移參數(shù)R1:

其中P1和Q0分別表示目標(biāo)點(diǎn)集P和參考點(diǎn)云Q中的點(diǎn).求取平移和旋轉(zhuǎn)參數(shù)最典型的方法有四元數(shù)法[14]和奇異值分解法[15]等.

(3)利用上述求得的平移和旋轉(zhuǎn)參數(shù)對(duì)Q1進(jìn)行坐標(biāo)轉(zhuǎn)換,得到新的變換點(diǎn)集Q2:

(4)重復(fù)步驟(2)和(3),進(jìn)行迭代計(jì)算,其中m表示對(duì)應(yīng)點(diǎn)對(duì)的個(gè)數(shù):

(5)步驟(4)中得到的新的變換點(diǎn)集與參考點(diǎn)云,這兩個(gè)點(diǎn)集在配準(zhǔn)轉(zhuǎn)換過程中能使目標(biāo)函數(shù)最小:

i表示點(diǎn)云中的任意一點(diǎn).當(dāng)目標(biāo)函數(shù)最小時(shí)停止迭代計(jì)算,得到均方誤差

假設(shè)給定迭代收斂閾值τ,且τ＞0,相鄰兩次迭代間的均方誤差時(shí),停止迭代.若不滿足式(5),則重復(fù)步驟(4)重新迭代計(jì)算新的點(diǎn)集,直到滿足目標(biāo)函數(shù)的要求為止.

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

ICP算法是一種迭代計(jì)算的算法,具有較高的拼接匹配精度,但是ICP算法強(qiáng)調(diào)兩片待拼接的點(diǎn)云之間的數(shù)據(jù)點(diǎn)必須是一一對(duì)應(yīng)的包含關(guān)系,ICP算法為目標(biāo)點(diǎn)云中的每個(gè)點(diǎn)尋找在參考點(diǎn)云中對(duì)應(yīng)的點(diǎn),一一進(jìn)行匹配,無疑增加了計(jì)算量.如果初始位姿較好,則能獲取較好的拼接精度和收斂速度,若點(diǎn)云的初始姿態(tài)較差將直接影響計(jì)算機(jī)的計(jì)算速度.若初始位置較差會(huì)影響目標(biāo)點(diǎn)云尋找與之存在對(duì)應(yīng)關(guān)系的參考點(diǎn)云中的點(diǎn),在尋找對(duì)應(yīng)點(diǎn)時(shí)會(huì)出現(xiàn)錯(cuò)誤匹配,無形中增加了難度,因而也就難以保證算法精度及效率,對(duì)此部分做出改進(jìn)后對(duì)應(yīng)Step2,確定目標(biāo)點(diǎn)云中的點(diǎn)的三維坐標(biāo)并進(jìn)行排序,將鄰域搜索轉(zhuǎn)化為局部搜索,從而提高計(jì)算機(jī)的計(jì)算速度.從上述過程可知,由于需要計(jì)算目標(biāo)點(diǎn)云中每個(gè)點(diǎn)的對(duì)應(yīng)點(diǎn)因而計(jì)算量較大,可能使整個(gè)迭代過程陷入局部最優(yōu)而不是全局最優(yōu).另外此方法是對(duì)點(diǎn)云直接處理,無需進(jìn)行特征點(diǎn)提取、分割等操作.

由于傳統(tǒng)的ICP算法是采用遍歷的方式來尋找兩片點(diǎn)云之間的對(duì)應(yīng)關(guān)系,增大了計(jì)算機(jī)的計(jì)算量,降低了計(jì)算效率,針對(duì)傳統(tǒng)ICP算法的缺陷,本文提出的坐標(biāo)軸法用以計(jì)算目標(biāo)點(diǎn)云中的點(diǎn)及前后各n個(gè)點(diǎn)在坐標(biāo)軸上的距離,加以閾值限制,取距離最近的k個(gè)點(diǎn)構(gòu)成最近點(diǎn)集,減少了不必要的計(jì)算量,提高了計(jì)算效率.基本思想是確定一個(gè)點(diǎn)k的三維坐標(biāo)Pk,創(chuàng)建三個(gè)索引表,以坐標(biāo)遞增的順序存儲(chǔ)輸入點(diǎn)的三維坐標(biāo),從而將某個(gè)點(diǎn)的鄰域搜索轉(zhuǎn)化為局部搜索.另外點(diǎn)云模型中的點(diǎn)是均勻密集分布的,因而選擇坐標(biāo)與Pk坐標(biāo)相近的點(diǎn)組成搜索子集,其中在搜索最近點(diǎn)集時(shí),設(shè)定約束搜索范圍的閾值,減少不必要的計(jì)算量,然后計(jì)算子集中的每個(gè)點(diǎn)到Pk的距離,并以遞增的順序排列,進(jìn)而得到最近點(diǎn)集.以Pk為中心點(diǎn)進(jìn)行最近點(diǎn)集搜索時(shí),設(shè)置閾值以約束Pk點(diǎn)前后的搜索范圍,其中閾值的大小與掃描的點(diǎn)云距離有關(guān).當(dāng)閾值取值過小時(shí),不能獲取全部有效的最近點(diǎn),若閾值過大,則計(jì)算量仍然較大.經(jīng)多次實(shí)驗(yàn),設(shè)置閾值為0.01.

改進(jìn)后的ICP算法步驟如下:

Step1.尋找待拼接點(diǎn)云的特征點(diǎn),并進(jìn)行初始化,確立待測(cè)點(diǎn)云之間的對(duì)應(yīng)關(guān)系;

Step2.

1)確定一個(gè)點(diǎn)Pk的三維坐標(biāo),然后創(chuàng)建三個(gè)索引表;

2)將輸入的三維坐標(biāo)以坐標(biāo)遞增的順序排列,并存入數(shù)組Px、Py、Pz中,從而將某個(gè)點(diǎn)的鄰域搜索轉(zhuǎn)化為局部搜索;

3)將Pk點(diǎn)作為候選點(diǎn),計(jì)算數(shù)組 Px、Py、Pz中Pk點(diǎn)及前后各n個(gè)點(diǎn)在三維坐標(biāo)軸上的歐式距離;

4)判斷歐式距離與給定閾值的關(guān)系,若歐式距離大于等于閾值則停止計(jì)算,將全部點(diǎn)存入到新數(shù)組Tx、Ty、Tz中,若小于閾值則返回到數(shù)組Px、Py、Pz中重新選取候選點(diǎn);

Step3.求新數(shù)組Tx、Ty、Tz中三維坐標(biāo)的交集,計(jì)算出最近點(diǎn)集及坐標(biāo)變換矩陣,若誤差收斂則配準(zhǔn)到參考點(diǎn)云,否則返回重新計(jì)算最近點(diǎn).

改進(jìn)的ICP算法流程圖如圖1.

4 實(shí)驗(yàn)結(jié)果及分析

本文共進(jìn)行了三組實(shí)驗(yàn),分別采用斯坦福點(diǎn)云數(shù)據(jù)庫(kù)中的Bunny模型、Dragon模型及一組由Kinect采集的三維人體點(diǎn)云數(shù)據(jù),通過三組實(shí)驗(yàn)驗(yàn)證本文算法的有效性和正確性.

實(shí)驗(yàn)1采用的是不同視角下的Bunny點(diǎn)云模型,分別為點(diǎn)云數(shù)量是40 256的bunny_000.pcd模型和點(diǎn)云數(shù)量是40 097的bunny_045.pcd模型,如圖2(a)、(b)所示.實(shí)驗(yàn)先后采用傳統(tǒng)的ICP算法和改進(jìn)的ICP算法進(jìn)行點(diǎn)云拼接,得到拼接效果如圖2(c)、(d).由圖2(c)可知,采用傳統(tǒng)的ICP算法在拼接過程中出現(xiàn)較大程度上的錯(cuò)位,尤其在Bunny的耳朵、后背以及整個(gè)軀體上,從圖中可以看出未能得出良好的拼接效果.經(jīng)改進(jìn)的ICP算法拼接后效果良好,從圖2(d)中可以看出Bunny的耳朵、腳部以及頭部較傳統(tǒng)ICP算法實(shí)現(xiàn)了完全的拼接,姿態(tài)良好,并且在尾部和后背部分較傳統(tǒng)ICP算法也有明顯的改進(jìn).

圖1 改進(jìn)的ICP算法流程圖

圖2 Bunny點(diǎn)云拼接

實(shí)驗(yàn)2選取的是點(diǎn)云數(shù)量較小的Dragon點(diǎn)云模型,圖3(a)、(b)的初始點(diǎn)云數(shù)量分別為19 318、30 492.圖3(c)是經(jīng)傳統(tǒng)ICP算法拼接后的效果圖,可知Dragon點(diǎn)云在軀干和頭部的拼接較模糊,姿態(tài)差,拼接錯(cuò)位.從圖3(d)中可以看出Dragon的軀干部分拼接良好,尤其是在腳部和頭部實(shí)現(xiàn)完全拼接,效果優(yōu)良,另外在迭代時(shí)間上較傳統(tǒng)的ICP算法提高了19.11%.由此可以看出,經(jīng)改進(jìn)后的ICP算法在初始點(diǎn)云具有良好姿態(tài)的情況下,將拼接誤差大幅度降低,并且花費(fèi)的迭代時(shí)間減少,可見改進(jìn)后的算法減少了計(jì)算量,提高了拼接精度.

圖3 Dragon點(diǎn)云拼接

為進(jìn)一步驗(yàn)證本文算法的普適性,實(shí)驗(yàn)3采用一組由Kinect采集的三維人體點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn).圖4(a)、(b)表示兩片未拼接的初始點(diǎn)云,點(diǎn)云數(shù)量分別為12 675、14 742.從圖4(c)看出未經(jīng)改進(jìn)的傳統(tǒng)ICP算法在拼接時(shí)頭部出現(xiàn)偏移,并且手臂部位與身體部位也出現(xiàn)重疊,姿態(tài)較差,拼接精度較低.經(jīng)改進(jìn)的ICP算法拼接后,頭部和手臂部分的拼接有了明顯的改善如圖4(d),在迭代耗時(shí)上也由原先的0.821 s降低至0.567 s,提高了44.8%.

將迭代耗時(shí)和均方誤差作為收斂效果的標(biāo)準(zhǔn)進(jìn)行評(píng)價(jià),均方誤差記為error,迭代耗時(shí)記為time,改進(jìn)的ICP算法在最近點(diǎn)集的搜索上,設(shè)置一個(gè)閾值約束搜索范圍,避免了傳統(tǒng)ICP算法為目標(biāo)點(diǎn)云中的每個(gè)點(diǎn)尋找參考點(diǎn)云中與之對(duì)應(yīng)的點(diǎn)這一計(jì)算量較大的過程,取而代之的是將閾值范圍外的點(diǎn)剔除掉,從而減少了搜索的計(jì)算量.上述3組點(diǎn)云數(shù)據(jù)實(shí)驗(yàn)結(jié)果如表1所示.從表中可看出,在迭代時(shí)間上提高了19.1%～47.4%,在均方誤差上也優(yōu)于傳統(tǒng)ICP算法,從而驗(yàn)證了本文算法的有效性.

圖4 三維人體點(diǎn)云拼接

表1 兩種算法拼接性能比較

5 結(jié)束語

點(diǎn)云拼接的拼接精度和拼接速度對(duì)三維重建有著至關(guān)重要的意義,因此對(duì)于傳統(tǒng)ICP算法在點(diǎn)云拼接上存在的缺陷,提出一種改進(jìn)的ICP算法.首先是在選取特征點(diǎn)時(shí),將閾值與坐標(biāo)軸結(jié)合,設(shè)定約束候選點(diǎn)搜索范圍的閾值,獲得歐氏距離最近的點(diǎn)集,然后利用ICP算法對(duì)點(diǎn)云進(jìn)行拼接.實(shí)驗(yàn)結(jié)果表明在確保拼接精度的情況下迭代速度有明顯的提升,解決了傳統(tǒng)ICP算法在計(jì)算速度和迭代耗時(shí)上的問題,提高了算法的準(zhǔn)確性和有效性,有較高的應(yīng)用價(jià)值.雖然本文算法對(duì)于一般性點(diǎn)云數(shù)據(jù)的拼接取得了較傳統(tǒng)ICP算法拼接的良好效果,但仍有不足之處,未來將對(duì)一般性點(diǎn)云數(shù)據(jù)的拼接精度做進(jìn)一步研究.

1 Besl PJ,McKay ND.A method for registration of 3-D shapes.IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239–256.[doi:10.1109/34.121791]

2 Chen Y,Medioni G.Object modeling by registration of multiple range images.Proceedings of 1991 IEEE International Conference on Robotics and Automation.Sacramento,CA,USA.1991.2724–2729.

3 王瑞巖,姜光,高全學(xué).結(jié)合圖像信息的快速點(diǎn)云拼接算法.測(cè)繪學(xué)報(bào),2016,45(1):96–102.

4 楊帆,白寶興,張振普,等.基于多視點(diǎn)云拼接算法研究.長(zhǎng)春理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,37(3):124–127.

5 索俊鋒,劉勇,蔣志勇,等.基于三維激光掃描點(diǎn)云數(shù)據(jù)的古建筑建模.測(cè)繪科學(xué),2017,42(3):179–185.

6 周朗明,鄭順義,黃榮永.旋轉(zhuǎn)平臺(tái)點(diǎn)云數(shù)據(jù)的配準(zhǔn)方法.測(cè)繪學(xué)報(bào),2013,42(1):73–79.

7 馬敏杰,楊洋,范愛平,等.復(fù)雜建筑物三維激光掃描與室內(nèi)外精細(xì)建模.測(cè)繪與空間地理信息,2015,38(1):111–113.

8 Wang GH,Hu ZY,Wu FC,et al.Implementation and experimental study on fast object modeling based on multiple structured stripes.Optics and Lasers in Engineering,2004,42(6):627–638.[doi:10.1016/j.optlaseng.2004.05.008]

9 李學(xué)軍,楊晟,李振舉,等.標(biāo)識(shí)點(diǎn)快速提取與高精度單點(diǎn)匹配式定位算法.吉林大學(xué)學(xué)報(bào)(工學(xué)版),2014,44(4):1197–1202.

10 袁建英,王瓊,李柏林.利用標(biāo)志點(diǎn)多視圖約束實(shí)現(xiàn)結(jié)構(gòu)光掃描高精度粗拼接.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2015,27(4):674–683.

11 李俊峰.大口徑深焦比Hindle球面鏡曲率半徑精確測(cè)量.電子測(cè)量與儀器學(xué)報(bào),2014,28(12):1401–1407.

12 Zhang Y,Tao T,Mei XS,et al.An online spindle rotation error measurement system based on improved three point method.Proceedings of the 9th International Conference on Electronic Measurement &Instruments.Beijing,China.2009.651–656.

13 Wyngaerd JV,van Gool L,Kock R,et al.Invariant-based registration of surface patches.The Proceedings of the 7th IEEE International Conference on Computer Vision.Kerkyra,Greece.1999.301–306.

14 徐曉蘇,周峰,張濤,等.基于四元數(shù)自適應(yīng)卡爾曼濾波的快速對(duì)準(zhǔn)算法.中國(guó)慣性技術(shù)學(xué)報(bào),2016,24(4):454–459.

15 張成,汪東,沈川,等.基于奇異值分解的可分離壓縮成像方法.計(jì)算機(jī)研究與發(fā)展,2016,52(12):2816–2823.[doi:10.7544/issn1000-1239.2016.20150414]