彭 蹦,楊耀權(quán),江鵬宇

(華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院,河北 保定 071003)

1 引 言

自20世紀(jì)60年代以來(lái),三維空間信息技術(shù)(spatial information technology,SIT)不斷發(fā)展,三維激光掃描(terrestrial laser scanning,TLS)作為SIT主流技術(shù),廣泛應(yīng)用于工程測(cè)量、軍事技術(shù)、數(shù)字城市模型、歷史文物保護(hù)等領(lǐng)域[1],數(shù)字信息數(shù)據(jù)采集的逆向工程技術(shù)在三維重建中的作用也越發(fā)明顯[2]。然而,TLS技術(shù)在實(shí)際工程應(yīng)用中,往往需要多站點(diǎn)、多角度掃描才能得到完整的目標(biāo)三維表面信息。因此,在同一坐標(biāo)系下,片段式點(diǎn)云數(shù)據(jù)的精準(zhǔn)整合,在三維重建領(lǐng)域內(nèi)尤為重要,點(diǎn)云配準(zhǔn)精度指標(biāo)也會(huì)直接影響到三維模型的后期數(shù)據(jù)處理工作。

目前,國(guó)內(nèi)外主流的點(diǎn)云配準(zhǔn)算法均是在Besl和Makay提出的傳統(tǒng)ICP[3]基礎(chǔ)上加以改進(jìn)的算法,擺脫了傳統(tǒng)ICP算法收斂速度慢、點(diǎn)云配準(zhǔn)誤差大以及配準(zhǔn)效率低的問(wèn)題,改善了點(diǎn)云的配準(zhǔn)效果。

從點(diǎn)集特征關(guān)系出發(fā),楊小青[4]等人提出基于法向量特征的改進(jìn)配準(zhǔn)方法；陶海躋[5]等人根據(jù)局部法向量特征的變換提取配準(zhǔn)特征點(diǎn)；郎萍[6]等人提出基于旋轉(zhuǎn)圖像特征描述子的方法；Bhoram Lee[7]等人提出學(xué)習(xí)各向異性ICP(LA-ICP)算法,從對(duì)象深度數(shù)據(jù)流中將不確定參數(shù)化成不同方向下的高斯算子；李仁忠[8]等人在傳統(tǒng)ICP配準(zhǔn)算法的基礎(chǔ)上,提出使用內(nèi)部形態(tài)描述子(ISS)特征點(diǎn)的方法,對(duì)點(diǎn)云進(jìn)行精確配準(zhǔn)。針對(duì)目標(biāo)函數(shù)及搜索域設(shè)定,Mouna Attia[9]等人從三維點(diǎn)云初始狀態(tài)角度出發(fā),對(duì)ICP算法目標(biāo)函數(shù)進(jìn)行高效猜測(cè)；楊軍[10]等人提出了一種基于自適應(yīng)最優(yōu)閾值的ICP改進(jìn)算法,解決整體與部分3D模型間的配準(zhǔn)問(wèn)題；張名芳[11]等人提出在線學(xué)習(xí)合并閾值的層次聚類(lèi)算法,結(jié)合點(diǎn)云的空間密度分布改善目標(biāo)函數(shù)聚類(lèi)結(jié)果。針對(duì)尺度變換矩陣,趙夫群[12]等人提出基于有界旋轉(zhuǎn)角的改進(jìn)ICP配準(zhǔn)方法；付怡然[13]提出一種基于Gauss-Newton來(lái)改進(jìn)非線性最小二乘法的算法,對(duì)尺度變換矩陣進(jìn)行精準(zhǔn)求解,并結(jié)合正態(tài)分布變換(normal distribution transform,NDT)最終實(shí)現(xiàn)點(diǎn)云的精細(xì)配準(zhǔn)；蔣悅[14]等人提出一種高維正交子空間映射下的尺度點(diǎn)云配準(zhǔn)算法,解決了無(wú)序、數(shù)據(jù)被遮擋且噪聲干擾較大的點(diǎn)云配準(zhǔn)問(wèn)題。

上述方法對(duì)傳統(tǒng)ICP配準(zhǔn)算法的改進(jìn)停留在收斂速度或點(diǎn)云配準(zhǔn)精度上,兩者兼顧性不強(qiáng),尤其當(dāng)激光點(diǎn)云數(shù)據(jù)量較為龐大時(shí),以上改進(jìn)的算法在點(diǎn)云配準(zhǔn)效率上不是十分理想。

