基于表面間三棱錐體積測(cè)度的點(diǎn)云配準(zhǔn)

張 梅 文靜華 張祖勛 張劍清

1.貴州財(cái)經(jīng)學(xué)院,貴陽(yáng),550004 2.武漢大學(xué),武漢,430079

0 引言

三維激光掃描是近年來(lái)迅速發(fā)展起來(lái)的一種新型空間數(shù)據(jù)獲取手段和工具,在物體建模研究與應(yīng)用方面受到越來(lái)越廣泛的關(guān)注。隨著激光掃描技術(shù)的發(fā)展及成本的降低,這方面的研究受到越來(lái)越多的關(guān)注[1]。然而,由于激光掃描原理和物體本身形狀的限制,使得重建出一個(gè)準(zhǔn)確而高效的三維模型目前還存在著許多困難,其中之一便是點(diǎn)云的配準(zhǔn)。

在三維掃描過(guò)程中,許多因素決定了無(wú)法通過(guò)單個(gè)視覺(jué)傳感器一次掃描完成整個(gè)物體的測(cè)量。通常把物體表面分成多個(gè)局部相互重疊的子區(qū)域,從多個(gè)角度分別獲取它們的表面信息,從而得到多個(gè)獨(dú)立的三維點(diǎn)云,稱為多視(multi—view)點(diǎn)云。在掃描不同的子區(qū)域時(shí),所得三維點(diǎn)云在各自測(cè)量位置對(duì)應(yīng)的局部坐標(biāo)系下,而多次測(cè)量所對(duì)應(yīng)的局部坐標(biāo)系并不一致。把各次測(cè)量對(duì)應(yīng)的局部坐標(biāo)系統(tǒng)一到一個(gè)全局坐標(biāo)系下即為多視點(diǎn)云的配準(zhǔn)[2]。點(diǎn)云配準(zhǔn)有手動(dòng)配準(zhǔn)、依賴儀器的配準(zhǔn)和自動(dòng)配準(zhǔn)。通常我們所說(shuō)的點(diǎn)云配準(zhǔn)技術(shù)即是指最后一種[3]。點(diǎn)云自動(dòng)配準(zhǔn)技術(shù)是通過(guò)一定的算法或者統(tǒng)計(jì)學(xué)規(guī)律,利用計(jì)算機(jī)計(jì)算兩片點(diǎn)云之間的錯(cuò)位,從而達(dá)到把兩片點(diǎn)云自動(dòng)配準(zhǔn)的效果。

針對(duì)上述多視點(diǎn)云配準(zhǔn)方法的不足,本文提出一種基于離散對(duì)應(yīng)特征和表面間平均三棱錐體積誤差測(cè)度的改進(jìn)ICP算法來(lái)計(jì)算多視點(diǎn)云變換矩陣。先利用基于離散對(duì)應(yīng)特征點(diǎn)的方法求出一個(gè)初始的位姿,再使用基于表面間平均三棱錐體積誤差測(cè)度的改進(jìn)ICP算法進(jìn)行迭代求精。與傳統(tǒng)ICP算法的比較結(jié)果表明,本文改進(jìn)算法可以高效而精確地解算出點(diǎn)云模型配準(zhǔn)所需的各種坐標(biāo)變換參數(shù)。

1 初始位姿估計(jì)

利用離散的對(duì)應(yīng)特征進(jìn)行粗略配準(zhǔn)以估計(jì)初始位姿?；趯?duì)應(yīng)特征的配準(zhǔn)方法,就是先設(shè)法在兩個(gè)相鄰視圖的點(diǎn)云模型P和M(基準(zhǔn)點(diǎn)云模型)中找到n(n≥3)組特征對(duì)(或稱為對(duì)應(yīng)特征),每一組特征對(duì)都對(duì)應(yīng)了實(shí)際物體的同一特征。利用點(diǎn)云模型P中的n個(gè)特征(P1,P2,…,Pn)和點(diǎn)云模型M中的n個(gè)特征(M1,M2,…,Mn)的變換關(guān)系Mi=R0Pi+t0(i=1,2,…,n)來(lái)求解出剛性變換參數(shù)(R0,t0),從而實(shí)現(xiàn)粗略配準(zhǔn)。

