崔志婷 李彩林 王志勇 蘇本婭 王佳文 孫延坤

(山東理工大學(xué) 建筑工程學(xué)院, 山東 淄博 255000)

0 引言

為了實(shí)現(xiàn)對(duì)被測(cè)物體的整體覆蓋,進(jìn)行激光掃描時(shí)需要多點(diǎn)架站,每站點(diǎn)云具有獨(dú)立的坐標(biāo)系,通過(guò)將不同視角下的激光點(diǎn)云進(jìn)行拼合,實(shí)現(xiàn)各站點(diǎn)云坐標(biāo)系的統(tǒng)一,完成點(diǎn)云的配準(zhǔn)。點(diǎn)云配準(zhǔn)是點(diǎn)云處理流程中的重要步驟,更是逆向工程、計(jì)算機(jī)視覺(jué)等領(lǐng)域中進(jìn)行三維重建的關(guān)鍵問(wèn)題,其配準(zhǔn)的效率和精度對(duì)工程整體有十分重要的影響。

點(diǎn)云配準(zhǔn)通過(guò)尋找不同點(diǎn)云間的同名特征來(lái)計(jì)算他們之間的變換矩陣,然后將點(diǎn)云拼接在同一坐標(biāo)系下。配準(zhǔn)算法分為粗配準(zhǔn)和精配準(zhǔn),點(diǎn)云粗配準(zhǔn)使兩組點(diǎn)云數(shù)據(jù)盡可能接近,減小兩個(gè)點(diǎn)云模型間的差異,為精配準(zhǔn)提供良好的初值,提高配準(zhǔn)效率和精度。粗配準(zhǔn)方法有基于遺傳算法(Genetic Algorithm, GA)[1]、基于特征以及全局配準(zhǔn)的方法,同時(shí)還可以通過(guò)點(diǎn)云處理軟件進(jìn)行粗配準(zhǔn)。

ZHU等提出利用GA對(duì)部分重疊范圍掃描進(jìn)行對(duì)偶配準(zhǔn)的有效方法,利用可靠的成對(duì)配準(zhǔn)結(jié)果計(jì)算初始參數(shù),但該算法效率較低[2-3]?；谔卣鞯拇峙錅?zhǔn)首先是根據(jù)局部特征描述符計(jì)算點(diǎn)的特征,然后根據(jù)特征對(duì)點(diǎn)云進(jìn)行匹配,確定點(diǎn)的對(duì)應(yīng)關(guān)系后進(jìn)而對(duì)變換參數(shù)進(jìn)行求解[4-5]。SUN等提出了一種判別性強(qiáng)的局部形狀描述符—區(qū)域曲率圖(RCM),采用基于RCM子區(qū)域的搜索匹配策略尋找三維對(duì)應(yīng)點(diǎn),利用幾何一致性實(shí)現(xiàn)粗配準(zhǔn),具有較高的配準(zhǔn)效率[6]。RUSU等提出通過(guò)三維形狀描述符計(jì)算特征點(diǎn)的幾何特征,將來(lái)自不同點(diǎn)云的具有最相似特征的點(diǎn)對(duì)識(shí)別為對(duì)應(yīng)點(diǎn),求解變換參數(shù),這種算法容易受到噪聲點(diǎn)的干擾[7]。全局配準(zhǔn)算法中,有基于隨機(jī)抽樣一致算法(Random Samle Consensus, RANSAC)框架的方法,該方法利用點(diǎn)云數(shù)據(jù)間的重疊區(qū)域確定對(duì)應(yīng)點(diǎn),根據(jù)對(duì)應(yīng)點(diǎn)求解待匹配點(diǎn)云間的剛體變換關(guān)系,通過(guò)對(duì)候選基重復(fù)投票,最后將概率最高的候選基確定為最優(yōu)解,但該算法穩(wěn)定性不高,容易匹配錯(cuò)誤的對(duì)應(yīng)點(diǎn)[8]。ZHOU等提出一種快速全局配準(zhǔn)算法,該算法對(duì)點(diǎn)云表面的點(diǎn)進(jìn)行配準(zhǔn),不需要初始化,運(yùn)行速度較快[9]。AIGER等提出了四點(diǎn)全等集算法4PCS(4-Points Congruent Sets),此算法的理論基礎(chǔ)在于共面4點(diǎn)對(duì)的仿射不變性,通過(guò)使用廣域基,將搜索復(fù)雜度降低,對(duì)噪聲和離群點(diǎn)有較好的魯棒性[10]。MELLADO等提出超級(jí)四點(diǎn)全等集算法(Super 4-Points Congruent Sets,Super4PCS),該算法允許任意位姿的掃描,而且算法時(shí)間復(fù)雜度是線性的,通過(guò)在目標(biāo)點(diǎn)云中進(jìn)行光柵化的網(wǎng)格劃分來(lái)實(shí)現(xiàn)點(diǎn)對(duì)的快速提取,同時(shí)利用角度約束來(lái)減少無(wú)效點(diǎn)對(duì)的產(chǎn)生,提高了整體點(diǎn)云的配準(zhǔn)精度和效率[11]。點(diǎn)云還可以通過(guò)Geomagic Studio、RiSCAN PRO等點(diǎn)云處理軟件進(jìn)行粗配準(zhǔn)。

