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

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

0 引言

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

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

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

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

1 4PCS算法

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

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

圖1 四點基

(1)

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

(2)

2 Super4PCS算法

Super4PCS算法允許任意位姿的點云進行配準,能夠自動刪除有誤點對并對有效點對快速提取,實現(xiàn)點云的快速配準。Super4PCS算法的基本原理為:

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

(3)

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

(4)

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

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

圖2 Super4PCS示意圖

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

3 實驗與分析

3.1 實驗數(shù)據

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

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

表1 各站點云數(shù)

3.2 實驗結果與分析

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

圖4 Super4PCS算法配準效果圖

圖5 4PCS算法配準效果圖

圖6 軟件配準效果圖

根據配準效果圖4～6和表2可知:

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

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

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

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

表2 點云配準效果評估

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

4 結束語

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

實驗中采用的算法都是原始的經典自動粗配準方法,不少學者對這些算法進行了改進以提高配準效率和精度。對這些改進算法進行不同條件下的實驗對比與分析,將是下一步的研究工作。