一般常被選作對(duì)應(yīng)特征的幾何特征是點(diǎn)[11],首先用基于幾何特征的視覺(jué)技術(shù)目視判斷得到初值:如拐角、折痕、邊界,在兩個(gè)相鄰視圖的點(diǎn)云模型中手工指定n(n＞3)組對(duì)應(yīng)特征點(diǎn),然后通過(guò)一個(gè)線性最小二乘最優(yōu)化的過(guò)程求解出(R0,t0),最后將變換的(R0,t0)應(yīng)用到點(diǎn)云模型P上得到其剛性變換后的點(diǎn)云模型P′=R0×P+t0,從而將兩個(gè)點(diǎn)云模型P和M粗略配準(zhǔn)到同一坐標(biāo)系(M為基準(zhǔn)點(diǎn)云模型)。

2 三棱錐體積計(jì)算

誤差測(cè)度和有效點(diǎn)對(duì)的選擇策略對(duì)ICP算法的配準(zhǔn)精度和收斂速度有很大的影響[12-13],只有盡可能地排除偏離點(diǎn)的影響,定義一個(gè)能夠真正反映深度像重疊區(qū)域吻合程度的誤差測(cè)度,才能使算法具有更強(qiáng)的魯棒性,得到更加準(zhǔn)確的配準(zhǔn)結(jié)果?，F(xiàn)有的配準(zhǔn)算法[14-15]在誤差測(cè)度的選擇上始終都沒(méi)有跳出點(diǎn)對(duì)或者點(diǎn)面歐氏距離的范疇。本文提出另外一種衡量配準(zhǔn)誤差的概念:表面間平均三棱錐體積測(cè)度,將兩片激光點(diǎn)云重疊區(qū)域間的三維空間三棱錐體積作為誤差測(cè)度,并采用一種與之相匹配的點(diǎn)對(duì)選取策略完成三角網(wǎng)格的精確配準(zhǔn)。

點(diǎn)云模型配準(zhǔn)就是要找到輸入點(diǎn)云P和目標(biāo)點(diǎn)云 Μ之間的一個(gè)空間位置變換關(guān)系矩陣T(旋轉(zhuǎn)矩陣R與平移向量t),使得某種形式的誤差測(cè)度E在T下最小。目前,最常用的一種誤差測(cè)度方法,是由Besl等[4]提出的對(duì)應(yīng)點(diǎn)歐氏距離平方均值法:

式中,N為點(diǎn)云模型P上頂點(diǎn)的個(gè)數(shù)。

與式(1)中基于距離的誤差測(cè)度不同,本文提出了一種基于點(diǎn)云數(shù)據(jù)重疊區(qū)域間平均體積的誤差測(cè)度,如圖1所示。

2.拓寬企業(yè)融資渠道。深化債券市場(chǎng)融資功能，引導(dǎo)企業(yè)通過(guò)發(fā)行企業(yè)債、公司債、中期票據(jù)、資產(chǎn)支持票據(jù)、短期融資券、超短期融資券、項(xiàng)目收益?zhèn)热谫Y方式，擴(kuò)大融資規(guī)模；發(fā)揮政府投資引導(dǎo)基金作用，支持產(chǎn)業(yè)鏈核心企業(yè)發(fā)起、引導(dǎo)社會(huì)資本共同參與設(shè)立產(chǎn)業(yè)創(chuàng)投基金，為產(chǎn)業(yè)鏈上下游企業(yè)提供資金支持。鼓勵(lì)有條件的民營(yíng)企業(yè)聯(lián)合發(fā)起設(shè)立民營(yíng)資本投資公司。設(shè)立廣西并購(gòu)引導(dǎo)基金，推動(dòng)工業(yè)企業(yè)重組整合壯大。積極爭(zhēng)取投貸聯(lián)動(dòng)試點(diǎn)，大力推動(dòng)市場(chǎng)化法治化債轉(zhuǎn)股工作。

本文改進(jìn)算法的目的就是要找到一種適合進(jìn)行空間位置關(guān)系變換的方法,使得兩個(gè)點(diǎn)云模型重疊區(qū)域間的三維空間最小。兩個(gè)點(diǎn)云模型重疊區(qū)域間點(diǎn)與對(duì)應(yīng)三角形所夾的體積可以表示為

式中,x為點(diǎn)云RP+t上的頂點(diǎn);H(M,x)為點(diǎn)x到點(diǎn)云模型M上所有頂點(diǎn)歐氏距離的最小值;d(x,mi)(i=1,2,3)為頂點(diǎn)x到3個(gè)頂點(diǎn)mi之間的距離;Atri為對(duì)應(yīng)三角形的面積;hi為點(diǎn)云RP+t上頂點(diǎn)x到點(diǎn)云模型M上對(duì)應(yīng)三角形的3個(gè)頂點(diǎn)距離的均值。