本文將源點(diǎn)云和目標(biāo)點(diǎn)云按區(qū)域?qū)哟芜M(jìn)行粗略劃分,形成兩大類(lèi)區(qū)域方格,依據(jù)每個(gè)方格所在區(qū)域的法向量夾角特征,尋求點(diǎn)面曲率對(duì)應(yīng)關(guān)系,完成點(diǎn)云的初始配準(zhǔn)；在此基礎(chǔ)上,估算尺度變換矩陣的邊界旋轉(zhuǎn)角度,結(jié)合相關(guān)系數(shù)迭代因子,對(duì)剛性變換參數(shù)進(jìn)行最優(yōu)化調(diào)整。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證,針對(duì)20000數(shù)據(jù)點(diǎn)以上的點(diǎn)云,本文算法能明顯有效地提高點(diǎn)云的配準(zhǔn)精度,提升算法收斂速度。

2 點(diǎn)云預(yù)處理

依據(jù)傳統(tǒng)ICP 配準(zhǔn)算法的結(jié)構(gòu),大體可分為五個(gè)步驟:選擇特征點(diǎn)對(duì)集、確定目標(biāo)搜索函數(shù)、設(shè)定約束條件和策略、剔除無(wú)效點(diǎn)對(duì)、求解剛性變換矩陣參數(shù)。本文點(diǎn)云預(yù)處理過(guò)程包括有特征點(diǎn)對(duì)集的選擇和目標(biāo)搜索函數(shù)的確定。其中,主要從點(diǎn)云區(qū)域劃分、法向量夾角特征點(diǎn)選擇以及曲面曲率對(duì)應(yīng)關(guān)系三個(gè)方面來(lái)進(jìn)行說(shuō)明。

2.1 劃分點(diǎn)云格

將待配準(zhǔn)的A*、B*兩組原始點(diǎn)云數(shù)據(jù)分別進(jìn)行隨機(jī)均勻采樣,并以各個(gè)采樣點(diǎn)為初始聚類(lèi)中心,隨后利用基于歐氏空間距離的C—均值聚類(lèi)法進(jìn)行多次類(lèi)聚,將點(diǎn)云數(shù)據(jù)劃分為若干單元格子。歐氏空間距離公式如下:

(1)

其中,a和b分別表示空間n維向量；d12表示歐式距離。

2.2 提取法向量關(guān)鍵點(diǎn)

法向量夾角特征會(huì)隨著點(diǎn)云區(qū)域的起伏發(fā)生改變,如圖1所示。

圖1 不同點(diǎn)云分布區(qū)域的法向量Fig.1 Normal vector of different point cloud distribution areas

其中,γ2為平緩區(qū)域法向量n2的法向量夾角；γi+3為曲面區(qū)域法向量ni+3的法向量夾角；nx表示點(diǎn)云區(qū)域點(diǎn)的法向量,其中x=1,2…,i+j。

可以看出,在同一坐標(biāo)系內(nèi),點(diǎn)云平緩區(qū)域法向量夾角特征變化緩慢；而在點(diǎn)云曲面位置區(qū)域,法向量夾角特征變化快速,兩者特征區(qū)分比較明顯。

此時(shí),引入特征度概念,即點(diǎn)云分布區(qū)域某點(diǎn)ak的法向量夾角變化程度。同時(shí)可知,fi為點(diǎn)云法向量和其k-鄰域點(diǎn)法向量夾角的算術(shù)平均值。

(2)

其中,θij是γi法向量和γj法向量的夾角。

結(jié)合特征度的定義,在源點(diǎn)云集A*、B*中提取點(diǎn)云法向量特征關(guān)鍵點(diǎn),形成點(diǎn)云初始配準(zhǔn)點(diǎn)對(duì)集。其中,點(diǎn)云平緩區(qū)域在配準(zhǔn)過(guò)程中精度高,尺度迭代變換形態(tài)固定,而點(diǎn)云曲面區(qū)域在配準(zhǔn)的過(guò)程中容易發(fā)生錯(cuò)誤,從提高曲面區(qū)域點(diǎn)云配準(zhǔn)精度的角度出發(fā),應(yīng)選擇fi大的點(diǎn)作為特征點(diǎn),使曲面區(qū)域分布有比較多的法向量夾角特征。法向量特征關(guān)鍵點(diǎn)提取步驟如下:

