張 梅 文靜華 張祖勛 張劍清

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

0 引言

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

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

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

1 初始位姿估計

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

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

2 三棱錐體積計算

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

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

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

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

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

本文改進(jìn)算法的目的就是要找到一種適合進(jìn)行空間位置關(guān)系變換的方法,使得兩個點(diǎn)云模型重疊區(qū)域間的三維空間最小。兩個點(diǎn)云模型重疊區(qū)域間點(diǎn)與對應(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個頂點(diǎn)mi之間的距離;Atri為對應(yīng)三角形的面積;hi為點(diǎn)云RP+t上頂點(diǎn)x到點(diǎn)云模型M上對應(yīng)三角形的3個頂點(diǎn)距離的均值。

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

3.1 基于平均三棱錐體積的誤差測度

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

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

基于平均三棱錐體積的誤差測度計算步驟如下:

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

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

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

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

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

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

(2)k=0,迭代開始:①k←k+1,對點(diǎn)云模型P中的所有點(diǎn)應(yīng)用轉(zhuǎn)換矩陣Tk—1(旋轉(zhuǎn)矩陣Rk—1 與平移向量tk—1)生成P=Rk—1P+tk—1;②計算Tk—1下點(diǎn)云模型M和P所夾三維空間的平均體積誤差測度E(Tk—1);③找到點(diǎn)云模型P中所有點(diǎn)在M上的最近對應(yīng)點(diǎn),并取所有對應(yīng)點(diǎn)對中距離最近的90%作為有效的對應(yīng)點(diǎn)對;④利用旋轉(zhuǎn)向量,按照Gelfand等[13]的方法線性化旋轉(zhuǎn)矩陣Rk,從而通過求解一個線性系統(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)平臺的中心,旋轉(zhuǎn)平臺每轉(zhuǎn)動10°,三維激光掃描儀 VIVID910掃描一次,分別獲取在旋轉(zhuǎn)角度為 0°、10°、20°、30°、…、350°時的掛鉤激光點(diǎn)云數(shù)據(jù)。實(shí)驗(yàn)?zāi)康脑谟趯σ来蜗噜徱朁c(diǎn)獲取的激光掃描數(shù)據(jù)進(jìn)行配準(zhǔn),驗(yàn)證本文提出的改進(jìn)迭代最近點(diǎn)算法的有效性、正確性和可行性,比較本文方法與以往方法的配準(zhǔn)精度與收斂速度,為后續(xù)曲面物體深度圖像的分割提供完整三維幾何模型。

首先對掛鉤的 36片激光點(diǎn)云用文獻(xiàn)[11,16-17]中的方法進(jìn)行平滑、濾波、去噪、簡化等數(shù)據(jù)預(yù)處理。然后選取角度為0°的位置作為空間參考坐標(biāo)系,依次對其他視角獲取的點(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)精度和時間效率與文獻(xiàn)[18]基于對應(yīng)點(diǎn)距離平方均值誤差測度的算法進(jìn)行比較。圖2a所示為位于初始位置0°、用三維激光掃描儀VIVID910得到的基準(zhǔn)點(diǎn)云模型,含有51 322個三維數(shù)據(jù)點(diǎn);圖2b所示為旋轉(zhuǎn)10°后用三維激光掃描儀VIVID910得到的點(diǎn)云模型,含有51 397個三維數(shù)據(jù)點(diǎn)。

圖3a所示為文獻(xiàn)[18]算法的配準(zhǔn)結(jié)果,該算法利用兩個三維點(diǎn)云模型之間的平均歐氏距離作為誤差測度。其中,圖3b所示為本文算法的配準(zhǔn)結(jié)果。對照圖2可以看出,圖3b的配準(zhǔn)結(jié)果要明顯優(yōu)于圖3a的配準(zhǔn)結(jié)果?；趯?yīng)點(diǎn)對距離的配準(zhǔn)算法往往陷入局部最優(yōu)而無法得到正確的空間變換關(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ī)上計算得到的,開發(fā)平臺是MATLAB7.0。

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

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

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

5 結(jié)束語

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

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

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

[3]朱延娟,周來水,張麗艷.散亂點(diǎn)云數(shù)據(jù)配準(zhǔn)算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,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ù)字化檢測技術(shù)研究[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]吳敏,周來水,王占東,等.測量點(diǎn)云數(shù)據(jù)的多視拼合技術(shù)研究[J].南京航空航天大學(xué)學(xué)報,2003,35(4):552-555.

[12]賈云得.機(jī)器視覺[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)距離圖像的對準(zhǔn)算法[J].中國科學(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]李劍.基于激光測量的自由曲面數(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.