3 改進(jìn)的迭代最近點(diǎn)(ICP)配準(zhǔn)算法

3.1 基于平均三棱錐體積的誤差測(cè)度

由式(2)可以定義誤差測(cè)度為

實(shí)驗(yàn)結(jié)果表明,式(3)定義的誤差測(cè)度具有較強(qiáng)的魯棒性和較高的配準(zhǔn)精度。

基于平均三棱錐體積的誤差測(cè)度計(jì)算步驟如下:

(1)根據(jù)體積最小原則,找到點(diǎn)云P上所有點(diǎn)在點(diǎn)云M上的對(duì)應(yīng)三角形。

(2)E(|T|)=0,N=0,對(duì)點(diǎn)云P上的每一個(gè)頂點(diǎn)x,①找到其對(duì)應(yīng)三角形上的每一個(gè)頂點(diǎn)m1、m2、m3,并計(jì)算頂點(diǎn) x到3個(gè)頂點(diǎn)之間的距離d(x,mi)(i=1,2,3)的值;②利用海倫公式:

根據(jù)邊長(zhǎng) a、b、c,求出m1、m2、m3所圍三角形面積

3.2 基于平均體積誤差測(cè)度的點(diǎn)云配準(zhǔn)

假設(shè)兩片點(diǎn)云數(shù)據(jù)向量P和M(將P配準(zhǔn)到M),配準(zhǔn)算法是首先利用基于離散對(duì)應(yīng)特征點(diǎn)的方法得到剛體變換的初始估計(jì)。然后對(duì)P應(yīng)用轉(zhuǎn)換關(guān)系矩陣T(旋轉(zhuǎn)矩陣R與平移向量t)生成P′;從P′中拾取一點(diǎn)p,到M中尋找與p最近的一點(diǎn)m,構(gòu)成點(diǎn)對(duì)(p,m),去除間距特別大的對(duì)應(yīng)點(diǎn)對(duì),去除有頂點(diǎn)位于點(diǎn)云模型邊界上的對(duì)應(yīng)點(diǎn)對(duì),最后形成有效點(diǎn)對(duì)集合(Ps,Ms);利用旋轉(zhuǎn)向量,按照Gelfand等[13]的方法線性化旋轉(zhuǎn)矩陣R,從而通過(guò)求解一個(gè)線性系統(tǒng)得到新的變換關(guān)系矩陣Tk。計(jì)算Ps與Ms所夾的三維空間平均體積測(cè)度誤差,如果小于設(shè)定的值則結(jié)束,否則進(jìn)行下次迭代。改進(jìn)的最近點(diǎn)迭代配準(zhǔn)算法步驟如下:

(1)利用基于離散對(duì)應(yīng)特征點(diǎn)的方法計(jì)算初始位姿(R0,t0)。

(2)k=0,迭代開(kāi)始:①k←k+1,對(duì)點(diǎn)云模型P中的所有點(diǎn)應(yīng)用轉(zhuǎn)換矩陣Tk—1(旋轉(zhuǎn)矩陣Rk—1 與平移向量tk—1)生成P=Rk—1P+tk—1;②計(jì)算Tk—1下點(diǎn)云模型M和P所夾三維空間的平均體積誤差測(cè)度E(Tk—1);③找到點(diǎn)云模型P中所有點(diǎn)在M上的最近對(duì)應(yīng)點(diǎn),并取所有對(duì)應(yīng)點(diǎn)對(duì)中距離最近的90%作為有效的對(duì)應(yīng)點(diǎn)對(duì);④利用旋轉(zhuǎn)向量,按照Gelfand等[13]的方法線性化旋轉(zhuǎn)矩陣Rk,從而通過(guò)求解一個(gè)線性系統(tǒng)得到新的變換關(guān)系矩陣Tk,直到 E(|Tk—5|)—E(|Tk|)≤10—4或者k=kend,迭代終止。

(3)輸出最優(yōu)的變換關(guān)系Tk=(Rk,tk)。

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

將掛鉤放在旋轉(zhuǎn)平臺(tái)的中心,旋轉(zhuǎn)平臺(tái)每轉(zhuǎn)動(dòng)10°,三維激光掃描儀 VIVID910掃描一次,分別獲取在旋轉(zhuǎn)角度為 0°、10°、20°、30°、…、350°時(shí)的掛鉤激光點(diǎn)云數(shù)據(jù)。實(shí)驗(yàn)?zāi)康脑谟趯?duì)依次相鄰視點(diǎn)獲取的激光掃描數(shù)據(jù)進(jìn)行配準(zhǔn),驗(yàn)證本文提出的改進(jìn)迭代最近點(diǎn)算法的有效性、正確性和可行性,比較本文方法與以往方法的配準(zhǔn)精度與收斂速度,為后續(xù)曲面物體深度圖像的分割提供完整三維幾何模型。