1)設(shè)定關(guān)鍵點(diǎn)提取閾值δa,若某點(diǎn)處的法向量夾角算術(shù)平均值fi≤δa,則說(shuō)明該點(diǎn)處在點(diǎn)云平緩區(qū)域,特征價(jià)值不高,應(yīng)舍去；若某點(diǎn)處的法向量夾角算術(shù)平均值fi>δa,則說(shuō)明該點(diǎn)處在點(diǎn)云的曲面區(qū)域,記錄該點(diǎn)三維信息,予以保留；

2)判別fi是否滿足在k-領(lǐng)域點(diǎn)內(nèi)取得最大值max,如不滿足,則繼續(xù)在k-領(lǐng)域點(diǎn)內(nèi)尋找,fi最大值點(diǎn)即為關(guān)鍵點(diǎn)am；

2.3 選取初始匹配點(diǎn)對(duì)

曲率關(guān)系是三維曲面特征變化的一種表現(xiàn)形式,而剛性變換對(duì)曲率關(guān)系影響較小,因此曲率可以作為點(diǎn)云特征匹配的一個(gè)重要指標(biāo)形式。

本文主要以曲面的平均曲率關(guān)系作為初始特征點(diǎn)對(duì)匹配的依據(jù),設(shè)曲面S中某一點(diǎn)M處的平均曲率為Kn,其中,曲面S的表達(dá)形式如下:

z(x,y)=Ax2+By2+Cxy+Dx+Ey+F(3)

式(3)中各系數(shù)可以用一、二階導(dǎo)數(shù)表示:

(4)

(5)

(6)

(7)

(8)

可知,平均曲率Kn滿足公式:

(9)

U={(a1,b1),(a2,b2),…,(ai,bi)}

(10)

3 點(diǎn)云精確配準(zhǔn)

僅根據(jù)點(diǎn)間平均曲率關(guān)系進(jìn)行特征點(diǎn)粗匹配容易產(chǎn)生多種匹配點(diǎn)對(duì)結(jié)果,從而導(dǎo)致較大的配準(zhǔn)誤差,因此在粗匹配基礎(chǔ)上通常需要增加點(diǎn)間距離約束條件,剔除錯(cuò)誤匹配點(diǎn)對(duì)[15]。再依據(jù)邊界旋轉(zhuǎn)角約束旋轉(zhuǎn)矩陣及位移矢量,使用動(dòng)態(tài)迭代相關(guān)系數(shù)優(yōu)化剛性變換參數(shù),最終完成點(diǎn)云的精確配準(zhǔn)。

3.1 點(diǎn)間距離約束

在集U中任意取兩組點(diǎn)對(duì)(ai,bi)和(aj,bj),考慮到離散點(diǎn)云間一般無(wú)法完美匹配,因此通常取某一小的正臨界閾值點(diǎn)δb,滿足下式:

(11)

式中,dist( )表示歐式點(diǎn)間距離函數(shù)。

點(diǎn)云在坐標(biāo)尺度變換后,曲率關(guān)系相似點(diǎn)對(duì)之間的距離關(guān)系會(huì)維持在固定比例區(qū)間,依據(jù)這一特征,可以判定點(diǎn)對(duì)(ai,bi)和(aj,bj)是否符合點(diǎn)間距離比值約束條件,若符合則保留匹配點(diǎn)對(duì)；否則,剔除錯(cuò)誤點(diǎn)對(duì)關(guān)系,粗略對(duì)齊源點(diǎn)云和目標(biāo)點(diǎn)云的數(shù)據(jù)特征點(diǎn)。

3.2 邊界旋轉(zhuǎn)角

繞任意軸的三維旋轉(zhuǎn)可分解成單獨(dú)繞X、Y、Z單坐標(biāo)軸旋轉(zhuǎn)的疊加,若假定旋轉(zhuǎn)角分別為θx、θy、θz,則有如下旋轉(zhuǎn)矩陣關(guān)系:

(12)

(13)

(14)