本文分別利用Super4PCS算法、4PCS算法和點(diǎn)云處理軟件Geomagic Studio12,對(duì)四組激光點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)實(shí)驗(yàn),并對(duì)配準(zhǔn)結(jié)果進(jìn)行對(duì)比分析,得出他們各自的適用性。

1 4PCS算法

4PCS的算法原理為:首先在源點(diǎn)云P中隨機(jī)選擇3個(gè)點(diǎn),形成一個(gè)面,并依據(jù)共面不共線原則選擇第4個(gè)點(diǎn),從而組成一個(gè)共面的4點(diǎn)基B,然后在目標(biāo)點(diǎn)云Q中找到所有可能與B相似的全等的4點(diǎn)子集S,對(duì)于集合S中的每一個(gè)元素Si,利用其與B的對(duì)應(yīng)關(guān)系求得剛性變換矩陣Ti,使得B與Si的距離最小,然后根據(jù)(Largest Common Pointset,LCP)方法求得所有的最優(yōu)值并以此作為此輪迭代的最佳變換。最后將最佳變換矩陣T應(yīng)用到源點(diǎn)云P中,實(shí)現(xiàn)點(diǎn)云粗配準(zhǔn)。

在點(diǎn)云數(shù)據(jù)中的任意共面的4個(gè)點(diǎn)可以確定兩個(gè)點(diǎn)對(duì),4點(diǎn)集B={a,b,c,d}可以稱為一組基。如圖1所示,將每組基的表示量定義為:r1、r2、L1、L2,其中r1、r2為比例因子,其在點(diǎn)云旋轉(zhuǎn)和平移變化中具有仿射不變性,L1、L2為點(diǎn)距,如果兩組基的所有表示量都相等,則這兩組基具有一致性,即對(duì)應(yīng)的一致全等4點(diǎn)。r1、r2、L1、L2的具體表示如圖1所示。

圖1 四點(diǎn)基

(1)

L1=‖a-b‖,L2=‖c-d‖

(2)

2 Super4PCS算法

Super4PCS算法允許任意位姿的點(diǎn)云進(jìn)行配準(zhǔn),能夠自動(dòng)刪除有誤點(diǎn)對(duì)并對(duì)有效點(diǎn)對(duì)快速提取,實(shí)現(xiàn)點(diǎn)云的快速配準(zhǔn)。Super4PCS算法的基本原理為:

(1)在源點(diǎn)云內(nèi)選取基時(shí),要遵循距離最大化原則,即保證點(diǎn)與點(diǎn)之間的距離最大化但又不超過(guò)某一閾值,而這一閾值由重疊率f來(lái)確定,同時(shí)還要采用三加一策略,即先在可能為重疊區(qū)域的點(diǎn)云表面選擇3個(gè)不同的點(diǎn),第4個(gè)點(diǎn)由共面不共線原則進(jìn)行選取,由此共面4點(diǎn)組成一個(gè)基B={Pa,Pb,Pc,Pd}。確定基B后,可以得到相應(yīng)的比例r1、r2,以及兩點(diǎn)之間的距離d1、d2,其具體表示為:

(3)

d1=‖Pa-Pb‖,d2=‖Pc-Pd‖

(4)