首先對(duì)掛鉤的 36片激光點(diǎn)云用文獻(xiàn)[11,16-17]中的方法進(jìn)行平滑、濾波、去噪、簡(jiǎn)化等數(shù)據(jù)預(yù)處理。然后選取角度為0°的位置作為空間參考坐標(biāo)系,依次對(duì)其他視角獲取的點(diǎn)云數(shù)據(jù)配準(zhǔn)到該參考坐標(biāo)系。將多視角點(diǎn)云模型的配準(zhǔn)轉(zhuǎn)化成依次進(jìn)行的兩兩配準(zhǔn),并按照本文的改進(jìn)算法完成。

限于篇幅,只用初始位置0°(基準(zhǔn)模型)和旋轉(zhuǎn)10°兩視角的點(diǎn)云模型進(jìn)行配準(zhǔn),并將其配準(zhǔn)結(jié)果、配準(zhǔn)精度和時(shí)間效率與文獻(xiàn)[18]基于對(duì)應(yīng)點(diǎn)距離平方均值誤差測(cè)度的算法進(jìn)行比較。圖2a所示為位于初始位置0°、用三維激光掃描儀VIVID910得到的基準(zhǔn)點(diǎn)云模型,含有51 322個(gè)三維數(shù)據(jù)點(diǎn);圖2b所示為旋轉(zhuǎn)10°后用三維激光掃描儀VIVID910得到的點(diǎn)云模型,含有51 397個(gè)三維數(shù)據(jù)點(diǎn)。

圖3a所示為文獻(xiàn)[18]算法的配準(zhǔn)結(jié)果,該算法利用兩個(gè)三維點(diǎn)云模型之間的平均歐氏距離作為誤差測(cè)度。其中,圖3b所示為本文算法的配準(zhǔn)結(jié)果。對(duì)照?qǐng)D2可以看出,圖3b的配準(zhǔn)結(jié)果要明顯優(yōu)于圖3a的配準(zhǔn)結(jié)果?；趯?duì)應(yīng)點(diǎn)對(duì)距離的配準(zhǔn)算法往往陷入局部最優(yōu)而無(wú)法得到正確的空間變換關(guān)系,而本文算法卻可以得到比較精確的配準(zhǔn)結(jié)果。

圖4所示為圖3中兩種配準(zhǔn)算法收斂速度的比較。由于配準(zhǔn)誤差的單位不一樣(本文算法的單位是mm3,文獻(xiàn)[18]算法的單位是mm),因此分別在兩幅圖中顯示了兩種算法迭代100次的誤差分布。表1所示為圖3中配準(zhǔn)結(jié)果的定量比較,這些結(jié)果是在Pentium Ⅳ,2.66GHz CPU,960MB內(nèi)存的PC機(jī)上計(jì)算得到的,開(kāi)發(fā)平臺(tái)是MATLAB7.0。

由于利用海倫公式求解三角形面積需要更多的計(jì)算,因此本文算法每一次迭代的運(yùn)行時(shí)間會(huì)略長(zhǎng)。然而,如表1中有效點(diǎn)對(duì)數(shù)量的統(tǒng)計(jì),由于滿足條件的三角形對(duì)的數(shù)量要遠(yuǎn)遠(yuǎn)小于對(duì)應(yīng)點(diǎn)對(duì)的數(shù)量,因此,本文算法只需較少的時(shí)間就可以計(jì)算出新的空間位置變換關(guān)系,從而保證了每一次迭代的運(yùn)行時(shí)間和文獻(xiàn)[18]算法相比差距不大,再考慮迭代次數(shù),顯然本文算法具有更快的收斂速度。

表1 圖3中配準(zhǔn)結(jié)果的定量比較

圖5所示是按照本文改進(jìn)算法和實(shí)驗(yàn)方法依次完成所有36個(gè)掛鉤點(diǎn)云模型兩兩配準(zhǔn)后,得到的完整掛鉤多視角點(diǎn)云模型配準(zhǔn)融合三維幾何曲面模型。

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