分別求解X、Y、Z三個(gè)軸方向上的平均旋轉(zhuǎn)角度,記作Ex、Ey、Ez；估算X、Y、Z軸方向邊界偏差旋轉(zhuǎn)角,分別記作Δθx、Δθy、Δθz。將旋轉(zhuǎn)角的上、下邊界約束剛性變換矩陣,可得:

(15)

3.3 改進(jìn)ICP算法

綜合上述理論分析,本文基于法向量和邊界旋轉(zhuǎn)角融合的改進(jìn)ICP算法流程如圖2所示。

圖2 改進(jìn)ICP算法流程圖Fig.2 Improved ICP algorithm flow chart

算法大體步驟可描述為:

1)將利用點(diǎn)間約束條件匹配得到的精確點(diǎn)對(duì)作為初始狀態(tài),開(kāi)始進(jìn)行迭代運(yùn)算,令s=1；

2)估計(jì)三個(gè)坐標(biāo)軸方向的旋轉(zhuǎn)角邊界值,其中X軸旋轉(zhuǎn)邊界值[Ex-Δθx,Ex+Δθx],Y軸旋轉(zhuǎn)邊界值[Ey-Δθy,Ey+Δθy],Z軸旋轉(zhuǎn)邊界值[Ez-Δθz,Ez+Δθz]；

(16)

4)通過(guò)相關(guān)性{i,ds+1(i)},建立動(dòng)態(tài)迭代相關(guān)系數(shù)gs∈{1,2,3,…,ND},優(yōu)化剛性旋轉(zhuǎn)變換參數(shù)Rs和ts；

(17)

(18)

6)若|ds-ds-1|小于迭代收斂閾值δc或者大于算法預(yù)設(shè)的最大迭代次數(shù),則停止迭代運(yùn)算；否則令s=s+1,返回第三步,直到滿足循環(huán)跳出條件為止。

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

本文基于Windows 10 64位操作系統(tǒng),結(jié)合MATLAB R2015b完成三維點(diǎn)云模型的配準(zhǔn)仿真實(shí)驗(yàn)。為驗(yàn)證本文算法的改進(jìn)效果,實(shí)驗(yàn)過(guò)程將傳統(tǒng)ICP算法、文獻(xiàn)[4]提出的基于法向量改進(jìn)ICP算法和本文算法三種仿真實(shí)驗(yàn)結(jié)果進(jìn)行類(lèi)比研究。

仿真實(shí)驗(yàn)分別從斯坦福大學(xué)計(jì)算機(jī)圖形學(xué)實(shí)驗(yàn)室的開(kāi)放數(shù)據(jù)中,提取兔子點(diǎn)云RabbitBunny00、RabbitBunny45和椅子點(diǎn)云Chair01、Chair02做實(shí)驗(yàn)數(shù)據(jù)。其中,設(shè)定參數(shù)值:曲率搜索誤差閾值為du=0.003,法向量夾角特征提取閾值δa=0.005,點(diǎn)間距離約束條件下的閾值δb=0.002,算法收斂閾值δc=0.005,迭代次數(shù)達(dá)60次跳出迭代循環(huán)。

在兔子點(diǎn)云中提取法向量夾角特征,結(jié)合點(diǎn)面曲率對(duì)應(yīng)關(guān)系完成點(diǎn)云的初始配準(zhǔn),如圖3所示。

圖3 法向量夾角特征點(diǎn)匹配Fig.3 Normal vector angle feature point matching

在點(diǎn)間距離約束條件下對(duì)初始匹配點(diǎn)對(duì)進(jìn)一步約束,形成二次再匹配點(diǎn)對(duì)集結(jié)果,如圖4所示。

圖4 點(diǎn)間距離約束下的匹配點(diǎn)對(duì)Fig.4 Matching point pairs under the distance constraint between points

估算尺度變換矩陣旋轉(zhuǎn)角的邊界值,開(kāi)始運(yùn)行ICP算法迭代循環(huán),分別得到傳統(tǒng)ICP算法、文獻(xiàn)[4]提出的基于法向量改進(jìn)ICP算法以及本文改進(jìn)ICP算法的三條迭代誤差曲線,如圖5所示。

圖5 三種算法的迭代誤差曲線Fig.5 Iterative error curves of the three algorithms