(2)先在目標(biāo)點(diǎn)云Q中確定集合S1與S2。在目標(biāo)點(diǎn)云Q中以每一點(diǎn)qi為球心,并分別以R=d1±ε和R=d2±ε為半徑畫(huà)球。qi與在[d1-ε,d1+ε]范圍內(nèi)的點(diǎn)即為點(diǎn)對(duì)集合S1,而qi與[d2-ε,d2+ε]范圍內(nèi)的點(diǎn)對(duì)為集合S2。同時(shí)建立一個(gè)單位尺寸為ε的三維網(wǎng)格G將點(diǎn)云表面進(jìn)行柵格化。

(3)源點(diǎn)云P中選定的基如圖2(a)所示,在目標(biāo)點(diǎn)云Q中存在與其對(duì)應(yīng)的點(diǎn)集但同時(shí)也存在錯(cuò)誤的點(diǎn)集{qa,qb,qc',qd'},如圖2(b)所示。在目標(biāo)點(diǎn)云Q中提取與基B對(duì)應(yīng)的4點(diǎn)集。遍歷點(diǎn)對(duì)集合S1和S2中所有的候選點(diǎn)對(duì),根據(jù)交比一致性計(jì)算所有的交叉節(jié)點(diǎn)e,并存儲(chǔ)在網(wǎng)格G中。依據(jù)基B中兩對(duì)應(yīng)點(diǎn)對(duì)的夾角為θ,在網(wǎng)格G中提取出節(jié)點(diǎn)近似相等,同時(shí)兩點(diǎn)對(duì)之間的連線夾角近似等于θ,其誤差范圍在ξ內(nèi)的4點(diǎn)基進(jìn)行匹配。

圖2 Super4PCS示意圖

(4)在點(diǎn)云Q中所有滿足條件的與基B對(duì)應(yīng)的四點(diǎn)集合U={U1,U2,…,Un},求出基B與每一個(gè)Ui之間的變換矩陣,通過(guò)比較最大化公共點(diǎn)集LCP選擇其中配準(zhǔn)精度最高的變換矩陣進(jìn)行全局變換。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文采用激光掃描儀Z+F IMAGER?5010C分別對(duì)佛像和青銅器進(jìn)行實(shí)體三維掃描,如圖3(a)、(b)所示,獲取的佛像三維點(diǎn)云數(shù)據(jù)特征較為明顯;如圖3(c)所示,青銅器點(diǎn)云特征顯著且?guī)в性肼暋Ｍ瑫r(shí)利用三維激光掃描儀RIEGL VZ-400對(duì)孔子雕像進(jìn)行掃描,獲取的三維點(diǎn)云數(shù)據(jù)如圖3(d)所示。表1為各站點(diǎn)云數(shù)。

圖3 相鄰兩站激光點(diǎn)云數(shù)據(jù)

表1 各站點(diǎn)云數(shù)

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)在相同的運(yùn)行配置環(huán)境下進(jìn)行,分別對(duì)低重疊率佛像、高重疊率佛像、青銅器和雕像四種數(shù)據(jù)集進(jìn)行配準(zhǔn),對(duì)比分析Super4PCS、4PCS算法以及軟件Geomagic Studio 12配準(zhǔn)結(jié)果。圖4為Super4PCS算法配準(zhǔn)效果圖,圖5為4PCS算法配準(zhǔn)效果圖,圖6為軟件Geomagic Studio 12配準(zhǔn)效果圖。本文通過(guò)計(jì)算均方根誤差(Root Mean Square Error, RMSE)作為配準(zhǔn)精度指標(biāo),RMSE為源點(diǎn)云和目標(biāo)點(diǎn)云間的平均距離,并對(duì)3種方法的配準(zhǔn)時(shí)間進(jìn)行統(tǒng)計(jì)分析。結(jié)果如表2所示。

圖4 Super4PCS算法配準(zhǔn)效果圖

圖5 4PCS算法配準(zhǔn)效果圖

圖6 軟件配準(zhǔn)效果圖

根據(jù)配準(zhǔn)效果圖4～6和表2可知:

(1)對(duì)于低重疊率佛像點(diǎn)云來(lái)說(shuō),由于相鄰兩站點(diǎn)云重疊率過(guò)低,相似特征少,不利于點(diǎn)云配準(zhǔn)。由點(diǎn)云配準(zhǔn)效果圖可知,Super4PCS算法和4PCS算法在配準(zhǔn)低重疊率點(diǎn)云時(shí)結(jié)果均出現(xiàn)較大偏差,軟件配準(zhǔn)低重疊率點(diǎn)云則結(jié)果較好。Super4PCS算法和4PCS算法對(duì)點(diǎn)云重疊率有較高要求,因此在配準(zhǔn)低重疊率點(diǎn)云數(shù)據(jù)時(shí)可以選擇軟件配準(zhǔn)等其他有效方法。