本文在分析了現(xiàn)有點(diǎn)云模型配準(zhǔn)方法的基礎(chǔ)上,提出了一種基于表面間點(diǎn)與對(duì)應(yīng)三角形所夾三棱錐平均體積誤差測(cè)度的三角網(wǎng)格精確配準(zhǔn)算法,與現(xiàn)有ICP框架下的迭代配準(zhǔn)方法相比,該算法主要有兩個(gè)貢獻(xiàn):一是提出了表面間平均體積測(cè)度的概念,該測(cè)度衡量的不是對(duì)應(yīng)點(diǎn)對(duì)或者點(diǎn)面之間的歐氏距離,而是點(diǎn)與對(duì)應(yīng)三角形所夾三棱錐的平均體積;二是采用一種與表面間平均體積測(cè)度相匹配的選點(diǎn)策略,通過(guò)從點(diǎn)與對(duì)應(yīng)三角形的質(zhì)心所形成的點(diǎn)對(duì)中選取最近對(duì)應(yīng)點(diǎn)對(duì),有效地排除了偏離點(diǎn)的影響,確保了算法的精度和速度。

[1]戴靜蘭,陳志楊,葉修梓.ICP算法在點(diǎn)云配準(zhǔn)中的應(yīng)用[J].中國(guó)圖像圖形學(xué)報(bào),2007,12(3):517-521.

[2]路銀北,張蕾,普杰信,等.基于曲率的點(diǎn)云數(shù)據(jù)配準(zhǔn)算法[J].計(jì)算機(jī)應(yīng)用,2007,27(11):2766-2769.

[3]朱延娟,周來(lái)水,張麗艷.散亂點(diǎn)云數(shù)據(jù)配準(zhǔn)算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2006,18(4):475-480.

[4]Besl P J,McKay N D.A Method for Registration of 3—D Shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256.

[5]Chen Y,Medioni G.Object Modeling by Registration of Multiple Range Images[C]//Proceedings of IEEE International Conference on Robotics and Automation.Sacramento,CA,1991:2724-2729.

[6]Blais G,Levine M D.Registering Multi—view Range Data to Create 3D Computer Graphics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(8):820-824.

[7]Li Q,Griffiths J G.Iterative Closest Geometric Objects Registration[J].Computers and Mathematics with Applications,2000,40(10):1171-1188.

[8]張學(xué)昌,習(xí)俊通,嚴(yán)雋琪.基于點(diǎn)云數(shù)據(jù)的復(fù)雜型面數(shù)字化檢測(cè)技術(shù)研究[J].計(jì)算機(jī)集成制造系統(tǒng)—CIMS,2005,11(5):727-731.

[9]Helmut P,Stdfan L,Michael H.Registration without ICP[J].Computer Vision and Image Understanding,2004,95:54-71.

[10]Masuda T,Sakaue K,Yokoya N.Registration and Integration of M ultiple Range Images for 3—D Model Construction[C]//Proceedings of the 13th International Conference on Pattenrn Recognition.Vienna,1996:879-883.

[11]吳敏,周來(lái)水,王占東,等.測(cè)量點(diǎn)云數(shù)據(jù)的多視拼合技術(shù)研究[J].南京航空航天大學(xué)學(xué)報(bào),2003,35(4):552-555.

[12]賈云得.機(jī)器視覺(jué)[M].北京:科學(xué)出版社,2000.

[13]Gelfand N,Ikemoto L,Rusinkiewicz S,et al.Geometrically Stable Sampling for the ICP Algorithm[C]//Proceedings of the 4th International Conference on 3D Digital Imaging and Modeling.Banff,2003:260-267.

[14]張鴻賓,謝豐.基于表面間距離度量的多視點(diǎn)距離圖像的對(duì)準(zhǔn)算法[J].中國(guó)科學(xué) E輯:信息科學(xué),2005,35(2):150-160.

[15]Turk G,Levoy M.Zipped Polygon Meshes from Range Image[C]//Proceedings of ACM,Siggraph.Orlando,1994:311-318.

[16]李劍.基于激光測(cè)量的自由曲面數(shù)字制造基礎(chǔ)技術(shù)研究[D].杭州:浙江大學(xué),2001.

[17]Dalley G,Flynn P.Range Image Registration:a Software Platform and Empirical Evaluation[C]//Proceedings of the 3rd International Conference on 3D Digital Imaging and Modeling.Quebec,2001:246-253.

[18]Pulli K.Multi—view Registration for Large Data Sets[C]//Proceedings the 2nd International Conference on 3D Digital Imaging and Modeling.Ottawa,1999:160—168.