可知,本文改進(jìn)的ICP算法迭代收斂速度最快、誤差最小。針對(duì)不同規(guī)模下的點(diǎn)云數(shù)據(jù),討論算法的點(diǎn)云配準(zhǔn)速度,三種ICP配準(zhǔn)算法所耗費(fèi)的時(shí)間如表1所示。

表1 不同ICP算法下的三維點(diǎn)云配準(zhǔn)時(shí)間Tab.1 3D point cloud registration time under different ICP algorithms

通過(guò)表1數(shù)據(jù)可知,本文改進(jìn)ICP配準(zhǔn)算法與傳統(tǒng)ICP算法相比,點(diǎn)云配準(zhǔn)時(shí)間減少50 %以上,點(diǎn)云配準(zhǔn)速度顯著提升。但與文獻(xiàn)[4]提出的改進(jìn)ICP算法相比,本文算法在低數(shù)據(jù)量點(diǎn)云配準(zhǔn)速率上存在些許不足。

依據(jù)MATLAB R2015b的仿真結(jié)果,從直觀角度來(lái)分析點(diǎn)云配準(zhǔn)的精度指標(biāo),兔子點(diǎn)云配準(zhǔn)效果對(duì)比情況如圖6所示。

針對(duì)Chair01和Chair02點(diǎn)云數(shù)據(jù),參數(shù)設(shè)定值不變,依據(jù)MATLAB R2015b的仿真結(jié)果,得到Chair三維點(diǎn)云配準(zhǔn)效果對(duì)比如圖7所示。

可知,本文算法在點(diǎn)云的配準(zhǔn)實(shí)現(xiàn)中,表現(xiàn)較好。從直觀角度可以看出,本文算法相比于傳統(tǒng)ICP算法和文獻(xiàn)[4]提出的改進(jìn)ICP算法,點(diǎn)云配準(zhǔn)結(jié)果的重合度更高,迭代精度更大。其中,仿真誤差結(jié)果以數(shù)據(jù)的具體形式如表2所示。

圖6 兔子點(diǎn)云配準(zhǔn)效果對(duì)比Fig.6 Comparison of rabbit point cloud registration effects

圖7 椅子點(diǎn)云配準(zhǔn)效果對(duì)比Fig.7 Comparison of the point cloud registration effect of the chair

表2 不同ICP算法下的點(diǎn)云配準(zhǔn)誤差Tab.2 Point cloud registration error under different ICP algorithms

可得,本文改進(jìn)的ICP算法針對(duì)上述兩類(lèi)實(shí)驗(yàn)點(diǎn)云數(shù)據(jù),點(diǎn)云配準(zhǔn)誤差降至3 mm以下,在點(diǎn)云配準(zhǔn)精度上大大優(yōu)于傳統(tǒng)ICP算法和文獻(xiàn)[4]提出的改進(jìn)ICP算法。

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

本文提出一種基于法向量特征和邊界旋轉(zhuǎn)角相結(jié)合的改進(jìn)ICP配準(zhǔn)算法,在點(diǎn)云區(qū)域?qū)宇I(lǐng)域采用點(diǎn)云劃分的方法,大大縮短大數(shù)據(jù)點(diǎn)云的配準(zhǔn)時(shí)間。在點(diǎn)云配準(zhǔn)過(guò)程中,首先搜尋點(diǎn)云格的法向量夾角特征,結(jié)合點(diǎn)面曲率對(duì)應(yīng)關(guān)系,確定點(diǎn)云初始配準(zhǔn)結(jié)果；隨后人為估算尺度變換矩陣的旋轉(zhuǎn)角度,結(jié)合相關(guān)迭代系數(shù)優(yōu)化尺度變換參數(shù),最終得到精確配準(zhǔn)點(diǎn)云結(jié)果。

通過(guò)實(shí)驗(yàn)表明,本文改進(jìn)算法在傳統(tǒng)ICP算法的基礎(chǔ)上,實(shí)現(xiàn)了對(duì)點(diǎn)云配準(zhǔn)準(zhǔn)確性和快速性的優(yōu)化處理。對(duì)20000數(shù)據(jù)量以上的點(diǎn)云,相比傳統(tǒng)ICP算法和文獻(xiàn)[4]提出的算法,本文算法是一種更為有效、快速、準(zhǔn)確的點(diǎn)云配準(zhǔn)算法。