(2)對(duì)于高重疊率佛像點(diǎn)云,重疊區(qū)域相似特征多,有利于點(diǎn)云數(shù)據(jù)融合。軟件配準(zhǔn)精度高于4PCS算法的配準(zhǔn)精度,Super4PCS算法點(diǎn)云配準(zhǔn)效果最好。由表2可知,Super4PCS算法的配準(zhǔn)精度和效率明顯優(yōu)于其他兩種方法。

(3)對(duì)于青銅器點(diǎn)云,具有明顯的噪聲點(diǎn),噪聲點(diǎn)在一定程度上影響配準(zhǔn)精度和時(shí)間。由配準(zhǔn)效果圖可以看出,對(duì)存在噪聲點(diǎn)的兩站點(diǎn)云,4PCS算法和軟件配準(zhǔn)方法的配準(zhǔn)效果都存在明顯偏差,Super4PCS算法配準(zhǔn)效果較好。由表2可知,軟件配準(zhǔn)點(diǎn)云結(jié)果精度高于4PCS算法點(diǎn)云配準(zhǔn)精度,Super4PCS算法的配準(zhǔn)精度和效率優(yōu)于其他兩種方法,具有更高的魯棒性。

(4)對(duì)于雕像點(diǎn)云,點(diǎn)云數(shù)據(jù)量明顯增多,且相鄰兩站點(diǎn)云數(shù)差別較大,相比于其他點(diǎn)云數(shù)據(jù),其形狀更為復(fù)雜。從配準(zhǔn)效果圖可以看出,4PCS算法配準(zhǔn)后兩站點(diǎn)云有明顯的左右偏差,軟件配準(zhǔn)則有上下偏差,Super4PCS算法配準(zhǔn)效果最好。由表2可知,4PCS算法的點(diǎn)云配準(zhǔn)精度高于軟件配準(zhǔn)精度,相比于這兩種方法,Super4PCS算法配準(zhǔn)精度更高且更高效。

表2 點(diǎn)云配準(zhǔn)效果評(píng)估

總體來(lái)看,對(duì)于特征多、重疊率高的點(diǎn)云模型,3種方法都可以較好的完成配準(zhǔn)。對(duì)于重疊率較低的點(diǎn)云數(shù)據(jù),Super4PCS算法和4PCS算法不能實(shí)現(xiàn)點(diǎn)云的有效拼接,可以選擇其他有效方法。除低重疊率點(diǎn)云數(shù)據(jù)外,Super4PCS算法的配準(zhǔn)精度和效率最高,4PCS算法的效率其次,軟件Geomagic Studio 12的點(diǎn)云配準(zhǔn)精度和時(shí)間受人為因素的影響,具有不穩(wěn)定性。

4 結(jié)束語(yǔ)

本文通過(guò)運(yùn)用Super4PCS、4PCS算法和軟件Geomagic Studio 12對(duì)四組點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)實(shí)驗(yàn),統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果并進(jìn)行了比較分析。實(shí)驗(yàn)結(jié)果表明,Super4PCS效率最快,配準(zhǔn)效果最好,對(duì)噪聲有較好的抵抗力,不適用于低重疊率點(diǎn)云模型配準(zhǔn);4PCS配準(zhǔn)效率較快,對(duì)噪聲的抗干擾能力較差,同樣不適用于低重疊率點(diǎn)云配準(zhǔn);軟件Geomagic Studio 12效率最慢,適用于各種情況的點(diǎn)云配準(zhǔn),配準(zhǔn)精度受人為因素的影響。點(diǎn)云配準(zhǔn)時(shí),可以依據(jù)數(shù)據(jù)的特點(diǎn)選取合適的方法。

實(shí)驗(yàn)中采用的算法都是原始的經(jīng)典自動(dòng)粗配準(zhǔn)方法,不少學(xué)者對(duì)這些算法進(jìn)行了改進(jìn)以提高配準(zhǔn)效率和精度。對(duì)這些改進(jìn)算法進(jìn)行不同條件下的實(shí)驗(yàn)對(duì)比與分析,將是下一步的研究工作。